Visibility analysis and genetic algorithms for fast robot motion planning

Although extensive work about robot path planning has been carried out, there is still a need for fast, practical and general-purpose motion planners. New applications of robots, outside the known and fixed environment of a factory, will increase the need for such planners. In these situations it will be necessary to cope with very variable and complex environments and with direct human interaction. A new approach for n-degree-of-freedom robot motion planning, based on the concept of visibility tetrahedra and the use of genetic algorithms combined with local search methods, is presented in this paper. The proposed approach has been successfully tested over several selected experiments, obtaining fast planning even for complex situations.

1 Introduction

Although many different motion planning methods have been proposed [1] most of them are not used in practice. Complete planners are too slow to be useful except for some restricted cases, e.g. robots with two or three degrees of freedom (dot), and require a processing time that is exponential in the number of dof of the robot [4] The increasing need of practical planners for robots with many dof has focused the attention on randomized or probabilistic motion planning methods. These methods are incomplete or embed weaker notions of completeness because they will find a solution if exists given a sufficient running time.