郑州做网站zzmshl,广州微网站建设dmz100,wordpress 4.4.1下载,电商运营推广怎么做基于遗传算法的无人机监视覆盖航路规划算法研究
人工智能技术与咨询 点击蓝字 关注我们 来源#xff1a;《 计算机科学与应用》 #xff0c;作者 李御驰等 关键词: 人工势场法#xff1b;无人机#xff1b;监视覆盖航路规划 摘要#xff1a; 摘要: 为解决传统覆盖航路规…基于遗传算法的无人机监视覆盖航路规划算法研究
人工智能技术与咨询 点击蓝字 · 关注我们 来源《 计算机科学与应用》 作者 李御驰等 关键词: 人工势场法无人机监视覆盖航路规划 摘要 摘要: 为解决传统覆盖航路规划算法结果样式单一、对抗性环境下灵活性差的问题提出了基于遗传算法的监视覆盖航路规划算法生成样式多样、监视任务执行中对抗性好的监视覆盖航路。在人工势场法的基础上将激发势场的种子编码为二元组串形式的基因通过交叉、变异、合并等算子的操作增加种子样式的多样性从而规划出转弯少、监视时间间隔短、对抗性好的监视覆盖航路。最后通过算例对算法进行了验证结果表明算法有效地满足了监视任务覆盖航路规划的需求。
1. 引言
无人机航路规划是指在特定约束条件下寻找从起始点到目标点并满足无人机性能指标的最优或可行的航路。而覆盖航路规划的任务是确定一条路径该路径通过感兴趣的区域所有点同时避免障碍。经过查阅文献发现由于无人机受到任务区域和性能的约束关于监视覆盖航路规划的研究较少大多是关于地面机器人覆盖航路规划的研究。
A. Zelinsky等 [1] 提出了第一种基于网格的覆盖路径规划方法。他们使用网格表示任务区域并对网格应用完整的覆盖路径规划算法。该方法设定一个起始单元格和一个目标单元格。算法首先给目标网格赋值0给它周围的所有单元格赋值1。然后所有与标记1相邻的未标记网格都标记为2。这个过程不断重复直到标记面到达开始单元格。经过计算距离转换通过从开始单元格开始选择未访问的赋值最高的相邻单元格来找到覆盖路径。如果两个或两个以上的邻居单元格为相同的值则随机选择其中一个单元格。
H. Choset等 [2] 提出了一种能够产生完整覆盖路径的简单精确的网格分解技术。他们将任务区域划分成每个网格为梯形的工作空间并且只处理平面的多边形区域。使用简单的来回运动来覆盖每个单元网格通过查找与分解相关的邻接网格进行穷举遍历来保证完全覆盖任务区域详尽的前进规则决定了访问单元格的顺序最后生成覆盖每个单元格的特定“之”字形路径。
陈海等 [3] 证明了同等能量下无人机转弯过程比直线飞行过程效率低定义了凸多边形任务区域的长度和宽度并将凸多边形区域的覆盖航迹规划问题转化为求解凸多边形宽度的问题。他们按照“点边式”宽度算法找到凸多边形宽度出现时支撑平行线的方向如果无人机沿该方向利用扫描线对区域进行扫描覆盖则可以获得最少的转弯次数也就能够得到最短的飞行路程。但在地形起伏大的任务区域需要加入地形高程等约束进行三维航路规划。
覆盖航路规划问题在机器人领域 [4] [5] [6] 有较大的研究。但是如果将这些方法应用于监视飞行器的覆盖路径生成则在一次覆盖后其对手可以很容易地掌握这些路径的规律性不能满足监视任务的不可预测性和覆盖任务目标的频繁性要求。基于此我们提出了基于遗传算法规划监视覆盖航路。
2. 监视覆盖航路规划问题建模
2.1. 任务区域网格化
规划监视覆盖航路时必须考虑到无人机执行任务的区域简单易行的任务区域划分可以极大方便覆盖航路生成所以我们把任务区域网格化。网格化就是要将任务区域划分为规则的网格网格的大小由无人机监视器视场在地面的投影大小决定。那么任务区域就可以使用网格的集合来表示了设为A。网格要小于这个投影区域的大小但又要尽可能的大。若无人机的飞行高度为h垂直视场角为 αα 水平视场角为 λλ 俯视角为 ββ 。假设在地面的视场为梯形ABCD如图1所示 N,K,FN,K,F 分别为边 AB,PQ,CDAB,PQ,CD 的中点OK为 ∠NOF∠NOF 的角平分线。则网格的边长最大可以为 PQ2OKtanλ/2PQ2OKtanλ/2 Figure 1. UAV surveillance field of view 图1. 无人机监视视场
2.2. 人工势场法生成覆盖航路
人工势场法 [7] 就是为任务区域设定一个虚拟的人工势场每个网格上设定一个数字代表网格的势值。覆盖航路规划算法从一个起始的网格出发按照一定的规则沿着势场运动最终会形成一个覆盖航路。覆盖航路的生成样式和势场值的设置以及运动规则密切相关不同的势场值设置方法以及规则生成的覆盖航路不同。 传统的基于人工势场的覆盖航路生成方法是在两个点之间按照势值递增的趋势生成势场然后依据势场生成航路算法在避障以及覆盖效率方面有不错的效果但是生成的样式比较单一。为了丰富势场的样式我们将势场生成的起始态势进行了改进并将这种起始的态势成为种子。 所谓种子就是在势场生成算法开始的时候设定的一个势值不为0的网格的集合设为 S⊂AS⊂A 。传统的人工势场法中种子S只包含一个网格。基于种子概念的人工势场法生成覆盖航路的过程如下 步骤1选择任务区域网格集合的一个子集作为种子S并设其网格的势值均为1其他网格的势值为0 步骤2并行地更新势值为0的网格的势值从其邻居网格中选择势值最大的网格作为激发格并设当前网格的势值为激发格势值 1 步骤3重复运行步骤2直到所有的网格势值均为非零转步骤4 步骤4无人机从起始网格出发移动向势值最小的邻居网格并将起始网格标记为已覆盖 步骤5无人机不停地向势值最小的未覆盖的邻居网格移动。
2.3. 监视覆盖航路的目标函数
根据无人机监视任务的性质监视覆盖航路的优劣主要取决于覆盖航路实际执行的效率和效果也就是要更快、更频繁、更不可预测地完成对任务区域的覆盖监视落到具体航路的评价上就要求航路的转弯(次数、角度)要少、对单个网格的监视间隔要小、航路变换多样。因此监视覆盖航路规划的目标函数主要有以下几个 1) 转弯角度总值最小 每个转弯通常意味着无人机在转弯后再次减速并再次加速的额外成本所以要减少最小化路径中的转弯(次数、角度)来增加监视的效率。这里我们采用统计航路中所有拐弯角度总和的办法来度量航路的这一个性能并将这个总和称为拐弯角度总值 其中 qiqi 为航路上第i个转弯的角度拐弯角度总值越小的航路越有利于增加监视效率。 2) 网格上的势的总值及标准差最小化 为了反映对网格监视间隔的大小我们提出了一种势值动态增加的机制也就是在计算推进的过程中所有网格的势值也在同步增加但是刚刚覆盖过的网格的势值清零这样在计算过程中网格的势值就与监视间隔的大小成正比如果网格监视间隔时间大则网格势值的增加就多。这样就可以用网格的动态势值来评价对网格监视间隔。为了对航路有一个总体评价我们利用任务区域网格势值的总值、标准差来评价监视覆盖的效率。 其中 wiwi 为网格i的势值。 3) 航路的可预测性要小 监视任务的性质决定了无人机被发现的概率越小越好所以覆盖航路的可预测性至关重要。当覆盖航路越不容易被预测判断时无人机执行任务越不容易被发现任务的成功率和可靠性越高。若覆盖航路被预测出时敌方可根据预测避开无人机或采取措施迷惑无人机导致任务失败。 这里我们简单地利用种子更新的周期来评估可预测性的大小也就是种子更新越频繁覆盖航路样式的变换越频繁航路就越不容易被预测 3. 基于遗传算法的监视覆盖航路规划算法
3.1. 基因编码
普通的基因编码 [8] 以01字符串编码为主但这种编码形式不利于种子的直观表示并且经过交叉变异等操作后经常会产生非可行解。因此我们采用二元组串的形式进行编码每个网格可以对应平面直角坐标系上的一个唯一坐标而种子是网格的集合这样种子就可以编码成一个二元组串的形式。
3.2. 交叉、变异产生新的基因
1) 交叉算子
交叉 [9] [10] 是指通过交换两个个体中的部分基因位产生新的基因。从种群中选取两个个体配对在选定的节点上各截取一部分基因相互交换即产生新的基因组成两个全新的个体。如图2。
2) 变异算子
经过交叉过后的新基因某个或某些基因位会产生变异从而产生一定概率的不可预测性性波动进而增加种群进化的多样性。通过变异不仅可以改善航路规划的随机性使航路的可选择性更加丰富多样通过种子的改变产生下一步进行的更多可能的新的种子。还可以增加算法的局部搜索能力使得路径选择的方向更加广阔在面对新的信息时有更多适合的航路。
对于椭圆形种子的基因变异改变的是椭圆形的形状参数(如位置、长轴与x轴夹角、轴的长短)。如图3。
3) 合并算子
根据本问题的特殊性提出一种新的算子称为合并算子也就是将两个种子基因进行直接合并而生成基因。如图4。 Figure 2. Cross operation
图2. 交叉操作 Figure 3. Variation operation
图3. 变异操作 Figure 4. merge operation
图4. 合并操作
3.3. 监视覆盖航路生成
基于遗传算法的监视覆盖航路生成算法的步骤如下所示 步骤1初始化种子群在种群中选择一个种子在任务区域网格中生成势场无人机位于起始位置 (x0,y0)(x0,y0) t0t0 设定种子更新的周期T。 步骤2仿真步长向前推进 tt1tt1 势场中所有网格的势值增加某个数值p无人机从当前位置移动到势值最大的邻居网格 (x,y)(x,y) 中网格 (x,y)(x,y) 的势值清零。当达到种子更新周期条件的时候对种群进行交叉变异操作并选择一个基因重新生成任务区域网格的势场。 步骤3当生成的覆盖航路时间窗口满足要求的时候停止计算。 4. 仿真实验
为了对算法进行测试我们建立了30*30的任务区域网格每个网格看作图 G(V,E)G(V,E) 中的一个点所有的点构成图G的点集V对于一个网格我们定义其邻居为与其相邻的八个网格映射到图G中就是点之间只有存在邻居关系的时候才有边相连。 对于初始的种群我们选用点型、线型两种典型的人工势场种子编码产生遗传算法的初始种群。设定仿真每向前推进一步所有点的人工势场均增加0.001也就是 p0.001p0.001 种群更新的机制为按照仿真时间进行更新周期为T也就是每向前推进T时间利用算子更新遗传算法的种群并从种群中随机选择一个种子更新当前的势场继续生成航路。 在航路生成的过程中每隔30*30仿真步长统计一次航路的性能参数也就是转弯角度总值、人工势场势总值、网格势场最大值、网格势场值的标准差等参数其中目标函数中的不可预测性认为其与种群更新周期T成反比也就是T越大不可预测性越差反之不可预测性越好极端情况下当T为无穷大的时候不可预测性最差。 初始势场采用点型种子生成如图5所示。 Figure 5. Initial potential field 图5. 初始势场 为了更加连贯和度量一致的观察航路规划算法的统计在达到势场更新周期对势场进行更新的时候要进行一定的处理使得任务网格的总势保持不变也就是假设新的种子生成的势场总值为 P1P1 更新之前的总值为 P0P0 则要将新生成的势场除以一个常数 P1/P0P1/P0 进行了50*900个仿真步长的仿真也就是理想情况下可以对任务区域进行最大50次的覆盖监视得到的结果如图6所示。 从仿真结果来看转弯角度总值分布比较平稳位于111到245之间。势场总值也比较平稳初始几个周期的总势值比较大是因为初始势场生成设置的原因网格势场最大值以及标准差也存在这样的现象。 5. 小结
本文通过结合人工势场法对无人机任务区域生成网格势场在监视覆盖航路的约束条件下将势场 (a) 转弯角度总值(b) 势场总值(c) 网格势场最大值(d) 势场标准差
Figure 6. Analysis of the results
图6. 结果分析
种子编码成二元串组基因后进行算子操作产生更多新的种子增加航路变化的多样性。通过仿真验证算例的转弯角度总值、势场总值、网格势场最大值、势场标准差等结果表明本算法可以满足监视覆盖航路多样性和对抗性的需求。
关注微信公众号人工智能技术与咨询。了解更多咨询
赶紧长按上面图片添加关注! 转发点赞在看安排一下
