[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]
点击复制

融合改进A*算法和Morphin算法的移动机器人动态路径规划(/HTML)
分享到:

《智能系统学报》[ISSN:1673-4785/CN:23-1538/TP]

卷:
第15卷
期数:
2020年3期
页码:
546-552
栏目:
学术论文—机器学习
出版日期:
2020-05-05

文章信息/Info

Title:
Mobile-robot dynamic path planning based on improved A* and Morphin algorithms
作者:
成怡 肖宏图
天津工业大学 电气工程与自动化学院,天津 300387
Author(s):
CHENG Yi XIAO Hongtu
School of Electrical Engineering and Automation, University of Tianjin Polytechnic, Tianjin 300387, China
关键词:
移动机器人A*算法改进A*算法Morphin搜索树算法全局路径规划局部路径规划动态路径规划实时避障
Keywords:
mobile robotA* algorithmimproved A* algorithmMorphin search treeglobal-path planninglocal path planningdynamic path planningreal-time obstacle avoidanc
分类号:
TP242
DOI:
10.11992/tis.201812023
摘要:
在动态未知环境下对机器人进行路径规划,传统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(01):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(3):52.
[2]杨甜甜,刘志远,陈 虹,等.移动机器人编队控制的现状与问题[J].智能系统学报,2007,2(04):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(3):21.
[3]李润伟,蔡自兴,童宇,等.基于ATM的提高狭窄环境探测精度的改进方法[J].智能系统学报,2008,3(04):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(3):283.
[4]霍成立,谢 凡,秦世引.面向室内移动机器人的无迹滤波实时导航方法[J].智能系统学报,2009,4(04):295.
 HUO Cheng-li,XIE Fan,QIN Shi-yin.A case study in realtime UKFbased navigation for indoor autonomous travel of mobile robots[J].CAAI Transactions on Intelligent Systems,2009,4(3):295.
[5]海 丹,李 勇,张 辉,等.无线传感器网络环境下基于粒子滤波的移动机器人SLAM算法[J].智能系统学报,2010,5(05):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(3):425.[doi:10.3969/j.issn.1673-4785.2010.05.008]
[6]房立金,王洪光.架空线移动机器人行走越障特点[J].智能系统学报,2010,5(06):492.
 FANG Li-jin,WANG Hong-guang.Research on the characteristics of the movement and obstacleclearing processes of a wiresuspended mobile robot[J].CAAI Transactions on Intelligent Systems,2010,5(3):492.
[7]任立敏,王伟东,杜志江.移动机器人队形控制关键技术及其进展[J].智能系统学报,2013,8(05):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(3):381.[doi:10.3969/j.issn.1673-4785.201302011]
[8]贺超,刘华平,孙富春,等.采用Kinect的移动机器人目标跟踪与避障[J].智能系统学报,2013,8(05):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(3):426.[doi:10.3969/j.issn.1673-4785.201301028]
[9]阮晓钢,庞涛,张晓平,等.一种基于情感智能的机器人自主趋光行为研究[J].智能系统学报,2015,10(01):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(3):97.[doi:10.3969/j.issn.1673-4785.201312035]
[10]沈博闻,于宁波,刘景泰.仓储物流机器人集群的智能调度和路径规划[J].智能系统学报,2014,9(06):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(3):659.[doi:10.3969/j.issn.1673-4785.201312048]

备注/Memo

备注/Memo:
收稿日期:2018-12-20。
基金项目:天津市自然科学基金项目(18JCYBJC88400,18JCYBJC88300);天津市高等学校创新团队培养计划项目(TD13-5036)
作者简介:成怡,副教授,博士,主要研究方向为视觉导航技术、智能算法优化、控制系统建模。主持及参与国家、省部级科研项目5项,获2013年天津优秀青年教师资助计划。发表学术论文30余篇;肖宏图,硕士研究生,主要研究方向为路径规划算法、移动机器人
通讯作者:肖宏图.E-mail:tvtmail@163.com
更新日期/Last Update: 1900-01-01