12 1024x768

move(stattKX, W. G. C). state(Y. W. G. C)> opp(X. Y). i>ot(unsafc(stato{Y. W. G. C))>. vvrHelist(£'try farmer takes self. Y. W. G. C]). move(state{F, W. G. C). state(F. W. G. C))

writefist((" BACKTRACK from:'. F. W. G. CJ). fali. path (Goal. Goal. Been_stack) wótefSołution Pafh Is: *). nl. ro vorse_print_siack< Been _stack). path(State. Goai. Been stack) > move<State. Next_state). not(member_stack(Next_state. Been stack)), stack(Noxt_state. Been stack. New. boon stack). path(Next stale. Goal. New_been stack).!.

opp(o. w).

opp(w. •).

The codę is callcd by requcsting go. which inifializcs the rccursivc path calL To make running the program casier. w can crcatc a prcdicatc. called test that simplifcsibc input:

go(Start. Goal)

empty_stack(Empty_boen_stack). stackfSiart. Empty boon stack. Been_.stack), path(Start. Goal. Boon. stack).

testgo<state(w.w.w.w). stato(e.o.e.e)).

The algorithm backtnicks from States that allow no furihcr progres*. You may also sse tracę to monitor the various variablc bindings local to cach cali of path. It may also be noted that thi* program is a generał program for moving the four creatures from any (legał) position on the banks to any other (legał) position. including asking for a path from the goal back to the start State. Other interesting fcature* of production systems. including the fact that difTercnt orderings of the rules can producc di flferent searches through the graph. arc presented in the exercise$. A partial lnico of the cxecution of the program, showing only rules actually uscd to generale ncw States, is presented ncxt:

?'test

try farmer takes goal e w e w try farmer takes sełf w w e w try farmer takes wolf e e e w try farmer takes goal w e w w try farmer takes cabbage e e w e try farmer takes wolf w w w e try farmer takes goat e w e e BACKTRACK from e.w.e.e

BACKTRACK from w.w.w.e try farmer takes sełf w e w e try farmer takes goat e e o e

PART VI / LANGU AGES FOR Al PROBLEM SOLYING

Solution Path Is:

state(w.w.w.w)

sUłto(o.w.e.w)

iłtnto(w.w.e.w)

state(o.e.o.w)

staie(w.o.w.w)

stato(o.e.w.c)

stato(w.e.w.e)

stato(o.e.c.c)

In summary. ihis PROLOG program implcmcnts a production tyticm solution to the farmer, wolf. goat. and cabbagc problem. The move rules make up the content of the pro-duciion mcmory. The working memory is represenicd by the arguments of the path calL The production system eon troi mechanism is defined by the rccursńc path cali. Finał ly. the oedering of rules for generałion of children from cach stale (conflict rcsolution) is determined by the order in which the rules arc placed in the production memory.

14.4 Pesigning Alternative Search Strategies_

As the previous subsection demonstrated. and as is madę morc prccise in Scction 14.7. PROLOG itsclf uses depth-first search with backtracking. We mm show bow the iłKmaliw search strategies of Chapters 3.4. and 5 can be implcmcntcd in PROLOG. Our impicmcnfations of depth-first. breadth-firsl. and best-first search use Open and dosed lists to rccord States in the search. When search fails at any point wc do not go hack to the preccding values of open and closed. Instcad. open and closed arc updatcd uichin che path cali and the search continucs with these ncw ualues. The cm is used to kcep PROLOG from storing the old versions of open and closed.

14.4.1 Depth-First Search Using the Closed List

Bccausc the valucs of variables arc restorcd w hen rccursion backłracks. the list of vixitcd Hatcs in the depth-first path algorithm of Scction 14.3 rccords States only if they arc on the currcnt path to the gnał. Although the testing cach "ncw" stale for meinbership in this lisi pttvcnts loops. it still allows branches of the spacc to be rccxamincd if they arc rcachcd aloog palhs generated coriicr but abandoncd at that timc as unfruilful. A morc cflicicnt mytanentation kecps track of all the States that havc cvcr been cncountcrcd. This morc compłetc collcction of States macie up the list callcd closed in CTuptcr 3. and Closed.set in the foilowing algorithm.

Closed. .set holds all States on the currcnt path plus the States that werc rcjected w hen the algorithm backtrnckcd out of them; thus. it no longer rcprcscnts the path from the start to the currcnt statc. To capture this path Information. wc erratę the ordercd pair (State. Parent) to kcep track of cach State and its parent; the Start stale is represenicd by (Start, nil). These stale-parent pairs will be used to rc-crcate the solution path from the Clos«d„seL

CHARTER 14/ANIMTRODUCTION TO PROCOO 625