# Balancing Global Exploration and Local-connectivity Exploitation with Rapidly-exploring Random disjointed-Trees

arXiv: https://arxiv.org/abs/1810.03749 · HTML: https://mlsanity.com/paper/1810.03749/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2018.

## Built on by (most cited first, 8 of 8)

- [Parallelised Diffeomorphic Sampling-based Motion Planning](https://mlsanity.com/paper/2108.11775/) (2021)
- [A Review on Visual-SLAM: Advancements from Geometric Modelling to Learning-based Semantic Scene Understanding](https://mlsanity.com/paper/2209.05222/) (2022)
- [Obstacle Aware Sampling for Path Planning](https://mlsanity.com/paper/2203.04075/) (2022)
- [L4KDE: Learning for KinoDynamic Tree Expansion](https://mlsanity.com/paper/2203.00975/) (2022)
- [sbp-env: Sampling-based Motion Planners' Testing Environment](https://mlsanity.com/paper/2110.08402/) (2021)
- [Discover Life Skills for Planning with Bandits via Observing and Learning How the World Works](https://mlsanity.com/paper/2207.08130/) (2022)
- [Planning and Learning: Path-Planning for Autonomous Vehicles, a Review of the Literature](https://mlsanity.com/paper/2207.13181/) (2022)
- [Discovering Multiple Algorithm Configurations](https://mlsanity.com/paper/2303.07434/) (2023)

## Abstract (arXiv)

Sampling efficiency in a highly constrained environment has long been a major challenge for sampling-based planners. In this work, we propose Rapidly-exploring Random disjointed-Trees* (RRdT*), an incremental optimal multi-query planner. RRdT* uses multiple disjointed-trees to exploit local-connectivity of spaces via Markov Chain random sampling, which utilises neighbourhood information derived from previous successful and failed samples. To balance local exploitation, RRdT* actively explore unseen global spaces when local-connectivity exploitation is unsuccessful. The active trade-off between local exploitation and global exploration is formulated as a multi-armed bandit problem. We argue that the active balancing of global exploration and local exploitation is the key to improving sample efficient in sampling-based motion planners. We provide rigorous proofs of completeness and optimal convergence for this novel approach. Furthermore, we demonstrate experimentally the effectiveness of RRdT*'s locally exploring trees in granting improved visibility for planning. Consequently, RRdT* outperforms existing state-of-the-art incremental planners, especially in highly constrained environments.