Dynamic Path Planning Based on Bilevel Optimization A* Algorithm and Dynamic Window Method

doi:10.3778/j.issn.1002-8331.2103-0434

Abstract

Abstract:

To meet the needs of mobile robot’s dynamic obstacle avoidance and global optimal path planning in dynamic environment, a path planning algorithm for mobile robot based on the combination of bilevel optimization A* algorithm and dynamic window method is proposed. Based on the global path trajectory obtained by the traditional A* algorithm, firstly, through the first level of global optimization, the slope between the path nodes is calculated, and the key turning points are extracted to greatly reduce the number of path turning points; secondly, through the second level of global optimization, the path intersection is obtained by extending the path segment, and the path turning points are minimized by judging whether the intersection passes through obstacles; finally, the dynamic window method is designed, the problem that the robot is easy to fall into the “concave” and “C” shaped obstacles is solved, the safe distance is ensured, and the global optimal path is selected. The global simulation experiments of traditional A* algorithm, one-level optimization A*, two-level optimization A*, and fusion algorithm are carried out in static and dynamic two-dimensional raster maps. The experimental results show that the first level optimization A* algorithm greatly reduces the number of turning points; the second level optimization A* algorithm reduces the number of turning points to the minimum, but increases the path length by a small margin; the fusion algorithm realizes the robot’s real-time dynamic obstacle avoidance to reach the destination, and is closer to the global optimal planning while ensuring the safe distance.

Key words: path planning, dynamic window method, A* algorithm, fusion algorithm

摘要：

为满足动态环境中移动机器人既要动态避障抵到终点，又要尽可能地做到全局最优的路径规划需求，提出了一种双层优化A*算法与动态窗口法相结合的移动机器人路径规划算法。在传统A*算法求得的全局路径轨迹基础上，首先通过一层全局优化，计算路径节点间斜率，提取关键转折点，大幅度减少路径转折点数量；再通过二层全局优化，延长路径段求得路径交点，判断交点是否通过障碍物的方法，将路径转折点数降到最低；设计动态窗口法的轨迹评价函数，解决了机器人容易陷入“凹”“C”形障碍物的问题，同时保证了障碍物安全距离并选取全局最优的路径轨迹。最后分别在静态与动态的二维栅格地图中对传统A*算法、一层优化A*、二层优化A*以及融合算法进行仿真实验。实验结果表明一层优化A*算法大幅度降低了转折次数；二层优化A*算法将转折点数降到最低，但是路径长度小幅度增加；融合算法实现了机器人实时动态避障抵到终点，而且在保证安全距离的同时更加贴近全局最优规划。

关键词: 路径规划, 动态窗口法, A*算法, 融合算法

ZHAO Wei, WU Ziying. Dynamic Path Planning Based on Bilevel Optimization A* Algorithm and Dynamic Window Method[J]. Computer Engineering and Applications, 2021, 57(22): 295-303.

赵伟，吴子英. 双层优化A*算法与动态窗口法的动态路径规划[J]. 计算机工程与应用, 2021, 57(22): 295-303.

References

