欧洲冠军联赛四强

行业新闻

无人机航迹规划常用算法综述

 随着航空技术日益发展, 越来越多的无人机被用于替代飞行员执行一些高危险、 高强度或大范围巡检、 搜救任务, 因此完善的任务规划系统是无人机顺利完成任务的重要保障。任务规划系统一般由航迹规划、 导航、 数据通信3大子系统组成, 而航迹规划则是任务规划系统的核心部分。

航迹规划问题分析

在不考虑时间因素的情况下, 无人机航迹规划应该是在三维空间中进行的, 但在一些任务中, 无人机保持在固定高度飞行, 不需要考虑高度变化问题。因此在进行航迹规划时可以将三维空间中的物体投影到二维平面, 从而将三维航迹规划问题降至二维, 简化问题的复杂度。但在军事突防、 电力巡线、 山地救援等应用中, 二维航迹规划实用价值有限。笔者将从规划思想和构成两方面对航迹规划问题进行分析。

1.1 规划思想

航迹规划问题是一个包含多个优化目标和多个约束的非线性规划问题[2] , 其核心就是建立目标函数的数学模型和有效地处理各项约束。由于涉及约束条件较多, 目标函数复杂, 数学模型建立困难, 为降低问题复杂性, 目前大多数学者都采用分层规划的思想, 将航迹规划分为两步进行。首先根据已知的环境信息、 任务要求等在无人机起飞前为其规划出一条满足约束条件的全局最优参考航迹。无人机在按照此航迹飞行的过程中, 当出现未知或动态威胁信息时, 再进行局部航迹动态优化。由于全局参考航迹规划需要考虑整体的优化, 因此要在避免陷入局部最优的情况下尽量减少计算量。而局部航迹动态优化用于应对突发威胁, 因此要尽量缩短规划时间以确保实时性。

1.2 规划构成

无人机航迹规划一般由以下几个部分组成: 描述规划空间, 选择航迹的表示形式, 分析约束条件, 确定代价函数, 选取航迹搜索算法和航迹平滑。

1) 描述规划空间。其目的是建立一个便于计算机进行航迹规划所使用的环境模型, 即将实际的物理空间抽象成算法能处理的抽象空间, 实现相互间的映射。规划空间的表示是否合理直接影响规划的效率和结果的优劣性。一种好的规划空间表示法应能满足如下要求:

① 规划空间能合理且尽量完善地反映飞行环境中的各种信息(地形、 威胁、 障碍等), 以利于航迹搜索;

② 当飞行环境中的某些信息发生变化时能实时地进行更新, 以满足实时应用的要求;

③ 能满足无人机自身性能约束条件, 包括最大拐弯角、 最大爬升/俯冲角、 最大航迹距离、 最小航迹段长度和最低飞行高度等。

常用的规划空间表示方法有栅格法和图形法。栅格法将规划空间分解成为一些简单的单元,并为每个单元分配一个代价值, 对应于无人机经过空间相应区域的代价, 并判断这些单元之间是否存在可行路径, 找到包含起始点和目标点的单元, 从起始单元开始, 依次向栅格中代价最小的邻域移动, 最后到达目标单元。航迹搜索算法中的A*算法、 动态规划法等就是利用栅格描述规划空间。由于数字地图采用栅格的形式存储, 所以多数的航迹规划研究都是使用栅格法表示规划空间。图形法首先根据一定规则将规划空间表示成一个由一维线段构成的网络图, 然后采用某一搜索算法在该网络图上进行搜索。使用图形法必须表示出所有可能的路径, 否则就可能丢失最优解。图形法相比栅格法数据处理量少, 但是更新较困难。常用的图形法有Voronoi图法 、 可视图法(Visibility Graph) 、 随机路标图法(PRM:Probabilistic Road Map) 等。

2) 航迹表示。其形式有两种:一种是基于无人机运动学、 动力学描述的连续平滑航迹, 采用此种表示方法可以省去最后的航迹平滑环节;另一种是用航迹点表示, 相邻航迹点之间用直线段连接几何折线航迹。第2种表示方法有如下优点:

① 可以通过调整航迹节点的数目达到所需要的精度;

② 将复杂的航迹规划问题分解为一组统一形式的小规模子问题, 对于每个子问题, 只需关心一个点的坐标, 从而将考察航迹是否可行变为仅考察一个点或一条直线段是否满足要求;

③ 便于实现并行、 分布式计算。

3) 分析约束条件。航迹规划问题需要考虑的约束条件包括环境约束、 任务约束和无人机自身性能约束。环境约束有威胁约束(如被敌方雷达发现概率、 敌方导弹高炮击落概率、 撞地概率等)、 禁飞区约束、 复杂气象区约束等;任务约束有任务完成时间、 起始点、 目标点、 固定航向角、 低空/超低空突防等;无人机自身性能约束有最大/最小平飞速度、 最大航程、 最高/最低飞行高度、 水平最小转弯半径、 最大爬升角/俯冲角、 最大纵向曲率、 最大法向过载等 。若是进行二维航迹规划, 则不需要考虑无人机的爬升/俯冲角约束和飞行高度约束。

