Algorithm Design for Microrobots with Energy Constraints – ANCOR

In this project we design energy-aware algorithms for distributed tasks performed by a team of robots. Since each robot has an individual limit on the available energy we need to find ways to balancing the work among the robots such that no robot runs out of battery before finishing the task. Depending on the particular scenario, the placement of robots and their individual power reserves, the algorithm has to make conscious choices about the movement of robots and the order in which the robots should be deployed.

Another objective was to design energy-efficient algorithm for teams of heterogeneous robots having distinct rates of energy consumption. To
this end we subdivide the task of collaborative delivery into three subtasks, collaboration, individual planning, and coordination: First of all, if multiple robots work on delivering the same package, they need to collaborate, i.e., we have to find all intermediate drop-off and pick-up locations of the package. Secondly, if an robot works on more than one package, we have to plan in which order it wants to approach its subset of packages. Finally, we have to coordinate which robot works on which subset of all packages (if they do this without collaboration, the subsets form a partition, otherwise the subsets are not necessarily pairwise disjoint). Even though these three subtasks are interleaved, we investigate collaboration, planning and coordination separately to obtain the best approximations for these subtasks, which are then combined to obtain the final approximate solution.

Collaborative Delivery Problem: We proved the returning version of the problem to be easy for trees, unlike the non-returning version and provided an efficient algorithm for delivery in tree networks. Moreover our results showed both versions of the problem to be strongly NP-hard for planar graphs, which represent most transportation networks in real-life. We provided resource-augmented algorithms for the delivery problem and matching lower bounds to show that these algorithms were the most energy-efficient algorithms that can be computed in polynomial time. We also provide algorithms for the Fixed Path version of the problem when the path on which the package is to be transported is given in advance. For delivery with heterogenous robots having distinct rates of energy consumption and we provided a 4R-approximation algorithm when the ratio of energy consumption rates of any two robots is bounded by R.

Formation Problem:
We study the task of near-gathering k energy-constrained mobile robots with the objective of forming a configuration that minimizes either (i) the radius of a ball containing all robots, (ii) the maximum distance between any two robots, or (iii) the average distance between the robots. We prove that (i) is polynomial-time solvable and (ii) has a polynomial-time 2-approximation with a matching NP-hardness lower bound, while (iii) admits a polynomial-time 2(1-1/k)-approximation, but no FPTAS, unless P=NP.

Online Exploration Problem:
We consider the problem of exploring an unknown graph by k robots, starting at a single node of the graph. Assuming that there is a fixed energy budget B per robot, we provide online algorithms for tree exploration with or without return to the homebase, optimizing the number of robots used. For “exploration with return” we provide constant competitive algorithms, while for “exploration without return” we present a O(log B)-competitive algorithm and we show that this is best possible.

The project ANR-ANCOR is a fundamental research project conducted by scientists at the laboratory of theoretical computer science (LIF, renamed LIS) which is part of the Aix-Marseille University in Marseille France. This a joint French-Swiss project in partnership with the Institute of Theoretical Computer Science at ETH Zurich in Zurich, Switzerland. The project started on the first of July 2015 and is for a duration of 36 months in total. The French side of the project was funded by ANR France with a grant of 84,032.00 euros and a global cost of around 593,792.00 euros. The Swiss partners of the project at ETH Zurich were funded by SNF (Swiss National Science Foundation) according to the bilateral agreement between the ANR and SNF. The French team for the project, based in Marseille consisted of three permanent researchers, one postdoctoral researcher and one externally funded doctoral student.

With our project partners, we published several scientific articles and gave presentations at national and international conferences to disseminate the results obtained during this project. For the collaborative delivery problem we published two articles, one at SIROCCO 2016 and another at STACS 2017; both are top conferences in this domain of research and each article is peer-reviewed by international experts. These two articles present our results on the collaborative delivery problem for teams of homogeneous and heterogeneous robots respectively. A full and extended version of the former articles is due to appear in the journal ``Theoretical Computer Science« in 2019. We also wrote two other articles, one on the fixed-path version of the delivery problem and the other on the near-gathering problem for mobile robots with energy constraints. Both articles would be presented in the next edition of the conference SIROCCO in 2019. Full versions of these articles should appear in the next year.

In collaboration with the postdoctoral researcher and the doctoral student, we published two scientific articles that were presented at the international conference ALGOSENSORS 2017 and the francophone conference ALGOTEL 2017 respectively. The first paper studied the delivery problem in the scenario where robots can share energy on meeting. The second paper considered the online search and maximal exploration problem in the setting when the number of robots and their energy budgets are fixed in advance. An extended version of the paper has been submitted for publication in a journal. With an external collaborator, we published two articles on online exploration with fixed energy budgets, presented in the conference SIROCCO 2015 and published in the journal ``Theory of Computing Systems« in 2018. We also published another article on the problem of online exploration with return, presented at the international conference ICALP 2018.