[1] 霍凤财，迟金，黄梓健，等.移动机器人路径规划算法综述[J].吉林大学学报（信息科学版），2018，36（6）：639-647.
HUO F C，CHI J，HUANG Z J，et al.Review of path planning for mobile robots[J].Journal of Jilin University（Information Science Edition），2018，36（6）：639-647.
[2] 王永雄，田永永，李璇，等.穿越稠密障碍物的自适应动态窗口法[J].控制与决策，2019，34（5）：927-936.
WANG Y X，TIAN Y Y，LI X，et al.Self-adaptive dynamic window approach in dense obstacles[J].Control and Decision，2019，34（5）：927-936.
[3] 贾会群，魏仲慧，何昕，等.基于改进粒子群算法的路径规划[J].农业机械学报，2018，49（12）：371-377.
JIA H Q，WEI Z H，HE X，et al.Path planning based on improved particle swarm optimization algorithm[J].Transactions of the Chinese Society for Agricultural Machinery，2018，49（12）：371-377.
[4] 刘洋，马建伟，臧绍飞，等.基于融合Bezier优化遗传算法的路径规划[J].控制工程，2021，28（2）：284-292.
LIU Y，MA J W，ZANG S F，et al.Path planning based on genetic algorithm fused with Bezier optimization[J].Control Engineering of China，2021，28（2）：284-292.
[5] 迟旭，李花，费继友.基于改进A*算法与动态窗口法融合的机器人随机避障方法研究[J].仪器仪表学报，2021，42（3）：132-140.
CHI X，LI H，FEI J Y.Research on robot random obstacle avoidance method based on fusion of improved A* algorithm and dynamic window method[J].Chinese Journal of Scientific Instrument，2021，42（3）：132-140.
[6] 李文刚，汪流江，方德翔，等.联合A*与动态窗口法的路径规划算法[J/OL].系统工程与电子技术（2021-04-21）[2021-04-26].http：//kns.cnki.net/kcms/detail/11.2422.TN.20210420.1605.
014.html.
LI W G，WANG L J，FANG D X，et al.Path planning algorithm combining A* with DWA[J/OL].Systems Engineering and Electronics（2021-04-21）[2021-04-26].http：//kns.cnki.net/kcms/detail/11.2422.TN.20210420.1605.014.html.
[7] CARDON A，MARIA J，OMAR D，et al.Determination of the optimal method of bimanual assembly operations with Dijkstra algorithm（or shortest path）[J].Informacion Technologica，2017，28（4）：125-134.
[8] 张恒，何丽，袁亮，等.基于改进双层蚁群算法的移动机器人路径规划[J/OL].控制与决策（2021-01-05）[2021-03-15].https：//doi.org/10.13195/j.kzyjc.2020.0610.
ZHANG H，HE L，YUAN L，et al.Mobile robot path planning using improved double-layer ant colony algorithm[J/OL].Control and Decision（2021-01-05）[2021-03-15].https：//doi.org/10.13195/j.kzyjc.2020.0610.
[9] 程传奇，郝向阳，李建胜，等.融合改进A~*算法和动态窗口法的全局动态路径规划[J].西安交通大学学报，2017，51（11）：137-143.
CHENG C Q，HAO X Y，LI J S，et al.Global dynamic path planning based on fusion of improved A* algorithm and dynamic window approach[J].Journal of Xi’an Jiaotong University，2017，51（11）：137-143.
[10] 卞永明，季鹏成，周怡和，等.基于改进型DWA的移动机器人避障路径规划[J].中国工程机械学报，2021，19（1）：44-49.
BIAN Y M，JI P C，ZHOU Y H，et al.Obstacle avoidance path planning of mobile robot based on improved DWA[J].Chinese Journal of Construction Machinery，2021，19（1）：44-49.
[11] 华洪，张志安，施振稳，等.动态环境下多重A*算法的机器人路径规划方法[J].计算机工程与应用，2021，57（10）：173-180.
HUA H，ZHANG Z A，SHI Z W，et al.Robot path planning method of multiple A* algorithm in dynamic environment[J].Computer Engineering and Applications，2021，57（10）：173-180.
[12] 劳彩莲，李鹏，冯宇.基于改进A~*与DWA算法融合的温室机器人路径规划[J].农业机械学报，2021，52（1）：14-22.
LAO C L，LI P，FENG Y.Path planning of greenhouse robot based on fusion of improved A* algorithm and dynamic window approach[J].Transactions of the Chinese Society for Agricultural Machinery，2021，52（1）：14-22.
[13] 陈娇，陈佳，刘卿.改进A*和动态窗口法的移动机器人路径规划[J/OL].计算机集成制造系统（2020-10-26）[2021-03-15].http：//kns.cnki.net/kcms/detail/11.5946.TP.20201026.
1053.026.html.
CHEN J，CHEN J，LIU Q.Path planning based on improved A* and dynamic window approach for mobile robot[J/OL].Computer Integrated Manufacturing Systems（2020-10-26）[2021-03-15].http：//kns.cnki.net/kcms/detail/11.5946.
TP.20201026.1053.026.html.
[14] 槐创锋，郭龙，贾雪艳，等.改进A*算法与动态窗口法的机器人动态路径规划[J].计算机工程与应用，2021，57（8）：244-248.
HUAI C F，GUO L，JIA X Y，et al.Improved A* algorithm and dynamic window method for robot dynamic path planning[J].Computer Engineering and Applications，2021，57（8）：244-248.
[15] 宋晓茹，任怡悦，高嵩，等.移动机器人路径规划综述[J].计算机测量与控制，2019，27（4）：1-5.
SONG X R，REN Y Y，GAO S，et al.Survey on technology of mobile robot path planning[J].Computer Measurement & Control，2019，27（4）：1-5.
[16] MOLINOS E J，LLAMAZARES á，OCA?A M.Dynamic window based approaches for avoiding obstacles in moving[J].Robotics and Autonomous Systems，2019，118：112-130.