基于射线模型的改进全局路径规划算法

doi:10.12263/DZXB.20210307

电子学报 ›› 2022, Vol. 50 ›› Issue (3): 548-556.DOI: 10.12263/DZXB.20210307

基于射线模型的改进全局路径规划算法

蒋林¹^,², 方东君¹, 周和文³, 黄惠保³

^1.武汉科技大学冶金装备及其控制教育部重点实验室, 湖北武汉 430081
^2.武汉科技大学机器人与智能系统研究院，湖北武汉 430081
^3.珠海市一微半导体有限公司，广东珠海 519000

收稿日期:2021-03-04 修回日期:2021-03-19 出版日期:2022-03-25
- 作者简介:
- 蒋林男，1976年12月生于湖北荆门.现为武汉科技大学教授、博士生导师.主持在研国家重点研发计划项目，完成国家自然科学基金及省部级项目多项.在国内外发表学术论文SCI/EI论文40余篇.E-mail:jianglin76@wust.edu.cn
  方东君（通讯作者）男，1996年10月生于重庆，硕士.主要研究方向为单目视觉移动机器人导航.E-mail:729851238@qq.com
  周和文男，1981年出生于广东湛江.现为珠海市一微半导体有限公司产品总监、武汉科技大学兼职教授，主要研究方向为室内移动机器人定位与同步建图、导航规划、运动控制等.E-mail:howen@amicro.com.cn
  黄惠保男，1986年生于广东珠海.现为珠海一微半导体视觉算法工程师，主要研究方向为机器人SLAM、导航.E-mail:huibao.huang@amicro.com.cn
- 基金资助:
- 国家重点研发计划项目 (2019YFB1310000); 武汉市应用基础前沿项目 (2019010701011404); 湖北省重点研发计划项目 (2020 BAB098)

Improved Global Path Planning Algorithm Based on Ray Model

JIANG Lin¹^,², FANG Dong-jun¹, ZHOU He-wen³, HUANG Hui-bao³

^1.Key Laboratory of Metallurgical Equipment and Control Technology, Wuhan University of Science and Technology, Wuhan, Hubei 430081, China
^2.Institute of Robotics and Intelligent Systems, Wuhan University of Science and Technology, Wuhan, Hubei 430081, China
^3.Zhuhai A Micro Semiconductor Co. Ltd., Zhuhai, Guangdong 519000, China

Received:2021-03-04 Revised:2021-03-19 Online:2022-03-25 Published:2022-03-25
- Supported by:
- Program of National Key Research and Development Program of China (2019YFB1310000); Applied Fundamental Frontier Project of Wuhan (2019010701011404); Key Research and Development Project of Hubei Province (2020 BAB098)

摘要/Abstract

摘要：

针对目前服务于移动机器人的全局路径规划算法存在拐点多、耗时长或递归计算复杂等问题，本文提出一种基于射线模型的改进全局路径搜索算法.利用形态学滤波处理障碍物栅格地图，并引入碰撞估值增加靠近障碍物的栅格的代价值，形成梯度代价栅格地图.结合射线模型从起点向终点进行射线搜索，并在搜索过程中通过逆向优化算法优化路径.通过实验证明该全局路径规划算法比A*算法拥有更好的平滑性、灵活性、稳定性以及更短的路程，且搜索速度比A*快50%，移动机器人可以更安全、简洁的路径向目标点移动.

关键词: 全局路径规划, 射线模型, 逆向优化, 移动机器人, 改进A*算法

Abstract:

Aiming at the problems of many inflection points, long time consuming and complex recursive calculation in the global path planning algorithms currently used for mobile robots, an improved global path search algorithm based on ray model is proposed. Morphological filtering is used to process the raster map of obstacles, and collision estimation is introduced to increase the generation value of the raster near the obstacles, and the gradient cost raster map is formed. Combined with the ray model, ray search is carried out from the beginning to the end, and the path is optimized by the inverse optimization algorithm during the search process. Experiments show that the global path planning algorithm has better smoothness, flexibility， and stability. Our algorithm not only has shorter moving distance, but also has 50% faster search speed than A* algorithm. The mobile robot can move to the target point in a safer and simpler path.

Key words: global path planning, ray model, reverse optimization, mobile robot, improved A* algorithm

