基于仿人发育的混合空域智能无人机防碰撞策略研究

雷鹏飞，魏贤智，张启瑞，齐 铎，张志浩

(1.空军工程大学 空管领航学院，西安 710051；2.空军工程大学 航空工程学院，西安 710051；3.中国人民解放军 93525部队，西藏 日喀则 857060)

0 引言

随着国家低空开放政策的实施以及无人机技术的飞速发展[1]，越来越多的中小型无人机将会穿梭在城市上空，进行搜索救援、航空拍摄、气象观测以及货物运送等活动。为了保证飞行安全，各国将无人机限制在特定空域内进行飞行，使无人机与有人机进行隔离飞行。但随着航空技术与航空事业的发展，在有限的空域资源内往往存在有人机、无人机以及静态障碍共存的混合空域。在混合空域中，一方面，需要无人机能在城市密集障碍环境中对静态的楼宇障碍进行有效地自主防碰撞，保证其飞行安全；另一方面，在混合空域中由于动态障碍密集的加大，需要无人机能够对动态障碍进行快速反应，具备在密集动态障碍中快速防碰撞的能力[2]。

目前针对无人机自主防碰撞已经有了许多研究。传统的无人机自主防碰撞路径规划算法主要包括：可视图法、Dijkstra算法、A*算法、RRT算法等。可视图法由Lozano-Perez和Wesley于1979年提出[3]，其将障碍物视为多边形，机器人视为一个点，将起点、障碍物各顶点、终点的所有连线进行组合连接，构建可视图的关键在于障碍物各顶点之间可见性的判断，要求所连接线段不能穿过多边形内部，而后通过线段所赋权值的大小选取最优路径。Dijkstra算法[4]是一种经典的广度优先的状态空间搜索算法，其通过计算起点到环境模型中任意一点的最短距离从而得到全局最优路径。A*算法在广度优先的基础上增加了一个代价函数 ，既考虑了当前节点与起点的距离代价，同时也考虑了当前节点与终点的距离代价，通过调节的大小来调整算法的精度与速度。RRT算法[4]是一种简单有效的随机算法，通过从根节点随机向外扩散，生成随机扩展树，当叶子节点包含目标点时，即可获得一条路径。RRT算法虽然具有搜索效率快，能够用于高维空间的优点，但是其随机扩展的方式，使得结果可能并不是最优的，并且RRT算法并不适用于狭长的搜索环境。

由于约束条件的增加以及环境模型复杂度的上升，传统的路径规划算法在进行路径规划时，存在适应性差、难以求解的问题。为更好地解决路径规划问题，智能优化算法应运而生[5]。

智能优化算法主要包括遗传算法、蚁群算法、粒子群算法以及飞蛾扑火算法等。遗传算法(GA)是借鉴达尔文进化论、孟德尔遗传机制提出的一种启发式搜索算法。其本质上是一种并行、全局搜索算法。文献[6]提出了一种双循环遗传算法(DCGA，double-cycling genetic algorithm)，在实验考虑环境模型及运动约束的情况下，提出了新颖的综合适应度函数，利用两次遗传算法寻找最优路径，在第一次规划中使用部分适应度函数，第二次规划中使用整体适应度函数；通过双循环机制，实现了静态规划和动态避障相结合。与传统遗传算法相比，DCGA算法路径规划的结果更加符合实际。

文献[7]提出了一种改进的自适应蚁群算法(IAACO)，通过引入角度引导因子和障碍物排除因子，对ACO算法的实时性和安全性进行改进，同时改进了蚁群算法的信息素更新规则，并将路径规划问题转化为多目标规划问题，最后在二维栅格环境当中进行仿真实验，通过与ACO算法和IACO算法的对比分析，验证了IAACO算法在保证解的质量的同时，具有更快的收敛速度和更强的全局寻优能力。

文献[8]运用BSO算法，其通过将粒子群算法(PSO)与天牛须算法(BAS)相结合，运用天牛觅食的方式代替粒子寻优过程，并运用到三维路径规划当中，通过实验证明BSO算法加快了迭代收敛速度，降低了算法陷入局部最优解的概率。

文献[9]提出用Lévy飞行轨迹改进的飞蛾扑火优化算法，提高了路径规划的收敛速度和寻优精度；文献[10]通过引入自适应惯性权重对火焰更新机制进行改进，通过对步长进行自适应调整，对火焰位置产生扰动，充分利用了最优火焰的位置，同时自适应的方式很好地平衡了算法的全局搜索能力和局部搜索能力；其次引入遗传算法交叉算子和高斯变异算子，将每次迭代产生的最优火焰与其余火焰进行交叉重组，使得算法在前期搜索过程中能够跳出局部最优，加快算法的搜索效率。

