Common motion planning algorithms


1.Configuration space search
Every point in configuration space represents a work state.
Configuration space search will find a path from initial state to the end state.
According to what the end state information obtained, the search method can be:
    (1) uninformed search:
          breadth-first-search, Dijkstra search etc
    (2)informed search:
          A star search etc

Example



Path formed by Dijkstra search

Path formed by A* search

2.Probabilistic Roadmap method
•A Monte Carlo method
•Path is shown up only when thousands of people walk through.
•The difference between path formed by PRM and by the global optimal search decreases with a growing number of samples in PRM.
•Don’t need build configuration space.
•Explore a lot of samples.

Example-Probabilistic Roadmap method

3.Rapidly exploring Random Tree
 A Monte Carlo method.
 Build tree use a initial node (usually the start node).
 When the leaf node gets close enough to the destination node, path is formed.  

derivative method:  Bidirectional Rapidly exploring Random Tree
     build two trees from start node and destination node. 
    when two leaf nodes from two trees respectively get close enough, a path is formed. 

4.Artificial Potential Field method

Combine two potential field and lead a way through start position to the end.
Change the problem into optimization problem.