Overview
========

All activity in Soar is formulated as applying *operators* to {states} within
a *problem space* to achieve a *goal* as shown in Figure ? for a simple
Blocks World task.  A *goal* is some desired situation, such as stacking
three blocks on top of each other in a specific order to form a tower as
shown at the right of Figure ?.  *States* are data structures that define
possible stages of progress in the problem, such as different positions of
blocks.  *Operators* transform a state via some action, such as changing the
location of a block, and are depicted by arrows in the figure.  A *problem
space* is the collection of states and operators that are available for
achieving a goal.  In general, a problem space is not represented explicitly
by enumerating all of the states, which may be infinite, but is instead
generated through the application of operators.

*Problem solving* is the process of moving from a given *initial
state* in the problem space, through intermediate states generated by
operators, reaching a *desired state*, and thereby attaining the goal.  If we
view problem solving from this perspective, it is a sequential activity,
where only a single operator is selected and applied at each stage.  Various
search methods arise through using knowledge to select appropriate operators
and states during problem solving. Figure ? shows the result of using a
look-ahead search that detects dead-ends.

Consider the problem of stacking blocks with a robot that has a gripper for
grabbing the blocks and a camera for seeing the blocks, as shown in the left
of Figure ?.  A state in the problem space would consist mostly of the data
available from the sensors of the robot, such as the locations of the blocks
and the gripper in an xyz-space, or that the gripper is open. The state may
have additional data built up through simple inferences, such as that block A
is on top of block B, or that the gripper is above block A.  The state might
have other data recalled from earlier experiences, such as that block B is
slippery and difficult to pick up.  In all, the state may contain data from
any of these sources.  The right of Figure ? includes a predicate logic
description of this state.

The operators in a problem space transform one state to another.  The
transformation can be made directly by modifying the information in the
state.  For example, in a problem involving internal computation and
reasoning, the operators may directly modify the state by augmenting the
state with the sum of two numbers.  The transformation can also be made
indirectly, by performing actions in the external environment.  If a real
robot is being controlled, the operators will make changes to the world,
which then will be detected by the sensors, thus changing the state.  In many
cases, a single operator may do both, possibly by giving a command to move
the arm, as well as creating an internal expectation of the results of the
action.

The set of available operators is determined by the actions that the system
can use to manipulate its environment and by the system's own knowledge of
the task.  For a task involving a real robot, the operators might include
moving the gripper to a specific location, changing the orientation of the
gripper, opening the gripper, and closing the gripper.  This set of operators
might be restricted by additional knowledge, such as that the current problem
should be solved by not moving more than one block at a time.  The set might
also be expanded through the creation of complex operators that involve
sequences of relatively primitive operators.  In controlling the robot, which
requires commands for manipulating the gripper directly, the system may
perform much of its problem solving in a problem space consisting of abstract
operators that move blocks directly from one position to another.  These
operators will then be implemented in a primitive problem space that
corresponds to the robot's physical actions.

For a task that involves internal reasoning, such as multiplying two numbers
"in the head", the problem space may have the basic operators of multiplying
two single digits at a time, as well as additional operators for activities
such as adding, keeping track of the current position in the problem, and so
forth.  The problem space might also have a large number of special-purpose
operators that are acquired through experience (such as the squares from 1 to
20), or incorporate special properties of certain numbers (i.e., the digits
that result from multiplying by 9 always sum to a multiple of 9).  The
available operators, and thus the available problem spaces for such a task,
are determined by the knowledge embedded in the system.

When an operator makes a modification to the state, the modification must
endure even after the operator is no longer current. The modification is
*persistent* because the purpose of applying an operator is to change the
situation.  Usually the change affects only a small part of the state;
however, no matter how big or small the change is, it is a step in the
problem space.  Operator applications are the only way to make persistent
changes to the state.  Other changes to the state that are not dependent on
the selection of an operator, but are instead based on the contents of the
state are called *refinements*. Refinements are not persistent; they will be
undone whenever the situation in which they were created changes.  For
example, the inference that one block is to the right of another should not
persist if it is based on specific coordinates, and the coordinates change.
Similarly, the set of operators that are relevant should change as the state
changes.

Within a problem space, a problem is solved by starting at some initial
state, transforming that state through the application of operators until a
state is reached that is recognized as being a desired state.  It is through
this activity of selecting and applying operators that Soar solves problems.
Our use of "problem solving" is meant to be generic, so that it includes
calculating, reasoning, and similar activities that involve performing
operations on data.  The exact type of behavior that Soar produces is
dependent on the knowledge encoded in it.  For example, if there is little
knowledge about a particular task, there will be extensive search, as
different paths are explored before the goal is achieved.  If the system has
extensive knowledge of a task, the behavior will appear controlled and devoid
of search.

While trying to solve a problem in a problem space, the directly available
knowledge may be incomplete or inconsistent.  This is expected in any
intelligent system that is working with limited knowledge in a novel
environment.  The system may not know the appropriate problem spaces, initial
states, or operators for the task.  The system may also not know which of the
available objects is appropriate for the current situation, or it may not
know how to perform a complex action.  We call these situations *impasses*
because the system is unable to make progress in the current problem given
its available knowledge. Figure ? shows an example impasse in the Blocks
World problem, where there are three possible operators, but the available
knowledge is insufficient for discriminating between them.

An impasse is an occasion in which to cast the lack of knowledge itself as a
problem to be solved.  In a problem space formulation, this involves creating
a subgoal to resolve the impasse and then selecting an appropriate problem
space, initial state, and so on, for working on the goal.  The problem space
selected for the subgoal may be the same as used for the goal where the
impasse arose, but it need not.  It should be a problem space that is
appropriate for generating information that will lead to the resolution of
the impasse.  If the impasse arises from the inability to apply an operator
to the current state because some preconditions of the operator were not
satisfied, then the impasse can be resolved by *operator subgoaling*.  In
operator subgoaling the state is transformed through the application of other
operators so that the preconditions of the first operator are satisfied.  For
an impasse that arises to apply an operator, possibly because the application
itself requires problem solving, a completely different problem space may be
appropriate.

Within a subgoal, the problem solving may also reach an impasse, leading to a
hierarchy of goals, problem spaces, and impasses.  Such a hierarchy is not
uncommon in AI; however, they are for the most part for applications of
complex operators cast as plan-goal hierarchies.  More novel are problem
space hierarchies for reasoning about control decisions, so-called
{meta-goals}.  Problem spaces with impasses provide a framework in which both
types of goals are treated uniformly, so that a meta-goal is a goal to make a
selection between alternative problem spaces, states, or operators.  The
processing in the goal involves search of a problem space to select the best
alternative.  One hypothesis made in Soar is that impasse-driven goal
generation is sufficient for all goals and that no other goal generation and
selection mechanisms are required [Lair84].  Thus, no deliberate goal
generation mechanism is available in Soar.
 
A common approach in AI is to split a single goal into multiple subgoals,
with the expectation that the smaller goals will be easier to solve than the
original goal.  As shown in Figure ?, a goal can split into multiple subgoals
by having a problem space with operators for each subgoal. The sequence of
operators that achieve each of the subgoals provides the standard conjunctive
decomposition of a goal.  The problem of ordering the conjunctive goals is
exactly the problem of deciding which operator to apply first. Disjunctive
decompositions arise when there is more than one operator available for a
given subgoal.  A hierarchy of goals will arise if one of the selected
operators leads to an impasse, and thus another goal that can be further
decomposed.

When an impasse is resolved, it is because some result was produced by the
problem solving in a subgoal.  That result is new knowledge that was
previously not directly available in the problem space where the impasse
arose.  The knowledge had to be recalled or generated in the subgoal through
time-consuming problem solving.  Producing the result provides an opportunity
to learn.  If the processing of the subgoal can be captured in an efficient
form, so that the results of the subgoal can be produced directly without
problem solving, the impasse and associated problem solving can be avoided in
future.  This will speed up problem solving in the future, and possibly
capture knowledge that was only available at the time the original impasse
arose.

The top-level goal and problem space are distinguished because they are not
generated in response to impasses.  The top-level problem space is where the
system interacts with its environment in pursuit of its most basic goals,
such as maintaining its energy supply and avoiding damage to itself.  The
operators of this problem space can perform actions in the external
environment and the states in this problem space reflect the system's
perception of the external environment.  Other operators in this problem
space can be more abstract, requiring substantial problem solving or at least
sustained problem solving that will naturally be carried out in a subgoal.
Interaction can also be carried out within a subgoal by using the state and
operators of the top-level problem space as part of the problem space in the
subgoal.