articles+ search results

Computer Science - Distributed, Parallel, and Cluster Computing

Two autonomous mobile robots and a non-autonomous one, also called bike, are placed at the origin of an infinite line. The autonomous robots can travel with maximum speed $1$. When a robot rides the bike its speed increases to $v>1$, however only exactly one robot at a time can ride the bike and the bike is non-autonomous in that it cannot move on its own. An Exit is placed on the line at an unknown location and at distance $d$ from the origin. The robots have limited communication behavior; one robot is a sender (denoted by S) in that it can send information wirelessly at any distance and receive messages only in F2F (Face-to-Face), while the other robot is a receiver (denoted by R) in that it can receive information wirelessly but can send information only F2F. The bike has no communication capabilities of its own. We refer to the resulting communication model of the ensemble of the two autonomous robots and the bike as S/R. Our general goal is to understand the impact of the non-autonomous robot in assisting the evacuation of the two autonomous faulty robots. Our main contribution is to provide a new evacuation algorithm that enables both robots to evacuate from the unknown Exit in the S/R model. We also analyze the resulting evacuation time as a function of the bike's speed $v$ and give upper and lower bounds on the competitive ratio of the resulting algorithm for the entire range of possible values of $v$.

Computer Science - Data Structures and Algorithms and Computer Science - Discrete Mathematics

We consider search by mobile agents for a hidden, idle target, placed on the infinite line. Feasible solutions are agent trajectories in which all agents reach the target sooner or later. A special feature of our problem is that the agents are $p$-faulty, meaning that every attempt to change direction is an independent Bernoulli trial with known probability $p$, where $p$ is the probability that a turn fails. We are looking for agent trajectories that minimize the worst-case expected termination time, relative to competitive analysis. First, we study linear search with one deterministic $p$-faulty agent, i.e., with no access to random oracles, $p\in (0,1/2)$. For this problem, we provide trajectories that leverage the probabilistic faults into an algorithmic advantage. Our strongest result pertains to a search algorithm (deterministic, aside from the adversarial probabilistic faults) which, as $p\to 0$, has optimal performance $4.59112+\epsilon$, up to the additive term $\epsilon$ that can be arbitrarily small. Additionally, it has performance less than $9$ for $p\leq 0.390388$. When $p\to 1/2$, our algorithm has performance $\Theta(1/(1-2p))$, which we also show is optimal up to a constant factor. Second, we consider linear search with two $p$-faulty agents, $p\in (0,1/2)$, for which we provide three algorithms of different advantages, all with a bounded competitive ratio even as $p\rightarrow 1/2$. Indeed, for this problem, we show how the agents can simulate the trajectory of any $0$-faulty agent (deterministic or randomized), independently of the underlying communication model. As a result, searching with two agents allows for a solution with a competitive ratio of $9+\epsilon$, or a competitive ratio of $4.59112+\epsilon$. Our final contribution is a novel algorithm for searching with two $p$-faulty agents that achieves a competitive ratio $3+4\sqrt{p(1-p)}$.

Quantum Physics and Computer Science - Emerging Technologies

Entanglement distribution is a core mechanism for the future quantum Internet. The quantum world is, however, a faulty environment. Hence, successful entanglement swapping is error-prone. The occurrence of quantum state errors can be mitigated using purification and error correction, which can be repeated in the former case and concatenated in the latter case. Repeated purification merges low-fidelity qubits into higher-quality ones, while concatenated error correction builds upon the redundancy of quantum information. In this article, we study in-depth and compare the two options: repeated purification and concatenated error correction. We consider using repeated purification and concatenated error correction to mitigate the presence of faults that occur during the establishment of Bell pairs between remote network nodes. We compare their performance versus the number of repetitions or concatenations, to reach a certain level of fidelity in quantum networks. We study their resource requirements, namely, their work memory complexity (e.g., number of stored qubits) and operational complexity (e.g., number of operations). Our analysis demonstrates that concatenated error correction, versus repeated purification, requires fewer iterations and has lower operational complexity than repeated purification to reach high fidelity at the expense of increased memory requirements.
Comment: ACM Format, 21 pages, 14 figures, 1 table

