摘   要： 移动机器人路径规划技术是机器人研究领域中的核心技术之一。通过对全局路径规划和局部路径规划中各种方法的分析，指出了各种方法的优点和不足以及改进的办法，并对移动机器人路径规划技术的发展趋势进行了展望。
关键词： 移动机器人； 路径规划； 遗传算法

    移动机器人是装备了机械腿、轮子、关节、抓握器等执行器以及控制器来完成特定任务的一种实体智能体。近年来，随着科学技术的飞快发展，移动机器人在工业、农业、医疗、服务、航空和军事等领域得到了广泛的应用，已成为学术研究的重点。在移动机器人的研究中，导航研究是核心，而路径规划是机器人导航研究的重要环节之一。在机器人执行任务时，要求机器人在工作环境中（有障碍物或无障碍物）能根据一定的评价标准搜索一条从起始地点到目标地点的最优或次优路径[1]。移动机器人的路径规划根据环境是否已知可分为基于地图的全局路径规划和基于传感器的局部路径规划。
1全局路径规划
1.1栅格分解法
    栅格分解法是目前广泛研究的路径规划方法之一。该方法把移动机器人的运动环境分解为多个简单的栅格并根据它们是否被障碍物占据来进行状态描述，障碍物栅格和非障碍物栅格具有不同的标识值，它能快速直观地融合传感器信息。但是为了得到比较精确的规划结果，必须将环境划分为较小的栅格，这就导致存储空间增大，在大规模环境下路径规划的计算复杂程度将加大。为了克服栅格表示的存储空间问题，邰宜斌提了一种四叉树分割方法[2]，该算法递归地把环境分解为大小不一的矩形区域，这些矩形区域或者完全被障碍物占据，或者是完全自由可行的。每次递归都将一个较大的栅格划分为4个较小的栅格，取得了较好的计算效果。另外栅格分解法随着机器人自由度的增加会出现“维数灾难”问题，不适用于解决多自由度机器人在复杂环境中的路径规划。Frank在2004年提出了概率栅格分解算法，在该算法中引入随机采样，可使多自由度机器人在复杂环境中快速找到一条可行路径。2006年吕太之等在概率栅格分解算法的基础上引入了Anytime算法，将随机采样应用到栅格分解算法中，使算法效率得到了提高，但是受环境信息和随机采样的影响比较大[3]。
1.2拓扑法
    拓扑法主要包括三部分：划分状态空间、构建特征网、在特征网上搜索路径。拓扑法的基本要素是节点和边，用节点表示某个特定的位置，用边表示这些位置之间的联系，可以用G=(V,E)描述空间的特征，其中V表示顶点集合，E表示连接顶点的边集合[4]。利用该方法可缩小搜索空间，使得存储需求小，适合于大规模环境的路径规划，但是构建特征网的过程比较复杂，而且当障碍物增加时如何将增加的节点与已有节点进行节点匹配是一个难点。2005年，王力虎等提出了一种适用于清扫机器人的区域充满拓扑算法，用传感器感知环境信息以建立环境的拓扑地图，机器人可以利用搜索图的方法搜索环境，可达到环境的有效覆盖，但在搜索时没有具体体现节点间的距离、清扫覆盖率等信息，使得搜索效率不是很高[5]。2006年，种琤等提出了一种基于扫描法的构造环境拓扑图方法，利用启发式函数法实现对所构建拓扑图的扩展，采用了逐步构建环境拓扑图的方式，实现了在线构建,可应用于任意工作环境，且计算复杂度低，但此算法不能保证搜索到最优路径[6]。
1.3惩罚函数法
    在机器人运行环境中因为有障碍物，使得机器人的路径规划成为一个有约束的问题，惩罚函数法将这个有约束的问题转化为一系列无约束极小化问题，再通过解决这些无约束问题获得原约束问题的最优解[7]。柳在鑫、王进戈等在2009年将机器人的路径规划问题转化为一类带有不等式约束条件的非线性极小化问题，并采用惩罚函数法来求解此类问题，该方法原理简单，算法易行，使用范围广[8]。
2 局部路径规划
2.1人工势场法
    人工势场法是机器人局部路径规划中最经典的方法，该方法是由Khatib在1986年提出的，它的基本原理是：把机器人在工作环境中的运动看作是在一个人造受力场中的运动，其中目标对机器人产生引力，障碍物对机器人产生斥力，机器人在这两类力的合力作用下向目标前进[9]，该合力就是机器人的加速度力，可用来控制机器人的运动方向，利用人工势场法进行机器人的路径规划,计算简单，所规划的路径光滑，有较好的实时性，但会因为局部最小值而导致目标点不能到达。近几年来国内陆续有学者提出了一些改进方法。2006年，刘义等提出了修改斥力函数法，用来解决局部最小值问题[10]。哈尔滨工业大学的张建英等提出了添加附加控制力的方法，即当机器人在障碍物附近振荡，无法离开障碍物时，给机器人施加一个控制力，使机器人绕过障碍物向目标位置前进，但通过此方法规划的路径在障碍物边缘有抖动现象产生[11]。
