机器人集群路径规划技术研究现状*

高 明，唐 洪，张 鹏

(1.国防科技大学 智能科学学院，湖南 长沙 410073；2.国防科技大学 研究生院，湖南 长沙 410073；3.国防科技大学 教务处，湖南 长沙 410073)

设机器人集群通过简单的相互作用和环境相互作用，使大量机器人能够完成复杂的任务[1]。机器人集群从诸如蚂蚁、蜜蜂、鱼群、鸟群等社会型群居生物中汲取灵感衍生出群体智能(swarm intelligence)的新概念，该术语最初由Beni和Wang于1989年在其蜂窝机器人系统的背景下提出，其现象是当它们遵循非常简单的规则，并通过个体之间进行简单的交互时，群体能够展现出智能、灵活、高效、可扩展和高可靠等优势。例如：蚁群可以共同努力建立巨大的巢穴，鱼群能够共同抵御比自己个头大几百倍的鲸鲨，鸟群则能够在迁徙过程中形成特定队形以实现节能飞行，等等。当然，该现象不仅局限于低端生物，即便在具有高等智能的人类身上也会自发地出现，比如人群仅凭借简单的观察和神经反射就会避免拥挤。群体的行为由个体局部交互涌现，这种行为是自组织的，具有自适应和完全分散的特点。群体智能模拟“分散的自组织系统的群体行为”[2]。这些系统通常是简单智能体，它们彼此之间以及与环境相互作用。虽然他们缺乏对系统全局状态的了解以及根据一系列简单规则来行动的能力，但他们之间的相互作用往往会在某些情况下产生全局行为并智能涌现。任何群体智能行为都具有两个基本特征[3]：自组织和分工。自组织是指一组动态机制，它们为智能体纯粹的底层交互建立基本规则，并产生全局层面可观察的现象；分工则指的是不同的任务由特定个体同时执行，它们相互合作以实现更大的目标。

机器人领域的学者和研究人员为了更好地了解社会型群居生物如何相互作用并实现目标，开始模拟这些群体及其行为，因此形成了“机器人集群”这个新的研究领域，从而能够将机器人应用于更广泛的领域。目前，机器人集群已经在以下任务背景下开展研究：

1)聚合，指机器人在空间上组合在一起。聚合用于将集群中的机器人足够靠近，并且可以用来作为执行一些任务的起点，比如集体运输。

2)按图形编队，指机器人编队形成特定的几何图案，如圆形、正方形、线形、星形、格子等。这些图形可确保集群保持通信范围和克服环境限制，比如形成一条链通过狭窄通道。

3)物理连接，指机器人彼此连接以形成特定结构。用于增加机器人的牵引力，比如在粗糙地形上移动时为集群提供稳定性，组装成特定结构用于搭建房屋等。

4)收集和组装零件，收集遍布环境中的零件并在特定区域中组装它们。可用于产生二维或三维结构(例如墙壁)。

5)导航，指机器人集群内相互导航。某个机器人不知道它们的实际位置或目标的位置，集群可由先前部署的机器人提供方向引导，形成通信中继。如机器人从猎物到巢穴形成链条，并在觅食任务中指明其他机器人的方向。

6)绘图+定位，指机器人集群获取环境地图的过程。绘图和定位通常是一起解决的，首先，它用于对以前未知的环境进行绘图;其次，确定机器人或目标位置。

7)部署，指通过集群覆盖尽可能多的空间来解决在环境中部署机器人的问题。可应用于安防或监视等场合。

8)协调运动，指移动的同时保持队形，可用于相互之间避碰和规避外部障碍物。

9)集体运输，指机器人协作共同运输物体。

10)集体表决，指在一致性和集体决策中，机器人必须就共同决策达成一致，例如选取哪条路径或跟踪哪些目标。

11)觅食，指机器人集群寻找猎物并将其带回巢穴。可应用于联合搜索和救援行动。

当然，还有很多这样的例子，单个机器人的能源和资源有限，机器人集群由许多机器人组成，它们协同工作并像团队一样相互协调，协作完成更复杂的任务，从而提高任务效率和任务质量，实现任务执行的灵活性。

