Back To Schedule
Wednesday, October 27 • 3:15pm - 3:30pm
Parallel RRT Algorithm for Robotic Motion Planning

Sign up or log in to save this to your schedule, view media, leave feedback and see who's attending!

Feedback form is now closed.
The advent of autonomous technology ranging from self-driving cars to robotic surgery has propelled motion planning algorithms to the forefront of research. The Rapidly-exploring Random Tree (RRT) algorithm is one such example that is used by robots to find a suitable path between two points while avoiding obstacles. It does this by building a search tree rooted at the start point and then grows the tree by randomly generating and connecting nodes in the search space. It then verifies each connection to ensure no collision has taken place. The algorithm terminates when the goal region is searched and returns a valid path through the tree.

Traditionally, RRT is designed to run sequentially on a single thread. Increasing the speed and efficiency of the algorithm would facilitate its use in highly complex realistic scenarios. With the advent of powerful computing machines, it is an opportune time to enhance the performance of these algorithms. This paper presents a novel parallel-RRT motion planning algorithm that performs computationally intensive steps in batches simultaneously on multiple threads. This increases the number of nodes created and collision checked per second hence finding paths faster.

To test the novel algorithm, we recorded the time taken for a car in a two dimensional space to navigate from a start to a goal point while avoiding obstacles in unknown environments. Results proved that the algorithm successfully utilized the additional threads to calculate paths quicker and more efficiently. In terms of speed, the algorithm showed a 2x speedup when using 2 threads and a 2.35x speedup when using 3 threads. In terms of efficiency, which was reflected by the number of connections added to the search tree per second, the algorithm showed a 2.25x increase in efficiency using 2 threads and a 3x increase using 3 threads.

These preliminary results show promise for leveraging parallel implementations of motion planning algorithms. The use of novel parallel algorithms such as that utilized in this paper heralds the progression into a new era of motion planning capabilities and would invigorate current development efforts in robotics and automation.

Authors: Mantej Singh, Rahul Shome, and Lydia Kavraki


Mantej Singh

Rice University

Wednesday October 27, 2021 3:15pm - 3:30pm CDT

Attendees (2)