State representation issues
---------------------------

The representation for a state can affect the efficiency and the generality
of problem solving and learning.  From our experience, efficiency and
generality are maximized if productions are able to test and modify only
those aspects of the problem that are necessary to perform the required
functions.

In practice, this translates into two rules:
     
  1. *All relevant knowledge should be represented explicitly*;
     
  2. *Dynamic and static information should be represented
     independently.*

Relevant knowledge should be represented explicitly as opposed to being
implicit within the conditions of productions.  For example, if it is
relevant that one block is larger than another, this should be represented
explicitly in working memory with a ^larger-than annotation (or some such),
rather than being tested for implicitly in productions, for example by
testing that block A's ^size is greater than block B's (see Section 
See Predicates on page See Predicates).

*Static* information remains constant throughout all states in the problem
space.  For example, in a problem space for stacking blocks, the size, name,
and color of a block will not be changed by any of the operators that move
blocks.  *Dynamic* information is information that does change from state to
state, such as the location of a block in our example.

By representing the dynamic information independently, it can be modified,
copied, or tested without accessing the static information, thus maximizing
the generality of any learning dependent on it.  That is, we can compare
relationships without testing static information explicitly.  For example, if
we wanted to test that two blocks were on both on top of a third block, we
could test for the equality of the relationship between the blocks without
explicitly testing the blocks' names.  This would result in a more general
chunk (see Section See Constants on page See Constants).

In addition, using an independent representation of dynamic information
allows us to easily represent multiple states referring to the same objects
(i.e., the current state and the desired state).  The dynamic information
will be different for the different states, but the static information will
be the same.  Thus the static information does not need to be replicated.

For different problem spaces, different information will be static or
dynamic.  For instance, in our example, if we included operators that allowed
us to paint the blocks, then color would become a dynamic property.  Thus,
*the structure of the representation of a situation will be dependent on the
problem space used to attempt a goal.* An implication of this is that the
extension of a problem space through the discovery of a new operator may
require modifying the underlying state representation.

In the remainder of this section, we derive a representation for a state of
the Blocks World task that represents the relevant data explicitly and
represents dynamic and static information independently.  As a general
strategy, we suggest representing states as a set of objects.  (In this
context we mean conceptual objects, such as blocks, rather than Soar working
memory objects.)  Each object has a representation of its dynamic properties
which contains a pointer to its static representation.

In the Blocks World task, the relevant knowledge is:
     
  1. The types of the available objects: blocks and a table.
     
  2. The blocks being manipulated.
     
  3. The names of the blocks.
     
  4. The table that the blocks can rest on.
     
  5. The *ontop* relationship between blocks and the table, such as that one
     block is on top of another block, or that a block is on top of the
     table.
     
  6. The property of a block that its top is clear.
     
  7. The property that the table is always clear enough to hold more blocks.

For a simplified internal model (where it is a assumed that the table is
large enough to hold all of the blocks), this information is sufficient.  If
this were a task performed by a real robot, we would include additional
information, such as the x and y coordinates of the blocks, and the size and
orientations of the blocks.

All of this information should be represented explicitly in working memory so
that it can be directly matched by productions.  Any predicate which must be
tested by productions should be explicitly placed in working memory, as in
Section See Predicates on page See Predicates, as opposed to being
"computed" implicitly within production conditions.

One possible representation that makes all of the relations explicit is
*model based*.  In a model-based representation, each object represented in
working memory directly corresponds to an object in the situation being
represented.  In this case, each object corresponds to a block or to the
table.  The augmentations of the objects' representations correspond to the
objects' properties and the relations between the objects.  Using this
representational scheme, we could represent the state where block A is on top
of block B, block B is on the table, and block C is also on the table as
follows:

(<state> ^objects <table> <block-A> <block-B> <block-C>)
(<block-A> ^name A     ^type block ^clear yes ^ontop <block-B>)
(<block-B> ^name B     ^type block ^clear no  ^ontop <table>)
(<block-C> ^name C     ^type block ^clear yes ^ontop <table>)
(<table>   ^name table ^type table ^clear yes)

In using this representation, the blocks are referenced by their identifiers,
such as <block-A>, instead of their name, such as A.  If the names were used,
any access of the block would test the name, even if it was irrelevant (see
Section See Constants on page See Constants).

