IIIT Hyderabad Publications |
|||||||||
|
FPGA based hybrid architecture for parallelizing RRT with software defined multi-RRT seedingAuthor: Krishna Gupta Date: 2019-05-18 Report no: IIIT/TH/2019/46 Advisor:Madhava Krishna AbstractField Programmable Gate Array (FPGA) is gaining popularity in robotics applications due to low cost, portability, low power dissipation, high speed and seamless interface to the hardware. On the other hand, robotics algorithms are mostly arithmetic in nature so they can be easily parallelized and implemented on FPGA. Asynchronous FPGAs have gained remarkable research interest over the last decade.FPGA exceeds the computing power of software-based implementations by breaking the paradigm of sequential execution and accomplishing more per clock cycle by enabling hardware level parallelization at an architectural level. Introducing parallel architectures for a computationally intensive algorithm like Rapidly-Exploring Random Trees(RRT) will result in an exploration that is fast, dense and uniform. 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 from samples drawn randomly from the search space and is inherently biased to grow towards large unsearched areas of the problem. But the overall performance of the algorithm comes down due to high computation delay with the increase in the maps size and geometric constraints. One way to improve the performance is by parallelizing RRT. Here parallelizing RRT refers to multiple RRT modules working in parallel to achieve faster exploration of the map. And to accommodate all the data that is coming from multiple modules an architecture is required. So with the aim to minimize computation delay with the increase in maps size and geometric con- straints, we present the FPGA based hybrid architecture that allows multiple RRTs to work together combined with modified K-means sensitive to the geometric and kinematic constraints of the robot for accelerated and uniform exploration of the map. Through a cost function delineated in later sections, FPGA based combinatorial architecture delivers superlative speed-up but consumes very high power while hierarchical architecture delivers relatively lower speed-up with acceptable power consumption levels. The hybrid architecture combines the qualities of both combinatorial and hierarchical architecture. To determine the number of RRT nodes to be allotted to the combinatorial and hierarchical blocks of the hybrid architecture, a cost function, comprised of fundamentally inversely related speed-up and power parameters, is formulated. This maximization of the cost function, with its associated constraints, is then mathematically solved using a modified branch and bound, that leads to the optimal allocation of RRT modules to both blocks. For the initial placement of RRTs, we came up with a software-defined strategy for identification of these starting points using a modified K-Means. Strategized placing of the seeds (starting points) of each RRT module can lead to a more homogeneous and faster exploration as compared to the indiscriminate placement of the same. Further, to validate the empirical working of the architectures in a real-world scenario, a Zynq-SoC based differential drive robotic system was built as a test platform to run the architectures in real time in a complex environment filled with obstacles. It is observed that this hybrid architecture delivers the highest performance-per-watt out of the three architectures for differential, quad-copter and fixed-wing kinematics. The overall system is a hardware-software co-design to achieve real-time, ASIC like performance that delivers accelerated and homogeneous exploration. Full thesis: pdf Centre for Robotics |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |