Subgoaling and default productions
----------------------------------

As mentioned previously, there are multiple move-block operators proposed for
each state. Without the search-control productions that create preferences
for the operators, Soar would have insufficient knowledge to select among the
operators.  If we assume that the search control productions do not exist,
then a tie impasse arises.

In response to the tie impasse, Soar creates a subgoal. There exist default
productions that are sensitive to the tie impasse and they propose a problem
space, called the *selection* problem space (see Chapter *Note Default
knowledge in Soar:: on page See Default knowledge in Soar).  If no other
competing problem spaces are proposed, the selection problem space is chosen.
The operators of the selection problem space evaluate the tied alternatives,
thereby allowing preferences to be created for them.  Once sufficient
preferences are available to distinguish a single choice, the tie will be
broken, and problem solving can continue.

Below is a partial trace of the tie impasse and selection problem space.

0   G: G1
1   P: P1 (top-ps)
2   S: S1 (top-state)
3   O: O2 (build-tower)
4   ==> G: G2 (operator no-change) 
5       P: P2 (blocks-world)
6       S: S1 (top-state)
7       ==> G: G3 (operator tie)
8           P: P3 (selection)
9           S: S2 

To compute an evaluation, an *evaluate-object* operator is created for each
tied operator.  If no knowledge is available in productions to directly
compute an evaluation, another *no-change impasse* will arise to apply the
evaluate-object operator.  In the associated subgoal, called the *evaluation
subgoal*, the operator being evaluated can be "tried-out" in a simulation of
the task to gain more knowledge about it.  Conceptually, Soar is looking
ahead to investigate the effects of the operator, but is not actually
applying the operator to the top-level state.  Therefore, a copy of the
original state is used in this subgoal, and the operator being evaluated is
selected and applied with one of the following results:

  1. Another operator is selected.
     
     The new state does not match the desired state, and there is only one
     operator (or there are multiple operators, but preferences indicate that
     one of these is superior to the others). This operator will be applied
     to the current state without additional subgoaling.
     
  2. An impasse occurs.
     
     The new state does not match the desired state, and there are again
     multiple acceptable operators from which to select. This is also a tie
     impasse, and will result in additional levels of subgoaling.
     
  3. An evaluation is computed.
     
     The new state does not match the desired state, but an evaluation is
     available for the state.  The evaluation could be symbolic, such as
     success or failure, or numeric, such as a specific number on some scale.
     Task specific knowledge, possibly encoded in Soar as an operator,
     creates an augmentation of the state of the selection space as the
     result of the evaluate-object operator.  Default knowledge is sensitive
     to the creation of this evaluation and terminates the specific
     instantiation of the evaluate-object operator.  This leads to the
     selection of another evaluate-object operator.  Later, when sufficient
     evaluations have been computed so that the tied operators can be
     compared, default knowledge will create desirability preferences for the
     operators, breaking the tie.  Of course, if success is detected, a best
     preference will be created and the tie impasse will be immediately
     resolved, eliminating the need to apply the remaining evaluate-object
     operators.

In order to perform a lookahead search, additional productions must be
created.  Below is a list of the two basic types of knowledge that must be
added for lookahead, including examples from the Blocks World.

  1. Lookahead state creation The state used for lookahead can not be the
     exact same state as the one that led to the tie because the lookahead
     will modify it.  Therefore, an internal copy of the state must be
     created that can be modified during the lookahead.  Soar contains
     default knowledge to create copies of states for lookahead.  The default
     knowledge must be able to detect that a copy should be made as well as
     which aspects of the state need to be copied (see Section *Note State
     copying:: for details).  This information is kept on the problem space.
     For the Blocks World, the following production would be sufficient.
     
     IF   the goal is to build a tower subgoal, and
          the problem space is named blocks-world,
     THEN augment the problem space to signify that 
             the dynamic information in the state 
             should be copied in lookahead.
     
     
  2. State evaluation There must be some way to evaluate the states of the
     lookahead.  At the least, it must be possible to detect when the goal
     has been achieved.  It may also be possible to compute numeric or other
     symbolic evaluations (such as failure).  See Section *Note Computing
     evaluations:: on page See Computing evaluations for more details.
     For the blocks world, this production is necessary because the original
     production that detects that the Blocks World problem is complete only
     terminates the operator to build a tower.  It does not make the
     achievement of success explicit.
     
     IF   the goal is an evaluation subgoal, and
          the problem space is named blocks-world, and
          the state is the desired state,
     THEN create an evaluation of that operator with a symbolic 
             value of success.
     
     
  3. Search control If additional knowledge is available to control the
     search in the lookahead, the evaluation will be computed much faster.
     For the almost all tasks, a lookahead should avoid unnecessary steps.
     For the Blocks World, it is not desirable to move the same block twice
     in a row because it could always be moved directly in a single step.  We
     can encode this knowledge by adding a production that rejects an
     operator if it will move a block that has just been moved.
     
     IF   the goal is to build a tower subgoal, and
          the problem space is named blocks-world, and
          there is an acceptable operator that will
              move the block just moved,
     THEN create a reject preference for that operator.
     
     
  4. Additional productions might be added to avoid duplicate states; however, this
     requires remembering, either in working memory or production memory, the previous
     states encountered during the lookahead.

