融合改进A<sup>*</sup>算法和动态窗口法的全局动态路径规划

程传奇; 郝向阳; 李建胜; 张振杰; 孙国鹏

doi:10.7652/xjtuxb201711019

您当前的位置：

首页 >

文章列表页 >

融合改进A^*算法和动态窗口法的全局动态路径规划

更新时间：2025-07-09

- 融合改进A^*算法和动态窗口法的全局动态路径规划
- Global Dynamic Path Planning Based on Fusion of Improved A^* Algorithm and Dynamic Window Approach
- 西安交通大学学报 2017年51卷第11期页码：137-143
- 作者机构：
  
  信息工程大学导航与空天目标工程学院,郑州,450001
- 作者简介：
- 基金信息：
  
  : 2017-04-04。作者简介: 程传奇(1989—),男,博士生;郝向阳(通信作者),男,教授,博士生导师。基金项目: 国家高技术研究发展计划资助项目(2015AA7034057A);国家自然科学基金资助项目(61173077)
- DOI：10.7652/xjtuxb201711019
  中图分类号： TP242.6
- 网络首发：2017-11-10，
  
  纸质出版：2017
- 稿件说明：
移动端阅览
程传奇, 郝向阳, 李建胜, 等. 融合改进A^*算法和动态窗口法的全局动态路径规划[J]. 西安交通大学学报, 2017,51(11):137-143. DOI: 10.7652/xjtuxb201711019.

Global Dynamic Path Planning Based on Fusion of Improved A^* Algorithm and Dynamic Window Approach[J]. 2017, 51(11): 137-143. DOI: 10.7652/xjtuxb201711019.
程传奇, 郝向阳, 李建胜, 等. 融合改进A^*算法和动态窗口法的全局动态路径规划[J]. 西安交通大学学报, 2017,51(11):137-143. DOI: 10.7652/xjtuxb201711019. DOI：

Global Dynamic Path Planning Based on Fusion of Improved A^* Algorithm and Dynamic Window Approach[J]. 2017, 51(11): 137-143. DOI: 10.7652/xjtuxb201711019. DOI：

摘要

针对移动机器人路径规划全局最优、实时避障的需求

提出了一种融合改进A

算法和动态窗口法的全局动态路径规划方法。首先

基于传统A

算法

结合Manhattan和Euclidean距离

设计了一种优化的启发搜索函数; 然后

利用关键点选取策略

剔除冗余路径点和不必要的转折点; 最后

融合动态窗口法

构造了顾及全局最优路径的评价函数

基于该评价函数

应用动态窗口法

进行实时动态路径规划

在保证规划路径全局最优性的基础上

提高了平滑性及路径规划的局部避障能力。实验结果表明:与传统A

算法相比

所提算法规划的路径更平滑

可实时动态避障

且能输出控制参数

这利于机器人的自动控制; 与动态窗口法相比

所提算法能够保证规划路径的全局最优性

路径长度由28.879 m缩短为22.285 m。该研究对于移动机器人自主导航的应用具有重要的参考价值。

Abstract

To meet the requirements of global optimal and real-time obstacle avoidance in mobile robot path planning

a novel method based on the fusion of improved A

algorithm and dynamic window approach is proposed. Combining Manhattan distance with Euclidean distance

a more appropriate heuristic function is designed for A

algorithm. Then a key node culling scheme is introduced into the traditional A

algorithm to remove the redundant nodes. An evaluation function considering globally optimal path is constructed. The dynamic window approach based on the evaluation function is applied to perform real-time dynamic path planning to guarantee the sm

oothness of path and the local obstacle avoidance ability as holding the global optimality of path. The experimental results demonstrate that compared with traditional A

algorithm

the smoother path is found

the ability of dynamic obstacle avoidance is more obvious and the control parameters for robots are obtained. The proposed method outperforms traditional dynamic window approach in guaranteeing the global optimality of path planning

and the path distance reduces from 28.879 m to 22.285 m.

关键词

Keywords

references

HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths [J]. IEEE Transactions on Systems Science & Cybernetics, 1968, 4(2): 100-107.

STENTZ A. Optimal and efficient path planning for partially known environments [C]∥IEEE International Conference on Robotics and Automation. Piscataway, NJ, USA: IEEE, 1994: 3310-3317.

EELE A J, RICHARDS A. Path-planning with avoidance using nonlinear branch-and-bound optimization [J]. Journal of Guidance Control Dynamics, 2015, 32(2): 384-394.

