VF-RRT Implementation

As the final project for a course in algorithmic robotics, a classmate and I implemented Vector Field RRT in C++ and contributed it to OMPL, an open-source project for unifying a collection of algorithms that solve a variety of motion planning problems, with both practical and educational applications.

The classic RRT algorithm finds a collision-free path via randomly sampling a state in a robot's configuration space and trying to reach it by a (typically linear) motion from the nearest state in a tree of valid, reachable states. The tree is seeded with the start state of the path. Sampling favors the goal state, and the tree grows until the goal is reached.

VF-RRT is applicable to problems in which there is some sort of vector field throughout the space of robot configurations. This field could represent anything from wind or water currents to the gradient of a potential energy function. Often we are interested in not just a correct solution, but also a cheap solution, where cheap is defined in terms of letting the field carry the robot instead of fighting it. The algorithm differs from classic RRT in that sampled points are not used as-is. The tree is not expanded directly toward the sample, but in some direction that is a linear combination of the sampled direction and the vector field direction. Then only a small step is made in this direction. This process effectively biases expansion downstream, which is the heuristic toward finding a solution cheaper than the naïve one given by RRT. As such, VF-RRT certainly does not give the best solution, but merely a good solution with little extra computation time.

Our implementation is currently in a branch of OMPL and will be merged into the release soon.