Collision avoidance by free space enumeration based on heuristic graph search
Abstract:This paper describes a general method using configuration space for planning a collision-free path of a manipulator with 6 degrees of freedom (DOF). 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, and the cells concerning path planning are efficiently enumerated based on a heuristic graph search algorithm. A heuristic function which characterizes the search strategy can be defined to give priority to the gross motion using the first few joints. A bi-directional search strategy is also introduced to improve efficiency. The memory is allocated only to the portion of the configuration space concerning path planning, and the data of the free space defined in the 6-dimensional configuration space can be efficiently stored. This algorithm of free space enumeration is independent of the kinematic characteristics of the manipulator. Therefore, this method is generally applicable to any type of manipulator. It has actually been implemented and has been applied to a 6-DOF articulated manipulator.
Document Type: Research Article
Affiliations: Research and Development Center, Toshiba Corporation, 4-1 Ukishima-cho, Kawasaki-ku, Kawasaki, Kanagawa Pref. 210, Japan
Publication date: January 1, 1990