BHATTACHARYA P, GAVRILOVA M L. Roadmap-based path planning-using the voronoi diagram for a clearance-based shortest path [J]. IEEE Robotics Automation Magazine, 2008, 15(2): 58-66.

KOTHARI M, POSTLETHWAITE I. A probabilistically robust path planning algorithm for UAVs using rapidly-exploring random trees [J]. Journal of Intelligent Robotic Systems, 2013, 71(2): 231-253.

SOLTANI A R, TAWFIK H, GOULERMAS J Y, et al. Path planning in construction sites: performance evaluation of the Dijkstra, A*, and GA search algorithms [J]. Advanced Engineering Informatics, 2002, 16(4): 291-303.

张彪, 曹其新, 王雯珊. 使用三维栅格地图的移动机器人路径规划 [J]. 西安交通大学学报, 2013, 47(10): 57-61.

ZHANG Biao, CAO Qixin, WANG Wenshan. An algorithm for mobile robot path planning based on 3D grid map [J]. Journal of Xi'an Jiaotong University, 2013, 47(10): 57-61.

MONTIEL O, SEPAG'ULVEDA R, OROZCO-ROSAS U. Optimal path planning generation for mobile robots using parallel evolutionary artificial potential field [J]. Journal of Intelligent Robotic Systems, 2015, 79(2): 1-21.

FOX D, BURGARD W, THRUN S. The dynamic window approach to collision avoidance [J]. IEEE Robotics Automation Magazine, 1997, 4(1): 23-33.

SEDER M, PETROVIC I. Dynamic window based approach to mobile robot motion control in the presence of moving obstacles [C]∥IEEE International Conference on Robotics and Automation. Piscataway, NJ, USA: IEEE, 2007: 1986-1991.

GLASIUS R, KOMODA A, GIELEN S C A M. Neural network dynamics for path planning and obstacle avoidance [J]. Neural Networks, 1995, 8(1): 125-133.

朱大奇, 孙兵, 李利. 基于生物启发模型的AUV三维自主路径规划与安全避障算法 [J]. 控制与决策, 2015, 30(5): 798-806.

ZHU Daqi, SUN Bing, LI Li. Algorithm for AUV's 3D path planning and safe obstacle avoidance based on biological inspired model [J]. Control and Decision, 2015, 30(5): 798-806.

雷伟军, 程筱胜, 戴宁, 等. 基于改进遗传算法的多模型加工路径规划 [J]. 机械工程学报, 2014, 50(11): 153-161.

LEI Weijun, CHENG Xiaosheng, DAI Ning, et al. Multi-model machining path planning based on improved genetic algorithm [J]. Journal of Mechanical Engineering, 2014, 50(11): 153-161.

潘杰, 王雪松, 程玉虎. 基于改进蚁群算法的移动机器人路径规划 [J]. 中国矿业大学学报, 2012, 41(1): 108-113.

PAN Jie, WANG Xuesong, CHENG Yuhu. Improved ant colony algorithm for mobile robot path planning [J]. Journal of China University of Mining Technology, 2012, 41(1): 108-113.

王殿君. 基于改进A*算法的室内移动机器人路径规划 [J]. 清华大学学报(自然科学版), 2012, 52(8): 1085-1089.

WANG Dianjun. Indoor mobile-robot path planning based on an improved A* algorithm [J]. Journal of Tsinghua University(Science and Technology), 2012, 52(8): 1085-1089.

刘建华, 杨建国, 刘华平, 等. 基于势场蚁群算法的移动机器人全局路径规划方法 [J]. 农业机械学报, 2015, 46(9): 18-27.

LIU Jianhua, YANG Jianguo, LIU Huaping, et al. Robot global path planning based on ant colony optimization with artificial potential field [J]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(9): 18-27.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

兼顾启停特性和转角时耗的移动机器人路径规划

采用改进灰狼算法的移动机器人路径规划

Baldwin效应的自适应免疫网络规划算法

四足机器人自由步态规划建模与算法实现

引入改进蝠鲼觅食优化算法的水下无人航行器三维路径规划

融合改进A*算法和动态窗口法的全局动态路径规划

Global Dynamic Path Planning Based on Fusion of Improved A* Algorithm and Dynamic Window Approach

DOI：10.7652/xjtuxb201711019

摘要

Abstract

关键词

Keywords

references

融合改进A^*算法和动态窗口法的全局动态路径规划

Global Dynamic Path Planning Based on Fusion of Improved A^* Algorithm and Dynamic Window Approach