Publication

J. Yan, S.F. Smith and J. Li. WinkTPG: An Execution Framework for Multi-Agent Path Finding Using Temporal Reasoning. IEEE Transactions on Automation Science and Engineering, 23, 9162-9175, 2026.

Abstract: 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 percent over existing MAPF execution methods. We further validate WinkTPG in high-fidelity physics-based simulation and on real-world robots. Note to Practitioners—The motivation of this article originates from the need to execute large-scale multi-agent path-planning solutions reliably in practical applications such as warehouse logistics, industrial material transport, and factory or airport automation. Although discrete MAPF planners can generate conflict-free paths, their solutions are often not directly executable by real robots due to kinodynamic constraints and execution timing uncertainties. This article develops WinkTPG, a windowed execution framework that converts MAPF plans into safe and kinodynamically feasible speed profiles while maintaining precedence relations implied by the discrete plan. WinkTPG further employs receding-horizon replanning to correct timing deviations caused by disturbances or sensing noise, making it suitable for practitioners deploying multi-robot fleets in constrained, time-critical environments.

Download the paper in pdf.