Using moments to plan paths for the Oxford AGV

Abstract

A simple algorithm based on the artificial potential field paradigm and capable of planning translational motions for a convex polygonal object among polygonal obstacles is outlined. A heuristic based on the concept of taking moments is introduced. It allows this algorithm to be extended to include a rotational degree of freedom. It is then shown that this method can be used form the basis of a local obstacle avoidance algorithm for a robot vehicle following a corridor. It is observed that the lines of minimum potential which the moving object is made to follow correspond to the Voronoi diagram of the environment. It is also observed that the form of the Voronoi diagram under the Euclidean (L/sub 2/) metric is not necessarily ideal for path planning and that the minimum distance function upon which the potential field approach relies may be calculated more swiftly under the L/sub 1/ and L/sub infinity / metrics. For these reasons the form of the Voronoi diagram under those metrics is investigated.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>