PI-RRT# (CUDA)

A standalone, parallelised implementation of PI-RRT#, the policy-iteration variant of RRT#, written directly in CUDA rather than against OMPL. The search runs backwards from the goal vertex towards the start, samples uniformly with rejection plus local and goal bias, exploits cuboid obstacle geometry for collision detection, and uses FLANN radius search for nearest neighbours.

After each batch of samples two replanning modules run. Policy improvement iterates over the list of promising vertices, looking among each vertex’s neighbours for a better parent with lower cost-to-come; this is the parallelised part, implemented as three CUDA kernels, one each for finding a better parent, adding a new child and deleting the old one. Policy evaluation then propagates edge costs from the goal to compute the value of the start vertex, which in turn generates the next list of promising vertices.

Profiling the earlier work showed that invoking a CUDA kernel every iteration is dominated by host-to-device transfer, so the kernel is called at intervals instead, solving a larger dynamic programming problem less often.

Reference

O. Arslan and P. Tsiotras, “Incremental Sampling-based Motion Planners using Policy Iteration Methods,” 55th IEEE Conference on Decision and Control, 2016.

Requires CUDA and FLANN. See the Incremental Sampling-Based Algorithms and Stochastic Optimal Control on Random Graphs project page for the wider context.

Visit the GitHub repository for the source code.