四旋翼无人飞行器的航迹规划*

李 翊 王 朕 姜 鹏 杨智勇 康宇航

(1.海军装备部驻西安地区军事代表局 西安 710054) (2.海军航空工程学院 烟台 264001)(3.海军航空兵学院舰载机系 葫芦岛 125001)

四旋翼无人飞行器的航迹规划*

李 翊1王 朕2姜 鹏3杨智勇2康宇航2

(1.海军装备部驻西安地区军事代表局 西安 710054) (2.海军航空工程学院 烟台 264001)(3.海军航空兵学院舰载机系 葫芦岛 125001)

针对已知的局部地图,对现有的各种遗传算法进行了修改,提出一种改进型的遗传算法对四旋翼无人飞行器进行航迹规划。传统的遗传算法收敛慢,且容易陷入局部最优解或者“早熟”现象。针对这些同题,论文对交叉概率与变异概率进行自适应调整,自适应函数也进行了动态标定。实验结果表明该算法的可行性及可靠性。

四旋翼无人飞行器; 自适应函数; 交叉概率; 变异概率; 航迹规划

Class Number TP242.6

1 引言

无人飞行器航迹规划是在综合考虑无人飞行器到达时间、燃料消耗、威胁以及飞行区域等因素的前提下,寻找从初始点到目标点,并且满足某些特定指标最优的飞行航迹。航迹规划方法主要有：栅格法、SAS搜索算法、动态几何规划算法、蚁群算法、鱼群算法、人工势场法和遗传算法。其中遗传算法全局寻优能力最强,本文选用遗传算法来对四旋翼无人飞行器进行航迹规划[1～5]。

2 遗传算法

遗传算法是借鉴生物界的进化规律(适者生存,优胜劣汰)演化而来的搜索算法。由美国密西根大学Holland教授的学生Bagley在1967年首次提出的。遗传算法是一种随机全局搜索算法。

图1 遗传算法的进化

图1表示遗传算法循环流程。在遗传算法中,首先产生初始种群。通过适应度函数决定种群中个体的好坏,根据适应度函数计算出种群中每一个个体的适应值。适应值高的个体更可能被留下来,而适应值低的个体则很可能被淘汰。选择中应尽可能地保证优秀的个体被选中。根据实际情况确定选择机制,如轮盘赌选择机制、均匀排序机制、随机联赛机制等[6]。

3 遗传算法在航迹规划中的应用

本文的研究背景是第六届国际空中大赛,四旋翼无人飞行器已经从起飞点飞到一个包含若干小房间的大房间中(如图2所示),建立起了局部的环境特征地图,需要通过航迹规划找出一条从航迹规划起始点返回到起飞点的路径。如果四旋翼无人飞行器在小房间中,则需要先飞出房间然后再进行航迹规划;如果没有,仅仅是在大房间的走廊中,则直接进行航迹规划。本文采用一种改进型的遗传算法对无人飞行器进行航迹规划,该算法将动态标定遗传算法、自适应遗传算法和大变异遗传算法结合在一起,设计思想如图2。

图2 国际空中机器人大赛比赛场地示意图

3.1 四旋翼无人飞行器的编码

遗传算法的第一步就是确定染色体的编码方式,它决定了四旋翼无人飞行器在航迹规划的表现形式,航迹的编码方式主要包括利用导航点位置来编码、利用飞行距离编码、利用飞行距离和航向角的编码等,优秀的编码方式能够提高算法效率;反之也能降低算法效率。由于四旋翼无人飞行器创建的是特征地图,且四旋翼无人飞行器每隔50ms给一次指令,结合这一特点可以对四旋翼无人飞行器采用导航点位置方位的编码方式：将四旋翼无人飞行器从航迹规划起始点到四旋翼无人飞行器的起飞点的所有航路作为种群的个体[11],其染色体结构如图3所示。

图3 染色体结构

