11institutetext: Center of Ubiquitous Computing
Faculty of Information Technology and Electrical Engineering
University of Oulu, Finland

# The Limits of Learning and Planning:
Minimal Sufficient Information Transition Systems

Basak Sakcak  Vadim Weinstein  Steven M. LaValle This work was supported by a
European Research Council Advanced Grant (ERC AdG, ILLUSIVE: Foundations of
Perception Engineering, 101020977), Academy of Finland (projects PERCEPT
322637, CHiMP 342556), and Business Finland (project HUMOR 3656/31/2019).
(e-mail: firstname.lastname@oulu.fi).

###### Abstract

In this paper, we view a policy or plan as 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. Regardless of
whether policies are obtained by learning algorithms, planning algorithms, or
human insight, we want to know the limits of feasibility for given robot
hardware and tasks. Toward the quest to find the best policies, we establish
in a general setting that minimal information transition systems (ITSs) 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 feasible policies.

###### keywords:

planning, sensing uncertainty, information spaces, theoretical foundations

##  1 Introduction

Robotics increasingly appears as an application area for other fields. It is a
frequent target for designing and testing machine learning algorithms,
planning algorithms, sensor fusion methods, control laws, and so on. This may
lead many to believe that robotics itself does not have its own, unique
theoretical core (on this, we agree with Koditschek [6]). Thus, are we missing
something? Surely robotics is not a pure algorithmic problem or pure nonlinear
control problem. Could there be a theory that plays a similar role to Turing
machines for computer science, or ${\dot{x}}=f(x,u)$ over differentiable
manifolds for control theory, and yet is distinct from both? Can we formulate
and potentially answer questions such as: Does a solution even exist to the
problem? What are the minimal necessary components to solve it? What should
the best learning approach imaginable produce as a representation? Such
questions would be analogous to existence and uniqueness in control and
dynamical systems, or decidability and complexity (especially Kolomogorov) in
theoretical computer science.

|  |
---|---|---
(a) |  | (b)
Figure 1: (a)The internal robot brain is defined as an ITS that interacts with
the external world (robot body and environment). (b)Coupled internal and
external systems mathematically capture sensing, actuation, internal
computation, and the external world.

This paper proposes a robotics theory that is built from the input-output
relationships between a programmable mechanical system (robot) and its
environment via sensing and actuation; see Figure 1(a). The key is to focus on
necessary and sufficient conditions that a robot’s internal processor (i.e.,
“brain”) must maintain to solve required tasks, such as collision-free
navigation or coverage. We assume that the robot hardware and actuation model
are fixed, and that for a given set of tasks in a space of environments, we
must determine the weakest amount of sensing, actuation, and computation that
would be sufficient for solving tasks. We will call such conditions minimal
sufficient: If you take away anything from a minimal sufficient system, the
tasks will become unsolvable.

We introduce the notion of an information transition system (ITS) to formally
model the robot’s brain (as well as any other system observers). The
“information” part of an ITS is inspired by von Neumann’s definitions in the
context of sequential games with hidden information (and not Shannon’s later
notion of information theory). This inspired the development of information
spaces [8] (Chapter 11) as a foundation of planning with imperfect state
information due to sensing uncertainty. The concept of sufficient information
mappings appears therein. It is generalized in this paper, and the state space
of each ITS will in fact be an information space.

In our work, the ITS and its underlying information space serve as the domain
over which a plan or policy can be expressed and analyzed. Note that prior
work in planning usually assumes that the space one plans over is fixed, as in
a configuration space or state (phase) space based on the robot’s mobility.
Even the information spaces described in [8] remain fixed in the planning
phase. A notable exception is by O’Kane and Shell [11], in which information
spaces for passive filtering are reduced algorithmically, and is closely
connected to this paper. All such spaces will be considered here as potential
information spaces, and we intend to reduce or collapse them as much as
possible in the development of an information-feedback plan. This is perhaps
closer to the goals of machine learning, in which candidate representations
are determined through optimization of discrepancies with respect to input-
output data. In this paper, we in fact consider both model-free and model-
based ITSs, in alignment with the choices commonly found in machine learning
[2].

The robot’s ITS is coupled to the physical world, which is itself modeled as a
transition system. Note that the physical world model is not “given” to the
robot; we will formalize notions of “who gets what” information in Section 3.
The coupled system is inspired by neuroscience models (for example, [4]). Many
of the concepts in this paper build upon [12], in which we recently proposed
an enactivist-oriented model of cognition based on information spaces. By
enactivist [5], it is meant that the necessary brain structures emerge from
sensorimotor interaction and do not necessarily have predetermined, meaningful
components as in the classical representationalist sense.

Section 2 provides a mathematical formulation of robot-environment interaction
as transition systems. Section 3 develops notions of sufficiency and
minimality over the space of possible ITSs. Section 4 applies the general
concepts to address what it means to solve both passive (filtering) and active
(planning/control) tasks minimally and Section 5 provides simple examples.

##  2 Mathematical Models of Robot-Environment Systems

####  2.0.1 Internal and external systems

In this paper, we will consider a robot embedded in an environment and
describe this system as two subsystems, named internal and external, connected
through symmetric input-output relations. External refers to the system
describing the physical world, and internal is the complement of it. This
interaction is shown in Figure 1(b). In this sense, the states of the external
and internal systems are similar to the use of the term in control theory and
computer science, respectively.

External system corresponds to the totality of the environment and the robot
body within it. Let $X$ denote the set of states of this system; a state could
be for example, the configuration of the robot in a known environment (or
within a set of possible environments) or its phase. There are no restrictions
on $X$; it may be discrete, an $n$-dimensional manifold, a function space, and
so on. Next, let $U$ be the set of control inputs (also referred to as
actions) such that when applied at state $x\in X$ causes it to change
according to a state transition function $f:X\times U\rightarrow X$. The set
$U$ can also be anything: a finite or infinite discrete set, a compact or non-
compact manifold, and so on. Similarly, at each state $x$, $y=h(x)$ is the
output in which $h:X\rightarrow Y$ is a state-based sensor mapping and $Y$ is
the set of all possible observations.

The internal system (robot’s brain) observes the external system through a
sensor mapping and interacts with it through a selection of actions with
respect to a policy (alternatively, we can call it a plan or a strategy).
Therefore, the input to the internal system is an observation and its output
is an action. The states of this system correspond to the retained information
gathered through the outcomes of actions in terms of sensor observations. To
this end, the basis of our mathematical formulation of the internal is the
notion of __information space_ (I-space)_ [8]. We will use the term
__information state_ (I-state)_ to refer to the state of the internal system
and denote it with ${\iota}$, and ${\cal I}$ will denote the set of all
I-states, that is, the _I-space_. Note that the notions I-space and I-state
are not exclusive to the internal system and we will use them in a more
general setting in the following sections. Similar to the external system, the
internal system evolves with each $y\in Y$ according to the information
transition function $\phi:{\cal I}\times Y\rightarrow{\cal I}$. The output
then corresponds to the control command given by an information feedback
policy $\pi:{\cal I}\rightarrow U$.

Finally, we can write the coupled dynamical system composed of these two
subsystems defined as external and internal as

$\displaystyle\centering x^{\prime}\@add@centering$
$\displaystyle=f(x,\pi({\iota}))$ $\displaystyle y=$ $\displaystyle h(x)$
$\displaystyle{\iota}^{\prime}$ $\displaystyle=\phi({\iota},h(x))$
$\displaystyle u=$ $\displaystyle\pi({\iota}).$ (1)