2.2遗传算法
    遗传算法(GA)的概念最初是由Bagley和Rosengerg于1967年在其博士论文中首先提出了的。在1975年美国Michigan大学的J. Holland教授把它写到了专著《Adaptation in Natural and Artificial Systems》中，此后GA才逐渐为人所知，并且广泛应用到控制、规划、优化设计等方面。利用GA算法对移动机器人进行路径规划的基本步骤为：
　 (1)选择编码方式，并将路径用编码表示；
　 (2)产生初始群体；
　 (3)确定适应度函数并根据适应度函数计算初始群体的适应度值；
　 (4)如果不满足条件，{选择、交换、变异、计算新一代群体的适应性值}；
　 (5)输出结果。
    遗传算法直接对移动机器人的路径进行操作，采用概率化的寻优方法，自适应地调整搜索方向，不采用确定性搜索规则，易于并行化，但对于未知复杂环境，利用遗传算法进行路径规划时运算速度慢，而且需要占据大量的存储空间。近几年许多研究学者提出了一些改进后的遗传算法，例如王洲等提出了移动机器人在静态障碍物环境中路径规划的新方法，该方法设计了5个遗传算子（选择、交叉、变异、删除、插入），并且提出了新的变异算子、插入算子和删除算子，加快了较好个体在群体中的传播，提高了路径搜索速度和解的精度[12]。对于遗传算法的改进，王新杰等将其与图搜索法相结合，用Dijkstra算法王求得初始路径，再利用遗传算法的一系列选择、交叉、变异操作来优化路径，这种方法减少了搜索的盲目性，不会产生无效路径[13]。当机器人处于静动态障碍物同时存在的环境中时，卢瑾等在机器人路径规划时引入了双重遗传算法机制，第一重算法针对静态障碍物环境，第二重算法针对动态障碍物环境，两重算法采用不同的适应度函数作为评价标准，通过改进操作算子、引入优化算子，可快速有效地找到同时能避开静动态障碍物的最优路径，仿真结果验证了该方法的有效性。但对于动态的、未知复杂环境下的路径规划没有进行验证[14]。
2.3模拟退火算法
　模拟退火算法（SA）依据固体退火原理，固体在加温时，内部粒子运动随温升增强，变为无序状，再进行退火，粒子运动减弱并渐趋有序，最后达到稳定。把机器人在未知环境中的运动看作是粒子的布朗运动，可以对其随机性的扰动应用模拟退火算法来引导机器人向势能最小的方向运动，从而实现机器人在线的路径规划[4,15]。利用SA进行移动机器人路径规划的一般步骤如下：
　 (1)初始化运行参数，给定起始点、终止点及初始搜索方向；
　 (2)确定势能函数和方向函数，对k=1，…，L（迭代次数）做第(3)至(6)步；
　 (3)产生新解；
    (4)建立局部寻优评估函数，计算增量；
　 (5)若增量小于零则接受新解作为新的当前解，否则根据Metropolis以概率e-ΔE/(kT)接受新解作为新的当前解；
　 (6)输出最优解。
    模拟退火算法与初始值无关，具有描述简单、使用灵活、鲁棒性强等优点，当退火速度慢时执行时间长、收敛速度慢，得到的解性能比较好，当退火速度快时可能得不到最优解。对于模拟退火算法的改进可以从采用并行搜索结构、改进对温度的控制方式、设计合适的评估函数等方面进行。王仲民等在用模拟退火算法对移动机器人进行路径规划时减少了路径搜索过程中所出现冗余路径点的数量，重新生成路径，生成后的路径减少了迂回，有效提高了算法的收敛速度[16]。
2.4蚁群算法
    蚁群算法是由Dorigo M在1991年提出的,主要应用于旅行商问题（TSP）、调度问题（JSP）、车辆路线问题（GCP）[17]，近年来一些学者例如Liu G利用蚁群算法进行机器人路径规划的研究[18],利用蚁群算法进行移动机器人路径规划的一般步骤如下：