机器人集群涵盖机器人平台、通信、集群自主决策、集群任务规划、集群路径规划、集群控制等多项核心技术。其中，机器人集群路径规划是实现机器人集群路径生成、避障、避碰等导航和协调任务的关键，内涵是“在线实时为集群内每一个机器人生成从其起始位置到目标位置的运动路径，并要求集群路径总代价最低或较低，能够实现集群内机器人相互避碰，且避免与环境碰撞”。具体到路径规划问题的建模和优化求解，描述机器人集群路径规划问题模型各异，有仿生学模型、人工势场模型、几何曲线模型、经典栅格模型等，但规划问题的目标是统一的，即集群内机器人从各自起始位置出发，同时到达各自目标位置、次序到达各自目标位置或时间窗间隔到达目标位置，规划问题的约束具体包括空间障碍约束、避碰约束、到达次序约束、到达时间窗约束等。相比于单个机器人路径规划问题，集群路径规划问题难点在于：第一，由于集群通常由大量机器人组成，底层位形空间具有高维度，路径规划变得具有挑战性；第二，路径规划的多项式空间(Polynomial SPACE,PSPACE)是完整的，寻求一个精确解的规划算法(如果存在，或者不存在则报告无解)仅限于在低维系统可行；第三，数学上规模通常很大且计算复杂，特别是在对特定最优性提出要求时，该问题变成计算复杂度很高的问题，对问题维度呈指数依赖，即使是离线都难以求解。寻求复杂环境中高效率和可扩展性的反应式协调规划算法成为机器人集群领域的热点问题。

目前，针对多机器人、多智能体、多无人平台都有相应的文献综述和学术归纳，但这些研究侧重于规划算法本身、机器人编队、协调控制等问题。文献[4]讨论多机器人路径规划方法的重要特征，机器人之间的协调对于路径规划非常重要，质量和精度需要众多机器人之间协作以实现其目标。随着机器人数量增加，释放少量优先权给机器人，使它们能够无碰地执行分配。文献[5]总结了多无人机协同路径规划方法研究。首先给出了问题描述和约束，然后总结了解框架和路径协调方法，接着介绍了几个常用于多无人机的协同路径规划方法，最后展望了未来可能的研究方向。文献[6]对空中机器人集群关键技术进行了系统性综述，将具有分布式分配的同步规划作为其中一项核心关键技术，但它侧重于介绍分布式任务分配问题，对于协同路径规划问题只是简单地提及。文献[7]从多无人车编队角度系统地研究了编队控制和编队路径规划方法，认为人工势场法、遗传算法和最优控制方法是多无人车编队路径规划的三种主流方法。不过，该综述未从可扩展性和求解框架角度对多无人车路径规划问题进行分析。

本文较全面深入地调研了机器人集群路径规划的技术发展现状。不同于绝大多数多智能体协同规划综述文献，本文创新性地归纳了适用于不同集群规模、可扩展性要求、通信需求以及算法要求的集群规划基础计算架构，即冗余计算架构、分布计算架构和分层计算架构，为该领域研究人员提供了切实可行的参考思路；从可扩展性和适用性角度，分类介绍了机器人集群路径规划方法，包括仿生学方法、人工势场法、几何学方法、经典搜索法和进化学习法；收集整理了可免费下载或开源的机器人集群仿真平台，以便于高校学生或研究人员快速构建集群仿真验证环境。

1 集群分布计算架构

机器人集群路径规划问题本质上是一个群体智能计算问题，计算架构对于集群效能的发挥至关重要。根据群体规模、通信条件和任务需求，设计合理的计算架构成为实现机器人集群系统的关键和重要前提。考虑集群可扩展性以及同路径规划算法的适应性，可以归纳为三种主要计算架构：冗余计算架构、分布计算架构和分层计算架构。

1.1 冗余计算架构

天线冗余计算架构是指将同一个路径规划算法复制至每个机器人规划器中，规划器启动前，每个机器人收集当前时刻集群内其他机器人的状态信息，将其输入至规划器(虚拟中心)，同步执行集群路径规划，再将规划器产生的集群路径中属于自己的路径计划取出来发送给执行器[8-9]，如图1所示。

图1 冗余计算架构Fig.1 Redundant computing architecture

该计算架构适用于无法或难以实现完全分布式计算的路径规划算法，比如几何学路径规划方法。它对通信即时可靠性和电磁环境要求很高，严重依赖于输入状态信息的一致性，一旦因为通信时延或者丢包导致信息不一致，就会造成规划结果的不一致甚至是路径冲突，该架构仅仅适合于小规模机器人集群在相对理想通信条件下使用。在工程实践中，一方面通过多次重传机制确保输入信息的一致；另一方面，尽可能限定运用于小规模集群路径规划问题。