Whereas the equations on the left side describe the evolution of this coupled
system, the ones on the right show the respective outputs of each subsystem.
Given an initial state $(x_{1},{\iota}_{1})\in X\times{\cal I}$, there exists
a unique state-trajectory.

Suppose the system evolves in discrete stages. For the external system,
starting from an initial state $x_{1}$, each stage $k$ corresponds to applying
an action $u_{k}$ which then yields the next stage $k+1$ and the next state
$x_{k+1}=f(x_{k},u_{k})$. As the system evolves through stages,
${\tilde{x}}_{k}=(x_{1},x_{2},\dots,x_{k})$,
${\tilde{u}}_{k-1}=(u_{1},u_{2},\dots,u_{k-1})$,
${\tilde{y}}_{k}=(y_{1},y_{2},\dots,y_{k})$, correspond to the state, action
and observation histories up to stage $k$, respectively. Note that applying
the action $u_{k}$ at stage $k$ would result in a transition to state
$x_{k+1}$ and the corresponding sensor reading $y_{k+1}=h(x_{k+1})$. The same
applies for the internal system, we can describe its evolution, starting from
an initial I-state ${\iota}_{0}$ following the state transition equation
${\iota}_{k}=\phi({\iota}_{k-1},y_{k})$. At stage $k$, $\pi({\iota}_{k})$
would produce the action $u_{k}$. Note that the stage index of the I-state
starts from $0$, this corresponds to any prior information the internal system
might have regarding the external; ${\iota}_{1}$ is then obtained using
${\iota}_{0}$ and $y_{1}$. Furthermore, $\pi({\iota}_{0})=u_{0}=()$ for all
policies $\pi$, meaning that no action is outputted at this stage.

####  2.0.2 Generalizing to transition systems

Without loss of generality, we can describe the internal and external
subsystems as transition systems of the form $(S,\Lambda,T)$ in which $S$ is
the set of states, $\Lambda$ is the set of names for the outgoing transitions,
and $T\subset S\times\Lambda\times S$ is a ternary relation describing the
transitions. If for each $(s,\lambda)\in S\times\Lambda$ there is a unique
$s^{\prime}\in S$ such that $(s,\lambda,s^{\prime})\in T$, then we will write
this system as $(S,\Lambda,\tau)$ in which $\tau:S\times\Lambda\rightarrow S$
is a function, and call the system an automaton. This corresponds to a
deterministic system. Note that our definition of an automaton differs from
the one usually used in computer science in the sense that ours do not
necessarily have a start state and a set of accepting states, and it is not
necessarily finite. Suppose ${\cal T}:S\times\Lambda\rightarrow{\rm pow}(S)$,
in which ${\rm pow}(\cdot)$ denotes the power set. Then, the transition system
$(S,\Lambda,{\cal T})$ is a nondeterministic automaton.

In [12], we have used the notion of state-relabeled transition systems to
model the internal and external systems. A state-relabeled transition system
is the quintuple $(S,\Lambda,T,\sigma,L)$ in which $\sigma:S\rightarrow L$ is
a labeling function and $(S,\Lambda,T)$ is a transition system. Preimages of a
labeling function $\sigma$ induce a partitioning of the state space $S$. Let
$S/\sigma$ be the set of equivalence classes $[s]_{\sigma}$ induced by
$\sigma$ such that $S/\sigma=\\{[s]_{\sigma}\mid s\in S\\}$ and
$[s]_{\sigma}=\\{s^{\prime}\in S\mid\sigma(s^{\prime})=\sigma(s)\\}$. Then, we
can define a new transition system $(S/\sigma,\Lambda,T/\sigma)$ called the
_quotient_ of $(S,\Lambda,T)$ by $\sigma$, in which
$T/\sigma=\\{\left([s]_{\sigma},\lambda,[s^{\prime}]_{\sigma}\right)\mid(s,\lambda,s^{\prime})\in
T\\}$. Note that $(S/\sigma,\Lambda,T/\sigma)$ is a reduced version of
$(S,\Lambda,T)$. We might be interested in finding a labeling function
$\sigma$ such that the corresponding quotient transition system is as simple
as possible while ensuring that it is still useful. In the following sections,
we will provide motivations for a reduction and discuss in more detail the
requirements on $\sigma$ for the quotient system to be useful.

Considering the deterministic case and the description of an automaton given
above, external and internal systems can be written as state-relabeled
automata $(X,U,f,h,Y)$ and $({\cal I},Y,\phi,\pi,U)$, respectively, in which
$h$ and $\pi$ are considered as labeling functions. Interpreting the labels as
the output of a transition system, coupled internal-external system can be
described in terms of the state-relabeled transition systems formulation too
such that output of one transition system is an input for another. Described
this way, coupling of two transition systems result in unique paths in either
automaton initialized at a particular state.

##  3 Sufficient Information Transition Systems

###  3.1 Information transition systems

In the general setting, an I-state corresponds to the available (stored)
information at a certain stage with respect to the action and observation
histories. Consequently, an I-space refers to the collection of all possible
I-states. We will use the term __information transition system_ (ITS)_ to
refer to a transition system whose state space is an I-space. We have already
used the notion of I-space while modeling the internal system representing the
robot brain, which makes it an ITS. Here, we extend the notion of an ITS to
include different perspectives from which the external and the coupled system
is viewed. In particular, we identified three perspectives corresponding to 1)
a plan executor which corresponds to the robot brain 2) a planner, and 3) an
(independent) observer. With a slight abuse of previously introduced notation
and terminology, we will use the term “internal” to refer to any system that
is not the external and we will use ${\cal I}$ to denote a generic I-space. We
describe an ITS in a robot-centric way such that an observation will refer to
a sensor-reading, that is, $y$. However, an independent observer defined over
the coupled system can observe, at stage $k$, both the action taken $u_{k-1}$
and the corresponding sensor-reading $y_{k}$.

Recall that the information regarding the external is obtained through the
sensor-mapping and any potential prior knowledge. Suppose that no policy is
fixed over the I-space. Then, the corresponding internal system can be modeled
as an ITS of the form $({\cal I},U\times Y,\phi$), in which $\phi:{\cal
I}\times(U\times Y)\rightarrow{\cal I}$ is a state (information) transition
function, if it is deterministic. We will then use the term _deterministic
information transition system_ (DITS) to refer to them. Otherwise, it is
called a _nondeterministic information transition system_ (NITS) and described
as $({\cal I},U\times Y,\Phi)$, in which $\Phi\subseteq{\cal I}\times(U\times
Y)\times{\cal I}$ is the transition relation. This formulation corresponds to
the perspectives other than the plan executor such that it is possible to take
any action from an I-state as it is not constrained by a policy, hence the
outgoing transitions are determined by the elements of $U\times Y$.

A plan executor corresponds to the internal system (robot’s brain) described
in the previous section. The only information regarding the external is gained
through manipulating the state of the external system through actions and
obtaining the corresponding sensor readings. Recall the representation used in
the previous section, that is, $({\cal I},Y,\phi)$, and $\pi:{\cal
I}\rightarrow U$ a labeling function. This can be considered as a constrained
version of the DITS described in the previous paragraph such that the
transitions are restricted to those that can be realized under $\pi$. To show
that, we augment the definition of internal system corresponding to the robot
brain such that the transitions now also correspond to labels. Let $({\cal
I},U\times Y,\Phi)$ be the augmented transition system describing the internal
such that

