欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2017103459874
申请人: 桂林电子科技大学
专利类型:发明专利
专利状态:未下证
专利领域: 测量;测试
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于规则网格DEM数据的路径规划新方法,其特征在于,包括如下步骤:(1)DA*算法中基于指数函数构建新的完备性函数g(n);

针对灾害救援对坡度和距离的路径需求,基于DEM数据,以坡度和距离设计DA*算法新的完备性函数g(n),具体如下:g(n)=d(n)+p(sg(n))  (1)

其中,n为当前点,d(n)是以当前点与上一点的距离的函数,sg(n)为当前点的坡度,p(sg(n))是以当前点坡度为参数的函数;

将指数函数引入坡度函数,将空间路径的计算引入距离函数,并以不同权重调整距离函数和坡度函数对完备性函数的影响,则g(n)的新函数构造如下:g(n)=q×DG(n,n-1)+(1-q)×esg(n)  (2)其中,q为调整距离函数与坡度函数的权重;DG(n,n-1)为当前点n与其上一点n-1的空间路径单元距离;sg(n)是当前点n的坡度;

所述空间路径的距离计算,以点间的高程差和平面距离计算,DG(n,n-1)计算公式为:其中,H(n)为当前点的高程,H(n-1)为上一点的高程;L(n,n-1)是平面路径单元距离,其是空间路径在平面上的投影,受DEM数据分辨率的影响;

利用大地坐标,L(n,n-1)的计算公式如下:

其中,(Xn,Yn)、(Xn-1,Yn-1)分别为当前点n与上一点n-1的大地坐标,X、Y分别为从DEM数据中所获取相关点的经度和纬度值;R=6371393米,为地球半径;

所述当前点n的坡度sg(n)计算公式为:

其中,fx、fy分别为当前点东西方向的高程变化率和南北方向的高程变化率;在规则网格的DEM数据中,通常以中心点周围3×3的移动窗格计算fx、fy;fx、fy的计算方法采用三阶不带权差分模型的坡度计算方法,具体如下:其中,zi为窗格编号,g为窗格间距,是规则网格DEM数据中一个单元格的长度,单位为米,其随着DEM数据分辨率的不同而不同;

(2)基于DEM分辨率自适应的完备性函数优化;

以实数a替换公式(2)中的指数函数esg(n)的底数e,则g(n)变换如下:g(n)=DG(n,n-1)+asg(n)  (7)

为保证引入底数a后能够满足距离和坡度的约束关系,建立一个距离与坡度的关联表达式如下:DG(n,n-1)=masg(n)  (8)

其中,m为调整距离与坡度的比例系数;

在距离尽可能小,坡度尽可能大的情况下,若公式(8)成立,则a在公式(7)能够平衡距离与坡度对g(n)的影响;

在公式(8)中,坡度取坡度阈值S0;令m=10,坡度函数值远大于距离函数值距离;距离则取平面路径单位的距离,其小于等于对应的空间路径单位距离,以D0表示平面路径单位的平均距离,则公式(8)变换如下:平面路径单位只包含了南北、东西方向 与对角线方向 在规则网格中,东西与南北方向上的平面路径单位距离相等,而对角线方向则相互之间相等,因此,D0的计算方法就是求南北或东西方向 与对角线方向 的平面单位路径距离的均值,即:针对实际的规则网格DEM数据,任取一个点都可以计算出相应DEM数据分辨率下对应的D0值,则: 将a代入公式(7),此时,公式(3)计算的距离、公式(5)计算的坡度和底数a,都随实际环境的DEM数据变化而变化,从而使得完备性函数g(n)实现DEM数据分辨率的自适应性;

(3)路径的可通行性评估

针对所选择数字地图区域的地表要素数据,将地表障碍对应坐标的节点标注为地表障碍;在路径选择中,先判断相邻节点是否为地表障碍,若是则直接加入到DA*算法关闭列表,否则根据公式(7)计算各节点的代价;

(4)构造DA*算法的新启发性函数h(n);

为保持与完备性函数g(n)的一致性,基于距离和坡度的约束关系,构造DA*算法的新启发性函数h(n)如下:h(n)=DH(n,end)+ash(n,end)  (10)其中,DH(n,end)为当前点与终点的距离,其计算公式同公式(3),H(n)、H(end)分别为当前点与终点的高程;DH(n,end)中的L(n,end)计算采用公式(4);sh(n,end)表示当前点到终点的坡度,其计算公式为:其中,L(n,end)计算同样采用公式(4);

(5)基于权重动态调整的DA*寻路新算法优化;

基于公式(7)和公式(10),DA*算法评价函数如下:

计算搜索深度,其以当前点与起点的曼哈顿距离计算,以SD(n)表示当前点n与起点的搜索深度,则SD(n)=|Xn-X0|+|Yn-Y0|,其中(X0,Y0)为起点坐标,(Xn,Yn)为当前点坐标,该距离越大,则当前点离起点越远,即搜索深度越深;

以L表示起点与终点的曼哈顿距离,则有L=|Xe-X0|+|Ye-Y0|,其中(X0,Y0)为起点坐标,(Xe,Ye)为终点坐标;

以DEMXY表示DEM数据横纵距离,以(XLB,YLB)表示DEM数据区域中左下角点的坐标,以(XRB,YRB)表示右下角点的坐标,以(XRU,YRU)表示右上角点的坐标,以(XLU,YLU)表示左上角点的坐标,则:DEMXY=|XRB-XLB|+|YLU-YLB|;

由于搜索路径的起点与终点位于DEM数据对应的区域内部,因此,起点与终点的曼哈顿距离L与DEM数据横纵距离DEMXY满足关系:L≤DEMXY;

调整DA*算法中g(n)和h(n)的权重,进一步提高公式(12)DA*算法的效率,以q1、q2分别表示DA*算法中g(n)和h(n)的权重,且q1+q2=1,则有:f(n)=q1×g(n)+q2×h(n)  (13)

以q0表示初始权重,且q0∈[0.5,0.9],考虑到起点到终点的路径越长,数据量越大,初始权重也需要相应加大,则令:其中,L为起点与终点的曼哈顿距离,DEMXY为DEM数据横纵距离,以Δq表示随着搜索深度的增加,权重变化的增量,令:

其中,L为起点与终点的曼哈顿距离,SD(n)为当前点n的搜索深度;

基于初始权重q0与权重增量Δq,令q2=q0-Δq;q1=1-q0+Δq,将权重信息代入公式(13),则新的路径规划DA*算法的评估函数如下:(6)在实际环境中,基于DEM数据和设置的坡度阈值,计算出算法中的各个参数后,根据公式(16)可以快速搜索出一条从起点到终点的合适路线。