Presentations
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.
- Fixed Path Version:
When the path on which the package is to be transported is given in advance, collaborative delivery
remains NP-hard. We compared this version of the problem with the original version where the path is not provided. We
provided 3-approximation and 5/2-approximation algorithms for directed and undirected graphs respectively. We also
showed lower bounds of 2 and 1.5 for the approximation ratio in directed and undirected graphs. In the special case of
single pickup per agent, we showed better approximation algorithms for the fixed path version compared to the original
problem.
- Delivery by only a few Agents:
For the original version of collaborative delivery, it is sufficient for each robot to participate only once in the delivery schedule.
Thus, determining the order in which the robots are used is equivalent to solving the problem. This observation implies a polynomial time solution to the problem when the number of robots is a constant. On the contrary we show that the fixed path version is weakly NP hard even if there are O(1) robots. We also provide an FPTAS for solving the fixed path version of collaborative delivery with a time complexity of O(k.n^(k+2).B^k) for k robots with uniform budget B.
- Heterogenous Agents:
We studied the collaborative delivery problem for agents having distinct rates of energy
consumption with the objective of minimizing the total energy expenditure. We showed that the problem can be easily
solved for a single package, however the multi-package delivery is NP-hard even for planar graphs. For this case, we
provided a 4R-approximation algorithm when the ratio of energy consumption rates of any two agents is bounded by R.
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.
