Heuristische Bewegungsplanungsstrategien im IR^3

Abstract

Two general heuristic approaches to the geometric motion planning problem are considered. Both heuristics make use of efficient collision detection algorithms and combine motion planning with collision detection to speed up planning or to extend planning facilities. The first approach tries to speed up motion planning by ignoring all obstacles in the scene which do not contribute to the planned collision-free path. In order to obtain such a minimal scene the heuristic computes a collision-free path in a scene and checks the planned paths for collisions with ignored obstacles using standard collision detection algorithms. The heuristic thereby conserves qualitative features of the algorithms used like completeness, computation of most-secure, euclidian-shortest or time-optimal paths. It can be used with any kind of motion planning algorithms like classical ones, algorithms for dynamical environments or multiple moving objects. The advantages of the heuristic are shown for a complete algorithm handling 3-dimensional objects with two translational degrees of freedom using the configuration space approach of Lozano-Perez and Wesley. The second heuristic extends the facilities of algorithms for static environments by classifying the obstacles in the scene in fixed and movable obstacles forming a motion planning problem with many degrees of freedom. The complex problem is decomposed in a series of simple problems which can be solved efficiently by known algorithms and the solutions are combined to a solution for the whole problem. It is shown that together with a problem modification strategy the heuristic nearly always extends and never reduces the facilities of motion planning algorithms in static environments.