1.2 分布计算架构

分布计算架构是指一种完全分布式计算的架构，机器人集群拥有一个全局优化目标，机器人规划器以此为自身的优化目标(也容许考虑私有目标，比如避碰等)，结合感知器感知的环境状态和通信获得的其他机器人当前状态，以同步或异步方式规划自身路径，再将规划得到的路径计划发送给执行器[10-11]，如图2所示。

图2 分布计算架构Fig.2 Distributed computing architecture

该计算架构适用于完全分布式计算的路径规划算法，如：仿生学路径规划方法、人工势场法、进化学习路径规划方法等。它对通信即时可靠性和电磁环境要求较低，对信息的不一致性不敏感，不过，对于通信带宽有一定要求，在集群规划器执行时刻甚至需要连续频繁大容量的信息交换，对即时带宽有较高的要求。该架构适合于中等规模机器人集群在相对复杂通信条件下使用，当规模达到一定程度时，也存在规划算法难以收敛的问题。

1.3 分层计算架构

分层计算架构是一种全局集中、局部分散的计算架构，由机器人集群中的一个中心节点或虚拟中心节点执行全局路径规划，将路径计划(中间目标点)分发给集群内所有机器人，机器人再以仿生方式跟踪这些中间点，在跟踪过程中考虑同环境的避障问题以及同其他机器人的避碰问题[11]，如图3所示。

图3 分层计算架构Fig.3 Layered computing architecture

该计算架构适用于可分层计算的路径规划算法，如人工势场路径规划法、经典搜索路径规划法，也适用于仿生学方法。它无论对通信即时可靠性还是对通信带宽的要求都很低，对信息的不一致不敏感，规划器工作过程中不需要大量的信息交互。该架构适合于大规模机器人集群在复杂通信条件下使用，当然集群密度不能够超出环境容限。

2 集群路径规划方法

从可扩展性和适用性角度，重点介绍仿生学方法、人工势场法、几何学方法、经典搜索法、进化学习五类可以用于集群路径规划问题的方法。其中，仿生学方法、人工势场法由于其分布或分层特点可以天然地应用于机器人集群路径规划；几何学方法、经典搜索法是机器人路径规划的经典方法类别，通过采用冗余计算架构，可以用于集群路径规划；进化学习法是近年来伴随着机器学习热潮产生的一类新方法。

2.1 仿生学方法

仿生群体智能算法是一类最适用于机器人集群路径规划的方法，一直是群体智能领域研究热点，它受自然界社会型生物行为启发，如蚁群、鱼群、鸽群、萤火虫、粒子群以及蝙蝠等，这些生物基于邻近个体间的直接交互，或者所有个体内的共识主动性来实现信息交换，通过个体间自组织协作实现复杂行为的智能涌现，具有分布式、自组织、可扩展等天然优势。大量研究人员通过模拟上述生物行为，设计了各种群体智能算法，如蚁群算法、鱼群算法、鸽群算法、萤火虫算法、粒子群等。

2.1.1 蚁群算法

蚁群优化(Ant Colony Optimization,ACO)算法[1]受蚂蚁觅食行为启发，它是启发式方法与蚂蚁环境交互行为相结合的产物，属于非线性优化的元启发式算法，其使用群体智能模型来模拟蚂蚁寻找食物最短路径行为。蚂蚁表现出复杂社会行为——共识主动性，该现象是在著名的双桥实验[10]中观察到的：当选择短路径和长路径食物源时，蚂蚁在一段时间后始终会找到最短路径。

尽管ACO易于获得近似最优解，但很难找到最优解，文献[11]提出一种蚁群路径规划算法，可获得更高质量的全局最优路径，且可在满意解和迭代次数之间进行灵活的权衡。文献[12]提出一种基于蚁群优化的动态环境下机器人集群路径规划算法。为了避免ACO易于陷入局部僵局和停滞问题，文献[13]将自组织协作机制引入集群路径规划中，通过局域信息交换，增强局部范围内机器人之间的通信协作，避免死锁。当某个机器人进入死锁区域时，同周围其他个体共享死锁区域位置，主动改变蚁群停留在死锁范围内的信息素，以便其他机器人绕过死锁范围，继续寻找最短路径。不过由于蚂蚁运动具有一定随机性，当种群规模较大时，很难在短时间内找到更优路径，这仍是大规模集群面临的难题。

