WinkTPG: An Execution Framework for Multi-Agent Path Finding Using Temporal Reasoning
This addresses the gap between simplified MAPF plans and real-world execution for applications like robotics and logistics, though it is incremental as it builds on existing MAPF methods.
The paper tackles the problem of refining Multi-Agent Path Finding (MAPF) plans into kinodynamically feasible ones by proposing WinkTPG, a window-based execution framework that improves solution quality by up to 51.7% and handles up to 1,000 agents in 1 second.
Planning collision-free paths for a large group of agents is a challenging problem with numerous real-world applications. While recent advances in Multi-Agent Path Finding (MAPF) have shown promising progress, standard MAPF algorithms 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 kinodynamically feasible plan while accounting for uncertainties and preserving collision-freeness. 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 in 1 second and improves solution quality by up to 51.7% over existing MAPF execution methods.