一种改进的启发式算法根据路径规划

文摘

研究无人作战飞行器(UCAV)路径规划是在军用和民用领域越来越重要。本文提出了一种新的数学模型和一种改进的基于稀疏的启发式算法搜索(SAS)作战无人机路径规划问题。摘要飞行约束条件将被视为满足飞行限制和任务的要求。有三个模拟,模型算法的影响将会调查,有效性和优势的模型和算法进行验证。

1。介绍

如今,无人作战飞行器(UCAV)长期以来一直是具有挑战性的军用和民用领域的研究人员。路径规划被定义为寻找最优路径的移动对象从起始点到目标点在特定约束(包括环境约束和运动约束)1]。路径规划的目标是找到路径与存活率最高,降低损失,较短的一段时间。目前,路径规划问题已广泛应用于不同的领域,如巡航导弹,直升机和无人作战。在现代战争中,随着各种防空技术的发展,毫无疑问,路径规划问题是越来越多的被关注在军事领域。很多学者不断研究的路径规划问题。无人的代表技术路径规划就像PSO (1,2),动态规划(3),算法(4,5],蚁群算法[6)、遗传算法(7,8],等等9- - - - - -13]。文献[14]讨论了稀疏算法,另一个有效的方法,从而大大提高了搜索的效率,但很容易陷入一个死循环的情况下缺乏机动能力。文献[5采用稀疏算法,但角启发式函数不考虑约束条件的数目很小;仿真结果不科学。文献[7,15]提出了大量的算法计算,使得算法不适合寻求优化的解决方案。要解决这些问题,一种改进的启发式算法16)进行了研究,考虑了角信息在一定范围内,采用两种轨迹平滑的矫直方法处理和比较,并给出相应的仿真。

2。相关的工作

2.1。基本的数学模型

无人的路径规划问题可以建模为一个约束优化问题。之前搜索跟踪、飞行条件和元素(如地形、威胁、气候等)的相关路径规划表示为符号信息。

让经度,纬度和高度状态空间的某一点。路径规划的空间可以表示为一组:,代表一个空间。在实际规划,规划空间分为二维网格或三维网格;一系列的节点获得和内置网络图,如图1。路径规划问题可以简单地归结为一个组合优化问题获得网络的最短路径图。也就是说,当无人飞行路径由一些节点的网络图,一种特定的路径花费最小的代价。

假设一组网络图的节点形式

定义一组,包括所有路径从起点到终点:

让和是两个相邻节点的路径,两个节点之间的连接线可以表达的的成本价值可以表示两个节点之间的连接线,无人的路径规划问题定义如下:

从上面的内容可以看出,无人战斗机的性能约束并不反映在计划。网络图中的节点是否可行点考虑无人战斗机的性能约束,无人战斗机的性能约束的路径可以从解决反映上述优化问题。这是一个新的数学模型。相比之下,(5),我们的新数学模型考虑了更多的约束。和仿真结果表明,它是非常有用的近似最优解。除此之外,还擅长在复杂条件下加工路径规划。

2.2。路径规划的基本约束条件

有许多因素影响路径规划的结果。这些因素包括地形特征,威胁的地点,和任务需求,在数学建模的基本约束。路径规划应满足基本约束,主要包括下列约束(4]。

最小路径长度。飞机一般不希望编织,并将不断,因为这增加了燃料成本和增加导航错误。

最大转向角。飞机的转弯角度不超过最大转向角。例如,飞机不能严重碰撞形成对抗的风险更大。

路线距离约束。路线的长度不超过最大距离因为燃料的限制。

特定的接近角到目标点。这都限制了UCAV接近敌方飞机从一个预先确定的角度,以确保无人防守薄弱的部分。

2.3。路径规划的成本

在满足一些约束的前提下,根据路径规划旨在生成轨迹存活率最高。因此,在战场威胁地点应充分考虑。威胁因素和燃料限制主要是考虑在计算轨迹成本。

