From Feasibility Tests to Path Planners for Multi-Agent Pathfinding
From Feasibility Tests to Path Planners for Multi-Agent Pathfinding
复制标题
从可行性测试到多智能体寻路的路径规划器
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Kostas E. Bekris
中科院分区：
文献类型：
--
作者：
A. Krontiris;Ryan Luna;Kostas E. Bekris
多智能体寻路是与组合搜索相关的一个重要挑战，并且具有许多应用，例如仓库管理、机器人和计算机游戏。寻找最佳解决方案是 NP 难题，并且会引发最佳求解器的可扩展性问题。然而有趣的是，检查实例的可行性需要线性时间。这些线性时间可行性测试可以扩展以提供路径规划器，但据作者所知，尚未为一般图提供这样的求解器。这项工作首先描述了一种路径规划器，其灵感来自于一般图上多智能体寻路的线性时间可行性测试。初步实验表明，可扩展性合理，但相对于现有的次优解决方案，路径质量较差。这导致了一种算法的开发，该算法相对于替代方案实现了高效的运行时间和路径质量，并在可用的基准上找到了解决方案。本文概述了最终方法与可行性测试和现有次优规划器的关系。实验结果评估了不同的算法，包括最佳求解器。
Multi-agent pathfinding is an important challenge that relates to combinatorial search and has many applications, such as warehouse management, robotics and computer games. Finding an optimal solution is NP-hard and raises scalability issues for optimal solvers. Interestingly, however, it takes linear time to check the feasibility of an instance. These linear-time feasibility tests can be extended to provide path planners but to the best of the authors’ knowledge no such solver has been provided for general graphs. This work first describes a path planner that is inspired by a linear-time feasibility test for multi-agent pathfinding on general graphs. Initial experiments indicated reasonable scalability but worse path quality relative to existing suboptimal solutions. This led to the development of an algorithm that achieves both efficient running time and path quality relative to the alternatives and which finds a solution on available benchmarks. The paper outlines the relation of the final method to the feasibility tests and existing suboptimal planners. Experimental results evaluate the different algorithms, including an optimal solver.