Computer Science - Distributed, Parallel, and Cluster Computing and Computer Science - Discrete Mathematics

Consider search on an infinite line involving an autonomous robot starting at the origin of the line and an oblivious moving target at initial distance $d \geq 1$ from it. The robot can change direction and move anywhere on the line with constant maximum speed $1$ while the target is also moving on the line with constant speed $v>0$ but is unable to change its speed or direction. The goal is for the robot to catch up to the target in as little time as possible. The classic case where $v=0$ and the target's initial distance $d$ is unknown to the robot is the well-studied ``cow-path problem''. Alpert and Gal gave an optimal algorithm for the case where a target with unknown initial distance $d$ is moving away from the robot with a known speed $v<1$. In this paper we design and analyze search algorithms for the remaining possible knowledge situations, namely, when $d$ and $v$ are known, when $v$ is known but $d$ is unknown, when $d$ is known but $v$ is unknown, and when both $v$ and $d$ are unknown. Furthermore, for each of these knowledge models we consider separately the case where the target is moving away from the origin and the case where it is moving toward the origin. We design algorithms and analyze competitive ratios for all eight cases above. The resulting competitive ratios are shown to be optimal when the target is moving towards the origin as well as when $v$ is known and the target is moving away from the origin.

Electrical Engineering and Systems Science - Systems and Control

The recent drastic increase in mobile data traffic has pushed the mobile edge computing systems to the limit of their capacity. A promising solution to this problem is the task migration provided by unmanned aerial vehicles (UAV). Key factors to be taken into account in the design of UAV offloading schemes must include the number of tasks waiting in the system as well as their corresponding deadlines. An appropriate system cost which is used as an objective function to be minimized comprises two parts. First, an offloading cost which can be interpreted as the cost of using computational resources at the UAV. Second, a penalty cost due to potential task expiration. In order to minimize the expected (time average) cost over a time horizon, we formulate a Dynamic Programming (DP) equation and analyze it to describe properties of a candidate optimal offloading policy. The DP equation suffers from the well-known "Curse of Dimensionality" that makes computations intractable, especially when the state space is infinite. In order to reduce the computational burden, we identify three important properties of the optimal policy. Based on these properties, we show that it suffices to evaluate the DP equation on a finite subset of the state space only. We then show that the optimal task offloading decision associated with a state can be inferred from the decision taken at its "adjacent" states, further reducing the computational load. Finally, we provide numerical results to evaluate the influence of different parameters on the system performance as well as verify the theoretical results.

Electrical Engineering and Systems Science - Systems and Control

As the automotive industry is developing autonomous driving systems and vehicular networks, attention to truck platooning has increased as a way to reduce costs (fuel consumption) and improve efficiency in the highway. Recent research in this area has focused mainly on the aerodynamics, network stability, and longitudinal control of platoons. However, the system aspects (e.g., platoon coordination) are still not well explored. In this paper, we formulate a platooning coordination problem and study whether trucks waiting at an initial location (station) should wait for a platoon to arrive in order to leave. Arrivals of trucks at the station and platoons by the station are modelled by independent Bernoulli distributions. Next we use the theory of Markov Decision Processes to formulate the dispatching control problem and derive the optimal policy governing the dispatching of trucks with platoons. We show that the policy that minimizes an average cost function at the station is of threshold type. Numerical results for the average cost case are presented. They are consistent with the optimal ones.

Computer Science - Distributed, Parallel, and Cluster Computing

Two cooperating, autonomous mobile robots with arbitrary nonzero max speeds are placed at arbitrary initial positions in the plane. A remotely detonated bomb is discovered at some source location and must be moved to a safe distance away from its initial location as quickly as possible. In the Bomb Squad problem, the robots cooperate by communicating face-to-face in order to pick up the bomb from the source and carry it away to the boundary of a disk centered at the source in the shortest possible time. The goal is to specify trajectories which define the robots' paths from start to finish and their meeting points which enable face-to-face collaboration by exchanging information and passing the bomb from robot to robot. We design algorithms reflecting the robots' knowledge about orientation and each other's speed and location. In the offline case, we design an optimal algorithm. For the limited knowledge cases, we provide online algorithms which consider robots' level of agreement on orientation as per OneAxis and NoAxis models, and knowledge of the boundary as per Visible, Discoverable, and Invisible. In all cases, we provide upper and lower bounds for the competitive ratios of the online problems.

