Impasses
--------

When the preferences for an augmentation do not lead to a consensus choice,
an *impasse* arises.  Soar's handling of the impasse depends on the type of
augmentation.  Soar distinguishes two types of impasses.  *Attribute
impasses* arise when a decision can not be made for any augmentation except a
context slot. *Context impasses* arise when a decision cannot be made for a
context slot.

For an attribute impasse, Soar creates an *impasse object* that describes the
type of impasse, and any tying or conflicting candidates.  The impasse
objects can then be tested by productions to detect that there were
insufficient preferences to select the value of an augmentation.  There is no
requirement that the impasse be resolved as it is often possible to continue
problem solving with some limited uncertainty.  Impasses are resolved when a
consensus choice can be made, usually through the addition of new
preferences.  Resolving an attribute impasse can be a bit tricky because as
soon as a new preference is created by a production to resolve the impasse,
the impasse object is removed from working memory.  If the production that
created the preference tested the impasse object, it could be retracted,
leading to another attribute impasse and indefinite looping.  To avoid the
retraction, the preference to resolve the impasse should be created by an
operator application production.

If an impasse arises for a context slot then it signifies that knowledge to
perform a PSCM function is lacking.  In response to this type of impasse, a
subgoal is created in which the full power of Soar's problem solving can be
used to retrieve or generate additional knowledge, ultimately leading to the
creation of preferences that resolve the impasse.  Once a subgoal is created,
productions fire to propose problem spaces, and then initial states, followed
by operators, and so on.  The knowledge to resolve the impasse may be
retrieved by any type of problem solving, from searching to discover the
implications of different decisions, to asking an outside agent for advice.
There is no *a priori* restriction on the processing, except that it involves
applying operators to states.

Within a subgoal, additional impasses may be encountered, leading to
additional goals, and the creation of a stack of goals and their associated
contexts.  As stated earlier, the context stack is contained in working
memory.  Because of the nature of the PSCM functions, and the semantics of
preferences, only one context impasse is possible at a time for a given goal.
If there is an impasse for a given context augmentation, say the problem
space, no decision is made on lower context slots, in this case the state and
operator.

There are four types of impasses that can arise from the preference scheme:

  1. A *tie* impasse arises if the preferences for an attribute do not
     distinguish between two or more values with acceptable preferences.  A
     tie impasse can be resolved by creating preferences that prefer one
     option (better, best, require), eliminate alternatives (worse, worst,
     reject, prohibit), or make the objects indifferent (indifferent).  If
     two values have best or worst preferences, they will tie unless
     additional preferences distinguish between them.
     
  2. A *conflict* impasse arises if at least two values have conflicting
     better or worse preferences (such as A is better than B and B is better
     than A) for an attribute, and neither one is rejected, prohibited, or
     required.  A conflict impasse can be resolved by creating preferences to
     require one option (require), or eliminate the alternatives (reject,
     prohibit).
     
  3. A *constraint-failure* impasse arises if there is more than one required
     object for an attribute, or if an object has both a require and a prohibit
     preference.  These preferences represent constraints on the legal selections
     that can be made for a decision and if they conflict, no progress can be made
     from the current situation and the impasse cannot be resolved by creating
     additional preferences for the values.
     
  4. A *no-change* impasse arises if none of the context slots change value
     during the decision procedure. A no-change can be resolved by creating a
     reconsider preference for the last object selected, or by creating
     acceptable or require preferences for the next empty slot of the
     context.

A given attribute or context slot can have only one impasse at a time. Given
the semantics of the preferences, it is possible to have a tie or conflict
and a constraint-failure at the same time.  In these cases, Soar detects only
the constraint-failure.