基于Voronoi骨架的移动机器人融合路径规划

doi:10.3901/JME.2025.05.165

机械工程学报 ›› 2025, Vol. 61 ›› Issue (5): 165-177.doi: 10.3901/JME.2025.05.165

扫码分享

基于Voronoi骨架的移动机器人融合路径规划

武星¹, 李杨志¹, 臧铁钢¹, 孟昭旭², 陈俊哲¹, 王晨涛¹

1. 南京航空航天大学机电学院南京 210016;
2. 中国兵器工业第二〇八研究所北京 102202

收稿日期:2024-03-28 修回日期:2024-07-05 出版日期:2025-03-05 发布日期:2025-04-15
作者简介:武星(通信作者)，男，1982年出生，博士，研究员，硕士研究生导师。主要研究方向为移动机器人感知定位与导航控制。E-mail：wustar5353@nuaa.edu.cn;李杨志，男，2000年出生，硕士研究生。主要研究方向为移动机器人路径规划与控制。E-mail：Liyz13193439079@163.com
基金资助:
国防基础科研计划重点项目(JCKY2022209B001)和江苏高校“青蓝工程”优秀青年骨干教师项目(2022)资助项目。

Combined Path Planning Based on Voronoi Skeleton for Mobile Robots

WU Xing¹, LI Yangzhi¹, ZANG Tiegang¹, MENG Zhaoxu², CHEN Junzhe¹, WANG Chentao¹

1. College of Mechanical & Electrical Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 210016;
2. No. 208 Research Institute of China Ordnance Industries, Beijing 102202

Received:2024-03-28 Revised:2024-07-05 Online:2025-03-05 Published:2025-04-15

摘要/Abstract

摘要： 针对栅格地图下移动机器人路径规划存在路径拐点多、运行不平滑、安全性不高等问题，提出一种基于Voronoi骨架的融合路径规划方法。首先采用Delaunay三角剖分、对偶Voronoi图构造及无向图邻接矩阵变换等方法将栅格地图变换为Voronoi骨架图。其次基于骨架顶点使用A*算法进行全局路径规划，并根据空间避障需求进行路径点优化，提高全局路径的安全性与精炼性。再次优化DWA算法速度采样空间，通过引入全局优化引导改进评价函数，构建全局引导型DWA算法，并采用动态目标点将局部路径规划与全局规划路径进行融合。实验结果表明，该融合路径规划方法具有导航安全性、路径平滑性和运行高效性，可使移动机器人快速规避随机动-静态障碍物。

关键词: Voronoi骨架图, A*算法, DWA算法, 路径规划, 移动机器人

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

中图分类号:

TP242

武星, 李杨志, 臧铁钢, 孟昭旭, 陈俊哲, 王晨涛. 基于Voronoi骨架的移动机器人融合路径规划[J]. 机械工程学报, 2025, 61(5): 165-177.

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.

导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks

链接本文: http://www.cjmenet.com.cn/CN/10.3901/JME.2025.05.165

http://www.cjmenet.com.cn/CN/Y2025/V61/I5/165

参考文献

[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.

基于Voronoi骨架的移动机器人融合路径规划

Combined Path Planning Based on Voronoi Skeleton for Mobile Robots

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	顾连睿, 郭国强, 江仁政, 毋天歌, 柯帅, 孔志学, 赵欢. 薄壁复杂结构的机器人打磨路径规划和力位控制技术现状与发展[J]. 机械工程学报, 2026, 62(5): 117-132.
[2]	林松, 戴建生, 宋屹峰, 王洪光, 袁兵兵. 具有可重构躯干的轮式移动机器人曲面运动特性分析[J]. 机械工程学报, 2026, 62(5): 168-181.
[3]	赵浩宇, 侯鹏帅, 陈星全, 邵宇乐, 董奇, 陈杰. 非结构化地形环境下移动机器人导航[J]. 机械工程学报, 2026, 62(3): 396-406.
[4]	张志勇, 姜志昊, 胡林, 黄彩霞. 面向连续弯道的改进人工势场建模与动态避障路径规划[J]. 机械工程学报, 2026, 62(2): 271-282.
[5]	杨秀建, 袁志豪. 基于交错式栅格粒度地图的非平坦地形环境下无人车辆路径规划[J]. 机械工程学报, 2026, 62(2): 313-328.
[6]	陈祉旭, 陈远航, 李晨星, 杨春利. 复杂叶片修复的电弧熔丝沉积姿态控制方法研究[J]. 机械工程学报, 2025, 61(22): 47-56.
[7]	姚静, 李曼迪, 张熙堃, 郭琪, 李想, 张昊. 增材制造流道低压损短路径设计优化方法[J]. 机械工程学报, 2025, 61(22): 271-281.
[8]	李通甲, 臧鹏翔, 郭为忠. 新型磁吸附轮式机器人定位、规划与控制算法[J]. 机械工程学报, 2025, 61(21): 60-74.
[9]	赵靖, 王伟达, 杨超, 李颖, 项昌乐, 向真, 昌磊. 一种兼顾运行距离与能耗的飞行车辆多模态任务路线规划方法[J]. 机械工程学报, 2025, 61(2): 222-235.
[10]	史羽胜, 张明路, 张小俊, 焦世龙, 焦鑫, 李满宏. 可变形轮腿复合机器人优化设计与越障性能[J]. 机械工程学报, 2025, 61(11): 45-56.
[11]	邓建新, 袁邦颐, 黄秋林, 丁度坤, 辛曼玉, 刘光明. 基于工业机器人的复杂曲面磨抛关键技术综述[J]. 机械工程学报, 2024, 60(7): 1-21.
[12]	张伟民, 徐森生, 张月. 基于改进A^*算法的室内巡检机器人路径规划研究[J]. 机械工程学报, 2024, 60(20): 315-326.
[13]	王晓飞, 许家忠, 丁亮, 黄成, 杨怀广, 刘美军. 趋向性锁链式路径规划算法[J]. 机械工程学报, 2024, 60(19): 53-61.
[14]	宋荆洲, 宫兴龙, 段嘉辰, 张腾飞. 可跳跃移动机器人机构设计与跳跃过程控制研究综述[J]. 机械工程学报, 2024, 60(15): 1-17.
[15]	徐文琳, 彭羽, 何智成, 姜潮. 复杂路径规划的机构分区运动学拓扑构型设计[J]. 机械工程学报, 2024, 60(11): 62-73.