【重点推荐】Cooperative Heterogeneous MRS_2019_ACM_Part1

红袖舞墨 · 发表于水下机器人&ROV&AUV&UUV 2023-1-5 01:40:27

本期为American University of Beirut的 Yara Rizk 和 Mariette Awad 以及 United Technologies Research Center 的 Edward W. Tunstel 共同撰写的最新综述，主题为异构多机器人协同，介绍了任务分解、联盟形成、任务分配、感知SLAM、规划与控制等方面的多机器人协同课题。原文于2019年发表于ACM Computing Surveys Vol. 52, No. 2, 共31页，由于内容过长拆分为两篇来写。本篇为论文前半部分，涵盖Introduction、Multi Agent Systems、Existing MRS 和 Task Decomposition。

Cooperative Heterogeneous Multi-Robot Systems: A Surveydoi.org/10.1145/3303848

本文后半部分及相关Review见以下链接（还没写完QwQ）

燃雪：Review: Advances in Multi-Robot Systems_2002_TRA20 赞同 · 3 评论文章

燃雪：【重点推荐】Cooperative Heterogeneous MRS_2019_ACM_Part26 赞同 · 1 评论文章

物联网的出现和各种计算系统的广泛部署导致了完成各种任务的异构多代理系统(MAS)的形成。在确定现有MAS的局限性、遗留的挑战和可能的未来方向的同时，为了突出现有MAS的先进状态，我们调查了该领域最近的贡献。本文以机器人代理为研究对象，重点分析了MAS子领域在任务分解、联盟形成、任务分配、感知、多代理规划与控制等方面所面临的挑战。虽然有些部分比其他部分取得了更大的进步，但要将有效的自治MAS部署到真正的智能城市环境中，还需要进行更多的研究，因为与MAS假设的验证环境相比，实际的智能城市环境限制更多。具体来说，更自主的端到端解决方案需要通过实验测试和开发，同时结合自然语言本体和字典来自动分解复杂的任务，并利用大数据的进步来改进机器人的感知算法。

1、Introduction

我们生活的世界是动态的，不可预测的，这使得设计一个能够有效适应所有环境的自主机器人变得非常困难。因此，各种形状、大小、能力的机器人，如无人飞行器(UAVs)、无人地面飞行器(UGVs)、类人机器人等，都被设计成能够相互协作、与人协同完成复杂任务的机器人。随着物联网的出现，到2020年，这些设备的价值预计将超过200亿美元。允许这些设备进行合作将显著增加自动化任务的范围。在以下领域集成这些设备：医疗保健、交通系统、应急响应系统、家务和老年人护理等将使智慧城市更加智能。

在这项工作中，我们讨论了有关使用异构（Heterogeneous）多机器人系统(MRS)自动化执行复杂任务的文献，在此之前，我们对更一般的多智能体系统(MAS)领域进行了简要概述。本文介绍了实现自动化的工作流程的主要组成部分：任务分解、联盟形成、任务分配、感知、MAS计划和控制，并对每个领域的现有工作进行了调查，找出了一些尚存的挑战和未来可能的研究方向。

然而，异构MAS的许多方面不在本综述中涵盖。其中包括但不限于研究个体间奖励分配的信用分配（credit assignment）;共识问题（Consensus）；以及Leader-Follower框架下包含控制（Containment Control）。虽然机器人-机器人通信的通信协议使agent能够通过信息交换进行合作，以及寻求设计高效信息交换策略的信息流问题是MAS的重要组成部分，但我们不在本调查中包括它们。

面向MRS的端到端框架很少;最引人注目的是swarmanoid，它使用三种类型的机器人群集来完成搜索和检索任务。许多解决方案仍然需要大量的人工干预来实现复杂的任务。此外，MRS的个别方面也得到了解决，比如让机器人访问云上的信息，同时组建联盟和分配任务。然而，需要对IOT辅助机器人进行更多的端到端测试和MRS应用才能取得更大的进展。自然语言处理和字典可以帮助自动化复杂的任务分解，大数据的进步可以用来提高感知能力，从而提高决策能力。

