Balancing Global Exploration and Local-connectivity Exploitation with Rapidly-exploring Random disjointed-Trees
This work addresses sampling efficiency for motion planning in robotics, offering an incremental improvement with novel balancing mechanisms.
The paper tackles the challenge of sampling efficiency in constrained environments for motion planning by proposing RRdT*, a multi-query planner that balances local exploitation and global exploration using a multi-armed bandit approach, resulting in outperforming state-of-the-art planners in highly constrained settings.
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.