💻 computer science

Bi-Layer Ant Colony Optimization for Multi-Robot Task Allocation and Routing in Delivery Applications

本文提出了一种双层蚁群优化算法，该算法将任务分配与路径规划统一为一个单一优化问题，通过在多机器人配送应用中与混合整数线性规划（MILP）和粒子群优化（PSO）基准模型相比，实现了减少高达17.7%的总行驶距离和近20%的完成时间，从而展示了卓越的效率和可扩展性。

原作者： Le Na Nguyen, Thanh Long Nguyen, Thanh Thao Ton Nu, Quan Le, Manh Duong Phung

发布于 2026-08-26

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Le Na Nguyen, Thanh Long Nguyen, Thanh Thao Ton Nu, Quan Le, Manh Duong Phung

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在繁忙的现代物流世界中，货物的移动依赖于协同工作的移动机器人集群。这些机器必须在复杂的环境中导航，以提取物品并将其运送到特定的目的地，但挑战不仅在于从 A 点行驶到 B 点。真正的难点在于协调：决定哪台机器人应该处理哪个包裹，并确定访问一系列地点的最有效顺序。如果这些决策是孤立做出的，机器人可能会不必要地交叉路径，行驶比需要更长的距离，或者在其他机器人工作时闲置等待。这个问题被称为多机器人任务分配，处于机器人技术与数学的交汇点，其目标是协调一组独立的智能体，以实现集体目标并达到最高效率。对于配送服务而言，一个好的计划与一个伟大的计划之间的区别，直接转化为节省的时间、降低的能耗以及为客户提供更快的服务。

富兰克林大学越南分校（Fulbright University Vietnam）和文科大学（VinUniversity）的研究人员提出了一种解决这一协调难题的新方法，不再采用将问题分解为独立步骤的传统方法。他们不再先决定哪台机器人承担哪项工作，然后再确定每台机器人的路线，而是将这两个决策视为一个单一且相互关联的问题。他们开发了一个受真实蚂蚁觅食行为启发的系统。在自然界中，蚂蚁在移动时会留下一种被称为“信息素”的化学气味；路径上的气味越强，其他蚂蚁跟随该路径的可能性就越大，最终引导蚁群找到前往食物的最短路径。研究人员将这一生物学原理转化为一种计算机算法，能够同时学习分配机器人任务的最佳方式以及访问它们的最佳顺序。通过使用两层这种数字气味轨迹——一层引导哪台机器人承担哪项任务，另一层引导每台机器人的停靠顺序——该系统使整个机群能够作为一个统一的整体来优化其性能，而不是作为一系列独立的实体。

为了测试这一想法，团队使用标准的机器人软件创建了一个模拟环境，在充满静态障碍物的 10 米乘以 15 米的空间内放置了三台完全相同的机器人。他们进行了实验，要求机器人完成五项、十项或二十项交付任务，每次运行的取货和卸货位置都是随机生成的。这种新算法与该领域使用的另外两种常用方法进行了对比测试：一种依赖严格的数学计算来寻找完美答案，另一种则使用不同类型的群集智能。结果显示，这种新方法始终优于其他方法。在模拟中，与严格的数学方法相比，该算法减少了高达 17.7% 的机器人总行驶距离；与另一种群集智能方法相比，减少了近 10% 的行驶距离。它还大幅缩减了时间，在某些情况下将总完成时间缩短了近 20%。

这种方法的成功在于其观察全局的能力。传统方法通常将任务分配和路径规划作为两个独立的阶段来解决，这可能导致次优的结果，因为一个好的分配可能需要一条困难的路径，或者某种分配可能导致一条短路径变得无法实现。通过同时解决这两个问题，新系统避免了这些陷阱。模拟表明，随着任务数量的增加，新方法保持了稳定和高效，而其他方法则表现出更多的变数，并且往往产生更长的路径。研究人员观察到，该算法不仅找到了更短的路径，而且具有高度的一致性，这表明它是管理复杂配送场景下机器人机群的可靠工具。虽然这些发现来自计算机模拟而非现实世界的街道测试，但它们提供了强有力的证据，证明将任务分配和路径规划视为一个耦合问题可以显著提高多机器人系统的效率。这项工作表明，如果未来的配送机群能够采用这种统一的决策方法，它们将能以更快的速度和更低的能源成本进行运作。

技术摘要：用于多机器人任务分配与路径规划的双层蚁群优化算法

问题定义

本文针对物流与配送场景下的多机器人任务分配（MRTA）问题进行了研究。其核心挑战在于协调一组移动机器人来执行一系列配送任务，其中每个任务都包含一个特定的取货位置和一个送货位置。

该优化问题被定义为一个需要同时输出两个结果的耦合决策过程：

任务分配（Task Assignment）： 确定由哪台机器人执行特定的每个任务。
任务排序（Task Sequencing）： 确定机器人执行其分配到的任务的最佳顺序。

