=ADD=
=author=
Van Geem; Carl
=title=
Fast Planning of a Good Path for a Manipulator Using Potential Fields on a Non-Uniform Grid in C-Space
=number=
96-15
=month=
5
=year=
1996
=url=
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1996/96-15.ps.gz
=abstract=
This Ph.D. Thesis considers the Robot Motion Planning Problem for a robot arm
using the concept of Configuration Space. The approach described here
leads to a path with some particular properties. It also gives rise to
a complete solution of the problem under certain conditions. 

The thesis tends to be applicable, since the considerations on which
the approach is ented are practice oriented. On the other hand only
bits and parts are implemented for the moment, and some parts of the
work are still in a theoretical phase. We strongly believe that these 
parts can be implemented and fit together. 

Our original results of research are the following: 
We observed that the use of a non-uniform grid in combination 
with a potential field similar to the Manhattan distance on a 
uniform grid makes the use of a repulsive potential superfluous 
when we want to end up with a safe 
but (in Configuration Space) short path. In order to represent the
non-uniform grid, we have chosen to use the so called GET
Representation for a $2^k$-tree (due to Klaus Burger, diploma thesis:
``A Kernel-Based Construction System (KBC)'', RISC-Linz, 1992).

As a motivation for the use of a non-uniform grid as opposed to
a uniform grid, we counted out for a set of polygons with a particular
shape what the gain in number of cells is when using cells of
different sizes.

We observed that it is possible to translate the algorithms due to
Irene Gargantini (``Linear Octtrees for Fast 
Processing of Three-Dimensional Objects'', Computer Graphics and Image
Processing, Vol.20, 1982) for neighbour computation in quad- and
octrees to the GET Representation, and did so. The neighbour
computation in the non-uniform grid (looking for adjacent cells of a
given cell) is an essential operation for the construction of a
potential field on the grid. 

We implemented a non-hierarchical construction of a potential field on a 
non-uniform grid. We also describe a hierarchical construction. 
The advantage of a hierarchical construction is
that we at first can construct the non-uniform grid and a potential field
on it up to a certain dimension and expand the model of the
Configuration Space to a higher dimension later on, when necessary. This
corresponds more or less to the approach of gross and fine motion
planning as it is known in the literature.

When it is observed during execution of a path that an
obstacle is positioned differently compared to its position during 
the planning faze, the model has to be updated.
We describe how to update the representation of the grid and the 
potential field (without recomputation of the whole model) when 
slight changes in the position of an
obstacle have occured.
=note=
Ph.D. thesis
=location=
2
=owner=
2
=source=
3
=reftype=
14