# WinkTPG: An Execution Framework for Multi-Agent Path Finding Using Temporal Reasoning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 17 of its 34 references that are in the map.
- First posted on arXiv 2 Aug 2025.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

## Builds on (most cited first, 17 of 17)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1901.11282/) (2019)
- [Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments](https://mlsanity.com/paper/1710.01447/) (2017)
- [Improving Continuous-time Conflict Based Search](https://mlsanity.com/paper/2101.09723/) (2021)
- [Multi-Agent Motion Planning with B'ezier Curve Optimization under Kinodynamic Constraints](https://mlsanity.com/paper/2311.14145/) (2023)
- [CL-MAPF: Multi-Agent Path Finding for Car-Like Robots with Kinematic and Spatiotemporal Constraints](https://mlsanity.com/paper/2011.00441/) (2020)
- [db-CBS: Discontinuity-Bounded Conflict-Based Search for Multi-Robot Kinodynamic Motion Planning](https://mlsanity.com/paper/2309.16445/) (2023)
- [Receding Horizon Re-ordering of Multi-Agent Execution Schedules](https://mlsanity.com/paper/2312.04190/) (2023)
- [Advancing MAPF Toward the Real World: A Scalable Multi-Agent Realistic Testbed (SMART)](https://mlsanity.com/paper/2503.04798/) (2025)
- [STT-CBS: A Conflict-Based Search Algorithm for Multi-Agent Path Finding with Stochastic Travel Times](https://mlsanity.com/paper/2004.08025/) (2020)
- [Safe Interval Path Planning With Kinodynamic Constraints](https://mlsanity.com/paper/2302.00776/) (2023)
- [A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution](https://mlsanity.com/paper/2403.18145/) (2024)
- [db-A*: Discontinuity-bounded Search for Kinodynamic Mobile Robot Motion Planning](https://mlsanity.com/paper/2203.11108/) (2022)
- [Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses](https://mlsanity.com/paper/2408.14527/) (2024)

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

- [From Discrete Plans to Real-World Execution: A World-Model-Driven Framework for Execution-Aware Multi-Agent Path Finding](https://mlsanity.com/paper/2511.21886/) (2025)

## Abstract (arXiv)

Planning collision-free paths for a large group of agents is a challenging problem in many real-world applications. While recent advances in Multi-Agent Path Finding (MAPF) have shown promising progress, standard MAPF planners continue to rely on simplified kinodynamic models, preventing agents from directly following the generated MAPF plan. To bridge this gap, we propose kinodynamic Temporal Plan Graph planning (kTPG), a multi-agent speed optimization algorithm that efficiently refines a MAPF plan into a set of kinodynamically feasible speed profiles. We further incorporate execution timing uncertainty models and provide deterministic guarantees under bounded uncertainty models and probabilistic guarantees under stochastic models. Building on kTPG, we propose Windowed kTPG (WinkTPG), a MAPF execution framework that incrementally refines MAPF plans using a window-based mechanism, dynamically incorporating agent information during execution to reduce uncertainty. Experiments show that WinkTPG can generate speed profiles for up to 1,000 agents within 1 second and improves solution quality by up to 51.7% over existing MAPF execution methods. We further validate WinkTPG in high-fidelity physics-based simulation and on real-world robots.