Kavraki Lab

A Platform for High-Dimensional Motion Planning

SRT is a motion planner that combines advantages of traditional sampling-based planners. SRT is geared toward high-dimensional problems that test the limits of current motion planners. SRT creates a roadmap of trees that integrates the global sampling properties of PRM [Kavraki et al.] with the local sampling properties of tree-based planners, such as RRT [LaValle, Kuffner] and EST [Hsu et al.] SRT is shown to be significantly faster and more robust than PRM and the tree-based planners it uses.

Algorithm

SRT constructs a roadmap aimed at capturing the connectivity of the free configuration space and then uses the roadmap to answer multiple queries. The nodes of the roadmap are not single configurations but trees, which are referred to as milestones. Connections between milestones are computed by sampling-based tree planners. The roadmap construction goes through several stages: milestone computations, candidate edges, and edge connections.


Fig. A problem with 48 DOFs that SRT can easily solve.

(a) Milestones (b) Candidate Edges
(c) Edge Connections (d) Query Solving

Milestones: In SRT, the trees of the roadmap are computed by sampling their roots uniformly at random in the free configuration space and then using a sampling-based tree planner to explore the region around the root configuration.

Candidate edges: Neighboring trees are considered as candidate edges for connections, where a distance metric defines closeness between trees. Random neighbors are also used to offset any problems with the distance metric.

Connect trees: Connections between trees are computed by a sampling-based tree planner. For each candidate edge (T’, T’’), a small number of close pairs of configurations of T’ and T’’ are quickly checked with a fast local planner. If any local path is found, no further computation takes place. Otherwise, a more complex tree-connection algorithm is executed, e.g., bi-directional RRT or EST. During the tree connection, additional configurations are typically added to the trees T’ and T’’. If the tree-planner is successful, the edge (T’, T’’) is added to the roadmap and the graph components to which T’ and T’’ belong are merged into one.

Solve queries: Queries are solved by rooting two trees at the initial and goal configurations and then connecting the trees to the neighboring trees in the roadmap. A path is found if at any point the initial and goal tree lie on the same connected component of the roadmap.