与本文的工作最接近的两项综述发表于近10年前：一是MRS协调，包括任务分配、分解、资源分配。然而,它专注于以市场为基础的方法和不包括工作联盟的形成和决策模型。最近的一项调查讨论了觅食、编队控制、协同对象操作和位移、路径规划和足球等应用中现有的MRS架构、通信方案、群体机器人、任务分配和学习。

其他的调查比我们的工作范围更小，集中在一个特定的研究领域，如MAS的合作规划和控制模型和算法和MAS的分布共识。一些调查集中在MRS及其分配的任务上;Arai等人确定了MRS的七个主要研究领域，包括机器人架构、测绘和探索以及运动协调，并讨论了在每个领域的最新研究和挑战。Ota调查了分配给MRS的任务，将其分为到达点、清扫区域和复合任务，以及一次性和多时间任务，即需要多次迭代才能完成的任务。Murray调查了多车辆系统的协同控制及其在军事、运输系统和移动传感器网络中的应用。Portugal和Rocha对MRS的巡逻进行了调查，而Robin和Lacroix则专注于MRS目标的检测和跟踪。Yan等人研究了移动MRS中的协调，包括用于运动和任务规划的通信协议和决策算法。Doriya等提出了MRS中的通信与协调，包括隐式和显式通信算法。包括集中和分布式协调，包括任务分解、分配和执行。Merrick调查了决策算法。Grieco等人讨论了IoT-robotics集成以提高性能，并设想了医疗保健、军事和智能城市中的场景。

2、Multi Agent Systems

2.1 Intelligent Agent

智能体是一种物理的(机器人)或虚拟的(软件程序)实体，它可以在感知环境的同时自主地对环境执行动作以实现目标。理性的行为人寻求执行能带来最佳结果的行为。认知架构是“智能主体的底层基础设施”: 主体的大脑。它包括感知、推理、学习、决策、解决问题、互动和交流。它的评估基于特定领域的性能度量、通用性、通用性、合理性、最优性、效率、可伸缩性、自主性和可改进性。

文献中提出了许多agent分类。一种分类将agent区分为三种类型:reactive agent、deliberative agent和deliberative agent。reactive只是对环境变化作出反应。他们的工作流程包含两种基本元素:感觉(Sense)和行动(Action)。 deliberative agent 在没有任何外部刺激的情况下开始行动，并依赖于计划。这种sense-plan-act 或 sense-model-plan-act范式包含按顺序执行的三种基本要素:感觉(S)、计划(Plan)和行动(A)。Hybrid agent根据规划算法执行行动或对当前的感知做出反应。这三种类型的代理的工作流如图所示。更精细的分类将agent分为以下几种:简单反射(对当前的感觉输入作出反应)、基于模型的反射(保持环境的内部状态)、基于目标的反射(执行完成目标的动作)和基于效用的代理(最大化效用函数)。这四种类型被认为是学习代理，如果他们学习环境的一个元素或他们的控制算法的参数有监督。

图1：三种agent与多种异构Robot

2.2 Multi Agent Systems

MAS是由多个自主、相互作用的主体组成，这些主体有共同或冲突的目标和感觉信息。它们的特征是分散和不完全信息、异步计算和分散控制。然而,集中或混合动力系统也认为MAS。MRS将代理限制为物理机器人。MAS被看作是分布式人工智能中“涉及协调、并行行动和问题解决”的领域，第二个子领域是分布式问题解决。然而，Parker将分布式智能定义为执行诸如推理、解决问题和学习等认知功能的一组实体。认知计算系统这个术语也被用来指MAS，被定义为由多种智能代理组成的软硬件协同优化架构，这些智能代理可以与人类交互，并通过利用每个实体的优势来完成任务。移动认知在机器人、汽车和智能手机等移动平台上实现了分布式认知计算架构。