文献[11]通过Tent混沌映射对飞蛾种群的初始化过程进行优化，增加了解的均匀性和多样性，增强了算法的全局搜索能力；而后借鉴模拟退火算法中的Metropolis准则和遗传算法的算术杂交操作，使得算法既能够以一定概率接受当前的劣解，同时也能够以一定概率产生扰动，起到了既能够产生扰动，同时又能控制扰动误差的作用。

本文通过分析人在密集障碍环境中的思想活动，参照人的发育式学习防碰撞机理，通过仿人的思维机制建立了面向混合空域中密集障碍的无人机实体模型和发育模型，最终构建了基于仿人发育的无人机防碰撞方法。能够有效解决无人机在进入混合空域时自主防碰撞飞行，以及帮助无人机自主逃脱规划路径中的“死区”，最终到达安全区域。并能在密集障碍环境中，随着环境熟悉度的提升而不断发育自身防碰撞行为，减少路径规划所需时间[12-13]。

1 人的发育式学习防碰撞机理分析

当人在陷入密集障碍中时，面对众多的障碍，其会在密集障碍中进行思考，从而选择最安全的路径进行防碰撞。并在随着对这种碰撞环境的熟悉程度提升，人会自身发育，从而“不假思索”地对环境产生反应，思考出安全路径的时间越来越短。图1为人在密集障碍中进行发育式学习防碰撞的示意图，黑色为障碍物，白色为身处障碍环境中的人，黑色曲线为人通过思考，对障碍环境所规划的安全路径。

图1 人的发育式学习防碰撞示意图

在初始遇见这种环境时，人往往需要大量的时间对障碍进行感知、预判，并通过大脑计算规划出安全的路径，但在密集动态障碍环境中，动态障碍在思考的时间内会产生位移，影响人的安全，因此需要一种针对密集动态障碍的快速防碰撞方法。人在密集障碍环境中会有一种条件反射式的防碰撞行为，这是因为随着人的成长，经历过许多的密集障碍环境，导致自身会对熟悉的环境进行反应，并且随着环境熟悉度的提升，对越熟悉的环境，往往需要思考的时间更为短暂[14-16]。

2 面向混合空域中密集障碍的实体模型

2.1 混合空域环境模型

在混合空域中由于静态建筑与建筑之间的空隙通常比较狭窄，并且动态障碍密集难以预测，这就为无人机的防碰撞带来极大困难。如图2所示，本文构建了一个典型的混合空域环境模型示意图，无人机的探测范围如图中黑色圆形所示，图中阴影部分为混合空域中动态障碍密集区，灰色为静态建筑障碍，黑色为动态障碍。无人机需要根据自身携带的传感器在混合空域中保证自身安全并能到达规定的目标点[17-18]。

图2 混合空域环境模型

2.2 无人机模型

在无人机路径规划的过程中，无人机的飞行轨迹不仅受到环境因素的影响，同时也受到因其设计、制造过程中已经决定的自身性能的限制。本文针对的是在城市中使用的中小型旋翼无人机，其具有灵活的机动性，可以在飞行时忽略最小转弯半径与过载等因素，因此，我们可以把无人机作为一个可操纵的质点[9]，建立旋翼无人机的质点运动方程：

图3 无人机栅格化模型

3 仿人思想无人机发育准则模型

针对传统算法难以满足混合空域密集障碍这种特殊环境的防碰撞要求，本文综合运用快速随机生成树模型以及广度优先搜索，在避障过程中仿照人的思想活动构造出适用于无人机自主防碰撞的发育准则模型[19-20]。

快速随机生成树即快速遍历随机树(RRT，rapidly-exploring random tree)，是一种在已知环境中通过采样扩展的方式进行搜索的算法。就其名称来看，Rapid-exploration指的是算法的效果，即实现快速的搜索；Random指的是搜索的方式，通过在环境中随机采样的方式探索整个环境；Tree指的是已搜索的位置通过树状结构来存储，每个位置都有自己的父节点和子节点，搜索完成的路径通常是从树的根节点到一个叶节点的路径。该算法主要特点：一是搜索速度快，二是该算法是概率完备的，即如果规划时间足够长，且确实存在一条可行路径，RRT总是可以找出这条路径的。基于以上两点，该方法经常被应用于无人机的路径规划问题。但同时该算法也有比较明显的缺点，比如通常不最优、规划的路径不平滑等。

