# Multi-Agent Planning under Local LTL Specifications and Event-Based Synchronization

arXiv: https://arxiv.org/abs/1610.08380 · HTML: https://mlsanity.com/paper/1610.08380/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Oct 2016.

## Built on by (most cited first, 5 of 5)

- [Conformal Temporal Logic Planning using Large Language Models](https://mlsanity.com/paper/2309.10092/) (2023)
- [ConformalNL2LTL: Translating Natural Language Instructions into Temporal Logic Formulas with Conformal Correctness Guarantees](https://mlsanity.com/paper/2504.21022/) (2025)
- [Decomposition-based Hierarchical Task Allocation and Planning for Multi-Robots under Hierarchical Temporal Logic Specifications](https://mlsanity.com/paper/2308.10393/) (2023)
- [Simultaneous Task Allocation and Planning for Multi-Robots under Hierarchical Temporal Logic Specifications](https://mlsanity.com/paper/2401.04003/) (2024)
- [NSP: A Neuro-Symbolic Natural Language Navigational Planner](https://mlsanity.com/paper/2409.06859/) (2024)

## Abstract (arXiv)

We study the problem of plan synthesis for multi-agent systems, to achieve complex, high-level, long-term goals that are assigned to each agent individually. As the agents might not be capable of satisfying their respective goals by themselves, requests for other agents' collaborations are a part of the task descriptions. We consider that each agent is modeled as a discrete state-transition system and its task specification takes a form of a linear temporal logic formula, which may contain requirements and constraints on the other agent's behavior. A traditional automata-based approach to multi-agent plan synthesis from such specifications builds on centralized team planning and full team synchronization after each agents' discrete step, and thus suffers from extreme computational demands. We aim at reducing the computational complexity by decomposing the plan synthesis problem into finite horizon planning problems that are solved iteratively, upon the run of the agents. As opposed to full synchronization, we introduce an event-based synchronization that allows our approach to efficiently adapt to different time durations of different agents' discrete steps. We discuss the correctness of the solution and find assumptions, under which the proposed iterative algorithm leads to provable eventual satisfaction of the desired specifications.