Continuous space

You might already be familiar with path finding algorithms such as Dijkstra's algorithm or A*, these only work in discrete spaces like grids or graphs, but in a lot of robotics use-cases you would like to move in a continuous space.
RRT is an algorithm that builds a tree that converts the continuous space approximately into a discrete problem, each node in the tree will be an approximation of the shortest route to the root node, the process is iterative and becomes more accurate the more nodes are added.
RRT* is RRT with a heuristic that improves previous nodes when new ones are added, this results in much smoother paths.

How it works

We could try to explain how RRT* works in this wiki page, but we could never do it better than this video from MATLAB (it's not MATLAB specific):

Demo implementation

Path planning algorithms need a model of the environment, in the future we would like to use SLAM to build this model, but for now this demo expects this to be given, specifically a mask of what space is obstacle and what is drivable, aka an occupancy grid. This can be painted in.
You can find the demo-code here.

The green circle is the goal, the red tank is the robot. you can see the path being made pretty fast and then refined to be shorter/smoother. Becuase the tree is built from the goal and maps the whole space, we can move the robot without needing to change the tree, effectively we have a short path from any point in the space to the goal.

In this gif we moved the robot manually with the cursor but the real robot can also follow this, all the sensor data is collected to update the virtual model. One of the problems is that the physical robot's location drifts over time, we want to solve this by using SLAM.

Sources

Douglas, B. (2020). Autonomous navigation. YouTube. Retrieved November 12, 2021, from https://www.youtube.com/playlist?list=PLn8PRpmsu08rLRGrnF-S6TyGrmcA2X7kg.

Related Issues

Issues: #69