　 (1)建立环境模型；
　 (2)建立巢穴邻近区和食物气味区；
　 (3)在邻近区放足够多的蚂蚁；
　 (4)每只蚂蚁方向函数选择行走栅格；
　 (5)若产生无效路径则删除，否则直到蚂蚁到达食物终点；
　 (6)调整有效路径并保存最优路径；
    (7)更改有效路径的信息。
    重复(3)~(7)直到达到某个迭代次数，结束整个算法[4]。
    蚁群算法由于采用启发式搜索，容易陷入早熟，而很难发现其他更优路径，可以结合启发式搜索和随机搜索的方法进行改进。例如杨志晓等提出了一种改进的蚁群算法，该算法在对机器人进行路径规划时引入了优先级和起始目标导引函数，采用状态转移概率和优先级的组合优化方法来平衡各路径的信息量，算法在初始阶段的搜索范围大，有效避免了早熟现象，算法在后期根据起始目标导引函数来寻求最优路径[19]。
3 混合路径规划方法
    混合路径规划方法是结合一种或两种算法的优点，相互之间取长补短，以提高规划效率。郑秀敏等在2007年提出了一种栅格法-模拟退火法，即用栅格法表示环境信息，利用模拟退火算法进行局部路径规划，使路径跳出局部极小值，到达目标位置[20]。
    黄席樾等在对移动机器人进行静态路径规划时提出了一种基于神经网络模型的遗传算法和模拟退火算法相结合的方法，对环境采用神经网络模型表示，利用中间路径点不在障碍物内的约束条件建立与神经网络的输出关系，编码时把无碰撞作为约束条件，把最短路径作为适应度函数选择的条件，仿真结果表明,该方法在路径规划时收敛性好,有效地提高了路径规划的质量[21]。杜宗宗等在移动机器人的路径规划中运用模拟退火算法对遗传算法进行优化，并将避开障碍物的初始种群生成方法和基于启发式知识的遗传算子的设计方法应用其中，避免了遗传算法收敛较慢、局部寻优能力差、易陷入局部极值点等缺点，使得遗传算法和模拟退火算法在路径规划中达到优势互补的目的；仿真结果表明，在种群规模较大且进化代数充足的情况下，该算法的成功率更高、平均代价值更小、路径长度更短[22]。
    续欣莹等提出了一种基于人工免疫势场法的移动机器人路径规划算法，该算法在生成初始路径群后将路径长度作为适应度函数，通过免疫操作进行路径优胜劣汰的选择，有效防止了“早熟收敛”现象的产生，仿真结果表明了该算法的有效性[23]。
    国海涛等提出了一种结合蚂蚁算法与遗传算法的机器人路径规划方法，先用栅格法对机器人的运动空间建模，然后用蚂蚁算法进行全局搜索，搜索出一条导航路径，再对该路径上的点用遗传算法进行调节，最后得到近似最优路径，仿真结果表明该方法能使机器人快速规划出路径，具有操作简单、不会陷入局部最优等优点[24]。肖本贤等提出了一种在复杂环境中机器人路径规划的新方法，该方法为了缩小最优解的范围采用随机搜索和重点搜索相结合的搜索方式，同时采用最大-最小蚂蚁系统MMAS算法[25,26]的思想动态调整路径上的信息激素，缩短了搜索时间，大大减小了陷入局部解的概率[27]。
4 展望
    (1)对环境的感知技术。机器人必须通过传感器感知环境的信息，处理器通过处理这些传感器信息后，进一步决策机器人的具体行为。如何正确地感知环境信息，关键在传感器，只有先进的传感器才能有效地采集环境信息，从而提高机器人动作的准确性。目前超声波、激光雷达、视觉等传感器在移动机器人中得到了实际应用，但是这些传感器都有一定的局限性，例如超声波传感器的检测范围取决于其使用的波长和频率，视觉传感器所获得图像的清晰和细腻程度取决于分辨率，分辨率越高图像越清晰，但所需的存储空间就越大，图像分析和处理速度就越慢。所以对移动机器人的环境感知技术将是未来移动机器人研究的一个突出方面。
    (2)多传感器信息融合技术。多传感器信息融合的目的是提高系统的可靠性和鲁棒性，在移动机器人路径规划中，传感器起了很重要的作用，多传感器所获得的信息具有冗余性、互补性、协同性，可对现场环境进行快速并行分析，有利于机器人快速找到有效路径。但是多传感器信息融合技术还存在很多难题，例如如何减小信息融合的错误率、如何提高信息融合的实时性、如何建立有效的信息融合质量评价机制等。
    (3)群体机器人的路径规划技术。群体机器人在协作工作时都希望能找到一条无碰撞、最快到达目标的路径，群体机器人路径规划既要考虑避障又要考虑机器人之间的相互协作，在路径规划上难度将增加，另外当目标点移动时还要考虑目标的位置信息和速度信息，整个路径规划将更加复杂，这方面研究是今后研究的重点。
    目前，对移动机器人的路径规划研究提出了很多方法，但尚未形成统一和完善的体系，还有许多关键问题例如机器人运动环境建模、机器人导航控制器的学习和优化、实时故障诊断、实时运动规划与控制等技术问题亟待解决和完善。
