Sloppy motors, flaky sensors, and virtual dirt: Comparing imperfect ill-informed robots

Robots must complete their tasks in spite of unreliable actuators and limited, noisy sensing. In this paper, we consider the information requirements of such tasks. What sensing and actuation abilities are needed to complete a given task? Are some robot systems provably "more powerful" than others? Can we find meaningful equivalence classes of robot systems? This line of research is inspired by the theory of computation, which has produced similar results for abstract computing machines. The basic idea is a dominance relation over robot systems that formalizes the idea that some robots are stronger than others. We show that this definition is directly related to the robots' ability to complete tasks. Our prior work in this area assumes perfect control and sensing, requires that the robot begin with a single fixed initial condition within a known environment, and models of time as a sequence of variable-length discrete stages, rather than as a continuum. In this paper, we substantially improve upon that earlier work by addressing these problems.