MAS评估标准是特定的或不变的。特定领域的标准对性能进行量化。搜救工作的绩效指标包括获救人数或扑灭火灾的人数。不变标准包括解决方案的最优性、算法的时间和空间复杂度、负载平衡、公平性、资源利用和重新分配速度、通信开销、对噪声和代理故障的鲁棒性和可伸缩性。

基于多种标准，MAS被划分为多个类别。一种分类根据agent的多样性和交际能力分为四类:同质非交际、同质交际、异质非交际和异质交际。Agent多样性可以来自感觉或驱动能力、认知算法或形态学。MAS也被分为集中、分层、分散或混合架构。考虑到agent交互，复杂性可分为三类:无直接交互、简单交互和复杂条件交互。

基于交互类型，MAS可以根据目标、资源和agent技能表现出合作、竞争和协作的交互。一个更广泛的分类是积极的和消极的，在这里agent相互帮助或互不干涉、阻碍其他agent。我们主要关注的是协作交互，agent意识到其他agent并拥有相同的目标，它们各自的行动导致共同目标的实现。举例来说，搜索和救援、探索、目标分类和置换对象等。

图1表示具有三个层次结构的异构MRS体系结构。在最高级别上，关于所有机器人和复杂任务的信息都可以在云中获得。机器人可以通过云进行通信，并利用云中的任何计算资源和可用信息。较低级别的(MRS)包含具有指定子任务的机器人子集。这个子集或联盟之间的交互是局部的，可以是已经讨论过的不同类型的交互之一。信息从各种机器人的传感器中收集并在它们之间交换。最后，最底层是agent，它可以进入自己的感官输入并控制自己的执行器。它可以与联盟内的其他机器人通信，也可以连接到云上。由于系统是异构的，代理不完全相同，可以有不同的认知结构(反应性、商议性或混合性)或不同的物理特性(例如UGVs和UAVs)。这三层体系结构会导致复杂的任务不能在简单的自动化框架下执行。

2.3 任务分类

善于合作的MRS被分配到各种各样复杂程度不同的任务。任务复杂性决定了任务的难度，从而影响完成任务所需机器人的数量和类型，可能由多个更简单的子任务组成。单机器人的任务可以由一个机器人完成，如小尺度地图、挑选和放置、导航等问题。多机器人任务需要多个协作机器人完成。根据成功完成任务所需的协作程度，可以进一步区分多机器人任务，从松散到紧密。松散协调的任务可以分解为子任务，这些子任务可以在机器人之间最小的交互下独立执行。例子包括大规模勘探和测绘、有害物质清理、跟踪和监视。在这种情况下，环境可以被划分为不相交的区域，机器人在指定的区域内操作。紧密耦合的任务是不可分解的，需要在机器人之间进行大量交互的情况下协调执行。例如机器人足球、物体运输和大型建筑施工。

2.4 多机器人系统工作流程

为了设计一个能够完成复杂任务的MRS系统，我们确定了四个主要设计模块：

任务分解，即将复杂任务分解为较简单的子任务;联盟组建，即组建代理团队;任务分配，将子任务分配给代理团队执行;任务执行/计划和控制，即通过对环境执行一系列的行动来完成一项任务。

除了对每个组成部分的各种输入和约束之外，文献还对不同组成部分采用了不同程度的自动化。图2给出了一种工作流程，该工作流程要求设计人员根据可用的机器人功能，将复杂的任务分解为更简单的子任务，并由一组代理组成联盟。然后由机器人团队自主执行任务分配以及机器人计划和控制。尽管许多研究人员选择在MRS中静态分配联盟以简化设计，但其他研究人员却执行了动态联盟形成。

图2： Workflow

目前的MRS系统大部分遵循图2中的框架，但有些系统并入了联盟自动形成算法。据我们所知，仍没有全自动系统的实现，即，给MRS分配了一个复杂的任务，并且系统将这个复杂的任务自动分解为子任务，组成联盟，并分配和执行了这些子任务。

