[科普中国]-路径规划

路径规划问题分类

根据对环境信息的把握程度可把路径规划划分为基于先验完全信息的全局路径规划和基于传感器信息的局部路径规划。其中，从获取障碍物信息是静态或是动态的角度看，全局路径规划属于静态规划(又称离线规划)，局部路径规划属于动态规划(又称在线规划)。全局路径规划需要掌握所有的环境信息，根据环境地图的所有信息进行路径规划；局部路径规划只需要由传感器实时采集环境信息，了解环境地图信息，然后确定出所在地图的位置及其局部的障碍物分布情况，从而可以选出从当前结点到某一子目标结点的最优路径。

根据所研究环境的信息特点，路径规划还可分为离散域范围内的路径规划问题和连续域范围内的路径规划问题。离散域范围内的路径规划问题属于一维静态优化问题，相当于环境信息简化后的路线优化问题；而连续域范围内的路径规划问题则是连续性多维动态环境下的问题。1

路径规划的一般步骤一般的连续域范围内路径规划问题，如机器人、飞行器等的动态路径规划问题，其一般步骤主要包括环境建模、路径搜索、路径平滑三个环节。

（1）环境建模。环境建模是路径规划的重要环节，目的是建立一个便于计算机进行路径规划所使用的环境模型，即将实际的物理空间抽象成算法能够处理的抽象空间，实现相互间的映射。

（2）路径搜索。路径搜索阶段是在环境模型的基础上应用相应算法寻找一条行走路径，使预定的性能函数获得最优值。

（3）路径平滑。通过相应算法搜索出的路径并不一定是一条运动体可以行走的可行路径，需要作进一步处理与平滑才能使其成为一条实际可行的路径。

对于离散域范围内的路径规划问题，或者在环境建模或路径搜索前己经做好路径可行性分析的问题，路径平滑环节可以省去。

常用算法路径规划的方法有很多，根据其自身优缺点，其适用范围也各不相同。根据对各领域常用路径规划算法的研究，按照各种算法发现先后时序及算法基本原理，将算法大致分为四类:传统算法、图形学的方法、智能仿生学算法和其他算法。2

传统算法传统的路径规划算法有：模拟退火算法、人工势场法、模糊逻辑算法、禁忌搜索算法等。3

（1）模拟退火算法（Simulated Annealing），简称SA)是一种适用于大规模组合优化问题的有效近似算法。它模仿固体物质的退火过程，通过设定初温、初态和降温率控制温度的不断下降，结合概率突跳特性，利用解空间的邻域结构进行随机搜索。具有描述简单、使用灵活、运行效率高、初始条件限制少等优点，但存在着收敛速度慢、随机性等缺陷，参数设定是应用过程中的关键环节。

（2）人工势场法是一种虚拟力法。它模仿引力斥力下的物体运动，目标点和运动体间为引力，运动体和障碍物间为斥力，通过建立引力场斥力场函数进行路径寻优。优点是规划出来的路径平滑安全、描述简单等，但是存在局部最优的问题，引力场的设计是算法能否成功应用的关键。

（3）模糊逻辑算法网模拟驾驶员的驾驶经验，将生理上的感知和动作结合起来，根据系统实时的传感器信息，通过查表得到规划信息，从而实现路径规划。算法符合人类思维习惯，免去数学建模，也便于将专家知识转换为控制信号，具有很好的一致性、稳定性和连续性。但总结模糊规则比较困难，而且一旦确定模糊规则在线调整困难，应变性差。最优的隶属度函数、控制规则及在线调整方法是最大难题。

（4）禁忌搜索算法（TS）是一种全局逐步寻优算法，是对人类智力过程的一种模拟。通过引入一个灵活的存储结构和相应的晋级规则来避免与会搜索，并通过藐视准则来赦免一些被紧急的优良状态，以实现全局优化。

图形学的方法传统算法在解决实际问题时往往存在着建模难的问题，图形学的方法则提供了建模的基本方法，但是图形学的方法普遍存在着搜索能力的不足，往往需要结合专门的搜索算法。图形学的方法有：C空间法、栅格法、自由空间法、voronoi图法等。

（1）C空间法又称可视图空间法，即在运动空间中扩展障碍物为多边形，以起始点、终点和所有多边形顶点间的可行直线连线（不穿过障碍物的连线）为路径范围来搜索最短路径。C空间法的优点是直观，容易求得最短路径；缺点是一旦起始点和目标点发生改变，就要重新构造可视图，缺乏灵活性。即其局部路径规划能力差，适用于全局路径规划和连续域范围内的路径规划。尤其适用于全局路径规划中的环境建模。

