移动机器人路径规划方法研究

高涵　高柏军

[摘 要] 本文介绍了几种路径规划方法的优缺点以及改进方法。针对人工势场法的不足提出改进算法，并对该方法进行仿真分析。展示利用模糊神经网络法避障实例，应用结果表明该方法可以有效地避开障碍物到达目标位置。

[关键词] 路径规划；人工势场；启发式算法；蚁群算法；遗传算法

中图分类号： TP242.6 文献标识码：A 文章编号：2095-5200（2015）05-014-04

[Abstract] The paper illustrates several trajectory palnning algorithms principles，merits and demerits and improved algorithms.Then， the paper presents improved algorithm for disadvantages of APF and makes simulation.Finally， the paper gives an example of avoiding obstacle by using fuzzy neural network .The results show that it can avoid obstacles effectively.

[Key words] Trajectory planning；artificial potential fields；heuristic algorithm；ant colony optimization algorithm；genetic algorithm

路径规划技术是移动机器人研究领域中的重要组成部分[1]，主要方法有可视图法[2]、栅格法[3]、人工势场法[4]、模糊逻辑法[5-6]、神经网络法[7]、蚁群算法[8]等智能算法。本文介绍了几种路径规划方法特点和国内外研究学者提出的改进算法；其次，针对人工势场法的不足提出了一种改进方法并对其做了仿真分析；最后，列举了模糊神经网络法实例，应用结果表明该方法可以有效地避开障碍物到达目标位置。

1 几种路径规划方法

1.1 人工势场法

人工势场法 （Artificial Potential Field）是由Khatib于1986年提出的一种虚拟力法[9]，它的基本思想是建立一个虚拟势场函数，该势场函数可以按一定的规律对机器人产生虚拟力。此算法优点是规划的路径较为平滑，但存在局部极小值、目标不可达问题。

针对上述问题，国内外研究学者提出了有效解决方法。国内哈尔滨工业大学于振中等[10]构造改进的人工势场模型，使用势场强度代替力矢量进行路径规划。刘传领[11]提出当机器人陷入局部最小值状态时，引入逃脱力函数使其摆脱局部最小的限制。于魁龙等[12]提出模糊控制和人工势场相结合的路径规划方法。王丽[13]引入了“follow-wall行为”，使机器人沿着障碍物边界行走，能迅速摆脱局部极小值问题。国外Prahlad Vadakkepat[14]在势场函数中引入了逃脱力，使机器人摆脱局部最小的限制。Josu Agirrebeitia等[15]建立一个新的势场函数和短程曲线实现路径规划，可以解决局部最小值问题。TingChen等[16]利用栅格法建立模型，然后采用人工势场法与遗传算法相结合的方法生成避障路径。Jean Bosco Mbede等[17]利用人工势场法与模糊逻辑控制法相结合的方法来解决局部最小值问题。

1.2 A*算法

A*（A-star）算法是一种典型的启发式搜索算法，是基于栅格地图法的一种路径搜索算法[18]。该算法从起点开始，检查其相邻的方格，寻求估值函数最小值，然后向四周扩展，直至找到目标。该算法搜索速度很快，但用它搜索出的路径受栅格的限制仍然无法保证规划的路径最短。

针对上述问题，国内北京工业大学张晓[19]利用传统A*算法搜索出路径，然后优化路径点。陈圣群 [20]

采用A*算法和D*算法结合方法搜索出最优路径。史辉等[21]改进A*算法估值函数，再利用K-d树空间索引结构，动态加载节点信息实现路径规划。国外Daniel Cagigas[22]改进了A*算法，构造地图并利用预先计算路径（物化路径的成本）方式，使得算法运行速度更快、时间更短、规划出的路径最优。Sloman Aaron[23]用动态A*算法寻找次优无碰路径，再用蚁群算法优化次优路径，算法结合改善了收敛速度，提高了效率。Marija Dakulovi?等[24]利用Witkowski算法[25]和动态A*算法相结合，可以寻求最短路径。

