﻿ 融合改进A*算法和Morphin算法的移动机器人动态路径规划
«上一篇
 文章快速检索 高级检索

 智能系统学报  2020, Vol. 15 Issue (3): 546-552  DOI: 10.11992/tis.201812023 0

### 引用本文

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.

### 文章历史

Mobile-robot dynamic path planning based on improved A* and Morphin algorithms
CHENG Yi , XIAO Hongtu
School of Electrical Engineering and Automation, University of Tianjin Polytechnic, Tianjin 300387, China
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.
Key words: mobile robot    A* algorithm    improved A* algorithm    Morphin search tree    global-path planning    local path planning    dynamic path planning    real-time obstacle avoidanc

1 基于改进A*算法的全局路径规划

1)初始化地图信息包括起点、目标点、障碍物信息等；

2)创建Open列表与Closed列表，将起点的节点信息放入Open列表中；

3)如果Open列表中为空，表示没有找到路径，退出；

4)寻找起点周围可以到达的方格(周围8个方格)，并把起点设置为这些方格的“父节点”，然后把周围节点加入到“Open列表中”，根据列表中节点 $f$ (估计函数)的值进行从小到大排序；

5)从Open列表中找到最佳节点，作为新的“父节点”，并将上一个父节点移到Closed列表中；

6)在Closed列表中选取扩展节点，将扩展节点的周围节点加入Open列表中。判断当前父节点是否为目标点，如果是，则通过当前父节点向上遍历到起点，找到组成路径的所有节点，否则，转到4)；

7)设置变量 $i$ ( $i$ ≥3)，判断Closed列表中 $i - 1$ $i$ $i + 1$ 节点是否在同一直线上，如果在删除 $i$ 节点，否则全部保留， $i$ 增加1；

8)将Closed列表中最后得到的路径节点进行移动平均滤波处理，得到平滑路径。

2 Morphin搜索树算法局部路径规划 2.1 Morphin搜索树算法

Morphin算法是CMU根据Ranger[17]算法提出的基于地面分析的局部路径规划算法，也是一种基于先验栅格地图进行可行性统计分析的局部避障算法[18-20]。其核心思想是：根据机器人自身的传感器对环境信息进行实时检测，根据不同的转向角度生成一组可行驶路径集，然后根据机器人当前的状态，包括俯仰角、转向角以及前方路径的可通行率、安全性，选出一条最适宜通行的路径。该算法不仅计算量较少、效率较快，能够较好地处理环境建模的不确定性，也能较好地与全局路径规划算法结合，共同决策机器人的运动行为[21]。Morphin算法预测线如图1所示，其中圆环为机器人，Target菱形为目标，黑色块为障碍物。

Morphin算法由运动模型和评价函数两部分组成。运动模型的核心思想是根据前进方向按照同样的时间、不同的转移角生成一组路径，利用评价函数对每条路径进行估计，得到最优路径。Morphin算法运动模型的建立就是建立搜索路径组和搜索弧线组[22]。搜索路径组是指由当前环境信息得到的可能运行的位置。搜索弧线组由多条预测线组成。已知机器人当前位置、速度及运动方向角，即 $[x(t),y(t),v(t),\theta (t)]$ 。可以推算出搜索路径组：

 $\begin{array}{l} \left[ \begin{array}{l} x(t + \mu ) \\ y(t + \mu ) \\ \end{array} \right] = \left[ \begin{array}{l} x(t) \\ y(t) \\ \end{array} \right] - \left[ \begin{array}{l} {\textit{v}}(t)\mu \cos {{\bf{\theta }}_s}(t) \\ {\textit{v}}(t)\mu \sin {{\bf{\theta }}_s}(t) \\ \end{array} \right] \end{array}$ (1)

 $\begin{array}{l} \left[ \begin{array}{l} x(t + \ell i) \\ y(t + \ell i) \\ \end{array} \right] = \left[ \begin{array}{l} x(t + \ell (i - 1)) \\ y(t + \ell (i - 1)) \\ \end{array} \right]{\rm{ - }}\left[ \begin{array}{l} {\textit{v}}(t)\ell \cos {{{\theta }}_s}(t) \\ {\textit{v}}(t)\ell \sin {{{\theta }}_s}(t) \\ \end{array} \right] \end{array} \!\!\!\!\!$ (2)

 $f = \left\{ \begin{array}{l} \infty ,\quad {\text{弧线上有障碍物}}\\ {\gamma _1}L + {\gamma _2}M + {\gamma _3}\Delta d + {\gamma _4}N,\quad {\text{无障碍物}} \end{array} \right.$ (3)

2.2 局部规划与动态路径规划流程

 Download: 图 2 融合算法流程图 Fig. 2 Flow chart of the fusion of algorithms

 $G = \alpha \cdot X_{\rm{angle}} + \beta \cdot Y_{\rm{dist}} + \lambda \cdot Z_{\rm{velocity}}$ (4)

1)机器人根据探测障碍物信息每隔一段时间更新栅格地图信息，同时保存当前节点；