$\Phi=\\{({\iota},(u,y),{\iota}^{\prime})\in{\cal I}\times(U\times
Y)\times{\cal I}\mid u=\pi({\iota})\land{\iota}^{\prime}=\phi({\iota},y)\\},$
(2)

by construction, this augmented ITS is also deterministic111We could use the
same approach for the external system too. In that case, let $(X,Y\times U,F)$
be this augmented transition system corresponding to the external, in which
$F$ is the set of transitions such that $F=\\{(x,(y,u),x^{\prime})\in
X\times(Y\times U)\times X\mid y=h(x)\land x^{\prime}=f(x,u)\\}$. Further
creating bipartite graphs (for either system) such that transitions from a
state correspond either to an observation $y\in Y$ or to an action $u\in U$
allows us to describe the coupling as a form of intersecting two automata.
However, because it is not central to this paper we will not elaborate on this
topic.. Suppose $({\cal I},U\times Y,\Phi^{\prime})$ is the DITS that is not
constrained by a policy. Then, $\Phi\subseteq\Phi^{\prime}$.

###  3.2 History information spaces

An I-space constitutes the state space of an ITS. Therefore, we describe the
basic I-space named _history I-space_ denoted as ${\cal I}_{hist}$. It will be
used to derive other I-spaces as well. A _history I-state_ at stage $k$
corresponds to all the information that is gathered through sensing (and
potentially also through actions) up to stage $k$ assuming perfect memory. Let
${\eta}_{k}$ denote the history I-state at stage $k$, that is
${\eta}_{k}=({\eta}_{0},{\tilde{u}}_{k-1},{\tilde{y}}_{k})$, in which
${\eta}_{0}$ is the initial condition. Recall that ${\tilde{u}}_{0}$ is
assumed to be the null-tuple, hence, ${\tilde{u}}_{k}$ starts with $u_{1}$ for
any $k>1$.

Let ${\cal I}_{0}$ be the set of initial conditions whose description varies
with the available prior information. We defer the descriptions of possible
${\cal I}_{0}$ to the following paragraph. The history information space at
stage $k$ is expressed as ${\cal I}_{k}={\cal
I}_{0}\times{\tilde{U}}_{k-1}\times{\tilde{Y}}_{k}$. In general, the number of
stages that the system will go through is not fixed. Therefore, we can define
history I-space as the union over all $k\in\mathbb{N}$, that is, ${\cal
I}_{hist}=\bigcup_{k\in\mathbb{N}}{\cal I}_{k}$. The DITS corresponding to
${\cal I}_{hist}$ becomes $({\cal I}_{hist},U\times Y,{\phi_{hist}})$, in
which

${\eta}_{k}={\phi_{hist}}({\eta}_{k-1},u_{k-1},y_{k})={\eta}_{k-1}{}^{\frown}u_{k-1}{}^{\frown}y_{k}$

and ⌢ is the concatenation operation that adds an element at the end of a
sequence.

We consider two categories of initial conditions depending on whether
information regarding the state space $X$ of the external system is available
or not. Suppose $X$ or any information regarding $X$ is not given. Then, an
I-state at stage $k$ simply is
${\eta}_{k}=({\tilde{u}}_{k-1},{\tilde{y}}_{k})$, that is, the concatenation
of action and observation histories up till stage $k$. We call this type of
history I-space, the _model-free history I-space_, and respectively call the
corresponding ITS, _model-free history ITS_. In this case, we can treat
${\eta}_{0}$ as ${\eta}_{0}=()$. Thus, ${\cal I}_{0}=\\{()\\}$. For the second
category of initial conditions, full or partial information regarding $X$,
against which the actions and observations can be interpreted, is given. We
will then use the terms _model-based history I-space_ and _model-based history
ITS_ to refer to the respective I-space and ITS. The initial condition
${\eta}_{0}$ could be (i) a known state $x_{1}\in X$ such that ${\cal
I}_{0}=X$, (ii) a set of possible initial states $X_{1}\subset X$ such that
${\cal I}_{0}={\rm pow}(X)$ or (iii) a probability distribution $P(x_{1})$
over $X$ such that ${\cal I}_{0}\subseteq\mathcal{P}(X)$, in which
$\mathcal{P}(X)$ is the set of all probability distributions over $X$.

###  3.3 Sufficient state-relabeling

In [12] we have introduced a notion of _sufficiency_ that substantially
generalizes the definition in Chapter 11 of [8] and is presented here for
completeness.

######  Definition 3.1 (Sufficient state-relabeling).

Let $(S,\Lambda,T)$ be a transition system. A labeling function
$\sigma:S\rightarrow L$ defined over the states of a transition system is
sufficient if and only if for all $s,q,s^{\prime},q^{\prime}\in S$ and all
$\lambda\in\Lambda$, the following implication holds:

$\sigma(s)=\sigma(q)\land(s,\lambda,s^{\prime})\in
T\land(q,\lambda,q^{\prime})\in
T\implies\sigma(s^{\prime})=\sigma(q^{\prime}).$

If $\sigma$ is defined over the states of an automaton $(S,\Lambda,\tau)$,
then $\sigma$ is sufficient iff for all $s,q\in S$ and all
$\lambda\in\Lambda$, $\sigma(s)=\sigma(q)$ implies that
$\sigma(\tau(s,\lambda))=\sigma(\tau(q,\lambda))$.

Consider the stage-based evolution of external system $(X,U,f,h,Y)$ with
respect to the action (control input) sequence
${\tilde{u}}_{k-1}=(u_{1},\dots,u_{k-1})$. This corresponds to the state and
observation histories till stage $k$, that are
${\tilde{x}}_{k}=(x_{1},\dots,x_{k})$ and
${\tilde{y}}_{k}=(y_{1},\dots,y_{k})$. Recall that applying $u_{k}$ at stage
$k$ would result in a transition to $x_{k+1}$ and the corresponding
observation $y_{k+1}=h(x_{k+1})$. Hence, in this context, sufficiency of $h$
implies that given the label $y_{k}=h(x_{k})$ and the action $u_{k}$, it is
possible to determine the label $y_{k+1}=h(x_{k+1})$. One interpretation of
sufficiency of $h$ is that the respective quotient system sufficiently
represents the underlying system up to the induced equivalence classes. This
notion is similar to minimal realization of a system, that is, the minimal
state space description that models the given input-output measurements (see
for example [7]). Second interpretation is in a predictive sense. Suppose the
quotient system is known. Then, the label $y_{k+1}=h(x_{k+1})$ can be
determined before the system gets to $x_{k+1}$, using the current label
$y_{k}$ and the action to be applied $u_{k}$. Furthermore, under a fixed
policy, complete observation-trajectory can be determined from the initial
observation by induction.

Now, consider an internal system with a labeling function ${\kappa}:{\cal
I}\rightarrow{\cal I}^{\prime}$, that is, $({\cal I},U\times
Y,\phi,\kappa,{\cal I}^{\prime})$, and its evolution with respect to the
observation history $\tilde{y}=(y_{1},\dots,y_{k})$. At stage $k$, the state
of the automaton is ${\iota}_{k}$ and with $(u_{k},y_{k+1})$ the system
transitions to ${\iota}_{k+1}=\phi({\iota}_{k},u_{k},y_{k+1})$. Sufficiency of
${\kappa}$ implies that given ${\kappa}({\iota}_{k})$, $u_{k}$, and $y_{k+1}$,
we can determine ${\kappa}({\iota}_{k+1})$. This is equivalent to the
definition introduced in Chapter 11 of [8] and makes it a special case for
Definition 3.1.

