电子学报 ›› 2022, Vol. 50 ›› Issue (3): 548-556.DOI: 10.12263/DZXB.20210307
蒋林1,2, 方东君1, 周和文3, 黄惠保3
收稿日期:
2021-03-04
修回日期:
2021-03-19
出版日期:
2022-03-25
作者简介:
基金资助:
JIANG Lin1,2, FANG Dong-jun1, ZHOU He-wen3, HUANG Hui-bao3
Received:
2021-03-04
Revised:
2021-03-19
Online:
2022-03-25
Published:
2022-03-25
Supported by:
摘要:
针对目前服务于移动机器人的全局路径规划算法存在拐点多、耗时长或递归计算复杂等问题,本文提出一种基于射线模型的改进全局路径搜索算法.利用形态学滤波处理障碍物栅格地图,并引入碰撞估值增加靠近障碍物的栅格的代价值,形成梯度代价栅格地图.结合射线模型从起点向终点进行射线搜索,并在搜索过程中通过逆向优化算法优化路径.通过实验证明该全局路径规划算法比A*算法拥有更好的平滑性、灵活性、稳定性以及更短的路程,且搜索速度比A*快50%,移动机器人可以更安全、简洁的路径向目标点移动.
中图分类号:
蒋林, 方东君, 周和文, 等. 基于射线模型的改进全局路径规划算法[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.
路径条件 | 房间图 | Andromeda | Destination | Python |
---|---|---|---|---|
简单 | ![]() | ![]() | ![]() | ![]() |
一般 | ![]() | ![]() | ![]() | ![]() |
复杂 | ![]() | ![]() | ![]() | ![]() |
表1 三种复杂程度下各地图中的路径效果
路径条件 | 房间图 | 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 |
表2 三种复杂程度下各地图中的路径参数
路径条件 | 地图 | 时间(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) | 路程 (像素) | 节点 (个) | 拐点 (个) | 拐角 (°) |
---|---|---|---|---|---|---|
简单 | 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 |
表4 本文算法与A*路径参数对比
路径条件 | 搜索算法 | 时间 (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 | 化建宁, 赵忆文, 等. 一种新的移动机器人全局路径规划算法[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) |
[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. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||