OMOscar Morales-Ponce

Oscar Morales-Ponce

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Oscar Morales-Ponce has a total of 12 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Multimodal Search on a Line

    by Jared Coleman, Dmitry Ivanov, Evangelos Kranakis, Danny Krizanc, Oscar Morales Ponce


  • Open Access

    Linear Search with Probabilistic Detection and Variable Speeds

    by Jared Coleman, Oscar Morales-Ponce

    We present results on new variants of the famous linear search (or cow-path) problem that involves an agent searching for a target with unknown position on the infinite line. We consider the variant where the agent can move either at speed $1$ or at a slower speed $v \in [0, 1)$. When traveling at the slower speed $v$, the agent is guaranteed to detect the target upon passing through its location. When traveling at speed $1$, however, the agent, upon passing through the target's location, detects it with probability $p \in [0, 1]$. We present algorithms and provide upper bounds for the competitive ratios for three cases separately: when $p=0$, $v=0$, and when $p,v \in (0,1)$. We also prove that the provided algorithm for the $p=0$ case is optimal.

  • Linear Search for an Escaping Target with Unknown Speed

    by Jared Coleman, Dmitry Ivanov, Evangelos Kranakis, Danny Krizanc, Oscar Morales-Ponce


  • Open Access

    Linear Search for an Escaping Target with Unknown Speed

    by Jared Coleman, Dmitry Ivanov, Evangelos Kranakis, Danny Krizanc, Oscar Morales-Ponce

    We consider linear search for an escaping target whose speed and initial position are unknown to the searcher. A searcher (an autonomous mobile agent) is initially placed at the origin of the real line and can move with maximum speed $1$ in either direction along the line. An oblivious mobile target that is moving away from the origin with an unknown constant speed $v<1$ is initially placed by an adversary on the infinite line at distance $d$ from the origin in an unknown direction. We consider two cases, depending on whether $d$ is known or unknown. The main contribution of this paper is to prove a new lower bound and give algorithms leading to new upper bounds for search in these settings. This results in an optimal (up to lower order terms in the exponent) competitive ratio in the case where $d$ is known and improved upper and lower bounds for the case where $d$ is unknown. Our results solve an open problem proposed in [Coleman et al., Proc. OPODIS 2022].

  • Open Access

    The Snow Plow Problem: Perpetual Maintenance by Mobile Agents on the Line

    by Jared Coleman, Oscar Morales-Ponce

    We propose and study a new perpetual maintenance problem: The Snow Plow Problem. Inspired by snow removal in urban environments, we consider the perpetual maintenance by n mobile agents of a fixed-length interval over which some resource accumulates continuously over time (i.e. snow). In order to maintain the interval, agents must traverse it, collecting accumulated resources by plowing over continuous segments, and then return to some predefined destination point on the interval to dump collected resources. In a sense, our problem can be described as a combination of the well-studied patrolling and delivery problems. The maintenance cost for an agent is some combination of the distance traveled and the volume of resources collected between visits to the destination. We first study the case where the maintenance cost is simply the maximum amount of snow each agent must carry at any point in time and provide an optimal O(n) algorithm for computing optimal trajectories for the mobile agents for scenarios where the destination is at an endpoint and snow falls uniformly across the interval. Then, we generalize the problem for any maintenance cost which can be expressed as the product of a positive, non-decreasing travel cost function f(x) (the cost to travel to a distance x) and a positive resource cost function g(x) such that represents the volume of snowfall in one unit of time in the sub-interval (y, z]⊆(0, 1]. We provide a (1 + ϵ)-approximation algorithm that runs in O(nlog 1/ϵ) time and an exact O(n) algorithm for the case where f(x) = ax and g(x) = b for some positive constants a and b. Finally, we generalize further to consider scenarios where the destination is at any point along the interval, providing another (1 + ϵ)-approximation algorithm which runs in O(nlog 1/ϵ) time.

  • Delivery to Safety with Two Cooperating Robots

    by Jared Coleman, Evangelos Kranakis, Danny Krizanc, Oscar Morales-Ponce


  • Computing the Optimal Longest Queue Length in Torus Networks

    by Mehrdad Aliasgari, Burkhard Englert, Oscar Morales-Ponce

  • Open Access

    Synchronous Robotic Framework

    by Nagarathna Hema Balaji, Jyothsna Kilaru, Oscar Morales-Ponce

    We present a synchronous robotic testbed called SyROF that allows fast implementation of robotic swarms. Our main goal is to lower the entry barriers to cooperative-robot systems for undergraduate and graduate students. The testbed provides a high-level programming environment that allows the implementation of Timed Input/Output Automata (TIOA). SyROF offers the following unique characteristics: 1) a transparent mechanism to synchronize robot maneuvers, 2) a membership service with a failure detector, and 3) a transparent service to provide common knowledge in every round. These characteristics are fundamental to simplifying the implementation of robotic swarms. The software is organized in five layers: The lower layer consists of a real-time publish-subscribe system that allows efficient communication between tasks. The next layer is an implementation of a Kalman filter to estimate the position, orientation, and speed of the robot. The third layer consists of a synchronizer that synchronously executes the robot maneuvers, provides common knowledge to all the active participants, and handles failures. The fifth layer consists of the programming environment.

  • Open Access

    How to Stop Disagreeing and Start Cooperatingin the Presence of Asymmetric Packet Loss

    by Oscar Morales-Ponce, Elad M. Schiller, Paolo Falcone

    We consider the design of a disagreement correction protocol in multi-vehicle systems. Vehicles broadcast in real-time vital information such as position, direction, speed, acceleration, intention, etc. This information is then used to identify the risks and adapt their trajectory to maintain the highest performance without compromising the safety. To minimize the risk due to the use of inconsistent information, all cooperating vehicles must agree whether to use the exchanged information to operate in a cooperative mode or use the only local information to operate in an autonomous mode. However, since wireless communications are prone to failures, it is impossible to deterministically reach an agreement. Therefore, any protocol will exhibit necessary disagreement periods. In this paper, we investigate whether vehicles can still cooperate despite communication failures even in the scenario where communication is suddenly not available. We present a deterministic protocol that allows all participants to either operate a cooperative mode when vehicles can exchange all the information in a timely manner or operate in autonomous mode when messages are lost. We show formally that the disagreement time is bounded by the time that the communication channel requires to deliver messages and validate our protocol using NS-3 simulations. We explain how the proposed solution can be used in vehicular platooning to attain high performance and still guarantee high safety standards despite communication failures.