[1]成怡,肖宏图.融合改进A*算法和Morphin算法的移动机器人动态路径规划[J].智能系统学报,2020,15(3):546-552.[doi:10.11992/tis.201812023]
CHENG Yi,XIAO Hongtu.Mobile-robot dynamic path planning based on improved A* and Morphin algorithms[J].CAAI Transactions on Intelligent Systems,2020,15(3):546-552.[doi:10.11992/tis.201812023]
点击复制
CHENG Yi,XIAO Hongtu.Mobile-robot dynamic path planning based on improved A* and Morphin algorithms[J].CAAI Transactions on Intelligent Systems,2020,15(3):546-552.[doi:10.11992/tis.201812023]
融合改进A*算法和Morphin算法的移动机器人动态路径规划
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
15
期数:
2020年第3期
页码:
546-552
栏目:
学术论文—机器学习
出版日期:
2020-05-05
- Title:
- Mobile-robot dynamic path planning based on improved A* and Morphin algorithms
- Keywords:
- mobile robot; A* algorithm; improved A* algorithm; Morphin search tree; global-path planning; local path planning; dynamic path planning; real-time obstacle avoidanc
- 分类号:
- TP242
- 摘要:
- 在动态未知环境下对机器人进行路径规划，传统A*算法可能出现碰撞或者路径规划失败问题。为了满足移动机器人全局路径规划最优和实时避障的需求，提出一种改进A*算法与Morphin搜索树算法相结合的动态路径规划方法。首先通过改进A*算法减少路径规划过程中关键节点的选取，在规划出一条全局较优路径的同时对路径平滑处理。然后基于移动机器人传感器采集的局部信息，利用Morphin搜索树算法对全局路径进行动态的局部规划，确保更好的全局路径的基础上，实时避开障碍物行驶到目标点。MATLAB仿真实验结果表明，提出的动态路径规划方法在时间和路径上得到提升，在优化全局路径规划的基础上修正局部路径，实现动态避障提高机器人达到目标点的效率。
- Abstract:
- The traditional A* algorithm can experience collisions or path-planning failure in dynamic complicated environments. To meet global optimal requirements and achieve real-time obstacle avoidance in mobile-robot path planning, we propose a novel method that fuses an improved A* algorithm with a Morphin search tree algorithm. First, we improved the A* algorithm by reducing the selection of key nodes in the path-planning process and performing path smoothing when planning the global optimal path. Then, based on the local information obtained by the mobile-robot sensor, the Morphin search tree algorithm is used to dynamically localize the global path. Thus, obstacles are avoided both by ensuring a better global path and by real-time obstacle avoidance as the robot moves to the target. The MATLAB simulation results show that the proposed dynamic path-planning method improves both the time and path. The local path is corrected via the optimized global-path planning, dynamic obstacle avoidance, and the improved efficiency with which the robot reaches the target point.
- 参考文献/References:
-
[1] QURESHI A H, AYAZ Y. Potential functions based sampling heuristic for optimal path planning[J]. Autonomous robots, 2016, 40(6): 1079-1093.
[2] SONG Baoye, WANG Zidong, ZOU Lei. On global smooth path planning for mobile robots using a novel multimodal delayed PSO algorithm[J]. Cognitive computation, 2017, 9(1): 5-17.
[3] LEE J. Heterogeneous-ants-based path planner for global path planning of mobile robot applications[J]. International journal of control, automation and systems, 2017, 15(4): 1754-1769.
[4] 李元, 王石荣, 于宁波. 基于RGB-D信息的移动机器人SLAM和路径规划方法研究与实现[J]. 智能系统学报, 2018, 13(3): 445-451
LI Yuan, WANG Shirong, YU Ningbo. RGB-D-based SLAM and path planning for mobile robots[J]. CAAI transactions on intelligent systems, 2018, 13(3): 445-451
[5] FAZLOLLAHTABAR H, HASSANLI S. Hybrid cost and time path planning for multiple autonomous guided vehicles[J]. Applied intelligence, 2017, 48(2): 482-498.
[6] HAN J, SEO Y. Mobile robot path planning with surrounding point set and path improvement[J]. Applied soft computing, 2017, 57: 35-47.
[7] SUDHAKARA P, GANAPATHY V. PRIYADHARSHINI B, et al Obstacle avoidance and navigation planning of a wheeled mobile robot using amended artificial potential field method[J]. Procedia computer science, 2018, 133: 998-1004.
[8] TAHIR Z, QURESHI A H, AYAZ Y, et al. Potentially guided bidirectionalized RRT* for fast optimal path planning in cluttered environments[J]. Robotics and autonomous systems, 2018, 108: 13-27.
[9] 朱大奇, 孙兵, 李利. 基于生物启发模型的AUV三维自主路径规划与安全避障算法[J]. 控制与决策, 2015, 30(5): 798-806
ZHU Daqi, SUN Bing, LI Li. Algorithm for AUV’s 3-D path planning and safe obstacle avoidance based on biological inspired model[J]. Control and decision, 2015, 30(5): 798-806
[10] 伍永健, 陈跃东, 陈孟元. 改进QPSO和Morphin算法下移动机器人混合路径规划[J]. 电子测量与仪器学报, 2017, 31(2): 295-301
WU Yongjian, CHEN Yuedong, CHEN Mengyuan. Hybrid path planning of mobile robot based on improved QPSO and Morphin algorithm[J]. Journal of electronic measurement and instrumentation, 2017, 31(2): 295-301
[11] MAOUDJ A, HENTOUT A, BOUZOUIA B, et al. On-line fault-tolerant fuzzy-based path planning and obstacles avoidance approach for manipulator robots[J]. International journal of uncertainty, fuzziness and knowledge-based systems, 2018, 26(5): 809-838.
[12] 万晓凤, 胡伟, 郑博嘉, 等. 基于改进蚁群算法与Morphin算法的机器人路径规划方法[J]. 科技导报, 2015, 33(3): 84-89
WAN Xiaofeng, HU Wei, ZHENG Bojia, et al. Robot path planning method based on improved ant colony algorithm and Morphin algorithm[J]. Science & technology review, 2015, 33(3): 84-89
[13] 秦玉鑫, 王红旗, 杜翠杰. 基于双层A*算法的移动机器人路径规划[J]. 制造业自动化, 2014, 36(24): 21-25, 40
QIN Yuxin, WANG Hongqi, DU Cuijie. A path planning approach to moving robot based on double layer A* Algorithm[J]. Manufacturing automation, 2014, 36(24): 21-25, 40
[14] XU Yaru, LIU Rong. Path planning for mobile articulated robots based on the improved A* algorithm[J]. International journal of advanced robotic systems, 2017, 14(4): 1-10.
[15] ZHANG Hongmei, LI Minglong. Rapid path planning algorithm for mobile robot in dynamic environment[J]. Advances in mechanical engineering, 2017, 9(12): 1-12.
[16] 王红卫, 马勇, 谢勇, 等. 基于平滑A*算法的移动机器人路径规划[J]. 同济大学学报(自然科学版), 2010, 38(11): 1647-1650
WANG Hongwei, MA Yong, XIE Yong, et al. Mobile robot optimal path planning based on smoothing A* algorithm[J]. Journal of Tongji University (Natural Science), 2010, 38(11): 1647-1650
[17] SIMMONS R, KROTKOV E, CHRISMAN L, et al. Experience with rover navigation for lunar-like terrains [C]//Proceedings of 1995 IEEE/RSJ International Conference on Intelligent Robots and Systems. Human Robot Interaction and Cooperative Robots. Pittsburgh, USA, 1995: 441-446.
[18] 张飞, 白伟, 乔耀华, 等. 基于改进D*算法的无人机室内路径规划[J]. 智能系统学报, 2019, 14(4): 662-669
ZHANG Fei, BAI Wei, QIAO Yaohua, et al. UAV indoor path planning based on improved D* algorithm[J]. CAAI transactions on intelligent systems, 2019, 14(4): 662-669
[19] BELGHITH K, KABANZA F, HARTMAN L. Randomized path planning with preferences in highly complex dynamic environments[J]. Robotica, 2013, 31(8): 1195-1208.
[20] 诸葛程晨, 唐振民, 石朝侠. 基于多层Morphin搜索树的UGV局部路径规划算法[J]. 机器人, 2014, 36(4): 491-497
ZHUGE Chengchen, TANG Zhenmin, SHI Zhaoxia. A local path planning algorithm for UGV based on multilayer Morphin search tree[J]. Robot, 2014, 36(4): 491-497
[21] 曹清云, 倪建军, 王康, 等. 一种改进的未知动态环境下机器人混合路径规划方法[J]. 计算机与现代化, 2016(4): 54-58
CAO Qingyun, NI Jianjun, WANG Kang, et al. A robot hybrid path planning algorithm under improved unknown and dynamic environment[J]. Computer and modernization, 2016(4): 54-58
[22] 张兆宁, 魏中慧. 危险天气下基于多重Morphin算法的终端区三维实时改航方法[J]. 南京航空航天大学学报, 2015, 47(4): 467-473
ZHANG Zhaoning, WEI Zhonghui. 3-D real-time deviation method for avoiding hazardous weather in terminal airspace based on Morphin planning algorithm[J]. Journal of Nanjing University of Aeronautics and Astronautics, 2015, 47(4): 467-473
- 相似文献/References:
-
[1]蔡自兴,王 勇,王 璐.基于角点聚类的移动机器人自然路标检测与识别[J].智能系统学报,2006,1(1):52.
CAI Zi-xing,WANG Yong,WANG Lu.Corner clustering based detection and recognition of natural landmark for mobile robot[J].CAAI Transactions on Intelligent Systems,2006,1():52.
[2]杨甜甜,刘志远,陈 虹,等.移动机器人编队控制的现状与问题[J].智能系统学报,2007,2(4):21.
YANG Tian-tian,LIU Zhi-yuan,CHEN Hong,et al.Formation control of mobile robots: state and open prob lems[J].CAAI Transactions on Intelligent Systems,2007,2():21.
[3]李润伟,蔡自兴,童宇,等.基于ATM的提高狭窄环境探测精度的改进方法[J].智能系统学报,2008,3(4):283.
LI Run-wei,CAI Zi-xing,TONG Yu.Improving the accuracy of exploring the narrow environment by using ATM[J].CAAI Transactions on Intelligent Systems,2008,3():283.
[4]霍成立,谢 凡,秦世引.面向室内移动机器人的无迹滤波实时导航方法[J].智能系统学报,2009,4(4):295.
HUO Cheng-li,XIE Fan,QIN Shi-yin.A case study in realtime UKFbased navigation for indoor autonomous travel of mobile robots[J].CAAI Transactions on Intelligent Systems,2009,4():295.
[5]海 丹,李 勇,张 辉,等.无线传感器网络环境下基于粒子滤波的移动机器人SLAM算法[J].智能系统学报,2010,5(5):425.[doi:10.3969/j.issn.1673-4785.2010.05.008]
HAI Dan,LI Yong,ZHANG Hui,et al.Simultaneous localization and mapping of a mobile robot in wireless sensor networks based on particle filtering[J].CAAI Transactions on Intelligent Systems,2010,5():425.[doi:10.3969/j.issn.1673-4785.2010.05.008]
[6]房立金,王洪光.架空线移动机器人行走越障特点[J].智能系统学报,2010,5(6):492.
FANG Li-jin,WANG Hong-guang.Research on the characteristics of the movement and obstacleclearing processes of a wiresuspended mobile robot[J].CAAI Transactions on Intelligent Systems,2010,5():492.
[7]任立敏,王伟东,杜志江.移动机器人队形控制关键技术及其进展[J].智能系统学报,2013,8(5):381.[doi:10.3969/j.issn.1673-4785.201302011]
REN Limin,WANG Weidong,DU Zhijiang.Key technologies and development of? formation control of mobile robots[J].CAAI Transactions on Intelligent Systems,2013,8():381.[doi:10.3969/j.issn.1673-4785.201302011]
[8]贺超,刘华平,孙富春,等.采用Kinect的移动机器人目标跟踪与避障[J].智能系统学报,2013,8(5):426.[doi:10.3969/j.issn.1673-4785.201301028]
HE Chao,LIU Huaping,SUN Fuchun,et al.Target tracking and obstacle avoidance of mobile robot using Kinect[J].CAAI Transactions on Intelligent Systems,2013,8():426.[doi:10.3969/j.issn.1673-4785.201301028]
[9]阮晓钢,庞涛,张晓平,等.一种基于情感智能的机器人自主趋光行为研究[J].智能系统学报,2015,10(1):97.[doi:10.3969/j.issn.1673-4785.201312035]
RUAN Xiaogang,PANG Tao,ZHANG Xiaoping,et al.Research on the autonomous phototaxis behavior of a robot based on emotion intelligence[J].CAAI Transactions on Intelligent Systems,2015,10():97.[doi:10.3969/j.issn.1673-4785.201312035]
[10]沈博闻,于宁波,刘景泰.仓储物流机器人集群的智能调度和路径规划[J].智能系统学报,2014,9(6):659.[doi:10.3969/j.issn.1673-4785.201312048]
SHEN Bowen,YU Ningbo,LIU Jingtai.Intelligent scheduling and path planning of warehouse mobile robots[J].CAAI Transactions on Intelligent Systems,2014,9():659.[doi:10.3969/j.issn.1673-4785.201312048]
备注/Memo
收稿日期:2018-12-20。
基金项目:天津市自然科学基金项目(18JCYBJC88400，18JCYBJC88300)；天津市高等学校创新团队培养计划项目(TD13-5036)
作者简介:成怡，副教授，博士，主要研究方向为视觉导航技术、智能算法优化、控制系统建模。主持及参与国家、省部级科研项目5项，获2013年天津优秀青年教师资助计划。发表学术论文30余篇;肖宏图，硕士研究生，主要研究方向为路径规划算法、移动机器人
通讯作者:肖宏图.E-mail:tvtmail@163.com
更新日期/Last Update:
1900-01-01