• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 30
    • 下载费用:30 金币  

    重庆时时彩高手公式: 一种适用于复杂低空下飞行器的路径规划方法.pdf

    关 键 词:
    一种 适用于 复杂 低空 飞行器 路径 规划 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    摘要
    申请专利号:

    CN201410147792.5

    申请日:

    2014.04.14

    公开号:

    CN103913172A

    公开日:

    2014.07.09

    当前法律状态:

    授权

    有效性:

    有权

    法律详情: 专利权的转移IPC(主分类):G01C 21/20登记生效日:20180212变更事项:专利权人变更前权利人:北京航空航天大学变更后权利人:北京如翼信息技术有限公司变更事项:地址变更前权利人:100191 北京市海淀区学院路37号变更后权利人:100083 北京市海淀区中关村东路1号院3号楼-1-101-127|||授权|||实质审查的生效IPC(主分类):G01C 21/20申请日:20140414|||公开
    IPC分类号: G01C21/20 主分类号: G01C21/20
    申请人: 北京航空航天大学
    发明人: 张学军; 曾捷; 管祥民
    地址: 100191 北京市海淀区学院路37号
    优先权: 2013.12.06 CN 201310651493.0
    专利代理机构: 北京永创新实专利事务所 11121 代理人: 姜荣丽
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201410147792.5

    授权公告号:

    |||||||||

    法律状态公告日:

    2018.03.06|||2016.09.21|||2014.08.06|||2014.07.09

    法律状态类型:

    专利申请权、专利权的转移|||授权|||实质审查的生效|||公开

    摘要

    本发明公开了一种适用于复杂低空下飞行器的路径规划方法,属于飞行管理方法和系统技术领域。所述方法首先建立飞行器路径规划模型;然后采用自适应差分目标进化算法对单架飞行器进行路径规划?;谒龅牡ゼ芊尚衅髀肪豆婊椒?,本发明还提供一种多架飞行器路径规划方法。本发明是一种多机协同进化的冲突解脱方法,运算效率高,能够满足预规划路径的需求;能够满足低空空域自由飞行条件下的单机和多机路径规划需求;具有一定的反馈设置,能够在保证规划路径的安全性的同时也获得较高的飞行效率。

    权利要求书

    权利要求书
    1.  一种适用于复杂低空下飞行器的路径规划方法,其特征在于:假设(1)所有飞行器都在同一高度层以不同速度飞行,且各自在飞行过程中飞行速度不发生改变;(2)每架飞行器都确定了各自的起点和终点;(3)低空空域飞行环境已知,包括禁止飞行区域位置和范围、威胁点位置和辐射半径;(4)通用飞行器物理性能限制包括最大偏转角和最大飞行距离;所述路径规划方法具体包括如下步骤:
    第一步,建立飞行器路径规划模型;
    第二步,采用自适应差分目标进化算法对单架飞行器进行路径规划,具体步骤如下:
    S1:确定规划空间、起始点S和目标点E,利用启发式初始化算法初始化种群,并完成相对极坐标个体向绝对值坐标个体转化的种群预处理;
    S2:根据航行速度v和采样时间步长Δt,对种群个体完成航迹点离散化;
    S3:根据第一步中所建立的飞行器路径规划模型,利用初始种群的个体的离散化航迹点进行航迹约束验证和目标值计算,并计算每个个体的所有约束的约束值之和err_ind;
    S4:对父代种群进行按照自适应差分算子进行遗传交叉与变异操作,形成子种群;
    S5:完成子种群中子代个体航迹点离散化,将离散化的航迹点带入问题模型,完成与个体约束、目标函数值及所有约束的约束值之和err_ind的计算;
    S6:父代与子代形成混合群,对混合群实施改进的快速非支配排序,确定混合群各个体所分布的Pareto层;
    S7:对混合群每一层的个体进行改进的聚集距离与排挤机制,根据支配关系及个体拥挤度从混合群中选取种群大小数目的个体组成新的父代种群;
    S8:判断进化过程是否结束,如果达到最大迭代的代数,转入S9;否则转入S4;
    S9:从种群中非支配层中选出个体,其代表的航迹即为所求航迹;
    步骤S1中所述的初始化种群,采用两种初始种群个体表达方式,即相对极坐标编码方式和绝对值坐标编码方式,包含相对极坐标生成初始染色体和初始种群个体坐标转换两步:
    (S101)航迹节点初始化按式(26)获得相对极坐标(r,θ,z)的值表示其对应的三维航迹节点,其中rand()代表均匀分布取值,r的下限Minseg和上限代表相邻航迹点间的最短允许距离,turn_θ的上下限和飞行器机动性相关,得到的θi的正负代表了下一航迹段较前一航迹段的偏转方向,逆时针为正,顺时针为负;
    ri=rand(Minseg,MaxLNw)θi=rand(-turn_θ,turn_θ)zi=rand(min(start.z,end.z),max(start.z,end.z))---(26)]]>
    其中,(start.z,end.z)代表起始点和目标点的高度坐标值。
    (S102)初始种群个体坐标系转换:
    利用相对极坐标法生成初始种群后,利用相对极坐标和绝对值坐标的对应关系,通过式(27)和式(28)对生成的相对极坐标表示的个体的二维航迹进行坐标系转化,将生成的相对极坐标初始种群转化成绝对值坐标表示的初始种群;第一个航迹节点W1的绝对值坐标(x1,y1,z1)由其相对极坐标(r1,θ1,z1)由式(27)和式(28)得到,其中(start.x,start.y)和(end.x,end.y)为起始点和目标点的二维坐标;
    α=arctan(end.y-start.yend.x-start.x)x1=start.x+r1*cos(α+θ1)y1=start.y+r1*sin(α+θ1)z1=z1---(27)]]>
    基于已求得的W1(x1,y1,z1),得到后续航迹点Wi的绝对值坐标(xi,yi,zi):
    sumθ=Σk=1i+1θkxi=xi-1+ri+1*cos(α+sumθ)yi=yi-1+ri+1*sin(α+sumθ)zi=zi---(28)]]>
    其中,i=2,...,N-1;
    步骤S2中所述的种群个体航迹节点离散化,具体是指:
    在假定飞行器以速度v匀速飞行的前提下,将航迹节点离散化,得到进行约束验证的离散化点序列dis{S,P1,P2,...,PN-2,E};以由两连续的航迹点Pi(xi,yi,zi)和Pi+1(xi+1,yi+1,zi+1)构成的航迹段li为例,i=0,...,N-1,航迹段li的离散点序列disp_li{Pi1(xi1,yi1,zi1),Pi2(xi2,yi2,zi2),...,Pim(xim,yim,zim)}的坐标值由下式得到:


    θi=arctan(yi+1-yixi+1-xi)---(31)]]>
    m=floor((xi+1-xi)2+(yi+1-yi)2+(zi+1-zi)2Δt*v)---(32)]]>
    其中为航迹段li在竖直方向上的偏移角度,θi为航迹段li在二维平面上的相对于x轴正向的偏移角度,Δt为取样时间步,floor()为向下取整函数;
    所述的步骤S4中种群自适应差分遗传交叉与变异操作,形成子种群,具体为:
    S401:对初始种群进行评价,即计算初始种群中每个个体的目标函数值;
    S402:进行变异操作,对每个目标个体通过式(33)产生其对应的变异个体
    viG+1=xr1G+F*(xr2G-xr3G)---(33)]]>
    其中:的下标r1,r2和r3是随机选择的不同的数,且与目标向量的下标i也不同;F为缩放因子,用来控制偏差变量的放大程度;
    S403:通过式(34),将目标个体和其变异个体进行交叉操作,则得到对应的交叉个体所有目标个体的交叉操作完成后,其交叉个体形成临时种群;
    uijG+1=vijG+1,if(randCR)orj=qxijG,if(rand>CR)andj≠q---(34)]]>
    其中:CR为交叉因子,是个体进行交叉操作的控制概率,q是一个在[1,D]之间的随机产生的整数,以确保交叉个体至少能从变异个体获得一维参数;字母D是指一个常数;
    所述的步骤S6中的改进的快速非支配排序,具体如下:
    设a与b是种群中两个个体,使用约束条件下改进的快速排序算子来完成个体a与b的支配关系的比较,流程如下:
    S601:得到个体a与个体b的与自身相关约束的各约束的约束值之和a.err_ind与b.err_ind;
    S602:判断个体a与b是否违约,即各自的err_ind值与0的大小关系,若a.err_ind与b.err_ind都大于0,即a和b都违反了约束条件,是不可行解,则转至S603;若只有一个个体的err_ind大于0,则转至S604;若两个个体的err_ind值都等于0,则转至S605;
    S603:若两个体的err_ind不同,转至S603.1;若两个体err_ind相同,转至S603.2;
    S603.1:按约束值之和大的个体支配约束值之和小的个体的原则,如果a.err_ind>b.err_ind,则个体a支配个体b,反之,则个体b支配个体a;
    S603.2:个体a与b支配关系不可比较,互不支配;
    S604:按没有违反约束条件的个体支配违反约束条件的个体原则,若b.err_ind>0且a.ind_err=0,则个体a支配个体b;若a.err_ind>0且b.ind_err=0,则个体b支配个体a;
    S605:进行改进的快速非支配排序;
    改进的快速非支配排序方法算子步骤如下:种群中每个个体p都有两个参数np和Sp,其中np为种群中支配个体p的个体数目,Sp为种群中被p支配的个体的集合,
    SS1:找到种群中np=0的个体,并保存在当前集合F1中;
    SS2:临时集合H赋空;对于当前集合F1中的每个个体i,考察它所支配的个体集合Si,将Si中每个个体j的nj减1,若nj-1=0,则将个体j放入集合H;此时集合H为当前层个体集合的下一层的个体集合;
    SS3:F1即为第1支配层个体集合,赋予该层内个体相同的非支配排序irank;
    SS4:以H为当前集合,返回步骤SS2,直至整个种群排序完毕。
    如果第j个优化目标的目标函数上,有|fj(a)-fj(b)|≤δ,则认为个体a和b在fj上的值相等,如果个体a和b在所有的目标之上都有这样的关系,则个体a与b互不支配;其中,fj(a)和fj(b)分别代表个体a和个体b之于第j个目标函数fj的函数值;
    对于步骤S7中所述的改进的聚集距离计算,以种群某一Pareto层F上个体的聚集距离计算为例,给出改进聚集距离的计算方法:
    S701:计算出种群某一Pareto层F的个体个数NF;
    S702:对F内的每个个体的聚集距离赋零值,即:F[i].dis=0,i=1,…,popsize;popsize为种群大小,即种群中个体的数目;
    S703:对每个目标函数fj,j=1,..n,得到每个个体的函数值F[i].fj,按F[i].fj的大小将F内个体进行排序;
    S704:根据F层个体的排序情况,将边界点个体的聚集距离赋值无穷大,将其余个体的聚集距离按赋值,i=2,…,NF-1,即用一个个体被包围的矩形的对角线之和表示该个体的聚集距离;其中,fkmax和fkmin分别代表第k个函数的最大值和最小值。

    2.  根据权利要求1所述的一种适用于复杂低空下飞行器的路径规划方法,其特征在于:步骤S7中基于种群排序和每一层个体拥挤度的排挤机制,通过快速非支配排序以及拥挤度计算后,每个个体i都有两个属性:非支配序irank和聚集距离I[i].distance;利用这两个属性,从混合群中选取种群大小个数目的个体形成新一代进行进化的父代种群,选择标准为:若两个个体非支配排序不同,则取序号较小的个体;如果两个个体在同一级,则取聚集距离大的个体。

    3.  一种基于协同自适应差分多目标进化算法的多飞行器航迹规划方法,其特征在于包括如下步骤:
    步骤A:对每一架飞行器进行启发式初始化种群:
    A1:确定规划空间、起始点S和目标点E,利用启发式初始化算法初始化种群,并完成相对极坐标个体向绝对值坐标个体转化的种群预处理;
    A2:当所有飞行器种群都完成启发式初始化后,进入步骤B;
    步骤B:对每一架飞行器种群:
    B1:根据航行速度v和采样时间步长Δt,对种群个体完成航迹点离散化;
    B2:根据飞行器路径规划模型,利用初始种群的个体的离散化航迹点进行航迹约束验证和目标值计算,并计算每个个体的所有约束之和err_ind;
    B3:对父代种群进行按照自适应差分算子进行遗传操作,形成子种群;
    B4:完成子代个体航迹点离散化,将离散化的航迹点带入问题模型,完成与个体约束、目标函数值及所有约束之和err_ind的计算;
    B5:父代与子代形成混合群,对混合群实施改进的快速非支配排序,确定混合群个个体分布的Pareto层;
    B6:根据种群代表个体选择机制,从混合群中选择出本飞行器种群的代表个体;
    B7:当所有飞行器种群都完成混合群的代表个体选择后,进入步骤C;
    步骤C:对每一架飞行器种群:
    C1:接收其余各飞行器混合群选择出的代表个体,进行本飞行器混合群所有个体协同避撞约束值计算,得到混合群中每个个体的所有约束之和err_all;
    C2:对混合群每一层的个体进行改进的聚集距离计算与排挤机制,根据支配关系及个体拥挤度从混合群中选取种群大小数目的个体组成新的父代种群;
    C3:判断进化过程是否结束,如果满足终止条件,转入C4;否则转入步骤B;
    C4:从种群中非支配层中选出个体其代表的航迹即为所求航迹。

    4.  根据权利要求3所述的一种基于协同自适应差分多目标进化算法的多飞行器航迹规划方法,其特征在于:步骤C1中所有个体协同避撞约束值计算,根据碰撞检测机制进行计算;所述的碰撞检测机制,假设飞行器A和飞行器B分别从各自的起点SA和SB沿着其航迹a和航迹b飞行向终点EA和EB,Wak,Wbk分别为航迹a和航迹b的航迹节点,k=1,....Nw;Nw为需要规划的航迹节点数,pai,pbi分别为某同一时刻飞行器A和飞行器B在航迹a和航迹b上所处的位置点,va和vb分别为飞行器的飞行速度,Δt为一个小时间步,则对飞行器A的规划航迹a和飞行器B的规划航迹b进行的碰撞检测的流程为:
    S1:按照位置计算算子,得到自起飞时刻起,每隔时间步Δt,两架飞机分别在航迹a和航迹b上各自将所处的位置点序列和Pa和Pb点序列的元素数Nt由飞行时间短的那条航迹的飞行时间决定;
    S2:从起飞开始,每隔Δt时刻,计算在同一时刻,沿航迹a飞行的飞行器A和沿路径b飞行的飞行器B之间的距离,即从i=0开始到i=Nt,计算pai和pbi的距离|paipbi|,记为
    S3:判断沿各自航迹飞行的两机在某一时刻是否产生冲突:若小于预设的安全距离,即则称飞行器A的路径a与飞行器B的路径b发生一次冲突,即飞行器A的航迹a和飞行器B的航迹b的免碰撞约束违约。

    5.  根据权利要求4所述的一种基于协同自适应差分多目标进化算法的多飞行器航迹规划方法,其特征在于:所述的位置计算算子的流程如下:
    SS1:计算飞行器A的航迹a和飞行器B的航迹b各自的航程距离,分别记为La和Lb,并由得到各机分别在该两航迹上的飞行时间Ta和Tb;
    SS2:计算飞行器A在航迹a和飞行器B在航迹b的上所有航迹段上的飞行时间序列,即所有由一个航迹节点到达下一航迹节点的飞行时间构成的序列:和再计算各飞行器到达各自航迹点的时刻序列以航迹a为例,其中ta由式(37)计算求得:
    tai=Σk=1iTsegak,i=1,2,...,Nw---(37)]]>
    Tsegai=|WaiSA|v,i=1|WaiWai-1|v,i=2:Nw|EAWai|v,i=Nw+1---(38)]]>
    SS3:计算碰撞检测的测试次数Nt,其中celling()为向上取整函数;
    SS4:确定航迹a与航迹b进行碰撞检测的采样位置点序列和
    其中求解pai{xai,yai,zai}的算法流程为,i=1,…,Nt:
    SSS1:begin_t记录从每一航迹段的起点到该航迹段的起始采样点的时间,begin_t赋初值为0;k为航迹段下标,k=1:N-1;
    SSS2:当k<=Nw+1时:
    1)计算在第k航迹段上的累计采样点时间det,det=i*Δt+being_t,计算第k航迹段在竖直方向上的偏移角度和在二维平面上的相对于x轴正向的偏移角θk;
    2)当det小于本航迹段的飞行时间Tsegak时,即当det≤tak时,按式(39)计算pai{xai,yai,zai},并且i=i+1:

    否则:
    3)判断是否到达最后一个采样点,即当i==Nt+1时,按式(40)计算pai{xai,yai,zai}:
    xai=Wak.xyai=Wak.yzai=Wak.z---(40)]]>
    否则k=k+1,且being_t=det-tak。

    说明书

    说明书一种适用于复杂低空下飞行器的路径规划方法
    技术领域
    本发明涉及一种飞行管理方法和系统,是一种适用于复杂低空空域的通用航空器飞行器路径规划的方法。
    背景技术
    低空空域原则上是指真高1000米以下的空域范围,在该区域内活动的主要是通用航空飞行器。低空空域环境复杂,通用航空飞行器在该区域内可自由飞行(是由美国联邦航空局(FAA,Federal Aviation Administration)提出,它是一种全新的航空理念,赋予飞行人员自由实时地选择航路以及飞行航速等状态的权利,即实行自主管理),自主性强。在某些场景(比如应急救灾)下飞机密度高,飞行的安全性和高效性难以保证。随着我国逐步开放低空空域,通用航空势必蓬勃发展,为保障飞行运行的安全与效率,对通航飞行器规划合理经济的路径十分重要。
    路径规划是指在给定的规划空间内,寻找运动体从起始点到达目标点且满足约束条件和一定性能指标的最优或最可行轨迹。对通航飞行器进行路径规划是保证飞行器飞行安全和提高效率的重要手段,目前国内外对该领域的研究主要包括传统规划算法和智能规划算法。传统规划算法包括动态规划算法、最优控制法和导数相关法等,这类方法要进行大规模的反复迭代,缺乏智能导向能力,计算量普遍较大,算法计算时间长,不适用于低空空域的自由飞行,而且鲁棒性较差;智能规划算法包括启发式寻优搜索、蚁群算法、神经网络算法和遗传算法。由于路径规划的实质是NP问题。既随着问题规模的增长,计算复杂度急剧加大。遗传算法因其启发搜索算子和良好的寻优能力已被证明是解决NP问题的有效方法。通用航空飞行器的路径规划问题的实质又是一系列相互冲突的目标优化,使用多目标优化算法比对将多个目标加权折衷成的单目标优化更优。
    发明内容
    本发明为了解决现有技术中存在的问题,提供一种适用于复杂低空下飞行器的路径规划方法,术语协同多目标优化方法,所述的路径规划方法中,假设(1)所有飞行器都在同一高度层以不同速度飞行,且各自在飞行过程中飞行速度不发生改变;(2)每架飞行器都确定了各自的起点和终点;(3)低空空域飞行环境已知,包括禁止飞行区域位置和范围、威胁点位置和辐射半径;(4)通用飞行器物理性能限制包括最大偏转角和最大飞行距离;所述路径规划方法具体包括如下步骤:
    第一步,建立飞行器路径规划模型;
    第二步,采用自适应差分目标进化算法对单架飞行器进行路径规划,具体步骤如下:
    S1:确定规划空间、起始点S和目标点E,利用启发式初始化算法初始化种群,并完成相对极坐标个体向绝对值坐标个体转化的种群预处理;
    S2:根据航行速度v和采样时间步长Δt,对种群个体完成航迹点离散化;
    S3:根据第一步中所建立的飞行器路径规划模型,利用初始种群的个体的离散化航迹点进行航迹约束验证和目标值计算,并计算每个个体的所有约束的约束值之和err_ind;
    S4:对父代种群进行按照自适应差分算子进行遗传交叉与变异操作,形成子种群;
    S5:完成子种群中子代个体航迹点离散化,将离散化的航迹点带入问题模型,完成与个体约束、目标函数值及所有约束的约束值之和err_ind的计算;
    S6:父代与子代形成混合群,对混合群实施改进的快速非支配排序,确定混合群各个体所分布的Pareto层;
    S7:对混合群每一层的个体进行改进的聚集距离与排挤机制,根据支配关系及个体拥挤度从混合群中选取种群大小数目的个体组成新的父代种群;
    S8:判断进化过程是否结束,如果达到最大迭代的代数,转入S9;否则转入S4;
    S9:从种群中非支配层中选出个体,其代表的航迹即为所求航迹;
    步骤S1中所述的初始化种群,采用两种初始种群个体表达方式,即相对极坐标编码方式和绝对值坐标编码方式,包含相对极坐标生成初始染色体和初始种群个体坐标转换两步:
    (S101)航迹节点初始化按式(26)获得相对极坐标(r,θ,z)的值表示其对应的三维航迹节点,其中rand()代表均匀分布取值,r的下限Minseg和上限代表相邻航迹点间的最短允许距离,turn_θ的上下限和飞行器机动性相关,得到的θi的正负代表了下一航迹段较前一航迹段的偏转方向,逆时针为正,顺时针为负;
    ri=rand(Minseg,MaxLNw)θi=rand(-turn_θ,turn_θ)zi=rand(min(start.z,end.z),max(start.z,end.z))---(26)]]>
    其中,(start.z,end.z)代表起始点和目标点的高度坐标值。
    (S102)初始种群个体坐标系转换:
    利用相对极坐标法生成初始种群后,利用相对极坐标和绝对值坐标的对应关系,通过式(27)和式(28)对生成的相对极坐标表示的个体的二维航迹进行坐标系转化,将生成的相对极坐标初始种群转化成绝对值坐标表示的初始种群;第一个航迹节点W1的绝对值坐标(x1,y1,z1)由其相对极坐标(r1,θ1,z1)由式(27)和式(28)得到,其中(start.x,start.y)和(end.x,end.y)为起始点和目标点的二维坐标;
    α=arctan(end.y-start.yend.x-start.x)x1=start.x+r1*cos(α+θ1)y1=start.y+r1*sin(α+θ1)z1=z1---(27)]]>
    基于已求得的W1(x1,y1,z1),得到后续航迹点Wi的绝对值坐标(xi,yi,zi):
    sumθ=Σk=1i+1θkxi=xi-1+ri+1*cos(α+sumθ)yi=yi-1+ri+1*sin(α+sumθ)zi=zi---(28)]]>
    其中,i=2,...,N-1;
    步骤S2中所述的种群个体航迹节点离散化,具体是指:
    在假定飞行器以速度v匀速飞行的前提下,将航迹节点离散化,得到进行约束验证的离散化点序列dis{S,P1,P2,...,PN-2,E};以由两连续的航迹点Pi(xi,yi,zi)和Pi+1(xi+1,yi+1,zi+1)构成的航迹段li为例,i=0,...,N-1,航迹段li的离散点序列disp_li{Pi1(xi1,yi1,zi1),Pi2(xi2,yi2,zi2),...,Pim(xim,yim,zim)}的坐标值由下式得到:


    θi=arctan(yi+1-yixi+1-xi)---(31)]]>
    m=floor((xi+1-xi)2+(yi+1-yi)2+(zi+1-zi)2Δt*v)---(32)]]>
    其中为航迹段li在竖直方向上的偏移角度,θi为航迹段li在二维平面上的相对于x轴正向的偏移角度,Δt为取样时间步,floor()为向下取整函数;
    所述的步骤S4中种群自适应差分遗传交叉与变异操作,形成子种群,具体为:
    S401:对初始种群进行评价,即计算初始种群中每个个体的目标函数值;
    S402:进行变异操作,对每个目标个体通过式(33)产生其对应的变异个体
    viG+1=xr1G+F*(xr2G-xr3G)---(33)]]>
    其中:的下标r1,r2和r3是随机选择的不同的数,且与目标向量的下标i也不同;F为缩放因子,用来控制偏差变量的放大程度;
    S403:通过式(34),将目标个体和其变异个体进行交叉操作,则得到对应的交叉个体所有目标个体的交叉操作完成后,其交叉个体形成临时种群;
    uijG+1=vijG+1,if(randCR)orj=qxijG,if(rand>CR)andj&NotEqual;q---(34)]]>
    其中:CR为交叉因子,是个体进行交叉操作的控制概率,q是一个在[1,D]之间的随机产生的整数,以确保交叉个体至少能从变异个体获得一维参数;字母D是指一个常数;
    所述的步骤S6中的改进的快速非支配排序,具体如下:
    设a与b是种群中两个个体,使用约束条件下改进的快速排序算子来完成个体a与b的支配关系的比较,流程如下:
    S601:得到个体a与个体b的与自身相关约束的各约束的约束值之和a.err_ind与b.err_ind;
    S602:判断个体a与b是否违约,即各自的err_ind值与0的大小关系,若a.err_ind与b.err_ind都大于0,即a和b都违反了约束条件,是不可行解,则转至S603;若只有一个个体的err_ind大于0,则转至S604;若两个个体的err_ind值都等于0,则转至S605;
    S603:若两个体的err_ind不同,转至S603.1;若两个体err_ind相同,转至S603.2;
    S603.1:按约束值之和大的个体支配约束值之和小的个体的原则,如果a.err_ind>b.err_ind,则个体a支配个体b,反之,则个体b支配个体a;
    S603.2:个体a与b支配关系不可比较,互不支配;
    S604:按没有违反约束条件的个体支配违反约束条件的个体原则,若b.err_ind>0且a.ind_err=0,则个体a支配个体b;若a.err_ind>0且b.ind_err=0,则个体b支配个体a;
    S605:进行改进的快速非支配排序;
    改进的快速非支配排序方法算子步骤如下:种群中每个个体p都有两个参数np和Sp,其中np为种群中支配个体p的个体数目,Sp为种群中被p支配的个体的集合,
    SS1:找到种群中np=0的个体,并保存在当前集合F1中;
    SS2:临时集合H赋空;对于当前集合F1中的每个个体i,考察它所支配的个体集合Si,将Si中每个个体j的nj减1,若nj-1=0,则将个体j放入集合H;此时集合H为当前层个体集合的下一层的个体集合;
    SS3:F1即为第1支配层个体集合,赋予该层内个体相同的非支配排序irank;
    SS4:以H为当前集合,返回步骤SS2,直至整个种群排序完毕。
    如果第j个优化目标的目标函数上,有|fj(a)-fj(b)|≤δ,则认为个体a和b在fj上的值相等,如果个体a和b在所有的目标之上都有这样的关系,则个体a与b互不支配;其中,fj(a)和fj(b)分别代表个体a和个体b之于第j个目标函数fj的函数值;
    对于步骤S7中所述的改进的聚集距离计算,以种群某一Pareto层F上个体的聚集距离计算为例,给出改进聚集距离的计算方法:
    S701:计算出种群某一Pareto层F的个体个数NF;
    S702:对F内的每个个体的聚集距离赋零值,即:F[i].dis=0,i=1,…,popsize;popsize为种群大小,即种群中个体的数目;
    S703:对每个目标函数fj,j=1,..n,得到每个个体的函数值F[i].fj,按F[i].fj的大小将F内个体进行排序;
    S704:根据F层个体的排序情况,将边界点个体的聚集距离赋值无穷大,将其余个体的聚集距离按赋值,i=2,…,NF-1,即用一个个体被包围的矩形的对角线之和表示该个体的聚集距离;其中,fkmax和fkmin分别代表第k个函数的最大值和最小值。
    基于所述的单架飞行器路径规划方法,本发明还提供一种多架飞行器路径规划方法,包括如下步骤:
    步骤A:对每一架飞行器进行启发式初始化种群:
    A1:确定规划空间、起始点S和目标点E,利用启发式初始化算法初始化种群,并完成相对极坐标个体向绝对值坐标个体转化的种群预处理;
    A2:当所有飞行器种群都完成启发式初始化后,进入步骤B;
    步骤B:对每一架飞行器种群:
    B1:根据航行速度v和采样时间步长Δt,对种群个体完成航迹点离散化;
    B2:根据飞行器路径规划模型,利用初始种群的个体的离散化航迹点进行航迹约束验证和目标值计算,并计算每个个体的所有约束之和err_ind;
    B3:对父代种群进行按照自适应差分算子进行遗传操作,形成子种群;
    B4:完成子代个体航迹点离散化,将离散化的航迹点带入问题模型,完成与个体约束、目标函数值及所有约束之和err_ind的计算;
    B5:父代与子代形成混合群,对混合群实施改进的快速非支配排序,确定混合群个个体分布的Pareto层;
    B6:根据种群代表个体选择机制,从混合群中选择出本飞行器种群的代表个体;
    B7:当所有飞行器种群都完成混合群的代表个体选择后,进入步骤C;
    步骤C:对每一架飞行器种群:
    C1:接收其余各飞行器混合群选择出的代表个体,进行本飞行器混合群所有个体协同避撞约束值计算,得到混合群中每个个体的所有约束之和err_all;
    C2:对混合群每一层的个体进行改进的聚集距离计算与排挤机制,根据支配关系及个体拥挤度从混合群中选取种群大小数目的个体组成新的父代种群;
    C3:判断进化过程是否结束,如果满足终止条件,转入C4;否则转入步骤B;
    C4:从种群中非支配层中选出个体其代表的航迹即为所求航迹。
    本发明的优点在于:
    1、本方法是一种多机协同进化的冲突解脱方法,运算效率高,能够满足预规划路径的需求;
    2、本方法能够满足低空空域自由飞行条件下的单机和多机路径规划需求。
    3、本方法具有一定的反馈设置,能够在保证规划路径的安全性的同时也获得较高的飞行效率。
    附图说明
    图1为飞行器路径规划模型;
    图2为违反地图范围航迹示意图;
    图3A~图3D为一航迹段与一个禁飞区之间可能存在的四种情形;
    图4为威胁区域i对路径段j的威胁系数计算示意图;
    图5为自适应差分多目标进化算法的流程图;
    图6A和图6B分别为用相对极坐标和笛卡尔坐标表示的同一航迹;
    图7为第i航迹段的航迹节点离散化示意图;
    图8为基于协同差分多目标进化算法的多飞行器航迹规划流程图;
    图9为飞行器航迹间的碰撞检测示意图。
    具体实施方式
    下面将结合附图和实施例对本发明作进一步的详细说明。
    首先对涉及到的几个定义进行如下说明:
    1、飞行冲突与飞行碰撞:当两架飞行器之间的距离小于冲突阈值(碰撞阈值时),则认为这两架飞行器存在冲突风险(碰撞风险)。
    2、个体:每一个体均代表问题的一个潜在解,每一个体都被评价优劣,并以一定的概率有可能进行遗传操作,进行进化。个体也称染色体。
    3、染色体编码:编码就是将一个问题的可行解从其解空间转换到算法所能处理的搜索空间的转换方法。编码对于基于遗传算法的智能优化算法的性能以及种群多样性影响很大。
    4、种群:遗传算法中维持由一群个体组成的一个群体集合叫种群,种群中个体的数目叫做种群大小。
    5、父代与子代:种群经过遗传操作之前为父代,经过遗传操作之后得到的新种群为其子代。
    6、协同多目标进化:一种基于协同进化的多目标优化方法。
    7、多目标进化个体的支配关系:给定最小化多目标优化问题,若p和q是进化群体pop中 任意两个不同的个体,若同时满足:①对所有子目标,p不比q差,即fk(p)<=fk(q),k=1,2,…,m;②至少存在一个子目标,使p比q好,即存在k∈{1,2,..,m},使fk(p)<fk(q)。则称p支配q。p为非支配的(non-dominated),q为被支配的(dominated)。当且仅当存在i∈{1,2,..,m},使fi(p)<fi(q),且存在j∈{1,2,..,m},使fj(p)<fj(q),则称p与q互不支配。
    8、Pareto最优解:多目标问题存在多个目标,由于目标之间存在冲突且无法比较,故很难寻找到一个最优解使所有目标函数都达到最优,通常存在一个解集,这个解集中的解就全体目标函数而言是无法比较优劣的,即pareto解。其定义为(设问题为最小化多目标问题):对于可行解x,当且仅当存在可行解x*使:①F(x)<=F(x*),F(x)指目标函数向量集;②至少存在一个fj(x)<fj(x*),其中fj(x)是目标函数之一。
    本发明提供一种适用于复杂低空下飞行器的路径规划方法,假设:
    (1)所有飞行器都在同一高度层以不同速度飞行,且各自在飞行过程中飞行速度不发生改变。(2)每架飞行器都确定了各自的起点和终点。(3)低空空域飞行环境已知,包括禁止飞行区域位置和范围、威胁点位置和辐射半径。其中禁止飞行区域为矩形区域,威胁区域为以威胁点为圆心、辐射半径为半径的圆形区域。(4)通用飞行器物理性能限制包括最大偏转角和最大飞行距离。
    所述的路径规划方法,具体包括如下步骤:
    第一步,建立飞行器路径规划模型;
    结合附图1,为了模拟飞行器的飞行环境,本发明从复杂低空空域环境、飞行器机动性能和航迹性能指标几个方面建立飞行器路径规划模型。
    其中,飞行路径生成的影响因素中不能违背的标准,如自身机动性能等,称之为约束;而一些概率性的影响因素,如潜在威胁区域风险,若飞行航迹超标量不大,飞行器是完全可以在承担一定风险前提下飞行的,则称它为目标。在低空空域中飞行的每架飞行器规划的路径必须满足环境约束和其自身的物理性能约束,并且实现安全和高效的目标。
    所述的环境约束具体如下:
    (1)地图约束:飞行器必须在已知的地图范围内飞行以确保飞行安全。一条飞行路径的地图约束值可由下式取得:
    cmap=Σi=0Nci---(1)]]>
    ci=1,if(xmaplxixmapu)^(ymaplyiymapu)0,else---(2)]]>
    其中,Cmap是指一条飞行路径之于地图约束的约束违反值,Ci指飞行路径上的节点i之于地图约束指数,Ci=0时节点i位于地图内,即不违约,ci=1时不在地图内,违约。(xi,yi)为路径点i的坐标,N为路径点数目,为确定地图区域的坐标轴上下界。 如图2所示,某一飞行路径起点为S,终点为E,其间包括路径点W1、W2、W3、W4,若有路径点W1和W2在地图范围之外,则视作违反地图范围约束的路径点。
    (2)禁止飞行区域:飞行环境中会存在一些已知的极其危险区域,飞行器一旦进入,则面临极大危险。禁止飞行区域(PFZ)代表飞行环境中风险极大、信息未知的区域,是飞行器禁止进入的区域。本发明设定禁止飞行区域抽象为一个矩形区域,其主要参数为四个顶点坐标位置,设飞行空间域内禁止飞行区域的个数为NP,记第i个禁飞区为PFZi(i=1,2...,NP),其顶点位置分别为
    本发明中将一条航迹(也称飞行路径)进入所有禁止飞行区域(禁飞区)的航迹长度之和作为该航迹在禁飞区约束上的约束值,当约束值为零时该航迹不违背禁止进入禁飞区约束。由于禁飞区信息以二维形式给出,本发明只计算航迹在禁飞区二维平面上的投影长度作为其进入禁飞区长度。一条飞行航迹的禁止飞行区域约束值cPEZ可由式(3)取得:
    cPEZ=Σi=1NpΣj=1N-1lji---(3)]]>
    lji=0,,if seg(i,j)=0(xji1-xj)2+(yji1-yj)2,if seg(i,j)=1(xji1-xji2)2+(yji1-yji2)2,if seg(i,j)=2(xj-1-xj)2+(yj-1-yj)2,if seg(i,j)=-1---(4)]]>

    其中式(4)中的lji为航迹的第j个航迹段在第i个禁飞区中的二维航迹长度,Np为禁止飞行区域的数目。seg(i,j)返回一个航迹段与一个矩形禁止飞行区域的交互可能存在四种情形之一,如图3A~3D所示:
    (a)航迹段j完全在第i个禁飞区之外,此时lji=0;如图3A所示,所述的航迹段是指航迹点Wj-i(xj-1,yj-1)和航迹点Wj(xj,yj)之间的一段。
    (b)如图3B,航迹段j的一个端点(xj,yj)在第i个禁飞区内,即航迹段j与第i个禁止飞行区域的某一边界存在一个交点此时lji=(xji1-xj)2+(yji1-yj)2;]]>
    (c)如图3C,航迹段j的两个端点(xj-1,yj-1)和(xj,yj)在第i个禁飞区内,即航迹段j完全位于第i个禁飞区内,此时lji=(xj-1--xj)2+(yj-1-yj)2;]]>
    (d)如图3D,航迹段j与第i个禁飞区的某两条边界存在交点即航迹段j完全穿越第i个禁飞区,此时lji=(xji1-xji2)2+(yji1-yji2)2.]]>
    (3)地形障碍约束;
    飞行区域的地形障碍主要是指飞行区域地形的高度起伏,如山峰、山谷的情况。飞行器在飞行过程中会遇到不可飞越的高山等障碍物,一旦撞山,会产生坠落等严重后果,所以在进行航迹规划时应当禁止飞行器直接碰撞到地形障碍物。对某一条航迹而言,其地形障碍约束可由式(6)取得:
    cterrain=Σi=0Ncter_i---(6)]]>
    cter_i=1,ifziterrain(xi,yi)0,else---(7)]]>
    其中,terrain(xi,yi)为返回点(xi,yi)处的地势高度函数。
    所述的自身物理约束具体如下:
    (1)偏转角约束:
    由于通用航空飞行器自身的物理性能限制,当其需改变航向时,应使偏转角不超过其允许的最大偏转角θ。一条飞行路径的偏转角约束值cturn可由式(8)取得:
    cturn=Σj=1N-1cj---(8)]]>
    cj=1-ajTaj+1|aj||aj+1|cosθ---(9)]]>
    其中,aj代表由第j+1节点和第j节点确定的航迹段j的向量:aj=(xj+1-xj,yj+1-yj)。
    (2)最大俯仰角约束模型;
    与最大偏转角类似,受飞行器自身的机动性能影响,飞行器在飞行的垂直平面内不能以任意角度进行爬升和俯冲。一条航迹的俯仰角约束值cpitch可由式(10)取得:
    cpitch=Σj=1N-1cp_j---(10)]]>
    cp_j=0,if(β-tan-1[|zj+1-zj||(xj+1-xj)2+(yj+1-yj)2|])<0β-tan-1[|zj+1-zj||(xj+1-xj)2+(yj+1-yj)2|],else---(11)]]>
    其中,β代表飞行器物理性能规定的最大俯仰角;(xj,yj,zj)和(xj+1,yj+1,zj+1)分别表示第j个航迹节点和第j+1个航迹节点。
    (3)最小航迹段约束模型;
    为了确保飞行器能更安全和更准确地飞行,在飞行器进行拐弯、爬升等飞行姿态调整前后,飞行器应该保持一段距离的直飞状态以便完成其姿态调整过程。这个直飞状态至少应该达到的步长距离就称为飞行器的最小航迹段飞行距离约束,在本文用Minseg表示最小航迹段。 一条航迹的航迹段约束可以由式(12)取得:
    cseglen=Σj=1N-1csl_j---(12)]]>
    csl_j=0,iflj-Minseg&GreaterEqual;01,else---(13)]]>
    lj=(xj+1-xj)2+(yj+1-yj)2+(zj+1-zj)2---(14)]]>
    其中,lj代表第j航迹段的实际长度,(xj,yj,zj)和(xj+1,yj+1,zj+1)分别表示第j个航迹节点和第j+1个航迹节点。
    (4)最大飞行距离(也叫最大航程)约束:飞行器在整个飞行过程中,其航程会受到燃油和时间配给的限制,因此存在最大航程约束,记为maxL。一条路径的最大航程约束值cTdis可由式(15)取得:
    cTdis=0,if MaxL-Σj=1N-1lj&GreaterEqual;01,else---(15)]]>
    lj=(xj+1-xj)2+(yj+1-yj)2+(zj+1-zj)2---(16)]]>
    为飞行器规划路径时,飞行器的油耗、飞行时间和安全系数都应该保证。在这里多目标是由两个相互矛盾的目标组成,分别是最小风险目标和最短路径目标。
    本发明中潜在威胁区域建模为圆形区域,基于威胁作用半径,计算飞行器航迹受到所有未知威胁区域的威胁指数大小。当飞行器处于威胁区域范围内时,威胁区中心对飞行器的威胁指数强,飞行器越远离威胁中心,威胁指数越弱??梢杂酶鞲龊郊6蔚耐仓甘屠幢硎菊龊郊5耐仓甘?,一条航迹的最小风险目标值frisk可由式(17)计算得出:
    frisk=Σj=1N-1risk(segj)---(17)]]>
    以由航迹点wj-1和航迹点wj确定的第j航迹段的威胁代价计算为例,选取该航迹段中的六个点来计算第i个潜在威胁区域(如威胁区域i)对第j航迹段的威胁指数,如式(18)所示,图4为对应示意图:
    segriski(segi)=lj6*Σi=1Nsite[Pi(wj-1)+Pi(Pj(16))+Pi(Pj(26))+Pi(Pj(36))+Pi(Pj(46))+Pi(Pj(56))]---(18)]]>
    其中,Segriski()为函数名,参数为segj,代表第j航迹段之于第i个潜在风险区对的风险值;lj表示第j航迹段的长度,Nsite为潜在威胁区个数,Pi(p)为威胁点i对某一点p的威胁概率,可由式(19)计算得到:
    Pi(p)=Ki(dp(i))4,ifdpi<Rsafei0,else---(19)]]>
    dp(i)=(Pj(p).x-Riski.x)2+(Pj(p).y-Riski.y)2,p=0,16,...,56---(20)]]>
    其中,Rsafei为威胁区域i的威胁半径,(Riski.x,Riski.y)为第i个威胁目标的二维位置,Ki为威胁区域i的威胁强度,dp(i)为点p距威胁区域圆心的距离,p代表第j航迹段上的第等分点。
    2)最短路径目标;
    在保证飞行安全的前提下,航迹短意味着所需要的时间短、油耗少,所以在符合约束最大航迹长度的前提下,短路径优于长路径,要求航迹长度应尽可能的小。本文使用真实飞行距离和最小可能长度的比值界定计算一条路径的最短路径长度目标值,即利用最小飞行距离lmin对实际路径长度进行归一化作为目标函数flenr,见式(21):
    flenr=Σi=1N-1(xi+1-xi)2+(yi+1-yi)2+(zi+1-zi)2lmin---(21)]]>
    lmin=(xend-xstart)2+(yend-ystart)2+(zend-zstart)2---(22)]]>
    其中,lmin为起点到终点的直线距离,(xstart,ystart,zstart)和(xend,yend,zend)分别为起点和终点坐标;(xi,yi,zi)和(xi+1,yi+1,zi+1)分别为起点和终点间任意相邻两点的坐标。
    对于所述的协同避撞约束,在多机(M架飞行器)执行飞行任务时,各机需要在满足其飞行性能的基础上绕开禁飞区,回避威胁区域等找到一条经济快速的路径,到达各自的目的地实施任务,每一架飞行器的航迹都要满足在沿为它规划好的航迹上飞行过程中不与沿其余飞行器航迹飞行的任一飞行器相撞。为了安全起见,一旦同一时刻任意两架飞行器之间的距离小于某一安全阈值,则认为这两架飞行器对应的航?;岵逋?,是不安全的。
    飞行器A的航迹a的协同避撞约束值Caco为:飞行器A的航迹a与其余所有飞行器(设一共有M架飞行器,则与其他M-1架飞行器)的各自的种群代表航迹的冲突之和,如式(23)所示:
    Caco=ΣB=1&ForAll;A&NotEqual;BMΣi=0Ntab+1ci---(23)]]>
    ci=1-diabdmin,ifdiab<dmin0---(24)]]>
    diab=(xai-xbi)2+(yai-ybi)2+(zai-zbi)2---(25)]]>
    其中,b为飞行器B的种群的代表航迹个体,Ntab为取时间步的总次数,为飞行器A沿每一个航迹a与飞行器B沿航迹b在同一时刻各自所在位置点{xai,yai,zai}与{xbi,ybi,zbi}的空间距离。
    第二步,基于所述的飞行器路径规划模型,采用自适应差分目标进化算法对单架飞行器进行路径规划,结合流程图5,具体步骤如下:
    S1:确定规划空间、起始点S和目标点E,利用启发式初始化算法初始化种群,并完成相对极坐标个体向绝对值坐标个体转化的种群预处理。
    S2:根据航行速度v和采样时间步长Δt,对种群个体完成航迹点离散化。
    S3:根据第一步中所建立的航迹规划模型,利用初始种群的个体的离散化航迹点进行航迹约束验证和目标值计算,并计算每个个体的所有约束的约束值之和err_ind。
    S4:对父代种群进行按照自适应差分算子进行遗传交叉与变异操作,形成子种群。
    S5:完成子种群中子代个体航迹点离散化,将离散化的航迹点带入问题模型,完成与个体约束、目标函数值及所有约束的约束值之和err_ind的计算。
    S6:父代与子代形成混合群,对混合群实施改进的快速非支配排序,确定混合群各个体所分布的Pareto层。
    S7:对混合群每一层的个体进行改进的聚集距离与排挤机制,根据支配关系及个体拥挤度从混合群中选取种群大小数目的个体组成新的父代种群。
    S8:判断进化过程是否结束。如果满足终止条件(达到最大迭代的代数),转入S9;否则转入S4。
    S9:从种群中非支配层(第一层)中选出个体,其代表的航迹即为所求航迹。
    步骤S1中所述的种群初始化,具体如下:
    用多目标进化算法进行航迹规划的前提是确定进行进化操作染色体结构,其结构直接决定了路径规划的效率和优劣。本发明中采用启发式种群算法进行种群初始化的方法,采用两种初始种群个体表达方式,即相对极坐标编码方式和绝对值坐标编码方式,包含相对极坐标生成初始染色体和初始种群个体坐标转换两步:
    (S101)航迹节点初始化按式(26)获得相对极坐标(r,θ,z)的值表示其对应的三维航迹节点,其中rand()代表均匀分布取值,r的下限Minseg和上限代表相邻航迹点间的最短允许距离,turn_θ的上下限和飞行器机动性相关,得到的θi的正负代表了下一航迹段较前一航迹段的偏转方向,逆时针为正,顺时针为负。此策略好处是在初始化过程中就充分利用了已知信息,如航迹段最小长度限制和最大偏转角限制,从而减少搜索空间。
    ri=rand(Minseg,MaxLNw)θi=rand(-turn_θ,turn_θ)zi=rand(min(start.z,end.z),max(start.z,end.z))---(26)]]>
    其中,(start.z,end.z)代表起始点和目标点的高度坐标值。
    (S102)初始种群个体坐标系转换:
    利用相对极坐标法生成初始种群后,利用相对极坐标和绝对值坐标的对应关系,通过式(27)和式(28)对生成的相对极坐标表示的个体的二维航迹进行坐标系转化,将生成的相对极坐标初始种群转化成绝对值坐标表示的初始种群。
    图6表示了分别用(a)相对极坐标和(b)笛卡尔坐标的同一路径。第一个航迹节点W1的绝 对值坐标(x1,y1,z1)可由其相对极坐标(r1,θ1,z1)由式(27)和式(28)得到,其中(start.x,start.y)和(end.x,end.y)为起始点和目标点的二维坐标。
    α=arctan(end.y-start.yend.x-start.x)x1=start.x+r1*cos(α+θ1)y1=start.y+r1*sin(α+θ1)z1=z1---(27)]]>
    基于已求得的W1(x1,y1,z1),可得后续航迹点Wi(i=2,...,N-1)的绝对值坐标(xi,yi,zi):
    sumθ=Σk=1i+1θkxi=xi-1+ri+1*cos(α+sumθ)yi=yi-1+ri+1*sin(α+sumθ)zi=zi---(28)]]>
    步骤S2中所述的种群个体航迹节点离散化,具体是指:
    每相邻的两个航迹节点形成一个航迹段,飞行器依次沿着航迹段飞行,所以航迹段上的点也是需要进行约束验证的。本发明在假定飞行器以速度v匀速飞行的前提下,将航迹节点离散化,得到进行约束验证的离散化点序列dis{S,P1,P2,...,PN-2,E}。以由两连续的航迹点Pi(xi,yi,zi)和Pi+1(xi+1,yi+1,zi+1)构成的航迹段li(i=0,...,N-1)为例,如图7所示,航迹段li的离散点序列disp_li{Pi1(xi1,yi1,zi1),Pi2(xi2,yi2,zi2),...,Pim(xim,yim,zim)}的坐标值可由下式得到:


    θi=arctan(yi+1-yixi+1-xi)---(31)]]>
    m=floor((xi+1-xi)2+(yi+1-yi)2+(zi+1-zi)2Δt*v)---(32)]]>
    其中为航迹段li在竖直方向上的偏移角度,θi为航迹段li在二维平面上的相对于x轴正向的偏移角度,Δt为取样时间步,floor()为向下取整函数。
    所述的步骤S4中种群自适应差分遗传交叉与变异操作,形成子种群,具体为:
    S401:对初始种群进行评价,即计算初始种群中每个个体的目标函数值。
    S402:进行变异操作,对每个目标个体通过式(33)产生其对应的变异个体
    viG+1=xr1G+F*(xr2G-xr3G)---(33)]]>
    其中:的下标r1,r2和r3是随机选择的不同的数,且与目标向量的下标i也不同;F为缩放因子,用来控制偏差变量的放大程度。
    S403:通过式(34),将目标个体和其变异个体进行交叉操作,则可得到对应的 交叉个体所有目标个体的交叉操作完成后,其交叉个体形成临时种群。
    uijG+1=vijG+1,if(randCR)orj=qxijG,if(rand>CR)andj&NotEqual;q---(34)]]>
    其中:CR为交叉因子,是个体进行交叉操作的控制概率,q是一个在[1,D]之间的随机产生的整数,以确保交叉个体至少能从变异个体获得一维参数。字母D是指一个常数。
    本发明中采取自适应动态调整缩放因子F和交叉因子CR的大小策略,对种群中的每代个体都采用不同的缩放因子F和交叉因子CR进行差分进化,F和CR在进化过程中随着种群进化而变化的规律如式(35)和(36)所示:
    F=Fmin+(Fmax-Fmin)*exp(-GMaxgen-G+0.1)---(35)]]>
    CR=GMaxgen*CRmax---(36)]]>
    其中,Maxgen代表最大进化代数,G代表当前代数。
    本步骤结束以后得到由对初始种群进行差分操作得到的子代种群(子种群)。
    所述的步骤S6中的改进的快速非支配排序,具体如下:
    由于本发明中的复杂低空下飞行器航迹规划是在满足多约束条件下的多目标优化问题,在这种有约束条件下的多目标优化情况下,设a与b是种群中两个个体,本发明使用约束条件下改进的快速排序算子来完成个体a与b的支配关系的比较,流程如下:
    S601:得到个体a与个体b的与自身相关约束的各约束的约束值之和a.err_ind与b.err_ind。
    S602:判断个体a与b是否违约,即各自的err_ind值与0的大小关系。若a.err_ind与b.err_ind都大于0,即a和b都违反了约束条件,是不可行解,则转至S603;若只有一个个体的err_ind大于0,则转至S604;若两个个体的err_ind值都等于0,则转至S605。
    S603:若两个体的err_ind不同,转至S603.1;若两个体err_ind相同,转至S603.2。
    S603.1:按约束值之和大的个体支配约束值之和小的个体的原则,如果a.err_ind>b.err_ind,则个体a支配个体b,反之,则个体b支配个体a。
    S603.2:个体a与b支配关系不可比较,互不支配。
    S604:按没有违反约束条件的个体支配违反约束条件的个体原则,若b.err_ind>0且a.ind_err=0,则个体a支配个体b;若a.err_ind>0且b.ind_err=0,则个体b支配个体a。
    S605:进行改进的快速非支配排序。
    其中非支配排序方法算子步骤如下:(种群中每个个体p都有两个参数np和Sp,其中np为种群中支配个体p的个体数目,Sp为种群中被p支配的个体的集合)
    SS1:找到种群中np=0的个体,并保存在当前集合F1中。
    SS2:临时集合H赋空。对于当前集合F1中的每个个体i,考察它所支配的个体集合Si,将Si中每个个体j的nj减1,若nj-1=0(即个体j只被个体i支配,说明个体j在个体i的下一层),则将个体j放入集合H。此时集合H为当前层个体集合的下一层的个体集合。
    SS3:F1即为第1支配层个体集合,赋予该层内个体相同的非支配排序irank。
    SS4:以H为当前集合,返回步骤SS2,直至整个种群排序完毕。
    本发明设计一常数参数为比较精度δ用于改进快速非支配排序算子:如果第j个(一共有n个优化目标,j=1,…,n)目标函数上,有|fj(a)-fj(b)|≤δ,则认为个体a和b在fj上的值相等,如果个体a和b在所有的目标之上都有这样的关系,则个体a与b互不支配。其中,fj(a)和fj(b)分别代表个体a和个体b之于第j个目标函数fj的函数值。这样算法能在另一个函数上处于劣势的个体将被另一个个体支配,从而在搜索过程中逐渐移除那些在某个或某些目标上与其余个体差别很小但在其他目标上较差的个体,使最终结果中出现不合理个体的概率减少。
    对于步骤S7中所述的改进的聚集距离计算,具体为:
    下面以种群某一Pareto层F上个体的聚集距离计算为例,给出改进聚集距离的计算方法:
    S701:计算出种群某一Pareto层F的个体个数NF。
    S702:对F内的每个个体的聚集距离赋零值,即:F[i].dis=0,i=1,…,popsize。popsize为种群大小,即种群中个体的数目。
    S703:对每个目标函数fj(j=1,..n),得到每个个体的函数值F[i].fj,按F[i].fj的大小将F内个体进行排序。
    S704:根据F层个体的排序情况,将边界点个体的聚集距离赋值无穷大,将其余个体的聚集距离按(i=2,…,NF-1)赋值,即用一个个体被包围的矩形的对角线之和表示该个体的聚集距离;其中,fkmax和fkmin分别代表第k个函数的最大值和最小值。
    步骤S7中基于种群排序和每一层个体拥挤度的排挤机制,通过快速非支配排序以及拥挤度计算后,每个个体i都有两个属性:非支配序irank和聚集距离I[i].distance。利用这两个属性,可以从混合群(2倍原种群大?。┲醒∪≈秩捍笮「鍪康母鎏逍纬尚乱淮薪母复秩?,选择标准为:即若两个个体非支配排序不同,则取序号较小的个体;如果两个个体在同一级,则取聚集距离大(拥挤度?。┑母鎏?。
    基于所述的单架飞行器路径规划方法,本发明还提出了基于协同自适应差分多目标进化算法的多飞行器航迹规划方法,流程图如图8所示,具体步骤如下:
    步骤A:对每一架飞行器进行启发式初始化种群:
    A1:确定规划空间、起始点S和目标点E,利用启发式初始化算法初始化种群,并完成相对极坐标个体向绝对值坐标个体转化的种群预处理。
    A2:当所有飞行器种群都完成启发式初始化后,进入步骤B。
    步骤B:对每一架飞行器种群:
    B1:根据航行速度v和采样时间步长Δt,对种群个体完成航迹点离散化。
    B2:根据单机航迹规划问题描述一节中所建立的航迹规划模型,利用初始种群的个体的离散化航迹点进行航迹约束验证和目标值计算,并计算每个个体的所有约束之和err_ind。
    B3:对父代种群进行按照自适应差分算子进行遗传操作,形成子种群。
    B4:完成子代个体航迹点离散化,将离散化的航迹点带入问题模型,完成与个体约束、目标函数值及所有约束之和err_ind的计算。
    B5:父代与子代形成混合群,对混合群实施改进的快速非支配排序,确定混合群个个体分布的Pareto层。
    B6:根据种群代表个体选择机制,从混合群中选择出本飞行器种群的代表个体。
    B7:当所有飞行器种群都完成混合群的代表个体选择后,进入步骤C。
    步骤C:对每一架飞行器种群:
    C1:接收其余各飞行器混合群选择出的代表个体,进行本飞行器混合群所有个体协同避撞约束值计算,得到混合群中每个个体的所有约束之和err_all。
    C2:对混合群每一层的个体进行改进的聚集距离计算与排挤机制,根据支配关系及个体拥挤度从混合群中选取种群大小数目的个体组成新的父代种群。
    C3:判断进化过程是否结束。如果满足终止条件,转入C4;否则转入步骤B。
    C4:从种群中非支配层(第一层)中选出个体其代表的航迹即为所求航迹。
    本发明中采用多种群协同进化,即将所有无人机的运动状态、性能约束、威胁情况、目标等集中起来进行大规模优化,求出符合约束且时空协同的无人机航迹将成为高维、强耦合,优化难度大的问题,计算量巨大,复杂度高。借助于协同进化的思想,将集中优化问题分解成低维问题,每个独立的种群分别代表不同的飞行器,并行进化,在进化过程中接收其余种群选择的代表个体来对自身种群解进行协同约束评价。
    上述步骤C1中所有个体协同避撞约束值计算,根据碰撞检测机制进行计算。要计算一条航迹的免碰撞约束,就需建立航迹间的碰撞检测机制。本发明提出了更具实时性的“时点对时点”航迹间碰撞检测机制,下面通过对某两架飞行器的航迹碰撞约束分析来讲述本发明的碰撞检测机制。
    如图9所示,飞行器A和飞行器B分别从各自的起点SA和SB沿着其航迹a和航迹b飞行向终点EA和EB,Wak,Wbk(k=1,....Nw;Nw为需要规划的航迹节点数)分别为航迹a和航迹b的航 迹节点,pai,pbi分别为某同一时刻飞行器A和飞行器B在航迹a和航迹b上所处的位置点,va和vb分别为飞行器的飞行速度,Δt为一个小时间步,则对飞行器A的规划航迹a和飞行器B的规划航迹b进行的碰撞检测的流程为:
    S1:按照位置计算算子(Position-Obtain Strategy,SOS),得到自起飞时刻起,每隔时间步Δt,两架飞机分别在航迹a和航迹b上各自将所处的位置点序列和Pa和Pb点序列的元素数Nt由飞行时间短的那条航迹的飞行时间决定。
    S2:从起飞开始,每隔Δt时刻,计算在同一时刻,沿航迹a飞行的飞行器A和沿路径b飞行的飞行器B之间的距离,即从i=0开始到i=Nt,计算pai和pbi的距离|paipbi|,记为
    S3:判断沿各自航迹飞行的两机在某一时刻是否产生冲突:若小于预设的安全距离,即则称飞行器A的路径a与飞行器B的路径b发生一次冲突,即飞行器A的航迹a和飞行器B的航迹b的免碰撞约束违约。
    飞行器航迹间的碰撞检测机制中需要用到位置计算算子SOS,它的流程如下:
    SS1:计算飞行器A的航迹a和飞行器B的航迹b各自的航程距离,分别记为La和Lb,并由得到各机分别在该两航迹上的飞行时间Ta和Tb。
    SS2:计算飞行器A在航迹a和飞行器B在航迹b的上所有航迹段上的飞行时间序列,即所有由一个航迹节点到达下一航迹节点的飞行时间构成的序列:和;再计算各飞行器到达各自航迹点的时刻序列和以航迹a为例,其中ta可由式(37)计算求得:
    tai=Σk=1iTsegak,i=1,2,...,Nw---(37)]]>
    Tsegai=|WaiSA|v,i=1|WaiWai-1|v,i=2:Nw|EAWai|v,i=Nw+1---(38)]]>
    SS3:计算碰撞检测的测试次数Nt,其中celling()为向上取整函数。
    SS4:确定航迹a与航迹b进行碰撞检测的采样位置点序列和
    在位置计算算子中,需要求解pai{xai,yai,zai},其算法流程为:
    SSS1:begin_t记录从每一航迹段的起点到该航迹段的起始采样点的时间,begin_t赋初值为0;k为航迹段下标,k=1:N-1。
    SSS2:当k<=Nw+1时:
    1)计算在第k航迹段上的累计采样点时间det,det=i*Δt+being_t,计算第k航迹段在竖直方向上的偏移角度和在二维平面上的相对于x轴正向的偏移角θk。
    2)当det小于本航迹段(第k段航迹段)的飞行时间Tsegak时,即当det≤tak时,按式(39)计算pai{xai,yai,zai},并且i=i+1:

    否则(即当det>Tsegak时):
    3)判断是否到达最后一个采样点,即当i==Nt+1时,按式40计算pai{xai,yai,zai}:
    xai=Wak.xyai=Wak.yzai=Wak.z---(40)]]>
    否则k=k+1,且being_t=det-tak。
    在上述碰撞检测机制的基础之上,就可以计算问题模型中的协同避撞约束值(式23)。
    本发明中提出种群代表选取机制为合作个体选取机制。
    下面以某个飞行器种群为例,介绍种群代表个体选择的流程:
    S1:选择出种群中所有非支配层的个体,形成待选集合。
    S2:在待选集合中,寻找安全飞行目标frisk=0的个体,如果frisk=0的个体有多个,则转至S3;如果没有frisk=0的个体,即所有个体frisk>0,则进入S4;如果frisk=0的个体只有一个,则该个体作为代表个体,并结束代表个体选择操作;
    S3:对所有frisk=0的个体进行航迹长度flenr的比较,找到,将待选集合中具有最小航迹长度min(flenr)的个体作为代表个体,并结束代表个体选择操作。
    S4:所有frisk>0的个体进行frisk的大小比较,找到待选集合中的最低威胁指数min(frisk)。
    S5:并以min(frisk)对所有frisk>0的个体的frisk进行归一化处理,如个体i对应相对威胁指数为Refriski=friskimin(frisk).]]>
    S6:扔弃REfriski≥V的解,其中V为设定的相对安全阈值。
    S7:在待选集合中保留的个体中进行航迹长度flenr的比较,将待选集合中具有最小航迹长度min(flenr)的个体作为代表个体,并结束代表个体选择操作,并结束代表个体选择操作。
    这样,最终就选出了一个潜在威胁指数较低并且合理大小路径长度的解。此外,种群代表个体选择算子除了用于飞行器航迹协同约束评价外。当跑完最大代数后得到了非支配Pareto解集,也可以使用本算子从非支配Pareto解集中挑选出最终解,作为本飞行器的最终选择航迹。

    关于本文
    本文标题:一种适用于复杂低空下飞行器的路径规划方法.pdf
    链接地址://www.4mum.com.cn/p-6130669.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
  • 重庆时时彩如何看龙虎 pk10怎么算冠军口诀 大乐透2003年36期开奖结果 扑克牌算命 pk10为何前赢后输 万人棋牌官网下载 亿酷棋牌下载 dnf95版本刷哪里最赚钱 2978手机版游戏大厅 废旧金属赚钱不 陕西快乐10分走势表 现在赚钱买卖 北京pk10大享计划软件 免费送彩金娱乐网址 预测大乐透最准的专家 pc蛋蛋28加拿大开奖