Motion / Path Planning
The Motion Planning problem is to find an optimal path for the robot to move through gradually from start to goal while avoiding any obstacles in between
- This seems pretty easy but it’s hard
There’s another image that I have in Autonomous Vehicles.
Path planning approaches are gauged by
- Completeness: Guaranteed to find a solution? (if one exists)
- Optimality: Finds the best solution (for example, shortest)
At a high level, we can divide path planning into 2 different categories: sampling-based and search-based path planning.
Thinking about path planning
The naive way is to think about path planning in terms of simple 2D grids.
But this is not always the case in the real world, where the domain is continuous, and your robot might have multiple actuators, and is non-holonomic.
Search-Based Path Planning
In search-Based planning, we divide the problem into 2 phases:
- Graph construction (trivial if you are already given a grid)
- Graph search
There are multiple ways you can construct a graph, including:
- Cellular Decomposition (most popular, where you discretize from continuous to discrete space to get a grid)
- Visibility Graph
- Voronoi Diagram
Once you have a graph constructed, you can use any of these search algorithms to do
Sampling-Based Path Planning
Sampling-Based algorithms are suitable for high-dimensional problems because the size of the graph they construct is not explicitly exponential in the number of dimensions. The con is that they are not very repeatable or provable.
Sampling based methods can be divided into two categories:
- Multi-query: multiple start and goal configurations can be connected without reconstructing the graph structure
- Single-query: the tree is built from scratch for every set of start and goal configurations
- Probabilistic Road Maps (PRM) for multi-query
- Rapidly Exploring Random Trees (RRT) for single-query
Self-Driving Cars
Many approaches in the field of path planning are based on splines.