Multi-Objective Search for Optimal Multi-Robot Planning with Finite LTL Specifications and Resource Constraints

Abstract

We present an efficient approach to plan action sequences for a team of robots from a single finite LTL mission specification. The resulting execution strategy is proven to solve the given mission with minimal team costs, e.g., with shortest execution time. For planning, an established graph-based search method based on the multi-objective shortest path problem is adapted to multi-robot planning and extended to support resource constraints. We further improve planning efficiency significantly for missions which consist of independent parts by using previous results regarding LTL decomposition. The efficiency and practicality of the ROS implementation of our approach is demonstrated in example scenarios.