Collision avoidance by free space enumeration using multiple search strategies.
Koichi Kondo · Journal of the Robotics Society of Japan · 1989
This paper presents a general and efficient method using a configuration space for planning a collision-free path among known stationary obstacles for a manipulator. The basic approach taken in this method is to restrict the free space concerning path planning and to avoid executing unnecessary collision detections, based on the idea that a collision-free path can be planned using only partial information of the configuration space. The configuration space is equally quantized into cells in a six dimensional array, and the cells cencerning path planning are enumerated by simultaneously executing multiple search strategies. The coefficients for heuristic functions are randomly generated, and search strategies of different characteristics are defined for enumerating free space cells. The efficiency of each search strategy is evaluated during free space enumeration, and a more promising one is automatically selected and is preferentially executed. The total number of necessary collision detections for free space enumeration mainly depends on the most efficient search strategy among these ones. Therefore, the free space cells are efficiently enumerated for all kinds of manipulators of different kinematic characteristics in all kinds of working environments. This method has been actually implemented and has been applied to several examples which have different characteristics.