路径规划

Path Planning
在数学上通常可以被建模为图论问题、优化问题或几何问题。

路径规划是机器人学中的一个基础问题，旨在为机器人在给定环境中寻找一条从起始点到目标点的无碰撞路径。它主要关注的是几何路径，而不考虑时间、速度、加速度、动力学等因素。路径规划是运动规划的前置步骤。

核心思想：在地图中寻找可行路线

路径规划的核心任务是在一个已知或未知（需要同时构建地图）的环境中，找到一条从A点到B点的可行路线，同时避开所有障碍物。这通常涉及到对环境的建模和对搜索算法的应用。

环境表示

在进行路径规划之前，需要将机器人所处的环境进行建模：

1. 栅格地图 (Grid Map):

   • 原理: 将环境离散化为一系列规则的网格单元。每个单元格被标记为“可通过”或“障碍物”。
   • 优点: 简单直观，易于实现，适用于基于搜索的算法。
   • 缺点: 空间分辨率受限，存储量大，对复杂环境的表示不够精细。

2. 拓扑地图 (Topological Map):

   • 原理: 将环境抽象为节点和边构成的图。节点代表环境中的关键位置（如房间、走廊交叉口），边代表这些位置之间的连接关系。
   • 优点: 抽象程度高，存储量小，适用于高层次的全局规划。
   • 缺点: 丢失了精确的几何信息，不适合局部精细导航。

常见路径规划算法

1. 基于搜索的方法 (Search-based Methods)

这类方法在离散化的环境中进行系统搜索，通常能找到最优路径（如果存在）。

• Dijkstra算法

  • 原理: 一种单源最短路径算法，从起始点开始，逐步向外扩展，找到到所有可达点的最短路径。它保证找到最短路径。
  • 优缺点:
    • 优点: 保证找到最短路径。
    • 缺点: 搜索范围广，效率较低，不适用于大规模环境。

• BFS (Breadth-First Search)

  • 原理: 从起始点开始，逐层向外搜索，优先访问距离起始点近的节点。对于无权图，它能找到最短路径。
  • 优缺点:
    • 优点: 简单，对于无权图能找到最短路径。
    • 缺点: 搜索范围广，内存消耗大。

• DFS (Depth-First Search)

  • 原理: 从起始点开始，沿着一条路径尽可能深地搜索，直到达到终点或死胡同，然后回溯。
  • 优缺点:
    • 优点: 内存消耗小。
    • 缺点: 不保证找到最短路径，可能陷入无限循环。

• A 算法*

  • 原理: 一种启发式搜索算法，结合了Dijkstra算法的完备性和贪婪最佳优先搜索的效率。它通过一个启发式函数 (Heuristic Function) 来估计从当前点到目标点的代价，从而优先探索最有希望的路径。
  • 公式: $f(n)=g(n)+h(n)$
    • $f(n)$: 从起始点经过节点 $n$ 到目标点的估计总代价。
    • $g(n)$: 从起始点到节点 $n$ 的实际代价。
    • $h(n)$: 从节点 $n$ 到目标点的估计代价（启发式函数）。
  • 优缺点:
    • 优点: 效率高，能够找到最优路径（如果启发式函数是可接受的）。
    • 缺点: 启发式函数的设计影响性能；计算成本随维度呈指数增长。

2. 基于采样的方法 (Sampling-based Methods)

这类方法通过在C-space中随机采样点来构建一个图或树，然后在这个图/树上搜索路径。它们适用于高维空间和复杂障碍物环境。

• PRM (Probabilistic Roadmaps)

  • 原理: 在C-space中随机采样大量点，并尝试连接这些点（如果连接路径无碰撞）。最终形成一个“路线图”，然后在这个图上使用图搜索算法（如A*）寻找路径。
  • 优缺点:
    • 优点: 适用于高维空间和复杂障碍物环境；能够找到最优路径（如果采样足够密集）。
    • 缺点: 需要预先构建路线图；不保证找到路径（概率完备性）。

• RRT (Rapidly-exploring Random Trees)

  • 原理: 从起始点开始，以随机的方式快速“生长”一棵树，直到树的某个分支到达目标区域。每次生长时，从树中选择一个节点，向随机采样的点方向扩展一小步。
  • 优缺点:
    • 优点: 适用于高维空间和复杂障碍物环境；能够快速找到一条可行路径（概率完备性）。
    • 缺点: 找到的路径通常不是最优的；需要后处理来平滑路径。