###  3.4 Derived information transition systems

Even though it seems natural to rely on a history ITS, dimension of a history
I-space increases linearly with each stage, making it impractical in most
cases. Thus, we are interested in defining a reduced ITS that is more
manageable.Furthermore, this would largely simplify the description of a
policy for a planner or a plan executor.

Recall the quotient of a transition system by a a labeling function. We
rewrite $({\cal I}_{hist},U\times Y,\phi_{hist})$ as $({\cal I}_{hist},U\times
Y,\Phi_{hist})$, in which

$\Phi_{hist}=\\{({\eta},(u,y),\phi_{hist}({\eta},u,y))\in{\cal
I}_{hist}\times(U\times Y)\times{\cal I}_{hist}\\}.$ (3)

We can introduce an _information mapping_ (I-map) ${\kappa}:{\cal
I}_{hist}\rightarrow{\cal I}_{der}$ that categorizes the states of ${\cal
I}_{hist}$ into equivalence classes through its preimages. In this case,
${\kappa}$ serves as a labeling function and a reduction can be obtained in
terms of the quotient of $({\cal I}_{hist},U\times Y,\Phi)$ by ${\kappa}$,
that is, $({\cal I}_{hist}/{\kappa},U\times Y,\Phi/{\kappa})$.

It is crucial that the derived ITS is a DITS so that the labels can be
determined using only the derived ITS without making reference to the history
ITS.Considering the quotient system derived from $({\cal I}_{hist},U\times
Y,\phi)$, which is a DITS by definition, by ${\kappa}$, we can not always
guarantee that the resulting ITS is deterministic. This depends on the I-map
used for state-relabeling as stated in the following proposition.

######  Proposition 3.2.

For all non-empty $U$ and $Y$, and for the corresponding ${\cal I}_{hist}$,
there exists a labeling function ${\kappa}$ such that the quotient of $({\cal
I}_{hist},U\times Y,\phi)$ by $\kappa$, that is, $({\cal
I}_{hist}/{\kappa},U\times Y,\Phi/{\kappa})$, in which $\Phi$ is defined as in
(3), is not a DITS.

######  Proof 3.3.

Let ${\kappa}:{\cal I}_{hist}\rightarrow\\{l_{1},l_{2}\\}$ such that
${\kappa}^{-1}(l_{1})=\\{{\eta}_{k}=({\tilde{u}}_{k-1},{\tilde{y}}_{k})\in{\cal
I}_{hist}\mid{\tilde{u}}_{k-1}=(u_{i})_{i=1,\dots,k-1},u_{i}=u,\forall
i=1,\dots,k-1\\}$ is the set of histories that correspond to applying the same
action for $k-1$ times and ${\kappa}^{-1}(l_{2})$ is its complement, that is,
${\kappa}^{-1}(l_{2})={\cal I}_{hist}\setminus{\kappa}^{-1}(l_{1})$. Then,
there exist sequences ${\eta}_{k-2}=({\tilde{u}}_{k-3},{\tilde{y}}_{k-2})$ and
${\eta}_{k-1}=({\tilde{u}}_{k-2},{\tilde{y}}_{k-1})$ such that
${\eta}_{k-2}={\eta}_{k-1}{}^{\frown}(u,y)$ and
${\eta}_{k}={\eta}_{k-1}{}^{\frown}(u,y)$ for which
${\kappa}({\eta}_{k-2})={\kappa}({\eta}_{k-1})=l_{2}$ and
${\kappa}({\eta}_{k})=l_{1}$. Thus,

$\\{([{\eta}_{k-2}]_{\kappa},(u,y),[{\eta}_{k-1}]_{\kappa}),([{\eta}_{k-1}]_{\kappa},(u,y),[{\eta}_{k}]_{\kappa})\\}\in\Phi/{\kappa}.$

Since $[{\eta}_{k-2}]_{\kappa}=[{\eta}_{k-1}]_{\kappa}$ and
$[{\eta}_{k-1}]_{\kappa}\neq[{\eta}_{k}]_{\kappa}$, the transition
corresponding to $([{\eta}_{k-1}]_{\kappa},(u,y))$ is not unique; thus,
$({\cal I}_{hist}/{\kappa},U\times Y,\Phi/{\kappa})$ is not deterministic.∎

Note that Proposition 3.2 holds also in the case of a generic ITS $({\cal
I},U\times Y,\phi)$, with non-history I-states, if $\exists
s,s^{\prime},q,q^{\prime}\in{\cal I}$ such that
$\\{(s,(u,y),s^{\prime}),(q,(u,y),q^{\prime})\\}\in\Phi$, in which $\Phi$ is
defined using $\phi$ as in (3). Then, any I-map ${\kappa}$ such that
${\kappa}(s)={\kappa}(q)$ and ${\kappa}(s^{\prime})\neq{\kappa}(q^{\prime})$
results in a quotient system that is not a DITS.

For the quotient system derived from $({\cal I}_{hist},U\times Y,\phi)$ to be
a DITS depends on the sufficiency of ${\kappa}$. In [12] it is shown that the
quotient of a transition system $(S,\Lambda,T)$ by a labeling function
$\sigma$ is an automaton (recall our definition) if and only if
$(S,\Lambda,T)$ is full222A transition system $(S,\Lambda,T)$ is full, if
$\forall s\in S,\lambda\in\Lambda$ there exists at least one $s^{\prime}\in S$
with $(s,\lambda,s^{\prime})\in T$. and $\sigma$ is sufficient. As
$\phi_{hist}$ is a function with domain ${\cal I}_{hist}\times(U\times Y)$, it
is full, then, the following follows from [12] as a special case.

######  Proposition 3.4.

Let $({\cal I}_{hist}/{\kappa},U\times Y,\Phi_{hist}/{\kappa})$ be the
quotient of $({\cal I}_{hist},U\times Y,\phi_{hist})$ by ${\kappa}$, in which
$\Phi$ is defined as in (3), then $({\cal I}_{hist}/{\kappa},U\times
Y,\Phi/{\kappa})$ is a DITS if and only if ${\kappa}$ is sufficient.

For an I-map ${\kappa}:{\cal I}_{hist}\rightarrow{\cal I}_{der}$, $({\cal
I}_{hist}/{\kappa},U\times Y,\Phi_{hist}/{\kappa})$ is isomorphic to $({\cal
I}_{der},U\times Y,\Phi_{der})$, in which
$\Phi_{der}=\\{({\kappa}({\eta}),(u,y),{\kappa}({\eta}^{\prime}))\mid({\eta},(u,y),{\eta}^{\prime})\in\Phi_{hist}\\}$
[12]. Thus, we can use the labels introduced by ${\kappa}$ as the new
(derived) I-space and the corresponding quotient system as the derived ITS.
Suppose, ${\kappa}$ is sufficient. Then, the derived ITS is a DITS, meaning
that given the I-state ${\iota}_{k-1}\in{\cal I}_{der}$, and ($u_{k-1}$,
$y_{k}$), ${\iota}_{k+1}\in{\cal I}_{der}$ can be uniquely determined.
Consequently, we can write the derived ITS as $({\cal I}_{der},U\times
Y,\phi_{der})$ in which $\phi_{der}:{\cal I}_{der}\times(U\times
Y)\rightarrow{\cal I}_{der}$ is the new information transition function.
Therefore, we no longer need to rely on the full histories and the history ITS
and can rely solely on the derived ITS. This is shown in the first two rows of
the following diagram:

