Persistent Space-Level Path Segment Finding for Multiple Nonholonomic Agents

Multiagent path finding (MAPF) is a critical problem in real-world multiagent systems, where agents reach their respective destinations without colliding with one another. Most MAPF solvers assume agents move at constant speeds with no delays and stop upon reaching their goal. However, real-world nonholonomic agents face delays like deceleration, lane changes, and acceleration, which impact efficiency. Moreover, tasks are continuously generated, making it challenging to meet production requirements. To address this issue, we propose a novel approach, the space-level path segment (SLPS) finding algorithm, which bridges the gap between traditional MAPF methods and the real-world requirements of nonholonomic agents. SLPS defines necessary and optional constraints to construct the collision detection graph (CDG) and formulates an optimization problem to minimize task completion time, resulting in the simplified CDG. It then computes a single SLPS, allowing nonholonomic agents to operate at varying speeds without synchronization. In addition, SLPS supports persistent MAPF tasks through four event-triggered methods, enabling flexible replanning in response to dynamic changes. Experimental results demonstrate that SLPS reduces average task completion time compared to the closest state-of-the-art solvers, proving its efficiency for real-world applications.