2.3.1。模型的威胁

威胁模型的雷达。影响雷达检测概率的因素主要包括地球曲率,大气折射和吸收,地面杂波干扰,距离飞机和雷达,雷达截面,雷达的性能,和地面多路径效应。为了简化,我们主要采取的距离飞机雷达和雷达性能考虑。假设飞行高度飞机雷达的水平距离、雷达最大水平范围、雷达性能系数,显示的雷达检测概率模型可以如下: 如果,近似表达式可以等效如下: 如果,飞机在雷达的探测距离,和威胁模型可以简化如下: 使用公式(5)的近似表达式 如果飞机的雷达最大水平范围内,对雷达威胁飞机是零。威胁模型的雷达可以表示如下:

地对空导弹的威胁模型。假设导弹目标的概率分布服从泊松分布水平距离,造成的概率最大的攻击半径是,如果飞机,导弹威胁模型可以给出如下: 根据公式(5),可以等效近似表达式如下: 如果飞机的最大的攻击半径范围内,导弹对飞机的威胁是零。导弹的威胁模型可以给出如下:

威胁的地形模型。由地形引起的主要危险是山峰,这可能是一个障碍的飞行时,飞机飞行在固定的高度。和山峰可以表示为锥。假设峰值的横截面是一个飞行高度和半径的圆周周长峰的中心位置,飞机的当前位置的水平距离从飞机到中央的峰值可以表示如下: 与以上几种威胁,飞机和峰值之间的碰撞是致命的飞机的风险。因此,必须保持足够的空间和时间,当飞机越过高峰。山峰的威胁模型可以给出如下:

恶劣气候的威胁模型。类似于峰值对飞机的威胁,假设半径横截面上的恶劣气候和水平距离飞机恶劣天气的中心,恶劣气候的数学模型可以给出如下:

2.3.2。路径规划成本核算功能

在这篇文章中,成本计算成本和燃料成本函数与威胁。因为燃料成本成正比航行中,函数可以作为成本计算 在哪里是总成本的路线,是th路线成本,是th路线长度,它可以降低敌人的防空系统范围内的飞机飞行时间减少路线的总长度,的威胁指数吗th路线,它确保飞机能飞在安全的区域,和和是距离因素和威胁因素的权重系数,然后呢。此外,他们可以根据特定需求的路由性能。例如,有时我们需要最低的路线,有时最高的存活率是必需的。

的威胁指数计算线路需要集成th路线,为了简化,计算平均值的威胁指数的某些点的路线,然后乘以影响部分的长度。把线路分成相等的部分,选择破发点的路由上,他们的立场可以表示为 威胁指数上路线是由表达式 在哪里是已知的威胁源的数量,是th路线长度,破发点的威胁值,值吗可以根据计算准确性和路线调整长度。根据不同分类的威胁,它可以通过公式计算(8);(11);(13);(14)。

2.4。稀疏的算法

启发式搜索(17)旨在利用启发式信息来找到最优路径的最低成本。启发式搜索和其他方法之间的主要区别是,成本信息与启发式信息。给出了启发式搜索的成本核算功能 在哪里扩展的节点,是实际的成本从开始节点扩展节点,然后呢估计成本的扩展节点到目标节点。根据不同的任务要求,启发式信息可能涉及许多因素如地面威胁来源,人工障碍,飞行时间,和燃料数量。一个合适的启发式函数可以大大提高搜索速度和获取容易的解决方案。

要解决的主要问题是如何获取候选节点集在搜索过程。在状态空间表达式的节点可以分为两种类型:网格节点图形表达和节点的表达式。前者扩展节点射线的形式;后者将状态空间划分为网格有一定规模,然后扩展了相邻网格指出。例如,基本基于网格搜索。在启发式搜索节点可以分为三种状态:(1)节点扩展。(2)节点生成但没有延长。(3)节点还没有生成。

