移动机器人路径规划

移动机器人路径规划概述 与人工势场法 整理人：李帅 中国科学院合肥智能机械研究所 仿生感知实验室 overview 1.什么是路径规划 2.路径规划的常用方法 3.人工势场法 1.1 定义 -how should I go there？ 依据某种最优准则，在工作空间中寻找一条从起始状 态到目标状态的避开障碍物的最优路径。 需要解决的问题： 1. 始于初始点止于目标点。 2. 避障。 3. 尽可能优化的路径。 1 .什么是路径规划 2 . 机器人路径规划常用方法 2.4 人工势场法 2.1 基于几何构造的方法 2.2 栅格法 2.3 智能化路径规划方法 2.1基于几何构造的方法 （自由空间法） 基本步骤： 1.将机器人抽象为点，适当扩大障碍物的 大小。 2.构造自由空间。 3.采用图搜索算法如 Dijkstra算法寻找最 优路径。 2.11基于几何构造的常用算法 可视图法 Voronoi法 2.2栅格法（ 1） 图中灰 色区 域为障碍物 2.2栅格法（ 2） 图中黄 色的路 线表示 该算法 得到的 最优路 径 2.2D*（ dynamic A*)算法（ 3） 美国火星探测器核 心的寻路算法就是 采用的 D*算法 适合于动态路径规 划 D*算法的思 路可以推广 到改造自由 空间法使其 具有动态规 划功能 2.3智能化路径规划方法 基于逻辑推理的路径规划方法 基于模糊逻辑的路径规划方法 基于强化学习的路径规划方法 基于遗传算法的路径规划方法 基于神经网络的路径规划方法 2.31基于逻辑推理的路径规划方法 1.定义一个状态（ state）集， 该集合反映机器人通过传感 器测得的当前状态。 2.定义一个行为（ action）集， 该集合反映了机器人当前可 以采取的动作。 3.确定从状态到行为的映射关 系。 2.32基于模糊逻辑的路径规划方法 在基于逻辑推理的路径规划方法基础进 行改进： 传感器的一次测量值与多个状态对应，每个 状态有一个隶属度对应。 根据模糊推理结果确定行为。 2.33基于强化学习的路径规划 在基于逻辑推理的路径规划方法基础进 行改进： 具有在线学习功能（通过 Q学习算法实现） 2.34基于遗传算法的路径规划（ 1） 建模： 对 2维路径规划问题，将待规划的路径看 成是 n个点组成的点集，除初始点和目标点外 其余 n-2个点 （ xi， yi ） i=2,3,4n -1都未 知，共有 2(n-2)个未知参数 。 2.34基于遗传算法的路径规划（ 2） 11 2 2 2 2 , 2 , 3, 3, 1 , 1 1 1 22 m in ( . . . ) ( ) ( ) nn l n n i i i i i ii E f x y x y x y L x x y y 优化目标： 约束： （ xi， yi ）必须在障碍物外部。 采用惩罚函数法转化为 无约束优化问题 进行处理： m i n lcE E w E (EC为惩罚项） 2.34基于遗传算法的路径规划（ 3） 遗传算法具有全局寻优性能，对上述无 约束优化问题可以得到全局最优解。 当然，其他的优化算法同样可以用于路 径规划。 2.35基于神经网络的路径规划 1.按照 2.34的方法，转化为优 化问题。 2.用神经网络表示惩罚函数。 3根据 E递减推导出相应的反 向传播算法用于神经网络的训 练 . 优势： 神经元可以并行计算 2.4人工势场法基本原理 障碍物对机器人施加排斥力，目 标点对机器人施加吸引力合力形 成势场，机器人移动就像球从山 上滚下来一样 机器人在合力作用下向目标 点移动 3.人工势场法 3.1人工势场法的基本原理（ 2.4） 3.2人工势场法的实用算法 3.3人工势场法的改进算法 3.2人工势场法的实用算法 3.21非点形障碍物问题 普通的障碍物的形状不是一个点，如何 确定一个障碍物对机器人的排斥力呢？ 方案 1：计算障碍物内所有点斥力的合力。 方案 2：用离障碍物最近的点进行计算。 方案 3： 3.22死锁（ dead lock）现象（ 1） 如何克服死锁现象： 死锁现象的实质是落入局部极 值，全局优化算法可以避免落入局 部极值。 3.22死锁（ dead lock）现象（ 2） 避免死锁的改进算法： APF与随机采样相结合如 RPP算法 APF与遗传算法（ GA）相结合 APF与其他全局优化算法相结合： 如：粒群算法，蚁群算法，模拟退火法，附加 动量法等。 3.23GNRON问题： 障碍物与目标点过于接近引起斥力场和引力场 同时存在而阻碍到达目标点的现象。 解决方案： 3.24移动机器人为多面体的情况 方案 1：一般情况下，可以将机器人作为 点，适当扩大障碍物来进行研究。 方案 2：对多面体每个顶点计算排斥力和 吸引力，障碍物对机器人的排斥力是对 所有顶点排斥力的合力。 3.3人工势场法的改进算法（ 1） 主要是针对死锁问题进行改进 RPP算法 (APF与随机采样相结合） 的原理： 1.开始时执行 Descend模式 2.如果没有出现死锁则成功，否则执行 Escape模式 3.如果 Escape模式失败，执行 Backtrack模式 3.3人工势场法的改进算法（ 2） 一种 APF与 GA相结合的算法： 在基于 GA的路径规划算法（ 2.34）中介 绍了 GA如何用于路径规划，但是这种算法 存在着计算量 (n) 与路径规划的质量之间的 矛盾。采用 APF与 GA结合的算法可以取较 小的 n获得满意的效果并且避免死锁。 3.3人工势场法的改进算法（ 2） APF与 GA相结合的算法原理： 1.选取初始可行种群，每个种群中具有 n-2个参数 （ xi， yi ） （ 2.34）。 2. 每一个种群中 ,在相邻两个点（ xi， yi ）和（ xi+1， yi+1 ） 之间利用 APF得到一条连接这两个点的无碰撞路径。 对于一个种群来说，就可以得到从起始点到目标点的 无碰撞路径。 3.计算每个种群对应的路径的长度作为适配度，对 （ xi， yi ） 进行交叉、变异、选择运算得到新的 n-2个参数。 4.重复上述步骤直至结束。 3.3人工势场法的改进算法（ 2） 交叉前： 交叉后：