2.1.2 鱼群算法

人工鱼群(Artificial Fish Swarm,AFS)算法[14]模仿鱼群交互行为，找到最高密度食物源。建模的鱼群具有四种基本行为：一是觅食，趋向于高食物浓度区域；二是聚集，游到高食物浓度区域而不会过分聚集在食物中心；三是追尾，追尾食物浓度高的个体，但不会聚集在其周围；四是随机，自由游动，不断扩大其搜索范围。该算法模拟真实鱼类的尾迹和活动，利用自下而上优化模型实现全局优化，具有全局性、快速收敛性、搜索空间自适应性、参数鲁棒性以及可追溯性等优点。不过，算法也存在缺陷，即早期收敛速度明显快于后期、参数选择会影响收敛速度和解的精确性、鱼群数量越多优化时间越长、过宽的优化范围和小的变化可能导致收敛速度变慢等问题。

同蚁群算法类似，AFS易于陷入局部最优，文献[15]提出一种混合改进人工鱼群算法，首先利用A*算法确定次优路径，然后基于惯性权重因子改进AFS的自适应行为，引入衰减函数来改善鱼的视觉范围和移动步长，用于平衡全局和局部路径规划，提高收敛速度和质量。该算法在避免局部最优、收敛速度和精度方面得到了改进，不过当鱼群规模过大时，算法需大量计算并占用更多存储空间；而当鱼群数量太少时，鱼群局部优化、早熟且易于落入局部极值。针对经典AFS最优解不精确和收敛效率低的问题，文献[16]提出一种自适应增强猎食行为和分段自适应鱼视距与步长的鱼群算法，称其为混合自适应人工鱼群算法。自适应增强猎食行为用于改进鱼的猎食过程，设计分段自适应策略用于改造鱼的视野和步长。

2.1.3 鸽群算法

鸽群优化(Pigeon-Inspired Optimization,PIO)算法[17]受自然界中鸽子归巢行为启发，模仿鸽子在寻找目标的不同阶段使用不同导航工具这一机制，包括两种不同算子模型：一种是地图和指南针算子，使用磁性物体感知地磁场，在头脑中形成地图，把太阳高度作为指南针来调整飞行方向，当接近目的地时，对太阳和磁性物体的依赖性减小。另一种是地标算子，模拟导航工具中地标对鸽子的影响，当飞近目的地时，将更多依赖附近地标。如果鸽子对地标熟悉，将直接飞向目的地。否则，将跟随那些对地标熟悉的鸽子飞行。鸽群优化算法相比于蚁群、粒子群等传统仿生智能算法，不容易陷入局部最优，具有收敛速度快、计算简单、鲁棒性强等优势，不过算法对于一些较为复杂的收敛速度问题，仍然存在速度较慢、收敛精度偏低、稳定性较差等问题。

2.1.4 萤火虫算法

萤火虫算法[18]是基于萤火虫闪烁行为的群体智能算法，它能够产生生物发光化学反应，通过不同强度的持续发光或闪烁来吸引其他萤火虫，亮度可随环境改变，吸引力则与亮度成正比。对于集群路径规划问题，萤火虫算法具有两大优势，即具有自动细分群体和处理多模态的能力。首先，吸引力随距离减小，这导致整个群体可以自动细分为子群，且每个群体可以围绕每种模态或局部最优进行群集；其次，如果种群大小大于模态的规模，这种细分允许萤火虫能够同时找到所有最佳集群[19]。

文献[20]提出一种基于路径选择的全局路径规划方法。首先利用群搜索优化(Group Search Optimizer,GSO)算法覆盖多个局部最优解的能力，一次生成多条路径；然后针对多条路径提出两种选择算法，在通过路径交叉点时，对交叉路径进行重新评估并选择较优路径，最终达到路径最优；最后通过启发式搜索快速选择到适当路径，它重用了原搜索结果，从而避免了二次规划。文献[21]提出一种基于萤火虫方法(Firefly-based Approach,FA)的机器人集群路径规划方法，将萤火虫社会行为用来优化群体行为。考虑到路径规划问题是一个NP-复杂度问题，多目标进化算法是求解该问题的一种有效方法，为此，文献[20]提出一种多目标萤火虫算法用于解决机器人路径规划问题的路径安全性、路径长度和路径光滑性等问题。

