基于改进稀疏 A算法的三维航迹规划方法.doc

精品论文基于改进稀疏 A*算法的三维航迹规划方法张俊峰，周成平（华中科技大学图像识别与人工智能研究所，武汉 430074）5摘要：无人飞行器的飞行空间广大，规划环境多种多样，针对带有方向约束的海对陆规划环 境，本文提出了一种改进的稀疏 A*算法用于该环境下的三维航迹规划。给出稀疏 A*算法改进后的搜索区域模型，在陆地环境和海洋环境中分别采用不同的稀疏策略加快规划，用逆向 规划的方法使航迹规划满足攻击段的方向约束，用局部搜索的方法解决发射段的方向约束问10题。仿真实验表明，改进后的稀疏 A*方法比一般稀疏 A*算法规划速度更快、更加适用于这 种带有方向约束的海陆规划环境。关键词：航迹规划；改进稀疏 A*；海陆规划；方向约束中图分类号：TP13;TP1815A 3D Route Planning Based On The Improved Sparse A* AlgorithmZHANG Junfeng, ZHOU Chengping(Institute for Pattern Recognition and Artificial Intelligence, HuaZhong University of Science andTechnology, WuHan 430074)20Abstract:Against the 3D route planning for land and sea with direction constrained planning environment, this article proposes a improved sparse A* algorithm. This article gives the searching space mode of the sparse A* algorithm, provides different sparse strategies in the land and marine environment, uses reverse planning method to satisfy the direction constraint of the attack segment, uses local search method to solve the direction constraint of the emission25paragraph. Simulation results show that the improved method is more adaptable than the general algorithm for the land and sea with direction constrained planning environment.Key words: route planning; improved sparse A*; land and sea route planning;direction constraint0引言30飞行器航迹规划是在综合考虑飞行器的机动性能、飞行区域以及飞行任务的一些特定约 束条件等因素的基础上，规划处从起始点到目标点的最优航迹或满足一定要求的航迹1。飞 行器航迹规划在栅格规划空间中一般是三维规划，搜索空间广大，常用的栅格搜索方法包括 A*算法和遗传算法2等。为了减少搜索空间，Robert J S 等提出了在二维平面上进行航迹搜 索的改进 A*算法，叫做稀疏 A*算法3。李春华等将稀疏 A*算法扩展到三维空间4，根据具35体约束条件剪除搜索空间，大大缩短了搜索时间。但是搜索空间的广大导致规划环境的多种 多样，特定约束条件根据任务的不同也不相同，一般性的稀疏 A*算法不能保证在各种情况下都能满足规划时间要求。针对带有方向约束的海陆规划环境下三维航迹规划，本文对用于 三维航迹规划的一般性稀疏 A*算法进行改造。改进稀疏 A*算法的搜索模型，在不同规划环 境中分别采用不同的稀疏策略，用逆向规划的方法使目标点满足入射角度约束，采取在发射40点周围局部搜索的方法解决发射段的方向约束问题，使规划能在较短的时间寻找到较优的航 迹，接下来的仿真实验证明了该改进算法的优良之处。作者简介：张俊峰（1989-），男，硕士，无人飞行器航迹规划通信联系人：周成平（1957），男，副教授，计算机视觉，无人飞行器航迹规划研究. E-mail:morphlingHust1989163.com- 5 -1问题描述无人飞行器的航程从几百公里到几千公里不等，经过的环境各不相同，大体来说，有陆 到陆、海到陆、海到海这么几种情况。本文讨论的规划是海到陆的情况，即发射点在海上而45目标点在陆地上，无人飞行器需要满足的约束具体有以下几种：1)匹配辅助制导约束：无人飞行器要利用 GPS 或者地形匹配区进行定位，陆地环境 优先选择地形匹配区，其次选择 GPS，海洋环境只有 GPS 供选择；匹配辅助制导 还有最小匹配距离和最大匹配距离的约束；2)水平机动约束：由于飞行器本身性能限制，水平机动有最小转弯半径和最大转弯角50度的约束；3)飞行高度约束：飞行器有最大飞行高度约束和最小离地高度约束；4)高度机动约束：由于飞行器本身性能限制，飞行器有最小/最大爬升角度，最小/最 大爬升水平距离，最小/最大下滑角度，最小/最大下滑水平距离约束；5)禁飞区/威胁区约束：航迹不能通过禁飞区，要尽量绕开威胁区；556)方向约束：目标点入射角度在任务文件中给定，实际入射角度可在给定角度一定范 围内浮动，目标点和最后一个导航点之间不做水平机动；发射点和第一个导航点之间不做水平机动，发射点方向可以任意；7)航程约束：飞行器有最大的飞行航程限制。基于稀疏 A*算法的航迹规划主要任务是从发射点开始在航迹点的可行空间中寻找下一60个可行航迹点直到到达目标点，这一系列航迹点组成的航迹在所有可以搜索到的航迹中和固 定的代价权值组合下是代价最小的，也可以说是最优的。2改进的三维稀疏 A*算法三维稀疏 A*算法与传统 A*算法的最大区别是前者在扩展航迹节点时，将考察各种约束 条件，有效地去除搜索空间。同时将该航迹点的可行搜索空间分割成多个子空间，每个子空65间搜索代价最优的航迹点5。稀疏 A*算法与传统 A*算法的本质是一样的，是一种基于启发式搜索策略的智能搜索算 法，用于解决从起始点到目标点之间最短(或最小代价)路径的寻优问题，算法流程也没有大 的改变，具体如下：1)初始化，输入初始状态，得到起始点；702)启动算法，将起始点放入 OPEN 表中；3)执行搜索，扩展子节点，运行搜索过程，搜索完成则输出结果，否则继续搜索。 核心搜索部分的流程具体如下：1.对 OPEN 表以代价值为键进行排序；2.取出代价最小的航迹点 p,放入 CLOSED 表中；753.若航迹点 p 是目标点，返回搜索完成，否则执行下一步；4.在扩展区域中搜索航迹点 p 的子节点，计算子节点的代价，检测子节点是否在 OPEN表中，如果在 OPEN 表里且当前代价更小，更新 OPEN 表中子节点代价，将子节 点父指针指向 p，完成一次扩展转步骤 1，如果不在 OPEN 表中，则执行下一步；5.检测子节点是否在 CLOSED 表中，如果在 CLOSED 表中且当前代价更小，更新子80节点代价，将子节点指针指向 p，将子节点移回 OPEN 表，完成一次扩展转步骤 1， 如果子节点不在 CLOSED 表中，直接将子节点父指针指向 p 并放入 OPEN 表，完成一次扩展转步骤 1。2.1稀疏 A*算法的搜索区域三维航迹规划有最小/最大匹配距离即最小/最大扩展步长、最大拐弯角度约束，用几何85方法可以推出当前航迹点的水平投影搜索区域是一个关于当前航迹点水平飞行方向对称的扇形面积，它的圆心角大小至少是飞行器的最大拐弯角大小。如图 1 所示，其中阴影部分为可行搜索区域，q 为最大拐弯角度的一半,根据圆周角定理可以推出扇形面积的圆心角大小：p qqo90图 1 水平搜索区域Fig.1 Horizontal search area三维航迹规划有最大爬升角、最大下滑角等高度机动限制，以当前航迹点为参考点，在笛卡尔坐标系下把水平可行搜索区域向 Z 轴正向旋转最大爬升角，向 Z 轴负向旋转最大下 滑角，得到的立体区域即是当前航迹点的可行搜索空间，这个空间是一个四棱锥面和球面包95围的区域，如图 2 所示。普通稀疏 A*算法的策略是在这个区域按照一定角度粒度取 M 个扇 面，在每个扇面上按照一定距离和角度粒度将扇面分成 S 个扇区，也可以说是划分网格，这 样就把搜索空间分解为 M ´ S 个子空间，然后在子空间中搜索地形匹配点或者 GPS 点。航 迹点三维搜索区域如图 2 所示：1002.2 改进的稀疏策略图 2 航迹点三维搜索区域Fig.2 The waypoint 3D search area105110无人飞行器的匹配制导约束要求飞行器在陆地上优先搜索匹配区，在海洋上只搜索 GPS 点，所以设计多种网格尺度加快搜索。搜索之前要确定当前航迹点搜索区域所在环境是陆地 还是海洋，判断准则是以水平搜索扇面的四个顶点代表搜索区域，如果四个顶点至少有一个 在陆地上就认为是陆地环境，否则为海洋环境。确定环境之后，在不同的环境采取不同的稀疏策略。陆地环境下首先用最粗的网格粒度 划分扇面，在每个网格中随机挑选一点判断是否是匹配点，是匹配点则进行水平连接和高度 规划试探生成一段可行航迹，不是匹配点直接抛弃；可行航迹生成成功则保留匹配点进 OPEN 表，否则抛弃该点；如果在最粗的网格粒度下找到了匹配点就认为这次航迹点的扩展115120125130135140成功了，否则减小网格粒度重复以上步骤直到网格粒度取了预定的最小值；最细网格粒度下匹配点和 GPS 点同等看待，能够生成可行航迹段就保留，不能就抛弃。海洋环境下只搜索 GPS 点，而 GPS 点可以是地图任意位置，使用陆地环境的稀疏策略很容易在最粗网格就扩 展成功跳出，显然这样丢失了大量解，故海洋环境下在最细网格粒度下进行搜索扩展。这种 稀疏策略具有自适应性，同时避免了丢解过多的缺点，加快了海陆环境下的航迹规划。2.3 方向约束问题目标点的入射角度在一个漏斗状的区域范围内，而发射点的方向是任意的，正向规划的 话发射点的可行搜索区域是一个球形，一方面增加了无用方向的扩展，增加了 OPEN 表里 的子节点个数，而 A*的规划时间与 OPEN 表里的子节点个数是正相关的；另一方面规划到 目标点附近入射方向很难对准到漏斗形的区间中，因为目标点在陆地上，陆地上优先选择地 形匹配点，而匹配点是有可匹配方向的。本文采用逆向规划的方法解决这个问题，把目标点 作为起始点进行规划，起始点的搜索区域跟 2.1 节中间航迹点的搜索区域非常类似，工程上 实现起来比较方便，而且发射点方向任意，发射点在海上附近都是 GPS 点，规划到发射点 附近时方向相对好对准一些。逆向规划并非完美，规划到离发射点最近的一个航迹点 P 点时会发生搜索回溯现象，个 别情况下耗时巨大不能忍受。经分析发现造成该问题的原因在于稀疏策略丢失了一些解导致 考察的 GPS 点不够多，虽然 P 点方向在 p 点和发射点的连线方向上，但是 P 点到发射点的 距离不满足最小/最大匹配距离，这样算法就发生了回溯。为了解决这个问题，本文提出了在发射点周围局部搜索的方法。具体来说，以发射点为 球心，分别以最小匹配距离和最大匹配距离为半径做球面，两个球面之间的立体区域即是发 射点局部搜索的搜索空间。局部搜索空间依然采用海洋环境下的稀疏策略在子空间中从内到 外找 GPS 点和距离发射点第二近的航迹点进行连接，实际上，逆向 A*规划的目标点此时就 变成了距离发射点第二近的航迹点而不再是发射点了。至于如何判断航迹点是否是距离发射点第二近，可以采取距离判断的方法：当规划到的 航迹点满足它到发射的距离在二倍最小匹配距离和二倍最大匹配距离之间时就把当前航迹 点作为规划结束点，进入局部搜索处理阶段。2.4 A*估价函数设计稀疏 A*算法是一种启发式搜索算法，启发中的估价是用估价函数表示的，估价函数一 般形式为6：f (n) = g(n) + h(n)(1)145150g(n) 是在状态空间中从初始节点到 n 节点的实际代价，h(n) 是从 n 到目标节点最佳路径的估计代价，体现了搜索的启发信息。本文考虑的代价包括三个要素：航程、经过威 胁区长度、高度。已知航程是起始航迹点到当前航迹点的航程，预估航程即当前航迹点到发 射点的直线航程；已知经过威胁区长度是起始点到当前点航迹经过威胁区的长度，预估经过 威胁区长度即当前航迹点到发射点直线航迹经过威胁区的长度；已知高度是起始点到当前点 航迹的平均高度，预估高度与地形相关，无法估计。最后得出的代价计算公式为：f (n) = w1 * (Lg + Lh ) + w2 * (LTg + LTh ) + w3 * H g(2)其中，w1 、w2 、w3 代表权值系数，通过调整它们的权值表现出航迹的偏好； Lg 、 Lh155代表已知航程和未知航程，H g 代表已知高度。3仿真实验LTg 、 LTh 代表已知经过威胁区长度和预估经过威胁区长度，160本文算法在 Intel Core 2 Duo CPU 2.80GHz PC 机上进行试验，运行环境为 Windows XP， 编程环境为 VS2005。实验使用了 36000 ´ 54000 的数字地形高程图，每个像素代表的实际距 离是 30m。代价权系数w1 、w2 、w3 取值分别为 80,10,10，表 1 给出了改进后的稀疏 A*算 法和普通稀疏 A*算法的规划时间比较，两种方法都是逆向规划，普通稀疏 A*算法一直采用 最细粒度的网格：表 1 规划时间对比表Tab.1 Planning time comparison table规划方法规划时间/s实验一实验二实验三实验四实验五改进稀疏 A*864524171067387普通稀疏 A*10265313413256451165注：统计的规划时间经过了四舍五入的操作1701754结论飞行器的规划环境多种多样，普通的稀疏 A*算法在特定规划环境中不一定好用，本文 给出了一种用于海对陆规划环境三维规划的改进稀疏 A*算法。首先给出稀疏 A*算法的扩展 区域模型，在陆地环境上采用粒度从粗到细的弹性网格稀疏策略，在海洋环境上直接使用最 细粒度网格稀疏搜索空间，以此加快规划。另外对于攻击段和发射段的方向约束问题设计逆 向规划和局部搜索的方案。仿真实验表明，改进后的方法比一般稀疏 A*算法针对性更强， 更能适应这种带有方向约束的海陆规划环境。对于其他复杂的规划环境，也可参考本文的改 进思路对稀疏 A*算法进行改进。参考文献 (References)1801851 郑昌文，严平等.飞行器航迹规划研究现状与趋势J. 宇航学报，2007，28（6）：1441-1446. 2 崔珊珊. 遗传算法的一些改进及应用D. 合肥：中国科学技术大学，2010.3 Robert J S, Peggy G I S. Robust algorithm for algorithm for real-time route planningJ. IEEE Trans. onAerospace and Electronic System,2000,36(3):869-878.4 李春华，郑昌文. 一种三维航迹快速搜索方法J. 宇航学报，2002，23（3）：13-17.5 陈前洋，秦筱楲等. 基于稀疏 A 算法的三维航迹并行规划算法J. 华中科技大学学报：自然科学版，2005，33（5）：42-45.6 姚远，周兴社，张凯龙等. 基于稀疏 A 和改进人工势能场的无人机动态航路规划J. 控制理论与应用，2010，27（7）：953-959.