Path Planning of Multi-Robot Systems With Boolean Specifications Based on Simulated Annealing

In this letter, we address the path planning of multi-robot systems (i.e., a team of identical mobile robots) with a global high-level specification that is given as a Boolean formula over some regions of the environment. The task is composed of logical requirements on the trajectories and the final states of the robots for some interest regions. First, a preprocessing algorithm based on Dijkstra algorithm is developed to calculate the shortest path between each interest region according to the global map information and the Boolean specification. Then, a simulated annealing based approach is developed to obtain a path trajectory of each robot such that the Boolean specification is satisfied on the final state, while the total travel distance is minimized. Finally, several numerical studies are investigated to show that the developed approach is superior to the existing methods in terms of both the computational cost and the quality of the obtained solution.