Multi-Agent Planning with Spatio-Temporal and Topological Constraints using STL-GO

Researchers introduced two encodings for multi-agent path planning with spatio-temporal and topological constraints expressed in STL-GO, a logic supporting graph operators. The encodings, based on mixed-integer programming (MIP) and satisfiability modulo theory (SMT), provide soundness guarantees and were evaluated on a multi-UAV search-and-rescue benchmark, demonstrating expressiveness under dynamic multi-graph interactions.

arXiv:2607.28679v1 Announce Type: new Abstract: Multi-agent planning problems arise in a variety of engineering applications, such as multi-robot wildfire fighting and unmanned aerial inspection in factories. A particular challenge is the existence of spatio-temporal i.e., when and/or where an agent should do what and topological constraints i.e., how agents should interact , as typically formalized via the notion of graphs. Over the last years, various frameworks have been proposed that can capture such constraints via spatio-temporal logics. We focus here on spatio-temporal logic with graph operators STL-GO , a recent formalism that supports reasoning about multiple agents and their topologies, such as sensing, communication, and task topologies. In this paper, we consider the problem of planning multi-agent paths that satisfy constraints written in STL-GO. This problem is particularly challenging due to the need of encoding multiple, potentially time-varying graphs via the graph operators inherent to STL-GO. We present two encodings of this problem, one based on mixed-integer programming MIP and another based on satisfiability modulo theory SMT , with soundness guarantees. We provide a unified interface for specifying agent constraints, their graph topologies, and the STL-GO specification, enabling seamless use of both methods and facilitating direct comparison between them. We evaluate both encodings on a multi-UAV search-and-rescue benchmark, ablating over team size and graph complexity, highlighting the expressiveness of the proposed encodings under dynamic multi- graph interactions.