11 1024x768

sta;e(e. w. e. e.)

f

sławo. ó. o. W)

T

t

Figurę 14.2 Portionofthe siatę space graph of the farmer, wolf. goat. and cabbage problem, inchiding unsafe States.

This rulc dres when a State (the present location in the graph) is presented to the firn parameter of move in which the farmer and wolf arc at the same location. Whcn the rak dres, a new stale, the sccond parameter of move. is produccd witlt the valuc ol'X oppositc. opp. the yaluc of Y. '|\vo conditions arc satisficd to producc the new statc: drst. thar the valucs of the drst two parameters arc the same and. sccond. that both of their new loca* tiOns arc oppositc their old.

The drst condition was chcckcd implicitly in the unification proccss, in that move i* not cven callcd unless the drst two parameters arc the same. This test may be dooe c\plicitly by using the following rulc:

move(state(F, W. G. C). statę(Z, Z. G. C))F = W. opp(F, Z).

This cquivalcnt move rulc drst tests whether F and W arc the same and. only ifthcysc (on the sanie side of the rivcr), assigns the oppositc valuc of F to Z. Notę that PROLOG can do "assignmcnf' by the binding of variablc values in unification. Bindings arc shared by all occurrcnces of a variab!e in a clause, and the scope of a variablc is limited to ibe cłause in which it occurs.

Patiem nutching, a powcrfiil tool in Al programming. is cspccially importam in pruh* ing scarch. States Ibal do not fil the pattems in the nile are autoniatically pruned. In this scmc. the first vcrsioo of the move rulc offers a morę cfficient rcprcscntation because uni* dcaiion docs not cvcn considcr tlić statc prediente unless its first two parameters arc ideo-tical.

PART VIILANGUAGES FOR Al PROBLEM SOLVING

Next, we creatc a predkalc lo test whether cach new statc t% sale. so that nothing is cjten in Ihc proces* of Crossing the rhrer. Agam. unification plays an importom role in this definition. Any statc w herc the sccond and third parameters arc the same and oppositc the first parameter is unsafc: the wolf cats the gont. Altcmativcły. if the third and fourth parameters arc the same and oppositc the first parameter. the statc i$ unsafc: the gnat cats the cabbagc. Th esc unsafe situations may be represented with the folfowing rules.

unsafo(statc{X. Y. Y. C)) opp(X. Y).

unsafe(state(X. W. Y. Y» opp(X, Y).

Scveral points should be mentioned herc. First, if a statc is to be not unsafe (i.c., saki according to the definition of not in PROLOG, neither of thcsc unsafe prcdicatcs can be tnąc. Thus. neither of tltcse prcdicatcs can unity with the current statc or. if they do ■if)'. their conditions musi not be satisficd. Sccond. not in PROLOG is noc cxactly equivalcnt to the logicai -i of the first-order predicatc calculus: not is rather “negation by frilure of its oppositc.” The reader should test a number of States to verify that unsafe does what it is intended to do. Now. not unsafe is added to the pmious production rulc:

movo(state(X. X. G. C). state(Y. Y. G. C))

opp(X. Y). not(unsafo(state(Y. Y. G. C))).

The not unsafe test calls unsafe. as mentioned above. to sec whether the gencraicd statc B an acccptablc new statc in the scarch. When all critcria arc met. including the chcck in the path algorithm that the new stale is not a member of the visitcd-statc list. path is (rccursivcly) cnlled on this sunę co go decper into the graph. When path is called. the new iUie is added to the visitcd-sfaic list.

In a similar fashion. we can creatc the thrcc other production rules to represent the farmer taking the goat. cnbbagc. and himsclf across the mer. We have added a writelist cominand to cach production rulc to print a tracę of the current rulc.

The reverse_print_stack command is uscd in the terminating condition of path to print out the finał solution path. Finally. we add a fifth “pseudorulc” that always finrs. bceause no conditions arc ploccd on it. when all pre\*ious rules havc failed; ii indicatcs that tbe path cali is backtracking from the current statc. and then it itself fails. This pscudorulc is added to assist the uscr in sccing what is going on os the production system is running.

We now present the ftill production system program in PROLOG to solić the farmer, wolf. goat. and cabbagc problem. The PROLOG prcdicatcs unsafe. writelist. and che ADT stack prcdicatcs of Scction 14.2.1. must also be included:

movo(statO{X. X. G, C). stato(Y. Y. G. C)) opp(X. Y). not (u nsafo(stato( Y. Y. G. C))). writefist([‘try farmer takos wolf'. Y. Y, G. CJ).

move{state(X. W. X. C). stato(Y. W. Y, C)) opp(X. Y). not(unsnfo(state<Y. W. Y. C))). writollst(£*try farmer takos goat*. Y. W. Y. CJ).

move(state(X. W. G. X). state<Y. W. G. Y)) opp{X. Y). not(unsafe(stato(Y. W, G. Y))). writelist((*try farmer takes cabbago'. Y. W. G, YJ).

CHARTER 14 / AN INTROOUCTION TO PROLOG 623