优化机器人路径规划中的依赖图，提速并减少冗余
Streamlining the Action Dependency Graph Framework: Two Key Enhancements
- 移除冗余等待动作，提升实际执行效率
- 新算法将构建时间从平方级降至准线性
- 适合需要高效多机协同的机器人系统
多智能体路径规划（MAPF）对共享环境中多机器人的协调至关重要，但计划的实际执行受操作不确定性影响。动作依赖图（ADG）框架通过在等待与移动动作间建立基于优先级的依赖关系，保障动作正确执行。原始构建算法存在效率低下的问题，最坏时间复杂度为二次方，且生成网络中包含大量冗余依赖。本文提出两项改进：首先证明等待动作通常冗余，并实验证明移除后可加快真实机器人系统的整体执行速度；其次提出一种优化的ADG构建算法——稀疏候选划分（Sparse Candidate Partitioning, SCP），跳过不必要的依赖关系，将时间复杂度降至准线性，显著提升构建速度。
原文摘要 · Abstract (English)
Multi Agent Path Finding (MAPF) is critical for coordinating multiple robots in shared environments, yet robust execution of generated plans remains challenging due to operational uncertainties. The Action Dependency Graph (ADG) framework offers a way to ensure correct action execution by establishing precedence-based dependencies between wait and move actions retrieved from a MAPF planning result. The original construction algorithm is not only inefficient, with a quadratic worst-case time complexity it also results in a network with many redundant dependencies between actions. This paper introduces two key improvements to the ADG framework. First, we prove that wait actions are generally redundant and show that removing them can lead to faster overall plan execution on real robot systems. Second, we propose an optimized ADG construction algorithm, termed Sparse Candidate Partitioning (SCP), which skips unnecessary dependencies and lowers the time complexity to quasi-linear, thereby significantly improving construction speed.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。