On dynamic multi-agent pathfinding methods: review, simulations and modifications
For researchers and practitioners in multi-agent pathfinding, this work provides a comparative evaluation and a new algorithm that addresses the challenge of dynamic obstacles and partial observability.
This paper systematically evaluates six pathfinding algorithms for Dynamic Multi-Agent Pathfinding (D-MAPF) and introduces A**, a novel method that decouples offline path generation from online adaptation. A** improves solution quality in dynamic environments with frequent changes and limited sensing.
This paper presents a systematic study of pathfinding algorithms in the context of Dynamic Multi-Agent Pathfinding (D-MAPF), a setting that combines dynamic obstacles, partial observability, and inter-agent conflicts. We evaluate six representative algorithms: Dijkstra, D* Lite, Space-Time A*, WHCA*, M*, and a novel method denoted as A** within a unified simulation framework. The proposed A** algorithm introduces a template-based approach that decouples offline geometric path generation from online temporal adaptation. By precomputing multiple diverse candidate paths and dynamically reconnecting to them using space-time planning, A** improves solution quality in environments with frequent changes and limited sensing