Best Student Paper Award at SMC 2021
Best Paper Award Finalist at SMC 2021
What is RRT-Rope?
RRT-Rope aims at finding a near-optimal solution in a drastically shorter amount of time for UAV path planning in large-scale 3D environments. The proposed approach benefits from RRT-connect fast computation to find a feasible path, and post-processes it quickly to a near-optimal path, taking advantage of intermediate nodes added to each branch of the tree and stretching them like a rope. RRT-Rope gives better results in terms of path cost and computation time than other popular RRT variations and shortening techniques in all our simulation environments, and is up to 70% faster than the next best algorithm in a representative environment.
Why?
The idea comes from an autonomous drone project designed to map underground mining stopes. Mining cavities are often large-scale and uncluttered. Many path planning algorithms have been introduced so far, but most are costly, in path cost, and in processing time, in such environments. Rapidly-exploring Random Tree (RRT) algorithms are popular because of their probabilistic completeness and rapidity in finding a feasible path in single-query problems. Many of the algorithms (e.g. Informed RRT*, RRT#) developed to improve RRT need considerable time to converge in large environments. Shortcutting an RRT is an old idea that has been proven to outperform RRT variants. Underground mining stopes are 3-ball homotopic and the optimal path is therefore in the same homotopy class as any feasible path. The idea of the project is to take advantage of this to develop a path planning algorithm that finds a near-optimal solution in a drastically shorter amount of time than the state-of-the-art in large-scale uncluttered 3D environments.
BibTeX
@inproceedings{petit2021rrtrope,
author = {Petit, Louis and Desbiens, Alexis Lussier},
title = {RRT-Rope: A Deterministic Shortening Approach for Fast Near-optimal Path Planning in Large-Scale Uncluttered 3D Environments},
booktitle = {2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC)},
year = {2021},
url = {https://arxiv.org/abs/2606.31948}
}