1. Collaborative Delivery on a Fixed Path with Homogeneous Energy-Constrained Agents
- Author
-
Chalopin, Jérémie, Das, Shantanu, Disser, Yann, Labourel, Arnaud, Mihalák, Matúš, Censor-Hillel, Keren, Flammini, Michele, Algorithmique Distribuée (DALGO), Laboratoire d'Informatique et Systèmes (LIS), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Technische Universität Darmstadt (TU Darmstadt), Department of data science and Knowledge Engineering [Maastricht], Maastricht University [Maastricht], ANR-14-CE36-0002,ANCOR,Algorithm Design for Microrobots with Energy Constraints(2014), DKE Scientific staff, RS: FSE DACS NSO, Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Technische Universität Darmstadt - Technical University of Darmstadt (TU Darmstadt), Department of Data Science and Knowledge Engineering, Maastricht University, Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France, Graduate School CE, TU Darmstadt, Dept. of Advanced Computing Sciences, RS: FSE DACS, and RS: FSE DACS Mathematics Centre Maastricht
- Subjects
Vertex (graph theory) ,Mathematical optimization ,Schedule ,Traverse ,General Computer Science ,Computer science ,Distributed computing ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,02 engineering and technology ,Hardness of approximation ,01 natural sciences ,Theoretical Computer Science ,Collaborative delivery ,Energy constrained ,0202 electrical engineering, electronic engineering, information engineering ,Fixed path ,Time complexity ,ComputingMilieux_MISCELLANEOUS ,Approximation algorithm ,Directed graph ,Energy constrained robots ,Approximation algorithms ,Computer Science::Multiagent Systems ,Homogeneous ,010201 computation theory & mathematics ,Bounded function ,Path (graph theory) ,Graph (abstract data type) ,020201 artificial intelligence & image processing ,Mobile agents ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Directed graphs - Abstract
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 a distinct vertex of the graph, and can move along the edges of the graph carrying the package. 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 of finding a feasible schedule remains np hard (as the original 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, given the initial positions of the agents. We show the existence of better approximations for the fixed-path version of the problem (at least for the restricted case of single pickup per agent), compared to the known results for the general version of the problem, thus answering the open question from the previous paper.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.
- Published
- 2019