4) 确定代价函数。代价函数将算法与实际物理问题紧密联系在一起。对于无人机航迹规划, 代价函数是评价航迹优劣的标准, 代价值越小则表明航迹越优, 反之表明航迹越差。确定代价函数需要综合考虑影响航迹性能的各项因素, 对各个指标进行量化和计算。三维航迹规划的代价函数通常包含航迹长度代价、 威胁代价和高度代价, 表示为

                                                                      J=ω1L+ω2T+ω3H(1)

                                                                      ω1+ω2+ω3=1(2)

其中J为航迹总代价, L为航迹长度代价, 一些文献也称其为燃油代价, T为威胁代价, H为高度代价; ω1、ω2、ω3为相应的权系数, 根据任务需要设置其值。二维航迹规划则不需要考虑高度代价。

5) 选取搜索算法。根据任务需求选取合适的算法规划出满足约束条件、 规避障碍、 使代价函数获得最优值的航迹是航迹规划问题的核心部分。

6) 航迹平滑。通过相应算法搜索出的航迹对于无人机实际飞行而言并不一定可行, 例如规划出的航迹拐弯点较多, 而无人机在实际飞行中由于自身机动限制不能频繁转弯, 因此需要对规划出的航迹进行平滑处理, 消除不必要的拐弯点以利于无人机实际飞行。常用航迹平滑方法有三次样条插值法、 贝塞尔曲线(Bezier Curve)、 k-trajectory算法 等。

2 常用航迹规划算法

无人机航迹规划的本质是路径规划, 即寻找适当的策略构成连接起点到终点位置的由序列点或曲线组成的路径, 因此用于航迹规划的算法实际上也就是路径规划算法。路径规划算法有很多, 每种算法都有其自身的优缺点和适用范围, 按照规划决策可以将算法分为传统经典算法和现代智能算法[11] 两类。

2.1 传统经典算法

近年来常用于航迹规划的传统经典算法有Dijkstra算法、 人工势场法(APF:Artificial Potential Field)和模拟退火算法(SAA: Simulated Annealing Algorithm)。Dijkstra算法是图论中求解最短路径的经典算法, 适用于每条边的权数为非负的情况, 能得到从指定顶点到其他任意顶点的最短路径。使用Dijkstra算法进行航迹规划, 构建的赋权图的顶点代表航迹点, 赋权图的边代表所有可行航迹, Dijkstra算法的作用就是在这些可行航迹里找到最优航迹。Dijkstra算法实现简单, 但其运算时间和所用内存与搜索空间中节点个数平方成正比, 在大范围高维空间中搜索时间长, 对内存要求也很高, 因此多用于二维静态航迹规划[12,13] 。由于航迹规划空间范围大, 对于Dijkstra算法在航迹规划中的应用, 如何选取有效航迹点, 减少航迹点数量, 缩短规划时间是问题的关键。文献[12] 在Voronoi图的基础上使用Dijkstra算法寻找最优航迹, 将威胁看作一个点, 选取各威胁点之间连线的中垂线的交点为航迹点。这种方法能保证航迹最大化避开各个威胁, 安全性高, 但航迹较长。并且没有考虑无人机最大转弯角约束, 航迹不一定可飞。文献[13] 在可视图的基础上使用Dijkstra算法寻找最短航迹, 将多边形障碍的各个顶点看作航迹点, 并建立转弯角约束机制。这种方法得到的航迹短, 满足无人机最大转弯角约束, 但由于航迹贴近障碍物, 安全性较低。此外, 可视图不能表达物体运动的方向性约束的缺陷导致Dijkstra算法在搜索时可能找不到路径。虽然Dijkstra算法多用于二维航迹规划, 但也有学者将其应用于三维航迹规划。文献[14] 将飞行空间映射到由若干个四面体组成的三维Delaunay三角网中, 四面体的顶点对应威胁的位置, 四面体内切球的中心作为航迹点, 所有相邻四面体内切球中心点的连线构成一个三维网络, 这个三维网络就是所有可行航迹。然后用Dijkstra算法在这个三维网络上寻找最短航迹。最后用人工势场法对初始航迹进行优化, 获得平滑可飞的航迹。该方法与Voronoi图法类似, 规划出的航迹能最大化避开威胁, 安全性高, 但航迹相对较长。目前使用Dijkstra算法进行航迹规划多是利用Voronoi图、 概率地图或可视图描述规划环境, 然后在此基础上利用Dijkstra算法寻找最短航迹, 但得到的航迹若安全性高则航迹长, 若航迹短则安全性低, 没有在航迹长度与安全性之间寻找到一个好的平衡。

人工势场法是一种模拟电势场分布的规划方法, 任务区域内的目标点产生引力场, 威胁源产生斥力场, 无人机在引力和斥力的共同作用下向目标点运动。传统人工势场法定义如下。

(未完待续)

导航栏目



联系我们

LIANXIREN:CHENXIANSHENG

YOU XIANG:cj@swtjb.net.cn

GONG SI:ZHONGKEHUIJUKEJIYOUXIANGONGSI

DI ZHI:BEIJINGXICHENGQUPUTAOYUAN1HAOPANGUZHIKU1LOU


用手机扫描二维码关闭
二维码