Multi-Agent Path Planning for Finite Horizon Tasks with Counting Time Temporal Logics

Authors:

Abstract
In this paper, we consider the multi-agent path planning problem for high-level tasks with finite horizons. In many situations, there is the need to count how many times a sub-task is satisfied in order to achieve the overall task. However, existing temporal logic languages, such as linear temporal logic, may not be efficient in describing such requirements. To address this issue, we propose a new temporal logic language called Counting Time Temporal Logic (CTTL) that extends linear temporal logic by explicitly counting the number of times that some tasks are satisfied. To solve the CTTL path planning problem, we use integer linear programming to encode the satisfaction of the task. We demonstrate that our approach is both sound and complete. To validate our results, we present numerical experiments to show the scalability of the proposed approach. Furthermore, we provide a simulation case study of a team of autonomous robots to illustrate the synthesis procedure.
Funding Information
  • National Natural Science Foundation of China