This representation makes it difficult to copy the state without accessing
irrelevant data.  In copying the state for a lookahead search, constant,
static augmentations, such as the name and the type augmentations, must be
copied (so that we can compare the current to the desired state), even though
only the under and ontop augmentations can be modified in the lookahead
search.  As we have continually been preaching, accesses to these specific
constants will show up in chunks and thus make learning undergeneral.

A more subtle problem arises when another state must be represented that
refers to the same objects, such as the desired state of a goal.  A desired
state may represent some constraints on the blocks that must be achieved in
order to satisfy the goal.  For example, the goal may be to stack the blocks
so that block A is on block B and block B is on block C, which is on the
table.  This could be represented as:

(<dstate> ^objects <dtable> <dblock-A> <dblock-B> <dblock-C>)
(<dblock-A> ^name A ^ontop <dblock-B>)
(<dblock-B> ^name B ^ontop <dblock-C>)
(<dblock-C> ^name C ^ontop <dtable>)
(<dtable>   ^name table)

However, with this representation, there is not a single object representing
a given block.  For example, block A is represented by objects <block-A> and
<dblock-A>.  Thus, each different use of an object is represented by a
different object in working memory.  Therefore, in order to determine if an
object in the current state meets the constraints of the desired state, a
production must match two object structures and test that they have the same
constant for a name.  As described in Section See Constants on page 
See Constants, this leads to overly specific chunks because they will test the
specific names of the blocks when equality is all that is needed.

One way to avoid these problems is to have a single representation of all of
the static properties of an object, with all of the dynamic structure of an
object represented separately.  The dynamic structures are specific to a
given state, so they are accessed through augmentations of a state.  We will
call these dynamic structures *object-dynamic*.

The static structures are accessed through augmentations of the dynamic
objects, and are called ^object-static. Using this representational scheme,
the initial and desired states presented earlier are represented as follows:

(<state> ^object-dynamic <block-A-dyn> <block-B-dyn>
                         <block-C-dyn> <table-dyn>)
(<block-A-dyn> ^object-static <block-A> ^clear yes ^ontop <block-B>)
(<block-B-dyn> ^object-static <block-B> ^clear no  ^ontop <table>)
(<block-C-dyn> ^object-static <block-C> ^clear yes ^ontop <table>)
(<table-dyn>   ^object-static <table>   ^clear yes)

(<dstate> ^object-dynamic <dblock-A-dyn> <dblock-B-dyn> <dblock-C-dyn>)
(<dblock-A-dyn> ^object-static <block-A> ^ontop <dblock-B>)
(<dblock-B-dyn> ^object-static <block-B> ^ontop <dblock-C>)
(<dblock-C-dyn> ^object-static <block-C> ^ontop <dtable>)

(<block-A> ^name A     ^type block)
(<block-B> ^name B     ^type block)
(<block-C> ^name C     ^type block)
(<table>   ^name table ^type table)

This representation makes it possible to compare the identity of objects in
the current and desired states for equality without testing any specific
constants.

Additional static information, such as the color, size, or shape of a block
can be added to the object-static representation.  Additional dynamic
information, such as the exact x, y, and z location of an object can be added
to the object-dynamic.

This representation has three problems.  First, when creating the desired
state (or other states that are alternatives to the current state), the same
identifiers for the static object information must be used.  This often
requires matching an abstract description of the desired state against the
current state to determine the identifiers of the internal descriptions of
the objects.  Although this requires testing the specific values of
constants, it does not affect the chunks learned during problem solving,
because the *results* of the subgoal will not be dependent on the specific
values of the constants, but only on the identifiers.  Thus this process does
not lead to overly specific learning.

The second problem with this representation is that it requires that a
commitment is made to which information is dynamic and which information is
static when the problem is set up.  Thus, a preanalysis of the operators of
the problem space maybe necessary.  If new operators are discovered during
problem solving, it may be necessary to dynamically modify the structure of
the representation (and this could be difficult).

The third problem with this representation is that it uses a {multi-valued
attribute} as an augmentation of the state.  Multi-valued attributes can
decrease the efficiency of the production matches and should be avoided if
possible.  One possible approach is to explicitly maintain a focus of
attention on a subset of the objects, thus reducing the cost of matching
productions that access the objects focussed on.  The problem with focus of
attention mechanisms is that they require deliberate selection of which
objects should be attended to, and thus exact their own efficiency costs;
however, these selections are open to control through preferences, and thus,
can be minimized with additional knowledge.