第一种节点称为关闭节点,我们可以构建一个表命名关闭存储这种节点;第二种节点称为开放节点,因为节点生成但没有扩展,这样的节点可以被存储在一个表命名开放。开始节点存储在开放表在初始搜索。新节点可以根据不同的生成可扩展规则,然后这些新节点插入开放表的增量成本价值与最小值,节点可以优先扩展,它可以存储在关闭表。

3所示。基于稀疏的路径规划方法搜索算法

3.1。稀疏的基于约束的路径规划算法

Szczerba等人提供了一个先进的基本版本2000年搜索算法叫做SAS(稀疏搜索)。传统的算法的基础上设计了网格搜索。例如,在图2,定义作为当前节点和为扩展节点。八邻域子节点时考虑扩展节点。此外,我们还可以考虑更多的邻居节点扩展节点。但是,一般来说,更大的社区对应于更复杂的路线,更大的内存空间,不再收敛时间。由于节点只能扩展到八个固定方向,生成的路径可能无法满足约束的路径规划中引入部分2.2。

SAS (5等)可以把约束最小的一步,最大转向角,和最大路径搜索算法,有效凝聚的搜索空间。SAS不仅提高了搜索效率,而且满足飞行约束条件。在下一节中,我们将介绍如何结合飞行约束条件的过程扩展的节点。我们还将讨论如何设置一个合理的成本函数。

3.2。可扩展节点的规则

让最小的一步,最大转向角。基于已知的电流方向节点,当前节点的搜索是有限的和一系列的扇形区域。扇形区域的内侧轴电流的方向节点。然后,扇形区域分为相等的部分,结向量之间的距离是每个的成本计算部分和当前节点。为了节省空间,加快收敛速度,只有每个部门的节点以最低的成本是保留。如图3,扇形区域分为三个相等的部分:,,代表节点与每个扇形区域的最低成本,分别。集根据不同的精度要求和收敛速度,节点的数目应该小于。重复这个过程,当扩展节点。删除节点的最小成本开放表,然后将该节点定义为当前节点和当前节点插入关闭表。扩展当前的节点,然后将所有子节点插入开放表的增量成本价值。

路线距离的约束是允许的最大长度的路线代表燃料和到达时间的有效载荷约束在一个特定的任务。路线的长度超过最大距离()称为无效的路线。在上述讨论的基础上,以最低的成本获取节点插入开放表,定义当前节点,我们需要做出判断的另一个条件如下: 在哪里是实际的开始点和当前点之间的距离,是当前节点和目标点之间的直线距离,通常是几次的价值直线起始点到目标点之间的距离。如果当前节点满足上述需求,它可以扩展;否则会被丢弃。这种方法不仅可以满足飞行限制也产生直接的有效途径。

3.3。轨迹成本函数

在上述讨论的基础上,启发式搜索的成本函数可以表示为。实际的成本函数可以通过公式计算(15),在这里,我们讨论的计算。

的基本启发式函数采用曼哈顿距离显示当前节点到目标节点的距离: 在哪里当前节点的坐标吗目标节点的坐标。考虑目标接近角的限制,飞机将达到目标在一个固定的方向。角信息是考虑在设计成本函数。当前的课程和课程目标之间的偏差是用于指导搜索过程在预定的方向。成本函数(1)添加了角信息可以表示如下: 在哪里是距离启发式函数可以计算公式(20.),是角启发式函数可以计算公式(22),和是启发式的距离和角度启发式的权重系数,分别和。在公式(22),,线的方向,当前节点和目标节点和连接吗是预定的目标接近角。假设,,,规范如下:

在传统的搜索方法,路径可能过早地倾向于预定目标方向,这样生成的路径可能不是最短路径。只有当飞机接近目标可以飞机向预定目标方向的长途飞行,没有必要一直角进行启发式在整个搜索过程。在拟议的方法,启发式函数考虑角度信息。让半径,仿真步长,是系数范围。半径的大小可以调整根据机动能力和仿真步长。飞机应该能够及时把预定的方向在这个范围内。如果节点是在这个范围内,启发式函数是用来计算成本;否则启发式函数使用。该方法不仅能使飞机接近预定的目标方向,还得到一个近似最优解。在sa算法,计算路线成本可以表示如下: 在哪里之间的距离是和目标节点和是实际的成本价值。产生的成本价值可以通过公式计算距离和威胁(15)。

