【路径规划】第一周： 大杂烩

传统的路径规划方法多是根据环境模型的描述形式，采取相对简单的类似于几何数学模型的算法（如几何法、启发式算法）完成机器人路径的搜索。

可视图法

可视图法分别将机器人和障碍物假设为一质点和近似多边形，用可视的线段将质点、目标点及多边形的各顶点进行有序的组合连接，即连线不能穿越障碍物多边形，将机器人路径规划问题转换为搜索起始点到目标点之间最短线段集合，常采用 A算法或其改进算法搜索最短路径。由于搜索的路径是连接障碍物顶点的线段，机器人易与障碍物发生碰撞，当环境障碍物、特征信息量较多时，搜索路径的时间较长；同时可视图法灵活性较差，对环境的适应性及实时性较差，不能保证所寻的路径是全局最优。
切线图法是可视图法的改进方法，用障碍物的切线表示弧，降低了机器人与障碍物碰撞的几率，缺点是当机器人控制误差较大时，同样易与障碍物发生碰撞；在误差允许的情况下，采用切线法规划路径常选择远离障碍物的路径表示弧。可视图法多与启发式搜索算法结合来完成机器人路径规划，如 A、Dijkstra 等。

栅格法

栅格法是用不同性质及不同序号的两类栅格描述机器人工作环境，即自由栅格和障碍栅格，自由栅格区域内不含障碍物，障碍栅格区域内包含障碍物。机器人路径规划问题就转换为搜索工作空间内可行栅格的有序集合。该方法以栅格为基本单位记录机器人所在环境信息，栅格尺度越大，特征地图的描述越粗糙，规划的路径质量越差，误差也越大；栅格尺度越小，环境障碍物描述的越精确，规划的路径质量越好，但此是以大量的存储空间及搜索算法的复杂度为代价，因此，应根据具体的应用环境，选择合适的栅格尺度及相应的优化搜索栅格有序集合的算法。栅格地图既可以描述真实环境的很多特征，又可以实现时间和空间消耗最优，因此，栅格地图是当前广泛采用的环境地图的描述方法。

人工虚拟势场法

工虚拟势场法是一种有效的局部路径规划方法[9]。其主要思想是将机器人工作的环境描述为虚拟的势场，目标点为机器人的引力源，而障碍物为机器人的斥力源，在两力的合力作用下，机器人实时有效地规避障碍物并沿着无碰撞路径向目标点移动。人工虚拟势场法因其数学原理简单、实时性高及生成路径平滑等优点在机器人局部路径规划中有着广泛的应用，但该方法存在固有的缺陷：其一，由于其规划的路径是依据有限的局部环境信息，缺乏全局环境上宏观自我调节能力，极易陷入局部最优；其二，由于力的不平衡是机器人移动的主要因素，其极易在非目标点处达到力平衡，从而产生目标不可达现象；其三，在障碍物之间的狭窄空间里，极易陷入徘徊抖动等不稳定状态。

机器人智能避障路径规划方法

随着环境特征信息的增加及所需完成任务难度的增加，基于传统的简单几何数学模型的机器人路径规划方法难以取得较为理想的效果，研究者根据自然界一些生物的习性，将其本能应用到机器人路径规划中，提出了仿生智能优化算法，该类算法是采用群体行为在复杂解空间中寻找全局最优解，其具有随机、并行和分布式的特点。由于这些仿生优化算法具有跨学科领域的寻优策略和避免陷入局部最优的潜在能力，其在路径规划领域取得了较好的效果，比较有代表性的有遗传算法和蚁群算法。

遗传算法

遗传算法是美国 Michigan 大学的Holland JH教授于20世纪60 年代末提出，其用选择、复制、交叉和变异等操作，模拟自然界生物遗传及进化过程而提出的一种自适应全局优化概率搜索算法。遗传算法是一种迭代算法，由于其具有较好的全局寻优能力和并行计算特性，是目前机器人路径规划研究中应用较成熟的一种方法。其将初始集经过选择、复制、交叉和变异等操作不断迭代计算获得新的解集，并依据个体的适应度，遵循自然界“适者生存”和“优胜劣汰”的原则，引导生物搜索过程向“最适应环境”的个体（最优路径）逼近，并最终收敛到最优解（最优路径）或次优解（近似最优路径）。

由于自然界的生物进化是一个多种群漫长进化过程，模拟此过程的遗传算法需要大规模的种群及大的搜索空间，易早熟及收敛速度慢是遗传算法在进行机器人路径规划时存在两大问题，前者会产生局部最优，后者会降低算法的实时性，影响其搜索路径效率。为此，大量的研究工作对其进行了改善

蚁群算法

蚁群算法是生物学家经过对自然界中蚂蚁觅食过程的长期细致观察，发现该生物群中个体通过一种信息媒介协作完成寻找蚁巢到食物源最短路径的任务。在蚂蚁寻找食物的运动过程中，蚂蚁个体会在所经过的路径上留下随时间而挥发的信息素，且能感知前代蚂蚁所留的信息素及其强度，并依据信息素浓度高低指导自己的觅食方向，遗留在路径上的信息素也成为蚂蚁个体之间信息交流的“媒介”。由于相等时间内，选择信息素浓度较高的短路径的蚂蚁个体数量较多，其遗留在较短路径的信息素浓度也会随之增强，根据蚂蚁这种依据“信息素交流机制”来觅食的群体行为，本质是一个群体从无序到有序的动态优化过程，其隐含的并行处理性能使其应用领域不断扩大。蚁群算法是一种随机搜索寻优方法，其在寻优过程中，要逐渐遗忘历史信息，不断探索新的路径信息，即信息素挥发机制，其赋予了蚁群的创新和探索未知空间的潜在能力。

根据自然生物习性衍生的蚁群算法，采用模拟自然界真实蚂蚁生物习性的随机概率选择和信息素的挥发机制及正反馈机制，其有局限性，即随机性易导致算法收敛速度慢，正反馈及挥发机制易使算法陷入局部最优，其需要解决的关键问题是在“探索”和“利用”之间寻找一个平衡点，既要使蚁群算法搜索空间尽可能大（即随机性大，复杂度高），以便其能够在“觅食”过程中寻找到全局最优路径，又要利用先验知识（即距离信息、启发信息和信息素），使系统以较大的概率较快地收敛到全局最优，其本质是解决蚁群算法全局搜索能力与收敛到全局最优速度的矛盾，即随机性和信息素更新强度的矛盾。为此，不少研究者对相关问题进行大量的深入研究，寻求降低其复杂度及深度的改进优化算法。

影响蚁群算法性能的主要因素是信息素更新机制和路径搜索策略，因此，国内外研究者主要从参数优化、信息素更新机制和路径搜索策略等方面改进。

除此以外，研究者提出了其它很多智能优化算法，诸如模糊控制，人工蜂群、神经网络、蛙跳算法、免疫算法、帝国竞争算
法、萤火虫算法、鱼群算法等等。

---

什么是路径规划？

室内路径规划

• 路径规划指的是根据用户的起始位置、终点位置和室内地图为用户规划出一条行走距离最短的可通达路线。

机器人路径规划：

• 移动机器人路径规划的目标是通过环境感知与主动避障功能找到一条可行的最佳路径，此路径从起始点至终点在给定的工作空间中不与任何障碍物相交，同时要优化机器人运动路径，使其尽可能达到更短、更平滑的要求。

路径规划步骤：

• （1）建立包含有障碍物的区域和自由移动区域的环境地图模型；
• （2）在建立的环境地图模型基础上选择合适的路径搜索算法，以便实现快速、实时的路径规划。路径轨迹的产生过程如下图所示。