Skip to content
This repository has been archived by the owner. It is now read-only.
Switch branches/tags

Latest commit


Git stats


Failed to load latest commit information.
Latest commit message
Commit time
ARCHIVE NOTICE: The implemneted environment had been cleaned up and extended into a dedicated SBP planning module at sbp-env. This repo will remains as is for the ICRA'19 version.

Rapidly-exploring Random disjointed-Trees

RRdT* uses multiple disjointed-trees to exploit local-connectivity of spaces via Markov Chain Monte Carlo (MCMC) random walk, which utilises neighbourhood information derived from previous successful and failed samples. The active balancing of global exploration and local exploitation is the key to improve sample efficiency.

This is a repository that contains a Python implementation of the algorithm describe in the paper, along with implementation of other state-of-the-art planners that had been experimentally compared to RRdT*.

The algorithm is described in the paper from ICRA'19. A complementary video that explains the concept can be found here. If you want to cite this work in your research, you can use this BibTex entry.



I always recommend people to create a virtual environment for each of their specific research project. You can do this with

# assuming python3 and bash shell
python -m venv rrdt
source rrdt/bin/activate

to create a virtual environment named as rrdt.

Install dependencies

You can install all the needed packages with pip.

pip install -r requirements.txt

Quick Guide

You can get a detailed help message with

python --help

but the basic syntax is

python <PLANNER> <MAP> [options]

It will open a new window that display a map on it. Every white pixel is assumed to be free, and non-white pixels are obstacles. You will need to use your mouse to select two points on the map, the first will be set as the starting point and the second as the goal point.


Run maps with different available Planners

This repository contains a framework to performs quick experiments for Sampling-Based Planners (SBPs) that are implemented in Python. The followings are planners that had implemented and experimented in this framework.

Note that the commands shown in the respective demos can be customised with additional options. In fact, the actual command format used for the demonstrations is

python <PLANNER> maps/room1.png start <sx> <sy> goal <sx> <sy> -vv

to have a fix set of starting and goal points for consistent visualisation, but we omitted the start/goal options in the following commands for clarity.


python rrdt maps/room1.png -vv

RRdT* Planner


python rrt maps/room1.png -vv

RRT* Planner


python birrt maps/room1.png -vv

Bi-RRT* Planner

Informed RRT*

python informedrrt maps/room1.png -vv

Informed RRT* Planner

The red ellipse shown is the dynamic sampling area for Informed RRT*


There are also some other planners included in this repository. Some are preliminary planner that inspired RRdT*, some are planners with preliminary ideas, and some are useful for debugging.

How does it works

You can have a look of the paper Balancing Global Exploration and Local-connectivity Exploitation with RRdT, or this video that briefly explain the concepts:

RRdT youtube video


If you found the algorithm or the implementations of SBPs framework useful, please cite the following paper.

    title={Balancing Global Exploration and Local-connectivity Exploitation with Rapidly-exploring Random disjointed-Trees},
    author={Lai, Tin and Ramos, Fabio and Francis, Gilad},
    booktitle={Proceedings of The International Conference on Robotics and Automation (ICRA)},


Rapidly-exploring Random disjointed-Trees for Motion Planning





No releases published


No packages published