Abstract: We consider the problem of determining the information requirements to perform robot tasks, using the concept of information invariants. This paper represents our attempt to characterize a family of complicated and subtle issues concerned with measuring robot task complexity. We also provide a first approximation to a purely operational theory that addresses a narrow but interesting special case.
We discuss several measures for the information complexity of a
task: (a) How much internal state should the robot retain? (b) How
many cooperating agents are required, and how much communication
between them is necessary? (c) How can the robot change (side-effect)
the environment in order to record state or sensory information to
perform a task? (d) How much information is provided by sensors? and
(e) How much computation is required by the robot? We consider how
one might develop a kind of “calculus” on (a)-(e) in order to
compare the power of sensor network systems analytically. To this end, we
attempt to develop a notion of information invariants. We develop a
theory whereby one sensor network can be “reduced” to another (much in
the spirit of computation-theoretic reductions), by adding, deleting,
and reallocating (a)-(e) among collaborating autonomous agents.