Below is a partial trace of the problem solving using lookahead.  Comments
are included in the trace following semi-colons (;).

0   G: G1 
1   P: P1 (top-ps)
2   S: S1 (top-state)
  ;; Initial state has A on B and B and C on the table.
  ;; The goal is to get A on B on C on the table.

3   O: O2 (build-tower)
4   ==>G: G2 (operator no-change)
5      P: P2 (blocks-world)
6      S: S1 (top-state)
  ;; O3: ontop(a,b)
  ;; O4: ontop(b,table)
  ;; O5: ontop(c,table)
7      ==>G: G3 (operator tie)
8         P: P3 (selection)
9         S: S2 
10        O: O8  (evaluate-object O3 (move-block))
  ;; The operator to move A to the table is selected for evaluation.
  ;; The selection was made because all evaluate-object
  ;;     operators are indifferent.

11        ==>G: G39 (operator no-change)
12           P: P2 (blocks-world)
13           S: D7 
14           O: O3 move-block(A table)
  ;; operator O3 applies to a copy of the original state.
  ;; Block A is moved to the table.

  ;;  O10: move-block(c,a)
  ;;  O13: move-block(c,b)
  ;;  O14: move-block(b,c)
  ;;  O15: move-block(b,a)

15           ==>G: G5 (operator tie)          
  ;; A tie-impasse arises between operators to move blocks B and C.
  ;; All operators to move block A have been rejected.

16              P: P4 (selection)
17              S: S3 
18              O: O19 (evaluate-object O13 (move-block))
  ;; The operator to move B onto A is selected for evaluation.

19              ==>G: G6 (operator no-change)
20                 P: P2 (blocks-world)
21                 S: D9 
  ;; A copy of the original lookahead state is created.

22                 O: O13 (move-block)
  ;; Move B onto A is selected and applied.
  ;; The only operator that is acceptable and not rejected is moving 
  ;;    C on B.

23                 O: O24 (move-block)
24                 ==>G: G7 (state no-change)
25                    ==>G: G8 (goal no-change)
  ;; operator O24 (move-block) evaluates to FAILURE because 
  ;;    there are no operators available once C is on B.  There is no 
  ;;    progress that can be made, so default productions create the 
  ;;    FAILURE evaluation.

27              O: O18 evaluate-object 014 (move-block)
  ;; operator O8 is terminated and an new evaluate-object operator is 
  ;;    selected.

28              ==>G: G9 (operator no-change)
29                 P: P2 (blocks-world)
30                 S: D11 
31                 O: O14 (move-block)
;; Move B on C
32                 O: O30 (move-block)
;; Move A on B
  Evaluation of O3 (move-block) is partial-success
    32:       O: O3 (move-block)
    33:       ==>G: G10 (operator tie)
;;  O37: move-block(c,b)
;;  O38: move-block(b,c)
;;  O39: move-block(b,a)
;;  O4:  move-block(c,a)
    34:          P: P5 (selection)
    35:          S: S4 
    36:          O: O43 (evaluate-object O37 (move-block))
    37:          ==>G: G11 (operator no-change)
    38:             P: P2 (blocks-world)
    39:             S: D13 
    40:             O: O37 (move-block)
    41:             O: O48 (move-block)
    42:             ==>G: G12 (state no-change)
    43:                ==>G: G13 (goal no-change)
 ;; Evaluation of O37 (move-block) is failure
    44:          O: O42 (evaluate-object O38 (move-block))
    45:          ==>G: G14 (operator no-change)
    46:             P: P2 (blocks-world)
    47:             S: D15 
    48:             O: O38 (move-block)
    49:             O: O54 (move-block)
;;  Goal implement-evaluate-object succeeded. 
;;  Evaluation of O38 (move-block) is success
    50:       O: O38 (move-block)
    51:       O: O36 (move-block)
;;  Goal build-tower succeeded. 
    52:    O: O1 (wait)
  ;; build-tower is terminated, allowing wait to be selected.