解决产线长周期运行下的多智能体路径规划问题
Streaming Multi-agent Pathfinding
- 将智能体按周期流建模，共享动作序列以提升效率
- 新算法在长时间场景下运行速度显著优于传统方法
- 适合工业产线、持续运行的多机器人系统
多智能体路径规划（MAPF）任务是将一组智能体从起点导航至目标点。然而，这一设定不适用于工作时长极长且周期性的产线场景。为此，本文提出流式多智能体路径规划（S-MAPF）问题，假设同一智能体流中的个体具有周期性起始时间，并共享相同的动作序列。所提出的智能体流冲突搜索算法（ASCBS）通过引入循环顶点/边约束来处理冲突，并探索了在该框架中使用不相交分割策略的潜力。实验结果表明，在长时间运行场景中，ASCBS在求解时间上优于传统MAPF求解器。
原文摘要 · Abstract (English)
The task of the multi-agent pathfinding (MAPF) problem is to navigate a team of agents from their start point to the goal points. However, this setup is unsuitable in the assembly line scenario, which is periodic with a long working hour. To address this issue, the study formalizes the streaming MAPF (S-MAPF) problem, which assumes that the agents in the same agent stream have a periodic start time and share the same action sequence. The proposed solution, Agent Stream Conflict-Based Search (ASCBS), is designed to tackle this problem by incorporating a cyclic vertex/edge constraint to handle conflicts. Additionally, this work explores the potential usage of the disjoint splitting strategy within ASCBS. Experimental results indicate that ASCBS surpasses traditional MAPF solvers in terms of runtime for scenarios with prolonged working hours.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。