无人旋翼飞行器的三维在线航迹规划研究王兴龙

1、第二十八届（2012）全国直升机年会论文无人旋翼飞行器的三维在线航迹规划研究王兴龙 宋彦国 （南京航空航天大学直升机旋翼动力学国家级重点实验室，南京, 210016） 摘 要：无人旋翼飞行器的航迹规划系统包含初始参考航迹的确定和在线航迹规划。初始参考航迹是在执行飞行任务前,根据所经区域内已知的地形、地貌、障碍和威胁等信息以及飞机本身机动能力的限制计算出初始飞行航迹；在线航迹规划是当飞行环境中有预先未知威胁出现时，可根据更新后的信息重新规划来获得新的全局最优航迹。本文利用进化算法规划出初始参考航迹，利用A*算法进行航迹在线重规划。仿真结果表明，进化算法得到了很好的初试参考航迹，A*算法的搜索速度

2、满足了在线航迹规划的实时性要求。关键词：无人旋翼飞行器; 在线航迹规划; 进化算法; A*算法1 引言无人旋翼飞行器的航迹规划是指在给定的规划空间内，在满足众多约束条件的情况下，寻找出一条从起始点到目标点的最优或次优的飞行航迹，该条航迹要尽量减少无人飞行器在飞行过程中被敌方雷达等探测设施捕获和被敌方火力单元摧毁以及撞地或撞山的概率，这对航迹规划系统提出了更高的要求。为了满足这些要求，需要在规划方法，系统结构，甚至交互式界面等方面进行大量研究工作，这正是现在所面临的主要任务。目前针对航迹规划问题提出了很多优化方法,这些方法各有优缺点,很难同时满足实时性、全局最优性的要求。文献1讨论了A*算法在二

3、维水平航路的规划应用和基于蚁群算法的航路规划研究，但都仅限于离线航迹规划，对时间没有渴求的场合，未提及在线航迹规划；文献2介绍了基于RTRS(一种针对静止目标的UAV在线实时航迹搜索方法)的在线航迹规划的方法，但却没有讨论飞行过程中一旦出现新的威胁，在线重规划能否满足实时性要求；文献3考虑了二维平面的实时航迹规划，但这只适用于机器人的二维航路规划，不能满足无人飞行器的三维航迹规划要求。 由于进化算法不受空间限制性假设约束，不要求优化函数具有连续、导数存在等假设，对航迹规划这种含有大量模糊信息、多约束的问题，总能搜索到全局最优解或者近似最优解，并且改进的A*算法具有高速的搜索速度和效率，所以本文

4、拟采用进化算法和A*算法相结合的方法作为航迹规划系统的核心算法进行航迹在线重规划研究。2 基于进化算法的初始航迹规划进化算法是一种基于生物进化理论的群体搜索技术，是一种迭代算法，它是从某个初始解集出发，遵循一定的操作规则，比如选择、复制、交叉、变异等遗传操作，不断地通过迭代计算以得到新一代解集，并根据个体的适应度，按照“适者生存、优胜劣汰”的法则，引导搜索过程向“最适应环境”的个体(即最优解)逼近，逐代的演化出越来越优的近似解，最终能收敛到最优解或满意解。任何进化计算技术需要首先确定基因编码的方式，用以表达所研究的问题。本文的进化算法采用实值基因编码方式，如图 2.1所示，每个染色体代表一条航

5、迹，它由一系列航迹节点构成，航迹节点之间用直线连接。其中每一航迹节点保存为一个结构体，除了记录航迹节点的空间坐标外，还包含状态变量，它包含如下信息：(1) 当前节点是否为可用航迹点，即确定该点不在等效威胁和障碍的范围之内，确保无人旋翼飞行器飞行时可以安全到达该点；(2) 接该节点和上一节点的航迹段是否为可用航迹段，即确保航迹段没有穿过威胁和障碍。当且仅当一条航迹的所有节点和所有航迹段都是可用时，该航迹才是可行的，因此种群中的染色体(航迹)可能是可行的，也可能是不行的。 图 2.1 因编码染色体结构对于每条航迹的评价函数，确定为： 其中，指该条航迹从起始点到目标点的总距离代价值，航迹规划总是寻求

6、短距离的飞行路径，所以越小越好；指该条航迹上各个节点到各个威胁中心的威胁代价值，规划出的航迹应该尽量远离威胁，所以越小越好；指该条航迹上各个节点的高度代价值，令等于当前点的高度值与规定的最小飞行高度的差值，为了利用地形的遮挡打到隐蔽飞行的目的，飞行器飞行高度不宜太高，而过低又会增加飞行器碰地的概率，所以高度的选择应适宜，越小越好。为相应的权系数，通过对参数的大小调节，可以改变各个代价在整体中所占的比重。综上所述，评价函数越小，代表此条航迹就越理想。对于进化算子，本文采用交叉算子和变异算子。其中交叉算子采用单点交叉，只有一个交叉点，在选择出来的个个体中任意挑选两个个体作为交叉对象，随机产生一个交

