Go backward to Evaluating states.
Go up to Using lookahead search.
Search control
--------------
As described in Section See The evaluate-object operator on page
See The evaluate-object operator, the lookahead search can be controlled
through the addition of control knowledge. For the Blocks World, a simple,
but effective, piece of control knowledge is to never move a block twice.
Although, it is possible to solve a problem by moving the same block twice,
there is always a shorter path.
Detecting that a block has moved twice requires maintaining a bit of history,
namely, that the block that was moved. Soar does not automatically maintain
any history of the operators that have applied. Therefore, productions must
be added to maintain a record of the block that has moved. This is easy to
do by merely adding productions that will fire in parallel with the existing
operator application productions.
The first production below creates an augmentation (^last-moved-block) with
the value of the block being moved by the current operator. The second
production deletes the old value.
(sp blocks-world*apply*operator*remember*moved-block
(goal <g> ^state <s> ^operator.moving-block <mb>)
-->
(<s> ^last-moved-block <mb> + ))
(sp blocks-world*apply*operator*forget*last-moved-block
(goal <g> ^state <s>
^operator.moving-block <mb> <> <lmb>)
(<s> ^last-moved-block <lmb>)
-->
(<s> ^last-moved-block <lmb> - ))
Using the ^last-moved-block augmentation, the following production
rejects any operator that will move the most recently moved block.
(sp blocks-world*reject*move-block*twice
(goal <g> ^state.last-moved-block <mb> ^operator <o> +)
(<o> ^moving-block <mb>)
-->
(<g> ^operator <o> -))
By adding these search-control productions, the lookahead search will avoid
trying wasted moves. This greatly reduces the search space. For example,
whenever a tower is constructed that is not the desired state, the only
available operator is to move the block that was placed on top the tower.
The search control productions will reject this operator and a dead end is
detected. Soar can then abandon that path.
Section See The evaluate-object operator on page *Note The
evaluate-object operator:: has a complete description of the problem solving
using this knowledge. Below is a trace of the blocks world if lookahead
search is used because of the lack of any operator control knowledge. The
information about operator ties is written by an additional monitoring
production.
Soar> d 50
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)
ontop(a,b)
ontop(b,table)
ontop(c,table)
7: ==>G: G3 (operator tie)
O3: move-block(a,table)
O4: move-block(c,a)
O5: move-block(a,c)
8: P: P3 (selection)
9: S: S2
10: O: O8 (evaluate-object O3 (move-block))
11: ==>G: G4 (operator no-change)
12: P: P2 (blocks-world)
13: S: D7
ontop(a,b)
ontop(b,table)
ontop(c,table)
14: O: O3 (move-block)
APPLIED O3: move-block(a,table)
ontop(a,table)
15: ==>G: G5 (operator tie)
O13: move-block(c,b)
O14: move-block(b,c)
O15: move-block(b,a)
O10: move-block(c,a)
16: P: P4 (selection)
17: S: S3
18: O: O19 (evaluate-object O13 (move-block))
19: ==>G: G6 (operator no-change)
20: P: P2 (blocks-world)
21: S: D9
ontop(a,table)
ontop(b,table)
ontop(c,table)
22: O: O13 (move-block)
APPLIED O13: move-block(c,b)
ontop(c,b)
23: O: O24 (move-block)
APPLIED O24: move-block(a,c)
ontop(a,c)
24: ==>G: G7 (state no-change)
25: ==>G: G8 (goal no-change)
Evaluation of O13 (move-block) is failure
26: O: O18 (evaluate-object O14 (move-block))
27: ==>G: G9 (operator no-change)
28: P: P2 (blocks-world)
29: S: D11
ontop(a,table)
ontop(b,table)
ontop(c,table)
30: O: O14 (move-block)
APPLIED O14: move-block(b,c)
ontop(b,c)
31: O: O30 (move-block)
APPLIED O30: move-block(a,b)
ontop(a,b)
Goal implement-evaluate-object succeeded.
Evaluation of O14 (move-block) is success
Evaluation of O3 (move-block) is partial-success
32: O: O3 (move-block)
APPLIED O3: move-block(a,table)
ontop(a,table)
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
ontop(a,table)
ontop(b,table)
ontop(c,table)
40: O: O37 (move-block)
APPLIED O37: move-block(c,b)
ontop(c,b)
41: O: O48 (move-block)
APPLIED O48: move-block(a,c)
ontop(a,c)
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
ontop(a,table)
ontop(b,table)
ontop(c,table)
48: O: O38 (move-block)
APPLIED O38: move-block(b,c)
ontop(b,c)
49: O: O54 (move-block)
APPLIED O54: move-block(a,b)
ontop(a,b)
Goal implement-evaluate-object succeeded.
Evaluation of O38 (move-block) is success
50: O: O38 (move-block)
APPLIED O38: move-block(b,c)
ontop(b,c)
51: O: O36 (move-block)
APPLIED O36: move-block(a,b)
ontop(a,b)
Goal build-tower succeeded.
52: O: O1 (wait)