论文部分内容阅读
[摘要]针对传统的A*算法在无人机航迹规划问题中的局限性,提出一种改进的A*算法,并结合无人机的性能约束直接对三维空间进行航迹搜索。算法有效的减少搜索空间,缩短搜索时间。仿真结果证明改进算法的有效性。
[关键词]航迹规划 三维航迹 改进A*算法
中图分类号:TP2文献标识码:A文章编号:1671-7597(2009)0810017-02
一、基于改进A*算法的无人机三维航迹规划
(一)算法描述
在A*算法中,恰当的启发函数可以高效率的找到最优路径,动态权值是一种提高启发式搜索算法效率的有效方法。传统的A*算法代价函数为:
,在代价函数中启发函数的参数是一个常值。针对无人机航迹规划搜索的需要,结合变权分析思想,采用动态权值的方法对A*算法进行优化,通过对搜索初、后期赋予启发函数不同的权值来实现,将算法的代价函数改进为:
式中:表示由起始点到当前结点的实际代价值;
表示由当前结点到目标点的实际代价估计值。
采用由当前结点与目标结点之间的直线距离作为启发函数:
其中: 为保证能够搜索到目标的最小权值, 为一次搜索的节点数。从而在搜索初期当无人机距离目标较远时,值较大,以速度优先,保证规划可以快速的收敛到一个与目标接近的范围内;在搜索后期接近目标时
值接近1,以准确度优先,保证当无人机接近目标时减少搜索的盲目性。
(二)三维空间航迹结点扩展
通过适当的网格对规划空间进行合理的划分是实施A*算法的基础[3],网格大小由约束条件来确定。将无人机的性能约束[4]与规划空间的划分结合起来,是缩小搜索空间的有效方式,从而能够有效的减小扩展的结点数量。具体的结点扩展方法如下:
1.最小步长,最大拐弯角和最大爬升/俯冲角约束。在三维航迹规划空间中,每一个网格取做一小立方体,边长为其最小步长。当无人机从一个网格进入相邻网格时,可在最大拐弯角、最大爬升/俯冲角的范围内选择下一个可行航向。设定上升和下降时与水平方向的夹角不超过45度,这样无人机的飞行限制在向前的九个方向,实际上当前结点的可搜索空间是一个由四棱锥面和球面包围的区域内。从一个网格进入相邻网格时,每个网格单元中取最小代价结点作为搜索空间的待选结点,所有可行的结点不超过9个,大大缩小了搜索空间的规模。
2.航迹距离约束。航迹距离约束对应于被计算航迹的最大允许长度,它代表了某一特定任务燃料的负荷或到达时间上的限制。搜索过程中长度大于这个距离(记为 )的航迹被认为是无效航迹,将不做考虑,予以剔除。例如一个当前结点,只有满足 时才把
加入到可能的航迹结点。这里 是从起始位置到经过的真实距离,
是从到目标点的直线距离,它小于或等于实际要经过的航迹长度。
3.飞行高度限制。无人机规划出来的航迹要尽可能避开障碍,谨慎的通过敌方防御区域。而实际飞行时被敌方探测器发现或被地面防御系统摧毁的概率随高度的增加而增加,而飞得过低往往会使得与地面相撞的坠毁概率增加。因此,要在减少坠毁概率的高飞和减少地面防御系统摧毁概率的低飞之间进行折衷。在特定的任务中,可以根据任务要求限定航线离地高度的最小值。
(三)地形的平滑
传统的航迹算法是在对整个数字地图进行平滑处理的基础上进行航迹规划的。这里把对数字地图的地形平滑处理融合到航迹选择的过程中,在计算航迹代价函数之前,对open表中的有效结点和当前航迹点按其连接的方向进行平滑,然后计算航迹代价函数。这样使得平滑处理只需要满足从当前航迹点到选择结点方向的飞行约束条件,降低了对地形平滑约束要求,能够使无人机飞行的航迹更加贴近地形。
考虑到无人机的纵向机动能力受到最大航迹爬升角的限制,可以将其转化为对地形坡度的限制[5]。设a,b为数字地图上相邻的两点,其高度分别为 和 ,其水平距离为。它们的连线和地平面之间的角度为 ,则:
考虑到低空突防的无人机会受到最大法向加速度的限制[5]。其在垂直平面内的运动轨迹的曲率 和法向加速度 有如下关系:
可将无人机的法向过载限制转化为对地形曲率的限制。设等效地形高程图函数为 ,沿ab方向的曲率为:
求出栅格点 的右曲率 。若,则曲线在栅格点处凹,需要减小栅格点处的右曲率至,增加点 的高度:
若 ,则曲线在栅格点处凸,需要增大栅格点处的右曲率至,增加点 的高度:
在栅格点左边的曲率平滑算法原理同上。
(四)算法流程
利用open表保存待扩展结点,closed表保存已扩展结点。
1.设置初始结点,目标结点,将初始结点插入open表中,将closed表置空。
2.若open表为空,则算法失败,可通过调节结点扩展的方式来重新进行搜索。
3.对open表中的结点按代价从小到大进行排列,从open表中移出排在第一位的点作为当前结点,将它从open表中删除放入closed表中。
4.判断当前结点是否为目标结点,若是则航迹规划结束。从最后计算的位置开始向上回溯直到起始位置,即可得到从起始到目标的最小代价航迹。
5.若当前结点不是目标结点,对当前结点进行后继结点的扩展:构造扩展空间,当前位置的待扩展区域的水平剖面大小为最大拐弯角的两倍,并以进入当前节点航线在水平面上投影的方向为对称轴。垂直剖面大小为最大爬升/下滑角的两倍,关于水平方向对称。待扩展区半径长度为最小步长,将在该区域每个网格单元中取最小代价结点作为搜索空间的待选结点,当前结点共产生9个后继结点。
6.对每一个后继结点进行判断:(1)若open,则称该结点为old,比较同一结点新老路径的代价值,如果生成的结点new的代价值小于open表中old的代价值,则更新open表中的代价值,取较小的代价值作为该后继结点 的代价;若closed,则称该结点为old,比较同一结点新老路径的代价值,如果生成的结点new的代价值小于closed表中old的代价值,则更新closed表中的代价值,取较小的代价值作为该后继结点 的代价;若open&closed,则计算该点的代价值;(2)判断扩展出的后继结点是否满足最大距离约束( )和飞行高度约束(每一点离地高度),若满足则执行下一步。
7.对当前结点和其有效后继结点间的地形进行平滑处理,把结点插入到open表中,返回第三步。
二、仿真实验
实验使用128×128的数字地形高程图和模拟生成的威胁数据采用上述算法进行仿真实验,使用VisualC++6.0编程环境实现,将航迹在Matlab中显示出来。仿真中,规划的初始结点坐标为(1,1,30),目标结点坐标为(110,120,450),如图1。
在相同实验条件下选取完全一样的参数对传统的A*算法和优化的A*算法进行航迹的仿真。表1给出了两种方法结果的比较。
三、结论
本文提出的改进A*算法结合变权分析思想,建立动态权值启发函数进行航迹规划。引入动态权值,通过在规划的不同阶段,赋予不同的权值进行航迹搜索,能够显著提高算法的搜索效率。当无人机面对广泛的战场环境进行航迹规划时,采用此算法的效率较高。
参考文献:
[1]闵昌万,飞行器航迹规划与轨迹控制研究[D].西北工业大学博士论文,1999.
[2]尼尔森(Nilsson,J.N.)著,郑扣根、庄越挺译,人工智能,北京:机械工业出版社,2000.
[关键词]航迹规划 三维航迹 改进A*算法
中图分类号:TP2文献标识码:A文章编号:1671-7597(2009)0810017-02
一、基于改进A*算法的无人机三维航迹规划
(一)算法描述
在A*算法中,恰当的启发函数可以高效率的找到最优路径,动态权值是一种提高启发式搜索算法效率的有效方法。传统的A*算法代价函数为:
,在代价函数中启发函数的参数是一个常值。针对无人机航迹规划搜索的需要,结合变权分析思想,采用动态权值的方法对A*算法进行优化,通过对搜索初、后期赋予启发函数不同的权值来实现,将算法的代价函数改进为:
式中:表示由起始点到当前结点的实际代价值;
表示由当前结点到目标点的实际代价估计值。
采用由当前结点与目标结点之间的直线距离作为启发函数:
其中: 为保证能够搜索到目标的最小权值, 为一次搜索的节点数。从而在搜索初期当无人机距离目标较远时,值较大,以速度优先,保证规划可以快速的收敛到一个与目标接近的范围内;在搜索后期接近目标时
值接近1,以准确度优先,保证当无人机接近目标时减少搜索的盲目性。
(二)三维空间航迹结点扩展
通过适当的网格对规划空间进行合理的划分是实施A*算法的基础[3],网格大小由约束条件来确定。将无人机的性能约束[4]与规划空间的划分结合起来,是缩小搜索空间的有效方式,从而能够有效的减小扩展的结点数量。具体的结点扩展方法如下:
1.最小步长,最大拐弯角和最大爬升/俯冲角约束。在三维航迹规划空间中,每一个网格取做一小立方体,边长为其最小步长。当无人机从一个网格进入相邻网格时,可在最大拐弯角、最大爬升/俯冲角的范围内选择下一个可行航向。设定上升和下降时与水平方向的夹角不超过45度,这样无人机的飞行限制在向前的九个方向,实际上当前结点的可搜索空间是一个由四棱锥面和球面包围的区域内。从一个网格进入相邻网格时,每个网格单元中取最小代价结点作为搜索空间的待选结点,所有可行的结点不超过9个,大大缩小了搜索空间的规模。
2.航迹距离约束。航迹距离约束对应于被计算航迹的最大允许长度,它代表了某一特定任务燃料的负荷或到达时间上的限制。搜索过程中长度大于这个距离(记为 )的航迹被认为是无效航迹,将不做考虑,予以剔除。例如一个当前结点,只有满足 时才把
加入到可能的航迹结点。这里 是从起始位置到经过的真实距离,
是从到目标点的直线距离,它小于或等于实际要经过的航迹长度。
3.飞行高度限制。无人机规划出来的航迹要尽可能避开障碍,谨慎的通过敌方防御区域。而实际飞行时被敌方探测器发现或被地面防御系统摧毁的概率随高度的增加而增加,而飞得过低往往会使得与地面相撞的坠毁概率增加。因此,要在减少坠毁概率的高飞和减少地面防御系统摧毁概率的低飞之间进行折衷。在特定的任务中,可以根据任务要求限定航线离地高度的最小值。
(三)地形的平滑
传统的航迹算法是在对整个数字地图进行平滑处理的基础上进行航迹规划的。这里把对数字地图的地形平滑处理融合到航迹选择的过程中,在计算航迹代价函数之前,对open表中的有效结点和当前航迹点按其连接的方向进行平滑,然后计算航迹代价函数。这样使得平滑处理只需要满足从当前航迹点到选择结点方向的飞行约束条件,降低了对地形平滑约束要求,能够使无人机飞行的航迹更加贴近地形。
考虑到无人机的纵向机动能力受到最大航迹爬升角的限制,可以将其转化为对地形坡度的限制[5]。设a,b为数字地图上相邻的两点,其高度分别为 和 ,其水平距离为。它们的连线和地平面之间的角度为 ,则:
考虑到低空突防的无人机会受到最大法向加速度的限制[5]。其在垂直平面内的运动轨迹的曲率 和法向加速度 有如下关系:
可将无人机的法向过载限制转化为对地形曲率的限制。设等效地形高程图函数为 ,沿ab方向的曲率为:
求出栅格点 的右曲率 。若,则曲线在栅格点处凹,需要减小栅格点处的右曲率至,增加点 的高度:
若 ,则曲线在栅格点处凸,需要增大栅格点处的右曲率至,增加点 的高度:
在栅格点左边的曲率平滑算法原理同上。
(四)算法流程
利用open表保存待扩展结点,closed表保存已扩展结点。
1.设置初始结点,目标结点,将初始结点插入open表中,将closed表置空。
2.若open表为空,则算法失败,可通过调节结点扩展的方式来重新进行搜索。
3.对open表中的结点按代价从小到大进行排列,从open表中移出排在第一位的点作为当前结点,将它从open表中删除放入closed表中。
4.判断当前结点是否为目标结点,若是则航迹规划结束。从最后计算的位置开始向上回溯直到起始位置,即可得到从起始到目标的最小代价航迹。
5.若当前结点不是目标结点,对当前结点进行后继结点的扩展:构造扩展空间,当前位置的待扩展区域的水平剖面大小为最大拐弯角的两倍,并以进入当前节点航线在水平面上投影的方向为对称轴。垂直剖面大小为最大爬升/下滑角的两倍,关于水平方向对称。待扩展区半径长度为最小步长,将在该区域每个网格单元中取最小代价结点作为搜索空间的待选结点,当前结点共产生9个后继结点。
6.对每一个后继结点进行判断:(1)若open,则称该结点为old,比较同一结点新老路径的代价值,如果生成的结点new的代价值小于open表中old的代价值,则更新open表中的代价值,取较小的代价值作为该后继结点 的代价;若closed,则称该结点为old,比较同一结点新老路径的代价值,如果生成的结点new的代价值小于closed表中old的代价值,则更新closed表中的代价值,取较小的代价值作为该后继结点 的代价;若open&closed,则计算该点的代价值;(2)判断扩展出的后继结点是否满足最大距离约束( )和飞行高度约束(每一点离地高度),若满足则执行下一步。
7.对当前结点和其有效后继结点间的地形进行平滑处理,把结点插入到open表中,返回第三步。
二、仿真实验
实验使用128×128的数字地形高程图和模拟生成的威胁数据采用上述算法进行仿真实验,使用VisualC++6.0编程环境实现,将航迹在Matlab中显示出来。仿真中,规划的初始结点坐标为(1,1,30),目标结点坐标为(110,120,450),如图1。
在相同实验条件下选取完全一样的参数对传统的A*算法和优化的A*算法进行航迹的仿真。表1给出了两种方法结果的比较。
三、结论
本文提出的改进A*算法结合变权分析思想,建立动态权值启发函数进行航迹规划。引入动态权值,通过在规划的不同阶段,赋予不同的权值进行航迹搜索,能够显著提高算法的搜索效率。当无人机面对广泛的战场环境进行航迹规划时,采用此算法的效率较高。
参考文献:
[1]闵昌万,飞行器航迹规划与轨迹控制研究[D].西北工业大学博士论文,1999.
[2]尼尔森(Nilsson,J.N.)著,郑扣根、庄越挺译,人工智能,北京:机械工业出版社,2000.