第3期 成怡，等：融合改进A*算法和Morphin算法的移动机器人动态路径规划 ·551· 径并不是最优的。同时在初始阶段双向搜索树会 [2]SONG Baoye,WANG Zidong,ZOU Lei.On global 对地图进行大面积探索，包括不可通行的死区， smooth path planning for mobile robots using a novel mul- 导致节点增多，占用内存增加。模糊算法根据设 timodal 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].Internation- al journal of control,automation and systems,2017,15(4): 入死锁。所以同等环境下本文动态算法在灵活性 17541769 与适应性方面更优。表2是A*算法、改进A*算 [4]李元，王石荣，于宁波.基于RGB-D信息的移动机器人 法、Bidirectional RRT、模糊控制算法、动态算法的 SLAM和路径规划方法研究与实现).智能系统学报， 数据对比。 2018.13(3):445-451 表2路径规划算法比较结果 LI Yuan,WANG Shirong,YU Ningbo.RGB-D-based Table 2 Comparison of path planning results SLAM and path planning for mobile robots[J].CAAI 算法 平均时间s平均长度/m节点个数平滑处理 transactions on intelligent systems,2018,13(3):445-451. [5]FAZLOLLAHTABAR H.HASSANLI S.Hybrid cost and 传统A*算法 20.14 38.68 36 否 time path planning for multiple autonomous guided 改进A幸算法 18.08 32.03 23 是 vehicles[J].Applied intelligence,2017,48(2):482-498. 动态算法 18.75 40.22 32 是 [6]HAN J,SEO Y.Mobile robot path planning with surround- 模糊控制 33.71 47.87 142 是 ing point set and path improvement[J].Applied soft com- 双向RRT 22.24 51.55 103 否 puting,2017,57:35-47. [7]SUDHAKARA P,GANAPATHY V.PRIYADHAR- 通过动态算法在相同环境下与Bidirectional SHINI B,et al Obstacle avoidance and navigation plan- RRT算法和模糊控制的对比可以看出，在路径长 ning 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 plan- 4结束语 ning in cluttered environments[J].Robotics and autonom- ous systems,.2018,108:13-27. 本文针对传统A*算法面对动态障碍发生碰 [9]朱大奇，孙兵，李利.基于生物启发模型的AUV三维自 撞或者路径规划失败问题，提出了一种改进A*算 主路径规划与安全避障算法J几控制与决策，2015. 法与Morphin算法相结合的动态路径规划方法。 30(5):798-806. 首先对A*算法进行改进，优化传统A*算法的搜 ZHU Daqi,SUN Bing,LI Li.Algorithm for AUV's 3-D 索节点多，路径不平滑，不易运动控制等问题。 path planning and safe obstacle avoidance based on biolo- 并根据改进的A*算法进行路径规划；然后机器人 gical inspired model[J].Control and decision,2015,30(5): 按照规划出的全局路径行驶，如果碰到未知的静 798-806. 态或动态障碍物时，根据传感器检测到的信息调 [1O]伍永健，陈跃东，陈孟元.改进QPSO和Morphin算法 用Morphin算法进行局部规划。通过仿真验证了 下移动机器人混合路径规划.电子测量与仪器学报. 改进A*算法规划出的路径更加平滑，搜索节点更 2017,31(2):295-301 少；Morphin算法可以有效地避开动态障碍物。 WU Yongjian,CHEN Yuedong,CHEN Mengyuan.Hy- brid path planning of mobile robot based on improved 动态算法通过A*算法与Morphin算法相融合，使 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].Interna- [1]QURESHI A H,AYAZ Y.Potential functions based tional journal of uncertainty,fuzziness and knowledge- sampling heuristic for optimal path planning.Autonom- based systems,2018,26(5):809-838 ous robots,2016,40(6):1079-1093. [12]万晓凤，胡伟，郑博嘉，等.基于改进蚁群算法与Moph径并不是最优的。同时在初始阶段双向搜索树会 对地图进行大面积探索，包括不可通行的死区， 导致节点增多，占用内存增加。模糊算法根据设 定的转向角、阈值、安全距离等因素会出现死锁 现象，使机器人停在原地无法移动到目标。同时 在复杂的室内环境转向困难当转向角过大将会陷 入死锁。所以同等环境下本文动态算法在灵活性 与适应性方面更优。表 2 是 A*算法、改进 A*算 法、Bidirectional RRT、模糊控制算法、动态算法的 数据对比。 表 2 路径规划算法比较结果 Table 2 Comparison of path planning results 算法 平均时间/s 平均长度/m 节点个数 平滑处理 传统A*算法 20.14 38.68 36 否 改进A*算法 18.08 32.03 23 是 动态算法 18.75 40.22 32 是 模糊控制 33.71 47.87 142 是 双向 RRT 22.24 51.55 103 否 通过动态算法在相同环境下与 Bidirectional RRT 算法和模糊控制的对比可以看出，在路径长 度、耗费时间、与路径节点等方面得到明显的改 善。耗费更少的资源得到更优的结果同时保证机 器人安全有效地到达目标点。 4 结束语 本文针对传统 A*算法面对动态障碍发生碰 撞或者路径规划失败问题，提出了一种改进 A*算 法与 Morphin 算法相结合的动态路径规划方法。 首先对 A*算法进行改进，优化传统 A*算法的搜 索节点多，路径不平滑，不易运动控制等问题。 并根据改进的 A*算法进行路径规划；然后机器人 按照规划出的全局路径行驶，如果碰到未知的静 态或动态障碍物时，根据传感器检测到的信息调 用 Morphin 算法进行局部规划。通过仿真验证了 改进 A*算法规划出的路径更加平滑，搜索节点更 少；Morphin 算法可以有效地避开动态障碍物。 动态算法通过 A*算法与 Morphin 算法相融合，使 机器人获得最佳的路径、时间，有效地提升了机 器人的工作效率和安全性。 参考文献： QURESHI A H, AYAZ Y. Potential functions based sampling heuristic for optimal path planning[J]. Autonom￾ous robots, 2016, 40(6): 1079–1093. [1] SONG Baoye, WANG Zidong, ZOU Lei. On global smooth path planning for mobile robots using a novel mul￾timodal delayed PSO algorithm[J]. Cognitive computation, 2017, 9(1): 5–17. [2] LEE J. Heterogeneous-ants-based path planner for global path planning of mobile robot applications[J]. Internation￾al journal of control, automation and systems, 2017, 15(4): 1754–1769. [3] 李元, 王石荣, 于宁波. 基于 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. [4] FAZLOLLAHTABAR H, HASSANLI S. Hybrid cost and time path planning for multiple autonomous guided vehicles[J]. Applied intelligence, 2017, 48(2): 482–498. [5] HAN J, SEO Y. Mobile robot path planning with surround￾ing point set and path improvement[J]. Applied soft com￾puting, 2017, 57: 35–47. [6] SUDHAKARA P, GANAPATHY V. PRIYADHAR￾SHINI B, et al Obstacle avoidance and navigation plan￾ning of a wheeled mobile robot using amended artificial potential field method[J]. Procedia computer science, 2018, 133: 998–1004. [7] TAHIR Z, QURESHI A H, AYAZ Y, et al. Potentially guided bidirectionalized RRT* for fast optimal path plan￾ning in cluttered environments[J]. Robotics and autonom￾ous systems, 2018, 108: 13–27. [8] 朱大奇, 孙兵, 李利. 基于生物启发模型的 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 biolo￾gical inspired model[J]. Control and decision, 2015, 30(5): 798–806. [9] 伍永健, 陈跃东, 陈孟元. 改进 QPSO 和 Morphin 算法 下移动机器人混合路径规划 [J]. 电子测量与仪器学报, 2017, 31(2): 295–301. WU Yongjian, CHEN Yuedong, CHEN Mengyuan. Hy￾brid path planning of mobile robot based on improved QPSO and Morphin algorithm[J]. Journal of electronic measurement and instrumentation, 2017, 31(2): 295–301. [10] MAOUDJ A, HENTOUT A, BOUZOUIA B, et al. On￾line fault-tolerant fuzzy-based path planning and obstacles avoidance approach for manipulator robots[J]. Interna￾tional journal of uncertainty, fuzziness and knowledge￾based systems, 2018, 26(5): 809–838. [11] [12] 万晓凤, 胡伟, 郑博嘉, 等. 基于改进蚁群算法与 Morph- 第 3 期 成怡，等：融合改进 A*算法和 Morphin 算法的移动机器人动态路径规划 ·551·