马帅 王子铭

摘 要：移动机器人技术是近年来发展起来的一门重要学科，而路径规划是机器人研究领域的一个重要分支，它融合了机电工程、传感技术、自动控制、计算机技术及人工智能等多学科的最新研究成果，是当前人们最为热衷的科学技术研究方向之一。本文分析了目前广泛应用的移动机器人路径规划研究方法，详细介绍了環境建模方法和路径搜索算法，最后展望了移动机器人路径规划技术的发展趋势。

关键词：移动机器人;环境建模;路径规划

中图分类号：TP24文献标识码：A文章编号：1003-5168（2020）29-0014-03

Abstract： Mobile robot technology is an important subject developed in recent years， and path planning is an important branch in the field of robotics， which integrates the latest research results of multiple disciplines such as electromechanical engineering， sensor technology， automatic control， computer technology and artificial intelligence， and is one of the most popular scientific and technological research directions. This paper analyzed the currently widely used mobile robot path planning research methods， introduced the environment modeling method and path search algorithm in detail， and finally looked forward to the development trend of mobile robot path planning technology.

Keywords： mobile robot;environment modeling;path planning

路径规划技术在移动机器人技术研究领域中处于非常关键的地位，其目的是在移动机器人执行任务的周围环境有障碍物的情况下，依据某一种评价方法（所用经济代价最小或任务路径最短等），寻找出一条由初始状态（包含运动姿态和位置）到达目标状态的最优的无障碍路径。移动机器人的关键功能之一就是路径规划，是其实施避障任务和自主导航的基础，根据对环境信息的理解层次的不同，按其规划范围，可分为全局路径规划和局部路径规划[1]。全局路径规划又称离线规划，主要依据当前全局环境中掌握的所有信息，在全局地图上寻找全局最优路径或者是次优路径，它的作用是导引移动机器人向目标位置移动;局部路径规划是指在机器人运动过程中，利用自身装载的多种传感器来获取机器人周围的环境信息，并规划一条有效路径，通常具有较高的灵活性和实时性。

1 路径规划主要研究思路

路径规划是智能化和信息化技术在移动机器人应用研究中的重要表现，在操作者发出指令后，它可以自主添加执行任务细节，是完成其他高级任务的基础。移动机器人路径规划研究方向较多，人们可以从不同的切入点着手对其展开研究。但是，无论从哪一个侧重点进行分析研究，移动机器人路径规划研究方法一般可以归纳为参数输入、环境建模、利用合适算法规划路径、仿真输出结果等几个过程，其技术路线如图1所示。

移动机器人在路径规划的实际应用中需要解决两个主要问题：一是环境建模;二是路径搜索生成及处理策略[2]。本文先讨论环境建模方法，然后介绍路径规划算法，为学习人员提供一条思路。

1.1 环境建模

在执行路径规划任务时，移动机器人首先要获取即将行驶区域的环境地图。移动机器人主要依靠机身上配置的双目立体视觉、CCD工业摄像机、传感器等通过算法获得自身所处的位置，并在此基础上获取以上传感器所能够观测的一定范围内的地图信息。环境地图的主要创建方法是把移动机器人所在的相关环境信息分解为若干个形态各异的网格空间，利用多传感器获取的障碍物信息进行相关处理，最后依据某种设定规则来处理包含障碍物的网格信息。此时，环境地图信息已比较详尽，移动机器人可以利用处理好的环境信息进行路径规划。当前，环境地图的创建方法多种多样，拓扑地图、特征地图、栅格地图等是比较常见的地图创建方法，每种方法各有优劣势，适用于不同的应用场景。

1.1.1 拓扑地图。拓扑地图是一种通过化简和再调整，最终保留关键信息的地图，两点之间的距离及相对位置也不完全一定和实际的位置及距离对应。拓扑地图一般适合于规模较大的环境，多用图来进行表征。拓扑地图占用的存储空间小，在应用于移动机器人路径规划时，既简便又高效。不过，拓扑地图不能提供准确的尺度信息，所以其实并不适用于移动机器人的定位。

1.1.2 特征地图。特征地图是通过传感器采集周围环境的特征信息后，对其展开特征信息提取和共性信息挑选，得到简单几何特征而创建的地图。这种表示方法定位准确，实现起来较为简单，便于对障碍物信息进行特征识别和估计，其模型比较适合于计算机表示，参数化特征也和路径规划问题相匹配，但是该方法存在特征提取等预处理步骤，容易受到传感器的噪声干扰，因此不能推广应用在室外较为复杂的环境地图构建中。

1.1.3 栅格地图。栅格地图是在真实环境中通过数字化手段创建的地图。它将环境分解成一个个离散的栅格，每个栅格和现实环境中的一个小区域对应，表示环境区域是否存在障碍物。每个栅格都标有一个编号值，据此来分辨栅格所表征的环境区域的相对位置。环境信息可以被栅格地图详细描述，这种方法方便创建与维护。

1.2 常用路径规划算法

路径规划的核心是路径规划算法[3]，路径规划发展到今天，算法有很多种，比较常见的算法有以下几种：迪杰斯特拉算法、A*算法、D*算法、人工势场法、遗传算法（GA）等。

