Optimal task planning in multi-vehicle systems under syntactically co-safe Linear Temporal Logic

Abstract: Autonomous vehicles need to be able to perform different instructions during different missions and situations. For task specification, logical languages are often used. Depending on desired expressiveness, there are different methods of task specification and planning. In this paper we explore the case of multi-agent systems performing tasks specified by co-safe Linear Temporal Logic (scLTL) formulas in relation to three cost functions. Specifically, we make use of the Vehicle Routing Problem to define our problem domain. Semantics for scLTL-formulas of multiple vehicles are introduced, as well as translations of scLTL-formulas into MILP constraints. We discuss use-cases and show how missions can be specified for both entire fleets, subgroups and single vehicles. The resulting method consists of several steps, from scLTL-formulas, into MILP constrains, ready to be solved by an already established MILP-solver. The complexity of the algorithm is discussed, as the algorithm is shown costly when problem instances grow.