Oscar Morales-Ponce
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:
- Jared Coleman
Loyola Marymount University
7 shared publications - Danny Krizanc
Wesleyan University
4 shared publications - Evangelos Kranakis
Carleton University, Ottawa, Ontario, Canada
4 shared publications - Dmitry Ivanov
Carleton University
3 shared publications Burkhard Englert
University of North Caroline Wilmington
1 shared publication- Burkhard Englert
Department of Engineering and Computer Science California State University Long Beach
1 shared publication
Latest Publications
- 18 July 2025
- Published by Springer Nature
- p. 433-445
Linear Search with Probabilistic Detection and Variable Speeds
- 18 July 2025
- Published by Springer Nature
- p. 433-445
Linear Search with Probabilistic Detection and Variable Speeds
- Open Access
Linear Search with Probabilistic Detection and Variable Speeds
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.Open AccessLinear Search with Probabilistic Detection and Variable Speeds
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. - 22 June 2024
- Published by Springer Nature
- p. 396-407
Linear Search for an Escaping Target with Unknown Speed
- 22 June 2024
- Published by Springer Nature
- p. 396-407
Linear Search for an Escaping Target with Unknown Speed
- Open Access
Linear Search for an Escaping Target with Unknown Speed
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 AccessLinear Search for an Escaping Target with Unknown Speed
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
- 4 January 2023
- Published by Association for Computing Machinery (ACM)
- p. 110-114
The Snow Plow Problem: Perpetual Maintenance by Mobile Agents on the Line
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.
- 4 January 2023
- Published by Association for Computing Machinery (ACM)
- p. 110-114
Open AccessThe Snow Plow Problem: Perpetual Maintenance by Mobile Agents on the Line
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.
- 4 November 2021
- Published by Springer Nature
- p. 3-14
Computing the Optimal Longest Queue Length in Torus Networks
- 4 November 2021
- Published by Springer Nature
- p. 3-14
Computing the Optimal Longest Queue Length in Torus Networks
- Open Access
Synchronous Robotic Framework
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 AccessSynchronous Robotic Framework
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
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.
Open AccessHow to Stop Disagreeing and Start Cooperatingin the Presence of Asymmetric Packet Loss
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.