2)确定将要驶向的子目标点；

3)以机器人当前节点为起点，画出指向子目标点的直线，在直线两侧45°均匀地画出弧线，弧线利用附近的栅格点或已保存的节点表示；

4)根据评价函数 $G$ 从备选路径中选择值最小的弧线作为最优路径，按照路径移动后执行6)；当几条预测路径都无法避开障碍物执行5)；

5)将机器人旋转一定角度或等待一段时间进行尝试，如果不行，停止局部路径规划；调用A*算法重新进行全局规划，然后返回1)；

6)机器人成功绕开障碍物后回到全局路径上继续行驶到目标点。

3 仿真结果与分析

3.1 A*算法与改进A*算法仿真实验对比分析

 Download: 图 3 普通地图传统A*算法与改进A*算法实验 Fig. 3 Experiment of traditional A* algorithms and improved A* algorithms on general map
 Download: 图 4 随机地图传统A*与改进A*算法实验 Fig. 4 Randomly generated map traditional A* algorithms and improved A* algorithms experiment

3.2 引入Morphin算法后动态避障效果分析

 Download: 图 5 动态障碍物运动前位置 Fig. 5 Initial position before dynamic obstacle movement
 Download: 图 6 Bidirectional RRT算法规划路径 Fig. 6 Path planned by Bidirectional RRT algorithm
 Download: 图 7 模糊控制算法规划路径 Fig. 7 Path planned by fuzzy control algorithm

Morphin算法对机器人与障碍物是否碰撞进行预测，从而进行局部路径规划，如图8所示。由于小球A与小车运动路线无干扰，小车正常行驶；通过预测可知在虚线的D1点，将会与小球B碰撞，小车进行局部避障选择预测弧线G值最小的路径，避开后回到全局路径继续行驶。运动小球C在障碍物之间的通道中，此处机器人无法通过。对于运动小球C有2种情况。第1种情况，小球C速度为0.4 m/s，短时间内从机器人要行驶的通道内出来并且不阻挡机器人的运动。如图8所示，机器人在D2点等待球C运动出来，再按照规划好的全局路径行驶到目标点。

 Download: 图 9 动态避障重新规划路径 Fig. 9 Re-planned path using dynamic obstacle avoidance

4 结束语

 [1] QURESHI A H, AYAZ Y. Potential functions based sampling heuristic for optimal path planning[J]. Autonomous robots, 2016, 40(6): 1079-1093. DOI:10.1007/s10514-015-9518-0 (0) [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. DOI:10.1007/s12559-016-9442-4 (0) [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. DOI:10.1007/s12555-016-0443-6 (0) [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. DOI:10.11992/tis.201702005 (0) [5] FAZLOLLAHTABAR H, HASSANLI S. Hybrid cost and time path planning for multiple autonomous guided vehicles[J]. Applied intelligence, 2017, 48(2): 482-498. (0) [6] HAN J, SEO Y. Mobile robot path planning with surrounding point set and path improvement[J]. Applied soft computing, 2017, 57: 35-47. DOI:10.1016/j.asoc.2017.03.035 (0) [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. DOI:10.1016/j.procs.2018.07.076 (0) [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. DOI:10.1016/j.robot.2018.06.013 (0) [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. (0) [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. (0) [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. DOI:10.1142/S0218488518500368 (0) [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. DOI:10.3981/j.issn.1000-7857.2015.03.014 (0) [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. DOI:10.3969/j.issn.1009-0134.2014.24.006 (0) [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. (0) [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. (0) [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. DOI:10.3969/j.issn.0253-374x.2010.11.016 (0) [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. (0) [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. DOI:10.11992/tis.201803031 (0) [19] BELGHITH K, KABANZA F, HARTMAN L. Randomized path planning with preferences in highly complex dynamic environments[J]. Robotica, 2013, 31(8): 1195-1208. DOI:10.1017/S0263574713000428 (0) [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. (0) [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. DOI:10.3969/j.issn.1006-2475.2016.04.012 (0) [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. (0)