1.3 蚁群算法

蚁群算法（Ant Colony Optimization，简称ACO）是意大利学者Dorigo M等在20世纪90年代初提出的一种仿生类智能算法[26]。它是利用蚂蚁找寻食物过程中释放的信息素（也称外激素）使一定范围内的其他蚂蚁能够感觉到这种物质，并朝着物质强度高的方向移动，从而实现路径规划。蚁群算法具有信息反馈机制以及分布式计算特征，但求解速度慢，易陷入局部最优，且初期信息素匮乏会导致算法停滞。

针对上述问题，国内外研究人员相继提出路径规划的改进蚁群算法。国内复旦大学的陈雄等[27]引入限定信息素和自适应信息素挥发系数来解决蚁群算法应用中的停滞现象和搜索能力差的问题。毛琳波[28]利用蚁群算法搜索，在蚂蚁搜索到死角时建立相应的死角表，同时用惩罚函数更新轨迹强度，从而改善算法的性能，避免机器人路径规划出现死锁。邓高峰等[29]充分利用粒子算法和蚁群算法的优点，收敛到全局最优。南开大学任春明等[30]改进了蚁群算法收敛速度慢的不足，融入了遗传算法的交叉、变异操作来加快算法收敛。赵百铁[31]提出了一种四叉树和蚁群算法相结合的思想，可以解决机器人在大范围二维平面区域路径规划的问题。国外T.Stutzle [32]提出设置信息素上下限来避免算法出现过早停滞现象。Kwang-Seon Yoo[33]提出了基于蚁群算法动态拓扑优化的二维结构，改善了传统算法计算效率问题。Rana Forsati等[34]通过调整信息素值来防止过早收敛。M.A. Porta Garcia等[35]提出实时更新信息素可以改善蚁群算法的不足，并用模糊控制法进行优化。

1.4 遗传算法

遗传算法（Genetic Algorithms，简称GA）最初是由美国密歇根大学Holland 教授于1969年提出的，它是通过模拟自然界生物遗传机制和生物进化论而形成的一种随机搜索最优解的方法[36]。遗传算法操作简单，能克服人工势场法局部最优解导致死锁的问题，搜索从群体出发，具有潜在的并行性，实时性好等优点。但运算速度慢，局部寻优能力差，存在早熟收敛，随机游走会导致收敛性差、搜索时间长等问题。

针对上述缺点，国内外学者提出了改进算法。何娟等[37]先利用遗传算法计算初始信息素分布，然后再用蚁群算法优化。有效地结合了遗传算法的快速收敛性和蚁群算法的信息正反馈机制，改善了各自的不足。徐美清[38]引入路径修复机制来提高遗传算法的收敛速度。丁彪[39]利用概率快速随机搜索算法生成初始路径，再利用遗传算法优化，不仅降低计算复杂度，而且加快了收敛速度。张荣松[40]将复杂的二维编码问题简化为一维编码问题，优化并改进了标准遗传算法的选择算子和交叉算子，以移动机器人最短路径作为适应度函数进行优化，克服了遗传算法早熟收敛和运算结果不稳定等问题。Hong Qu等[41] 通过改变遗传算子寻求最优路径。Tuncer等[42]针对机器人动态路径规划提出了改进遗传算法，避免了早熟收敛问题。

2 仿真

本文利用MATLAB 2010a软件针对人工势场法进行仿真分析。

仿真主要步骤是先初始化起始点、目标点以及障碍物的位置，设定增益系数，障碍物的影响距离和机器人移动步长，然后计算机器人引斥力、合力、航向角及下一点位置，最后判断是否到达目标点。仿真流程图如图1所示。

仿真结果表明，改变斥力势函数可以解决人工势场法目标不可达问题。仿真结果如图2所示。图中黑色实体为障碍物，白色圆圈为目标点。

3 避障实例