中图分类号:

TP242.6

蒋林, 方东君, 周和文, 等. 基于射线模型的改进全局路径规划算法[J]. 电子学报, 2022, 50(3): 548-556.

Lin JIANG, Dong-jun FANG, He-wen ZHOU, et al. Improved Global Path Planning Algorithm Based on Ray Model[J]. Acta Electronica Sinica, 2022, 50(3): 548-556.

图/表 17

参考文献 20

1	化建宁, 赵忆文, 等. 一种新的移动机器人全局路径规划算法[J]. 机器人, 2006, 28(6): 593-597.
	HUAJian-ning, ZHAOYi-wen, et al. A new global path planning algorithm for mobile robot[J]. Robot, 2006, 28(6): 593-597. (in Chinese)
2	劳彩莲, 李鹏, 等. 基于改进A*与DWA算法融合的温室机器人路径规划[J]. 农业机械学报, 2021, 52(1): 14-22.
	LAOCai-lian, LIPeng, et al. 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. (in Chinese)
3	王晓燕, 吕金豆. 基于改进A*势场法的机器人动态路径规划研究[J]. 制造业自动化, 2021, 43(1): 83-87.
	WANGXiao-yan, Jin-douLÜ. Research on robot dynamic path planning based on improved A* and artificial potential field method[J]. Manufacturing Automation, 2021, 43(1): 83-87. (in Chinese)
4	马小陆, 梅宏. 基于改进势场蚁群算法的移动机器人全局路径规划[J]. 机械工程学报, 2021, 57(1): 19-27.
	MAXiao-lu, MEIHong. Global path planning for mobile robots based on improved potential field ant colony algorithm [J]. Journal of Mechanical Engineering, 2021, 57(1): 19-27. (in Chinese)
5	赵珊珊, 何宁, 等. 基于SIFT特征的铁路扣件状态检测算法[J]. 传感器与微系统, 2018, 37(11): 148-150, 154.
	ZHAOShan-shan, HENing, et al. Railway fastener state detection algorithm based on SIFT feature [J]. Transducer and Microsystem Technologies, 2018, 37(11): 148-150, 154. (in Chinese)
6	蒋林, 向超, 等. 加载语义似然估计的粒子滤波重定位[J]. 电子学报, 2021, 49(2): 315-323.
	JIANGLin, XIANGChao, et al. Particle filter relocation with semantic likelihood estimation[J]. Acta Electronica Sinica, 2021, 49(2): 315-323. (in Chinese)
7	LVT Z, FENGM Y. A smooth local path planning algorithm based on modified visibility graph[J]. Modern Physics Letters B, 2017, 31(19-21): 17400917.
8	程传奇, 郝向阳, 等. 融合改进A*算法和动态窗口法的全局动态路径规划[J]. 西安交通大学学报, 2017, 51(11): 137-143.
	CHENGChuan-qi, HAOXiang-yang, et al. Global dynamic path planning based on improved A* algorithm and dynamic window method [J]. Xi'an Jiaotong University Xuebao, 2017, 51(11): 137-143. (in Chinese)
9	张家旭, 周时莹, 等. 基于高斯伪谱法的汽车弯道超车路径规划与跟踪控制[J]. 天津大学学报(自然科学与工程技术版), 2021, 54(04): 397-404.
	ZHANGJia-xu, ZHOUShi-ying, et al. Path planning and tracking control of vehicle overtaking on curves based on gaussian pseudo-spectral method[J]. Journal of Tianjin University (Science And Technology), 2021, 54(04): 397-404. (in Chinese)
10	马小陆, 梅宏. 基于JPS策略的ACS移动机器人全局路径规划[J]. 机器人, 2020, 42(04): 494-502.
	MAXiao-lu, MEIHong. Global path planning of ACS mobile robot based on JPS strategy [J]. Robot, 2020, 42(04): 494-502. (in Chinese)
11	张哲, 吴剑, 等. 基于改进A*算法的多无人机协同战术规划[J]. 兵工学报, 2020, 41(12): 2530-2539.
	ZHANGZhe, WUJian, et al. Cooperative tactical planning for Multi-UAVs based on improved A* algorithm[J]. Acta Armamentarii, 2020, 41(12): 2530-2539. (in Chinese)
