rrt-algorithms: sampling planners that scale to n dimensions

Five sampling planners, no robot model

rrt-algorithms is a small Python package rather than a robotics stack. It collects five sampling-based planners that work in an arbitrary number of dimensions: plain rrt, rrt*, rrt* run bidirectionally, rrt* run bidirectionally with lazy shortening, and rrt connect. The README credits Chapter 5, Section 5 of Steven M. LaValle's Planning Algorithms, the part on rapidly exploring dense trees, and its reference list points to the 1998 RRT research report and the 2000 RRT-connect conference paper.

That shapes the audience. You are writing a path planner for a robot arm, a drone or a grid world and you want a reference implementation you can read, extend and test, not a simulator with a physics engine attached. The package deals with geometry: a bounded search space, a start and goal point, axis-aligned rectangular obstacles. It carries no sensor model, no dynamics, no control law and no notion of time, so it will not hand you a kinodynamically feasible trajectory on its own.

R-trees replace point-wise collision checking

The performance story rests on a single idea. The README states that the package uses R-trees to improve performance by avoiding point-wise collision-checking and distance-checking. A straightforward implementation of a sampling planner asks the obstacle set about every sampled point, and about every point along every candidate edge. An R-tree gives the library a spatial index over the obstacle rectangles, so nearby obstacles can be found without scanning the whole scene.

The saving grows with dimension and obstacle count, which is where sampling planners get slow, but the design has a price. The obstacle representation is fixed to axis-aligned (hyper)rectangles. The README notes that non-axis-aligned hyperrectangles or other obstacle shapes should also work, provided that collision_free and obstacle_free are updated to work with the new obstacles. In practice, changing the geometry model means editing the library rather than passing a different argument, which is the main maintenance commitment this package asks of you.

Search space bounds, start, goal and flat obstacle tuples

Configuration is deliberately plain. Bounds are a list of per-axis intervals, so a two dimensional space is a list of tuples and an n dimensional space extends the same pattern. Start and goal are tuples of coordinates, and obstacles are tuples that carry the lower corner first and the upper corner last. The README gives these shapes:

[(x_lower, x_upper), (y_lower, y_upper), ...]

The obstacle tuple uses the same idea in one flat sequence, with the lower corner of every axis followed by the upper corner of every axis. A new user should note the convention difference, since bounds group values per axis while the obstacle packs them into a single sequence, and mixing them up silently produces nonsense geometry rather than an error.

Beyond the geometry, the API needs a start location, a goal location, the number of iterations to expand the tree before testing connectivity with the goal, and a maximum number of overall iterations. Those four values are what a call site actually varies between problems.

The r parameter trades runtime against missed collisions

The resolution parameter deserves attention before any benchmarking. The README describes r as the discretization length to use for edges when sampling along them to check for collisions, and states plainly that higher numbers run faster but may lead to undetected collisions. That is a real failure mode, not a theoretical caveat. An obstacle thinner than the sampling interval can be stepped over, and the planner will hand back a path that passes through it.

q is the companion knob, the distance away from existing vertices to probe. Neither parameter has a suggested default in the documentation, and there is no note on how to choose them for a given map. The practical consequence is that a clean termination is not evidence of a collision free path. If validation matters, check the returned path against the obstacle set yourself at a finer resolution than the planner used.

None of these planners is a graph search either. The collection is built around uniform random sampling with a spatial index, so a workspace small enough to expand exhaustively as a grid is served better by a deterministic search than by anything in this package.

Bidirectional search, lazy shortening and RRT-connect

The five variants differ in how they attack the same problem, and the difference is algorithmic rather than cosmetic. Plain rrt grows one tree from the start. rrt* adds rewiring so that path cost improves as the tree grows. The bidirectional rrt* grows a tree from each end, and the lazy shortening variant pulls the two trees toward one another without eagerly contracting every edge. rrt connect uses the greedy extension style rather than uniform random sampling, following the Kuffner and LaValle paper that the reference list gives the title An efficient approach to single-query path planning.

The repository layout mirrors the split: example directories exist for rrt, rrt_bid, rrt_bid_h, rrt_connect and rrt_star. The README links Plotly visualizations for rrt and rrt* in two and three dimensions, plus bidirectional and heuristic bidirectional versions. One naming point is worth checking in the source before you rely on it. The plots are labelled heuristic bidirectional while the example folder is named rrt_bid_h, so what the heuristic actually does in the code is not something the README spells out.

Installing with a pinned rtree and Python 3.10

There is no install command in the README, but the packaging metadata is explicit. setup.py declares python_requires='>=3.10' and pins rtree to one version while keeping floor versions for the rest:

install_requires=['rtree==1.2.0',
                  'numpy>=1.25',
                  'plotly',
                  'scipy>=1.11'],

The distribution name is rrt-algorithms, the version string in setup.py is 0.0.1, and packages are discovered with find_packages so that the rrt_algorithms directory is picked up. The README separately lists Python 3+, NumPy, Rtree and Plotly as requirements and notes that Plotly is needed only for plotting, which matters if you intend to use the planners headlessly and skip the visualisation layer.

The single pinned dependency is the main upgrade hazard. The repository has no GitHub releases, so there is no tagged version whose dependency set was validated for you, and rtree==1.2.0 is fixed rather than given a range.

Contributing through a develop branch and an MIT licence

The tree is flat: .gitignore, .vscode, LICENSE, README.md, examples, rrt_algorithms and setup.py, with the default branch named develop. The contributing section is a fork and pull request flow with concrete commands:

git checkout -b my-new-feature
git commit -am 'Add some feature'
git push origin my-new-feature

The licence is MIT, so code taken from the repository can be reused in closed or open source projects under those terms, and anything you derive from it carries the same licence. The version string, the absent releases and the branch name together describe what kind of dependency this is: a readable reference implementation that you vendor or pin, not a service with a support commitment behind it. The last push was on 2026-09-05.

Editorial conclusion

Adopt rrt-algorithms if you want a short, readable sampling planner in an arbitrary number of dimensions and are prepared to supply your own obstacle model, robot model and path validation. Skip it if you need kinodynamic feasibility, dynamic obstacles, a sensor model or a maintained release train, since the package supplies none of those and the repository has no GitHub releases. Before you build on it, check the r discretization against your thinnest obstacle, confirm that collision_free and obstacle_free still match your obstacle geometry, and verify that the pinned rtree==1.2.0 works on your platform. The licence is MIT and the last push was on 2026-09-05, with the version string in setup.py still at 0.0.1.

Frequently asked questions

Official sources

1. Issues
2. License: MIT
3. motion-planning/rrt-algorithms on GitHub
4. README