An Iterative Approach for Heterogeneous Multi-Agent Route Planning with Temporal Logic Goals and Travel Duration Uncertainty

This paper introduces an iterative approach to multi-agent route planning under chance constraints. A heterogeneous team of agents with various capabilities is tasked with a Capability Temporal Logic (CaTL) mission, a fragment of Signal Temporal Logic. The agents' motion is modeled as a finite weighted graph, where the weights represent travel durations. Given the probability distribution over the durations of each edge's traversal, we want to find paths for all agents such that (a) the specification robustness is maximized, (b) travel time is minimized, and (c) the success probability is maximized. We tackle the problem using an iterative approach. In each stage, it selects edges' traversal duration and success probabilities and then solves a multi-agent route planning problem. We use an efficient Mixed-Integer Linear Programming (MILP) encoding for the latter. Our method provides a framework for agents to make informed decisions in choosing the most suitable edge attributes (travel durations and success probabilities) that consider agents' capabilities to perform tasks in the environment. The proposed iterative method leverages graph structure to generate a more efficient search space. The effectiveness of our method is demonstrated through simulated case studies where obtaining the optimal solution would otherwise be computationally expensive. Our approach efficiently explores the solution space, generating better solutions and improving the performance of multi-agent route planning with uncertain travel durations.