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

• URL: http://arxiv.org/abs/2607.28679v1
• Date: Wed, 29 Jul 2026 16:12:58 GMT
• Title: Multi-Agent Planning with Spatio-Temporal and Topological Constraints using STL-GO
• Abstract summary: We consider the problem of planning multi-agent paths that satisfy constraints written in graph operators (STL-GO)<n>This problem is particularly challenging due to the need encoding multiple, potentially time-varying graphs via the graph operators inherent to STL-GO.<n>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.
• Score: 2.0377799177694533
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Inference-Time Graph Engineering for Multi-Agent LLM Workflows [51.56038180639833]
  We introduce ReActNet, a training-free framework that compiles a query and a set of role-specialized agents into a sequence of directed communication graphs.<n>We show that ReActNet consistently improves over fixed-topology and learned-topology baselines while maintaining competitive inference cost.
  arXiv  Detail & Related papers  (2026-09-04T23:32:11Z)
• Generalizable Multi-Agent Planning from Signal Temporal Logic Specifications via Diffusion [3.7331950863394856]
  Multi-agent systems must satisfy rich, temporal tasks while avoiding collisions.<n>Current Signal Temporal Logic (STL) planning methods face critical limitations.<n>We introduce a new diffusion method for multi-agent planning with STL specifications.
  arXiv  Detail & Related papers  (2026-08-30T00:38:31Z)
• OFA-MAS: One-for-All Multi-Agent System Topology Design based on Mixture-of-Experts Graph Generative Models [57.94189874119267]
  Multi-Agent Systems (MAS) offer a powerful paradigm for solving complex problems.<n>Current graph learning-based design methodologies often adhere to a "one-for-one" paradigm.<n>We propose OFA-TAD, a one-for-all framework that generates adaptive collaboration graphs for any task described in natural language.
  arXiv  Detail & Related papers  (2026-01-19T12:23:44Z)
• Process-Centric Analysis of Agentic Software Systems [10.976178600911263]
  We introduce Graphectory to encode the temporal and semantic relations in software systems.<n>We analyze 4000 trajectories of two dominant agentic programming models.<n>Our fully automated analyses reveal that agents using richer prompts exhibit more complex Graphectory.
  arXiv  Detail & Related papers  (2025-12-02T04:12:29Z)
• Verification-Aware Planning for Multi-Agent Systems [35.82875628010279]
  We present VeriMAP, a framework for multi-agent collaboration with verification-aware planning.<n>The planner decomposes tasks, models subtask dependencies, and encodes planner-defined passing criteria.<n>We show how verification-aware planning enables reliable coordination and iterative refinement in multi-agent systems.
  arXiv  Detail & Related papers  (2025-10-20T02:54:29Z)
• Dynamic Generation of Multi-LLM Agents Communication Topologies with Graph Diffusion Models [99.85131798240808]
  We introduce a novel generative framework called textitGuided Topology Diffusion (GTD)<n>Inspired by conditional discrete graph diffusion models, GTD formulates topology synthesis as an iterative construction process.<n>At each step, the generation is steered by a lightweight proxy model that predicts multi-objective rewards.<n>Experiments show that GTD can generate highly task-adaptive, sparse, and efficient communication topologies.
  arXiv  Detail & Related papers  (2025-10-09T05:28:28Z)
• AgentRouter: A Knowledge-Graph-Guided LLM Router for Collaborative Multi-Agent Question Answering [51.07491603393163]
  tAgent is a framework that formulates multi-agent QA as a knowledge-graph-guided routing problem supervised by empirical performance signals.<n>By leveraging soft supervision and weighted aggregation of agent outputs, Agent learns principled collaboration schemes that capture the complementary strengths of diverse agents.
  arXiv  Detail & Related papers  (2025-10-06T23:20:49Z)
• Assemble Your Crew: Automatic Multi-agent Communication Topology Design via Autoregressive Graph Generation [91.17994756436259]
  Multi-agent systems (MAS) based on large language models (LLMs) have emerged as a powerful solution for dealing with complex problems across diverse domains.<n>Existing approaches are fundamentally constrained by their reliance on a template graph modification paradigm with a predefined set of agents and hard-coded interaction structures.<n>We propose ARG-Designer, a novel autoregressive model that operationalizes this paradigm by constructing the collaboration graph from scratch.
  arXiv  Detail & Related papers  (2025-07-24T09:17:41Z)
• Divide by Question, Conquer by Agent: SPLIT-RAG with Question-Driven Graph Partitioning [62.640169289390535]
  SPLIT-RAG is a multi-agent RAG framework that addresses the limitations with question-driven semantic graph partitioning and collaborative subgraph retrieval.<n>The innovative framework first create Semantic Partitioning of Linked Information, then use the Type-Specialized knowledge base to achieve Multi-Agent RAG.<n>The attribute-aware graph segmentation manages to divide knowledge graphs into semantically coherent subgraphs, ensuring subgraphs align with different query types.<n>A hierarchical merging module resolves inconsistencies across subgraph-derived answers through logical verifications.
  arXiv  Detail & Related papers  (2025-05-20T06:44:34Z)
• Decomposition-based Hierarchical Task Allocation and Planning for Multi-Robots under Hierarchical Temporal Logic Specifications [9.150196865878234]
  We formulate a decomposition-based hierarchical framework for robotic planning with temporal logic specifications. A Mixed Linear Program is used to assign sub-tasks to various robots. Our approach was experimentally applied to domains of navigation and manipulation.
  arXiv  Detail & Related papers  (2023-08-20T23:53:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.