xhi和yhi分别为四旋翼无人飞行器第i个航路点的横坐标和纵坐标;φhi为四旋翼无人飞行器在第i个航路点的航向角;bhi为四旋翼无人飞行器的航迹点中的状态变量,如果第i个航迹点可行,即满足约束条件(如在地图的可行范围内),并且第i个航迹点到第i+1个航迹点的航迹是可行的,则bhi=1,否则bhi=0。

3.2 四旋翼无人飞行器的适应度函数

适应度函数的选取直接影响到算法的最优解及效率[12]。适应度函数越复杂,则遗传算法就越复杂,这样遗传算法的效率就越低,所以适应度函数应该尽量简洁。适应度函数的值始终大于零,这一值越大,表示种群中的个体性能越好。四旋翼无人飞行器定高飞行,并且没有固定翼无人飞行器的最大爬升/俯冲角、最大转向角等限制,其需要考虑的约束条件主要有最小航迹段长度、航迹距离约束等,具体约束如下：

最小航迹段长度：假设四旋翼无人飞行器的最小航迹段长度为lmin,则四旋翼第i段飞行的航迹段长度lhi必须满足如下条件:

lhi≥lmin

(1)

航迹距离约束：假设四旋翼无人飞行器的航迹规划起始点到其起飞点为的直线距离为ldis,则无人飞行器飞行的航迹总长度必须满足如下条件:

(2)

航迹离最近障碍约束：假设四旋翼无人飞行器在航迹规划中的安全距离为lsecurity,第i个航迹点(xhi,yhi)用激光测距仪测得的最小距离为dlimin,则

dlimin≥lsecurity

(3)

在航迹点数目限制：四旋翼无人飞行器从航迹规划起始点到其起飞点所确定的航迹点数目应该有一个上限Nhj

∑i≤Nhj

(4)

在满足上述条件后,本文采用了罚函数法作为适应度函数计算种群中个体的适应值。罚函数的公式如式(5)

(5)

(6)

航迹的优劣通过其适应度函数来评估,每一条航迹的适应值都是采用动态标定适应度函数的方法来计算的,如式(8)和式(9)。

(8)

(9)

3.3 航迹规划中的遗传操作

细个体选择的好坏直接影响到航迹点的最优选择。如果种群中的个体选择得不好会使种群中相似度接近的个体增加而导致算法过早收敛而陷入局部最优解。选择操作算子主要是决策采用何种方式将子代种群从父代种群选择出来,本文主要采用轮盘赌的选择原则[13]。

交叉在航迹规划中表现为将航迹规划中的两条航迹按照某种规则进行组合而产生新的航迹,它是产生新的种群、新个体的主要手段,包括单点交叉与多点交叉、均匀交叉等。单点交叉仅仅是在航迹种群中的航迹个体上随机的选出某一个航迹点作为交叉点,而多点交叉则是在航迹种群中的航迹个体上随机的选出相同几个位置上的航迹点作为多个交叉点,这样可以产生更多不同的航迹,增加种群的多样性。交叉算子的收敛性决定了整个航迹搜索的收敛性能,它对算法的全局搜索能力起着决定性的作用。

变异与交叉都属于进化过程,不同的仅仅是变异只是单条航迹中的某一个或某几个航迹点发生变化,而不需要两条航迹,本文的变异操作仅仅是让航迹中的一个点发生变化。变异主要对算法的局部搜索能力起着决定性的作用。变异算子一般包括六个算子,分别为扰动算子、插入算子、删除算子、平滑算子、定向扰动算子、交换算子。

4 仿真验证

运用Matlab构建走廊、小房间、障碍环境模型,走廊的两面墙平行,房间分布于走廊两侧,由带小圆圈的矩形方块表示,障碍全部假定为正方形,由实心黑色正方形表示。如前所述,四旋翼无人飞行器需要先飞到房间门口在进行航迹规划,四旋翼无人飞行器航迹规划起始点为(25,40),终点为(0,0);分别将迭代次数设置为100和200求取四旋翼无人飞行器的最优航迹,可得仿真路线图(图4,图5)。

图4 最优航迹(100代)

