How to plan robot motion is a major topic in robotics development. This article summarizes an open-source GitHub library that implements commonly used path planning algorithms for robots, with animated GIFs demonstrating the processes. Most of the code is implemented in Python.
The open-source library implements both search-based and sampling-based path planning algorithms. The directory structure is shown below:
Search-based path planning algorithms
Search-based path planning algorithms are mature and widely used, often for character navigation in games and for mobile robot path planning.
Best-first search algorithm
Dijkstra algorithm
A* search algorithm
Bidirectional A* search algorithm
Repeated A* search algorithm
Anytime Repairing A* (ARA*) algorithm
Learning Real-Time A* (LRTA*) algorithm
Real-Time Adaptive A* (RTAA*) algorithm
Dynamic A* (D*) algorithm
Lifelong Planning A* algorithm
Anytime D* search algorithm: small changes
Anytime D* search algorithm: large changes
Sampling-based path planning algorithms
Unlike search-based methods, sampling-based path planning algorithms do not require explicit construction of the entire configuration space and are widely used for planning in high-dimensional problems.
Rapidly-exploring Random Tree (RRT) algorithm
Goal-biased RRT algorithm
Bidirectional RRT (RRT-Connect) algorithm
Extended RRT algorithm
Dynamic RRT algorithm
RRT* algorithm with N = 10000
RRT*-Smart algorithm with N = 1000
Fast Marching Tree (FMT*) algorithm
Informed RRT* algorithm with N = 1000
Batch Informed Tree (BIT*) algorithm
