.png){kind=icon}
Return
Persistent Space-Level Path Segment Finding for Multiple Nonholonomic Agents
.png){kind=icon}
PRE
AI
DOI：10.1109/TII.2025.3609041.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Collision avoidance
dynamic execution
lifelong multiagent path finding (MAPF)
multiagent path finding
nonholonomic agents
space-level path finding
Journal
IF:
9.9
Papers:
8.6K
Citations:
6.0W
Organization
View more organizations
Cited Papers
.png){kind=icon}
ShareSave
ShareSaveShareSave View more