机构名称：
¥ 1.0
多代理路径查找（MAPF）是在共享环境中发现无碰撞路径的问题，每个代理一个是每个代理的一个问题，同时最小化了旅行时间的总和。由于最佳地求解MAPF是NP-HARD，因此研究人员已经使用了副本且有效地求解MAPF的算法。基于优先级的搜索（PBS）是为此目的的领先算法。它一次找到一个单个代理的路径，并通过将优先级分配给碰撞代理并在其搜索过程中重新确定其路径来解决碰撞。但是，对于具有高密度的代理和障碍物的MAPF实例，PBS变得无效。因此，我们介绍了贪婪的PBS（GPB），该PBS（GPBS）使用贪婪的策略来通过最大程度地减少代理之间的碰撞数量来加快PBS。然后，我们提出了进一步加速GPB的技术，即部分扩展，目标推理，诱导的约束和软重新启动。我们表明，具有所有这些改进的GPB的成功率高于1分钟的运行时间限制的最先进的次优算法，尤其是对于具有小地图和密集障碍的MAPF实例。
基于贪婪优先级的搜索次优多代理路径查找
主要关键词
相关文件推荐
