15 1024x768

nile*. 4 safc chcck for legał mores. and a heuristie musi be specifically defincd for eac* appłication. The member check nmsi be spccilically designed for fivc element listó.

get.chiidrenaStale.,. O. _ J. Rastop«n_pq. Closed_sei. Childron. Goni) > bagoĄChild. mcves([State. . D. J. Rest open_pq.

Close<J_set. Child. Goal). Children). moves([St3tc. . Depth J. Rest open_pq. Closed set.

[Noxt. State. New_D. H. S], Goal) move(State. Next),

not(unsafe(Next)).    % dotermlnod by applicatioo

not(member pq((Next. J. Rest_opon ,pq». not(member_set([NexL _. _. J. Closed set)).

New_D is Depth +1.

heuristic(Nexi, Goal. H).    % detorminod by applicalion

SisN*w_D+R

FinalK. prinisolution prines the solution path. It rccun»ivcly finds State-Pareni poirs by maichmg tbe fint iwo cletncwis in ihc stale dcscription with the lirsl iwo cłcmcnts of the ttvc element list* ihat make up the Closed.sot. The start staic has nil as iis parem.

pnntsolution<[Stoto, nil. _. J. J write(Stato). nl.

printsołub‘on([Stato. Porom. _. Closed set)

member_s«t([Parent. Grandparent. _. J. Closed set).

prfntsolutk>n([Parent. Grandparent. J. Closed_set).

«itte(Stal»).nl.

14.5 A PROLOG Planner

In Sccfion 5.4 we describcd a prcdicatc calculus-based planning algorithm. It was predicate calculus (PC) bucd in that the PC represcnlalion was chosen for both the State of the planning world dcscriptions as \vcll as the changę of stale rulcs. In this sccfion w creaie a PROLOG rersion of thai algorithm.

We represeni the States of the world. including the begin and goni States, as lista of prcdicatc*. Two States, the start and goal States for our examplc. aro describcd:

start = (handempty ontable(b). onlable(c). on(a.b). cloar(c). clear(a)l goal ■ [handempty, ontabłe(a). ontable(b). on(c.b). clonr(a), clear(c>]

Thesc States are secn. along with a portioo of the scarch spacc, in Figures 14.3 and 14.4.

The men es in this błocks world are describcd using add and dcletc lists. as in Sectioa 7.4. The mov# prcdicatc* have threc argument*. First is the move prcdicatc naroc with it> argument*. The second argument » the list of prcconditions: the prcdicatcs that most be truć in the dcscńption of the sute of the world for the movc rulc to be applied to that suk. The third argument is the add and dcletc list: tbe prcdicatcs that are added lo and ddfld from the stale of the world to creaie the nęw stale of the world thai rcsults Dom apptyiaf

PART VI / LANGUAGES FOR Al PROBLEM SOLVtMG

inove rulc. Noticc how useful the ADT set operatora of union, intcracction. set diltcr-L|ce etc., are in manipulating the prcconditions and the add and dcletc lists. p_our of the moves within this world may be describcd:

_movo(plcKop(X). [handempty. clear(X). on(X.Y)]. [dol(handompty). del(clear(X)). del(on(X.Y)), add(clear(Y)). add(hofding(X))]).

Figuro 14.3 The start and goal States for the błocfcs world problem.

Figuro 14.4 The initial lovols of the blocks world State space.

CHAPTER 14 ; AN INTRODUCTION TO PROLOG

631