Heuristic Motion Planning with Movable Obstacles

Abstract

We present a heuristic approach to geometric path planning with movable obstacles. Treating movable obstacles as mobile robots leads to path planing problems with many degrees of freedom which are intractable. Our strategy avoids this computational complexity by decoupling the whole motion planning problem into a series of tractable problems, which are solved using known path planning algorithms. The individually computed solutions are then coordinated to a path plan. This method results in a powerful and practicable strategy for path planning with movable obstacles, which can be applied using a wide variety of known motion planning algorithms. 1 Introduction Objects in geometric path planning problems are usually divided into moving objects and fixed ones called obstacles. In a problem description the moving objects and the obstacles are given - usually as polygons or polyhedra - together with their positions and orientations. For the moving objects goal configurations are specified ...