A vector based approach to robot path planning

Abstract

A vector-based algorithm for planning the path of a robot among irregularly shaped obstacles is presented. This algorithm combines many of the desirable features of graph searching and potential field approaches to path planning. In this technique, a vector is created from the start position to the goal of the robot. If this vector crosses forbidden space, a second vector is used to determine a new intermediate goal and the previous goal is stored on a stack. The procedure is repeated until the latest intermediate goal can be reached, at which point the robot can be moved to this goal. This procedure is repeated by popping a goal off of the stack and continuing until the ultimate goal is reached. Preliminary results show much promise for quickly planning paths of robots in two or more dimensions. Examples of planning around multiple two-dimensional obstacles of convex and concave shapes are shown.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>