The kinematic roadmap: A motion planning based global approach for inverse kinematics of redundant robots

This paper proposes a novel and global approach to solving the point-to-point inverse kinematics problem for highly redundant manipulators. Given an initial configuration of the robot, the problem is to find a reachable (path-connected) configuration (and a feasible path to it) that corresponds to a desired position and orientation of the end-effector, Our approach is inspired by recent motion planning research and explicitly takes into account constraints due to joint limits, self-collisions, and static obstacles in the environment. Central to our approach is the novel notion of kinematic roadmap for a manipulator. The kinematic roadmap captures the connectivity of the connected component (that contains the initial configuration) of the free configuration space of the manipulator in a finite graph like structure. The point-to-point inverse kinematics problem is then solved using this roadmap, We provide completeness results for our algorithm, Our current implementation, based on Ariadne's Clew Algorithm [5], [32], is composed of two sub-algorithms: EXPLORE, an appealingly simple algorithm that builds the kinematic roadmap by placing landmarks in the free configuration space; and SEARCH, a local planner, that uses this roadmap to reach the desired end-effector configuration. Our implementation of SEARCH is an efficient closed form solution, albeit local, to inverse kinematics that exploits the serial kinematic structure of serial manipulator arms. Initial experiments with a seven-DOF manipulator have been extremely successful.