Agents are situated in time; they receive sensory data in time and do actions in time. The action that an agent does at a particular time is a function of its inputs. We first consider the notion of time.

Let $T$ be the set of time points. Assume that $T$ is totally ordered and has some metric that can be used to measure the temporal distance between any two time points. Basically, we assume that $T$ can be mapped to some subset of the real line.

$T$ is discrete if there are only a finite number of time points between any two time points; for example, there is a time point every hundredth of a second, or every day, or there may be time points whenever interesting events occur. $T$ is dense if there is always another time point between any two time points; this implies there must be infinitely many time points between any two points. Discrete time has the property that, for all times, except perhaps a last time, there is always a next time. Dense time does not have a “next time.” Initially, we assume that time is discrete and goes on forever. Thus, for each time there is a next time. We write $t+1$ as the next time after time $t$. The time points do not need to be equally spaced.

Assume that $T$ has a starting point, which we arbitrarily call $0$.

Suppose $P$ is the set of all possible percepts. A percept trace, or percept stream, is a function from $T$ into $P$. It specifies what is observed at each time.

Suppose $C$ is the set of all commands. A command trace is a function from $T$ into $C$. It specifies the command for each time point.

A percept trace for an agent is thus the sequence of all past, present, and future percepts received by the controller. A command trace is the sequence of all past, present, and future commands issued by the controller. The commands can be a function of the history of percepts. This gives rise to the concept of a transduction, a function from percept traces into command traces.

Because all agents are situated in time, an agent cannot actually observe full percept traces; at any time it has only experienced the part of the trace up to now. At time $t\in T$, an agent can only observe the value of the trace up to time $t$, and its commands cannot depend on percepts after time $t$.

A transduction is causal if, for all times $t$, the command at time $t$ depends only on percepts up to and including time $t$. The causality restriction is needed because agents are situated in time; their command at any time cannot depend on future percepts.

A controller is an implementation of a causal transduction.

The history of an agent at time $t$ is the percept trace of the agent for all times before or at time $t$ and the command trace of the agent before time $t$.

Thus, a causal transduction maps the agent’s history at time $t$ into the command at time $t$. It can be seen as the most general specification of a controller.

Although a causal transduction is a function of an agent’s history, it cannot be directly implemented because an agent does not have direct access to its entire history. It has access only to its current percepts and what it has remembered.

The memory or belief state of an agent at time $t$ is all the information the agent has remembered from the previous times. An agent has access only to the history that it has encoded in its belief state. Thus, the belief state encapsulates all of the information about its history that the agent can use for current and future commands. At any time, an agent has access to its belief state and its current percepts.

The belief state can contain any information, subject to the agent’s memory and processing limitations. This is a very general notion of belief.

Some instances of belief state include the following:

• •

  The belief state for an agent that is following a fixed sequence of instructions may be a program counter that records its current position in the sequence.

• •

  The belief state can contain specific facts that are useful – for example, where the delivery robot left a parcel when it went to find a key, or where it has already checked for the key. It may be useful for the agent to remember any information that it might need for the future that is reasonably stable and that cannot be immediately observed.

• •

  The belief state could encode a model or a partial model of the state of the world. An agent could maintain its best guess about the current state of the world or could have a probability distribution over possible world states; see Section 8.5.2.

• •

  The belief state could be a representation of the dynamics of the world – how the world changes – and the meaning of its percepts. Given its percepts, the agent could reason about what is true in the world.

• •

  The belief state could encode what the agent desires, the goals it still has to achieve, its beliefs about the state of the world, and its intentions, or the steps it intends to take to achieve its goals. These can be maintained as the agent acts and observes the world, for example, removing achieved goals and replacing intentions when more appropriate steps are found.

A controller maintains the agent’s belief state and determine what command to issue at each time. The information it has available when it must do this are its belief state and its current percepts.

A belief state transition function for discrete time is a function

where $S$ is the set of belief states and $P$ is the set of possible percepts; $s_{t+1}=\text{remember}(s_t,p_t)$ means that $s_{t+1}$ is the belief state following belief state $s_t$ when $p_t$ is observed.

A command function is a function

where $S$ is the set of belief states, $P$ is the set of possible percepts, and $C$ is the set of possible commands; $c_t=\text{command}(s_t,p_t)$ means that the controller issues command $c_t$ when the belief state is $s_t$ and when $p_t$ is observed.

The belief-state transition function and the command function together specify a causal transduction for the agent. Note that a causal transduction is a function of the agent’s history, which the agent does not necessarily have access to, but a command function is a function of the agent’s belief state and percepts, which it does have access to.

If there are a finite number of possible belief states, the controller is called a finite state controller or a finite state machine. A factored representation is one in which the belief states, percepts, or commands are defined by features. If there are a finite number of features, and each feature can only have a finite number of possible values, the controller is a factored finite state machine. Richer controllers can be built using an unbounded number of values or an unbounded number of features. A controller that has an unbounded but countable number of states can compute anything that is computable by a Turing machine.