Technical Details
The Algorithm
The algorithm is a basic RRT (Rapidly Expanding Random Tree) algorithm. It is a single
sided search in that it only expands from the start node outward towards the goal.
An RRT is given a start state, a configuration space, and a desired goal state. For a set
number of iterations, the algorithm generates a random state (random joint angles), finds
the closest node currently in the tree to that random state, then does a small interpolation
towards that random state. The new small interpolation is then added into the tree and connected
to the chosen closest node it spawned from. If the small interpolation runs into an obstacle,
violates constraints of the robot, or attempts to leave the constraints of the playpen, it is
considered invalid and a new random state is chosen to try again.
If a state gets within a specified tolerance of the goal state, then a path has been found via
the states of the tree from the goal back to the initial start state.
Example
Here is an example of the path found by the planner from a start state to and end state.
START END
A video of this interpolation can be found here.