基于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-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 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.

参考文献

[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]. 机械工程学报, 2025, 61(2): 222-235.
[2]	邓建新, 袁邦颐, 黄秋林, 丁度坤, 辛曼玉, 刘光明. 基于工业机器人的复杂曲面磨抛关键技术综述[J]. 机械工程学报, 2024, 60(7): 1-21.
[3]	张伟民, 徐森生, 张月. 基于改进A^*算法的室内巡检机器人路径规划研究[J]. 机械工程学报, 2024, 60(20): 315-326.
[4]	王晓飞, 许家忠, 丁亮, 黄成, 杨怀广, 刘美军. 趋向性锁链式路径规划算法[J]. 机械工程学报, 2024, 60(19): 53-61.
[5]	宋荆洲, 宫兴龙, 段嘉辰, 张腾飞. 可跳跃移动机器人机构设计与跳跃过程控制研究综述[J]. 机械工程学报, 2024, 60(15): 1-17.
[6]	徐文琳, 彭羽, 何智成, 姜潮. 复杂路径规划的机构分区运动学拓扑构型设计[J]. 机械工程学报, 2024, 60(11): 62-73.
[7]	何华, 刘全, 申屠舒展, 宫昭. 轮式多机协同搬运机器人轨迹跟踪控制器设计[J]. 机械工程学报, 2024, 60(11): 145-155.
[8]	闫守鑫, 王伟, 苏鹏飞, 贠超. 大型复杂锻件打磨路径的智能化规划方法[J]. 机械工程学报, 2024, 60(11): 216-225.
[9]	胡林, 杨冬兆, 张新, 章杰, 廖家才. 基于DQP-LMPC的智能车超车换道动态路径规划[J]. 机械工程学报, 2024, 60(10): 171-181.
[10]	聂士达, 刘辉, 廖志昊, 谢雨佳, 项昌乐, 韩立金, 林思豪. 考虑复杂地形的越野环境无人车辆路径规划研究[J]. 机械工程学报, 2024, 60(10): 261-272.
[11]	林晨, 魏洪乾, 荆威, 张幽彤. 汽车功能安全：面向敏感指令攻击场景的自主驾驶车辆路径规划风险缓解控制[J]. 机械工程学报, 2024, 60(10): 302-316.
[12]	普雪洁, 张建辉, 李建勇, 张健楠. 复杂技术系统隐性冲突求解路径规划方法[J]. 机械工程学报, 2024, 60(1): 309-328.
[13]	向红标, 杨大虎, 杨璐, 王收军, 张冕, 黄显, 霍文星. 复杂环境下磁弹性微型游泳机器人的路径规划与识别跟踪[J]. 机械工程学报, 2023, 59(5): 89-99.
[14]	吴宏宇, 牛文栋, 张玉玲, 王树新, 阎绍泽. 水下滑翔机多点探测能耗最低路径的规划方法[J]. 机械工程学报, 2023, 59(5): 156-166.
[15]	刘鹏, 贾寒冰, 张雷, 王震坡. 结构化道路下智能汽车自主换道轨迹规划研究[J]. 机械工程学报, 2023, 59(24): 271-281.