Search papers, labs, and topics across Lattice.
This paper introduces C-ORCA* and C-ORCA*-MAPF, advanced continuous-space algorithms for Multi-Agent Path Finding (MAPF) that proactively prevent deadlocks by considering agents' entire spatial trajectories and dependencies. By addressing the myopic nature of existing real-time solvers like ORCA*, these algorithms eliminate the significant flowtime overhead associated with reactive deadlock interventions. The results demonstrate a substantial improvement in solve rate, runtime, and flowtime compared to previous state-of-the-art methods, highlighting their effectiveness in coordinated multi-agent navigation scenarios.
Proactive deadlock avoidance in multi-agent navigation could revolutionize real-time pathfinding efficiency, slashing flowtime overhead dramatically.
Multi-Agent Path Finding (MAPF) is a problem that requires computing collision-free paths for a set of agents from their start locations to designated goal locations. The problem has broad applications in domains where teams of robots must operate in a coordinated manner. ORCA* is a real time MAPF solver that assigns for each timestep a velocity for each agent. Due to its real time nature, it is myopic to future deadlocks that result from current decisions. ORCA*-MAPF attempts to remedy this limitation by introducing fallback mechanisms when deadlocks are detected. However, post hoc interventions often introduce significant flowtime overhead. In this paper, we introduce C-ORCA* and C-ORCA*-MAPF, continuous space MAPF algorithms that incorporate agents' entire spatial trajectory and their spatial dependencies to proactively prevent deadlocks from occurring, thus avoiding the high flowtime overhead associated with post hoc corrections in ORCA*-MAPF. The C-ORCA* family of algorithms significantly outperform previous state-of-the-art in terms of solve rate, runtime, and flowtime.
