Motion planning; a survey of approaches.
Report 94.3.LT.4282, Transport Technology, Logistic Engineering.
Motion planning is planning the motion of an object through an environment
filled with obstacies. An important application is motion-planning of a
robot. Borsje [Report 93.3.LT.4193]
describes a motion planning problem incorporated in a production planning
problem. The motion planning problem has to be solved by the
production-planning program in order to determine whether or not a part
can be transported to its next destination in the production area.
A motion-planning problem is defined by the constraints imposed on the
motion. These constraints can be geometric constraints, kinematic
constraints and/or dynamic constraints. A classification of
motion-planning problems is given.
The find-path problem is the most fundamental motion-planning problem. lt
is the problem of finding a collision-free path for an object through an
environment containing stationary obstacles whose shapes and
configurations are known in advance. The only constraint is collision
avoidance. Complete algorithms solving a find-path problem of any
dimensionality exist, but suffer from extremely high complexity.
For high dimensional problems, only approximating algorithms are of
practical interest. These algorithms require many computations. Recently,
the application of parallel programming has made it possible to run these
algorithms in a reasonabie time.
For the case of two degrees of freedom the choice of both complete and
approximating algorithms is much richer. These methods are also applied to
higher dimensional problems. In this case the problem has to be reduced to
a two-dimensional problem first. Particularly elimination of rotational
degrees of freedom makes a probiem much easier to solve.
Reports on Logistic Engineering (in Dutch)
, TU Delft