Search

We consider the problem of collectively delivering a package from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent starts from some vertex of the graph; it can move along the edges of the graph and can pick up the package from a vertex and drop it in another vertex during the course of its movement. However, each agent has limited energy budget allowing it to traverse a path of bounded length B ; thus, multiple agents need to collaborate to move the package to its destination. Given the positions of the agents in the graph and their energy budgets, the problem of finding a feasible movement schedule is called the Collaborative Delivery problem and has been studied before. One of the open questions from previous results is what happens when the delivery must follow a fixed path given in advance. Although this special constraint reduces the search space for feasible solutions, the problem remains NP hard, as the general version of the problem. We consider the optimization version of the problem that asks for the optimal energy budget B per agent which allows for a feasible delivery schedule along a fixed path, given the initial positions of the agents. We provide polynomial time approximation algorithms for both directed and undirected graphs, and establish hardness of approximation for the directed case. Note that the fixed path version of collaborative delivery requires completely different techniques since a single agent may be used multiple times, unlike the general version of collaborative delivery studied before. We show that restricting each agent to a single pickup allows better approximations for fixed path collaborative delivery compared to the original problem. Finally, we provide a polynomial time algorithm for determining a feasible delivery strategy, if any exists, for a given budget B when the number of available agents is bounded by a constant. [ABSTRACT FROM AUTHOR]

We consider the problem of collectively delivering some package from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent has limited energy which constrains the distance it can move. Hence multiple agents need to collaborate to move the package, each agent handing over the package to the next agent to carry it forward. Given the positions of the agents in the graph and their respective budgets, the problem of finding a feasible movement schedule for the agents can be challenging. We consider two variants of the problem: in non-returning delivery, the agents can stop anywhere; whereas in returning delivery, each agent needs to return to its starting location, a variant which has not been studied before. We first provide a polynomial-time algorithm for returning delivery on trees, which is in contrast to the known (weak) NP-hardness of the non-returning version. In addition, we give resource-augmented algorithms for returning delivery in general graphs. Finally, we give tight lower bounds on the required resource augmentation for both variants of the problem. In this sense, our results close the gap left by previous research. [ABSTRACT FROM AUTHOR]

A collection of k mobile robots, initially placed at the origin of the plane, are searching for a stationary target. Each robot r i has a unit visibility range and can move no faster than its maximal speed v i , for i = 1 , 2 ,... , k. The robots can communicate between themselves. We consider two communication models: wireless, in which a message sent by a robot can reach all other robots immediately, regardless of their positions, and face-to-face (F2F), in which robots can only exchange information when they are meeting. We assume that up to f robots, where f < k , may be unreliable. We consider two models of unreliability: (1) crash faults, in which we deal with an absence of some of the robots' capabilities (communication, perception, motion, etc.), and (2) byzantine faults, in which the robots may be malicious in that they may execute a wrong algorithm (e.g., transmitting wrong information). The goal is to minimize the group search time, which is equal to the time of arrival to the target of the last reliable robot. This is expressed as a function of d , the distance from the origin to the target. Our proposed algorithms for crash faults are asymptotically optimal in d in both communication models. For byzantine faults, our algorithm is asymptotically optimal for the wireless model. In the F2F model, we propose two algorithms: the first one has a competitive ratio of 2, while the second algorithm works for k ≥ 2 f + 2 and is optimal when the robots speeds are all equal. [ABSTRACT FROM AUTHOR]

Abstract A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced. [ABSTRACT FROM AUTHOR]