Local Coordination Diagrams for Collision Avoidance in Multi-Robot Path Planning

Abstract

Autonomous robots are intended to help humans performing a lot of different tasks in a safer and more efficient way. Some of those tasks must be solved by a group of autonomous robots. Also, when the task can be solved only by one robot, for cost constraints, it is cheaper (for development and maintenance) to implement solutions including a group of simple robots. Solutions including multiple robots have to solve group problems like communication and coordination; also, common problems of autonomous robots like the widely studied problem of Path Planning must be rethought. In this case, finding a collision-free path is not enough because each robot also has to avoid collisions with other robots (by coordinating their movements). In this scenario, the path planning problem turns into the multi-robot motion planning (MRMP) problem. There are two approaches for solving the MRMP problem: coupled and decoupled. This work is focused on the decoupled approach because it has the potential to solve MRMP not only in a centralized way but, also in a concurrent or distributed way. In this sense, a new parallelizable algorithm, called Local Coordination Diagrams - LCD, is presented in this paper. Experimental results show that our approach can be applied efficiently to a large number of robots.