浙江大学地球科学学院（探秘浙江大学无人机集群算法）

2022年5月5日，位于湖州安吉的一片竹林，一群微型智能空中机器人竟自如地穿梭其中，时而灵巧地掠过低矮灌木丛，时而交叉飞行变换队形……，浙江大学控制科学与工程学院高飞博士团队联合浙大湖州研究院许超教授团队在《科学·机器人》期刊发表最新研究成果：经两年多研究，科研团队解决了未知复杂环境下机器人单机与群体的智能导航与快速避障方法等一系列核心技术，研发出小巧轻便、自主可控又能成群结队的飞行系统。

大规模的机器人空中编队表演已不新奇，通过前期的卫星定位和轨迹编码，机器人能够摆出多种造型。然而一旦失去地面计算机的控制，这些机器人就会群龙无首甚至撞到障碍物跌落下来。在未知复杂环境中的成群结队飞行，一直被看作是机器人与人工智能领域的一大技术瓶颈。那么浙江大学高飞团队此次实现的无人机集群控制导航和快速避障是如何实现的呢？笔者猜想大概率还是基于“蚁群算法”的优化和改良，使得无人机集群实现了基于群智能的三维路径规划及自主避障。

蚁群算法简介

蚁群算法是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。蚁群算法最早是由意大利学者Colorni A., Dorigo M. 等于1991年提出。经过20多年的发展，蚁群算法在理论以及应用研究上已经得到巨大的进步。蚁群算法是一种仿生学算法，是由自然界中蚂蚁觅食的行为而启发的。在自然界中，蚂蚁觅食过程中，蚁群总能够寻找到一条从蚁巢获取食物源的最优路径。下图显示了这样一个觅食的过程。

在图（a）中，有一群蚂蚁，假如A是蚁巢，E是食物源（反之亦然）。这群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶。假如在A和E之间突然出现了一个障碍物（图（b）），那么，在B点（或D点）的蚂蚁将要做出决策，到底是向左行驶还是向右行驶？由于一开始路上没有前面蚂蚁留下的 信息素（pheromone） ，蚂蚁朝着两个方向行进的概率是相等的。但是当有蚂蚁走过时，它将会在它行进的路上释放出信息素，并且这种信息素会以一定的速率散发掉。信息素是蚂蚁之间交流的工具之一。它后面的蚂蚁通过路上信息素的浓度，做出决策，往左还是往右。很明显，沿着短边的的路径上信息素将会越来越浓（图（c）），从而吸引了越来越多的蚂蚁沿着这条路径行驶。

通常来说，蚂蚁会以较大的概率优先选择信息素浓度较高的路径，并释放一定量的信息素以增强该条路径上的信息素浓度，这样就会形成一个正反馈，最终使得蚂蚁能够找到一条从A到E点的最佳路径，即距离最短。用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间，整个蚂蚁在正反馈下得到的最佳路径，便是待优化问题的最优解。

算法原理

蚁群算法的信息交互主要是通过信息素来完成的。蚂蚁在运动过程中，能够感知这种物质的存在和强度。初始阶段，环境中没有信息素的遗留，蚂蚁寻找事物完全是随机选择路径，随后寻找该事物源的过程中就会受到先前蚂蚁所残留的信息素的影响，其表现为蚂蚁在选择路径时趋向于选择信息素浓度高的路径。蚁群算法的基本原理:

1、蚂蚁在路径上释放信息素。

2、碰到还没走过的路口，就随机挑选一条路走。同时，释放与路径长度有关的信息素。

3、信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时，就选择信息素浓度较高的路径。

4、最优路径上的信息素浓度越来越大。

5、最终蚁群找到最优寻食路径。

算法实现

假如蚁群中所有蚂蚁的数量为m，所有位置之间的信息素用矩阵pheromone表示，最短路径为bestLength，最佳路径为bestTour。每只蚂蚁都有自己的内存，内存中用一个禁忌表（Tabu）来存储该蚂蚁已经访问过的地点，表示其在以后的搜索中将不能访问这些地点；还有用另外一个允许访问的位置表（Allowed）来存储它还可以访问的地点；另外还用一个矩阵（Delta）来存储它在一个循环（或者迭代）中给所经过的路径释放的信息素；还有另外一些数据，例如一些控制参数(α，β，ρ，Q)，该蚂蚁行走玩全程的总成本或距离（tourLength），等等。假定算法总共运行MAX_GEN次，运行时间为t。蚁群算法计算过程如下：

（1）初始化。

（2）为每只蚂蚁选择下一个节点。

（3）更新信息素矩阵。

（4）检查终止条件。如果达到最大代数MAX_GEN，算法终止，转到第（5）步；否则，重新初始化所有的蚂蚁的Delt矩阵所有元素初始化为0，Tabu表清空，Allowed表中加入所有的城市节点。随机选择它们的起始位置（也可以人工指定）。在Tabu中加入起始节点，Allowed中去掉该起始节点，重复执行（2），（3），(4)步。

（5）输出最优值。

算法在拓扑二维地图与三维空间路径规划的应用

常规的二维拓扑地图由若干个节点按照某种连接关系组合而成，强调不同节点间的连通性，节点之间的联通代价通常用权值代表，蚁群算法在利用信息素选择路径时，可以考虑在某个节点，按照该节点与其他节点的联通关系不同的权重比重（视为信息素比例）选择路径。

而三维空间不具有拓扑二维地图那样的连通性约束，而是不同经纬度对应的海拔高度最为约束，其余空间皆为自由解空间，因此考虑将三维空间切片分层，每一层的平面划分为若干个栅格，那么利用蚁群算法进行三维路径规划的本质即：在不同的切片平面确定不同的栅格，将这些栅格利用样条函数绘制成光滑的曲线。

1.将三维空间按照高度进行切片，切片数量可以根据算法的精度要求和时间成本等综合考虑；

2.针对每一个切片进行栅格化处理；如10*10个栅格；

3.某些栅格位于限制高度一下，若选择了该栅格会导致规划的路径与障碍物相交，因此需要筛选可行栅格；

4.在MATLAB定义切片信息结构体，该结构体应当包含每一个切片的可行栅格，本层切片与下一层切片的连接信息：包括信息素、启发因子等等；

5.本层切片的栅格与下一侧切片的栅格的选择操作即为蚂蚁在不同路口根据信息素浓度按照轮盘赌法选择路径的操作。

社会价值

把物理世界的运动信息表征成一系列的数学问题，关键是要识破复杂问题背后隐秘的特殊数学结构，化繁为简，浙大研发的这款新型机器人在仅使用机载视觉、机载计算资源的情况下，实现了在野外树林复杂环境下感知周围障碍物、定位自身位置及生成飞行路径、以及多智能体通讯等多项关键技术突破。未来在火灾等搜救场景中，类似的微型集群机器人能够更好实现搜救目标，减少搜救人员风险；在地形勘探中，也可以快速对人员无法到达的区域进行建模。