Path Planning Algorithm Based on Dynamic Obstacle Movement Information

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

Abstract

Abstract: The traditional path planning algorithm can only calculate the optimal path in the environment where the position of obstacles does not change. However, with the popularity of robots in dynamic environments such as shopping malls, hospitals and banks, traditional path planning algorithms are prone to collision with dynamic obstacles. Therefore, the robot path planning algorithm with random dynamic obstacles needs to be further improved. Therefore, the robot path planning algorithm under the condition of random dynamic obstacles needs to be further improved. In order to solve the robot path planning problem in dynamic environment, an improved dynamic window approach is proposed to solve the robot path planning problem in dynamic environment, and it is combined with the optimization A* algorithm to realize the global optimal path planning. In the global path planning, the optimal A* algorithm is used to solve the optimal path. In local path planning, the speed of dynamic obstacles is used as a priori information, and the evaluation function of the traditional dynamic window approach is expanded to realize autonomous and intelligent obstacle avoidance of the robot in a dynamic environment. Experiments show that the algorithm can realize real-time dynamic obstacle avoidance based on the global optimal path, which is specifically manifested in reducing the risk of collision without interfering with dynamic obstacles, making intelligent obstacle avoidance and making the path smoother, shorter and faster.

Key words: dynamic obstacle avoidance, dynamic window approach, A* algorithm, obstacle prediction, path planning

摘要： 传统的路径规划算法只能在障碍物不发生位置变化的环境中计算最优路径。但是随着机器人在商场、医院、银行等动态环境下的普及，传统的路径规划算法容易与动态障碍物发生碰撞等危险。因此，关于随机动态障碍物条件下的机器人路径规划算法需要得到进一步改善。为了解决在动态环境下的机器人路径规划问题，提出了一种融合机器人与障碍物运动信息的改进动态窗口法来解决机器人在动态环境下的局部路径规划问题，并且与优化A*算法相结合来实现全局最优路径规划。主要内容体现为：在全局路径规划上，采用优化A*算法求解最优路径。在局部路径规划上，以动态障碍物的速度作为先验信息，通过对传统动态窗口法的评价函数进行扩展，实现机器人在动态环境下的自主智能避障。实验证明，该算法可以实现基于全局最优路径的实时动态避障，具体表现为可以在不干涉动态障碍物的条件下减少碰撞风险、做出智能避障且路径更加平滑、长度更短、行驶速度更快。

关键词: 动态避障, 动态窗口法, A*算法, 障碍物预测, 路径规划

FENG Shuo, JI Xianyou, CHENG Bo, HAN Qidong, YU Shaowei. Path Planning Algorithm Based on Dynamic Obstacle Movement Information[J]. Computer Engineering and Applications, 2022, 58(21): 279-285.

封硕, 吉现友, 程博, 韩启东, 于少伟. 融合动态障碍物运动信息的路径规划算法[J]. 计算机工程与应用, 2022, 58(21): 279-285.

References

[1] FOX D，BURGARD W，THRUN S.The dynamic window approach to collision avoidance[J].IEEE Robotics & Automation Magazine，2002，4（1）：23-33.
[2] CAO P，FAN Z，GAO R X，et al.A focal any-angle path-finding algorithm based on a* on visibility graphs[J].arXiv：1706.03144，2017.
[3] ZHANG Y，LI L L，LIN H C，et al.Development of path planning approach based on improved A-star algorithm in AGV system[C]//Third International Conference on IoT as a Service，2017.
[4] CHENG C，HAO X，LI J，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.
[5] FU B，CHEN L，ZHOU Y，et al.An improved A* algorithm for the industrial robot path planning with high success rate and short length[J].Robotics and Autonomous Systems，2018，106.
[6] 刘子豪，赵津，刘畅，等.基于改进A*算法室内移动机器人路径规划[J].计算机工程与应用，2021，57（2）：186-190.
LIU Z H，ZHAO J，LIU C，et al.Path planning of indoor mobile robot based on improved A* algorithm[J].Computer Engineering and Applications，2021，57（2）：186-190.
[7] 陈秋莲，郑以君，蒋环宇，等.基于神经网络改进粒子群算法的动态路径规划[J].华中科技大学学报（自然科学版），2021，49（2）：51-55.
CHEN Q L，ZHENG Y J，JIANG H Y，et al.Improved particle swarm optimization algorithm based on neural network for dynamic path planning[J].Journal of Huazhong University of Science and Technology（Natural Science Edition），2021，49（2）：51-55.
[8] 王晓燕，吕金豆.基于改进A*势场法的机器人动态路径规划研究[J].制造业自动化，2021，43（1）：83-87.
WANG X Y，LYU J D.Research on robot dynamic path planning based on improved A* and artificial potential field method[J].Manufacturing Automation，2021，43（1）：83-87.
[9] 陈劲峰，黄卫华，章政，等.动态环境下基于改进人工势场法的路径规划算法[J].组合机床与自动化加工技术，2020（12）：6-9.
CHEN J F，HUANG W H，ZHANG Z，et al.Path planning algorithm based on improved artificial potential field method in dynamic environment[J].Modular Machine Tool and Automated Machining Technology，2020（12）：6-9.
[10] 华洪，张志安，施振稳，等.动态环境下多重A*算法的机器人路径规划方法[J].计算机工程与应用，2021，57（10）：173-180.
HUA H，ZHANG Z A，SHI Z W，et al.Robot path planning method of multiple A* algorithms in dynamic environment[J].Computer Engineering and Applications，2021，57（10）：173-180.
[11] 张艳，张明路，蒋志宏，等.动态环境下移动机器人路径规划的研究[J].合肥工业大学学报（自然科学版），2020，43（10）：1297-1306.
ZHANG Y，ZHANG M L，JIANG Z H，et al.Research on path planning of mobile robot in dynamic environment[J].Journal of Hefei University of Technology（Natural Science Edition），2020，43（10）：1297-1306.
[12] 吴飞龙，郭世永.融合改进A*和动态窗口法的AGV动态路径规划[J].科学技术与工程，2020，20（30）：12452-12459.
WU F L，GUO S Y.AGV dynamic path planning of AGV based on improved A* and dynamic window approach[J].Science Technology and Engineering，2020，20（30）：12452-12459.
[13] MOLINOS E J，LLAMAZARES N，OCAA M.Dynamic window based approaches for avoiding obstacles in moving[J].Robotics and Autonomous Systems，2019，118.
[14] SARANRITTICHAI P，NIPARNAN N，SUDSANG A.Robust local obstacle avoidance for mobile robot based on dynamic window approach[C]//International Conference on Electrical Engineering/Electronics，2013.
[15] RANDHAVANE T，BERA A，KUBIN E，et al.Pedestrian dominance modeling for socially-aware robot navigation[C]//2019 International Conference on Robotics and Automation（ICRA），2019.
[16] JAN Q H，KLEIN S，BERNS K.Safe and efficient navigation of an autonomous shuttle in a pedestrian zone[C]//Advances in Service and Industrial Robotics，2019：267-274.