Kavraki Lab

SyCLoP represents a new class of motion-planning methods that synergistically combine high level planning and sampling-based motion planning to significantly reduce the time for solving challenging motion-planning problems for robotic systems with non-trivial dynamics.

The interplay in SyCLoP between the discrete search and continuous state-space exploration takes place in a workspace decomposition. The workspace is decomposed to construct a discrete-model of the motion planning problem. 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 suggested 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 SyCLoP 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 SyCLoP 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. SyCLoP is an updated and refined version of an approach called DSLX (Discrete Search Leading Continuous Exploration) proposed by us before.

SyCLoP in action solving second-order kinodynamic motion planning problems involving cars, differential drives, unicycles, and others.