New Methods for Multi-Agent Planning with Complex Constraints

A new research paper tackles the complex challenge of multi-agent planning, which is critical for applications like multi-robot wildfire fighting or drone inspections. These problems often involve intricate spatio-temporal constraints, dictating when and where agents should perform actions, alongside topological constraints that define how agents interact through sensing, communication, or task dependencies. The authors focus on Spatio-Temporal Logic with Graph Operators (STL-GO), a formalism capable of expressing these multi-agent and topological requirements. They introduce two novel encoding methods to solve planning problems specified in STL-GO: one based on Mixed-Integer Programming (MIP) and another on Satisfiability Modulo Theory (SMT). Both encodings come with soundness guarantees. A unified interface is provided for specifying agent constraints, graph topologies, and the STL-GO specification, allowing for seamless use and direct comparison of the two methods. Evaluations on a multi-UAV search-and-rescue benchmark demonstrate the expressiveness and effectiveness of these encodings in handling dynamic multi-graph interactions, varying team sizes, and graph complexities.