A computationally efficient solution for path planning of mobile robots with boolean specifications

Abstract

This paper presents a solution with reduced computational complexity for path planning of a team of robots that should satisfy a mission expressed as a Boolean formula. It is assumed that the robots move in a partitioned environment containing some regions of interest. The robots should reach some final regions such that a Boolean formula expressed using the regions of interest is satisfied. Moreover, other Boolean formula should be true during the trajectories. This problem has been studied in [1], where it is shown that the solution based on Petri net models and mathematical programming has a considerable advantage when the number of robots is greater than three or four with respect to the transition system solution. Here we propose to further reduce the complexity, even if the obtained solution will not be anymore optimal with respect to the total number of transition firings. The solution is based also on Petri net models and mathematical programming, but a new abstraction method allows us to reduce the number of variables and constraints of the mathematical programs used to compute the trajectories.