Home > Articles > All Issues > 2017 > Volume 6, No. 6, November 2017 >

FPGA Based Massively Parallel Hybrid Architecture for Parallelizing RRTs

Gurshaant Singh Malik 1, Krishna Gupta 1, Raunak Dharani 2 , and K. Madhava Krishna 3
1. International Institute of Information Technology, Hyderabad, India
2. North Carolina State University, USA

Abstract— Field Programmable Gate Arrays(FPGA) exceed 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. As has been proved in already published research works, 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. FPGA based combinatorial architecture, which is one of the already published research works, delivers superlative speed-up but consumes very high power. The second of the already published research works, FPGA based hierarchical architecture, delivers relatively lower speed-up with acceptable power consumption levels. To combine the qualities of both, a hybrid architecture, that encompasses both combinatorial and hierarchical architecture, is designed. To determine the design parameters of the hybrid architecture, a cost function comprised of fundamentally inversely related speed-up and power parameters, as mentioned above, is formulated. This maximization of cost function, with its associated constraints, is then mathematically solved using a modified branch and bound, that leads to optimal deduction of the design parameters of the hybrid architecture. Via empirical experiments, 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, in environments of varying geometric complexity. The empirical experiments also confirmed that the hybrid architecture is scalable with 1.) Increase in the environment's geometric complexity and 2.) Increase in kinematic complexity of the robot.

Index Terms—FPGA, Mobile Robotics, RRT, Parallelization, Hardware, Exploration.

Cite: Gurshaant Singh Malik, Krishna Gupta, Raunak Dharani, and K. Madhava Krishna, "FPGA Based Massively Parallel Hybrid Architecture for Parallelizing RRTs," International Journal of Mechanical Engineering and Robotics Research, Vol. 6, No. 6, pp. 467-475, November 2017. DOI: 10.18178/ijmerr.6.6.467-475