针对承担终身取货和送货任务的有限能力代理的任务分配策略

《Knowledge-Based Systems》：Task Assignment Strategies for Capacitated Agents Engaged in Lifelong Pickup and Delivery Tasks

本研究针对多智能体有容量取送任务分配问题，提出基于接近中心性、Hausdorff距离和成本估计的任务分配策略，并在自动化仓库模拟中进行评估。实验表明，成本估计方法显著提升效率，接近中心性方法效果不佳，Hausdorff距离在大容量场景下表现较好。

　　这项研究聚焦于一个名为多智能体拾取与交付（Multi-Agent Pickup and Delivery, MAPD）的问题，它是经典多智能体路径规划（Multi-Agent Path Finding, MAPF）问题的一个长期版本。MAPD引入了容量增强的智能体，这些智能体可以携带多个物品，从而能够同时执行多个任务。任务的执行通常涉及一系列拾取和交付地点（即航点），以完成分配的任务。在决定智能体的下一个任务时，传统方法是选择距离智能体当前位置最近的拾取地点的任务。然而，本研究提出了一种新的观点，即通过优化这些具有容量限制的智能体的任务分配，可以显著提升多智能体路线规划的整体质量。

研究团队提出了一种名为“Token Passing with Multiple Capacity (TPMC)”的算法，该算法基于“Token Passing (TP)”算法，该算法最初用于解决MAPD问题。TPMC继承了TP中的初始化、智能体选择和死锁预防机制，同时重新设计了任务分配和路径规划部分，以充分利用智能体的容量优势。研究的主要目标是评估不同任务分配策略对TPMC算法效率的影响。为此，研究团队开发了三种不同的任务分配方法，分别基于“接近中心性”（Closeness Centrality）、“Hausdorff距离”（Hausdorff Distance）和“基于成本的估计”（Cost-Based Estimation）。这些方法在模拟的小规模和大规模自动化仓库环境中进行了评估，重点考察了它们在完成时间（makespan）方面的表现。

在实验结果中，基于“接近中心性”的方法在大多数情况下未能显著提升解决方案的质量。这表明，虽然该方法在理论上具有一定的合理性，但在实际应用中可能并不足够有效。相比之下，基于“Hausdorff距离”的方法在高容量智能体的场景中表现良好，能够更有效地分配任务。而“基于成本的估计”方法则在所有测试场景中都显示出显著的改进效果，表明其在任务分配中的实用性较高。这些发现为未来多智能体路径规划问题的解决提供了新的思路，尤其是在需要长期运作的自动化环境中。

在自动化仓库领域，多智能体拾取与交付问题（MAPDC）具有重要的现实意义。随着物流行业的不断发展，自动化仓储系统的需求日益增长，这些系统通常需要多个具有容量限制的智能体来执行复杂的任务。在这些场景中，任务的分配不仅要考虑智能体的当前位置，还要综合考虑任务的路径、时间以及与其他智能体的协调。因此，研究团队提出了一种新的任务分配策略，旨在提高任务分配的效率和效果，从而优化整体的路径规划方案。

为了实现这一目标，研究团队采用了多种策略。其中，基于“接近中心性”的方法旨在衡量任务与智能体航点之间的接近程度。该方法的核心思想是，如果一个任务的航点距离智能体当前的航点较近，那么该任务可能更适合当前的智能体执行。然而，实验结果显示，这种方法在大多数情况下未能显著提升解决方案的质量，说明其在实际应用中可能存在一定的局限性。

另一种方法是基于“Hausdorff距离”，该方法衡量的是智能体当前航点集合与候选任务的起点和终点集合之间的距离。通过这种方式，研究团队能够更全面地评估任务的可执行性，而不仅仅依赖于起点的距离。实验表明，在高容量智能体的场景中，这种方法能够有效提升任务分配的质量，从而优化整体的路径规划效果。

最后，研究团队提出了一种基于“成本估计”的方法，该方法综合考虑了任务执行的成本，包括路径长度、时间以及可能的冲突。这种方法的优势在于，它能够更准确地预测任务的执行效率，从而为智能体选择最合适的任务。实验结果表明，该方法在所有测试场景中都显示出显著的改进效果，说明其在多智能体路径规划中的潜力较大。

此外，研究团队还对TPMC算法进行了优化，以确保其在大规模任务分配场景中的完整性和效率。优化后的TPMC算法不仅能够更有效地处理任务分配问题，还能够更好地应对实际环境中的动态变化。这些改进对于提升自动化仓储系统的运行效率具有重要意义。

在实验设计方面，研究团队选择了两个不同的模拟仓库环境进行测试。第一个环境是MAPD研究中常见的基准测试场景，它是一个四邻域网格环境，适用于评估多智能体路径规划的基本性能。第二个环境则是一个更复杂的自动化仓库模型，用于测试任务分配策略在大规模场景中的表现。通过这两个环境的对比实验，研究团队能够更全面地评估不同任务分配策略的有效性。

实验结果显示，基于“接近中心性”的方法在大多数情况下未能显著提升解决方案的质量，而基于“Hausdorff距离”和“基于成本估计”的方法则在不同程度上表现出更好的效果。特别是在高容量智能体的场景中，基于“Hausdorff距离”的方法能够更有效地分配任务，从而减少整体的完成时间。而“基于成本估计”的方法则在所有测试场景中都显示出显著的改进效果，表明其在任务分配中的广泛应用潜力。

在实际应用中，多智能体路径规划问题不仅需要考虑任务的分配，还需要考虑路径的优化、时间的协调以及系统的动态性。因此，研究团队提出的任务分配策略不仅适用于静态环境，还能够适应动态变化的场景。这为未来自动化仓储系统的优化提供了新的方向，特别是在需要长期运作和实时调整的场景中。

总的来说，这项研究为多智能体路径规划问题提供了新的思路和方法，特别是在具有容量限制的智能体任务分配方面。通过引入“接近中心性”、“Hausdorff距离”和“基于成本估计”等新的任务分配策略，研究团队能够更有效地优化多智能体路径规划方案，从而提升自动化仓储系统的运行效率。这些方法的提出不仅有助于解决当前研究中的不足，还为未来相关领域的研究提供了宝贵的参考。