Probabilistic Multi-Robot Path Planning with High-Level Specifications using Petri Net Models

This paper considers the path planning problem of a multi-robot system in an uncertain environment with high-level specifications. The specification that the team of robots has to satisfy is given in form of a Boolean formula over the set of regions of interest. Opposed to the majority of solutions for this type of problem, in this paper we consider that the robots do not know with precision the location of these regions, having a probability distribution over the labeling instead. We present a planning algorithm that leverages the properties of Petri net models to efficiently solve an optimization problem that maximizes the probability of satisfying the formula. In addition, the solution of the optimizer avoids regions with high probability of being obstacles and tries to reduce the chances of collisions of the team. We also discuss the application of the algorithm in a distributed scenario, where the robots have different probability distributions and even outdated locations of the rest of the team. Simulations are presented to validate the proposed methodology.