An Algorithm For Planning An Optimum Collision-Free Path In Structured Environment

Abstract

An efficient algorithm for planning collision-free paths in a planar workspace, cluttered by known obstacles, is presented. The mobile entity is assumed to move with a fixed orientation. Our approach adopts the transformation of the obstacles from the Cartesian space into the configuration space (C-space). Moreover the feasible paths inside the workspace are represented through a set of straight line trajectories (spines), constituting the axes of natural freeways between C-space obstacles. The path planner finds out the optimum path for the mobile point, from the start to the target position, displacing it from spine to spine, at their intersection points. The proposed approach was applied to the three-dimensional gross motion planning of an industrial robot (a PUMA 560). In the experimental phase it always yielded satisfactory results, finding out optimum paths also in highly cluttered environments.