dijkstra算法_移动机器人常见路径规划算法学习笔记

路径规划目的：寻找一条路径，使机器人从起点到目标点逐渐移动，同时不碰到任何障碍物。

分类：

1. 组合规划（Combinatorial Planning）

1.1 Visibility graphs

1.2 Voronoi diagrams

1.3 Exact cell decomposition

1.4 Approximate cell decomposition

2. 基于采样的规划（Sampling-Based Planning）

2.1 Probabilistic road maps (PRM)

2.2 Rapidly exploring random trees (RRT)

3. 图搜索（Graph search）

3.1 Dijkstra’s Algorithm

3.2 A* Search

3.3 Potential Field algorithm

RRT

RRT（快速扩展随机树）。RRT使用搜索空间中的随机采样构造一棵树。随机生成点连接到最近的可连接节点。每次创建顶点时，都必须检查顶点是否位于障碍物之外。此外，将顶点链接到其最近的邻近节点也必须避免障碍。当在目标区域内生成节点或达到限制时，该算法结束。

RRT*

RRT*在继承了RRT所有的特性上，增加了两个新特性。

1. ChooseParent
2. Rewire

Dijkstra's Algorithm

迪杰斯特拉（Dijkstra）算法通过建立一组距源节点最短距离的节点，从单个源节点中找到最短路径树。

Dijkstra算法由荷兰计算机科学家Edsger Dijkstra于1959年发布。该图可以是有向的或无向的。使用该算法的一项规定是，图的每个边都需要具有非负权重。

优点：路径最短

缺点：遍历所有节点，时间复杂度（

）

// Dijkstra Algorithm
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0
 
while not frontier.empty():
   current = frontier.get()
 
   if current == goal:
      break
   
   for next in graph.neighbors(current):
      new_cost = cost_so_far[current] + graph.cost(current, next)
      if next not in cost_so_far or new_cost < cost_so_far[next]:
         cost_so_far[next] = new_cost
         priority = new_cost
         frontier.put(next, priority)
         came_from[next] = current

A* Search Algorithm

为了解决Dijkstra算法的搜索效率问题，1968年，A算法由Stanford研究院的Peter Hart, Nils Nilsson以及Bertram Raphael发表，其主要改进是借助一个启发函数来引导搜索的过程。

公式：

其中

是节点n从初始点到目标点的估价函数，

是在状态空间中从初始节点到节点n的cost，

是从节点n到目标节点的cost(Manhattan, Diagonal, Euclidean)。

优点：与Dijkstra相比提高了搜索效率。

// 

参考：

A Comparison of RRT, RRT* and RRT*-Smart Path Planning Algorithms.

https://medium.com/@theclassytim/robotic-path-planning-rrt-and-rrt-212319121378

https://www.redblobgames.com/pathfinding/a-star/introduction.html