On Multirobot Path Planning Based on Petri Net Models and LTL Specifications

Abstract

This paper proposes a method exploiting the advantages of Petri net (PN) and Büchi automata models, by joining them in a newly defined <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Composed Petri net</i> representation. Based on the latter model, collision-free trajectories are computed for a team of robots. The path planning algorithm is divided into two steps: computing a solution in a reduced PN model, and projecting it to the PN assigned to the environment. The results, given by a set of Mixed Integer Linear Programming (MILP) problems, yield lower computational complexity when compared with previous approaches.