广度优先搜索(BFS，breadth first search，宽度优先搜索)，是最简便的图的搜索算法之一。BFS算法的核心思路就是：从某个点一直把其邻接点走完，然后任选一个邻接点把与之邻接的未被遍历的点走完，如此反复走完所有结点。类似于树的层序遍历。广度优先搜索算法关注的重点在于对每一层结点进行下一层的访问。

本文将通过综合以上两种算法模拟人的思想活动及发育特性来实现无人机防碰撞路径规划。

3.1 探索准则

假设无人机机载传感器能够感知周围障碍信息的距离为Rsensor，按照无人机的飞行区间将感知范围进行数字栅格化，对可飞域定义为0，障碍区域定义为1，如图4所示。

图4 无人机感知范围栅格化标注

利用广度优先算法，寻找一个飞行步长内所到达位置并进行记录，再从这些位置开始，寻找下一个飞行步长所能到达的所有位置(即两个飞行步长的所有位置)，以此类推直到记录完感知范围内所有飞行区间，如图5所示。

图5 广度优先算法感知障碍示意图

对于无人机来说，这种广度优先的思想虽然可以遍历感知范围，但数据量也会呈指数型增长规划时间也会不断加大，影响算法的有效性。因此我们引入随机生成树模型[13]简化探索过程，可以极大减少探索时间。利用随机生成树模型进行障碍感知的原理如图6所示，对于可飞域算法将多个栅格合并进行划分，而对障碍区域则不断进行四等分，并进行数据记录。由于随机生成树具有分层数据结构的特点，而我们只需对障碍区域进行探索，提高了搜索效率[21-22]。

图6 随机生成树简化障碍搜索模型示意图

3.2 最优路径准则

根据向广性准则选取到飞行节点后，无人机有多条路径进行飞行到达所选取的航点，设每条路径的代价函数为路径所遍历的栅格数，栅格数越多代表路径越长，长的飞行路径不符合无人机飞行经济性要求。可计算每条路径的飞行代价函数并取得最优飞行路径即代价函数最小、经历的栅格数最小的规划路径：

gpath=min(g1，g2，…，gn)

(2)

3.3 死区脱逃准则

由于无人机不能获取全局障碍信息而只能根据自身机载传感器感知外界信息，因此在陷入某些死区时很难找到出路。而人在陷入死胡同时，会进行路径的“试错”，即随机挑选一条路径行走并进行记录，当此路不通，则返回路口继续寻找另外路径直到找到正确的出口为止。本文仿照这种思想进行编程，在无人机发现进入死区后，则返回上一飞行航路点，并选择其它点作为下一飞行节点，如下所示：

算法: 死区脱逃准则

重复

If 进入死区

Then 回到上一节点opt(dot)

重新挑选路径节点

直到 逃离死区

3.4 邻居集准则

在无人机从死区逃出，并选择另外通路，此时虽然不会选择上一航路点进行飞行，但选择与上一航路点非常接近的航路点有时也可能会进入同一死区。如图7所示，无人机在通过航点1进入死区并逃出后，此时还有航点2，3进行飞行，但选择航点2则会进入同一死区，造成重复探索甚至威胁无人机安全。

图7 不同航点进入相同死区示意图

为了避免这种重复性的探索，我们定义邻居集的概念，在无人机进入死区需要重新寻找路径点时，避开当前位置点周围一定范围的点，这一定的范围即我们定义的邻居集，从而可以使无人机在同一死区仅探索一次，提高搜索效率。假设在t时刻，无人机从死区逃脱并已知其最后从死区脱逃点 ，则可定义与毗邻点为其邻居集，如式(3)所示：

(3)

寻找与D毗邻点的邻居，可找出下一次需要避免进入同一死区的所有邻居集，则在进行航路点选取时，只需避免这些死区邻居集D(X，Y) ，即可避免进入同一死区。如图7中黑色点集，航路点1，2属于同一邻居集，而航路点3属于另外邻居集。

3.5 发育准则

无人机所感知到的所有信息被传送到大脑思考模块，进行经验知识和当前环境的对比判断，将获取到的知识在当前环境下，根据感知到的经验知识，进行推演、判断，从而完成自身的发育行为。假设无人机的大脑为B(t)，则B(t)的时变状态更新函数ft与以下参数有关：感知信号集合S(t)、动作控制集合C(t)、无人机自身参数E以及当前时刻的“大脑”B(t)，则可构建无人机的发育准则为在当前变量基础上的不断更新记忆的过程：

B(t+1)=ft(S(t)，C(t)，E，B(t))

(4)

4 混合空域中无人机发育防碰撞方法的实现

