DODRL-HMRTA：一种面向动态不确定性下异构多机器人任务分配的基于学习的优化框架

《Neurocomputing》：DODRL-HMRTA: A learning-based optimization framework for heterogeneous multi-robot task allocation with dynamic uncertainties

　　

# 摘要

异构多机器人系统正被越来越多地部署用于执行复杂的协作任务，但现有方法往往忽视复杂的现实约束和动态因素，并且在大规模场景下计算效率较低。本文将异构多机器人任务分配问题（HMRTA）形式化为马尔可夫决策过程模型，利用新定义的局部感知场和分层奖励机制，并提出一种基于深度强化学习（DRL）的动态优化框架，以增强在不确定环境中的适应能力。该框架在训练过程中采用两种动态策略来提高样本多样性，并整合决策监督与探索加速机制以提升解的质量和效率。我们提出两种决策顺序和推理算法，以处理静态和动态任务分配。实验结果表明，与元启发式算法相比，我们的框架将运行时间减少了2至3个数量级，同时达到了其最优解质量的92%。它还在不同问题规模上具有良好的泛化能力，并能有效适应动态场景，展现出卓越的扩展性和鲁棒性。实验演示视频见：https://youtu.be/TbHEGRjXOPA。

# 引言

近年来机器人技术的快速发展使其在各行各业中得到了更深入的融合应用。在工业领域，协作机器人受到了广泛关注[1]。在仓储和服务行业，移动机器人系统已成为自动化货物搬运和分拣任务的重要组成部分[2]。同时，专用机器人正在具有社会影响力的应用中发挥作用，例如灾害救援[3]、检测[4]和复杂地形的探索[5]。随着机器人应用日益复杂，任务种类和数量不断增长，传统的单机器人方法已不再足够。多机器人系统（MRS）提供了更大的灵活性、可扩展性和增强的协作能力[6]。在许多情况下，由具有不同功能且能够协作的机器人组成的异构多机器人系统具有显著优势。然而，这也带来了协调多个机器人以在确保安全的前提下完成复杂任务的挑战。

该问题可描述如下：给定一组任务和一组机器人，目标是以最优方式将任务分配给机器人，从而实现整体目标。Gerkey和Mataric率先对该问题进行了正式的理论与分析[7]，并基于三个维度（机器人、任务以及分配是否瞬时）将其分为八类。除了单机器人任务、单任务机器人和瞬时分配这一相对简单的情况外，其他情况均为NP-hard问题。为解决这一挑战，已有大量研究开展。许多研究将多机器人任务分配（MRTA）、多旅行商问题（mTSP）和车辆路径问题（VRP）等问题扩展到MRTA中进行描述[8]，但大多数假设机器人同质性或仅根据容量区分机器人[9]。关于实际场景中任务之间的复杂依赖关系也进行了进一步分析[10]，强调了多个机器人之间的交叉调度依赖。此外，Nunes等人[11]讨论了任务的时间与顺序约束，指出这些约束与复杂任务依赖往往同时出现并相互影响。大多数旨在获得最优解的研究往往过于简化了现实问题描述[12]。然而，多机器人系统运行在不完美环境中，信息可能不准确或不完整。例如，机器人故障、动态任务、未知环境或不可预见事件使问题复杂化，并对所谓的"最优解"产生负面影响。因此，动态环境中的任务分配问题必须在解质量、实时响应性和对动态扰动的鲁棒性之间取得平衡，这具有重要的实际意义。

本文针对具有复杂时间和顺序约束的异构多机器人任务分配问题（HMRTA-TO），同时考虑各种动态不确定性。近年来人工智能的最新进展，特别是结合了强大的表示学习能力和强化学习决策能力的深度强化学习（DRL），在组合优化问题中取得了显著成功[13]、[14]。然而，基于DRL的方法很少应用于MRTA[15]。为此，我们提出了一种专为HMRTA-TO问题量身定制的新型基于马尔可夫决策过程（MDP）的动态优化框架，融入了基于DRL的训练框架和两种推理模式来处理动态不确定性。我们将该方法命名为基于DRL的HMRTA动态优化（DODRL-HMRTA）。实验结果表明，所提框架能够高效求解静态和动态问题，与元启发式算法相比实现了两到三个数量级的实时性能提升，同时保持较高的解质量。此外，它还展现出对更大问题的可扩展性和对相似场景的适应性。本文的主要贡献如下：