1.2.1 迪杰斯特拉算法。迪杰斯特拉算法又被称为Dijkstra算法，是由计算机专家E W Dijkstra提出的。它适用于有向图中，能够从一个顶点搜索到另一个顶点的最优路径。Dijkstra算法的特点是：选取一个节点作为移动机器人的起点，并由此起始点逐步对外扩展，直至抵达路径目标点所在的节点为止。Dijkstra算法作为一种最优化算法，它对于各个方向的搜索的可能性都是相等的，最终目的是寻找一个从初始状态到目标状态的最短路径，所以要遍历的节点很多，因此效率偏低。

1.2.2 A*算法。A*算法是一种启发式搜索算法（Heuristic Search Algorithm）[4]，它融合了广度优先搜索算法和迪杰斯特拉算法的优点，既获取最优的路径规划，又确保了搜索效率。因此，这种方法简洁快速，而且启发式搜索非常具有针对性，只要求获取搜索事件的部分状态空间信息，就能达到缩小搜索区域、减小搜索问题复杂度的目的，所有具有较高的路径寻找效率。但是，如果A*算法存在多個最小值，其不能保证搜索路径的最优化。

1.2.3 D*算法。D*算法是由Stentz提出的动态规划算法[5]，主要应用于面对周围未知环境或者存在动态变化的周围环境的场景，移动机器人在向目标位置搜索过程中只计算最短路径临近节点的更新情况。因此，该算法具有比较高的动态搜索效率，且可以处理任何成本参数发生变化的路径成本优化问题。D*算法是动态情景下的A*算法，但是对于远距离的最短路径上发生的变化，其计算工作量很大。

1.2.4 人工势场法。人工势场法是由Khatib提出的一种虚拟力场法。其基本原理可以这样描述：首先将移动机器人假设成一个点，在一种虚拟的受力场环境中运动。虚拟力场由引力场和斥力场组成，目标位置对移动机器人产生引力场，这种力随着移动机器人与目标位置的距离增大而减小（反比关系）;斥力场由测量环境中存在的所有障碍物产生的合力组成，这种力随移动机器人与障碍物距离的减小而增大（反比关系）。人工势场法的势场函数显示，移动机器人的运动方向取决于引力与斥力之间的矢量合，即势场函数下降的方向。这种方法在数学描述上结构简单，对底层的实时控制比较适用，缺点是容易陷入一些局部最优解的问题。

1.2.5 遗传算法。遗传算法（Genetic Algorithm，GA）是由Holland提出来的。20世纪60年代末，Holland受达尔文的自然选择和遗传机制等生物进化理论启发，研究并发展了一种随机搜索算法，其核心是寻找事件的最优解。其基本方法是：利用三个基本算子，即选择、交叉和变异设置机构的算法程序，对生物进化方向和过程进行数学方式的描述。该算法不寻求适应度函数是否存在可导或连续，而只限制其函数为正。同时，该算法作为并行算法，它的并行计算性能够完全适用于全局搜索。

2 路径规划技术的发展趋势

随着科学技术的飞速发展，移动机器人的应用范围越来越广泛，任务越来越复杂，各行业对移动机器人路径规划的能力需求随之提高，移动机器人的路径规划应用和研究呈现出一系列新的变化。

2.1 多源传感信息融合技术

目前，移动机器人应用趋于多元化，单一类型的传感器已经很难满足对环境信息的认识和理解。随着各个应用场景任务需求的增多，移动机器人捕获环境信息的感知能力和系统处理能力的要求不断提高。众所周知，相比传统的单一传感器，多源传感信息融合技术的测量精度更准确，能够更加全面地评估和描述被测对象与环境信息，从而使移动机器人做出正确的决策及判断。

2.2 多机器人协作控制

随着移动机器人的应用场景越来越多，单一机器人难以完成一些复杂的作业，因此采用多机器人相互协作共同完成指定任务是未来研究的一个方向。伴随科学技术的发展，工业、农业、医疗卫生、国防科技等行业对多机器人系统的需求越来越高，这种应用和研究仍然会继续发展。

2.3 多算法融合路径规划

目前，路径规划算法有人工势场法、A*算法、D*算法等，任何一个单独的算法都不足以解决实际应用中遇到的所有路径规划问题。新型交叉学科中容易出现新问题，创造新算法的难度大，而路径规划算法之间的优势互补可以有效提供一种解决问题的新思路[6]。人们可以将多种路径规划算法融合，以实现理想状态的路径规划。

3 结语

路径规划作为移动机器人导航技术的重要组成部分，是完成上层任务的先决条件，同时也是机器人具备智能化的重要标志。本文分析了移动机器人路径规划方法，详细介绍了环境建模方法和路径规划算法，展望了移动机器人路径规划技术的未来发展趋势，以期提高移动机器人路径规划水平。

参考文献：

[1]蒲兴成，李俊杰.基于改进粒子群算法的移动机器人多目标点路径规划[J].智能系统学报，2017（3）：301-309.

[2]郭江，肖宇峰.Bezier曲线与A*算法融合的移动机器人路径规划[J].微型机与应用，2017（2）：52-59.

[3]赵晓，王铮，基于改进A*算法的移动机器人路径规划[J].机器人，2018（6）：903-910.

[4]陈若男，文聪聪.改进A*算法在机器人室内路径规划中的应用[J].计算机应用，2019（4）：1006-1011.

[5]刘军，冯硕.移动机器人路径规划有向D*算法[J].浙江大学学报（工学版），2020（2）：291-300.

[6]霍凤财，迟金.移动机器人路径规划算法综述[J].吉林大学学报（信息科学版），2018（6）：639-646.