Raluca Budiu (ralucav+@cs.cmu.edu)
aprilie 1996 ?
În acest articol ne propunem să prezentăm una din problemele centrale ale inteligenței artificiale -- planificarea, împreună cu o soluție simplă (și parțială) a ei, implementată în limbajul PROLOG. Pentru înțelegerea articolului nu e necesară cunoașterea PROLOG-ului. Doar studiul codului din anexă necesită o minimă familiarizare cu acest limbaj.
Înainte de a da o definiție planificării, așa cum este ea înțeleasă de inteligența artificială, să considerăm următorul exemplu. Să ne imaginăm ca o persoană X, aflată în București, vrea să facă o călătorie la Londra. Ca să își poată atinge acest țel, X trebuie să ducă la îndeplinire cîteva acțiuni prealabile: să obțină o viză de la Ambasada Britanică, să-și cumpere bilet de avion, să-și facă bagajul, să se ducă la aeroport la data și ora precizată pe bilet, să ia avionul și, finalmente, să coboare la Londra. Aceste etape preliminare care trebuie satisfăcute pentru atingerea scopului final -- călătoria de la București la Londra -- se numesc acțiuni, și ele constituie un plan. Construirea explicită a unei succesiuni de astfel de acțiuni în vederea unui țel final oarecare este o planificare.
Pînă acum nimic nu pare să se lege de inteligența artificială. Să presupunem însă că X este un robot bucureștean, și că ne-ar place ca acest robot, în momentul în care cineva îi comandă o călătorie la Londra (sau orice altceva), să fie capabil să-și planifice singur (în sensul de mai sus) această călătorie, fără ca omul să trebuiască să-i precizeze explicit că are nevoie de o viză, de bilet, ș.a.m.d.
Planificarea în sensul inteligenței artificiale (de altfel singurul sens în care vom folosi acest cuvînt de-acum încolo) înseamnă generarea unei secvențe de acțiuni pentru un agent (de tipul unui robot) care poate schimba mediul (lumea) în care evoluează. Scopul planificării este atingerea unuia sau mai multor țeluri exprimate explicit.
O remarcă despre terminologie -- termenii ``lume'' și mediu se referă în acest articol la universul problemei de rezolvat.
În definiția de mai sus, am folosit cuvintele ``agent care poate schimba mediul în care evoluează''. Într-adevăr, dacă robotul X din exemplul dat nu e în stare să interacționeze cu lumea înconjurătoare altfel decît prin comenzile primite (nu poate să meargă sau să emită la rîndul lui cereri), atunci nici o speranță să obțină viza sau să cumpere biletul de avion, și cu atît mai puțin să se deplaseze la aeroport. Pe de altă parte, dacă robotul cu pricina știe să efectueze doar două acțiuni: să coase și să taie, oricît de ``inteligent'' ar fi el, e foarte puțin probabil să găsească o combinație de tăieturi și cusături (adică un plan bazat pe aceste două acțiuni) care să-l poarte la Londra.
Ca să recapitulăm, informația de intrare într-o problemă de planificare conține:
Înainte de a da un exemplu complet de problemă de planificare, trebuie să spunem că, pentru ca să se poată vorbi de o soluție la o astfel de problemă, lumea în care planul urmează a fi executat trebuie să fie cel puțin predictibilă, dacă nu chiar deterministă. Aceasta înseamnă, revenind la exemplul nostru, că nu luăm în considerare evenimente neașteptate de tipul aeroportul e închis, sau avionul se prăbușește la cinci minute după decolare sau avionul e deturnat de pe ruta spre Londra. Este evident că această ipoteză a unei lumi lipsite de neprevăzut este destul de departe de realitate.
În inteligența artificială (și nu numai), se obișnuiește ca, atunci cînd o problemă destul de complicată se dorește a fi rezolvată, să se caute mai întîi soluții ale ei pentru un caz particular mai simplu. Așa și cu planificarea. Ea a fost intensiv studiată pe un exemplu de-acum clasic, și anume în așa-numita lume a blocurilor. Toate obiectele în acest univers sunt cuburi de aceeași mărime. Ele pot fi așezate pe o masă (una singură în universul problemei, considerată infinită) sau unul peste celălalt. Agentul care poate modifica această lume este un robot cu un braț, cu care poate să apuce un singur bloc la un moment dat.
Iată un exemplu de stare inițială și de stare finală (de atins) în această lume (Figura 1):
| |
_|_ _|_
|----| |----| / \ |----| |----| / \
| b | | d | / \ | c | | d | / \
|----| |----| |----| |----|
| a | | c | | a | | b |
--------|----|-----|----|----- -----|----|------|----|------
Stare initiala Scop (Stare finala)
Figura 1.
Problema este cum putem reprezenta aceste configurații cu un limbaj mai apropiat de cel pe care l-ar putea înțelege un calculator. Dacă în locul robotului, cel căruia ar trebui să-i descriem aceste stări ar fi un om, și dacă am comunica cu acel om la telefon, de pildă, atunci probabil că i-am spune ceva de genul: ``starea inițială e următoarea: blocurile a și c sunt pe masă, blocul b este deasupra lui a și blocul d este deasupra lui c. Pe blocurile b și d nu mai este nici un alt bloc. Robotul nu ține nimic în mînă. Starea finală este etc.''. Ca atare, nu e o idee rea să descriem o stare în lumea blocurilor ca pe o colecție de ``fapte'' (adică afirmații adevărate în configurația respectivă).
Prin urmare, pentru a reprezenta o stare vom folosi următoarele literale:
Orice configurație din lumea blocurilor poate fi descrisă ca o mulțime sau o conjuncție (și logic) de astfel de literale. De exemplu, să vedem cum se reprezintă cele două stări din figura 1:
Starea inițială:
PE-MASA (a).
PE (b, a).
LIBER (b).
PE-MASA (c).
PE (d, c).
LIBER (d).
MINA-LIBERA.
Starea finală:
PE-MASA (a).
PE (c, a).
LIBER (c).
PE-MASA (b).
PE (d, b).
LIBER (d).
MINA-LIBERA.
Cu alte cuvinte, o stare se poate exprima printr-o colecție de fapte care sunt toate adevărate în configurația corespunzătoare ei.
Să vedem acum care sunt acțiunile elementare pe care robotul le poate duce la îndeplinire:
Fiind dată o stare inițială, robotul poate să o modifice folosind una dintre acțiunile (operatorii) de mai sus. În felul acesta, se ajunge într-o nouă configurație de blocuri care poate sau nu să fie identică cu cea finală. Dacă nu este, putem încerca să aplicăm din nou un operator, de data aceasta din noua stare în care tocmai am ajuns, și așa mai departe pînă cînd se atinge țelul urmărit. În plus, dacă ajungem într-o situație în care scopul devine de neatins (cu alte cuvinte, am ales o secvența proastă de operatori), putem oricînd să ne întoarcem la starea precedentă și să încercăm un alt operator. (Unii dintre dumneavoastră poate au identificat deja în clipa aceasta planificarea cu o căutare). Deci acțiunile oferă un mod de schimbare a lumii în care robotul evoluează.
Problema care se pune acum este să găsim un mod de a exprima tocmai schimbările pe care fiecare dintre aceste acțiuni le poate induce asupra asupra configurației curente de blocuri. Vom încerca să rezolvăm această problemă bazîndu-ne pe următoarele observații:
Într-adevăr, nu putem folosi operatorul (acțiunea) IA-DE-PE (c, a) în starea inițială din Figura 1, căci blocul c nu se află pe blocul a. Deci, pentru ca un operator să poată fi aplicat trebuie ca starea curentă să satisfacă anumite condiții, pe care le vom numi precondiții ale operatorului cu pricina.
Dacă în starea inițială din Figura 1 aplicăm de pildă acțiunea IA-DE-PE (b, a) , blocul a devine liber ; dacă însă folosim operatorul IA-DE-PE (d, c), blocul c este liber și blocul a este acoperit în continuare de b. Deci, un operator poate fi descris prin efectele (post-condițiile) sale, adică prin starea lumii după ce el a fost aplicat.
Acestea fiind spuse, un operator este unic reprezentat prin două mulțimi -- mulțimea precondițiilor sale și mulțimea post-condițiilor sale. Am spus deunăzi că post-condițiile unui operator sunt date de starea lumii după ce el a fost aplicat. Dar, în principiu, această stare depinde de starea anterioară aplicării operatorului respectiv. Într-adevăr, dacă în starea inițială din Figura 1 folosim operatorul IA-DE-PE (b, a), atunci starea în care ajungem devine cea din Figura 2:
PE-MASA (a).
| |----| PE-MASA (c).
/-|-\ | d | PE (d, c).
|----| /| b |\ |----| LIBER (d).
| a | |---| | c | IN-MINA (b).
-------|----|--------------|----|------ LIBER (a).
Figura 2.
În această nouă stare, practic nu s-a schimbat față de configurația inițială din Figura 1 decît ceea ce era legat de blocurile a și b, precum și de brațul robotului. În rest, blocurile c și d și-au păstrat configurația din starea anterioară. Deci post-condițiile unui operator cuprind, pe lîngă o descriere a felului în care operatorul respectiv modifică lumea, și faptele care au rămas neschimbate în urma aplicării operatorului respectiv. Dar acestea din urmă pot fi foarte multe (imaginați-vă că în loc de patru blocuri, am folosi cincizeci sau o mie). Prin urmare nu este convenabil să folosim în reprezentarea unui operator întreaga listă a post-condițiilor sale. Ce este de făcut?
Ne vom folosi de un mic truc. Am văzut că de fapt ceea ce este cu adevărat relevant pentru un operator este felul în care s-a schimbat starea posterioară aplicării operatorului față de starea anterioară aceluiași moment. Această schimbare este descrisă de două mulțimi: cea a condițiilor (faptelor) care devin adevărate în noua stare și cea a condițiilor care devin false după aplicarea operatorului. Putem scrie:
STARE-POST = STARE-ANTE + COND-ADAUGATE - COND-STERSE,
unde:
Ca să conchidem, un operator poate fi reprezentat prin următorul triplet:
De exemplu, operatorul IA-DE-PE (x, y) poate fi descris astfel:
IA-DE-PE (y, x)
preconditii:
LIBER (y).
MINA-LIBERA.
PE (y, x).
postconditii de adaugat:
IN-MINA (y).
LIBER (x).
postconditii de sters:
LIBER (y).
MINA-LIBERA.
PE (y, x).
Scopul nostru este să construim un planificator, adică un program capabil să construiască un plan pentru o scop și o stare inițială date, folosind niște operatori dependenți de problemă. Cum putem face acest lucru? Folosindu-ne de niște algoritmi informați de căutare. Vom încerca să explicăm ce sunt aceștia și în ce fel îi putem folosi în lunga expunere care urmează.
Planificarea este o problemă de căutare într-un spațiu al stărilor. Să vedem ce înțelegem prin această afirmație. Am văzut că în orice problemă de planificare există o stare de pornire (stare inițială) și un scop pe care dorim să-l atingem. Pentru ajunge în starea finală care satisface scopul de atins, putem folosi o mulțime de operatori. Aplicarea unuia sau altuia dintre acești operatori atrage după sine o modificare de stare. Toate stările noi care pot fi generate din starea inițială aplicînd oricare din operatorii ale căror precondiții sunt îndeplinite formează mulțimea succesorilor (stărilor succesoare) stării inițiale. În același mod putem defini mulțimea succesorilor unei stări alta decît cea inițială. Starea inițială, împreună cu toate stările care sunt succesoare unei alte stări formează un spațiu de stări. Cu alte cuvinte, un spațiu de stări este mulțimea tuturor stărilor care pot fi obținute din starea inițială aplicînd orice secvența posibilă de operatori. (Reamintim că un operator poate fi aplicat numai dacă precondițiile sale sunt îndeplinite). Starea finală este și ea o stare în acest spațiu (dacă problema are soluție). Soluția problemei de planificare este o succesiune de stări care pornește din starea inițială și ajunge în starea finală, iar secvența de operatori folosiți pentru a trece dintr-o stare în alta (pe drumul între starea inițială și cea finală) formează planul căutat. Un spațiu de stări poate fi reprezentat ca un graf în care nodurile sunt stări, iar muchiile operatori; o soluție ca o cărare în acest graf (vezi Figura 3).
stare initiala
o
/ | \
/ | \
o o o --> succesorii starii initiale
/ | / | \ \
/ | / | \ \
o o o o o ---> succesorii succesorilor starii
/ | / \ initiale
/ | / \
o o o o
stare
finala
Figura 3.
Cum se găsește soluția? Există două variante -- sau se alege o cărare anume după un criteriu oarecare și dacă la sfîrșitul cărării nu s-a ajuns în starea finală, atunci se abandonează căutarea (căutare ireversibilă); sau se explorează toate cărările pînă cînd se ajunge la o soluție (căutare exhaustivă). Ordinea de explorare este specifică fiecărui algoritm; astfel căutarea în adîncime explorează întotdeauna succesorii unei stări înainte de a-i explora ``frații'' (nodurile cu același părinte); căutarea în lățime face exact invers -- explorează mai întîi frații unui nod și apoi succesorii lui. Backtracking-ul este un caz special de căutare în adîncime.
Pentru că de cele mai multe ori spațiul stărilor este uriaș, se folosesc anumiți algoritmi de căutare informați. Acești algoritmi fac alegerea stării următoare celei curente după un criteriu legat de structura internă a stărilor candidate, care estimează apropierea acestora de soluție. În felul acesta, e posibil să se economisească timp și spațiu; însă, pe de altă, există riscul să nu se găsească o soluție pentru problema dată.
Să presupunem că am folosi pentru problema noastră o tehnică de căutare ireversibilă și informată de tipul hill-climbing (``urcuș de deal'' -- pe românește). Aceasta presupune utilizarea unei funcții euristice (de merit), care reprezintă tocmai criteriul despre care vorbeam în paragraful precedent. Iată cum arată algoritmul de hill-climbing:
Rămîne să vedem cum am putea alege o funcție de merit (euristică). Am spus că o astfel de funcție estimează apropierea unei stări de soluție; am putea deci să folosim ca euristică pentru o stare s funcția diferență dată de numărul de condiții din starea finală care nu sunt încă satisfăcute în starea s. O stare este cu atît mai bună cu cît funcția sa de merit este mai mică.
Vom vedea că această euristică este acceptabilă numai cînd condițiile ce trebuie satifăcute în starea finală sunt independente. Să considerăm un exemplu în care funcția diferență, împreună cu un algoritm hill-climbing, ratează soluția.
Fie din nou problema expusă în Figura 1. Din starea inițială putem ajunge în două stări succesoare distincte, corespunzînd aplicării operatorilor IA-DE-PE (b, a) sau IA-DE-PE (d, c). Cei doi succesori sunt descriși în Figurile 2 și 4.
PE-MASA (a).
PE (b, a).
|----| | LIBER (b).
| b | /-|-\ PE-MASA (c).
|----| /| d |\ |----| LIBER (c).
| a | |---| | c | IN-MINA (d).
-------|----|--------------|----|------
Figura 4.
Condițiile satisfăcute în starea scop din Figura 1 și nesatisfăcute în Figura 2 sunt { LIBER (c), PE (c, a), PE (d, b), PE-MASA (b), MINA-LIBERA }. Funcția diferența corespunzătoare este deci 5. În ceea ce privește starea din Figura 4, condițiile încă nesatisfăcute sunt { PE (c, a), PE (d, b), PE-MASA (b), MINA-LIBERA }, deci funcția diferența este 4. Algoritmul va alege succesorul cu cea mai mică funcție de merit, adică starea din Figura 4. Aceasta are o funcție diferența mai bună pentru simplul fapt că lasă blocul c liber, fapt de dorit în starea finală. În această nouă stare (cea din Figura 4), se pot folosi trei operatori: ASEAZA (d) sau PUNE (d, b) sau PUNE (d, c). Ultimul este exclus din start pentru că ne întoarce înapoi în starea inițială din Figura 1. Să vedem care sunt succesorii ce se pot obține prin aplicarea celorlalți doi operatori (Figura 5 și Figura 6).
|
|----| /-|-\ PE-MASA (a).
| d | / \ PE-MASA (c).
|----| PE (b, a).
| b | PE (d, b).
|----| |----| LIBER (d).
| a | | c | MINA-LIBERA.
--------|----|-----|----|-----------
Figura 5.
| PE-MASA (a).
/-|-\ PE-MASA (d).
|----| / \ PE-MASA (c).
| b | PE (b, a).
|----| |----| |----| LIBER (b).
| a | | c | | d | LIBER (c).
----------|----|----|----|----|----|----- MINA-LIBERA.
LIBER (d).
Figura 6.
Deși Figura 5 diferă prin mai puține condiții de starea finală din Figura 1 (funcție de merit 2) decît Figura 6 (funcție de merit 3), pentru un om este evident că Figura 6 este o alegere mai bună decît Figura 5 pentru atingerea stării finale din Figura 1. Algoritmul însă va prefera succesorul din Figura 5 pentru că el satisface în plus condiția PE (d, b), care apare în starea finală. El ignoră astfel faptul că această satisfacerea reală a acestei condiții depinde de fapt de condiția PE-MASA (b). Cu alte cuvinte, condițiile de îndeplinit pentru a ajunge în starea finală (numite și sub-scopuri) nu sunt independente unele de altele. În continuare, ținînd cont că algoritmul va evita ciclarea (adică trecerea printr-o stare în care a mai fost) și că el nu se va întoarce niciodată înapoi, finalmente se va ajunge în starea în care blocurile a, b, d, c formează un turn și programul se va opri fără să găsească soluția problemei.
O problemă se numește de planificare liniară dacă sub-scopurile cu care ea are de a face sunt independente. În general, foarte puține probleme intră în această categorie.
Am văzut că nu putem aplica hill-climbing-ul nici măcar pentru o problemă simplă din lumea blocurilor. Nu vom abandona însă funcția de merit pe care am ales-o (căci ea este de multe ori utilă, îmbunătățind considerabil timpul de căutare), ci vom face o căutare exhaustivă în ghidată de euristica diferență. În principal, aceasta diferă de o hill-climbing prin faptul că, dacă se ajunge la o stare blocantă (în care nu mai e nimic de făcut), algoritmul se întoarce înapoi în starea anterioară și încearcă un alt operator, chiar dacă acesta are o funcție de merit mai proastă decît cel folosit inițial. De exemplu, într-o situație în care are de ales între stările din Figura 5 și Figura 6, acest algoritm o va alege întîi pe cea din Figura 5, apoi se va întoarce înapoi și va lua în considerare cealaltă alternativă.
În secțiunea care urmează vom prezenta un algoritm (nu singurul posibil) pentru un planificator. El va folosi o căutare în adîncime ghidată de funcția de merit diferență.
Ideea algoritmului este să aleagă cel mai bun posibil succesor al stării curente S și să-l facă următoarea stare curentă Succ. Dacă Succ nu se găsește pe o cărare spre starea finală, atunci programul se întoarce în starea S și selectează al doilea cel mai bun succesor, și așa mai departe.
Algoritmul general este următorul:
function plan (StareInitiala, StareFinala)
Pasul 1. Creaza o Stiva goala cu operatorii aplicati pina acum:
StivaOp = {}
si o stiva a starilor de pe cararea in explorare:
StivaStari = { StareInitiala }.
Seteaza StareCurenta = StareInitiala.
Pasul 2. Daca StareCurenta = StareFinala, atunci
afiseaza operatorii din StivaOp in ordine inversa
(ei formeaza planul cautat);
intoarce succes.
Pasul 3. Genereaza toti succesorii posibili pentru StareCurenta
aplicind toti acei operatori ale caror preconditii sunt
indeplinite. Pastreaza intr-o coada Succs[StareCurenta]
toti acei succesori care nu apartin stivei StivaStari.
Pasul 4. Daca coada Succs[StareCurenta] nu este vida, sorteaz-o
dupa valorile ascendente ale functiei diferenta a starilor
din aceasta coada.
Pasul 5. Daca coada Succs[StareCurenta] este vida, atunci
StareCurenta ia valoarea din virful stivei
StivaStari; aceasta valoare se sterge de pe
StivaStari;
sterge virful stivei StivaOp;
du-te la pasul 5.
Pasul 6. Alege prima stare din coada Succs[StareCurenta] si fa-o
StareCurenta. Pune StareCurenta pe StivaStari si operatorul care a
generat-o in stiva StivaOp. Du-te la pasul 2.
Am folosit notația Succs[StareCurenta] pentru a desemna faptul că fiecare stare are coada ei proprie de succesori.
Algoritmul de mai sus a fost implementat în limbajul PROLOG. Listing-ul programului poate fi găsit în anexa care urmează. Programul a fost testat pentru probleme din lumea blocurilor cu 3, 4, 5 blocuri și pentru problema maimuței și a bananei, pe care o vom prezenta pe scurt. O maimuța înfometată se află închisă într-o cameră. În cameră se găsește un scaun lîngă o fereastră și un ciorchine de banane atîrnă de centrul tavanului. Maimuța este prea scundă ca să atingă bananele. Ea este capabilă de următoarele acțiuni: să se plimbe prin cameră, să împingă scaunul, să se urce pe scaun, să ia bananele (dacă ajunge la ele). Problema este să se elaboreze un plan pentru maimuța ca să mănînce bananele.
/*
* file plan.ari: planning algorithm
*/
% satisfy_conditions(Conditions, State):
%=======================================
% check whether the State has among its preconditions all the
% Conditions. Both arguments should be bound.
satisfy_conditions(Conditions, State):-
subset(Conditions, State).
% succ_state(State, Effects, NextState)
% =====================================
% compute the new state NextState in which the last applied operator
% brought us ; the NextState is the current State
% - to which we have added the effects in the add-sublist of
% Effects
% - and from which we have deleted the effects in the delete-
% sublist of Effects
succ_state(State, [], State).
succ_state(State, [add(Condition) | RestEffects], NextState) :-
succ_state(State, RestEffects, Temp),
insert_unique(Condition, Temp, NextState).
succ_state(State, [del(Condition) | RestEffects], NextState) :-
succ_state(State, RestEffects, Temp),
delete(Condition, Temp, NextState).
% plan(CurrentState, StateStack, OpStack):
%==========================================
% print out which operators for a given problem universe should be
% applied in order to reach the GoalState from a CurrentState;
% the StateStack contains the sequence of states that were already
% met; the OpStack is the sequence of operators that were applied
% (in reverse order).
plan(State, StateStack, OpStack) :-
goal(GoalState),
equal(State, GoalState), % check State = GoalState
write('Operators that were applied:'), nl,
display_stack(OpStack). % print the sequence of
% operators applied
plan(State, StateStack, OpStack) :-
choose_best_next(State, NextState, StateStack, Operator),
push(NextState, StateStack, NewStateStack),
push(Operator, OpStack, NewOpStack),
plan(NextState, NewStateStack, NewOpStack).
% choose_best_next(State, GoalState, NextState, StateStack, Operator):
%===================================================
% compute all the possible successors of the State, and chooses the
% NextState that is the closest to the GoalState; the operator applied
% to generate the best next state is returned in Operator.
choose_best_next(State, NextState, StateStack, Operator) :-
bagof(NState / Op, succ(State, StateStack, NState, Op)
, Succs), !,
quicksort(Succs, OrdSuccs),
member(NextState/Operator, OrdSuccs).
% greater(X, Y):
% ==============
% some order relation between two successor states
greater(X / OpX, Y / OpY):-
goal(Goal), !,
distance(X, Goal, Dx),!,
distance(Y, Goal, Dy),!,
Dx > Dy, !.
% succ(State, StateStack, NState, Op):
% ====================================
% compute the successor of a State in NState; the operator applied in order
% to obtain NState is returned in Op; a check is made to avoid generating
% a state already in StateStack.
succ(State, StateStack, NState, Op) :-
move(Op, Preconditions, Effects),
satisfy_conditions(Preconditions, State),
stack(X, X) \= Op,
succ_state(State, Effects, NState),
not(list_member_stack(NState, StateStack)).
% distance(State, Goal, d) :
% ==========================
% computes the distance (heuristic fun) between the State and the Goal;
% returns it in d.
distance(State, Goal, D) :- dist(State, Goal, 0, D).
dist(State, [], Acc, Acc):- !.
dist(State, [Cond | RestCond], Acc, D) :-
member(Cond, State), !,
dist(State, RestCond, Acc, D).
dist(State, [Cond | RestCond], Acc, D) :-
Acc1 is Acc + 1,
dist(State, RestCond, Acc1, D).
% go(InitialState, GoalState):
% ============================
% ask for getting from an InitialState to a GoalState.
% Both arguments should be bound.
go(InitialState, GoalState):-
asserta(goal(GoalState)),
empty(StateStack),
empty(OpStack),
push(InitialState, StateStack, NewStateStack),
plan(InitialState, NewStateStack, OpStack),
retract(goal(X)).
testblock31:-
go([handempty, ontable(b), ontable(c), on(a, b), clear(a), clear(c)],
[handempty, ontable(a), ontable(b), on(c, b), clear(a), clear(c)]).
testblock32 :-
go([handempty, ontable(b), ontable(c), on(a,b), clear(a), clear(c)],
[handempty, ontable(a), on(c,a), on(b,c), clear(b)]).
testblock33 :- /* Sussman anomaly */
go([handempty, on(c, a), ontable(b), ontable(a), clear(c), clear(b)],
[handempty, ontable(c), on(b, c), on(a, b), clear(a)]).
testblock41 :-
go([handempty, ontable(a), ontable(c), on(b, a), clear(b), on(d, c),
clear(d)],
[handempty, ontable(a), ontable(b), on(c, a), clear(c), on(d, b),
clear(d)]).
testblock42 :-
go([handempty, ontable(a), ontable(c), ontable(d), on(b, a),
clear(b), clear(c), clear(d)],
[handempty, on(c, a), ontable(a), on(b, d),
ontable(d), clear(c), clear(b)]).
testblock43 :-
go([handempty, ontable(a), ontable(c), on(b, a), on(d, b), clear(c),
clear(d)],
[handempty, ontable(b), on(d, b), on(a, d), on(c, a), clear(c)]).
testblock5:-
go([handempty, ontable(a), ontable(c), ontable(d),
on(b, a), clear(b), clear(c), on(e,d), clear(e)],
[handempty, ontable(c), on(b, a), on(a,c), clear(b),
ontable(e), on(d,e), clear(d)]).
testape :-
go([ape(door), on_the_earth, box(window), has(nothing)],
[ape(middle), on_the_box, box(middle), has(bannana)]).
testrich :-
go([poor, unknown], [rich, famous]).
/*
* file blocks.ari: operators for the planning problem in the blocks world
*/
move(
putdown(X),
[holding(X)],
[del(holding(X)),
add(ontable(X)), add(handempty)]
).
move(
pickup(X),
[handempty, clear(X), on(X, Y)],
[del(handempty), del(on(X, Y)),
add(clear(Y)), add(holding(X))]
).
move(
pickup(X),
[handempty, clear(X), ontable(X)],
[del(handempty), del(ontable(X)),
add(holding(X))]
).
move(
stack(X, Y),
[holding(X), clear(Y)],
[del(holding(X)), del(clear(Y)),
add(handempty), add(on(X,Y))]
).
/*
* file ape.ari: the problem of the ape and the banana
*/
move(
HOLDING,
[ape(middle), on_the_box, box(middle), has(nothing)],
[add(has(bannana)),del(has(nothing))]).
move(
leaping(X),
[ape(X), on_the_earth, box(X)],
[add(on_the_box), del(on_the_earth)]).
% pushing
% ========
move(
pushing(window, corner),
[ape(window), on_the_earth, box(window)],
[add(ape(corner)), add(box(corner)),
del(ape(window)), del(box(window))]).
move(
pushing(corner, middle),
[ape(corner), on_the_earth, box(corner)],
[add(ape(middle)), add(box(middle)),
del(ape(corner)), del(box(corner))]).
move(
pushing(window, door),
[ape(window), on_the_earth, box(window)],
[add(ape(door)), add(box(door)),
del(ape(window)), del(box(window))]).
move(
pushing(window, middle),
[ape(window), on_the_earth, box(window)],
[add(ape(middle)), add(box(middle)),
del(ape(window)), del(box(window))]).
% walking
% =======
move(
walking(door, window),
[ape(door), on_the_earth],
[add(ape(window)), del(ape(door))]).
move(
walking(window, middle),
[ape(window), on_the_earth],
[add(ape(middle)), del(ape(window))]).
move(
walking(corner, window),
[ape(corner), on_the_earth],
[add(ape(window)), del(ape(corner))]).
move(
walking(door, middle),
[ape(door), on_the_earth],
[add(ape(middle)), del(ape(door))]).
move(
walking(door, corner),
[ape(door), on_the_earth],
[add(ape(corner)), del(ape(door))]).
move(
walking(middle, window),
[ape(middle), on_the_earth],
[add(ape(window)), del(ape(middle))]).