参考文献
[1] 李磊，叶涛，谭民,等.移动机器人技术研究现状与未来[J].机器人，2002，24（5）：475-480.
[2] 邰宜斌，席裕庚.一种机器人路径规划的新方法[J].上海交通大学学报，1996，30（4）：94-100.
[3] 吕太之，赵春霞.基于改进概率栅格分解的路径规划[J].计算机工程，2007，33（21）：160-165.
[4] 蔡自兴，贺汉根，陈虹.未知环境中移动机器人导航控制理论与方法[M].北京：科学出版社，2009.
[5] 王力虎，张海洪.室内清扫机器人区域充满拓扑算法[J].机械工程师，2005(1)：17-19.
[6] 种琤，陈阳舟,崔平远，等.基于扫描法在线构造拓扑图的路经规划算法[J].计算机仿真，2006，23(4)：147-150.
[7] 靖民，梁迎春．机械优化设计[M]． 北京：机械工业出版社，2007：145-150．
[8] 柳在鑫， 王进戈,王强，等．利用渐开线的足球机器人射门算法研究[J].西安交通大学学报，2009，43(1)：95-98．
[9] KHATIB. Real-time obstacle for manipulators and mobile robot[J]. The International Journal of Robotic Research, 1986,5(1):90-98.
[10] 刘义，张宇.基于改进人工势场法的移动机器人局部路径规划的研究[J].现代机械，2006（6）：48-49.
[11] 张建英，赵志萍，刘暾.基于人工势场法的机器人路径规划(J).哈尔滨工业大学学报，2006，38(8)：1306-1309.
[12] 王洲，张毅，杨锐敏，等.基于遗传算法的移动机器人路径规划[J].微计算机信息，2008，24(26)：187-189.
[13] 王新杰, 武秋俊.基于改进遗传算法的移动机器人路径规划[J].煤矿机械，2008，29(4)：28-30.
[14] 卢瑾，柳东勇.基于双重遗传算法机制的路径规划[J].系统仿真学报，2008，20(8)：2048-2051.
[15] KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by Simulated Annealing[J].Science, 1983,220(4598):671-680.
[16] 王仲民，岳宏,刘继岩.基于改进模拟退火算法的移动机器人路径规划[J].计算机工程与应用，2005，41(19)：59-60,82.
[17] DORIGO M, BONABEAU E. Ant algorithms and stigmergy [J].Future Generation Computer Systems, 2000(16):851-871.
[18] LIU G. The ant algorithm for solving robot path planning problem[C].Third International Conf.on Information Technology any Applications, 2005(ICITA2005),2005,2(4-7):25-27.
[19] 杨志晓,郭胜国.基于改进蚁群算法的机器人路径规划算法[J].微计算机信息，2008，24(20)：252-253.
[20] 郑秀敏，顾大鹏，刘相术.基于栅格法-模拟退火法的机器人路径规划[J].机器人技术，2007，23（2）：247-248.
[21] 黄席樾,蒋卓强.基于遗传模拟退火算法的静态路径规划研究[J].重庆工学院学报(自然科学版)，2007，21(6)：53-57.
[22] 杜宗宗，刘国栋.基于遗传模拟退火算法的移动机器人路径规划[J].计算机仿真，2009，26(12)：118-121.
[23] 续欣莹,谢裙，谢克明.基于人工免疫势场法的移动机器人路径规划[J].北京工业大学学报，2008，34(10)：1116-1119.
[24] 国海涛, 朱庆保，司应涛.一种蚂蚁遗传融合的机器人路径规划新算法[J].小型微型计算机系统，2008，29(10)：1838-1840.
[25] DORIGO M, GAMBARDELLA L M, MIDDENORF,et al.Guest editorial:special section on ant colony optimization[J].IEEE Transactions on Evolutionary Computation,2002,6(4):317-319.
[26] STUTZLE T, HOOS H. MAX-MIN ant system[J]. Future  Generation Computer Systems,2000,16(9):889-914.
[27] 肖本贤,刘刚,余雷.基于MMAS的机器人路径规划[J].合肥工业大学学报,2008,31(1):63-67.