2.2 人工势场法

人工势场函数(Artificial Potential Functions,APFs)方法[22]将机器人工作空间定义为势场，势能是机器人导航过程中为避免碰撞障碍物而产生的力量，目标所在的低势能位置吸引机器人，障碍物所在的高势能位置则排斥机器人，这种通过施加障碍物虚拟斥力和目标的吸引力来计算势能仅需简单计算，它在机器人路径规划中极具吸引力，特别是在实时和动态环境应用中。APFs可基于分布式计算架构，独立运算于每个机器人之上，相当于多个机器人独立执行个体路径规划。由于无须统一建模与求解，特别适用于大规模集群路径规划问题。其优点在于：①APFs的计算速度很快，因为群体中每个机器人的合力仅取决于附近障碍物、目标以及与相邻机器人的有限交互；②具有可扩展性，当群体增加新机器人时通常只需计算障碍物的排斥力、目标的吸引力以及与邻近机器人的有限交互所产生的力。设计避免或最小化机器人陷入局部最小值概率的人工势场函数是一个具有挑战性的问题[23]。此外，充满复杂几何形状的多障碍环境中的机器人集群路径规划方法实际上目前仍不存在。

文献[24]运用APFs来获得流线型路径，将其用于复杂形状建筑的城市环境中无人机集群路径规划和协作目标跟踪问题。为提高集群路径规划效率，文献[25]将概率路标图与势场法相结合，提出一种组合路标图与势场集群(Combined Roadmaps and Potentials for Swarms,CRoPS)路径规划算法，使集群有效移动到期望目的地，同时避免相互碰撞以及同静态障碍物碰撞。CRoPS不使用概率路标图来规划群体整条路径，而是生成一系列中间目标，这些目标充当吸引势，以引导群体朝向期望的目的地运动；人工势场则为机器人提供局部反应式行为，这些行为旨在使群体保持内聚并远离障碍物。通过存在大量障碍物和狭窄通道的复杂环境仿真验证了CRoPS的有效性和可扩展性。文献[26]进一步对CRoPS算法进行扩展，提出一种可规避动态障碍物的组合路标图与势场集群(Combined Roadmaps and Potentials for Swarms for dynamic obstacles,dCRoPS)路径规划算法。首先，dCRoPS改进了CRoPS，使集群能够快速响应向其靠近的动态障碍物；其次，当机器人由于动态障碍物的干扰而无法到达计划的中间目标时，dCRoPS为群体中的机器人提供了目标的替代引导。文献[27]通过设计优先级选择机制并改进两种人工势场函数SWARM和SPREAD，实时实现集群分布式路径规划问题。通过在群组移动人工势场函数SWARM和不同优先级人工势场函数SPREAD中增加新的势场因子，使势函数可用于机器人集群路径避障协调阶段，同时解决人工势场法的局部最小问题。

2.3 几何学方法

除了从路径寻优角度研究机器人集群路径规划方法，也有不少研究侧重于使用B样条曲线、Bezier曲线、Dubins曲线，毕达哥拉斯曲线等二维平面或三维空间几何方法来生成或平滑路径。这类方法通常需要建立集群统一的数学几何路径曲线优化模型或集群内个体路径曲线之间的约束模型，集群规模容易造成模型或约束过于复杂，难于优化求解，仅适用于小规模集群路径规划问题。

2.3.1 杜宾斯曲线法

杜宾斯(Dubins)曲线是在满足曲率约束和规定始/末端切线方向的条件下，连接两个二维平面的最短路径。对于路径规划问题，主要考虑路径表示的简易性、路径曲率长度的计算复杂度以及改变路径长度的容易度3个问题。Dubins路径由圆弧及其切线连接而成，由于其表示及推导非常简单，已广泛应用于机器人路径规划问题。文献[28]研究了三维空间无人机集群协调路径规划方法，无人机安全飞行路径的同时到达问题。无人机同时到达由等长路径保证，考虑了无人机曲率的最大界限、无人机之间的最小间隔距离以及沿着飞行路径保证相等长度的路径非交叉等约束。通过测量路径之间的距离并通过找到路径交叉点来验证安全约束。

2.3.2 贝塞尔曲线法