• 一个用于HMRTA-TO问题的新型马尔可夫决策过程模型，利用局部感知场（LPF）和分层奖励机制。

• 一个考虑动态不确定性的综合训练框架，以及两种决策顺序和决策监督机制，以确保静态和动态调度的可靠推理。

• 实验结果表明，所提算法实现了高实时性能，保持了良好的解质量，有效处理各种动态不确定性，可针对更大问题规模进行扩展，并能适应具有相似特征的场景。

如图1所示，本文其余部分组织如下：第2节回顾相关综述和最新技术。第3节构建HMRTA-TO问题的优化模型。第4节详细描述所提出的MDP模型，包括训练和推理过程。第5节呈现并分析实验结果。最后，第6节总结全文并讨论潜在的未来研究方向。

# 相关工作

多机器人任务分配（MRTA）的研究可以追溯到几十年前。由于其组合特性，MRTA通常被建模为优化问题，其数学模型源自运筹学。多旅行商问题（mTSP）、车辆路径问题（VRP）和线性分配问题（LAP）等已被扩展到MRTA中，以形式化特定场景下的目标和约束[15]。

# 背景与问题建模

本文所解决的问题定义如下。设存在一组机器人和一组任务。某些任务具有优先级约束，只有在其前序任务完成后才能执行。每个任务有特定的资源需求、截止日期和执行时间。值得注意的是，某些机器人具有双重能力，使其能够执行两种类型的任务。如果某个机器人发生故障，任何未完成的任务将被重新分配给具备相应能力的其他机器人。

## 局部感知场模型（LPF）

在实际的多机器人系统（MRS）中，机器人在指定位置执行任务。由于资源有限和当前位置的限制，机器人无需全面估算所有潜在任务的效用。相反，我们引入了局部感知场（LPF），允许机器人过滤掉在当前位置和时间不可行或代价过高的任务。LPF被定义为以机器人当前位置为中心的区域，其...

# 实验结果与分析

在本节中，我们首先介绍实验设置，并在全知任务信息的三种问题规模下，将所提算法的性能与三种元启发式算法进行比较。比较主要关注目标函数和计算时间，证明所提算法在保持解质量的同时显著提高了求解速度。接下来，我们测试所提算法的泛化能力和可扩展性。我们还...

# 结论

总之，本文提出了DODRL-HMRTA，一种基于DRL的异构多机器人任务分配动态优化框架，专门用于解决复杂的时间和顺序约束问题。在自定义HMRTA-TO问题实例上，与各种元启发式方法相比的对比结果表明，所提方法在保持高解质量的同时实现了令人满意的实时性能。此外，该算法具有较强的泛化能力以及...

# CRediT作者贡献声明

曾奎：原稿撰写、验证、方法论。
方秋：审阅与编辑、指导、资源、调研、经费获取。
高长青：方法论、形式化分析、数据管理。
王立军：审阅与编辑、可视化。
严文彬：验证、软件。
王耀南：指导、经费获取。

# 利益冲突声明

作者声明以下可能被视为潜在利益冲突的财务利益/个人关系：
王耀南报告中国国家自然科学基金提供了财务支持。方秋报告湖南省科技创新计划提供了财务支持。如有其他作者，他们声明不存在任何已知的可能影响其工作的财务利益或个人关系。

曾奎 湖南大学电气与信息工程学院电子信息专业硕士候选人。他于2020年获得湖南大学自动化学士学位。其研究兴趣涵盖多机器人任务分配和路径规划。

曾奎 | 方秋 | 高长青 | 王立军 | 严文彬 | 王耀南

湖南大学机器人视觉感知与控制技术国家工程研究中心，人工智能与机器人学院，中国湖南省长沙市，410082