7、叉点位置，然后形成两个子个体，得到两个交叉后的新航迹；根据本文研究的具体内容，在变异算子中加入转弯角限制问题，即在选择出来的个个体中任意挑选一个个体作为变异对象，随机选择一航迹节点，如果该节点处航迹拐弯角大于给定的最大值，则在于该航迹节点相连的两航迹段上各插入一新的节点，然后删除开始选择的节点，得到变异后的新航迹。进化算法的步骤如下：(1) 随机生成大小为的种群；(2) 根据评价函数评价每一条航迹，将所有航迹按评价值从小到大排列；(3) 按评价值从小到大原则选取个个体作为繁殖下代的父代；(4) 对选择出来的个个体按一定的概率进行交叉和变异操作；(5) 将新生成的个体加入到种群中并计算各自的评价

8、值；(6) 将扩展后的种群中最差的，即评价值较大的个个体删除，使其恢复原来种群的大小；(7) 是否达到规定迭代次数或者近10次的迭代得到的最小代价值不变，是则转第(8)步，否则，进入第(3)步。(8) 选出航迹代价最小的个体作为所求航迹，进化过程结束。下面给出利用进化算法在已建立的三维的等效数字地图中规划出来的初始参考航迹，如图 2.2至图 2.5所示。 图 2.2 第0代个体 图 2.3 第50代个体 图 2.4 第150代个体 图 2.5 最优航迹平面图图 2.2至图 2.4表明，最优个体在经过150迭代后其代价值已经保持不变，说明进化算法收敛到了全局最优解，代价值最小的个体即为最优航迹。

9、从图 2.5最优航迹平面图中可以看出，最优航迹成功的避开了威胁和障碍，而且整条航迹的航迹点少，拐弯角小，飞行过程中不用频繁转弯，有利于飞行安全。3 在线航迹规划3.1 A*算法原理A*算法属于人工智能中一种经典启发式最优化算法，在具有二维规划环境的机器人路径规划中是被许多学者认为是最实用的搜索算法。A*搜索算法的代价函数由两部分组成，函数形式为： 式中表示某个待扩展节点,设表示起始点,表示目标点。则表示从起始点到当前点的实际代价值;表示从当前点到目标点的估计函数,称之为启发函数。就表示从起始点出发,通过节点到达目标点的最小代价路径的估计值。A*算法的思想就是每次在多个候选节点中选择值最小的节点

10、进行扩展。用A*算法在三维环境中进行在线的航迹规划，由于搜索空间的巨大，必然会导致算法的复杂性，在线规划所需要的时间增长，所以有必要通过缩小搜索范围和降维处理来简化算法，以便满足在线规划的实时性要求。首先，虽然无人旋翼飞行器可以空中悬停、任意方向飞行并且具有良好的地速性能，不受最大转弯角、最小航迹段长度的限制，但为了节省油耗和尽快完成任务，航迹中有些节点实际是不可取的，因此在航迹节点的扩展过程中,可以把背离目标点的节点去除掉,只留下趋向目标点的节点,这样可以大大缩减搜索空间,提高在线航迹规划的效率；其次，由于航迹规划的目的是为无人旋翼飞行器寻求一条最短、最安全的飞行航迹，所以让航迹距离、飞行高

11、度和所受威胁程度共同组成代价函数。在保证安全的前提下，航迹距离越小则航迹越优，所以中仍保留了在二维环境中应用的经典距离代价函数，飞行高度和所受威胁程度则起到调节节点远离各个威胁和控制飞行高度的作用。具体如式(3-2)。 式中表示从起始点到当前点的平面投影距离，即实际代价值；表示从当前点到目标点的估计得平面投影距离，即估计代价值；表示当前节点到各个威胁中心的威胁代价值；表示当前节点的高度代价值；为相应的权系数。3.2 在线航迹规划仿真对于在线航迹规划，在无人旋翼飞行器执行任务之前，地面计算机先把用进化算法规划好的初始参考航迹上传给机载计算机，随后飞行器开始执行任务。飞行器在飞行过程中要实时探测前

12、方是否有新的威胁，如果有新威胁，则立即减速飞行并更新飞行数据和数字地图，同时通过计算判断当前飞行航迹是否为不可通过状态。如果新威胁并未阻碍当前航迹，即航迹为可通过，则飞行器处于次紧急状态，但此时飞行航迹或许已经不是最优航迹，所以利用进化算法对新的数字地图进行全局规划，得到新的航迹，并得出当前飞行航迹是否还是最优航迹，如果是，则退出紧急状态，继续飞行；如果不是，则立即更新飞行航迹，飞行器转入新航迹飞行。如果新威胁阻碍了当前航迹，即航迹为不通过，则飞行器处于主紧急状态，立刻利用A*算法进行在线重规划，得到一条避开新威胁的航迹，并更新飞行航迹，随后飞行器转入新航迹飞行。重复上述过程，直至飞行器到达目