图5 最优航迹(200代)

当遗传迭代次数为100代时,四旋翼无人飞行器完全找到最优的航迹,并且适应值也很快收敛了;而当遗传迭代次数增加到200代时,四旋翼无人飞行器找到的最优航迹又要优于迭代次数为100代的航迹,两个航迹的步数都为25步。

5 结语

本文在局部特征地图的基础上,采用改进型的遗传算法对四旋翼无人飞行器的返程路线进行航迹规划。首先介绍遗传算法的基本原理及所要用到的一些遗传算法,针对实际情况,提出了一种改进型的遗传算法,该遗传算法在航迹规划时适应性比较强,在保证效率的基础上,也避免了陷入局部最优解与“早熟”。

[1] 谢晓方,孙涛,欧阳中辉.反舰导弹航路规划技术[M].北京:国防工业出版社,2010:1-10.

[2] 郑昌文,严平,丁明跃.无人飞行器航迹规划研究现状与趋势[J].宇航学报.2007:28(6):1441-1446.

[3] C. Zheng, M. Ding, C Zhou. Real-time route planning for unmanned air vehicle with an evolutionary algorithm[J]. International Journal of pattern Recognition and Artificial Intelligence,2003,17(1):63-81.

[4] C. Zheng, L. Li, F. Xu, et al. Evolutionary route planner for unmanned air vehicles[J]. IEEE Transactions on Robotics,2005,21(4):609-620.

[5] T. Asano, L. Guibas, J. Hershberger, et al. Visibility-polygon search and Euclidean shortest path[J]. In the Proceedings of 26th Symposium on Foundations of Computer Science, Berkeley, CA,1989:155-164.

[6] 丁明跃,郑昌文,周成平,等.无人飞行器航迹规划[M].北京:电子工业出版社,2009:42-60.

[7] 龚纯,王正林.精通MATLA最优化计算[M].北京:电子工业出版社,2009:380-400.

[8] 金晶,苏勇.一种改进的自适应遗传算法[J].计算机工程与应用,2005,18:64-69.

[9] Godberg. D. Genetic Algorithms in Search Optimization and Machine Learning[M]. USA: Addison Wesley Publishing Company,1988:7-10,59-308

[10] 马钧水,刘贵忠,贾玉兰.改进遗传算法性能的大变异操作[J].控制理论与应用,1998,15(3):404-408.

[11] 郭颖辉,朱华勇.基于遗传算法的飞行航路规划[J].计算机仿真,2004,1(2):69-71.

[12] 刘勇,康立山,陈镇屏.非线性并行算法—遗传算法[M].北京:科学出版社,1995:86-102.

[13] 雷英杰,张善文,李续武,等.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005:56-80.

Path Planning of Quad-rotor

LI Yi1WANG Zhen2JIANG Peng3YANG Zhiyong2KANG Yuhang2

(1. Navy Military Representative Office of Equipment Department in Xi’an, Xi’an 710054) (2. Naval Aeronautical Engineering Institute, Yantai 264001)(3. Naval Aviation Academy, Huludao 125001)

Under the premise of local map known, a variety of existing genetic algorithm has been modified. This paper proposes an improved genetic algorithm to carry out four-rotor UAV route planning. Traditional genetic algorithm converges slowly and is easy to fall into local optimal solution or “premature” phenomenon. In this paper, crossover probability and mutation probability has been adjusted adaptively, adaptive dynamic calibration function is also carried out. The experimental results show the algorithm’s feasibility and reliability.

quad-rotor, adaptive function, crossover probability, mutation probability, path planning

2014年6月7日,

2014年7月28日

李翊,男,硕士,工程师,研究方向:自动控制。王朕,男,硕士,讲师,研究方向:模式识别。姜鹏,男,硕士,副教授,研究方向:导航制导与控制。杨智勇,男,博士,讲师,研究方向:自动控制,人机交互系统。康宇航,男,博士,研究方向:导航制导与控制。

TP242.6

10.3969/j.issn1672-9730.2014.12.015