12	王洪斌, 郝策, 等. 基于A*算法和人工势场法的移动机器人路径规划[J]. 中国机械工程, 2019, 30(20): 2489-2496.
	WANGHong-bin, HAOCe, et al. Path planning of mobile robot based on A* algorithm and artificial potential field method[J]. China Mechanical Engineering, 2019, 30(20): 2489-2496. (in Chinese)
13	韩亚军, 刘家英. 基于B样条曲线的工业机器人运动轨迹误差优化研究[J]. 中国工程机械学报, 2020, 18(03): 199-204.
	HANYa-jun, LIUJia-ying. Research on motion trajectory error optimization of industrial robot based on B-spline curve [J]. Chinese Journal of Construction Machinery, 2020, 18(03): 199-204. (in Chinese)
14	王中玉, 曾国辉, 等. 基于改进双向A*的移动机器人路径规划算法[J]. 传感器与微系统, 2020, 39(11): 141-143, 147.
	WANGZhong-yu, ZENGGuo-hui, et al. Path planning algorithm for mobile robot based on improved bidirectional A*[J]. Transducer and Microsystem Technologies, 2020, 39 (11): 141-143, 147. (in Chinese)
15	闫文健. 动态场景下基于采样的移动机器人路径规划算法研究[D]. 哈尔滨: 哈尔滨工业大学, 2019.
	YANWen-jian. Research on Sampling-based Motion Planning Algorithm for Robots in Dynamic Scene[D]. Harbin: Harbin Institute of Technology, 2019. (in Chinese)
16	岳伟韬, 苏婧, 等. 占据栅格地图的最佳栅格大小与地图精度[J]. 机器人, 2020, 42(02): 199-206.
	YUEWei-tao, SUJing, et al. Optimal grid size and map accuracy for rastering map [J]. Robot, 2020, 42(02): 199-206. (in Chinese)
17	梁焰松. 室内导航路径规划算法的实现研究[D]. 武汉: 华中科技大学, 2015.
	LIANGYan-song. Research on Implementation of Indoor Navigation Path Planning Algorithm[D]. Wuhan: Huazhong University of Science and Technology, 2015. (in Chinese)
18	李宁. 面向家庭环境的移动机器人局部路径规划算法研究[D]. 哈尔滨: 哈尔滨工业大学, 2018.
	LINing. Research on Local Path Planning Algorithm for Mobile Robots Oriented to Home Environment[D]. Harbin: Harbin Institute of Technology, 2018. (in Chinese)
19	YAP P. Any-angle path planning for computer games[C]// Proceedings of the Seventh AAAI Artificial Intelligence and Interactive Digital Entertainment Conference. Stanford, California, USA: AAAI Press, 2011: 201-207.
20	聂铭远. 改进的蚁群3D-PTV匹配算法[C]//北京力学会第26届学术年会论文集. 北京: 北京力学会, 2020.
	NIEMing-yuan. Improved ant colony 3D-PTV matching algorithm[C]//Proceedings of the 26th Annual Conference of Beijing Society of Physical Mechanics. Beijing: Beijing Society of Physical Mechanics, 2020. (in Chinese)

路径条件	房间图	Andromeda	Destination	Python
简单
一般
复杂

路径条件	房间图	Andromeda	Destination	Python
简单
一般
复杂

路径条件	地图	时间（s）	路程（像素）	节点（个）	拐点（个）	角度（°）
简单	房间图	0.01532	143.091	5	3	37.566
	Andromeda	0.00427	149.345	3	1	59.076
	Destination	0.00576	129.683	5	3	63.435
	Python	0.04883	153.609	6	4	54.462
一般	房间图	0.15442	230.088	10	8	50.974
	Andromeda	0.03622	161.822	6	4	28.301
	Destination	0.6698	154.907	6	4	30.237
	Python	0.22352	248.713	9	7	32.150
复杂	房间图	0.26322	332.248	10	8	52.421
	Andromeda	0.00576	189.917	6	4	40.022
	Destination	0.31711	243.809	9	7	71.880
	Python	0.18687	132.644	7	5	78.972