贝塞尔(Bezier)曲线，依据四个位置任意的点坐标绘制出一条光滑曲线，常用于非完整机器人集群路径规划。大多数非完整机器人具有最小转弯半径约束，须在最小转弯半径约束和连续性约束下改进路径。文献[29]提出一种基于Bezier曲线的平滑方法，用于非完整机器人集群路径规划。算法包括全局路径规划、局部运动规划和优化规划三阶段：第一阶段，全局路径规划器在自由空间的Voronoi图分割中规划路径；第二阶段，运动规划器是基于Memetic算法的遗传算法；第三阶段，导航点被视为贝塞尔曲线控制点，可获得具有最小转弯半径约束的最优路径。由于提出算法还考虑了避碰问题，因此每个机器人始终沿规划路径与其他机器人保持最小安全距离。

2.3.3 毕达哥拉斯曲线法

毕达哥拉斯速端(Pythagorean hodograph)曲线[30]具有以下特点：①曲线上点均匀分布；②在计算路径长度时消除数值求积；③参数速度是其参数的多项式函数；④曲率和偏移曲线是有理形式。Shanmugavel等证明毕达哥拉斯曲线可用于自由空间以及有障碍区域的路径规划问题[31]。文献[32]重点研究无人机路径规划，使用毕达哥拉斯路径规划用于跟踪、检测和模拟污染云的形状。

2.4 经典搜索法

在经典搜索方法领域也存在不少可应用于机器人集群路径规划的有效研究。

2.4.1 概率路标图

概率路标图(Probabilistic Roadmap Maps,PRMs)算法[33]通过从机器人位形空间(简称C-空间)随机采样，保留满足特定可行性要求的点(例如，须对应可移动物体的无碰撞位形)，使用一些简单规划方法来连接这些点以形成路标图，在搜索路径过程中，采用标准图搜索技术从路标图中提取连接其起始位形至目标位形的路径。文献[26]提出一种可规避动态障碍物的组合路标图与势场集群路径规划算法，其集群路径是通过构建和搜索无碰撞路标图得到的，当群体由于动态障碍物干扰而偏离或无法达到计划的中间目标时，则再次搜索路标图以获得备选路径。虽然概率路标图算法可有效避免局部最小值问题，但在处理大规模机器人集群问题时其可扩展性仍然会出现问题。由于集群位形空间由每个机器人的各个位形空间的笛卡尔积组成，因此生成无冲突位形并通过无冲突路径连接相邻位形变得极具挑战性。目前，尽管存在大量的模拟群体行为的方法，但这些方法通常只能提供简单的导航和规划能力。为实现更复杂群体行为，文献[34]提出一种路标图路径规划与群体智能相结合的方法。它使用概率路标图的一种变体，即中轴概率路标图，不在C-空间随机均匀地生成节点，而在中轴或附近生成，非常适合于群体行为；另一方面，它将行为规则嵌入个体成员和路标图中，根据成员位置和状态来修改路标图边缘权重，实现了归巢、覆盖、搜索、穿越狭窄区域和放牧等群体行为。

2.4.2 经典路径寻优法

迪杰斯特拉(Dijkstra)算法是从一个顶点到其余各顶点的最短路径寻优算法，解决有向图中最短路径问题，作为最经典路径寻优算法被广泛应用于机器人路径规划问题。针对无人机集群协同路径规划问题，文献[33]提出一种自上而下的分层控制策略，群体首先使用Voronoi图和Dijkstra算法规划群体最优或次优路径，接着在底层设计自组织协调运动策略来引导无人机运动。著名的快速搜索随机树(Rapid-exploration Random Tree,RRT)是一种树形数据存储结构和算法，但RRT算法并不适用于机器人集群，文献[35]针对磁性微型机器人引导药物至瘤细胞问题提出了一种障碍加权快速搜索随机树，它将微型机器人引导至自由空间中轴区域附近以减小管壁对微型机器人集群的干扰，并采用分而治之策略通过离散区域转换执行群体聚合。

2.4.3 启发式搜索

