Hardware design of a fast, parallel Random Tree path planner

The Rapidly-Exploring Random Trees (RRT) method has been proved successful and efficient for solving path planning problems. Most recent work focuses on optimizing RRT itself and presents the results achieved from software. In this paper a dedicated hardware architecture for FPGA implementation of Rapidly-Exploring Random Tree (RRT) path planning is developed. The proposed architecture fully takes advantage of FPGAs´ natural parallel computing ability. The near neighbour (NN) search speed is improved by splitting the whole search space into several sub-spaces; correspondingly the tree nodes are stored in separate block RAMs and each Block RAM owns its independent traversal query module to enhance the memory throughput. Furthermore, to speed up the space exploration, each single path planning unit consists of two cooperating RRT modules which grow trees from each end of the path. One complete path planner involves several path planning units which work in a parallel master-slave mode to increase the probability of obtaining available path. Implementation in a 2D environment shows good path planning performance of the hardware design, with a 30x speed improvement compared to a PC implementation.