THE COMPLEXITY OF THE FREE-SPACE FOR MOTION PLANNING AMIDST FAT OBSTACLES

The complexity of motion planning algorithms highly depends on the com plexity of the robot's free space, i.e., the set of all collision-free placements of the robot. Theoretically, the complexity of the free sp ace can be very high, resulting in bad worst-case time bounds for moti on planning algorithms. In practice, the complexity of the free space tends to be much smaller than the worst-case complexity. Motion planni ng algorithms with a running time that is determined by the complexity of the free space therefore become feasible in practical situations. We show that, under some realistic assumptions, the complexity of the free space of a robot with any fixed number of degrees of freedom movi ng around in a d-dimensional Euclidean workspace with fat obstacles is linear in the number of obstacles. The complexity results lead to hig hly efficient algorithms for motion planning amidst fat obstacles.