该框架被认为是一种认知体系结构，通常嵌入到软件体系结构中，该体系结构可在抽象一些复杂性的同时实现各种组件的集成。在文献中已经开发了基于代理的建模和仿真工具，以对代理和MAS进行建模和测试。通常根据这些工具所实现的代理类型（例如，反应式或移动式），它们的建模强度和可伸缩性，它们的应用领域以及实现系统所需的努力来对其进行分类。许多软件架构都专门为机器人和MRS开发，它们使用特定于领域的建模和语言来创建功能更强大的建模工具。特定用于MRS的中间件体系结构，例如ROS，Orocos和OpenRTM，也已经开发出来，可以对通信协议进行建模，以通过硬件抽象提高功能的可移植性。机器人领域特定语言允许更高级别的抽象和自动化。

2.5 应用

结合了机器人代理，软件代理以及其他计算和传感设备的MAS在智慧城市中有许多应用，包括医疗保健，家庭服务和智能交通系统。诸如监视，导航和目标跟踪之类的军事应用还开发了MAS框架，以有效地自动化这些复杂任务。为了说明目的，我们讨论了可以使用MAS的两种情况：紧急响应和医疗保健。

MAS可以部署在紧急情况下。在自然灾害或人为灾害（战争）中，具有多种功能的机器人，如蛇形机器人、爬行器和微型无人机，可以在废墟中导航，搜寻受伤人员，而大型机器人则会将这些人救出，并将他们运到医院。运输机器人将能够从智能交通系统中获取最快路线的信息，并且交通信号灯可以被控制以引导交通。因此，MRS需要利用云和其他非机器人代理来改进系统。

在智能城市中，一个老年人护理系统可以由一个或多个能够为老年患者提供全天候物理护理的移动机器人和一个能够识别跌倒或医疗紧急情况并相应地通知移动机器人的监控系统组成。该系统可以进一步扩展，允许它与患者的医疗团队和亲属进行通信，以便进行更新和药物递送。Kraus讨论了机器人应该具备的有效帮助残疾患者的能力。它应该制定个性化的训练方案，监测患者的活动，并在需要时进行干预和提供鼓励。Woo等人开发了一个由无线传感器网络和一个机器人组成的系统，用于像所描述的场景那样的老年护理情况，但机器人仅用于陪伴，而不为患者提供身体护理。Benavidez等人提出了一种针对老年人和残疾人家庭护理的MRS，由云计算资源和执行各种任务的异构机器人组成，如房屋监控和地板清洁。

3. Existing MRS

许多异构MRS被提出来解决更广泛的复杂协作任务。这些系统允许异构机器人，即具有不同能力的机器人，如UAVs和UGVs，在复杂任务上进行协作。它们都朝着在现实世界中部署迈出了一步，但它们仍然做出一些假设或简化，从而限制了系统的泛化。接下来我们将讨论其中的一些系统，根据它们执行的协作任务的复杂性和自动化程度，从自动化程度最高到最低，对它们进行分组。在第一级（自动化程度最低）中，只有任务执行是自动化的，而第二级也可以自动分配任务或组建联盟，但不能两者都自动化。第三级自动化联盟的形成和任务分配，但不自动化任务分解。第四级自动化整个系统。图3描绘了现有工作在自动化和任务复杂性级别上的分布。表1总结了有关MRS及其任务的文献，只提到了自动化程度第二或更高的参考文献。目前没有任何工作可以实现第四级完全自动化

3.1 第三级自动化

一些参考文献实现了第三级自动化，其中联盟组建、任务分配和任务执行由MRS执行，而不受任何人为干扰。这些系统使用无人值守地面车辆进行寻宝、无人值守地面车辆进行监视、无人值守地面车辆导航和无人值守地面车辆探索。自治联盟形成和任务分配算法包括TraderBots，它基于拍卖、层次聚类、蚁群优化和记忆搜索算法和监督控制理论。这些算法主要在模拟环境或小规模实验中进行了测试，但已显示出有希望的结果。

3.2 第二级自动化

以下文献实现了第二层次的自动化，可分为两大类：（1）任务分解和联合由人工专家预先定义，但任务分配和执行由MRS自主执行；或（2）任务分解和分配由人工专家执行，但联盟形成任务执行由MRS执行。

第一组：自动分配和执行任务。应用包括医疗设施任务、协作导航和物体构造、障碍移除、足球机器人以及搜索和救援。

任务分配算法主要是基于拍卖的，其中代理根据其能力对任务进行投标，出价最高的人赢得执行任务；基于效用的算法，任务分配给具有最高效用或资格的代理，以及binary max sum规则。一些算法允许任务重新分配，在分布式框架中实现并允许机器人之间的通信。MRS系统包括成群的异构UGV、异构UAVs和能够重新配置形状的模块化机器人。参考文献通常包括模拟实验和真实世界实验，但主要集中在松散协调的任务上，如搜索和救援，这些任务比紧密协调的任务（如物体运输）简单。

第二组：自动联盟的形成和任务执行，用于各种应用，包括搜索救援和地雷探测。联盟由UGV或UAV组成，但不是两者的混合架构，这稍微简化了联盟的组建问题，因为机器人的能力不太多样化。在某些情况下，当考虑到它们的硬件能力时，机器人是同质的。这些工作中采用了各种联盟形成算法，包括群智能、粒子群优化、加权投票博弈和多阶段联盟形成算法。除了在模拟和真实环境中验证的勘探和地雷探测，其他参考文献仅给出了模拟结果。然而，为了简化实验，使用了同质机器人。这突出了在不受限制的实际应用中，部署具有自主动态联盟和自动任务执行的MRS的困难。

3.3 第一级自动化

最后，我们介绍了在MRS中只自动化任务执行阶段的参考文献，并根据任务复杂性对它们进行分组和排序。这些参考依赖于人类专家将任务分解为子任务，将机器人组合成联盟，并将任务分配给这些联盟。

PLASTIC-Policy的引入是为了发现在特种团队中机器人之间的最佳合作策略，允许机器人在任务执行中自适应，并在RoboCup足球机器人上得到验证。该问题被建模为马尔可夫决策过程（MDP），并采用拟合Q迭代算法进行求解。三个不同的机器人，一个高架起重机，一个移动机械手和一个移动摄像头被用来精确地放置一个长而重的横梁。地面和空中机器人的结合提高了整个系统的性能。开发了一种分布式循环Q学习算法，以使用一组UGV运输管子。

Swarmanoids是一种MRS框架，由三种功能互补的机器人群组成：眼机器人（带摄像头的四转子）、手机器人（夹爪）、脚机器人（轮式机器人：e-pucks）。系统进行了对象搜索和检测。人类设计者将复杂的任务分解为子任务。每一个子任务都可以由系统中的一种机器人来完成，即系统中的机器人被设计成子任务与机器人之间的一对一映射，消除了任务分配的需要。因此，该系统可以完成一个更复杂的任务，即使由于系统设计的原因，其工作流程自动化程度较低，其中包括技能互补的机器人和可以形成预定义联盟的单个机器人。

自然灾害场景下的水下搜救是使用无人水下航行器（UUV）和UAVs进行的。自主机器人进行了一个粗略的初步搜索，以确定感兴趣的区域，这些区域后来由遥控车辆进行了更彻底的调查。为了在救灾中收集信息，开发了一种导航和同步定位（SLAM）算法，OmniMapper SLAM基于图论和平方根平滑与映射。NavigationManager集成了基于搜索的路径规划和ARA*算法。

