IIIT Hyderabad Publications
FPGA based massively parallel architectures for super fast path planning via Rapidly Exploring Random Trees(RRT)
Author: Gurshaant Singh Malik
Report no: IIIT/TH/2016/54
Complex tasks are often handled through software implementation in combination with high per- formance processors. Taking advantage of hardware parallelism, FPGA is breaking the paradigm by accomplishing more per clock cycle with closely matched application requirements. With the aim to minimise computation delay with increase in map size and geometric constraints, FPGA based mas- sively parallel architectures are designed for super fast path planning via Rapidly Exploring Random Trees(RRT) algorithm. A Rapidly Exploring Random Tree (RRT) is an algorithm designed to efficiently search non-convex, high-dimensional spaces by randomly building a space-filling tree. The tree is constructed incrementally using samples drawn randomly from the search space. RRTs can be viewed as a technique to gener- ate open-loop trajectories for nonlinear systems with state constraints. But the algorithm is weighed down by extravagant waiting times in computation to completion, owing to its probabilistically random searching of the environment. Hence, the RRT algorithm can consume precious time cycles in generat- ing a solution to the problem of exploring a given environment. Efforts to ameliorate the unsatisfactory exploration time have focused on two areas : a.) Algorithmic design improvements b.) Parallelizing the algorithm. While Algorithmic design changes such as biased exploration, controlled exploration, faster nearest neighbour search have minimised the exploration times, the most breakthrough improve- ments have been achieved by attempts at parallelizing RRT. Here, parallelizing RRT refers to the design philosophy of integrating multiple RRT modules into an architecture that allows each of the RRT mod- ule to work in parallel while also enabling mechanisms for all of the RRT modules to collaborate and cooperate to achieve faster exploration of the environment. In the field of robotics, an FPGA is capable of delivering tightly packed, energy efficient infrastruc- tures adept in fast real time performance. An FPGA allows gate level control of system architecture. This allows the designer to tap the potential of hardware design, allowing control over minute details of arithmetic design, real time parallelization, pipe-lining of sequential processes. The hardware level flexibility afforded by an FPGA results in designs that are not only fast, but also small and power ef- ficient. FPGA boards generally consume small physical area, making it an ideal solution for robotic systems with constrained dimensions. FPGA implementation of Image processing descriptors, Random Decision Tree Body Part Recognition Using FPGA and FPGA based collision avoidance further validate this belief. This work presents two FPGA based massively parallel architectures : 1.) Hierarchical and 2.) Com- binatorial. These architectures are also analyzed against hardware implementations of other scalable RRT methods for motion planning, mainly Distributed RRT and K-Distributed RRT. Notable further- ance of acceleration capabilities was observed with the proposed architectures delivering a sizable gain over the other implementations while maintaining uniformity in exploration. To further quantify the rea- soning behind using FPGAs as the choice of parallel platform, quantitative analysis of the performance metrics of the RRT algorithm across numerous embedded hardware solutions was performed. It was ob- served that FPGA enables hardware level optimizations that offer real time performance and economical power consumption levels. Further, to validate the empirical functioning of the architectures in a real world scenario, a Zynq-SoC based differential drive robotic system was developed as a test platform to run the architectures in real time in a complex environment filled with obstacles. In summary, the designed architectures, proven adept at running in real-time on a robot, delivered a sizable gain over other state of the art algorithms, while maintaining critical parameters of the exploration like uniformity and density and also maintaining critical mobile robot requirements of small size and ambivalent power consumption levels.
Full thesis: pdf
Centre for Robotics
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved.