ANR LIF Aix-Marseille Université CNRS ETHZ

ANR SNF Project ANCOR ( Algorithm Design for Microrobots with Energy Constraints )


Collaborative Delivery Problem

Exploration by Energy Constrained Mobile Robots
(Presented at the Workshop on Self-organization in Swarm of Robots, Tokyo 2018)

Main Results

Collaborative Delivery Problem:

The objective is to deliver packages from designated source nodes to destination nodes, using a team of energy constrained agents. Previous results for single package delivery showed the problem to be NP-hard for general graphs and weakly NP-hard for the tree topology. Our results show a surprising difference in complexity of the problem depending on whether the agents return to their homebases (returning) or not (non-returning). 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.

Near Gathering of Robots:

We study the task of gathering k energy-constrained mobile agents in an undirected edge-weighted graph. Each agent is initially placed on an arbitrary node and has limited energy, which constrains the distance it can move. Since this may render gathering at a single point impossible, we study three variants of near-gathering: The goal is to move the agents into a configuration that minimizes either (i) the radius of a ball containing all agents, (ii) the maximum distance between any two agents, or (iii) the average distance between the agents. 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. We extend some of our results to additive approximation.

- - - - - ONLINE ALGORITHMS - - - - -

Online Exploration Problem:

We consider the problem of exploring an unknown graph by k agents, starting at a single node of the graph, where each robot has a constraint on its energy consumption which limits the number of edges it can traverse. Since any single robot may not completely explore the graph, the robots need to collaborate so that each node is visited by some robot. We consider three different optimization criteria: the size of the team, the energy budget per robot, and finally the number of nodes visited. Assuming that there is a fixed energy budget B per agent, we provide online algorithms for tree exploration with or without return to the homebase, optimizing the number of agents 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 by showing a matching lower bound on the competitive ratio for any online exploration algorithm. Finally we considered the exploration of the maximum number of nodes when both the budget B and the team size k is fixed a priori. For the maximal exploration problem we provide an online algorithm that visits at least one third of the number of nodes visited by any offline exploration algorithm. We also present an almost matching lower bound of 2.17 on the competitive ratio.