通过本文对比人的发育式学习防碰撞思想，结合广度优先算法与快速生成随机树算法构建出相应的算法准则并考虑邻居集概念以及死区脱离机制，继而设计混合空域中无人机发育防碰撞算法体系如图8所示。

图8 混合空域中无人机发育防碰撞算法体系图

如图8所示，在进行无人机避撞航路规划时，首先按照广度优先与随机生成树相结合的方式对栅格化的地图进行搜索寻找代价函数最低的规划路径，并判断当前是否进入死区，如果进入死区则返回上一个路径点并在下一步的搜索中避免选择进入同一死区的所有邻居集路径点，如果没有进入死区则继续进行路径的规划直到到达目标点。

5 仿真与分析

为了验证本文所提出的面向混合空域的无人机发育防碰撞算法在复杂环境中的有效性，本节从两个方面对算法性能进行仿真和分析：一是与传统的A-Star算法进行避障比较以及与基于图论思想的Voronoi算法进行对比分析，二是通过算法在同一环境中的不断重复并记录算法规划航路的时间变化，测试其发育防碰撞性能。

5.1 仿真对比分析

假设无人机飞行速度2 m/s，初始位置在混合空域中。图9是传统A-Star算法与本文发育算法仿真结果对比图。由图中可以看出，传统A-Star算法在陷入死区时并不能自主改出，无法为无人机提供安全的防碰撞航路。而本文所的发育算法能在进入死区后根据所构建的规则合理地规避障碍，并逃离死区。

图9 A-Star算法与发育算法自主防碰撞对比示意图

图10是基于Voronoi算法与本文发育算法的防碰撞效果仿真对比图。从图中可以看出，基于Voronoi算法很容易从障碍中穿行而过，而这种航线会严重威胁到无人机的安全。而在本文所构建的发育防碰撞思想，可以避开密集障碍，且在有限的可飞域中选择安全的航路。

通过与A-Star算法和基于图论思想的Voronoi算法进行比较我们发现，本文提出的发育算法在进行无人机避障路径规划中可以给出合理的避障路径并且避免了无人机为了避障而陷入“死胡同”无法到达目标点的情况。相比于两种传统方法而言，具有明显优势。

5.2 发育防碰撞算法测试

设定无人机的仿真环境为统一仿真环境，为保证发育防碰撞算法测试的有效性，预先规划好动态障碍的行进路线。在同一环境中对算法不断进行测试，可以得到在环境中无人机防碰撞并且脱离混合空域的时间如图11所示。可以看出，随着环境熟悉度的提升，无人机脱离混合空域密集障碍的时间越来越短，如同人一样在对环境进行记忆不断提高熟悉程度，达到发育的目的。当发育到一定程度，无人机无法再进行时间上的提升，这是由于已经到达了最优化，因此在自身性能之内，对环境已经十分熟悉，发育完全，不能再进行时间上的缩短。

图11 发育防碰撞算法测试图

综合上述仿真结果可知，根据仿人发育防碰撞思想构建无人机飞行准则进行发育防碰撞路径规划的方法，使得无人机可以在混合空域密集障碍中进行高效合理的安全飞行，并且在进入死区后能够自主寻找逃出死区的合理航路。并且随着环境熟悉度的提升，无人机自主规划脱离混合空域密集障碍的时间越来越短，如同人一样在对环境进行记忆，不断提高熟悉程度，达到发育的目的一样。与其他算法相比，本文算法由于具有发育的特性，因此有更好的防碰撞性能，更加适合于混合空域密集障碍环境中无人机的安全飞行。

6 结束语

随着航空技术与航空事业的不断繁荣，尤其是无人机领域的蓬勃发展，在有限的空域资源内有人机、无人机以及静态障碍共存的混合空域已成必然趋势，而对于混合空域密集障碍中无人机的安全飞行是非常重要的问题，现有的无人机避障路径规划方法普遍还有一定的局限性。本文通过考虑人的发育式学习防碰撞机理，基于仿人的思维机制建立相关的要素模型以及算法准则，结合广度有限、快速生成随机树等经典算法以及死区逃脱、邻居集等概念，给出了混合空域密集障碍中的无人机仿人发育自主防碰撞算法。仿真实验和分析证明，本文方法对于密集的静态、动态障碍的防碰撞是有效的，同时和传统的路径规划算法相比更加安全可靠。并且随着对环境的熟悉，无人机通过自身发育，需要进行防碰撞算法计算的时间越来越短，如同人对陌生环境逐渐熟悉之后，路越走越通。后续对于如何将算法应用于实践，并且将算法拓展为三维防碰撞，是我们今后需要深入研究的方向。