面向多值栅格地图的A * 最优路径算法改进
发布时间：2021-04-10 17:15
A*启发算法是最优路径规划问题中最有效的算法之一,在路径规划问题中得到广泛应用。针对多值栅格环境下的最优路径规划的效率问题,对A*算法在搜索策略上做了如下改进:一是提出了两种新的启发函数;二是提出了新的A*双向搜索算法。实验表明改进算法求得的路径为最优路径,搜索效率比传统的Dijkstra算法有显著提升,双向A*算法比单向A*算法效率有明显提高。
【文章来源】：测绘科学技术学报. 2019,36(02)北大核心
【文章页数】：7 页
【部分图文】：
通行成本图1．1新启发函数
Dijkstra算法大幅缩小且具有指向性，主要沿着起点至终点的最优路径进行扩展，原因是加入了终点的启发信息;方法3比方法2的搜索范围更小，搜索范围更收敛于最优路径，原因是对角启发函数携带的启发信息比动态启发函数多;方法4、方法5分别比方法2、方法3具有更小和更收敛的搜索范围，原因是加入了双向搜索算法。图3改进算法相对方法1的搜索点数效率提升比图4改进算法相对方法1的搜索时间效率提升比图5方法3相对于方法2的效率提升比图6方法4相对方法2的效率提升比图7方法5相对方法3的效率提升比图3～图7为各算法的效率提升对比图。图3～图5表明两种新启发函数都使算法效率显著提升。当网格距离较大时，动态启发函数效率提升比达到76%，对角启发函数效率提升比达到82%;且对角启发函数比动态启发函数更有效，当距离较大时，前者比后者效率大约提升20%。由于数据的非随机分布性，导致效率提升比曲线发生波动。从图6和图7可以看出，双向搜索对单向搜索的效率提升比随着起止点网格距离变大而波动性变大。当起止点网格距离较大时，双向搜索效率对于单向搜索明显提升，提升值达到30%左右;当起止点网格距离较小时，前者搜索点数比后者少，但两者时间效率差不多。原因是双向搜索判断是否达到终止条件的时间和搜索栅格时间数量级相近，效率提升比曲线波动大的原因是通行成本数据的非随机分布。图3和图4表明综合改进后的算法(方法4和方法5)比改进前算法的效率有了显著提升。搜索时间效率提升比随着起止点网格距离的增大波动性增大，最后趋于稳定，达到86%左右。3结?
Dijkstra算法大幅缩小且具有指向性，主要沿着起点至终点的最优路径进行扩展，原因是加入了终点的启发信息;方法3比方法2的搜索范围更小，搜索范围更收敛于最优路径，原因是对角启发函数携带的启发信息比动态启发函数多;方法4、方法5分别比方法2、方法3具有更小和更收敛的搜索范围，原因是加入了双向搜索算法。图3改进算法相对方法1的搜索点数效率提升比图4改进算法相对方法1的搜索时间效率提升比图5方法3相对于方法2的效率提升比图6方法4相对方法2的效率提升比图7方法5相对方法3的效率提升比图3～图7为各算法的效率提升对比图。图3～图5表明两种新启发函数都使算法效率显著提升。当网格距离较大时，动态启发函数效率提升比达到76%，对角启发函数效率提升比达到82%;且对角启发函数比动态启发函数更有效，当距离较大时，前者比后者效率大约提升20%。由于数据的非随机分布性，导致效率提升比曲线发生波动。从图6和图7可以看出，双向搜索对单向搜索的效率提升比随着起止点网格距离变大而波动性变大。当起止点网格距离较大时，双向搜索效率对于单向搜索明显提升，提升值达到30%左右;当起止点网格距离较小时，前者搜索点数比后者少，但两者时间效率差不多。原因是双向搜索判断是否达到终止条件的时间和搜索栅格时间数量级相近，效率提升比曲线波动大的原因是通行成本数据的非随机分布。图3和图4表明综合改进后的算法(方法4和方法5)比改进前算法的效率有了显著提升。搜索时间效率提升比随着起止点网格距离的增大波动性增大，最后趋于稳定，达到86%左右。3结?
【参考文献】：
期刊论文
[1]基于A*算法优化的月面巡视器路径规划研究[J]. 王楷文,彭松,刘少创,李海飞. 航天器工程. 2019(01)
[2]一种兼顾全局与局部特性的机器人动态路径规划算法[J]. 张旭,程传奇,郝向阳,李建胜,胡鹏. 测绘科学技术学报. 2018(03)
[3]基于改进A*算法的移动机器人安全路径规划[J]. 张红梅,李明龙,杨乐. 计算机仿真. 2018(04)
[4]基于邻接节点聚合的多层级MQA-A*路径规划算法[J]. 杨肖宁,程承旗,陈波,童晓冲,何静. 地理信息世界. 2018(01)
[5]摩托化机动路径规划的改进A*算法[J]. 刘凯,吕晓华,李爱光,周全. 测绘科学技术学报. 2017(05)
[6]地形坡度对越野机动时间影响分析[J]. 袁仁进,陈刚,王冰冰. 地理信息世界. 2017(06)
[7]计算机兵棋中越野机动路径网络分析[J]. 张欣,李培宁,顾明强. 地理空间信息. 2017(03)
[8]A*算法的改进及并行化[J]. 熊壬浩,刘羽. 计算机应用. 2015(07)
[9]一种利用改进A*算法的无人机航迹规划[J]. 占伟伟,王伟,陈能成,王超. 武汉大学学报(信息科学版). 2015(03)
[10]面向路径优化的变分辨率栅格成本表面模型建模方法[J]. 刘震,余洋,李建松,肖少辉. 测绘学报. 2014(05)
博士论文
[1]无人驾驶车辆运动障碍物检测、预测和避撞方法研究[D]. 辛煜.中国科学技术大学 2014
硕士论文
[1]复杂约束条件下航迹规划方法研究[D]. 董世建.北京理工大学 2016
[2]基于改进A*算法的游戏地图寻径的研究[D]. 周小镜.西南大学 2011
[3]路径规划在车辆导航系统中的应用研究[D]. 田明星.北京交通大学 2009
[4]快速路径寻优的GIS网络数据结构设计及算法研究[D]. 姜艳.复旦大学 2008
[5]越野机动的通道分析模型研究[D]. 张真.解放军信息工程大学 2006
本文编号：3130027
【文章来源】：测绘科学技术学报. 2019,36(02)北大核心
【文章页数】：7 页
【部分图文】：
通行成本图1．1新启发函数
Dijkstra算法大幅缩小且具有指向性，主要沿着起点至终点的最优路径进行扩展，原因是加入了终点的启发信息;方法3比方法2的搜索范围更小，搜索范围更收敛于最优路径，原因是对角启发函数携带的启发信息比动态启发函数多;方法4、方法5分别比方法2、方法3具有更小和更收敛的搜索范围，原因是加入了双向搜索算法。图3改进算法相对方法1的搜索点数效率提升比图4改进算法相对方法1的搜索时间效率提升比图5方法3相对于方法2的效率提升比图6方法4相对方法2的效率提升比图7方法5相对方法3的效率提升比图3～图7为各算法的效率提升对比图。图3～图5表明两种新启发函数都使算法效率显著提升。当网格距离较大时，动态启发函数效率提升比达到76%，对角启发函数效率提升比达到82%;且对角启发函数比动态启发函数更有效，当距离较大时，前者比后者效率大约提升20%。由于数据的非随机分布性，导致效率提升比曲线发生波动。从图6和图7可以看出，双向搜索对单向搜索的效率提升比随着起止点网格距离变大而波动性变大。当起止点网格距离较大时，双向搜索效率对于单向搜索明显提升，提升值达到30%左右;当起止点网格距离较小时，前者搜索点数比后者少，但两者时间效率差不多。原因是双向搜索判断是否达到终止条件的时间和搜索栅格时间数量级相近，效率提升比曲线波动大的原因是通行成本数据的非随机分布。图3和图4表明综合改进后的算法(方法4和方法5)比改进前算法的效率有了显著提升。搜索时间效率提升比随着起止点网格距离的增大波动性增大，最后趋于稳定，达到86%左右。3结?
Dijkstra算法大幅缩小且具有指向性，主要沿着起点至终点的最优路径进行扩展，原因是加入了终点的启发信息;方法3比方法2的搜索范围更小，搜索范围更收敛于最优路径，原因是对角启发函数携带的启发信息比动态启发函数多;方法4、方法5分别比方法2、方法3具有更小和更收敛的搜索范围，原因是加入了双向搜索算法。图3改进算法相对方法1的搜索点数效率提升比图4改进算法相对方法1的搜索时间效率提升比图5方法3相对于方法2的效率提升比图6方法4相对方法2的效率提升比图7方法5相对方法3的效率提升比图3～图7为各算法的效率提升对比图。图3～图5表明两种新启发函数都使算法效率显著提升。当网格距离较大时，动态启发函数效率提升比达到76%，对角启发函数效率提升比达到82%;且对角启发函数比动态启发函数更有效，当距离较大时，前者比后者效率大约提升20%。由于数据的非随机分布性，导致效率提升比曲线发生波动。从图6和图7可以看出，双向搜索对单向搜索的效率提升比随着起止点网格距离变大而波动性变大。当起止点网格距离较大时，双向搜索效率对于单向搜索明显提升，提升值达到30%左右;当起止点网格距离较小时，前者搜索点数比后者少，但两者时间效率差不多。原因是双向搜索判断是否达到终止条件的时间和搜索栅格时间数量级相近，效率提升比曲线波动大的原因是通行成本数据的非随机分布。图3和图4表明综合改进后的算法(方法4和方法5)比改进前算法的效率有了显著提升。搜索时间效率提升比随着起止点网格距离的增大波动性增大，最后趋于稳定，达到86%左右。3结?
【参考文献】：
期刊论文
[1]基于A*算法优化的月面巡视器路径规划研究[J]. 王楷文,彭松,刘少创,李海飞. 航天器工程. 2019(01)
[2]一种兼顾全局与局部特性的机器人动态路径规划算法[J]. 张旭,程传奇,郝向阳,李建胜,胡鹏. 测绘科学技术学报. 2018(03)
[3]基于改进A*算法的移动机器人安全路径规划[J]. 张红梅,李明龙,杨乐. 计算机仿真. 2018(04)
[4]基于邻接节点聚合的多层级MQA-A*路径规划算法[J]. 杨肖宁,程承旗,陈波,童晓冲,何静. 地理信息世界. 2018(01)
[5]摩托化机动路径规划的改进A*算法[J]. 刘凯,吕晓华,李爱光,周全. 测绘科学技术学报. 2017(05)
[6]地形坡度对越野机动时间影响分析[J]. 袁仁进,陈刚,王冰冰. 地理信息世界. 2017(06)
[7]计算机兵棋中越野机动路径网络分析[J]. 张欣,李培宁,顾明强. 地理空间信息. 2017(03)
[8]A*算法的改进及并行化[J]. 熊壬浩,刘羽. 计算机应用. 2015(07)
[9]一种利用改进A*算法的无人机航迹规划[J]. 占伟伟,王伟,陈能成,王超. 武汉大学学报(信息科学版). 2015(03)
[10]面向路径优化的变分辨率栅格成本表面模型建模方法[J]. 刘震,余洋,李建松,肖少辉. 测绘学报. 2014(05)
博士论文
[1]无人驾驶车辆运动障碍物检测、预测和避撞方法研究[D]. 辛煜.中国科学技术大学 2014
硕士论文
[1]复杂约束条件下航迹规划方法研究[D]. 董世建.北京理工大学 2016
[2]基于改进A*算法的游戏地图寻径的研究[D]. 周小镜.西南大学 2011
[3]路径规划在车辆导航系统中的应用研究[D]. 田明星.北京交通大学 2009
[4]快速路径寻优的GIS网络数据结构设计及算法研究[D]. 姜艳.复旦大学 2008
[5]越野机动的通道分析模型研究[D]. 张真.解放军信息工程大学 2006
本文编号：3130027
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3130027.html
