Multi-robot path planning for syntactically co-safe LTL specifications

Abstract

This paper presents an automatic strategy to control a team of identical robots that should satisfy a given task expressed as a syntactically co-safe Linear Temporal Logic (LTL) formula over a set of regions of interest. The team of robots is modeled by using a Petri net system with outputs (observations), thus avoiding the use of synchronized product of automatons. The strategy starts by translating the task into a Büchi automaton and by choosing a finite string satisfying the formula. Three Integer Linear Programming (ILP) formulations are used to find in the Petri net model a sequence of reachable markings such that the generated observations produce the chosen string of the Büchi automaton. If the string is not correctly followed, another one is found and the procedure is reiterated.