Collection of rrt-based algorithms that scale to n-dimensions:
Utilizes R-trees to improve performance by avoiding point-wise collision-checking and distance-checking.
This would not have been possible without Steven M. LaValle's excellent Planning Algorithms book, specifically Chapter 5, Section 5: Sampling-Based Motion Planning, Rapidly Exploring Dense Trees.
Define an n-dimensional Search Space, and n-dimensional obstacles within that space. Assign start and goal locations as well as the number of iterations to expand the tree before testing for connectivity with the goal, and the max number of overall iterations.
Assign bounds to Search Space in form: [(x_lower, x_upper), (y_lower, y_upper), ...]
Points represented by tuples of form: (x, y, ...)
Axis-aligned (hyper)rectangles represented by a tuples of form (x_lower, y_lower, ..., x_upper, y_upper, ...)
Non-axis aligned (hyper)rectangles or other obstacle representations should also work, provided that collision_free and obstacle_free are updated to work with the new obstacles.
Assign resolution of edges:
q: Distance away from existing vertices to probe.r: Discretization length to use for edges when sampling along them to check for collisions. Higher numbers run faster, but may lead to undetected collisions.Visualization examples can be found for rrt and rrt* in both 2 and 3 dimensions.
git checkout -b my-new-featuregit commit -am 'Add some feature'git push origin my-new-feature