Abstract
This article addresses issues involved in programming auto matic solvers for collision-avoidance problems in robotics. It presents a refined notion of empty space and shows that solution methods to the find-path problem all reduce to graph-search techniques. The article introduces an intrinsic tree structure for empty space that reduces the complexity of the problem and discusses inherent limitations to implemen tations, taking into account approximation and computer geometry problems. Computational complexity and practical limitations of the methods are addressed. This study shows how to develop a very simple and efficient solution to prob lems of gross motion for general manipulator robots. The approach is compatible with arbitrary assumptions about ob stacle geometry and representation of real objects in a com puter.