路径条件	地图	时间（s）	路程（像素）	节点（个）	拐点（个）	角度（°）
简单	房间图	0.01532	143.091	5	3	37.566
	Andromeda	0.00427	149.345	3	1	59.076
	Destination	0.00576	129.683	5	3	63.435
	Python	0.04883	153.609	6	4	54.462
一般	房间图	0.15442	230.088	10	8	50.974
	Andromeda	0.03622	161.822	6	4	28.301
	Destination	0.6698	154.907	6	4	30.237
	Python	0.22352	248.713	9	7	32.150
复杂	房间图	0.26322	332.248	10	8	52.421
	Andromeda	0.00576	189.917	6	4	40.022
	Destination	0.31711	243.809	9	7	71.880
	Python	0.18687	132.644	7	5	78.972

路径条件	本文算法	A*	对比
简单
一般
复杂

基于射线模型的改进全局路径规划算法

Improved Global Path Planning Algorithm Based on Ray Model

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 17

参考文献 20

相关文章 15

编辑推荐

Metrics

路径条件	搜索算法	时间（s）	路程（像素）	节点（个）	拐点（个）	拐角（°）
简单	A*	0.06881	175.782	154	57	45
简单	本文算法	0.03947	111.594	5	3	20.318
一般	A*	0.21615	234.955	207	65	45
一般	本文算法	0.13321	191.655	5	3	38.326
复杂	A*	0.43107	294.635	248	71	90
复杂	本文算法	0.17451	255.907	10	8	59.909

[1]	宣志玮, 毛剑琳, 张凯翔. CBS框架下面向复杂地图的低拓展度A*算法[J]. 电子学报, 2022, 50(8): 1943-1950.
[2]	许凯波, 鲁海燕, 黄洋, 胡士娟. 基于双层蚁群算法和动态环境的机器人路径规划方法[J]. 电子学报, 2019, 47(10): 2166-2176.
[3]	王保防, 张瑞雷, 郭健, 陈庆伟. 纵向打滑状态下的轮式移动机器人编队控制[J]. 电子学报, 2017, 45(1): 206-212.
[4]	张红强, 章兢, 周少武, 曾照福, 吴亮红. 基于简化虚拟受力模型的未知复杂环境下群机器人围捕[J]. 电子学报, 2015, 43(4): 665-674.
[5]	刘国荣, 张扬名. 移动机器人轨迹跟踪的模糊PID-P型迭代学习控制[J]. 电子学报, 2013, 41(8): 1536-1541.
[6]	江济良, 屠大维, 许烁, 赵其杰. 基于生物触角的仿生条件反射机器人导航算法[J]. 电子学报, 2013, 41(2): 388-394.
[7]	曹政才;赵应涛;付宜利. 车式移动机器人轨迹跟踪控制方法[J]. 电子学报, 2012, 40(4): 632-635.
[8]	柳长安;鄢小虎;刘春阳;吴华. 基于改进蚁群算法的移动机器人动态路径规划方法[J]. 电子学报, 2011, 39(5): 1220-1224.
[9]	陈卫东;朱奇光. 基于模糊算法的移动机器人路径规划[J]. 电子学报, 2011, 39(4): 971-974.
[10]	曹政才;赵应涛;吴启迪. 基于Backstepping和神经动力学的非完整移动机器人点镇定[J]. 电子学报, 2011, 39(3): 591-595.
[11]	曹政才;温金涛;吴启迪. 未知环境下一种移动机器人实时最优路径规划方法研究[J]. 电子学报, 2010, 38(11): 2535-2539.
[12]	石杏喜;赵春霞;郭剑辉. 基于PF/CUKF/EKF的移动机器人SLAM框架算法[J]. 电子学报, 2009, 37(8): 1865-1868.
[13]	刘贞;丁明理;王祁. WSN多节点决策信息融合在机器人自主导航中的应用[J]. 电子学报, 2008, 36(12): 2299-2305.
[14]	高庆吉;雷亚莉;胡丹丹;于咏生. 基于自适应感知复位算法的移动机器人定位[J]. 电子学报, 2007, 35(11): 2166-2171.
[15]	周兰凤, 洪炳熔. 用基于知识的遗传算法实现移动机器人路径规划[J]. 电子学报, 2006, 34(5): 911-914.