13、标点,其具体算法流程图如图 3.1。图 3.1 算法流程图本文在MATLAB环境下对所得算法进行了相应的仿真，仿真算例中，给定规划区域为，给定初始点为，目标点为。规划前测得的4个已知等效威胁，参数分别为：第一个等效山峰：第二个等效山峰：第三个等效山峰：第四个等效山峰：其中，表示第个等效山峰的高度，表示第个等效山峰的坐标，表示第个等效山峰在方向和方向的半径的一半。建立新威胁库，其中含有5个新威胁信息，每次有新威胁中断时，就会从库里随机选取一个作为新探测到的威胁。参数如下：第一个新威胁：第二个新威胁：第三个新威胁：第四个新威胁：第五个新威胁：仿真过程如图 3.2至图 3.5所示。 图 3.2 参考

14、航迹 图 3.3 飞行器沿参考航迹飞行 图 3.4 第一个新威胁出现 图 3.5 第二个新威胁出现 其中，图 3.2为利用进化算法规划出的参考航迹，如果在飞行器到达目标点之前一直没有出现新的威胁，则飞行器就沿此参考航迹飞行；图 3.3为在没有出现新威胁的情况下，飞行器沿参考航迹飞行；图 3.4为探测到第一个新威胁时的情况。航迹系统通过判断得知新威胁并未阻碍参考航迹，但此时参考航迹可能不再是最优轨迹，所以旋翼飞行器应该适当的降低飞行速度，判断原参考航迹是否还是最优航迹，即利用进化算法在新的三维数字地图上规划出一条从航迹前方某节点到终点的新航迹，此时新航迹为全局最优航迹，随后飞行器会在新航迹的起始

15、节点处转入新航迹飞行。图中由于新出现的威胁离参考航迹很远，所以未对参考航迹构成必要威胁，所以原参考航迹仍为最优航迹；图 3.5为探测到第二个威胁时的情况，航迹系统通过判断得知新威胁已经阻碍参考航迹，使之不能通过，所以必须立即进行在线重规划。由于无人旋翼飞行器具有空中悬停、任意方向都可以飞行等特点，所以飞行器先根据距离新威胁的程度，适当的选择减速飞行或者悬停，以便在飞行器被新威胁障碍发现或摧毁前规划出能新的全局最优航迹，进而达到避开新威胁的目的。图中的绿色曲线为利用A*算法规划出的新航迹，随后飞行器会沿着新航迹继续飞行直到到达目标点。计算结果和所用时间见于表1。表 1 航迹规划结果和数据规划算法

16、起始点(km)目标点(km)航迹点数航迹距离所用时间进化算法(0,0,0)(200,200,0)5310.31 km4.56 sA * 算法(0,0,0)(200,200,0)125320.90 km0.48 sA * 算法(98,65,35.3)(200,200,0)71173.76 km0.23 s为了比较两种算法的优缺点，给出了分别利用进化算法和A*算法规划初始参考航迹的数据。进化算法规划初始参考航迹用时4.56s，航迹距离为310.31km，A*算法规划初始参考航迹用时0.48s，航迹距离为320.90km。A*算法在航迹的搜索速度上具有优越性，而进化算法在航迹的最优性上较为突出，所以

17、进化算法适合应用在基于地面计算机的初始参考航迹上，A*算法适合应用在基于机载计算机的在线航迹规划上。4 结论本文研究了基于进化算法和A*算法的在线航迹规划问题，并在三维数字地图中对其进行了仿真实现。结果表明，进化算法得到了很好的初始参考航迹。规划出的航迹节点少，避免飞行器频繁转弯，但最优解的收敛速度不够快。飞行过程中，A*算法的搜索速度和效率较高，很好的满足了在线航迹重规划的实时性要求。考虑以上两种规划算法各自的优点，采用的进化算法和A*算法相结合的方法来进行在线航迹规划，达到了三维航迹在线规划的目的。参 考 文 献1 柳长安.无人机航路规划方法研究D.博士学位论文，西安：西北工业大学，2003年2 郑昌文、丁明跃编著，“无人飞行器航迹规划”，北京：电子工业出版社2008年10月3 严建林.基于进化算法无人机航路规划技术研究D.硕士学位论文，南京：南京航空航天大学，2008年4 张厚道.基于数字地图的无人战斗机低空突防轨迹规划方法研究D.硕士学位论文，西安：西北工业大学，20045 王磊，移动机器人路径规划研究D.硕士学位论文，哈尔滨：哈尔滨工程大学