跟踪和监视通过利用机器人的异构性和不同的媒介（陆地、空气、水）来提高覆盖率。HiDDeN是一种分布式算法，用于监督UAV和UUV在军事监视和海岸安全应用中的任务完成情况。另外提出了一种分布式框架来控制地面MRS，其中UGV与UAVs合作完成由地面基站转发的任务。该系统在很大程度上依赖于无人地面车辆和无人值守地面车辆之间的通信。整个系统遵循基于行为的自治框架，其中子任务被表示为状态机中的功能组件。在一个三机器人系统上进行的目标检测和监视实验验证了该框架的有效性。有研究聚焦于无人机，具有不同传感能力的直升机和飞艇合作跟踪目标，并检查和监测一个区域。地面系统包括基于行为图的MRS避碰和设定点跟踪导航算法和基于贝叶斯决策规则的MRS巡逻并用6个机器人进行室内巡逻验证。

大量机器人被部署到入侵者的探测和跟踪中，他们利用少量昂贵的机器人和大量的低成本感知机器人对未知的室内环境进行探索和映射。通过与启用GPS的UGV合作，开发了一个框架，以改进UAVs对群体感兴趣的对象的自定位和定位。最后，UAV-UGV-MAS也被用于执行步态监测。

导航、探索和地图绘制任务也利用了UAV-UGV的合作。例如，大量执行运动任务的无人值守地面车辆都得到了与位置相关信息的无人机的帮助。同样，Stegagno等人。使用单一的无人机来提高无人地面车辆的SLAM能力。Mathew等人为执行包裹递送任务的微型无人机和无人车开发了路径规划算法。该问题被建模为一个多仓库配送问题，转化为广义的旅行商问题，并在多项式时间内用核序列枚举算法求解。使用UGV和UAVs来记录温度、湿度、气体水平等，实现了温室传感器监测。无人机采用遥控操作，无人车自主导航。

采用分布式Lyapunov综合算法可以实现避免碰撞的导航。有文章提出了一种分布式的多机器人深度优先搜索算法，使得无人地面车辆能够以最小的信息交换和避免碰撞的方式有效地探索未知环境。基于图论和网络理论，开发了一种协作导航算法，以确保移动机器人收集信息所探索的环境完全覆盖。分层算法允许能力有限的机器人通过接收来自更强大机器人的任务来执行映射和探索。

MRS的编队控制算法已经开发出来，以使用Lyaponuv框架控制UGV和UAVs，另有文章中仅提出了针对UGV的分布式Lyapunov控制器。轮式和腿式机器人被控制在给定的队形中导航和避开障碍物。最后，有研究开发了一个基于平面的异构UAVs协同算法。

4. Task Decomposition

任务分解是实现复杂任务自动化的MAS工作流程的第一步，它将复杂任务划分为一组更简单或更原始的子任务，这些子任务要么相互独立，要么顺序依赖。例如，映射一个建筑可以分为建筑中各个楼层和房间的映射。

任务分解问题的规划者可以是一般的或特定领域的。后者的一个例子是足球任务分解，其中根据球和球员的相对位置将覆盖的场地划分给机器人。球被视为一个引力源，在它周围产生一个引力场，并影响子任务的分配。虽然许多系统要求设计者手动将复杂任务分解为一系列更简单的子任务，但有些工作试图将此过程自动化，并可分为三大类ecompose-then-Allocate、Allocate-then-Decompose和同时分解和分配.

Decompose-then-Allocate算法首先以集中的方式将一个复杂的任务分解成一个子任务列表，然后将各个子任务分配给可用的代理。任务树分解基于战场逻辑关系的任务划分。自动分解和抽象学会了使用互信息度量将复杂的决策任务分成子任务。在一个环境中行人跟踪是根据地理位置的接近程度动态划分的。由于需要对特定领域的高度理解来了解子任务之间的关系。Allocate-then-Decompose算法，如M+算法，首先将任务列表分配给agent，然后每个agent将该任务划分为更原始的子任务。这种方法允许代理根据代理的特定技能集分解任务，从而有效地执行任务。最后，同步任务分解和分配算法选择不解耦任务分解和分配步骤，并提出了一种基于任务树和拍卖的解决方案。这种方法通过提供反馈来改进基于agent能力的任务分解，从而产生更多特定于系统的分解。但是，由于子任务的微调，这可能会更加耗时。