Parallel Rapidly Exploring Random Trees
Zixin Shen, Haoran Zhang
Click for our checkpoint reportcheckpoint
Click for our final reportfinal
We propose to implement a parallel version of RRT algorithm, compare its performance against the serial version and benchmark it on different number of cores.
RRT is Rapidly Exploring Random Trees algorithm typically used in motion planning in autonomous vehicles therefore it's quite important to speed up the computation time to reduce the decision time of autonomous vehicle. RRT-based algorithms are relatively easy to implement without establishing a detailed map and also they are efficient for high dimensional state space.
1. Difficult to parallelize outer iterative loop because each iteration has strong data dependency with the previous iteration because they need to update the kd-tree, insert the node.
2. Hard to parallelize both finding nearby nodes and collision detection at the same time due to the nature of the algorithm.
We will start by a serial implementation of RRT and we will use the OpenMP to accelerate the RRT and analyze the speedup of the algorithm. And also we found some implementations using Cuda or OpenMP without optimal data structure, we would like to evaluate their performance and compare our performance with theirs.
Goals and Deliverables
Our basic goal is to have a working version of the RRT algorithm, as well as the benchmark script to measure the performance, then implement a basic parallel version RRT and compare the performance differences.
Our ideal goal is to improve our parallel version RRT with better parallel strategy as well as using data structures such as k-d tree and compare the performance difference with version 1 and speedup with different number of cores.
If things go well and we still have time, we will try to mitigate our algorithm on GPU using cuda and measure performance difference. We will also try to make our k-d tree lock free and achieve even better parallelism.
We will use the multi-core CPU (the GHC machines) for our basic implementation. And we will try to benchmark it on the PSC machine as well. Then if we have time, we will try to mitigate it on the GPU.
|W1: 11/09-11/15||Implement Serial RRT and reproduce the parallelized version of RRT other paper shows|
|W2: 11/16-11/22||Devise the Parallelized RRT, analyze the performance, figure out the bottleneck|
|W3: 11/23-11/29||Improve our Parallelized RRT with k-d tree, compared with cuda version, and initial parallelized RRT version.|
|W4: 11/30-12/08||Visualize the path generation and results, finalize the final report.|