Computer Science - Data Structures and Algorithms

We consider evacuation of a group of $n \geq 2$ autonomous mobile agents (or robots) from an unknown exit on an infinite line. The agents are initially placed at the origin of the line and can move with any speed up to the maximum speed $1$ in any direction they wish and they all can communicate when they are co-located. However, the agents have different wireless communication abilities: while some are fully wireless and can send and receive messages at any distance, a subset of the agents are senders, they can only transmit messages wirelessly, and the rest are receivers, they can only receive messages wirelessly. The agents start at the same time and their communication abilities are known to each other from the start. Starting at the origin of the line, the goal of the agents is to collectively find a target/exit at an unknown location on the line while minimizing the evacuation time, defined as the time when the last agent reaches the target. We investigate the impact of such a mixed communication model on evacuation time on an infinite line for a group of cooperating agents. In particular, we provide evacuation algorithms and analyze the resulting competitive ratio ($CR$) of the evacuation time for such a group of agents. If the group has two agents of two different types, we give an optimal evacuation algorithm with competitive ratio $CR=3+2 \sqrt{2}$. If there is a single sender or fully wireless agent, and multiple receivers we prove that $CR \in [2+\sqrt{5},5]$, and if there are multiple senders and a single receiver or fully wireless agent, we show that $CR \in [3,5.681319]$. Any group consisting of only senders or only receivers requires competitive ratio 9, and any other combination of agents has competitive ratio 3.

Computer Science - Distributed, Parallel, and Cluster Computing and Computer Science - Discrete Mathematics

We study a fundamental cooperative message-delivery problem on the plane. Assume $n$ robots which can move in any direction, are placed arbitrarily on the plane. Robots each have their own maximum speed and can communicate with each other face-to-face (i.e., when they are at the same location at the same time). There are also two designated points on the plane, $S$ (the source) and $D$ (the destination). The robots are required to transmit the message from the source to the destination as quickly as possible by face-to-face message passing. We consider both the offline setting where all information (the locations and maximum speeds of the robots) are known in advance and the online setting where each robot knows only its own position and speed along with the positions of $S$ and $D$. In the offline case, we discover an important connection between the problem for two-robot systems and the well-known Apollonius circle which we employ to design an optimal algorithm. We also propose a $\sqrt 2$ approximation algorithm for systems with any number of robots. In the online setting, we provide an algorithm with competitive ratio $\frac 17 \left( 5+ 4 \sqrt{2} \right)$ for two-robot systems and show that the same algorithm has a competitive ratio less than $2$ for systems with any number of robots. We also show these results are tight for the given algorithm. Finally, we give two lower bounds (employing different arguments) on the competitive ratio of any online algorithm, one of $1.0391$ and the other of $1.0405$.

Computer Science - Distributed, Parallel, and Cluster Computing and Computer Science - Discrete Mathematics