${{\cal I}_{hist}}$${{\cal I}_{hist}}$${{\cal I}_{hist}}$${{\cal
I}_{hist}}$${{\cal I}_{hist}}$ ${{\cal I}_{der}}$${{\cal I}_{der}}$${{\cal
I}_{der}}$${{\cal I}_{der}}$${{\cal I}_{der}}$ ${{\cal I}_{min}}$${{\cal
I}_{min}}$${{\cal I}_{min}}$${{\cal I}_{min}}$${{\cal I}_{min}}$ ${{\cal
I}_{task}}$${{\cal I}_{task}}$${{\cal I}_{task}}$${{\cal I}_{task}}$${{\cal
I}_{task}.}$$\scriptstyle{u_{1},y_{2}}$$\scriptstyle{{\kappa}}$$\scriptstyle{u_{2},y_{3}}$$\scriptstyle{{\kappa}}$$\scriptstyle{u_{3},y_{4}}$$\scriptstyle{{\kappa}}$$\scriptstyle{u_{4},y_{5}}$$\scriptstyle{{\kappa}}$$\scriptstyle{{\kappa}}$$\scriptstyle{u_{1},y_{2}}$$\scriptstyle{{\kappa}^{\prime}}$$\scriptstyle{u_{2},y_{3}}$$\scriptstyle{{\kappa}^{\prime}}$$\scriptstyle{u_{3},y_{4}}$$\scriptstyle{{\kappa}^{\prime}}$$\scriptstyle{u_{4},y_{5}}$$\scriptstyle{{\kappa}^{\prime}}$$\scriptstyle{{\kappa}^{\prime}}$$\scriptstyle{u_{1},y_{2}}$$\scriptstyle{{\kappa}^{\prime\prime}}$$\scriptstyle{u_{2},y_{3}}$$\scriptstyle{{\kappa}^{\prime\prime}}$$\scriptstyle{u_{3},y_{4}}$$\scriptstyle{{\kappa}^{\prime\prime}}$$\scriptstyle{u_{4},y_{5}}$$\scriptstyle{{\kappa}^{\prime\prime}}$$\scriptstyle{{\kappa}^{\prime\prime}}$
(4)

Note that we can similarly define an I-map that maps any derived I-space to
another. An example is given in (4) as the mappings ${\kappa}^{\prime}:{\cal
I}_{der}\rightarrow{\cal I}_{min}$ and ${\kappa}^{\prime\prime}:{\cal
I}_{min}\rightarrow{\cal I}_{task}$. The corresponding quotient system is
deterministic for ${\kappa}^{\prime}$, indicating that it is sufficient.
However, the quotient system by ${\kappa}^{\prime\prime}$ derived from ${\cal
I}_{min}$ is not deterministic, hence, ${\kappa}^{\prime\prime}$ is not
sufficient, as the next I-state can not be uniquely determined. Note that an
I-map whose domain is ${\cal I}_{hist}$ can also be defined as composition of
the mappings along the column of the diagram. For instance,
${\kappa}_{min}:{\cal I}_{hist}\rightarrow{\cal I}_{min}$ is the composition
of ${\kappa}$ and ${\kappa}^{\prime}$, that is,
${\kappa}_{min}={\kappa}^{\prime}\circ{\kappa}$ (same for
${\kappa_{task}}:{\cal I}_{hist}\rightarrow{\cal I}_{task}$).

###  3.5 Lattice of information transition systems

We fix ${\cal I}_{hist}$, which corresponds to fixing the set of initial
states ${\cal I}_{0}$. Then, each I-map ${\kappa}$ defined over ${\cal
I}_{hist}$ induces a partition of ${\cal I}_{hist}$ through its preimages,
denoted as ${\cal I}_{hist}/{\kappa}$. An I-map ${\kappa}^{\prime}$ is a
refinement of ${\kappa}$, denoted as ${\kappa}^{\prime}\succeq{\kappa}$, if
$\forall A\in{\cal I}_{hist}/{\kappa}^{\prime}$ there exists a $B\in{\cal
I}_{hist}/{\kappa}$ such that $A\subseteq B$. Let $K({\cal I}_{hist})$ denote
the set of all partitions over ${\cal I}_{hist}$. Refinement induces a partial
ordering since not all partitions of ${\cal I}_{hist}$ are comparable. The
partial ordering given by refinements form a lattice of partitions over ${\cal
I}_{hist}$, denoted as $(K({\cal I}_{hist}),\succeq)$.

At the top of the lattice, there is the partition induced by an identity I-map
(or equivalently, by a bijection), ${\kappa}_{id}:{\cal
I}_{hist}\rightarrow{\cal I}_{hist}$, since all of its elements are singletons
(all equivalence classes contain exactly one element), making it the maximally
distinguishable case. Conversely, we can define a constant mapping
${\kappa}_{const}:{\cal I}_{hist}\rightarrow{\cal I}_{const}$ for which ${\cal
I}_{hist}/{\kappa}_{const}$ is a singleton, that is, ${\cal
I}_{const}=\\{{\iota}_{const}\\}$, which then will be at the bottom of the
lattice. In turn, ${\kappa}_{const}$ yields the minimally distinguishable case
as all histories now belong to a single equivalence class. This idea is
similar to the notion of the _sensor lattice_ defined over the partitions of
$X$ [9, 13]. Indeed, if we take ${\cal I}_{0}=X$ and consider
${\kappa}_{est}:{\cal I}_{hist}\rightarrow X$, the ordering of partitions of
${\cal I}_{hist}$ such that ${\cal I}_{hist}/{\kappa}_{est}$ is the least
upper bound gives out the sensor lattice.

As motivated in previous sections, we are interested in finding a sufficient
I-map such that the quotient ITS derived from the history ITS is still
deterministic. Notice that the constant I-map ${\kappa}_{const}$ is sufficient
by definition since for all $(u,y)\in U\times Y$, and all
${\eta},{\eta}^{\prime}\in{\cal I}_{hist}$, we have that
${\kappa}_{const}({\eta})={\kappa}_{const}({\eta}^{\prime})$ and
${\kappa}_{const}(\phi_{hist}({\eta},(u,y))={\kappa}_{const}(\phi_{hist}({\eta}^{\prime},(u,y)).$
On the other hand, in certain cases it is crucial to differentiate certain
histories from the others. This will become clear in the next section when we
describe the notion of a task. Suppose ${\kappa}$ is a labeling that
partitions ${\cal I}_{hist}$ into equivalence classes that are of importance
and suppose that ${\kappa}$ is not sufficient. Then, we want to find a
refinement of ${\kappa}$ that is sufficient. This will serve as a lower bound
on the lattice of partitions over ${\cal I}_{hist}$ since for any partition
such that ${\cal I}_{hist}/{\kappa}$ is a refinement of it, the classes of
histories that are deemed crucial will not be distinguished. The following
defines the refinement of ${\kappa}$ that ensures sufficiency and a minimal
number of equivalence classes.

######  Definition 3.5.

Let $({\cal I}_{hist},U\times Y,{\phi_{hist}})$ be a history ITS and
${\kappa}$ an I-map. A _minimal sufficient refinement_ of ${\kappa}$ is a
sufficient I-map ${\kappa}^{\prime}$ such that there does not exist a
sufficient I-map ${\kappa}^{\prime\prime}$ that satisfy
${\kappa}^{\prime}\succ{\kappa}^{\prime\prime}\succeq{\kappa}$.

######  Remark 3.6.

It is shown in [12] that the minimal sufficient refinement of ${\kappa}$
defined over the states of an automaton $(S,\Lambda,\tau)$ is unique.

##  4 Solving Tasks Minimally

####  4.0.1 Definition of a task

We now connect the general ITS concepts to the accomplishment of particular
tasks. We have two categories: 1) active, which corresponds to planning and
executing an information-feedback policy that forces a desirable outcome in
the environment, and 2) passive, which means only to observe the environment
without being able to effect changes. Recall from Section 3.4 that there may
be model-free or model-based formulations. In the model-free case, tasks are
specified using a logical language over ${\cal I}_{hist}$ which will result in
a labeling and derived I-space ${\cal I}_{task}$ and associated I-map
${\kappa_{task}}$ that corresponds to the “resolution” at which the tasks are
specified. Various logics are allowable, such as propositional or a temporal
logic. The resulting sentences of the language involve combinations of
predicates that may assign true or false values to subsets of ${\cal
I}_{hist}$. Solving an active task (or tasks) requires that a sentence of
interest becomes true during execution of the policy. This is called
satisfiability. For example, the task may be to simply reach some goal set
$G\subset{\cal I}_{hist}$, causing a predicate in-goal$({\cal I}_{hist})$ to
become satisfied (in other words, be true). Using linear temporal logic, more
complex requirements, such as cycling through a finite sequence of subsets
forever while avoiding others, can be specified [3].