（2）自由空间法针对可视图法应变性差的缺陷，采用预先定义的基本形状（如广义锥形，凸多边形等）构造自由空间，并将自由空间表示为连通图，然后通过对图的搜索来进行路径规划。由于起始点和终点改变时，只相当于它们在己构造的自由空间中位置变化，只需重新定位，而不需要整个图的重绘。缺点是障碍物多时将加大算法的复杂度，算法实现困难。

（3）栅格（grid）法，即用编码的栅格来表示地图，把包含障碍物的栅格标记为障碍栅格，反之则为自由栅格，以此为基础作路径搜索。栅格法一般作为路径规划的环境建模技术来用，作为路径规划的方法它很难解决复杂环境信息的问题，一般需要与其他智能算法相结合。

（4） voronoi图是关于空间邻近关系的一种基础数据结构。它是用一些被称为元素的基本图形来划分空间，以每两点间的中垂线来确定元素的边，最终把整个空间划分成结构紧凑的voronoi图，而后运用算法对多边形的边所构成的路径网进行最优搜索。优点是把障碍物包围在元素中，能实现有效避障，缺点图的重绘比较费时，因而不适用于大型动态环境。

智能仿生学算法处理复杂动态环境信息情况下的路径规划问题时，来自于自然界的启示往往能起到很好的作用。智能仿生学算法就是人们通过仿生学研究，发现的算法，常用到的有:蚁群算法、神经网络算法、粒子群算法、遗传算法等。

（1）蚁群算法，（Ant Colony Algorithm简称ACA）的思想来自于对蚁群觅食行为的探索，每个蚂蚁觅食时都会在走过的道路上留下一定浓度的信息素，相同时间内最短的路径上由于蚂蚁遍历的次数多而信息素浓度高，加上后来的蚂蚁在选择路径时会以信息素浓度为依据，起到正反馈作用，因此信息素浓度高的最短路径很快就会被发现。算法通过迭代来模拟蚁群觅食的行为达到目的。具有良好的全局优化能力、本质上的并行性、易于用计算机实现等优点，但计算量大、易陷入局部最优解，不过可通过加入精英蚁等方法改进。

（2）神经网络算法是人工智能领域中的一种非常优秀的算法，它主要模拟动物神经网络行为，进行分布式并行信息处理。但它在路径规划中的应用却并不成功，因为路径规划中复杂多变的环境很难用数学公式进行描述，如果用神经网络去预测学习样本分布空间以外的点，其效果必然是非常差。尽管神经网络具有优秀的学习能力，但是泛化能力差是其致命缺点。但因其学习能力强鲁棒性好，它与其他算法的结合应用己经成为路径规划领域研究的热点。

（3）遗传算法（Genetic Algorithms，简称CA）是当代人工智能科学的一个重要研究分支，是一种模拟达尔文遗传选择和自然淘汰的生物进化过程中的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是按照基因遗传学原理而实现的一种迭代过程的搜索算法。最大的优点是易于与其他算法相结合，并充分发挥自身迭代的优势，缺点是运算效率不高，不如蚁群算法有先天优势，但其改进算法也是目前研究的热点。

路径规划应用路径规划的应用领域非常广泛，如：机器人机械臂的路径规划、飞行器航迹规划、巡航导弹路径规划、旅行商问题（PSP）以及其衍生的各种车辆（VRP）路径规划、虚拟装配路径规划、基于道路网的路径规划、电子地图GPS导航路径搜索与规划、路由问题等。

离散域范围内的最短路径规划问题属于离散域范围内最短路径规划的问题有：基于道路网的路径规划问题、电子地图CPS导航路径搜索规划问题、路由问题等。

（1）基于道路网和基于电子地图GPS导航的路径规划都可视作基于GIS (Geographical Information System)的路径规划问题。这些问题的解决都是从复杂的数据信息中提取出所需道路信息，以路口为节点，道路信息为路径信息，构造出复杂的路径信息拓扑网络，将起始点和目标点定位为这个拓扑网络上两个节点，而后运用路径搜索算法进行最短路径寻优规划。

（2）路由问题属于通信技术领域研究的重点。路由问题的主要功能是使数据信息顺利地从源节点传送到目标节点。根据Qos的设计需求，可在路径上设置不同的权重，定义路径参数。在网络拓扑结构中稳定高效地搜寻最优路径，快速聚合。实时地进行网络拥堵控制，根据具体情况进行动态路由选择。

（3）从最短路径规划的角度看，这一类问题的特点大同小异，都是在己知路径信息(节点数，路径参数信息，拓扑结构等)情况下，从己知起始节点到目标节点的最优路径路径规划问题，路径信息多为静态信息，即使有信息变动，智能算法也有足够的能力进行及时的应变规划。常用的算法有：Dijkstra算法、A*搜索算法、模拟退火算法、蚁群算法、遗传算法、粒子群算法、Floyd算法、Fallback算法等。

离散域范围内的遍历式最优路径问题属于离散域范围内遍历式最优路径的问题有：虚拟装配路径规划、旅行商问题(TSP)以及其衍生的各种车辆问题(VRP)和物流问题等。由于虚拟装配路径规划的核心是装配序列规划问题，而序列规划问题属于典型的TSP问题。

这类问题的一般特点是:己知路径信息为静态信息，对于单车辆问题，起始点唯一，最终目标节点为起始点，中间有多个子目标节点。要求车辆以最短的路径从起始点出发，遍历所有子目标节点后，回到起始点。当然，有的问题是以最短时间或最少费用等为规划目标，这样的路径规划问题可把相应路径信息调整为路径时间信息或路径费用信息，对应节点不变。此外，也有多车辆、多起点、考虑载重等因素的整体调控问题，此类问题是基于单车辆路径规划问题的延展应用。

解决此类路径问题的常用智能算法有：蚁群算法、禁忌搜索算法、模拟退火算法、神经网络算法、遗传算法、粒子群算法等。

连续域范围内的全局路径规划问题属于连续域范围内全局路径规划图的问题有:机器人机械臂自主移动路径规划、无人机飞行器航迹规划、巡航导弹航迹规划等。从路径规划角度来看，这类问题都是己知环境信息，且环境信息为静态信息的情况下，如何在安全范围内避开障碍物找到到达目的地的最短路径问题。

解决此类问题通常依靠智能算法与环境建模结合使用。直接应用于此类问题的路径规划算法有：可视图法、自由空间法、Voronoi图法、栅格法、惩罚函数法、模拟退火算法等。间接应用的智能算法有：A*搜索算法、蚁群算法、遗传算法、粒子群算法、人工势场法等。

连续域范围内的局部路径规划问题连续域范围内的局部路径规划和全局路径规划应用领域基本相同，它们在其应用领域内而对的环境不同，解决的问题也不同。局部规划而对的是动态的实时的环境信息，属于在线规划，对算法要求实时性好、高效、稳定，是目前研究的热点。

应用于此类问题的路径规划算法有：蚁群算法、遗传算法、粒子群算法、A*搜索算法、人工势场法、量子粒子群算法、神经网络算法等。

连续域范围内的遍历式路径规划问题连续域范围内的遍历式路径规划主要应用于：清洁机器人、草坪修剪机、扫雷机器人、搜救机器人、矿藏探测器等。其特点是：机器人需用最短的路径去覆盖所工作区域的每个角落，要求最大的覆盖率和最小的重复率。解决此类问题需先进行环境建模，最常用的方法是栅格法，后来Neumann de Carvalho R等人发明了模板模型法。

解决此类问题的常用算法有:神经网络算法、A*算法、遗传算法、粒子群算法、蚁群算法等。

路径规划的未来发展随着科学技术的不断发展，路径规划技术而对的环境将更为复杂多变。这就要求路径规划算法要具有迅速响应复杂环境变化的能力。这不是目前单个或单方而算法所能解决问题，因此在未来的路径规划技术中，除了研究发现新的路径规划算法外，还有以下几方而值得关注：4

（1）先进路径规划算法的改进。任何一种算法在实际应用过程中都要而对诸多困难，特别是自身的局限性。例如：A*算法作为一种启发式搜索算法具有鲁棒性好，快速响应的特点，但是应用于实际中还是存在弊端，对于A*算法应用于无人机航迹规划时的弊端，李季等提出了改进A*算法，解决了A*算法难以满足直飞限制并且有飞机最小转弯半径等约束的局限性这一问题。

（2）路径规划算法的有效结合（即混合算法）。任何的单一路径规划算法都不可能解决所有实际应用中的路径规划问题，特别是在而对交叉学科的新问题时，研究新算法的难度大，路径规划算法间的优势互补为解决这一问题提供了可能。对于多空间站路径规划问题，金飞虎等把蚁群算法和神经网络方法相结合解决了这一问题，并避免了单纯运用神经网络算法时出现的局部最小问题。

（3）环境建模技术和路径规划算法的结合。而对复杂的二维甚至三维连续动态环境信息时，算法所能做的是有限的，好的建模技术和优秀路径规划算法相结合将成为解决这一问题的一种方法。如栅格法和蚁群算法的结合， C空间法和Dijkstra算法的结合等。

（4）多智能体并联路径规划算法设计。随着科学技术的应用发展，多智能体并行协作己经得到应用。其中，多机器人协作和双机械臂协作中的路径冲突问题日渐为人们所关注，如何实现其无碰路径规划将成为日后研究的热点之一。