第6章 规划与导航#

避障不考，仅整理路径规划算法部分

---

6.1 什么是机器人导航？#

机器人通过先验知识及传感器感知所得环境及自身状态信息，通过长期规划（路径规划）和即时反应（避障），实现在有障碍物环境中到达目标位置的自主运动。

导航三问题 (3W)#

1. 我在何处？ → 定位
2. 要到何处去？ → 目标设定
3. 如何到达该处？ → 路径规划

---

6.2 路径规划 vs 避障#

两者相互辅助，缺一不可。

---

6.3 导航分类#

按环境信息可知性#

按传感器类型#

---

6.4 配置空间 (C-Space)#

概念#

• 物理空间 → 配置空间
• 机器人简化为点
• 障碍物按机器人尺寸膨胀补偿

离散地图构建#

三种离散化方式：

---

6.5 四种路径规划算法 ⭐核心#

算法总览#

前三者都是将问题转化为图的最短路径搜索。

---

(1) 可视图法 (Visibility Graph)#

核心思想:

• 节点: 起点、目标、所有障碍物顶点
• 边: 节点间不穿越障碍物的直线连线
• 路径: 在图上搜索最短路径

特点:

• 找到的是最短路径
• 路径贴近障碍物（危险！）
• 属于道路图方法

---

(2) Voronoi 图法#

核心思想:

• 以障碍物点为中心生成 Voronoi 图
• 沿 Voronoi 边产生路径
• 搜索选择最优路径

什么是 Voronoi 图？

• 将平面按距离最近原则分割为 Voronoi 单元
• Voronoi 边: 到两侧障碍物距离相等的点
• Voronoi 节点: 边的交点

特点:

• 路径距离障碍物最远（最安全！）
• 最大化机器人与障碍物的间隙
• 不追求最短路径

构建方法:

• 垂直等分法
• 分而治之 (divide and conquer)
• Fortune 法

---

(3) 单元格分解 (Cell Decomposition)#

核心思想:

• 将自由空间分解为若干单元格
• 单元格间建立邻接关系
• 在连通图中搜索从起点单元格到目标单元格的路径

类型:

---

(4) 势场法 (Potential Field)#

核心思想:

• 机器人看作人工势场中的点
• 运动类似于球向山下滚动

两种场:

合成势场:

$$U(q) = U_{\text{att}}(q) + U_{\text{rep}}(q)$$

势场力:

$$F(q) = -\nabla U(q)$$

机器人速度正比于势场力: $(v_x, v_y) \propto F(q)$

⚠️ 局部极小值问题#

问题描述: 机器人在非目标位置陷入势场极小值，无法继续运动。

解决方法:

1. 结合高层决策引导
2. 允许进入局部极小值，用其他策略跳出:
   • 随机运动
   • 跟墙或环绕等特殊运动
   • 改变障碍物势场

扩展势场法#

在基本势场上附加两个场:

• 转动势场: 力也是机器人相对于障碍物方向的函数
• 任务势场: 滤除不可能影响机器人的障碍物（仅考虑前方扇区）

---

6.6 算法对比总结 ⭐#

小结#

可视图 / Voronoi 图 / 单元格分解 → 图 (Graph): 节点与边 → 最短路径搜索问题

---

考前速记#