在上述讨论的基础上,是非常重要的,找到一个合理的启发式函数获得一个没有减少搜索速度的近似最优解。同样重要的是要设计相应的适合不同阶段的启发式函数跟踪搜索。

3.4。轨迹平滑矫直加工

3.4.1。方法1

从上面的描述,路径规划系统的最终目标是生成一组跟踪点数据,然后提供这些数据飞行任务管理器。因此,最初的路线通过搜索算法需要处理,以获得更小的数量的跟踪点。跟踪点位于起始点和目标点之间的路径表中存储。设置起始点作为当前点,遍历路径表中其他节点根据当前点到下一个点的顺序。检查连接是否当前节点和一个特定的访问节点会遇到的威胁。如果连接的当前节点和一个特定的访问节点遇到威胁时,回到前面的节点,将前面的节点作为当前节点,删除所有节点当前节点和最后一个当前节点之间,经常注意更新信息,从当前节点retraverse直到到达目标节点。否则继续遍历,重复以上步骤。

3.4.2。方法2

下面的方法是在搜索优化的过程。如图4,让当前节点,当前节点的父节点,是祖先节点,和他们的成本值,,,分别。在当前节点扩展的计划开放表关闭从当前节点表,计算路线成本祖先节点和成本的路线;从节点路由成本它的父节点是;成本从父亲节点的路线祖先节点是。判断他们的关系,如果,表示从当前节点的祖先节点连接的成本比从当前节点的父节点。因此,设置当前节点为父节点的祖先节点和调整其成本价值。

路线从上面的方法不仅可以获得降低路由成本也限制的数量。此外,有效信息的跟踪点可以生成支持未来的导航。

4所示。实验研究

路径规划的范围定义为和仿真步长和最小路径长度5公里。距离系数和威胁系数定义为和分别在计算实际成本;距离系数和角系数定义为和分别计算启发式函数时需要考虑的角度信息。最大约束路由距离是1.5倍起始点和目标点之间的直线距离。让角启发式系数范围5、最大转向角是60,3当扩展节点。(1)假设起始点的坐标目标点的坐标。威胁分布如图5,图中展示了路径规划的结果5。(2)假设起始点的坐标目标点的坐标。威胁分布和路径规划的结果如图所示6。第二种方法(见部分3.4.2)是在考虑路线处理和路径规划的结果可以如图所示7。(3)假设起始点的坐标目标点的坐标。威胁分布如图8和路径规划的结果如图所示8。第一种方法(见部分3.4.1)是在考虑路线处理和路径规划的结果可以如图所示8。

5。结论

本文提出一种改进的启发式算法是一种改进的版本的SAS UCAV路径规划算法。算法考虑不仅传统约束的路径规划,而且各种飞行约束条件,如角信息,跟踪平滑矫直处理,等等。相比之下,(5),仿真结果表明,角信息和轨迹平滑矫直加工是明智的,有效的,可行的。此外,该算法不仅能使飞机接近预定的目标方向,还得到一个近似最优解。和我们的改进算法减少扩展节点在复杂条件和运行效率要好得多。除此之外,一些模拟表明,我们提出的新模型和算法能够满足飞行作战无人机路径规划和任务需求的限制。

的利益冲突

作者宣称没有利益冲突。

确认

这个经济研究是由中国国家自然科学基金(61401363),科学和技术在航空电子设备集成实验室和航空科学基金(20155153034)和中央大学的基础研究基金(3102016 axxx005, 3102016 bjjgz009)。

引用

1. w ., a·h·朱和h . d .粉丝,“应用改进的粒子群优化算法在UCAV路径规划,“计算机工程34卷,第180 - 178页,2008年。视图:谷歌学术搜索
2. y张、吴l .和美国,“无人fitness-scaling自适应混沌粒子群优化的路径规划,“数学问题在工程ID 705238条,卷。2013年,9页,2013。视图:谷歌学术搜索|MathSciNet
3. 周x c j·g·严,r·陈”无人团队的合作路径动态规划模型基于全局优化方法,”电子科学与技术杂志》上,10卷,不。4、363 - 367年,2012页。视图:谷歌学术搜索
4. f·j·c·w·郑l . Li, f . c .太阳和m . y .叮“无人驾驶飞行器,进化路线规划”IEEE机器人,21卷,不。4、609 - 620年,2005页。视图:出版商的网站|谷歌学术搜索
5. 陈,c·w·刘,z . p .黄g s Cai,“全球对AUV的路径规划基于稀疏A *搜索算法,”鱼雷技术,20卷,不。4、271 - 274年,2012页。视图:谷歌学术搜索
6. y . p .他张a, h . y . Liu”路径规划为UCAV泰森多边形法图和蚁群优化的基础上,“电子光学和控制,16卷,不。11日,22 - 24,2009页。视图:谷歌学术搜索
7. x和z . c . Wang j . Wang Jing,“基于遗传算法的多路径路由,”计算机工程,37卷,不。20日,第199 - 197页,2011年。视图:谷歌学术搜索
8. Z.-J。徐和s .唐”飞行路径规划基于改进遗传算法”,《航天卷,29号5,1540 - 1545年,2008页。视图:谷歌学术搜索
9. j·f·刘,g·李和h . t .耿”一种新的启发式算法的循环平衡约束、包装问题”中国科学。信息科学,54卷,不。8,1572 - 1584年,2011页。视图:出版商的网站|谷歌学术搜索|MathSciNet
10. y, j·陈,l .沈,“混合分层轨迹规划的固定翼无人执行空对地多目标攻击,”系统工程与电子技术》杂志上,23卷,不。4、536 - 552年,2012页。视图:出版商的网站|谷歌学术搜索
11. h .段张x, y Yu和邵,“三维路径规划无人使用混合meta-heuristic ACO-DE算法,”仿真建模实践和理论,18卷,不。8,1104 - 1115年,2010页。视图:出版商的网站|谷歌学术搜索
12. g . Wang l .郭h .段l . Liu h . Wang和j·王,“混合meta-heuristic DE / CS UCAV路径规划算法,”信息与计算科学杂志》上,9卷,不。16,4811 - 4818年,2012页。视图:谷歌学术搜索
13. j . b .元,f, g . y, y .梁,“导航方法及其模拟无人机编队飞行,”计算机模拟,28卷,不。11日,第67 - 64页,2011年。视图:谷歌学术搜索
14. r . j . Szczerba p . Galkowski i s Glickstein和n . Ternullo“健壮的实时路径规划的算法,IEEE航空航天和电子系统,36卷,不。3、869 - 878年,2000页。视图:出版商的网站|谷歌学术搜索
15. g . Wang l .郭h .段l . Liu h . Wang和m .邵”对无人作战飞行器路径规划使用混合meta-heuristic DE /偏硼酸钡算法,”先进的科学、工程和医学,4卷,不。6,550 - 564年,2012页。视图:出版商的网站|谷歌学术搜索
16. w·r·k, p . p . Liu, j .邹和m .刘”作战无人机路径规划的改进启发式算法,”学报》第11届国际会议上仿生计算理论和应用程序页54-59 Springer,西安,中国,2016年10月。视图:谷歌学术搜索
17. b·黄和y . m .太阳,“改进方法调度柔性制造系统基于Petri网和启发式搜索,“《控制理论与应用,3卷,不。2、139 - 144年,2005页。视图:出版商的网站|谷歌学术搜索|MathSciNet

版权

版权©2017库恩Zhang et al。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。