Kavraki Lab

Sampling-based planners are usually thought of as offline planners which try to find a trajectory through some hard narrow passage. Typical problems include the need for possibly unbounded amounts of memory and the generation of trajectories that include a lot of redundant motions. Those problems are more pronounced if a robot has realistic motion constraints (e.g., bounded acceleration) and physical effects such are gravity and friction are modeled. This work describes a sampling-based kinodynamic motion planner that solves hard problems using replanning. The overall planning process is broken down into replanning cycles. In each cycle, a sampling-based planner is invoked for a small amount of time to produce a kinodynamic tree of possible future motions. Then a navigation function is used to evaluate these motions and select the one that brings the robot closer to its goal.

This approach has the advantage that it uses only bounded memory. Moreover, it has been shown experimentally that the produced paths are much shorter than those of state-of-the art sampling-based planners. In addition this algorithm was able to solve harder problems more consistently. These results agree on experiments with a segway and a blimp. Finally, due to the adaptive nature of replanning, this method can be extended to problems where the robot encounters unexpected obstacles and also moving obstacles.

Video: A segway is moving to its goal while avoiding newly sensed unexpected static obstacles. It also avoids moving obstacles that are assumed to be fully predictable here.
Video: A blimp flies to its goal by hovering among two parallel plates.