在自然界中，昆虫和动物种群经常会为了获取食物或适应环境组成不同的队形。比如说蚂蚁可以组成队形来一起搬运食物，或者用自己的身体组成一座桥来跨过缝隙。它们组成这些队形所依靠的是个体之间的互动和协调，而不是由一个核心的首领统一分配。这种依赖个体间自组织交互方式不但能很好地适应个体故障，也很容易扩展到由成千上万的个体组成的大规模集群。

来自西湖大学智能无人系统实验室、北航、清华、以及英国谢菲尔德大学的研究人员正是从这些自然现象中获取灵感，来设计让机器人集群更高效地组成队形的策略。研究成果以西湖大学赵世钰老师作为通讯作者发表于 Nature Communications。该工作第一作者为北京航空航天大学孙贵宾博士后（曾为西湖大学访问学生）。


问题与解决方案

在传统方法中，通常使用分配方法来解决机器人与队形间的匹配问题。具体来说，就是将队形离散化成与集群规模相适应的目标点集，然后为每个机器人分配一个唯一的目标点。一旦机器人分配得到自己在队形中所属目标点之后，就会规划一条无碰撞路径向该目标点移动。但这种基于分配的方法在遇到大规模集群控制时十分低效，因为分配运算的复杂程度随着机器人数量的增加而倍增。而且当个别机器人出故障时，还需要额外的算法来监测和修正。而如果使用去中心化的局部队形控制策略，那么机器人之间就可能争夺队形里的同一个目标位置，使得本来是合作关系的机器人之间产生了竞争关系，这种竞争也给队形控制造成了困难。

为了解决这些问题，作者们提出了一种基于均值漂移（mean-shift）探索思想的机器人集群队形控制策略：当集群中的机器人身边存在未被占据的空闲位置时,它就会主动放弃当前所在位置，并在队形中探索自己身边存在的大片未被其他机器人占据的区域。这是通过修改均值漂移算法实现的，并由 50 台机器人组成的集群进行实验验证。


集群队形探索策略的原理

这个策略由 3 个部分组成：图形化的人-集群交互界面、分布式机器人协商算法、分布式队形控制算法。

图形化的人-集群交互界面：作为第一步，操作员可以通过画图或者上传一张二进制图像的方法，在这个界面上告诉集群需要组成什么样的队形。图像会被转成一张黑白的网格图，其中黑色的网格表示机器人需要占据的位置，如下图。这个黑白网格随后被距离变换算法（distance transformation algorithm）转换成一张灰度网格图，以便让机器人更易于理解，并流畅地组成所需要的队形。在这个界面上，操作员只需要画出集群队形的大概形状，而不需要确定具体的物理参数。物理参数后续将由系统自动生成。网格的数量也不需要和机器人的数量一致，算法可以自动解决数量不匹配的问题。

针对指定队形的分布式协商算法：灰度网格一旦由人-集群界面生成，就会被发送给所有机器人，并保存在其内存中。这里用到的内存只在几十 kb 左右。关于队形的几何参数，比如每个机器人的位置和朝向都不是由人工制定的，而是由机器人之间相互协商，以分布式的形式决定。通过协商算法，所有机器人最终就指定的队形达成一致。

分布式控制算法：该算法是实现机器人集群组成复杂队形的核心。算法基于 mean-shift 探索思想，使得每个机器人能够主动地寻找周围未被占据的区域，并朝着该区域移动。具体来说，每个机器人会计算出周围未被占据的位置的密度，并将其作为一个概率分布。然后，它会使用 mean-shift 算法来寻找该分布的最大值，并将自己移动到该最大值所在的位置。这个过程会一直进行下去，直到所有机器人都移动到了期望的位置，从而组成所指定的队形。


机器人平台

实验平台使用的是 50 个可全向运动的机器人，机器人的外壳内部装有 LED 灯。LED 可以显示四种颜色：红色、绿色、蓝色和白色，分别对应于不同速度指令的大小。实验在室内进行，机器人需要运动捕捉系统进行实时定位。为了能够形成目标队形，每个机器人还需要获取邻近机器人的相关状态，以及感知周围环境障碍。这些都是通过一套并行多线程系统以分布式的方式实现的。