Solving a passive task only requires maintaining whether a sentence is
satisfied, rather than forcing an outcome; this corresponds to filtering.
Whether the task is active or passive, if satisfiability is concerned with a
single, fixed sentence, then a task-induced labeling (or task labeling for
short), that is, ${\kappa_{task}}$, over ${\cal I}_{hist}$ assigns two labels:
Those I-states that result in true and those that result in false. A task
labeling may also be assigned for a set of possible sentences by assigning a
label to each set of the common refinement of the partition of ${\cal
I}_{hist}$ induced by each possible sentence. In the model-based case, tasks
are instead specified using a language over $X$, and sentence satisfiability
must be determined by an I-map that converts history I-states into expressions
over $X$.

####  4.0.2 Problem families

It is assumed that the state-relabeled transition system $(X,U,f,h,Y)$
describing the external system is fixed, but it is unknown or partially known
to the observer (a robot or other observer).

Filtering (passive case) requires maintaining the label of an I-state
attributed by ${\kappa_{task}}$. Since ${\kappa_{task}}$ is not necessarily
sufficient, we can not guarantee that the quotient system by ${\kappa_{task}}$
is a DITS (Propositions 3.2 and 3.4). Thus, relying solely on the quotient
system by ${\kappa_{task}}$, we can not determine the class that the current
history belongs to (see the last row in (4)) and, hence can not determine
whether a sentence describing the task is satisfied (or which sentences are
satisfied).

Suppose the sets $U$ and $Y$ are specified, and at each stage $k$, $u_{k-1}$
is known and $y_{k}$ is observed. The following describes the problem for a
passive task given a state-relabeled (history) ITS $({\cal I}_{hist},U\times
Y,\phi_{hist},{\kappa_{task}},{\cal I}_{task})$, in which
${\kappa_{task}}:{\cal I}_{hist}\rightarrow{\cal I}_{task}$ is a task labeling
that is not sufficient, and ${\cal I}_{task}$ is the corresponding I-space.

######  Problem 4.1 (Find a sufficient I-space filter).

Find a sufficient refinement of ${\kappa_{task}}$.

Note that ${\cal I}_{hist}/{\kappa_{task}}$ determines a lower bound on the
partitioning of ${\cal I}_{hist}$ which is interpreted as the crucial
information that can not be lost. Consequently, histories belonging to
different equivalence classes with respect to ${\kappa_{task}}$ must always be
distinguished from each other. However, Problem 4.1 does not an upper bound.
At the limit, a bijection from ${\cal I}_{hist}$ is always a sufficient
refinement of ${\kappa_{task}}$. As stated previously, using history ITS can
create computational obstructions in solving problems. This motivates the
following problem.

######  Problem 4.2 (Filter minimization).

Find a minimal sufficient refinement of ${\kappa_{task}}$.

We now consider a basic planning problem, for which ${\cal
I}_{task}=\\{0,1\\}$, such that ${\kappa_{task}}^{-1}(1)\subset{\cal
I}_{hist}$ is the set of histories that achieve the goal, and
${\kappa_{task}}^{-1}(0)\subset{\cal I}_{hist}$ is its complement. Most
planning problems refer to finding a labeling function $\pi$ such that, when
used to label the states of the internal system, guarantees task
accomplishment. Then $\pi$ is called a feasible policy, which is defined in
the following. Consider an external system $(X,f,U,h,Y)$. Let
$\mathcal{R}_{X}({\cal I}_{task})\subseteq X$ be the set of initial states for
which there exist a $k$ and histories ${\tilde{x}}_{k}$, ${\tilde{u}}_{k-1}$,
and ${\tilde{y}}_{k}$, such that $x_{i+1}=f(x_{i},u_{i})$ and $y_{i}=h(x_{i})$
for all $0<i<k$, and ${\eta}_{k}\in{\kappa_{task}}^{-1}(1)$, in which
${\eta}_{k}$ is the history I-state corresponding to ${\tilde{u}}_{k-1}$ and
${\tilde{y}}_{k}$.

######  Definition 4.3 (Feasible policy for ${\cal I}_{task}$).

Let $({\cal I},Y,\phi,\pi,U)$ and $(X,f,U,h,Y)$ be the state-relabeled
transition systems corresponding to internal and external systems,
respectively. Labeling function $\pi$ defined over ${\cal I}$ is a feasible
policy for ${\cal I}_{task}$ if for all $x\in\mathcal{R}_{X}({\cal
I}_{task})$, the history corresponding to the coupled internal-external system
initialized at $({\iota}_{0},x)$ belongs to ${\kappa_{task}}^{-1}(1)$.

Most problems in the planning literature consider a fixed DITS and look for a
feasible policy for ${\cal I}_{task}$. This yields the following problem.
Typically, the I-space considered is $X$ which corresponds to state
estimation. Note that a DITS, in other words, the robot brain, can be seen as
an I-space filter itself.

######  Problem 4.4 (Find a feasible policy).

Given $({\cal I},Y,\phi)$, an internal system (robot brain), find a labeling
function $\pi:{\cal I}\rightarrow U$ that is a feasible policy for ${\cal
I}_{task}$.

We can further extend the planning problem to consider an unspecified internal
system which refers to finding a DITS, and a policy such that the resulting
histories satisfy the task description, that is, he problem of jointly finding
an I-space-filter and a policy defined over its states. Recall from (2) that a
policy constrains the transitions of an ITS to the ones that are realizable
under that policy.

######  Problem 4.5 (Find a DITS and a feasible policy).

Given $({\cal I}_{hist},U\times Y,\phi_{hist})$, for which
${\kappa_{task}}:{\cal I}_{hist}\rightarrow{\cal I}_{task}$ is a task labeling
and ${\cal I}_{task}$ is the corresponding I-space, find a sufficient I-map
${\kappa}:{\cal I}_{hist}\rightarrow{\cal I}$ and a feasible policy $\pi$ for
${\cal I}_{task}$ as a labeling function for the resulting quotient system by
${\kappa}$.

