The Complexity of Fine Motion Planning

Abstract

This paper concerns the problem of motion planning for robots with uncertainty in sensing and control. Although this problem has been studied before, this is the first attempt at its inherent complexity. To compensate for the uncertainties in sensing and control, our robot model includes damping— a limited capacity for compliance. In this setting, we show that motion planning for point objects is PSPACE-hard by a direct reduction from polynomial-space bounded Turing machine computations. We also present a restricted version of the problem that is PSPACE-complete.