Fast Multi-Agent Path Planning with Turn Actions: A Priority Inheritance Approach

Multi-Agent Path Finding (MAPF) has found wide application in real-world scenarios. However, the classical MAPF action models often overlook the kinematic constraints of real agents, which require in-place turns due to their orientations. Existing algorithms for MAPF with turn actions typically suffer from low computational efficiency and limited scalability, primarily due to the significantly larger state space. In this paper, we propose a priority inheritance approach that efficiently generates valid solutions in high-agent-density environments, significantly reducing computation time while maintaining acceptable solution quality. The proposed approach can solve instances with up to 1000 agents in seconds, making it well-suited for scenarios requiring rapid responses and high scalability.