Kavraki Lab

Physical and Biological Computing

DSLX represents a new class of motion-planning methods that combine in novel ways discrete and continuous search to significantly reduce the time for solving challenging motion-planning problems for robotic systems with non-trivial dynamics.

The interplay in DSLX between the discrete search and continuous state-space exploration takes place in a workspace decomposition. At each iteration the discrete search computes a lead, a sequence of decomposition regions that is estimated to be important for advancing the exploration toward the goal. The continuous state-space exploration uses the current lead to extend an exploring tree along the decomposition regions specified by the lead. Information such as coverage and exploration time is fed back from the continuous state-space exploration to the discrete search to improve the lead for the next iteration.

This interaction provides DSLX with the flexibility to extend the tree along promising directions while able to radically change direction if information from the exploration suggests other promising leads, as the figure on the right illustrates.

It is this flexible interplay between discrete search and continuous state-space exploration that enables DSLX to achieve significant speedups of up to two orders of magnitude when compared to other popular tree-based motion planners such as RRT and EST.