Note that ${\kappa_{task}}$ can already be sufficient, so that it is the
minimal sufficient refinement of itself, however, this does not necessarily
imply the existence of a feasible policy defined over ${\cal I}_{task}$.
Therefore, we are not looking for a refinement of ${\kappa_{task}}$ while
describing the DITS over which the policy is defined. On the other hand, we
can still talk about a notion of minimality. Let $({\cal I},Y,\phi,\pi,U)$ be
a state-relabeled DITS that solves Problem 4.5 (or similarly Problem 4.4)
which is the quotient system of history ITS by ${\kappa}$, then, $({\cal
I},Y,\phi,\pi,U)$ is _minimal for $\pi$_ if there does not exist a sufficient
I-map ${\kappa}^{\prime}$ with ${\kappa}\succ{\kappa}^{\prime}$ for which
there exists a $\pi^{\prime}$ for the quotient system by ${\kappa}^{\prime}$
that satisfies $\pi({\iota})=\pi^{\prime}({\kappa}^{\prime}({\iota}))$.

####  4.0.3 Learning a sufficient ITS

Although learning and planning overlap significantly, some unique issues arise
in pure learning (see also [12]). This corresponds to the case when ${\cal
I}_{task}$ is not initially given but needs to be revealed through
interactions with the external system, that is, respective action and
observation histories. It is assumed that whether the sentence (or sentences)
describing the task is satisfied or not can be assessed at a particular
history I-state.

We can address both filtering and planning problems defined previously within
this context, considering model-free and model-based cases. In the model-free
case, the task is to compute a minimal sufficient ITS that is consistent with
the actions and observations. Variations include lifelong learning, in which
there is a single, ‘long’ history I-state, or more standard learning in which
the system can be restarted, resulting in multiple trials, each yielding a
different history I-state. In the model-based case, partial specifications of
$X$, $f$, and $h$ may be given, and unknown parameters are estimated using the
history I-state(s). Different results are generally obtained depending on what
assumptions are allowed. For example, do identical history I-states imply
identical state trajectories? If not, then set-based, nondeterministic models
may be assumed, or even probabilistic models based on behavior observed over
many trials and assumptions on probability measure, priors, statistical
independence, and so on.

##  5 Illustrative Examples

In this section we provide some simple examples to show how the ideas
presented in this paper apply to filtering and planning problems. All problems
can be posed as well in a machine learning context for which ${\cal I}_{task}$
is not given but it is revealed through interactions between the internal and
external as the input-output data.

Figure 2: (a) State-relabeled history ITS described in Example 5.1, and
labeling function ${\kappa_{task}}$ yellow colored states correspond to states
that satisfy the task description. (b) Equivalence classes induced by
${\kappa}^{\prime}$; the minimal sufficient refinement of ${\kappa_{task}}$.
(c) Quotient of the history ITS by ${\kappa}^{\prime}$. (d)DITS describing the
internal system solving the planning problem described in Example 5.2. (e)
Environment used in Examples 5.1,5.2, the obstacle (an open disk) is shown in
black. (f) L-shaped corridor; $l_{1},l_{2}\leq l$.

Let $E\subseteq{\mathbb{R}}^{2}$ be a bounded planar environment (see Figure
2(e)) that is partitioned into regions separated by gates Each gate is either
green or red whose color can be detected by the robot’s color sensor and
follows the rule that each region shares a boundary with exactly two gates;
one green and one red. The set of possible observations are $Y=\\{r,g\\}$.

######  Example 5.1.

This example considers a filtering problem from the perspective of an
independent observer. Suppose the actions taken by the robot are not
observable and the only information about the system is the history of
readings coming from the robot’s color sensor; for example, $(r,r,r,g,r,g)$.
Then, the history I-space is the set of all finite length sequences of
elements of $Y$, that is, ${\cal I}_{hist}=Y^{*}$, which refers to the free
monoid generated by the elements of $Y$ (or the Kleene star of $Y$). Hence,
the history ITS can be represented as an infinite binary tree. The task is to
determine whether the robot crosses the gates consistently (in a clockwise or
counterclockwise manner) or not. Hence, the preimages of
${\kappa_{task}}:{\cal I}_{hist}\rightarrow{\cal I}_{task}$ partition ${\cal
I}_{hist}$ into two subsets: one which the condition is satisfied and the
others. The labeling induced by ${\kappa_{task}}$ is shown in Figure 2(a).
Clearly, ${\kappa_{task}}$ is not sufficient since there exist I-states
${\eta},{\eta}^{\prime}$ such that
${\kappa_{task}}({\eta})={\kappa_{task}}({\eta}^{\prime})$ and there exists a
$y$ for which
${\kappa_{task}}({\phi_{hist}}({\eta},y))\neq{\kappa_{task}}({\phi_{hist}}({\eta}^{\prime},y))$;
for example consider ${\eta}=(r,g)$, ${\eta}^{\prime}=(r,g,r)$ and $y=g$. A
sufficient refinement of ${\kappa_{task}}$ can be obtained (equivalence
classes shown in 2(b)), denote as ${\kappa}^{\prime}$, for which the quotient
DITS is shown in Figure 2(d). Furthermore, ${\kappa}^{\prime}$ is a minimal
sufficient refinement of ${\kappa_{task}}$ since it follows from Proposition
4.2 that if a labeling is not minimal then there is a minimal one that is
strictly coarser and is still sufficient. However, neither of the subsets that
belong to ${\cal I}_{hist}/{\kappa}^{\prime}$ can be merged, since merging
${\iota}_{nt}$ (colored gray) with anything else violates the condition that
${\kappa}^{\prime}$ is a refinement of ${\kappa_{task}}$ and any pairwise
merge of the others violate sufficiency.

Suppose the robot has a boundary detector, and executes a bouncing motion
using the two motion primitives $U=\\{u_{1},u_{2}\\}$, in which $u_{1}$ is
move forward and $u_{2}$ is rotate in place. Let a basic motion be move
forward and bounce off the walls, which can be implemented using the elements
of $U$. We assume that the boundary detector and color sensor readings do not
arrive simultaneously.

######  Example 5.2.

We now consider a planning problem (that belongs to the class described in
Problem 4.5) for which the goal is to ensure that the robot crosses the gates
consistently. The history I-space of the planner is ${\cal I}_{hist}=(U\times
Y)^{*}$ and the preimages of ${\kappa_{task}}$ partition ${\cal I}_{hist}$
into two sets; the histories that satisfy the predicate and the ones that do
not. Then, a DITS with only three states (see Figure 2(d)) can be derived
using the mapping ${\kappa}:{\cal I}_{hist}\rightarrow{\cal I}$, in which
${\cal I}=\\{i_{0},i_{1},i_{2}\\}$ such that for $\pi({\iota}_{1})$ boundary
with the red gate is set as a wall, $\pi({\iota}_{2})$ the boundary with the
green gate is set as a wall, and for $\pi({\iota}_{0})$ no boundary with gates
are considered as a wall. We assume that a bouncing motion can be determined
using the motion primitives so that the resulting trajectory will strike every
open interval in the boundary of every region infinitely often, with non-zero,
non-tangential velocities [1].

Consider a robot in an L-shaped planar corridor (Figure 2(f)). Let
$\mathcal{E}_{l}$ be the set of all such environments such that
$l_{1},l_{2}\leq l$, in which $l_{1}$ and $l_{2}$ are the dimensions of the
corridor bounded by $l$. We assume that the minimum length/width is larger
than the robot radius, that is, $1$. The state space $X$ is defined as the set
of all pairs $(q,E_{i})$, in which $(q_{1},q_{2})\in E_{i}$, and
$E_{i}\in\mathcal{E}_{l}$. The action set is $U=\\{0,1\\}\times\\{0,1\\}$
which corresponds to moving one step in one of the 4 cardinal directions; if
the boundary is reached, the state does not change. The robot has a sensor
that reports $1$ if the motion is blocked.

