Replanning: A Powerful Planning Strategy for Systems with Differential Constraints

K. I. Tsianos, “Replanning: A Powerful Planning Strategy for Systems with Differential Constraints,” Master's thesis, Rice University, Houston, TX, 2008.


Motion planning is a fundamental problem in robotics. When the differential constraints of a real robot are also modelled, the produced motions can be more realistic and make better use of the hardware’s capabilities. While it is not known if planning under differential constraints is a decidable problem and complete tractable algorithms are not available, sampling-based planners have been very successful at solving such problems. This thesis describes an online planning strategy which uses a sampling-based planner in a loop. Solutions for problems in static and known environments are computed incrementally through consecutive replanning steps. The robot is guided to the goal by a navigation function which is constantly updated to ensure the robot can explore all of its workspace. Experiments on various systems and workspaces show that the proposed approach can solve harder problems and produce paths of shorter duration compared to state-of-the art offline planners using only bounded memory.

PDF preprint: