基于元胞自动机的无人机航路规划算法研究

刘震

【摘 要】本文利用元胞自动机算法模型，对无人机航路规划进行仿真。实现了单目标和多目标，以及二维环境和三维环境下的航路规划仿真。仿真结果表明，元胞自动机航路规划算法实时性高，计算量少，可在短时间内规划出一条安全可行的航路。

【关键词】元胞自动机;航路规划;无人机

中图分类号： V249 文献标识码： A 文章编号： 2095-2457（2019）15-0016-002

DOI：10.19694/j.cnki.issn2095-2457.2019.15.007

Research on Unmanned Aerial Vehicle Route Planning Based on Cellular Automata

LIU Zhen

（No.20 Research Institute of CETC，Xi'an Shaanxi 710068，China）

【Abstract】This paper simulates UAV route planning based on cellular automata.The simulation achieves the route planning of single target and multi-target in 2D and 3D environments.The simulation results demonstrate that route planning based on cellular automata has high real-time performance and less computation.The algorithm can plan a safe and feasible route in a short time.

【Key words】Cellular automata;Route planning;Unmanned aerial vehicle

0 引言

航路规划是根据无人机所处的环境和无人机自身的机动能力，在障碍环境中规划出一条从起始点到目标点的安全路径。航路规划广泛应用于有人和无人飞机突防、民用航空运输、无人车、无人艇[1-2]等领域。目前的航路规划算法有A*搜索算法、人工势场法等[3-4]。A*搜索算法利用启发信息来搜索，减少了搜索范围，降低了问题复杂度，但是存在随着搜索空间的增大会使计算时间变长、占用内存、只能用于离线状态等问题[5]。人工势场法是通过设定环境中目标与障碍的势场函数，根据目标的引力和障碍的斥力，在环境中规划出一条最优航迹。人工势场法的优点是计算速度快，实时性好，但存在目标不可达和局部极值问题[6]，目前解决人工势场法问题的方法有模糊控制器法、遗传算法和模拟退火算法等[7]，这些解决方法均是在目标陷入局部极值后选择跳出极值的策略，并没有解决局部产生极值的问题。

本文利用元胞自动机演化算法模型，实现元胞自动机航路规划算法，根据无人机周围障碍分布情况，选择出无障碍可行路径，元胞自动机航路规划算法实时性高，计算量少，可在短时间内规划出一条最短的可行航路。

1 元胞自动机算法

元胞自动机是由冯诺依曼提出，来源于生物学的细胞繁殖。元胞自动机模型中，元胞分布于规则的网格中，一个网格为一个元胞，每一个元胞取有限的离散状态，根据设定的规则，元胞通过规则与周围其他元胞相互作用，实现状态更新。元胞自动机由元胞、元胞空间、邻居和状态转换规则四要素构成，用式（1）表示。

式中，A为元胞自动机系统;L为元胞空间，d为元胞空间维数;Q为元胞状态的状态集用式（2）表示;N为当前元胞在内所有邻居元胞集合;f为元胞自动机状态转换规则。

式中，0表示睡眠，1表示工作。

基于元胞自動机的航路规划算法大都选用Moore型元胞自动机，其原理如图1所示。绿色方格为当前的元胞，邻居的8个元胞为当前元胞下一步运动可达元胞位置。每个元胞的网格大小代表运动体每一步运动的实际大小，根据运动体实际周围的障碍分布情况，将障碍所在区域设为障碍元胞，障碍元胞为不可达元胞。根据当前元胞周围的8个元胞中可到元胞与目标元胞的距离，选取距离最短的可达元胞作为运动体下一步的位置，直到当前元胞到达目标元胞为止。

根据无人机周围障碍分布情况，将无障碍范围区域内坐标对应的数值设为0，即可达元胞位置坐标的数值为0;将障碍范围区域内坐标对应的数值设为1，即障碍元胞位置的数值为1。

元胞自动机算法步骤：

第一步：根据出当前元胞周围8个元胞坐标中的数值，选择出可达元胞;

第二步：计算出每个可达元胞与目标元胞的位置;

第三步：将距离目标元胞最短的可达元胞设置为当前元胞下一步移动到的位置。

第四步：根据第三步结果，移动元胞位置。

2 航路规划算法仿真

本文使用matlab平台进行元胞自动机航路规划算法仿真。设置了二维环境情况下，单目标和多目标等不同情况的航路规划任务，以及三维环境下元胞自动机的航路规划算法仿真分析。

设置如图2所示的二维环境下障碍分布地形图，航路规划目标位置为1个。图中红色区域为障碍物，为了使规划出的航路更加安全，对建立的环境障碍模型进行膨胀放大，以保证无人机与障碍物有一定的安全距离，黄色区域为膨胀放大区。仿真算法中，在红色区域和黄色区域的元胞均为障碍元胞，其他区域均为可达元胞。

绿色航线为元胞自动机算法规划出的航路，可以看到算法规划出的航路能够避开障碍物到达目标位置，并与实际的红色障碍物保持一定的安全距离，保证了无人机的飞行安全。可以看出规划出的航线都是直线到达，迭代步数少，耗时短。

设置如图3所示的二维环境下障碍分布地形图，航路規划目标位置为4个。绿色航线为元胞自动机算法规划出的航路，可以看到在多目标位置的情况下，算法规划出的航路能够安全的避开障碍物，并且按照设定的目标位置顺序依次到达。

三维环境不同于二维环境，包含了高度方向，元胞从二维扩展到三维，当前元胞可达的元胞除了本层元胞外，还有上层元胞和下层元胞可达，因此当前元胞周围可达的元胞数量增加到了26个。设置如图4所示的三维环境下障碍分布地形图，航路规划目标位置为1个。同样对建立的三维环境障碍模型进行膨胀放大，绿色航线为元胞自动机算法规划出的航路，可以看到在三维环境情况下，算法规划出的航路能够改变高度，进而安全的避开障碍物，到达设定的目标位置。图4 三维单目标实时规划航路图

3 总结

利用元胞自动机算法进行无人机航路规划仿真，算法可实现单个和多个目标位置的航路规划，为无人机规划出一条安全可行的航线。并且在多目标位置情况下，可按照设定顺序依次到达。元胞自动机航路规划算法不仅可以实现二维障碍环境下的航路规划，扩展到三维障碍环境下也可实现航路规划。仿真结果表明，元胞自动机航路规划算法实时性高，计算量少，可在短时间内规划出一条安全可行的航路。

【参考文献】

[1]王壮.无人机航路规划方法研究[D].硕士学位论文，西安，西安电子科技大学，2017.

[2]赵云钦，蔡超，王厚军，等.基于带电粒子搜索的无人潜航器航路规划方法[J]，计算机应用，2018，38（7）：2107-2112.

[3]程越，周中良，江建成.基于改进稀疏A*编队航迹实时规划方法[J].火力与指挥控制，2018，43（6）：0947-0950.

[4]卢艳军，李月茹.基于改进人工势场法的四旋翼飞行器航迹规划[J].火力与指挥控制，2018，43（11）：1984-1986.

[5]王村松.多无人机编队在线协同航路规划方法研究[D]. 南昌：南昌航空大学，2016.

[6]熊俊强.基于人工势场的多无人机航迹规划一致性研究[D].南昌：南昌航空大学，2017.

[7]Zhang Yingkun.Flight path planning of agriculture UAV based on improved artificial potential field method[C].The 30th Chinese Control and Decision Conference，2018：1526-1530.