Multi-robot Path Planning with Boolean Specifications and Collision Avoidance

Abstract

In this paper we consider the path planning problem for a team of identical mobile robots that should fulfill a given global specification. This specification is given as a Boolean formula over some regions of interest and should be satisfied on the final state (when the robots stop) and on the trajectories. The main novelty of this paper is the automatic computation of collision-free trajectories. The approach is based on a Petri net model and on solving two Mixed Integer Linear Programming problems. Based on the solutions of these problems, intermediate synchronization points are introduced in order to avoid possible collisions. Additionally, the algorithm in this paper is implemented in an open-source Matlab toolbox, called RMTool.