论文标题
多进球多代理拾取和交付
Multi-Goal Multi-Agent Pickup and Delivery
论文作者
论文摘要
在这项工作中，我们考虑了多代理拾取和交付（MAPD）问题，在该问题中，代理商不断参与新任务，并需要计划无碰撞路径以执行它们。要执行任务，代理需要访问由接送位置和交货位置组成的两个目标位置。我们提出了两种算法的变体，该变体使用Anytime Algorithm大型邻里搜索（LNS）为每个代理分配一系列任务，并使用多代理路径查找（MAPF）基于基于优先级的搜索（PBS）计划路径。 LNS-PBS已完整地用于良好的MAPD实例，MAPD实例的现实子类，并且比现有完整的MAPD算法中央更有效。 LNS-WPBS没有提供完整的保证，但在经验上比LNS-PBS更有效和稳定。它扩展到大型仓库中数千个代理商和数千个任务，并且在经验上比现有的可伸缩MAPD算法HBH+MLA*更有效。 LNS-PBS和LNS-WPB也适用于MAPD的更一般变体，即多目标MAPD（MG-MAPD）问题，其中任务可以具有不同数量的目标位置。
In this work, we consider the Multi-Agent Pickup-and-Delivery (MAPD) problem, where agents constantly engage with new tasks and need to plan collision-free paths to execute them. To execute a task, an agent needs to visit a pair of goal locations, consisting of a pickup location and a delivery location. We propose two variants of an algorithm that assigns a sequence of tasks to each agent using the anytime algorithm Large Neighborhood Search (LNS) and plans paths using the Multi-Agent Path Finding (MAPF) algorithm Priority-Based Search (PBS). LNS-PBS is complete for well-formed MAPD instances, a realistic subclass of MAPD instances, and empirically more effective than the existing complete MAPD algorithm CENTRAL. LNS-wPBS provides no completeness guarantee but is empirically more efficient and stable than LNS-PBS. It scales to thousands of agents and thousands of tasks in a large warehouse and is empirically more effective than the existing scalable MAPD algorithm HBH+MLA*. LNS-PBS and LNS-wPBS also apply to a more general variant of MAPD, namely the Multi-Goal MAPD (MG-MAPD) problem, where tasks can have different numbers of goal locations.
