| 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", in terms of the tasks that they can complete, 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.
Our basic contribution is a dominance relation over robot systems
that formalizes the idea that some robots are stronger than others.
This comparison, which is based on how the robots progress through
their information spaces, induces a partial order over the set of robot
systems. We prove some basic properties of this partial order and
show that it is directly related to the robots’ ability to complete tasks.
We give examples to demonstrate the theory, including a detailed
analysis of a limited-sensing global localization problem. |
