Distributed graph algorithms for energy-constrained mobile robots

31^st May 2018, 14:00
Dr Shantanu Das
Aix-Marseille University

Abstract

We consider distributed tasks for mobile robots moving on graph. Each robot has a constraint on its energy consumption which limits the number of edges it can traverse. Under such constraints, a team of robots need to perform a distributed task while sharing the work among them. In this model, even simple problems like delivering an object from source node to a target, becomes difficult to solve. We present some recent results for energy constrained robots that need to perform delivery in a collaborative manner. We study different variants of the problem depending on the structure of the graph and the energy budgets of the robots and whether or not they can share energy. We show hardness results, in-approximability results as well as positive results and efficient algorithms for feasible cases.