高计算成本、陷入局部极小值是造成大多数经典搜索路径规划方法失败的原因之一。其中，启发式策略被认为是解决这些问题的方法之一，启发式基于短时间间隔内结果的可用性，这对于NP完全问题是有效的[12]。文献[36]提出一种三维环境下无人机集群路径规划方法，采用A*启发式算法为每架无人机规划趋向于目标的路径，采用三维空间欧几里得距离作为启发式代价，并考虑减少整个集群路径长度的最佳组合，以最小化总路径长度为优化目标，计算所有飞机到达所有目标的可行路径长度，再分布式协商实现目标最优组合。文献[37]研究了机器人集群动态路径规划问题，要求群体中至少有一个机器人访问区域内次要目标或检查点，同时须避开静态和动态障碍物，它采用D*lite算法用于动态路径规划，并设计分布式集群自组织规划策略用于遍历检查点，仿真验证了算法适用于不同规模机器人和不同障碍数量的路径规划问题。

2.5 进化学习法

可以看出，无论是经典搜索法、人工势场法，还是仿生学方法，大多都存在路径适应性差、计算复杂度高、搜索时间长、收敛精度低、容易陷入局部最优等问题。为克服这些缺点，研究人员一直尝试不同技术，其中机器学习方法最受关注。通常，机器学习方法可分为三类[38]：监督学习、进化方法和强化学习。在机器人集群路径规划技术领域，都有运用这三类方法开展研究的案例。

2.5.1 监督学习

机器人领域的监督学习将神经网络引入经典搜索方法中，使算法既具备探索世界的能力又具有存储经验的能力。通过学习，机器人能够将所呈现的问题与已知问题和适当的解决方案进行比较，并且如果关于解的知识存储在经验中则快速响应。文献[39]提出一种集成群体智能与神经网络的障碍环境路径规划算法，称为蚁群交配算法。它通过将ACO与自适应共振理论神经网络结合，展现出良好的优化特性，能够针对不同环境在不到100代的时间内得到解。不过，该方法仍然存在缺点：适应度函数的参数调节十分烦琐，而且ART-1的警戒参数对网络的粒度具有显著影响。

2.5.2 进化方法

在机器人领域，进化方法的应用大多基于遗传算法。遗传算法是一种并行随机搜索优化方法。文献[40]提出一种基于遗传算法的水下机器人集群路径规划方法，为每个机器人生成最短避碰路径。机器人行进路径的笛卡尔坐标是随机生成的，它们被编码到染色体中，其适应度由位移总和来定义。通过仿真验证该算法能够为机器人集群规划安全无碰撞路径，增加更多机器人，方法仍然能够获得最优路径。

2.5.3 强化学习

强化学习是一种目标导向的机器学习方法。与监督学习不同，强化学习所需的训练信息是评价而非指导，其主要目的是研究从状态到行动的最佳映射，以得到最大化回报。强化学习在移动机器人的路径规划、运动控制等方面具有普遍适用性。文献[41]研究如何将经典Q-学习方法应用于机器人集群路径规划问题，利用蚁群算法的信息素机制解决了强化学习系统中的信息共享问题，并对Q-学习方法存在的问题进行了一些改进，并在Player/Stage群体智能体仿真平台上进行了仿真验证。相比经典粒子群优化(Particle Swarm Optimization,PSO)算法，该方法在群体机器人路径规划中具有更高的效率。

2.5.4 其他方法

基于教学-学习的优化(Teaching-Learning-Based Optimization,TLBO)算法[42-43]模拟教学现象。该算法凭借其收敛速度快、精度高的优点，非常适合解决机器人路径规划问题，为全局路径规划提供了一种新解决方案。文献[44]提出了一种改进TLBO机器人全局路径规划方法，称为非线性惯性加权改进教学-学习优化(Nonlinear Inertia Weighted Teaching-Learning-Based Optimization,NIWTLBO)算法，它在TLBO中引入非线性惯性加权因子来控制学习者的记忆率，并使用动态惯性加权因子代替教师阶段和学习者阶段的原始随机数。NIWTLBO不仅具有更快的收敛速度，而且与TLBO相比，计算精度更高。仿真实验表明：该方法比TLBO和其他算法具有更快的收敛速度和更高的搜索路径精度。

3 机器人集群验证平台

20多年来，来自机器人集群的挑战吸引了众多领域的研究人员。许多新的仿真模型和工具被开发用于研究群体智能理论与方法。本节将以年代为主线介绍几款适用于大规模智能体集群问题研究的仿真引擎，这些引擎具有较好的可视化效果，便于更直观地研究机器人群体行为，可为高校和研究院所的学生和老师提供重要参考。

3.1 StarLogo

