Near Optimal Kinodynamic RRT (NOK-RRT) is a new motion planning method I’ve developed. NOK-RRT is a joint kinodynamic motion planner, meaning it considers both positional restrictions (obstacles and boundaries), and dynamics in the planning at the same time. It’s based on the well-known RRT algorithm, and so is a sampling-based probabilistic planner.

In contrast to basic RRT, NOK-RRT plans in a 4D state space. Benefits of being a joint planner is decreasing the probability of failure in highly dynamic and obstacle rich environments.

This method also plans many times, and find the shortest path, in terms of path traversal time, not the positional length. Because of the dynamic limits each mobile robot has, the acceleration, deceleration, and cruising speed should be considered to compute the total traversal time. So the least traversal time, which seems to be the optimal solution, does not always correspond to the shortest path.

The multiple iterations are done on the GPU, using our GP-GPU RRT framework described here, and because of very high number of planning iterations, the output path is near optimal in terms of both failure rate and traversal time.

This method is most suitable for use on UAV planes and cruise missiles, that have many positional and dynamic restrictions.