MOTION PLANNING IN ENVIRONMENTS WITH LOW OBSTACLE DENSITY

We present a simple and efficient paradigm for computing the exact sol ution of the motion planning problem in environments with a low obstac le density. Such environments frequently occur in practical instances of the motion planning problem. The complexity of the free space for s uch environments is known to be linear in the number of obstacles. Our paradigm is a new cell decomposition approach to motion planning and exploits properties that follow from the low density of the obstacles in the robot's workspace. These properties allow us to decompose the w orkspace, subject to some constraints, rather than to decompose the hi gher-dimensional free configuration space directly. A sequence of unif orm steps transforms the workspace decomposition into a free space dec omposition of asymptotically the same size. The approach leads to near ly optimal O(n log n) motion planning algorithms for free-flying robot s with any fixed number of degrees of freedom in workspaces with low o bstacle density.