Combined Path Planning Based on Voronoi Skeleton for Mobile Robots

doi:10.3901/JME.2025.05.165

Abstract

Abstract: In response to these problems of excessive turning points, non-smooth motion, and insufficient safety for path planning of mobile robots on grid maps, a combined path planning method based on the Voronoi skeleton is proposed. Firstly, the grid map is transformed into a Voronoi skeleton graph by means of three methods, including Delaunay triangulation, dual Voronoi diagram construction, and adjacency matrix transformation of undirected graph. Secondly, global path planning is conducted using the A* algorithm based on skeleton vertices, followed by optimization of path points according to spatial obstacle avoidance requirements, thus enhancing the safety and refinement of the global path. Furthermore, the velocity sampling space of the DWA algorithm is optimized. Global optimization guidance is introduced through an improved evaluation function to construct a globally guided DWA algorithm. Then local path planning is combined with global path planning by using dynamic target points. Experimental results demonstrate that this combined path planning method possesses navigation safety, path smoothness, and operational efficiency, enabling mobile robot to avoid random dynamic-static obstacles rapidly.

Key words: Voronoi skeleton, A-star algorithm, DWA algorithm, path planning, mobile robot

CLC Number:

TP242

WU Xing, LI Yangzhi, ZANG Tiegang, MENG Zhaoxu, CHEN Junzhe, WANG Chentao. Combined Path Planning Based on Voronoi Skeleton for Mobile Robots[J]. Journal of Mechanical Engineering, 2025, 61(5): 165-177.

References

[1] 段书用，王启帆，韩旭，等. 具有确保安全距离的A*路径优化方法[J]. 机械工程学报，2020，56(18)：205-215. DUAN Shuyong，WANG Qifan，HAN Xu，et al. Improved A-star algorithm for safety insured optimal path with smoothed corner turns[J]. Journal of Mechanical Engineering，2020，56(18)：205-215.
[2] TAO Y，DUAN L，GAO H，et al. Heuristic expanding disconnected graph：a rapid path planning method for mobile robots[J]. Chinese Journal of Mechanical Engineering，2024，37(1)：32.
[3] XUE W，YING R，GONG Z，et al. SLAM based topological mapping and navigation[C]// 2020 IEEE/ION Position，Location and Navigation Symposium (PLANS). IEEE，2020：1336-1341.
[4] ZOU Q，SUN Q，CHEN L，et al. A comparative analysis of LiDAR SLAM-Based indoor navigation for autonomous vehicles[J]. IEEE Transactions on Intelligent Transportation Systems，2022，23(7)：6907-6921.
[5] LIU L X，WANG X，YANG X，et al. Path planning techniques for mobile robots：review and prospect[J]. Expert Systems with Applications，2023：120254.
[6] 王殿君. 基于改进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.
[7] DUCHON F，BABINEC A，KAJAN M，et al. Path planning with modified a star algorithm for a mobile robot[J]. Modelling of Mechanical and Mechatronic Systems，2014，96：59-69.
[8] LUO M，HOU X，YANG J. Surface optimal path planning using an extended Dijkstra algorithm[J]. IEEE Access，2020，8：147827-147838.
[9] 蒋林，李峻，马先重，等. 一种改进骨架提取的Voronoi路径规划[J]. 机械工程学报，2020，56(13)：138-148. JIANG Lin，LI Jun，MA Xianzhong，et al. Voronoi path planning based on improved skeleton extraction[J]. Journal of Mechanical Engineering，2020，56(13)：138-148.
[10] WANG J K，MENG M Q H. Optimal path planning using generalized Voronoi graph and multiple potential functions[J]. IEEE Transactions on Industrial Electronics，2020，67(12)：10621-10630.
[11] YANG W L，WU P，ZHOU X Q，et al. Improved artificial potential field and dynamic window method for amphibious robot fish path planning[J]. Applied Sciences，2021，11(5)：2114.
[12] FOX D，BURGARD W，THRUN S. The dynamic window approach to collision avoidance[J]. IEEE Robotics & Automation Magazine，1997，4(1)：23-33.
[13] 巩慧，倪翠，王朋，等. 基于Dijkstra算法的平滑路径规划方法[J]. 北京航空航天大学学报，2024，50(2)：535-541. GONG Hui，NI Cui，WANG Peng，et al. A Smooth path planning method based on Dijkstra algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics，2024，50(2)：535-541.
[14] 朱建阳，张旭阳，蒋林，等. 基于骨架关键点重规划的Voronoi图法路径规划[J]. 农业机械学报，2022，53(3)：215-224. ZHU Jianyang，ZHANG Xuyang，JIANG Lin，et al. Voronoi diagram path planning based on skeleton key points re-planning[J]. Transactions of the Chinese Society for Agricultural Machinery，2022，53(3)：215-224.
[15] 程传奇，郝向阳，李建胜，等. 融合改进A*算法和动态窗口法的全局动态路径规划[J]. 西安交通大学学报，2017，51(11)：137-143. CHENG Chuanqi，HAO Xiangyang，LI Jiansheng，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.
[16] 邹文，韩丙辰，李鹏飞，等. 融合改进A*算法和优化动态窗口法的路径规划[J]. 计算机集成制造系统，2024，30(1)：184-195. ZOU Wen，HAN Bingchen，LI Pengfei，et al. Path planning by integrating improved A* algorithm and optimized dynamic window approach[J]. Computer Integrated Manufacturing System，2024，30(1)：184-195.
[17] 武星，杨俊杰，汤凯，等. 面向复合地图的移动机器人分层路径规划[J]. 中国机械工程，2023，34(5)：563-575. WU Xing，YANG Junjie，TANG Kai，et al. Hierarchical path planning for mobile robots based on hybrid map[J]. China Mechanical Engineering，2023，34(5)：563-575.
[18] LAU B，SPRUNK C，BURGARD W. Efficient grid-based spatial representations for robot navigation in dynamic environments[J]. Robotics and Autonomous Systems，2013，61(10)：1116-1130.
[19] PERUMAL L. New approaches for Delaunay triangulation and optimisation[J]. Heliyon，2019，5(8)：e02319.
[20] FORTUNE S. Voronoi diagrams and Delaunay triangulations[M]. Handbook of discrete and computational geometry. Chapman and Hall/CRC，2017.
[21] SUN Y，WANG W，XU M，et al. Local path planning for mobile robots based on fuzzy dynamic window algorithm[J]. Sensors，2023，23(19)：8260.
[22] SHANG W，LIU J，NING R X，et al. Computational path planner for product assembly in complex environments[J]. Chinese Journal of Mechanical Engineering，2013，26(2)：282-292.