本实验室采用模糊神经网络的方法实现机器人避障[43]，编程在VisualC++ 6.0环境中实现。表2为模糊控制规则表。实验用到的移动机器人为四轮式HEBUT-Ⅱ型移动机器人，如图3所示。图4为在C++环境中制作的模糊神经网络界面，图5为控制面板上实际移动机器人避障轨迹图，图6可以看到移动机器人正在躲避障碍物，实验表明，HEBUT-Ⅱ移动机器人可以有效地避开障碍物。

4 结束语

本文针对人工势场法的不足提出了改进算法并对其做了仿真分析。对于HEBUT-Ⅱ的路径规划问题采用模糊神经智能方法，实例结果表明该方法可以顺利躲避障碍物到达目标位置。该实例为日后路径规划研究奠定了基础。

参 考 文 献

[1] 朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策，2010，25（7）：961-967.

[2] 杨淮清，肖兴贵，姚栋.一种基于可视图法的机器人全局路径规划算法[J].沈阳工业大学学报，2009（2）：225-229.

[3] 王娟娟，曹凯.基于栅格法的机器人路径规划[J].农业装备与车辆工程，2009（4）：14-17.

[4] 张殿富，刘福.基于人工势场法的路径规划方法研究及展望[J].计算机工程与科学，2013，35（6）：88-95.

[5] 朱长顺，赵永升. 应用于汽车操纵稳定性试验的转向机器人控制器设计[J].现代仪器与医疗，2013，19（2）：20-23.

[6] 苏治宝，陆际联.用模糊逻辑法对移动机器人进行路径规划的研究[J].北京理工大学学报，2003，23（3）：290-293.

[7] 邢军，王杰.神经网络在移动机器人路径规划中的应用研究[J].微计算机信息，2005（22）：110-111.

[8] Wang Zhangqi ，Zhu Xiaoguang ，Han Qingyao.Mobile Robot Path Planning based on Parameter Optimization Ant Colony Algorithm[J].Procedia Engineering，2011 （15）：2738-2741.

[9] 赵荣奇.基于人工势场法的机器人路径规划研究[D].山东：山东大学机械制造及其自动化，2008.

[10] 于振中，闫继宏，赵杰，等.改进人工势场法的移动机器人路径规划[J].哈尔滨工业大学学报，2011，43（1）：50-55.

[11] 刘传领.基于势场法和遗传算法的机器人路径规划技术研究[D].南京：南京理工大学计算机学院，2012.

[12] 于魁龙，贾小平，曹有辉，等.基于混合算法的局部路径规划[J].装甲兵工程学院学报，2008，22（2）：43-45.

[13] 王丽.移动机器人路径规划方法技术研究[D].西安：西北工业大学航海学院，2007.

[14] Prahlad Vadakkepat，Tong Heng Lee，Liu Xin.Application of Evolutionary Artificial Potential Field in Robot Soccer System[J].IEEE，2011：2781-2785.

[15] Josu Agirrebeitia，Rafael Aviles et al.A new APF strategy for path planning in environmentswith obstacles[J].Mechanism and Machine Theory，2005（ 40）： 645-658.

[16] Qiushi Zhang， Dandan Chen， Ting Chen. An Obstacle Avoidance Method of Soccer Robot Based on Evolutionary Artificial Potential Field[J].Energy Procedia， 2012 （16）：1792-1798.

[17] Jean Bosco Mbede，Xinhan Huang，Min Wang.Fuzzy motion planning among dynamic obstacles using arti?cial potential ?elds for robot manipulators[J].Robotics and Autonomous Systems， 2000 （32） ：61-72.

[18] 吴超帅.改进A*算法及其在ASR移动机器人路径规划中的应用[D].湘潭：湘潭大学信息工程学院，2012.

[19] 张晓.全方位移动平台的设计以及定位和路径规划[D].北京：北京工业大学机械工程学院，2013.

[20] 陈圣群，董林飞.Dijkstra和A-star算法在智能导航中的应用分析[J].重庆科技学院学报（自然科学版），2010，12（6）：159-161.

[21] 史辉，曹闻，朱述龙，朱宝山.A*算法的改进及其在路径规划中的应用[J].测绘与空间地理信息，2009，32（6）：208-211.

[22] Daniel Cagigas.Hierarchical D*algorithm with materialization of costs for robot path planning[J].Robotics and Autonomous Systems， 2005（52）：190-208.

[23] TAN Guan-Zheng，HE Huan，SLOMAN Aaron.Ant Colony System Algorithm for Real-Time Globally Optimal Path Planning of Mobile Robots[J].Acta Automatica Sinica，2007，33（3）：279-285.

[24] Marija Dakulovi?， Ivan Petrovi?.Two-way D* algorithm for path planning and replanning[J]. Robotics and Autonomous Systems， 2011 （59）： 329-342.

[25] C. Witkowski， A parallel processor algorithm for robot route planning， in： Int.Joint Conf. on Artificial Intelligence， IJCAI， Karlsruhe， West Germany， 1983， 827–829.

[26] Fan Xiaoping. Optimal path planning for mobile robots based on intensified ant colony optimization algorithm[C].Proceedings of 2003 IEEE International Conference on Robotics， Intelligence Systems and Signal Processing， 2003.131-136.

[27] 陈雄，袁杨.一种机器人路径规划的蚁群算法[J].系统工程与电子技术，2008，30（5）：952-955.

[28] 毛琳波，刘士荣，俞金寿.移动机器人路径规划的一种改进蚁群算法[J].华东理工大学学报（自然科学版），2006，32（8）：997-1001.

[29] 邓高峰，张雪萍，刘彦萍.一种障碍环境下机器人路径规划的蚁群粒子群算法[J].控制理论与应用，2009，26（8）：879-883.

[30] 任春明，张建勋.基于优化蚁群算法的机器人路径规划[J].计算机工程，2008，34（15）：1-3.

[31] 赵百轶，张利军，贾鹤鸣.基于四叉树和改进蚁群算法的全局路径规划[J].应用科技.2011，38（10）：23-28.

[32] T.stutzle and T.Hoos.Max-Min ant system and local search for combinatorial optimization problems[M].In S.Voβ，S.Martello，I.H.Osman，andC.Roucairol，editors Meta-Heuristics：Advances and Trends in Local Search Paradigms for optimization，Kluwer Boston，1998.

[33] Kwang-Seon Yooa， Seog-Young Han.A modified ant colony optimization algorithm for dynamic topology optimization[J].Computers and Structures， 2013 （123）： 68-78.

[34] Rana Forsatia， Alireza Moayedikiaa， Richard Jensenc.Enriched ant colony optimization and its application in feature selection[J].Neurocomputing， 2014 （142）： 354-371.

[35] M.A. Porta Garcia， Oscar Montiel， Oscar Castillo， etal， Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation[J]. Applied Soft Computing， 2009 （9）： 1102–1110.

[36] Holland JH.Adaption in natural and artificial systems[M].Ann Arbor University of Michigan.1975.

[37] 何娟，涂中英，牛玉刚.一种遗传蚁群算法的机器人路径规划方法[J].计算机仿真，2010，27（3）：170-174.

[38] 徐美清，孙晨亮.基于栅格地图的遗传算法路径规划[J].科技信息，2011（31）：76-77.

[39] 丁彪.基于改进遗传算法的移动机器人路径规划[J].自动化应用，2014（1）：1-3.

[40] 张荣松，包家汉.基于改进遗传算法的机器人路径规划[J].计算机技术与发展，2009，19（7）：20-23.

[41] Hong Qu， Ke Xing， Takacs Alexander.An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots[J].Neurocomputing ，2013 （120） ：509-517.

[42] Adem Tuncer， Mehmet Yildirim， Dynamic path planning of mobile robots with improved genetic algorithm[J].Computers and Electrical Engineering， 2012，38（6） ：1564-1572.

[43] 邢国芬.基于多传感器信息融合的移动机器人环境感知研究[D].天津：河北工业大学，2008.