X*: Anytime Multi-Agent Path Finding for Sparse Domains using Window-Based Iterative Repairs
X*: Anytime Multi-Agent Path Finding for Sparse Domains using Window-Based Iterative Repairs
复制标题
DOI：
10.1016/j.artint.2020.103417
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Kyle Vedder;Joydeep Biswas
中科院分区：
文献类型：
--
作者：
Kyle Vedder;Joydeep Biswas
现实世界的多智能体系统，如仓库机器人，在很大的时间限制下运行-在这种情况下，而不是花费大量的时间来解决最优路径，而是更可取的是快速找到有效的，无冲突的路径，即使是次优的，并给予额外的时间，以迭代地完善这些路径，以提高其成本。在这样的领域中，我们观察到，代理-代理冲突aresparse-它们涉及小的本地代理子集，并在地理上包含在一个小区域的整体空间。利用这种洞察力，我们可以首先为每个代理单独规划路径，并在代理之间发生冲突的情况下，执行限于本地子空间窗口的小型本地修复。在时间允许的情况下，这些窗口可以连续增长，并在其中细化修复，从而提高路径质量，并最终收敛到全局联合最优解。利用这些见解，我们提出了两个算法的贡献：1）窗口化的任意时间多智能体规划框架（WAMPF）的一类随时规划者，快速生成有效的路径与次优估计，并生成最佳路径，给出足够的时间，和2）X*，一个有效的WAMPF为基础的规划。在WAMPF的修复生长步骤中，X* 能够通过采用重用技术有效地找到连续的有效解。实验上，我们证明了在稀疏域中：1）X* 在到达有效路径的时间上优于最先进的任何时间或最佳MAPF解算器，2）X* 在到达最佳路径的时间上与最先进的任何时间或最佳MAPF解算器竞争，3）X* 快速收敛到非常紧的次优性界限，以及4）X* 在针对少量代理的有效路径的时间上与现有技术的次优MAPF解算器竞争，同时提供高得多的质量路径。
Real-world multi-agent systems such as warehouse robots operate under significant time constraints – in such settings, rather than spending significant amounts of time solving foroptimalpaths, it is instead preferable to find valid, collision-free paths quickly, even if suboptimal, and given additional time, to iteratively refine such paths to improve their cost. In such domains, we observe that agent-agent collisions aresparse– they involve small local subsets of agents, and are geographically contained within a small region of the overall space. Leveraging this insight, we can first plan paths for each agent individually, and in the cases of collisions between agents, perform small local repairs limited to local subspacewindows. As time permits, these windows can be successively grown and the repairs within them refined, thereby improving the path quality, and eventually converging to the global joint optimal solution. Using these insights, we present two algorithmic contributions: 1) the Windowed Anytime Multiagent Planning Framework (WAMPF) for a class of anytime planners that quickly generate valid paths with suboptimality estimates and generate optimal paths given sufficient time, and 2) X*, an efficient WAMPF-based planner. X* is able to efficiently find successive valid solutions by employing re-use techniques during the repair growth step of WAMPF. Experimentally, we demonstrate that in sparse domains: 1) X* outperforms state-of-the-art anytime or optimal MAPF solvers in time to valid path, 2) X* is competitive with state-of-the-art anytime or optimal MAPF solvers in time to optimal path, 3) X* quickly converges to very tight suboptimality bounds, and 4) X* is competitive with state-of-the-art suboptimal MAPF solvers in time to valid path for small numbers of agents while providing much higher quality paths.