We introduce a new problem which we call the Pony Express problem. n robots with differing speeds are situated over some domain. A message is placed at some commonly known point. Robots can acquire the message either by visiting its initial position, or by encountering another robot that has already acquired it. The robots must collaborate to deliver the message to a given destination. The objective is to deliver the message in minimum time. In this paper we study the Pony Express problem on the line where n robots are arbitrarily deployed along a finite segment. The robots have different speeds and can move in both directions. We are interested in both offline centralized and online distributed algorithms. In the online case, we assume the robots have limited knowledge of the initial configuration. In particular, the robots do not know the initial positions and speeds of the other robots nor even their own position and speed. They do, however, know the direction on the line in which to find the message and have the ability to compare speeds when they meet. First, we study the Pony Express problem where the message is initially placed at one endpoint of a segment and must be delivered to the other endpoint. We provide an O(n log n) running time offline algorithm as well as an optimal online algorithm. Then we study the Half-Broadcast problem where the message is at the center and must be delivered to either one of the endpoints of the segment [-1,1]. We provide an offline algorithm running in O(n^2 log n) time and we provide an online algorithm that attains a competitive ratio of 3/2 which we show is the best possible. Finally, we study the Broadcast problem where the message is at the center and must be delivered to both endpoints of the segment [-1,1]. Here we give an FPTAS in the offline case and an online algorithm that attains a competitive ratio of 9/5, which we show is tight.
Comment: 14 pages, 3 figures to be published in IWOCA 2021

Computer Science - Computational Geometry and Computer Science - Robotics

In the pattern formation problem, robots in a system must self-coordinate to form a given pattern, regardless of translation, rotation, uniform-scaling, and/or reflection. In other words, a valid final configuration of the system is a formation that is \textit{similar} to the desired pattern. While there has been no shortage of research in the pattern formation problem under a variety of assumptions, models, and contexts, we consider the additional constraint that the maximum distance traveled among all robots in the system is minimum. Existing work in pattern formation and closely related problems are typically application-specific or not concerned with optimality (but rather feasibility). We show the necessary conditions any optimal solution must satisfy and present a solution for systems of three robots. Our work also led to an interesting result that has applications beyond pattern formation. Namely, a metric for comparing two triangles where a distance of $0$ indicates the triangles are similar, and $1$ indicates they are \emph{fully dissimilar}.
Comment: 13 pages

Computer Science - Data Structures and Algorithms, F.1.1, and F.2.2

Assume that $m \geq 1$ autonomous mobile agents and $0 \leq b \leq m$ single-agent transportation devices (called {\em bikes}) are initially placed at the left endpoint $0$ of the unit interval $[0,1]$. The agents are identical in capability and can move at speed one. The bikes cannot move on their own, but any agent riding bike $i$ can move at speed $v_i > 1$. An agent may ride at most one bike at a time. The agents can cooperate by sharing the bikes; an agent can ride a bike for a time, then drop it to be used by another agent, and possibly switch to a different bike. We study two problems. In the \BS problem, we require all agents and bikes starting at the left endpoint of the interval to reach the end of the interval as soon as possible. In the \RBS problem, we aim to minimize the arrival time of the agents; the bikes can be used to increase the average speed of the agents, but are not required to reach the end of the interval. Our main result is the construction of a polynomial time algorithm for the \BS problem that creates an arrival-time optimal schedule for travellers and bikes to travel across the interval. For the \RBS problem, we give an algorithm that gives an optimal solution for the case when at most one of the bikes can be abandoned.

Computer Science - Robotics and Electrical Engineering and Systems Science - Systems and Control

We present an error tolerant path planning algorithm for Micro Aerial Vehicle (MAV) swarms. We assume navigation without GPS-like techniques. The MAVs find their path using sensors and cameras, identifying and following a series of visual landmarks. The visual landmarks lead the MAVs towards their destination. MAVs are assumed to be unaware of the terrain and locations of the landmarks. They hold a priori information about landmarks, whose interpretation is prone to errors. Errors are of two types, recognition or advice. Recognition errors follow from misinterpretation of sensed data or a priori information, or confusion of objects, e.g., due to faulty sensors. Advice errors are consequences of outdated or wrong information about landmarks, e.g., due to weather conditions. Our path planning algorithm is cooperative. MAVs communicate and exchange information wirelessly, to minimize the number of recognition and advice errors. Hence, the quality of the navigation decision process is amplified. Our solution successfully achieves an adaptive error tolerant navigation system. Quality amplification is parameterized with respect to the number of MAVs. We validate our approach with theoretical proofs and numeric simulations.
Comment: An early version of this paper appeared in the proceedings of IEEE GLOBECOM 2019, Waikoloa, Hawaii, Dec 9-14, 2019