根据对环境信息掌握的程度将其分为2种 ：基于环境先验完全信息的全局路径规划，又称静态或离线规划；基于传感器信息的局部路径规划，又称动态或在线路径规划。

 

人工势场法是Khatib提出的一种虚拟力法。其基本思想是将移动机器人在环境中的运动视为一种虚拟人工受力场中的运动。障碍物对移动机器人产生斥力，目标点产生引力，引力和斥力周围由一定的算法产生相应的势，机器人在势场中受到抽象力作用，抽象力使得机器人绕过障碍物。该法结构简单，便于低层的实时控制，在实时避障和平滑的轨迹控制方面，得到了广泛应用，其不足在于存在局部最优解，容易产生死锁现象，因而可能使移动机器人在到达目标点之前就停留在局部最优点。

主要的缺陷：

1)陷阱区域

2)在相近的障碍物之间不能发现路径。

3)在障碍物前振荡。

4)在狭窄通道中摆动。

针对这些缺陷，提出了一些改进办法。针对人工势场法存在“机器人在到达目标位置前由于陷入局部极小点而无法到达目标位置”的问题，解决的方法有：重新定义势函数，使之没有或有更少的局部极小点；利用搜索算法跳出局部极小点。还可以利用模拟退火算法使势函数跳出局部极小点，到达机器人的目标位置。

 

模糊逻辑算法基于对驾驶员的工作过程观察研究得出。驾驶员避碰动作并非对环境信息精确计算完成的，而是根据模糊的环境信息，通过查表得到规划出的信息，完成局部路径规划。优点是克服了势场法易产生的局部极小问题，对处理未知环境下的规划问题显示出很大优越性，对于解决用通常的定量方法来说是很复杂的问题或当外界只能提供定性近似的、不确定信息数据时非常有效。假设检测的是障碍物与机器人的距离和障碍物的运动信息，输出机器人速度变化和转角变化。

 模糊控制算法有诸多优点，但也有固有缺陷：人的经验不一定完备；输入量增多时，推理规则或模糊表会急剧膨胀。由于模糊隶属度函数的设计、模糊控制规则的制定主要靠人的经验和试凑，总结模糊控制规则时比较困难，而且，控制规则一旦确定，在线调整困难，无法很好地适应情况的变化。因此，如何得到最优的隶属度函数、控制规则以及对控制规则进行在线调整是该方法最大的问题。

模拟退火算法由Kirkpatrick S于1983年提出，源于物理退火过程。基本思想是利用随机优化问题求解过程与统计力学中热平衡问题的相似性，通过设定初温、初态和降温率控制温度的不断下降，结合概率突跳特性，利用解空间的邻域结构进行随机搜索。模拟退火算法用于路径规划可避免局部极值，但其理论收敛条件过于苛刻，在实际应用中往往无法满足。在有限计算量条件下的收敛性能依赖于自身参数，这使得参数设定成为算法应用过程中的一个关键环节。

路径规划是感知空间到行为空间的一种映射。映射关系可用不同方法实现，很难用精确数学方程表示，但采用神经网络易于表示。将传感器数据作为网络输入，由人给定相应场合下期望运动方向角增量作为网络输出，由多个选定位姿下的一组数据构成原始样本集，经过剔除重复或冲突样本等加工处理，得到最终样本集。将神经网络和模糊数学结合也可实现移动机器人局部路径规划。先对机器人传感器信息进行模糊处理，总结人的经验形成模糊规则。再把模糊规则作用于样本，对神经网络进行训练。通过学习典型样本，把规则融会贯通，整体体现出一定智能。实际中允许输入值偏离学习样本，只要输入接近一个学习样本的输入模式，则输出也就接近该样本输出模式。该性质使得神经网络可以模仿人脑在丢失部分信息时仍具有对事物正确的辨识力。

遗传算法以自然遗传机制和自然选择等生物进化理论为基础，构造了一类随机化搜索算法。利用选择、交叉和变异编制控制机构的计算程序，在某种程度上对生物进化过程作数学方式的模拟。只要求适应度函数为正，不要求可导或连续，同时作为并行算法，其隐并行性适用于全局搜索。多数优化算法都是单点搜索，易于陷入局部最优，而遗传算法却是一种多点搜索算法，故更有可能搜索到全局最优解。遗传算法的整体搜索策略和优化计算不依赖于梯度信息，解决了一些其它优化算法无法解决的问题。遗传算法运算速度不快，进化众多的规划要占据较大存储空间和运算时间，优点是克服了势场法的局部极小值问题，计算量不大，易做到边规划边跟踪，适用于时变未知环境的路径规划，实时性较好。遗传算法运用于移动机器人路径规划的研究近来取得了许多成果，其基本思想：将路径个体表达为路径中一系列中途点，并转换为二进制串。首先初始化路径群体，然后进行遗传操作，如选择、交叉、复制、变异。经过若干代进化以后，停止进化，输出当前最优个体，其过程如以下算法所示。