StarLogo[45]是MIT多媒体实验室于1994年开发的软件包，其仿真用户界面如图4所示。StarLogo提供了Logo编程语言Lisp的扩展和模拟多智能体系统的集成环境。不过尽管它易于使用且功能强大，但无法模拟复杂的三维世界以及物理实现。可用于建模分布式系统行为，可模拟许多现实群体现象,比如鸟群、蚂蚁和市场经济等。

3.2 Webots

Webots[46]是洛桑瑞士联邦理工学院开发的具备建模、编程和仿真的移动机器人开发平台，其集群仿真效果如图5所示。用户可以在一个共享环境中设计多种复杂的异构机器人，支持用户自定义环境，它使用开源动力学求解引擎(Open Dynamics Engine,ODE)检测物体碰撞和模拟刚性结构的动力学特性，可精确模拟物体速度、惯性和摩擦力等物理属性。每个机器人可以装配大量可供选择的仿真传感器和驱动器，机器人控制器可以通过内部集成化开发环境或者第三方开发环境进行编程，支持机器人行为在真实世界中测试，支持的操作系统包括Linux、Windows和MacOS。

3.3 Swarm

Swarm[47]是Minar等开发的模拟分布式系统的软件包，其集群仿真效果如图6所示。虽然Swarm提供了一个完备的系统来创建对象的层次结构和触发事件，但它并没有为三维模拟或可视化提供支持。Swarm通过访问Objective-C或Java库进行集合，而非独立的应用程序，涉及大量的编程工作。

3.4 Breve

Breve[48]是一个专为分布式系统和智能体模拟而设计的三维模拟环境，其仿真用户界面如图7所示。虽然Breve在概念上类似于Swarm和StarLogo等软件包，支持Linux、Windows、MacOS等操作系统。但是在模拟连续时间和连续三维空间方面，Breve的实现是完全不同的。Breve包括了面向对象解释的语言界面、OpenGL显示引擎、碰撞检测，以及关节体物理模拟和静态或动态摩擦等功能。其目标是允许快速轻松地实现分布式模拟以及先进的人工生命模拟。

(a) 可视化脚本(a) Visual script

3.5 Player/Stage

Player/Stage[49]是美国南加州大学机器人实验室开发的多机器人系统仿真环境。其中，Player是一个多线程的机器人驱动服务器，提供了方便的接口程序用于驱动机器人和传感器等设备，支持Linux、Solaris等操作系统；而Stage模拟这些设备，其虚拟得到的设备可以被Player控制，Stage在被设计时就考虑了多智能体系统的问题，可以提供对多机器人系统的测试仿真。Player/Stage软件界面效果如图8所示。

图8 Player/Stage软件界面效果Fig.8 Player/Stage software interface effect

3.6 SwarmFare

SwarmFare[50]是一个自组织沙箱系统，同时可以创建一个可合理模拟无人机运动学和通信的仿真环境，用于测试许多不同的多智能体场景和行为，其软件效果如图9所示。凭借强大的库和良好的界面，该系统在研究如何管理依据规则集运行的群体行为的过程中是一个功能强大的工具。

(a) 可视化脚本(a) Visual script

3.7 ARGoS/Buzz

ARGoS/Buzz[51]是欧盟资助的Swarmanoid项目中开发的官方通用模拟器，其集群仿真效果如图10所示。ARGoS/Buzz是第一款同时兼具高效(多机器人快速驱动)和灵活性(支持自由定制)的多机器人模拟器，可用于模拟大规模异构机器人集群的复杂实验，支持对10 000个机器人进行精确的实时二维动态仿真，并且可以对相同数量的机器人进行精确的实时三维动力学仿真。

(a) Breve仿真微型机器人(a) Breve simulation micro robot

4 结论

本文全面深入地调研了机器人集群路径规划的技术发展现状，创新性地归纳了适用于不同集群规模、可扩展性要求、通信需求以及算法要求的集群规划基础计算架构，包括冗余计算架构、分布计算架构和分层计算架构。从可扩展性和适用性角度，分类梳理了最适用于机器人集群的路径规划方法，包括仿生学方法、人工势场法、几何学方法、经典搜索法和进化学习法。并为集群仿真验证研究提供了七款可免费下载或开源的机器人集群仿真验证平台。

未来将以此为基础，更加全面地跟踪梳理领域相关研究，并将机器人集群路径规划技术综述拓展至机器人集群运动规划和机器人任务规划领域，为科学研究和教学工作提供更加科学的指导。