Optimal random sampling based path planning on FPGAs

Abstract

Random sampling based path planning algorithms have shown their high efficiency in robotics, navigation and related fields. The Rapidly-Exploring Random Trees (RRT) is the typical method and works well in a variety of applications. Due to the sub-optimal issue of original RRT, the recent algorithm, known as RRT*, significantly improves the optimality of solution by adding the “cost review” procedure. However, the original RRT experiences the bottle neck of complicated iterations and it becomes worse in RRT*. This paper presents the developed hardware architecture for RRT*, which fully exploits the parallel potential of algorithm. Unlike the sequential execution in software, the “exploration” and “review” are identified as independent processes and executed in parallel. For the complicated operation of inserting vertexes, one pipelined Kd-tree constructor is designed to fast rebuild the tree when new vertex generated. Furthermore, to speed up the near neighbors and nearest neighbor searching, the vertexes are stored in separate Kd-trees so that the search processes can be carried out concurrently in each data tree. This work explores the possible and power-efficient RRT* hardware architecture on FPGAs compared to PC implementation.