自组装形成复杂队形

该集群策略可以让机器人集群形成复杂队形，比如组成雪花形状。雪花形状由 6 个主分支和 18 个小分支够长，要形成这样的队形难度很大。这里的关键是让机器人在进入队形之后能够持续地探索，以寻找自己合适的位置，否则它们一旦进入队形之后就会陷入局部最优，停在图形的边缘，挡住了后面的机器人，导致后面的机器人无法进入队形。此外，还要让所有机器人都进入队形，而不是仅由部分机器人来组成队形。作者们提出的集群策略能够很好地解决这些问题，让机器人流畅自如地移动组成复杂队形。


集群规模自适应性

该策略对集群的规模具备很强地自适应性，会随着集群中机器人数量的变化而进行调整。当部分机器人离开集群时，剩下的机器人会自动填补它们空出的位置，继续保持队形。如下图所示，当海星队形的一角因为机器人的离队而缺失时，剩下的其它机器人很快就填补了空缺，重新组成了海星队形。尽管机器人数量比之前少了，但仍然可以保持整体队形不变。


协同运输和队形调控

自然界中的蚂蚁们可以通过合作，一起搬运比自己大得多的食物。机器人集群也同样能够做到协同运输，只要让它们组成一个中空的队形，如下图。当机器人组成中空的队形后，就会把货物围起来，接下来就只需要让它们在搬运过程中保持这个队形。实验人员让其中一些机器人作为领队，让它们知道在移动和转向的过程中队形应该是什么样。在机器人之间的协商过程中，领队会把握大方向，其它的机器人会逐渐与领队取得一致。


探索复杂环境

该集群队形策略也可以被应用到探索复杂环境的任务中，让集群机器人均匀地分布到一个复杂环境中，并且避开障碍物。在实验中，机器人集群从狭窄的过道涌入一个房间，而没有在入口被卡住。这个实验模拟的是人们进入电梯的场景，它很好地展示了集群策略中 mean-shift 算法的特性：先进入电梯的人必须往电梯内部移动，而不是停在入口附近，挡住身后的人。这个算法也可以用来探索迷宫之类的更复杂的环境。迷宫当中有许多转角等非凸结构，该算法通过探索，能够成功地让集群扩散到迷宫的各个角落，而不会陷入局部最优点。

实验证明，该策略可以成功组装高度非凸的形状，并具有强大的适应性。此外，该策略可以应用在一些更高难度的任务中，如协作运输和环境探索。

然而，作者们也指出该策略的局限在于它只能组成单连通形状，即可以在不抬起笔的情况下从任意一个点追踪到该形状中的任何其他点的形状。这是因为每个机器人的均值漂移探索都是基于对自己身边空位的感知。由于每个机器人的感知范围有限，如果两个不连通的形状组件相隔较远，就超出了感知范围。在实践中，这可以通过事先全局分配机器人到不同组件或添加连通不同组件的线段来解决。最后，虽然本文提出的算法是完全分布式的，但实验使用了中心化运动捕捉系统提供数据。未来的研究方向可以是开发内置传感的机器人硬件系统，实现大规模机器人集群的完全分布式队形排列。


作者简介

孙贵宾博士是北京航空航天大学博士后，分别于 2017 年和 2022 年在内蒙古大学和北京航空航天大学获得工学学士和博士学位，2022 年入选北京航空航天大学“卓越百人博士后计划”。主要从事集群自主协同控制与决策规划方面研究。

赵世钰博士是西湖大学工学院特聘研究员、智能无人系统实验室负责人。他的实验室研究关注于机器人系统中的控制、决策、感知等问题，致力于研究有趣、有用、有挑战性的下一代机器人系统。在追求高品质研究成果之外，他也致力于教授高影响力的课程。更多信息请参见实验室网站：https://shiyuzhao.westlake.edu.cn