目标是在确保每个任务都由单台机器人精确执行一次的前提下，最小化整个机队的总行驶距离。作者指出，现有方法通常将分配、排序和执行视为分别优化的独立阶段。这种分离可能导致全局协调性差、冗余运动以及系统效率降低。本文将 MRTA 建模为一个统一的优化问题，其中分配决策与排序决策是相互依赖的。

方法论：双层蚁群优化（ACO）

为了解决上述优化问题，作者提出了一种**双层蚁群优化（Bi-Layer ACO）**算法。与通过顺序求解各层的传统层次化方法不同，该方法将两个相互依赖的决策层集成到单个蚁群过程中。

核心框架

该算法采用了一种受蚂蚁觅食行为启发的群体智能元启发式算法。每个“蚂蚁”通过同时在两个决策层中导航来构建一个完整的解：

任务分配层：
- 确定任务向机器人的分配情况 ( $x_{i,j}$ )。
- 利用信息素矩阵 $\tau_{assign} \in \mathbb{R}^{m \times n}$ （任务 $\times$ 机器人）来表示分配任务 $j$ 给机器人 $i$ 的习得期望度。
- 启发式信息 ( $\eta_{assign}$ ) 源自机器人起始位置与任务取货位置之间距离的倒数。
任务排序层：
- 确定分配给每台机器人的任务访问顺序 ( $\pi_i$ )。
- 利用信息素矩阵 $\tau_{seq} \in \mathbb{R}^{m \times m}$ 来表示在同一台机器人的路径内，从任务 $j$ 过渡到任务 $k$ 的期望度。
- 启发式信息 ( $\eta_{seq}$ ) 源自当前任务送货位置与下一个任务取货位置之间距离的倒数。

算法执行

算法通过迭代循环进行：

构建（Construction）： 每只蚂蚁根据分配层的信息素值和启发式值，以概率方式将任务分配给机器人。一旦完成分配，排序层会为每台机器人构建路径。第一个任务的选择基于其与机器人起始点的接近程度，随后的任务则根据排序层的信息素值和启发式值进行采样。
评估（Evaluation）： 计算所构建解的总行驶距离，包括所有机器人的行驶距离之和（起始点到取货点、取货到送货、以及送货到下一个取货点的距离）。
信息素更新（Pheromone Update）： 在所有蚂蚁构建完方案后，对两个矩阵上的信息素轨迹进行更新。这包括：
- 挥发（Evaporation）： 降低现有的信息素水平以防止停滞。
- 强化（Reinforcement）： 根据解的质量 ( $Q/C(a)$ ) 沉积新的信息素，其中成本越低（即更好的解）的蚂蚁沉积的信息素越多。更新方程确保了分配对以及路径中特定的任务转换都能得到强化。

主要贡献

本文确定了以下主要贡献：

统一的目标函数： 提出了一个新的代价函数，将 MRTA 转化为一个耦合优化问题，明确捕捉了全局任务分布与局部路径规划之间的相互依赖关系。
双层 ACO 架构： 引入了一种新颖的算法框架，通过两个截然不同的、相互关联的信息素矩阵，将分配与排序集成到单个蚁群过程中。这实现了任务分配与路径规划的同步优化。
性能验证： 通过综合对比实验，证明了该方法相对于混合整数线性规划（MILP）和粒子群优化（PSO）的有效性。

实验结果

所提方法在 ROS 2 Humble 和 Gazebo 仿真环境中进行了评估，使用了三台 TurtleBot3 机器人。实验涵盖了包含 5、10 和 20 个任务的三种场景。

性能指标：

总行驶距离： 双层 ACO 在所有任务规模下均取得了最低的平均总行驶距离。
- 与 MILP 相比，ACO 减少了约 17.7% 的总距离（在 5 个任务时）。
- 与 PSO 相比，ACO 减少了约 9.8% 的总距离。
完成时间： 所提方法也展示了更快的任务完成时间。
- 与基准方法相比，ACO 缩短了近 20% 的完成时间。
稳定性与可扩展性：
- 与 PSO 和 MILP 相比，ACO 在距离和时间方面的标准差更低，表明其具有更稳定的收敛性。
- 随着任务复杂度增加（高达 20 个任务），ACO 保持了卓越的性能，而 MILP 和 PSO 则表现出更高的离散度和更高的成本。

意义与主张

论文声称，所提出的双层 ACO 框架有效地解决了现有 MRTA 方法中任务分配与路径规划分离的局限性。通过对这些决策进行联合优化，该方法减少了冗余运动并提高了整体任务执行效率。

作者得出结论，双层 ACO 是多机器人配送任务的一种可扩展且可靠的解决方案，它在探索（Exploration）与开发（Exploitation）之间取得了平衡，能够比传统的精确算法（MILP）或其他元启发式算法（PSO）产生更短、更一致的路径。该研究表明，这种统一的方法对于增强现实世界物流与配送系统的效率具有重要价值。作者指出，未来的工作将侧重于将该方法扩展到动态环境、异构机器人集群以及通信受限的场景。