  This paper addresses the lower limits of encoding and processing the
information acquired through interactions between an internal system (robot
algorithms or software) and an external system (robot body and its environment)
in terms of action and observation histories. Both are modeled as transition
systems. We want to know the weakest internal system that is sufficient for
achieving passive (filtering) and active (planning) tasks. We introduce the
notion of an information transition system for the internal system which is a
transition system over a space of information states that reflect a robot's or
other observer's perspective based on limited sensing, memory, computation, and
actuation. An information transition system is viewed as a filter and a policy
or plan is viewed as a function that labels the states of this information
transition system. Regardless of whether internal systems are obtained by
learning algorithms, planning algorithms, or human insight, we want to know the
limits of feasibility for given robot hardware and tasks. We establish, in a
general setting, that minimal information transition systems exist up to
reasonable equivalence assumptions, and are unique under some general
conditions. We then apply the theory to generate new insights into several
problems, including optimal sensor fusion/filtering, solving basic planning
tasks, and finding minimal representations for modeling a system given
input-output relations.
