移动机器人路径规划算法研究综述

    穆涛

    【摘 要】 机器人路径规划能够让机器人在移动过程中高效准确地避开障碍物，是目前机器人领域的研究热点，而规划算法的研究是为了提高机器人路径规划的搜索速度，缩短搜索时间。因此成为了路径规划的核心内容，本文重点将移动机器人路径规划分成全局规划和局部规划两类，然后对各类方法所对应的相关算法优缺点和改进现状进行分析和归纳，最后提出了移动机器人未来在路径规划研究的发展方向。

    【关键词】 移动机器人 全局路径规划 局部路径规划 混合路径规划

    1.引言

    近年来移动机器人目前在工业、农业、军事、服务业等领域得到广泛应用。实现机器人在未知环境下路径规划是一个关键技术问题，直接影响着机器人的智能水平。因此研究机器人路径规划对提高机器人的智能化水平、加快我国工业化进程具有重要的战略意义。

    移动机器人路径规划是指在工作环境中依照一个或多个评判标准（如时间最短、能耗最少等）寻找出一条从起始点到目标点的最优或次优的无碰撞路径。本文根据机器人对环境信息的掌握程度将路径规划分为全局路径规划和局部路径规划。全局路径规划可获取全局最优或次优路径。局部路径规划可实现实时动态路径规划，具有较高的灵活性和实时性。下面将对这两类常用算法进行详细分析。

    2.全局路径规划

    2.1 A*算法。A*算法是一种静态路网中求解最短路径的最有效搜索方法，它通过遍历当前节点的所有子节点，然后选择估价代价最小的节点作为路径节点，基于此节点再次进行下一步搜索，从而完成整个搜索过程，有搜索节点多和拐点过多的缺点。王中玉通过改进评价函数的权重比例和改进路径生成策略，来减少生成路径中的冗余点和拐点，以此来提高路径的平滑性，进而提高路径的搜索效率;李强则通过限制当前节点只朝目标节点所处的一个象限进行节点扩展，有效降低了寻路过程中搜索的节点数，提高了路径搜索效率。

    2.2 智能仿生算法。智能仿生算法是模拟生物进化和仿自然界动物昆虫觅食筑巢等行为的算法，主要有遗传算法、蚁群算法、粒子群算法等。

    遗传算法模拟自然界生物进化过程，通过选择、交叉、变异等操作搜索最优解，可同时处理多个个体，具有较高的自适应性和并行性，但有搜索耗时长，易出现局部最优解的缺點。王功亮对适应度函数添加转弯角度控制因子，把路径最短和转弯角度作为路径个体适应度函数值大小的影响因素，最后规划出的路径轨迹转弯次数减少且更加平滑;孙波通过对交叉、变异算子自调整策略进行改进，提高了算法的收敛速度。

    蚁群算法来自于对蚂蚁觅食行为的探索，蚂蚁在觅食过程中会在已行走过的道路上留下一种称为信息素的物质，特定时段上蚂蚁遍历的次数越多信息素浓度就越高，后继觅食的蚂蚁会根据信息素的浓度确定行走路径，这样浓度高的路径会被选为最优路径。但蚁群算法存在计算周期长、收敛慢、易出现局部最优等问题。徐宏宇等采用自适应启发式函数，增加目标点的吸引力，使路径快速准确的收敛于最优路径;封声飞等对初始信息素进行差异化分配并对路径启发信息进行改进，提高了算法收敛速度和蚂蚁搜索效率。

    粒子群算法是模拟鸟群飞行捕食行为，获得多维度寻优能力的一种算法，它和遗传算法相似也是从随机解出发，通过迭代寻找最优解。与遗传算法相比有实现简单，收敛快的优点，但存在过早收敛的问题，搜索性能对参数的依赖性过也过大，易于陷入局部极小值。魏勇通过引入差分进化算法来动态调整变异概率和缩放因子，增加种群中个体的多样性，扩大算法的搜索范围，从而避免局部最优路径的产生，最后结果验证了所提方案的有效性和可行性。王志中在路径规划中通过引入了跳出机制和牵引操作，跳出机制保持了种群多样性和全局搜索能力，牵引操作加快了算法收敛速度，结果显示规划出的路径在平滑度、规划时间上较传统粒子群算法具有优势。

    3.局部路径规划

    3.1 动态窗口法。动态窗口法主要是在速度（v，w）空间中采取多组速度，并模拟机器人在这些速度下一定时间内的轨迹，在得到多组轨迹后，对于这些轨迹进行评价，选取最优轨迹所对应的速度来驱动机器人运动。它有计算不复杂，快速求得最优解的优点，但是较高的灵活性会极大的降低行驶的平稳性。程传奇提出了一种融合改进A*算法和动态窗口法的全局动态路径规划方法，在A*规划的全局路径的基础上，通过动态窗口法进行实时动态路径规划，提高了路径平滑性及局部避障能力。

    3.2 人工势场法。人工势场是抽象的人造受力场，通过目标点产生的引力和障碍物产生的斥力的合力来控制移动机器人的运动。该方法结构简单，便于底层的实时控制，规划出来的路径一般是比较平滑并且安全，但仍存在局部最优和易在狭窄通道中动荡的缺点。陈金鑫针对人工势场法存在的局部极小缺陷，引入斥力偏转模型，引导机器人在路径规划时避开局部极小点，再引入斥力增益系数函数，进一步优化路径规划中航向改变过大的问题，在解决部分局部极小问题的同时提高了规划路径的质量，解决了静态环境下机器人的路径规划问题;罗强在传统的人工势场法中同时引入相对速度和相对加速度因素，实现了机器人在动态环境下的自主移动。

    3.3 神经网络法。人工智能领域中的一种新型算法，模拟动物神经网络行为，进行分布式并行信息处理。神经网络具有优秀的学习能力，但是一些情况下存在错判的问题。王耀南针对神经网络在一些情况下存在的路径非最优问题，通过对边界附近和障碍物之间的路径点引入了假想的非障碍物相邻点，增大了激励输入，使得路径点的活性值增大，改进后的生物激励神经网络方法适用于实时动态环境下的移动机器人路径规划，且全面提升了路径质量。

    4.混合路径规划方法

    移动机器人路径规划方法研究虽然取得了重大成果，但在进行局部或全局路径规划时各种算法仍存在一定的局限性，因此混合路径规划算法开始引起大众关注。相比全局和局部路径规划方法混合路径规划效率更高、实用性更强，目前多采用两种算法结合的方法弥补各自存在的问题。孙波等在遗传算法的选择操作中引入模拟退火思想来提高算法的全局搜索能力，实验表明改进后的算法效率好、可靠性高;陈尔奎采用改进的遗传算法进行全局路径规划然后在规划好的路径的基础上用改进的人工势场法进行局部动态避障，解决了局部极小点问题，最后规划的路径的时间和长度都有所缩短。混合路径规划算法虽在一定程度上弥补了单个算法的缺陷，但也存在着算法复杂度增加，收敛速度慢等缺点。

    5.展望

    从移动机器人路径规划的研究现状以及发展需求看，未来移动机器人的路径规划研究主要集中在以下四个方面。

    1）现有算法的改进。虽然关于路径规划算法很多，并且取得很多成果，但是每种算法都有自己的局限性，不能很好地适应更复杂的环境，因此对算法进行不断的创新改进俨然成为了一个成本相对较低突破点;

    2）新路径规划算法的研究。随着科技的发展，寻找更新更优的路径规划算法解决复杂的路径规划问题将会成为一种趋势。比如近几年兴起的深度学习、强化学习等或是未来新的仿生算法的出现;

    3）多机器人协同路径的研究。随着机器人工作环境的不断扩大、任务的复杂度的增加以及应用范围的扩大，系统需根据环境和任务在保证成员之间相互交换信息的前提下高效、快速、准确地组织多个机器人协同并行的完成多个任务;

    4）路径规划算法的有效结合。任何的单一路径规划算法都不可能解决所有实际应用中的路径规划问题，特别是面对复杂环境下的任务，加之研究新算法的难度较大，将出现更多的相互结合的路径规划算法来弥补彼此的不足。

    6.总结

    本文通过对全局和局部路径规划两类算法所对应的常用算法的发展现状和优缺点进行分析和归纳，指出了路径规划算法未来的研究方向。随着科技的发展，路径规划技术将会在更多的领域得到应用，并且将深入到我们生活的方方面面。

    【参考文献】

    [1] 王坤.基于遗传算法的移动机器人路径规划研究[D].哈尔滨工业大学，2012.

    [2] 王耀南，潘琪，陈彦杰.改进型生物激励神经网络的路径规划方法[J].控制工程，2018.

    [3] 陈尔奎，吴梅花.基于改进遗传算法和改进人工势场法的复杂环境下移动机器人路径规划[J].科学技术与工程，2018，18（33）：84-90.

    [4] 霍凤财，迟金，黄梓健.移动机器人路径规划算法综述[J].吉林大学学报（信息科学版），2018，36（06）：46-54.

    [5] 王春颖，刘平，秦洪政.移动机器人的智能路径规划算法综述[J].传感器与微系统，2018，37（8）：5-8.

    [6] 王志中.基于改进粒子群算法的机器人路径规划[J].制造技术与机床，2018， No.668（02）：159-163.

    [7] 朱龙彪，王景良，王辉.一种基于动态时间窗的泊车系统路径规划方法[J].工程设计学报.2018.

    [8] 赵江，张岩，马泽文.对AGV路径规划A星算法的改进与验证[J].计算机工程与应用，2018，54（21）：222-228.

    [9] 张福海， 李宁， 袁儒鹏. 基于强化学习的机器人路径规划算法[J]. 華中科技大学学报（自然科学版）， 2018， 46（12）：70-75.