Successive spherical approximations for planning collision-free paths in a three-dimensional robot workcell environment

Abstract

A hierarchical scheme for the representation of objects, which allows for rapid collision detection in a three-dimensional robot workcell, is presented. The Successive Spherical Approximation (SSA) scheme is based on a hierarchy of bounded rectangular sectors of spheres. The levels of the hierarchy provide a successively more detailed representation of a convex polyhedral object, ranging from a bounding sphere to the planar surfaces of the object itself. These levels allow for rapid and complete collision detection between objects in the robot workspace. The spherical nature of the SSA representation and the rapidity with which collisions can be detected make the representation well suited to generate-and-test path planning in a changing environment. A path planner, which uses the SSA representation and a set of rules based on a heuristic understanding of the robot workcell, is employed to find collision-free paths for the payload in the operational space of the environment. The planner generates paths based on the concept of a freespace cell and allows intelligent changes in both position and orientation of the object moving in a three-dimensional environment.