######  Example 5.3.

Consider a model-based history ITS with ${\eta}_{0}\subset X$ that specifies
the initial position as $q_{0}=(0,0)$ but does not specify the environment so
that it can be any $E_{i}\in{\cal{E}}_{l}$. Let ${\cal I}_{hist}$ be its set
of states and ${\kappa}_{ndet}:{\cal I}_{hist}\rightarrow{\rm pow}(X)$ be an
I-map that maps ${\eta}_{k}$ to a subset of $X_{k}\subseteq X$. Since
$(X,U,f,h,Y)$, and $X_{0}={\eta}_{0}$ are known, transitions for the quotient
system can be described by induction as
$X_{k+1}=\hat{X}_{k+1}(X_{k},u_{k})\cap H(y_{k+1})$, in which
$\hat{X}_{k+1}=\bigcup_{x_{k}\in X_{k}}f(x_{k},u_{k})$ and
$H(y_{k+1})\subseteq X$ is the set of all states that could yield $y_{k+1}$.
By construction, ${\kappa}_{ndet}$ is sufficient. Suppose
${\kappa_{task}}:{\cal I}_{hist}/{\kappa}_{ndet}\rightarrow{\cal I}_{task}$ is
a task labeling for localization that assigns each singleton a unique label
and all the other subsets are labeled the same. Since the transition
corresponding to $([X^{\prime}]_{{\kappa_{task}}},(u,y))$ in which
$X^{\prime}\subseteq X$ is not a singleton can lead to multiple labels
$[x^{\prime}]_{\kappa_{task}}$, in which $x^{\prime}$ is a singleton,
${\kappa_{task}}$ is not sufficient. Furthermore, ${\kappa}_{ndet}$ is a
minimal sufficient refinement of ${\kappa_{task}}$ because it is sufficient
and because there does not exist a sufficient ${\kappa}$ such that
${\kappa}_{ndet}\succ{\kappa}\succeq{\kappa_{task}}$. Suppose ${\kappa}$
exists, that would mean some equivalence classes can be merged. However, this
is not possible because merging any of the non-singleton subsets violates
sufficiency (as shown for ${\kappa_{task}}$) and merging singletons with
others violates that it is a refinement. A policy can be described over ${\cal
I}_{hist}/{\kappa}_{ndet}$; $u=(1,0)$ starting from $X_{0}$ until $y_{k}=1$ is
obtained and applying $u=(0,1)$ starting from $X_{k}$ until $y_{n}=1$ is
obtained, then it is found that $q=(k,n)$ and $E$ is the corridor with
$l_{1}=k$, $l_{2}=n$.

##  6 Discussion

We have introduced a mathematical framework for determining minimal feasible
policies for robot systems, by comparing ITSs over I-spaces. The uniqueness
and minimality results are quite general: $X$ and $U$ could be discrete,
typical configuration spaces, or more exotic, such as the power set of all
functions from an infinite-dimensional Hilbert space into an infinite-
dimensional Banach space.

Nevertheless, there are opportunities to expand the general theory. For
example, we assumed that $u$ is both the output of a policy and the actuation
stimulus in the physical world; more generally, we should introduce a mapping
from an action symbol $\sigma\in\Sigma$ to a control function
${\tilde{u}}\in{\tilde{U}}$ so that plans are expressed as $\pi:{\cal
I}\rightarrow\Sigma$ and each $\sigma=\pi(\iota)$ produces energy in the
physical world via a mapping from $\Sigma$ to ${\tilde{U}}$. Another extension
is to consider stochastic models, that amounts to an ITS with a probabilistic
I-space, and in which ways it ties to the representations used in the
literature such as _predictive state representations_ (PSRs) [10]. Other
potential extensions include continuous-time “transitions” and novel logics to
consider satisfiability questions over spaces of robot systems and tasks. An
interesting direction is to consider the hardware and actuation models are
variables, and fix other model components.

A grand challenge remains: The results here are only a first step toward
producing a more complete and unique theory of robotics that clearly
characterizes the relationships between common tasks, robot systems,
environments, and algorithms that perform filtering, planning, or learning. We
should search for lattice structures that play a role similar to that of
language class hierarchies in the theory of computation. This includes the
structures of the current paper and the sensor lattices of [9, 13]. Many
existing filtering, planning, and learning methods can be formally
characterized within this framework, which would provide insights into
relative complexity, completeness, minimality, and time/space/energy
tradeoffs.

## References

  * [1] L. Bobadilla, O. Sanchez, J. Czarnowski, K. Gossman, and S. M. LaValle.  Controlling wild bodies using linear temporal logic.  In Proceedings Robotics: Science and Systems, 2011.
  * [2] Axel Brunnbauer, Luigi Berducci, Andreas Brandstätter, Mathias Lechner, Ramin M. Hasani, Daniela Rus, and Radu Grosu.  Latent imagination facilitates zero-shot transfer in autonomous racing.  https://arxiv.org/abs/2103.04909v2.
  * [3] G. E. Fainekos, A. Girard, H. Kress-Gazit, and G. J. Pappas.  Temporal logic motion planning for dynamic mobile robots.  Automatica, 45(2):343–352, 2009.
  * [4] K. Friston.  The free-energy principle: A unified brain theory?  Nature Reviews Neuroscience, 11(2):127–138, 2010.
  * [5] D. D. Hutto and E. Myin.  Radicalizing enactivism: Basic minds without content.  MIT Press, 2012.
  * [6] D. E. Koditschek.  What is robotics? Why do we need it and how can we get it?  Annual Review of Control, Robotics, and Autonomous Systems, 4:1–33, May 2021.
  * [7] Ü. Kotta, C. H. Moog, and M. Tõnso.  Minimal realizations of nonlinear systems.  Automatica, 95:207–212, 2018.
  * [8] S. M. LaValle.  Planning Algorithms.  Cambridge University Press, Cambridge, U.K., 2006.  Also available at http://lavalle.pl/planning/.
  * [9] S. M. LaValle.  Sensing and Filtering: A Fresh Perspective Based on Preimages and Information Spaces, volume 1:4 of Foundations and Trends in Robotics Series.  Now Publishers, Delft, The Netherlands, 2012.
  * [10] Michael Littman and Richard S Sutton.  Predictive representations of state.  Advances in neural information processing systems, 14, 2001.
  * [11] J. M. O’Kane and D. A. Shell.  Concise planning and filtering: Hardness and algorithms.  IEEE Transactions on Automation Science and Engineering, 14(4):1666–1681, 2017.
  * [12] V. Weinstein, B. Sakcak, and S. M. LaValle.  An enactivist-inspired mathematical model of cognition.  under review, 2022.
  * [13] Y. Zhang and D. A. Shell.  Lattices of sensors reconsidered when less information is preferred.  In IEEE International Conference on Robotics and Automation, 2021\.

  *[I-space]: information space
  *[I-state]: information state
  *[ITS]: information transition system
  *[DITS]: deterministic information transition system
  *[NITS]: nondeterministic information transition system
  *[ I-space]: information space
  *[ I-state]: information state
  *[ ITS]: information transition system
  *[I-map]: information mapping
  *[PSRs]: predictive state representations