Automatic Motion Planning for Complex Articulated Bodies

Abstract

Much research has been devoted to path planning during the past decade, i.e. the geometrical problem of finding a collision-free path between two given postures (configurations) of an articulated body (robot) among obstacles. This problem has straightforward applications in robotic automation, computer aided design, and computer graphics animation. Current global techniques compute explicitly the non-colliding zones in configuration space. Thus, they require exponential space and time in the number of Degrees of Freedom (DOF) of the body. These methods are therefore untractable for more than 4 DOF. This report presents a new approach to path planning which does not require construction of an explicit description of the configuration space. The method consists of building and searching a graph connecting the local minima of a potential function defined over the configuration space. The graph is explored by means of a randomization technique that escapes the local minima by executing Bro...