01_search_based

planning algorithms

combinatorial planning
- cell decomposition
sampling-based planning
- BFS: breadth first search, visit all nodes but not give the path
- DFS: depth first search, visit all nodes but not give the path
- Dijkstra's algorithm: adding cost(start,current)
- greedy best first search: one closest to the goal will be explored first
- A*: adding obstacle cost and distance cost together
- ant colony algorithm(蚁群算法)
- PRM(probability road maps)
differential constraints

'''
这一类算法途中保留了三种点：
- 已访问的点 (closed)
- 边界点，已加入待访问队列 (open)
- 未访问
'''
# Dijkstra: 以障碍代价构造优先队列，优先访问代价较少的
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
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*： 增加当前到目标点的诱导方向
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
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 + heuristic(goal, next)
         frontier.put(next, priority)
         came_from[next] = current

运动规划

Principles of Robot Motion Theory, Algorithms, and Implementations
Planning Algorithms

基础的运动学和动力学

Introduction to Robotics Mechanics and Control 3rd edition
Robotics_ Modelling, Planning and Control-Springer-Verlag London (2009)
Springer Handbook of Robotics-2nd

research

01_search_based_planner