illustrations illustrations illustrations illustrations illustrations illustrations illustrations

Parallel Rapidly-Exploring Random Tree Algorithm

Published on May 26, 2017 by Mantej Singh on Robotics

Parallel Rapidly-Exploring Random Tree Algorithm

Developing a novel parallel Rapidly-Exploring Random Tree algorithm to increase the efficiency and speed of robotic motion planning.

To further my exploration in robotics and its capabilities in medical technology, I embarked on my senior capstone project with Professor Lydia Kavraki at Rice University to improve the performance of the Rapidly Exploring Random Tree (RRT) algorithms, which are widely used for motion planning in kinodynamic systems in the fields of surgical robotics and autonomous vehicles. As RRT algorithms have traditionally been programmed to run sequentially on a single core, they experience significant degradation of performance when deployed in more complex and higher dimensional spaces that better mirror reality. I sought to develop a novel parallel RRT algorithm that fully utilizes multiple threads present on multi-core machines using the OpenMP framework to run computationally intensive steps in parallel that optimized computation time. Since the robot could not simply move towards the goal state in any direction it pleased, I could not control its state directly but only through derivatives of its control parameters. This posed a unique challenge and forced me to think about how bet to transform and map the input onto the output data so that I could manipulate the robot as needed. Ultimately, I developed an algorithm that achieved higher computational speed and efficiency of resource utilization with a 2x speedup when using 2 threads and a 2.35x speed up when using 3 threads

Similar Stories