开始

随机初始化群体P(0)

计算群体P(0)中个体的适应度

t： =0

while(不满足终止准则)do

{

由P(t)通过遗传操作形成新的种群P(t+1)；

计算P(t+1)中个体的适应度，t：=t+1；

}

蚁群优化算法是由意大利学者Dorigo等人在2O世纪9O年代从蚁群觅食行为受到启发，通过模拟自然界蚂蚁寻径的行为，提出的一种全新的模拟进化算法。蚁群优化算法在并行运行环境(如网格环境)下可以同步寻优，加快了寻优速度。另外，它是一种通用性强的算法，稍加修改便可用于其他优化问题。但计算量较大，搜索时间较长，易于陷入局部最优解。

粒子群算法是由Kennedy博士和Eberhart博士于1995年从鸟类的捕食行为中受到启发提出的一种基于群体的智能随机优化算法。粒子群算法具有收敛速度快、算法简单、容易编程实现和鲁棒性强等特点，但是，粒子群算法也有一些缺陷，一是容易陷入局部极值点，导致得不到全局最优解；二是粒子群算法本身的参数设置，若参数选择不当，会导致寻优过程中粒子的多样性迅速消失，造成算法“早熟收敛”。

启发式方法的最初代表是A*算法 ，其新发展是D*和Focussed D*。这2种由Stentz A提出的增量式图搜索算法的产生。D*算法可以理解为动态的最短路径算法，而Focussed D*算法则利用A*算法的主要优点即使用启发式估价函数，2种方法都能根据机器人在移动中探测到的环境信息快速修正和规划出最优路径，减少了局部规划的时间，对于在线的实时路径规划有很好的效果。此外，还出现了一些基于A*的改进算法，它们一般都是通过修改A*算法中的估价函数和图搜索方向来实现的，可以较大地提高路径规划的速度，具有一定的复杂环境自适应能力。

基于滚动窗口的算法是基于预测控制理论的一种次优方法，其基本思想是依靠机器人实时探测到的局部信息，以滚动的方式进行在线规划。在滚动的每一步，根据探测到的局部信息，用启发式方法生成优化子目标，在当前滚动窗口内进行局部路径规划，然后，实施当前策略，随着滚动窗口的推进，不断取得新的环境信息，从而在滚动中实现优化与反馈的结合。在未知环境下，基于滚动窗口的机器人路径优化算法能够保证安全地避开障碍物，具有计算量小、反应迅速、可操作性强等特点，对动态未知环境有一定的适应性。

基于行为的路径规划最具代表性的是1986年Brooks的包容式体系结构，其基本思想是把移动机器人所要完成的任务分解成一些基本的、简单的行为单元，机器人根据行为的优先级，结合本身的任务综合做出反应。在基于行为的机器人控制系统中，不同的行为要完成不同的目标，多个行为之间往往产生冲突，因此，涉及到行为协调问题。Tyrrell等人将行为协调机制的实现方法分为两类：仲裁机制和命令融合机制。仲裁机制在同一时间允许一个行为实施控制，下一时间又转向另一个行为。它能够解决在同一时间由于多重行为而使执行器产生冲突的弊端，该方法具有行为模式简单灵活，实时性、鲁棒性强等优点。但当有多种行为模式时，系统做出正确判断的概率会降低。而命令融合机制允许多个行为都对机器人的最终控制产生作用，这种机制适用于解决典型的多行为问题。该机制在环境未知或发生变化的情况下，能够快速、准确地规划机器人路径。但当障碍物数目增加时，该方法的计算量会增大，影响规划结果。

基于再励学习的路径规划算法是一种未知环境下的实时规划方法。它来源于行为心理学，其基本思想是采用了动物学习心理的“试错法”原理，强调在与环境的交互中利用评价性反馈信号进行学习，为实现具有自学习能力的智能系统提供了有效手段。由于再励学习通过与环境的直接交互进行学习，不需要环境模型和先验知识，也不需要样本训练数据，而且，能够方便地在线实现，因此，比较适用于未知环境模型的不确定系统。

移动机器人在动态环境中进行路径规划所需的信息都是从传感器获得，单一传感器难以保证输入信息的准确性与可靠性，多传感器所获得的信息具有冗余性、互补性、实时性和低代价性，且可快速并行分析现场环境。目前的方法有：采用概率方法表示信息的加权平均法、贝叶斯估计法、多贝叶斯法、卡尔曼滤波法、统计决策理论法、仿效生物神经网络的信息处理方法、人工神经网络法等。

 

 

转载本文请联系原作者获取授权，同时请注明本文来自张红艳科学网博客。
链接地址：https://blog.sciencenet.cn/blog-281551-462161.html

上一篇：移动传感器（移动机器人）路径规划方法总结（一）
下一篇：cygwin下NS2的安装说明