10 1024x768

143 A Production System Example in PROLOG

la the section \\c write a production system solution to the farmer, wojf. goat, and ab-hage problem. The problem is stated as follows:

A farmer with his wotf. goat. and cabhage eonie to the edge of a rivcr they wish to cross. Thoc is a boat at the river’s edge. but. of counsc, only the farmer can row. The boat ulso caa carty outy tao things (induding the rower) at a timc. If the wolf is cvcr Icft alonc with the goat, the wolf will cat the goat; similarly. if the goat is left alonc with the cabhagc, the goat w ill eat ih* cabbage. De%ise a «cqucnce of crossings of the river so that all four characters arrivc satćly on the other side of the riyęr.

In the ncxt paragraphs we present a production system solution to this problem. First, we observe that the problem may be represented as a scarch through a graph. To do this we consider the possible moves that might be availablc at any timc in the solution process. Some of these movcs aro cvcntually ruled out because they produce States that arc untafe (something will be catcn).

For the moment, suppose that all States arc safc. and simply consider the graph of possible States. The boat can be used in four ways: to carry the farmer and wolf, the farmer and goat, the farmer and cabbage, and the farmer alonc. A State of the world is some combination of the characters on the iwo banks. Sevcral States of the scarch arc represented in Figurę 14.1. States of the world may be represented using the prcdicatc. state(F. W, G, C). with the location of the farmer as lirst parameter, location of the wolf as tccond parameter. the goat as third and the cabbage as fourth. We assumc tliat the róa rum "north to south" and that the characters arc on cithcr the east, e. or west. w. bat Thus. state(w, w, w, w) hasali characters on the West bank to start the problem.

It musi be pointed out that these cbośces arc convcntionś that havc bccn arbttrariłr chosen by the authors. Indccd. as researchcrs in Al continua!ly point out. the sekcóooof an appropriate rcpresentation is often the most critical aspect of problem soKing. These con\ entions arc sełected to fil the prcdicatc calculus rcpresentation in PROLOG. Differc* States of the world arc crcated by different crossings of the mor. represented by duages ■ the yalucs.of the parameters of the State prcdicatc as in Figurę 14.1. Other represatobent are certainły possible.

We now dcscribe a generał graph for this rivcr-crossing problem. For tbe time bdag. we ignore the fact that some States are unsafc. In Figurę 14.2 we sec the beginning of do graph of possible rmn es back and forth across the river. Since the farmer always nws. not nccessary to have a separate rcpresentation for the location of the boat. Figurę 14.2 represenu part of the graph that is to be searchcd for a solution path.

The rccuraivc path cali prcvious!y described prorides the control mechanisn for the production system scarch. The production raks are the raks for changing siatę in tk scarch. We define these as mowę raks in PROLOG form.

Bccause PROLOG uses Horn clauscs. a production system designed in PROLOG must cithcr represent production raks directly in Horn elause form or translate rules W this format. We uke tbe farmer option herc (and show how If ... then ... raks are ęlinngcd to Horn clauscs in Section 12.2). Horn clauscs rcquire that the panem for the present tuie

r. W .W)

E

^(e.w.e.w) —T*“* *• •• ^w)

"• •• *ł

StAtOlW. W. W. O)

sutofo. •• w. o) staUNw. O. w. •)

Figuro 14.1 Sampłe crosaings for the farmer, wotf. goat. and cabbage problem.

and the panem for the next stale boch be placcd in the head of tbe Horn clause. or to the Icft ofThese arc the arguments to the mova prcdicatc. The conditaons that tbe produc-(ion nile rcquircs to tire and return the next State arc płaced to the rigbc of. As słsown in the follow ing cxamplc. these conditions can also be caprcsscd as unification constraincs.

The first nile we define is for the farmer to takc the wolf across the river. This nile ■mutaccoum for boch the transfer from cast to west and the transfer frooi west to cast. and śmust not be applicabłe when the farmer and wolf arc on opposite sidesofthe mer. Thus. u musi tran*form stnte(e. o. O. C) to state(w. w. G. C) and statefw. w. G. C) to State(0, O. G. C). It musi also fail for state(e. w. G. C) and statefw. o. G. C). The vari-ahlcsG and C represent the fact that the thiid and fourth parameters can be bound to cithcr • or W. Whaicvcr Ihcir valucs. they rcmain the same arter the move of the farmer and wolf Some of the States produccd may indccd be ~unsafc ~

The following move nile openites oniy when the farmer and wolf arc in the same botśon and takes them to fhc opposite sidc of the mer. Notę that the goat and cabbage do Bot ełtange thcir present location (w*hatevcr it mighf be).

movc(stato(X, X. G. C). statofY. Y. G. C)) - opp(X. Y).

Opp(o. w).

OPP(W, o).

CHARTER 14/ AKINTROOOCTłON TO PROLOG 621