i7z10zy

Un aspect important al raþionamentului de bun simþ ºi al problemelor de planificare automata este capacitatea de a reprezenta acþiuni ºi de a raþiona despre aceste acþiuni, deci de a raþiona despre schimbari. Planificarea automata, care implica utilizarea acþiunilor, reprezinta un domeniu intens investigat al inteligenþei artificiale. Cele mai multe probleme de planificare se refera la domenii complexe, pentru care reprezentarea ºi prelucrarea descrierii complete a starilor problemei de rezolvat poate deveni foarte costisitoare. Din aceasta cauza, de multe ori este nevoie sa se adopte o strategie de reprezentare parþiala a universului problemei cit ºi o strategie de descompunere a problemei in subprobleme.
Raþionamentul despre acþiuni implica rezolvarea celor trei probleme ale raþionamentului de bun simþ, menþionate in capitolul anterior: problema cadrului, problema calificarii ºi problema ramificarii. Se considera cazul unui robot care trebuie sa execute acþiunile de mutare a obiectelor dintr-o camera. Daca robotul muta masa din centrul camerei linga fereastra, un sistem de planificare automata trebuie sa fie capabil sa deduca faptul ca nici covorul ºi nici dulapul nu ºi-au schimbat poziþia, chiar daca acest lucru nu s-a spus explicit . Aceasta este problema cadrului, deci a identificarii ºi inferarii tuturor faptelor care nu s-au schimbat ca efect al executarii unei acþiuni sau a trecerii timpului. Daca robotul trebuie sa execute acþiunea de mutare a bibliotecii din camera, el ar putea sa nu reuºeasca deoarece biblioteca este prea grea, sau pentru ca ea este ancorata in podea, sau din cauza ca se darima casa, etc. Inregistrarea tuturor precondiþiilor necesare executarii unei acþiuni este de multe ori imposibila, aceasta fiind problema cadrului. Daca robotul muta dulapul dintr-un loc in altul al camerei, floarea de pe dulap va fi mutata odata cu dulapul, anumite porþiuni de covor vor fi acoperite, s-ar putea ca fereastra sa fie blocata, etc. Aceasta este problema ramificarii, deoarece este imposibil sa se inregistreze toate consecinþele unei acþiuni. Astfel, reprezentarea completa ºi explicita a tuturor starilor universului unei probleme de executare a acþiunilor in lumea reala este foarte diferita, de fapt imposibila pentru situaþii complexe. Tot datorita complexitaþii problemelor de planificare, de multe ori este indicat sa se foloseasca paradigma de rezolvare a problemelor prin descompunere in subprobleme aPearl,1988i.
Tehnicile de rezolvare a problemelor prin descompunerea problemei in subprobleme sint viabile numai in cazul problemelor pentru care subproblemele componente nu interacþioneaza intre ele, deci sint independente. Altfel spus, rezolvarea unei subprobleme nu depinde de rezolvarea altor subprobleme ºi nici nu este afectata de rezolvarea subproblemelor ulterioare ei. Din pacate, pentru numeroase probleme nu exista o descompunere in subprobleme care sa satisfaca condiþia anterior enunþata, problemele rezultate din descompunere fiind interdependente. Din mulþimea problemelor interdependente, Herbert Simon identifica problemele aproape independente ca fiind o mulþime de subprobleme, provenite din descompunerea unei probleme, intre care exista numai o interacþiune redusa. Aceasta caracteristica simplifica, intr-o oarecare masura, problema generarii automate a planurilor, dar ºi in acest caz trebuie sa se þina seama de interacþiunile existente.
Din punct de vedere al inþelesului obiºnuit, planificarea implica stabilirea unei secvenþe de acþiuni pentru atingerea unui anumit scop. In cazul rezolvarii unei probleme de planificare cu ajutorul calculatorului, distincþia intre plan ºi acþiune este mai puþin evidenta, deoarece planul propus pentru a realiza un anumit scop nu este, de cele mai multe ori, aplicat pe masura dezvoltarii sale. Chiar daca problema implica acþiuni irevocabile in lumea reala, programul de planificare poate simula planul, ceea ce permite utilizarea unei strategii tentative. Succesul acestei abordari se bazeaza pe presupunerea ca lumea reala este predictibila. Din nefericire, acest lucru nu este intotdeauna adevarat, deci procesul de simulare nu poate considera toate alternativele posibile.
Un aspect important al problemelor de planificare este tocmai acela ca lumea reala nu este intotdeauna predictibila. Un plan bine alcatuit pentru atingerea unui scop in anumite condiþii poate sa nu mai funcþioneze la apariþia unor condiþii reale diferite. Modificarea neaºteptata a contextului poate sa invalideze tot planul sau numai o parte din el. O problema importanta este aceea a refacerii planului, pastrind totodata acele parþi din plan care ramin in continuare valide. Acest aspect constituie un argument in plus in favoarea necesitaþii descompunerii problemelor in subprobleme. Pe linga reducerea complexitaþii reprezentarii ºi a procesului de rezolvare a problemelor, descompunerea problemelor in subprobleme reduce ºi complexitatea operaþiilor de revizuire dinamica a planului, operaþii necesare pe parcursul executarii unui plan intr-o lume imprevizibila. Operaþiile de revizuire a planului se executa mai uºor in cazul unor probleme independente sau aproape independente.
Aºa cum se deduce ºi din aspectele prezentate anterior, problemele de planificare ºi raþionament despre acþiuni necesita un proces de cautare. De cele mai multe ori cautarea este condusa de scopuri, deci se face pornind de la starea scop ºi determinind secvenþele de operatori care fac trecerea de la starea iniþiala la starea finala. In scopul facilitarii operaþiilor de revizuire a planului, este util sa se asocieze fiecarei acþiuni executate in cadrul unui plan motivul care a determinat apariþia acþiunii in cadrul planului. Astfel, daca intr-o noua situaþie o anumita acþiune nu mai este necesara sau valabila, utilizind o strategie de backtacking condus de dependenþe, se pot determina restul acþiunilor din plan dependente de acþiunea in cauza, deci se pot identifica astfel acþiunile care trebuie reconsiderate.
Metodele de generare automata a planurilor pot fi imparþite in doua categorii: metode de planificare liniara ºi metode de planificare neliniara. In cazul planificarii liniare, o secvenþa de scopuri este rezolvata prin satisfacerea fiecarui subscop, pe rind. Un plan generat de o astfel de metoda conþine o secvenþa de acþiuni care duce la satisfacerea primului subscop, apoi secvenþa de acþiuni necesara satisfacerii celui de-al doilea subscop, ºi aºa mai departe.
Aceasta metoda nu poate fi utilizata pentru rezolvarea problemelor de planificare in care subproblemele interacþioneaza, aºa cum se va prezenta in Secþiunile 6.3 ºi 6.4. In acest caz, trebuie utilizata o metoda de planificarea neliniara care genereaza planuri prin considerarea simultana a mai multor subprobleme obþinute din descompunerea problemei iniþiale. Planul este intii incomplet specificat ºi rafinat ulterior considerind interacþiunile existente. O astfel de metoda se numeºte planificare neliniara deoarece planul nu este compus dintr-o secvenþa liniara de subplanuri complete. Planificarea neliniara implementeaza o paradigma de rezolvare a problemelor cunoscuta in inteligenþa artificiala sub numele de strategia deciziilor aminate. Aceasta abordare este utila ºi in cazul necesitaþii revizuirii dinamice a planului.
Primele sisteme de planificare automata au fost: sistemul GPS aNewell,Simon,1963i ºi sistemul STRIPS aFikes,Nilsson,1971i, ce vor fi prezentate in Secþiunea 6.2 ºi, respectiv, Secþiunea 6.3. Sistemul de planificare liniara STRIPS a fost primul program care a dat o rezolvare problemei cadrului, la nivelul implementarii.
Sistemul de planificare independent de domeniu HACKER aSussman,1975i a fost primul program care a considerat aspecte de planificare neliniara ºi a incercat sa dea o rezolvare anomaliei lui Sussman (anomalia lui Sussman este prezentata in Secþiunea 6.3). Primul sistem de planificare neliniara a fost NOAH aSacerdoti,1975i care a inclus o imbunataþire a modalitaþilor de reprezentare a planurilor, un set extins de operatori de modificare a planului ºi care a oferit o rezolvare consistenta anomaliei lui Sussman.
Un sistem de planificare neliniara de referinþa este sistemul MOLGEN aStefik,1981a,bi, destinat planificarii experienþelor de genetica moleculara. Sistemul MOLGEN este primul program care a utilizat propagarea restricþiilor ca o tehnica centrala in planificare ºi care a introdus conceptul de planificare ierarhica. Sistemul TWEAK aChapman,1987i, care va fi prezentat in Secþiunea 6.4, este un sistem recent de planificare neliniara care utilizeaza de asemenea propagarea restricþiilor ºi, in plus, ofera o formalizare ºi o analiza a eficienþei computaþionale a planificarii automate.
6.1 Formalizarea raþionamentului despre acþiuni
S-au propus diverse modele de formalizare logica a raþionamentului despre acþiuni. In continuare, se prezinta pe scurt un model monoton ºi doua modele nemonotone ale acþiunilor. Cititorul trebuie sa remarce faptul ca raþionamentul despre acþiuni este de tip nemonoton, implica cele trei probleme discutate anterior, deci oricare din abordarile formale nemonotone prezentate in Capitolul 5 pot constitui punctul de plecare al formalizarii acþiunilor.
Abordarea monotona
Prima propunere de formalizare a raþionamentului despre acþiuni a fost facuta de McCarthy aMcCarthy,Hayes,1969i. In aceasta abordare, exista axiome explicite care indica toate faptele ce ramin valabile dupa executarea fiecarei acþiuni. Aceste axiome sint de doua tipuri: axiome ale acþiunilor care indica faptele care se schimba ca efect al unei acþiuni, ºi axiome ale cadrului care indica faptele neafectate de executarea fiecarei acþiuni.
De exemplu, fie operaþia de mutare a unui obiect executata de un robot. Daca obiectul x care se muta ºi obiectul l peste care se va pune x sint libere, mutarea obiectului x peste l va avea ca rezultat faptul ca x este deasupra lui l. Formal, acest lucru se exprima astfel: unde notaþia ps semnifica faptul ca propoziþia p este adevarata in situaþia (sau la momentul de timp) s, iar expresia se refera la situaþia (sau timpul) in care acþiunea a fost executata.
Pe linga axiomele de acest tip, care descriu acþiuni, trebuie enunþate ºi axiome care descriu faptele ce nu se schimba in urma executarii unei acþiuni, deci axiomele cadrului. De exemplu, o axioma a cadrului poate enunþa faptul, prin mutarea obiectului x peste l, poziþia celorlalte obiecte nu se modifica, astfel:

Similar, trebuie adaugate axiome ale cadrului care indica faptul ca mutarea unui obiect nu afecteaza forma sau culoarea obiectelor existente:


Abordarea monotona pune doua mari probleme. Prima problema este de ordin epistemologic ºi consta in indicarea explicita a tuturor axiomelor cadrului. Acest lucru poate deveni foarte dificil, mai ales daca axiomele cadrului sint complexe. A doua problema este complexitatea computaþionala implicata de determinarea faptelor care ramin adevarate dupa executarea unei acþiuni. Daca baza de cunoºtinþe conþine un numar mare de fapte, numarul de deducþii necesare pentru demonstrarea acestor fapte poate deveni prohibitiv de mare.
Abordarea logicii implicite
O abordare nemonotona a descrierii acþiunilor permite reprezentarea schimbarilor prin axiome explicite care indica ce fapte se modifica ºi adaugarea unei singure axiome de raþionament implicit care spune ca toate celelalte fapte nu se modifica. Folosind logica implicita a lui Reiter a1980i, o formalizare posibila este:

Aceasta axioma exprima faptul ca daca propoziþia p este adevarata in situaþia (la momentul de timp) s ºi p este in continuare consistenta dupa executarea acþiunii a, se poate infera ca p este adevarata dupa acþiunea a. Deci, atit timp cit acþiunea a nu a produs o consecinþa care sa infirme p, propoziþia p poate fi considerata adevarata.
Abordarea implicita nu prezinta dificultaþile epistemologice ale celei monotone, dar ridica in continuare problema complexitaþii computaþionale. Pentru a determina faptele adevarate dupa executarea unei acþiuni, axioma cadrului descrisa mai sus trebuie aplicata pentru fiecare fapt de interes.
Abordarea lumilor posibile
Modelul lumilor posibile poate fi utilizat in formalizarea raþionamentului despre acþiuni, aºa cum arata Ginsberg ºi Smith a1988i. In aceasta abordare, rezultatul unei acþiuni reprezinta lumea noua cea mai apropiata de lumea curenta, in care rezultatele acþiunii sint consistente. De exemplu, daca un robot muta dulapul dintr-un loc in altul al camerei, rezultatul acestei acþiuni este cea mai apropiata lume de cea curenta, in care dulapul este in noua poziþie. In aceasta lume noua, dulapul nu va mai fi in vechea poziþie, tot ce se afla in dulap ºi deasupra lui va fi in noua poziþie ºi, in plus, fereastra sau tabloul din camera pot fi blocate de dulap.
In formalizarea acþiunilor prin lumi posibile, se identifica o serie de fapte ºi axiome care se numesc restricþii ale domeniului sau propoziþii protejate, ºi despre care se ºtie ca nu pot fi modificate de nici o acþiune. Se defineºte o lume parþiala ca fiind orice colecþie consistenta de fapte ºi axiome care descrie domeniul problemei, o parte din elementele acestei lumi fiind specificate ca protejate.
Se presupune ca lumea parþiala S descrie situaþia curenta ºi ca se doreºte adaugarea mulþimii de fapte C la aceasta lume. In modelul general al lumilor posibile, adaugarea de fapte la o lume curenta nu revine la considerarea mulþimii deoarece C poate fi inconsistenta cu S. Pentru a rezolva aceasta problema, se considera submulþimi ale mulþimii . In aceste submulþimi exista restricþiile domeniului care nu pot fi eliminate. Un exemplu de astfel de elemente protejate este axioma care indica faptul ca un obiect poate fi intr-un singur loc la un anumit moment.
Definiþie. Fiind data o mulþime de formule logice S, o mulþime de elemente protejate (restricþii ale domeniului) ºi o mulþime de formule suplimentare C, o lume potenþiala pentru C in S se defineºte ca fiind orice submulþime astfel incit:
(1) . T conþine formulele din C care trebuie explicit adaugate pentru a construi noua lume.
(2) . Orice element protejat din S este pastrat in noua lume.
(3) T este consistenta.
Se observa ca "apropierea" unei lumi potenþiale pentru C in S de lumea iniþiala S este reflectata de cardinalitatea mulþimii T. Astfel, daca T1 ºi T2 sint lumi potenþiale pentru C in S, ºi , T2 este cel puþin la fel de aproape de S ca ºi T1. Aceasta observaþie conduce la definiþia noþiunii de cea mai apropiata lume potenþiala sau a lumii posibile pentru C in S.
Definiþie. Fie o mulþime de formule logice S, o mulþime de elemente protejate ºi o mulþime de formule suplimentare C. O lume posibila pentru C in S se defineºte ca fiind mulþimea astfel incit:
(1) ,
(2) ,
(3) T este consistenta,
(4) T este maximala din punct de vedere al restricþiilor (1)*(3).
Se noteaza cu L(C,S) mulþimea de lumi posibile pentru C in S.
Plecind de la aceste noþiuni, Ginsberg ºi Smith formalizeaza acþiunile dupa cum urmeaza. Fie o descriere a universului iniþial al problemei S, impreuna cu o mulþime de acþiuni A. Fiecare acþiune este definita printr-o mulþime de precondiþii p(a) ºi o mulþime de consecinþe C(a). Precondiþiile trebuie sa fie adevarate pentru a putea executa acþiunea ºi rezultatul acþiunii este adaugarea faptelor din C(a) la descrierea lumii curente. Daca p(a) ar specifica toate precondiþiile necesare acþiunii, deci ar fi completa, ar dispare problema calificarii. Daca C(a) ar fi completa, ar dispare problema ramificarii.
Fiind data descrierea lumii S ºi o acþiune a, se doreºte definirea rezultatului acþiunii a ca fiind lumea noua obþinuta prin adaugarea consecinþelor acþiunii la lumea curenta. Dificultatea consta in faptul ca lumea rezultata poate fi inconsistenta. Se defineºte rezultatul unei acþiuni a, executata in lumea S, cu consecinþele C(a), ca fiind intersecþia tuturor lumilor posibile pentru C(a) in S, ºi se noteaza aceasta mulþime cu . Daca , atunci se considera ca . Definiþia efectului unei acþiuni in termenii modelului lumilor posibile se poate extinde la definiþia rezultatului unei secvenþe de acþiuni .


Autorii formalismului descris propun algoritmi pentru generarea lumilor posibile ºi pentru selecþia celei mai apropiate lumi posibile. Din nefericire, selecþia celei mai apropiate lumi posibile nu poate fi facuta intotdeauna deoarece sint cazuri in care nu exista o relaþie de incluziune intre lumile posibile generate. Construcþia formala propusa nu poate selecta o lume intre astfel de lumi ºi trebuie sa se recurga la cunoºtinþe specifice domeniului pentru a lua o decizie. In secþiunile care urmeaza se vor prezenta soluþii computaþionale ale raþionamentului despre acþiuni care incearca sa rezolve eficient o parte din problemele aparute in modelele formale.
6.2 Sistemul General Problem Solver
Unul dintre primele sisteme de planificare propuse a fost sistemul General Problem Solver, pe scurt GPS, dezvoltat la sfirºitul anilor '50 de Alan Newell ºi Herbert Simon a1963i. Strategia de rezolvare a problemelor utilizata in GPS este analiza bazata pe modalitaþi. Ideea de baza a acestei strategii, enunþata intiia oara de Aristotel, este urmatoarea: la rezolvarea unei anumite probleme, se presupune scopul atins, i.e. problema rezolvata, ºi se analizeaza cum, prin aceasta inþelegindu-se prin ce mijloace, se poate realiza acest deziderat. Daca se constata ca exista mai multe mijloace de realizare, se va considera acel mijloc care rezolva problema cel mai uºor ºi in acelaºi timp cel mai bine. Daca, dimpotriva, se constata ca exista un singur mijloc de rezolvare a problemei, se considera acel mijloc, ºi analiza se concentreaza asupra modalitaþilor de realizare a acestuia. Cu alte cuvinte, problema iniþiala s-a descompus (transformat) intr-o noua problema. Procesul de descompunere continua pina cind problema rezultata in urma unei descompuneri nu mai poate fi redusa printr-o noua descompunere, fie datorita faptului ca este suficient de simpla pentru a nu mai constitui o problema, fie datorita inexistenþei unor mijloace de reducere. In acest din urma caz, rezolvarea problemei eºueaza. Aristotel a conjecturat ca acesta este chiar modelul de analiza aplicat de oameni in subconºtient.
Newell ºi Simon au descris acest mod de analiza folosind noþiunea de eliminare a diferenþelor. Ei au identificat problema cu mulþimea diferenþelor existente intre starea scop ºi starea iniþiala a problemei ºi rezolvarea problemei cu reducerea acestor diferenþe pina la eliminarea lor, efectuind pentru aceasta numai transformari (acþiuni) posibile in universul problemei. Transformarile sint asociate cu o mulþime de precondiþii care trebuie sa fie indeplinite intr-o stare pentru a putea aplica transformarea in starea respectiva. Ca efect al transformarii, starea problemei se modifica in conformitate cu o mulþime de efecte asociate transformarii. Asocierea unei transformari cu precondiþiile ºi efectele sale formeaza un operator. Operatorii sint specificaþi de catre proiectantul problemei.
In viziunea celor doi autori, rezolvarea unei probleme utilizind analiza bazata pe modalitaþi consta in detectarea repetata a diferenþelor intre starea curenta ºi starea scop, apoi selectarea unui operator care poate fi aplicat pentru a reduce aceasta diferenþa. In cazul in care operatorul nu poate fi aplicat in starea curenta, se creaza subscopul prin care trebuie sa se ajunga din starea curenta in starea in care operatorul selectat poate fi aplicat. Dar este posibil ca operatorul selectat, deºi a redus o parte din diferenþele dintre starea curenta ºi starea scop, sa nu produca chiar starea scop dorita. Apare in acest fel un nou subscop, acela de a ajunge din starea produsa de operator in starea scop. Daca operatorul este bine ales, rezolvarea celor doua subprobleme, corespunzatoare celor doua scopuri, poate fi mai uºoara decit rezolvarea problemei iniþiale. Deci, o problema poate fi rezolvata fie aplicind direct un operator adecvat, fie rezolvind mai intii subproblemele ridicate de indeplinirea precondiþiilor operatorului adecvat ºi executind apoi acþiunea asociata lui.
Procesul de analiza bazata pe modalitaþi poate fi aplicat impreuna cu criterii euristice care fac ca strategia sa se concentreze mai intii pe eliminarea diferenþelor mai importante dintre starea scop ºi starea curenta. Pentru aceasta se pot asocia nivele de prioritate diferenþelor, diferenþele cu prioritate mai mare fiind considerate pentru a fi eliminate mai intii.
Aºa cum s-a aratat, operatorii de eliminare a diferenþelor sint operatori de transformare a unei stari intr-o alta stare ºi includ precondiþiile pe care trebuie sa le satisfaca o stare pentru ca un operator sa fie aplicabil in acea stare. O dezvoltare ulterioara a sistemelor de planificare a abandonat ideea reprezentarii integrale a starii, formulind operatorii de eliminare a diferenþelor sub forma unor reguli in care partea stinga specifica precondiþiile operatorului, iar partea dreapta indica efectul aplicarii operatorului asupra starii curente numai in termenii modificarii acesteia. Aceasta dezvoltare va fi prezentata in Secþiunea 6.3. Motivele acestei evoluþii in reprezentarea operatorilor au fost prezentate la inceputul acestui capitol.
Sistemul GPS foloseºte o structura de date suplimentara, numita tabela de diferenþe, pentru a indexa operatorii dupa diferenþele care pot fi reduse prin aplicarea lor. Se considera in continuare exemplul robotului Robo care foloseºte analiza bazata pe modalitaþi pentru a dezvolta un plan de calatorie intre localitaþile Paris ºi Bucureºti. Exista mai multe posibilitaþi de a calatori intre cele doua oraºe ºi Robo trebuie sa selecteze o posibilitate. Operatorii pe care Robo ii are la dispoziþie sint: , , , ºi , cu precondiþiile ºi efectele specificate in continuare.
Operator Precondiþii Efect




Tabela de diferenþe asociata problemei este prezentata in Figura 6.1.

Figura 6.1 Tabela de diferenþe pentru problema planului de calatorie
Pentru a ajunge de la Paris la Bucureºti, distanþa iniþiala este mai mare de 2000 km, deci operatorul selectat este foloseºte_avion. Pentru a folosi avionul, Robo trebuie sa fie la avion. Distanþa dintre Robo ºi Orly, presupunind ca Robo se afla in centrul Parisului, este intre 1-100 km, deci Robo la avion este un subscop ce poate fi atins daca se aplica operatorul de reducere a distanþei foloseºte_taxi. Pentru a folosi taxiul, Robo trebuie sa fie la taxi, ºi cum cea mai apropiata staþie de taxiuri este la o distanþa mai mica de 1 km, Robo poate merge. Acest subscop nu necesita nici o condiþie iniþiala, deci acest subscop poate fi realizat imediat. Acelaºi raþionament se poate aplica ºi in cazul ajungerii la Otopeni, deci pentru starea rezultata prin aplicarea operatorului selectat iniþial, ºi pentru a reduce diferenþele ºi a ajunge in centrul Bucureºtiului. Procesul descris poate fi reprezentat, in linii generale, de urmatorul algoritm:
Algoritm: Analiza bazata pe modalitaþi
MEA
1. daca atunci
1.1.
1.2. intoarce SUCCES
2. Selecteaza cea mai importanta diferenþa D intre Stare ºi Scop
3.
4. repeta
4.1. daca nu mai exista nici un operator neaplicat diferenþei D atunci
4.2. altfel
4.2.1. Selecteaza un operator potrivit O pentru a reduce diferenþa D
4.2.2. Genereaza descrierile a doua stari O_START ºi O_REZULTAT
4.2.3. daca MEA ºi
MEA atunci i. ii. repeta de la 1 pina
5. intoarce INSUCCES sfirºit.
Observaþii:
* O-START este o stare in care precondiþiile operatorului O sint satisfacute, iar O-REZULTAT este starea care rezulta din aplicarea operatorului O starii O-START.
* Ordinea de selecþie a diferenþelor poate afecta drastic performanþele rezolvarii problemei. Daca diferenþele semnificative nu sint selectate inaintea celor nesemnificative, se poate investi un efort considerabil pentru realizarea unor subscopuri care s-ar fi realizat deja prin atingerea scopului principal.
Acest mod de abordare a problemelor nu este potrivit pentru rezolvarea problemelor complexe deoarece, pe de o parte, eliminarea unei diferenþe poate influenþa planul stabilit pentru eliminarea altei diferenþe ºi, pe de alta parte, tabela de diferenþe poate avea dimensiuni considerabile in cazul aplicaþiilor complexe.
6.3 Planificare liniara in sistemul STRIPS
Sistemul GPS, deºi abandonat de multe vreme, a avut un rol important in dezvoltarea ulterioara a sistemelor de planificare automata. Unul dintre sistemele care a evoluat din sistemul GPS, sistemul STRIPS (STanford Research Institute Problem Solver) aFikes,Nilsson,1971i incearca sa rezolve o parte din limitarile existente in GPS.
6.3.1 Funcþionarea sistemului STRIPS
Reprezentarea acþiunilor ºi construirea planului in sistemul STRIPS aFikes,Nilsson,1971i pleaca de la presupunerea ca domeniul problemei de rezolvat nu se schimba semnificativ prin executarea unei acþiuni. Din acest motiv, in sistemul STRIPS se reprezinta un model unic al universului problemei, care este permanent actualizat pentru a reflecta rezultatul acþiunilor executate. Starea curenta a universului problemei este descrisa printr-o mulþime de formule bine formate in logica cu predicate de ordinul I. In plus se pot indica axiome specifice domeniului. Acþiunile sint descrise in sistem prin operatori de plan care nu mai specifica integral starea curenta in care un operator poate fi aplicat, ºi starea rezultata prin aplicarea operatorului. Descrierea unei acþiuni se face specificind condiþiile in care aceasta acþiune poate fi efectuata ºi schimbarile survenite in starea problemei ca urmare a executarii acþiunii. Schimbarile generate de efectuarea acþiunii pot fi vazute ca fiind formate din doua mulþimi: o mulþime de formule ce descriu noua stare a problemei, formule care devin adevarate in urma executarii acþiunii, ºi o mulþime de formule care devin false in urma executarii acþiunii. In consecinþa, fiecare operator este definit de urmatoarele elemente:
* Acþiune care reprezinta acþiunea asociata operatorului.
* Lista Precondiþiilor ce conþine formulele care trebuie sa fie adevarate intr-o stare a problemei pentru ca operatorul sa poata fi aplicat, notata in continuare cu LP.
* Lista Adaugarilor ce conþine formulele care vor deveni adevarate dupa aplicarea operatorului, notata in continuare cu LA.
* Lista Eliminarilor ce conþine formulele care vor deveni false dupa aplicarea operatorului, notata in continuare cu LE.
Se observa ca sistemul STRIPS a preluat de la predecesorul sau ideea de a ataºa unei acþiuni o mulþime de precondiþii. Acest fapt a fost posibil datorita pastrarii analizei bazate pe modalitaþi ca strategie de rezolvare a problemelor. Dar, in loc de a reprezenta rezultatul acþiunii prin descrierea integrala a noii stari, sistemul STRIPS reprezinta numai modificarile aduse de acþiune starii curente. Acest lucru permite, pe de o parte, simplificarea descrierii ºi, pe de alta parte, rezolvarea problemei cadrului. Orice predicat (element al starii curente) care nu apare explicit in Lista Adaugarilor sau in Lista Eliminarilor unei acþiuni, este automat considerat ca fiind nemodificat de executarea acelei acþiuni.
Se considera urmatorul exemplu in lumea blocurilor, considerat un exemplu clasic in inteligenþa artificiala. Exista o suprafaþa plana, numita masa, pe care pot fi plasate cuburi ºi un numar de astfel de cuburi, de aceeaºi dimensiune, aºezate pe masa. Problema cere sa se genereze un plan de transformare a unei configuraþii iniþiale date intr-o configuraþie finala, ºtiind ca exista urmatoarele condiþii:
(1) cuburile pot fi asezate unul peste celalalt cu ajutorul braþului unui robot care este folosit pentru a muta cuburile;
(2) braþul robotului nu poate þine decit un singur bloc la un moment dat.
Acþiunile care pot fi executate de braþul robotului sint:
* reprezinta acþiunea de apucare a blocului A aflat deasupra blocului B. Pentru a executa acþiunea, braþul robotului trebuie sa fie liber ºi deasupra blocului A nu trebuie sa se afle alte blocuri.
* reprezinta acþiunea de plasare a blocului A deasupra blocului B. Pentru a executa acþiunea, braþul robotului trebuie deja sa þina blocul A iar deasupra blocului B nu trebuie sa se afle alte blocuri.
* reprezinta acþiunea de apucare a blocului A aºezat pe masa. Pentru a executa acþiunea, braþul robotului trebuie sa fie liber, blocul A trebuie sa fie aºezat pe masa ºi deasupra blocului A nu trebuie sa se gaseasca alte blocuri.
* reprezinta acþiunea de aºezare a blocului A pe masa. Pentru a executa acþiunea, braþul robotului trebuie sa þina blocul A.
Pentru a specifica condiþiile in care un operator se poate executa cit ºi rezultatul executarii acestei acþiuni, se definesc urmatoarele predicate:
* este adevarat daca blocul A se afla peste blocul B.
* este adevarat daca blocul A este aºezat pe masa.
* este adevarat daca nu exista nici un bloc aºezat deasupra blocului A.
* este adevarat daca braþul robotului þine blocul A.
* ARMEMPTY este adevarat daca braþul robotului este liber.
In plus, se specifica axiomele domeniului, deci aserþiuni logice adevarate in aceasta lume a blocurilor, cum ar fi:



Cititorul este indemnat sa indice o exprimare in limbaj natural a acestor aserþiuni. Axiomele domeniului, care nu se modifica prin executarea acþiunilor, sint indicate de proiectant.
Pentru exemplul prezentat, lista operatorilor din sistemul STRIPS este urmatoarea:
LP:
LE: CLEAR(y)*HOLD(x)
LA: ON(x,y)*ARMEMPTY
LP:
LE:
LA:
PICKUP(x) LP:
LE:
LA:
PUTDOWN (x) LP:
LE:
LA:
Se observa ca, pentru acþiuni simple, Lista Precondiþiilor este de multe ori identica cu Lista Eliminarilor, insa precondiþiile nu sint eliminate intotdeauna. De exemplu, pentru ca braþul robotului sa þina un bloc ( ), blocul nu trebuie sa aiba un alt bloc deasupra lui. Dupa ce braþul robotului apuca blocul, acesta continua sa nu aiba nici un alt bloc deasupra lui.
In Figura 6.2 se prezinta schematic, pentru o instanþa a problemei specificata anterior, tranziþia din starea iniþiala Si in starea finala Sf, prin starea intermediara S in care blocul B este liber ºi se afla pe masa, iar blocul A este þinut de braþul robotului. In figura sint reprezentate ºi descrierile celor trei stari ºi acþiunile efectuate pentru a trece dintr-o stare in alta.





ARMEMPTY
Figura 6.2 Reprezentarea starilor ºi acþiunilor in lumea blocurilor
Sinteza planului in sistemul STRIPS se face in urmatorul mod: se considera descrierea starii finale, se inspecteaza aserþiunile din starea finala care nu exista in starea iniþiala ºi se selecteaza operatorii (acþiunile) ale caror Liste de Adaugari conþin aserþiunile de interes din starea finala. Pentru a putea aplica un astfel de operator, formulele din Lista Precondiþiilor operatorului trebuie sa fie adevarate in starea curenta. Sistemul verifica validitatea precondiþiilor cu ajutorul unui demonstrator de teoreme, utilizind faptele din starea curenta ºi axiomele domeniului. Precondiþiile care nu sint indeplinite devin, la rindul lor, aserþiuni care trebuie satisfacute pentru a putea aplica operatorii. Daca toate precondiþiile sint adevarate, operatorul poate fi aplicat. Inaintea aplicarii operatorului, variabilele acestuia sint instanþiate, daca este cazul, folosind substituþiile efectuate in timpul demonstrarii precondiþiilor operatorului. Aplicarea unui operator elimina din starea curenta formulele care identifica cu o formula din Lista Eliminarilor ºi adauga formulele din Lista Adaugarilor, obþinind astfel o noua stare. Procesul continua in acest fel pina la gasirea unei secvenþe de operatori care pot transforma descrierea starii iniþiale in descrierea starii finale. Aceasta secvenþa de operatori (acþiuni) constituie planul sintetizat de sistemul STRIPS.
Un astfel de proces de rezolvare a problemei implica, evident, un proces de cautare. Realizarea precondiþiilor unei operaþii stabileºte lista de scopuri care trebuie indeplinite iar un anumit scop poate fi indeplinit in mai multe moduri. Deoarece pot exista cai de cautare care conduc la eºec, apare necesitatea unei cautari cu reveniri. Revenirea la o stare anterioara, dintr-o stare curenta obþinuta pe baza modificarilor din Lista Adaugarilor ºi Lista Eliminarilor, se face prin adaugarea la starea curenta a elementelor din Lista Eliminarilor ºi eliminarea din starea curenta a elementelor din Lista Adaugarilor. Pentru ca acest lucru sa fie posibil, este necesar sa se memoreze acþiunea (operatorul) aplicata ºi obiectele asupra careia s-a aplicat aceasta acþiune pentru fiecare stare obþinuta pe parcursul cautarii. In exemplul din Figura 6.2, pentru a reveni din starea finala Sf in starea iniþiala Si, trebuie intii eliminate efectele acþiunii , apoi efectele acþiunii . Creºterea eficienþei procesului de revenire poate fi realizata prin adaugarea unui sistem de menþinere a consistenþei datelor. Diverse versiuni de planificatoare care au evoluat din sistemul STRIPS au folosit aceasta facilitate.
Utilizarea tehnicii prezentate poate pune mai multe probleme. Prima problema este aceea a apariþiei unui ciclu in satisfacerea scopurilor. De exemplu, pentru satisfacerea scopului SC1 este necesara realizarea precondiþiei SC2, pentru satisfacerea scopului SC2 este necesara realizarea precondiþiei SC3, iar pentru realizarea scopului SC3 este necesara realizarea precondiþiei SC1. In termenii unui proces de cautare, aceasta situaþie este echivalenta cu generarea unui spatiu de cautare de tip graf, cu cicluri.
A doua problema care poate apare este problema generata de interacþiunea intre scopuri. Daca se doreºte realizarea unei liste de scopuri ºi, dupa realizarea scopurilor S1 ºi S2, la realizarea scopului S3 se produce invalidarea scopului S1, sistemul nu va putea sa satisfaca conjuncþia de scopuri . In acest caz, se spune ca exista o interacþiune a scopurilor S1 ºi S3 pe calea . Exista diverse posibilitaþi de a trata aceasta problema. Fie, daca este posibil, se reordoneaza scopurile astfel incit interacþiunea sa nu mai apara, fie se incearca gasirea unei alte soluþii in speranþa ca, pentru noile planuri, scopul S1 nu va mai fi invalidat, fie se incearca satisfacerea scopului S1, in condiþiile in care se ºtie ca scopurile S2 ºi S3 sint satisfacute. In anumite situaþii, nici una din aceste variante nu este realizabila. In plus, daca programul funcþioneaza in timp real, un scop care a fost satisfacut nu mai poate fi resatisfacut sau, pentru alte cazuri, efectul acþiunilor efectuate nu mai poate fi anulat. Un plan ce conþine o acþiune de tipul "dinamiteaza uºa" nu mai poate fi modificat daca uºa a fost efectiv aruncata in aer. Alternativ, daca intr-o secvenþa de scopuri
S1: Intra in casa.
S2: Menþine integritatea uºii. scopul S1 poate fi satisfacut alternativ prin satisfacerea fie a subscopului S11, fie a lui S12:
S11: Descuie uºa.
S12: Dinamiteaza uºa. daca subscopul S11 eºueaza ºi se executa subscopul S12, atunci scopul S2 nu mai poate fi satisfacut.
O soluþie parþiala a problemelor enunþate a fost propusa in sistemul STRIPS prin utilizarea unei stive de scopuri ºi operatori. Aceasta stiva poate fi asimilata cu lista de tip FRONTIERA folosita in tehnicile de cautare. Programul foloseºte urmatoarele structuri de date:
* lista operatorilor, fiecare operator avind asociate cele trei liste: de precondiþii, adaugari ºi eliminari;
* descrierea starii curente a universului problemei;
* stiva de scopuri ºi operatori propuºi pentru satisfacerea acestor scopuri;
* lista scopurilor nesatisfacute pe calea curenta.
Se considera din nou exemplul lumii blocurilor ºi urmatoarea instanþa a problemei de planificare in aceasta lume: se cere gasirea unui plan de acþiuni pentru a ajunge din starea iniþiala Si in starea finala Sf, descrierile acestor stari fiind indicate in Figura 6.3, iar operatorii posibili fiind cei specificaþi anterior.





ARMEMPTY
Figura 6.3 O problema de planificare in lumea blocurilor
In continuare, se va utiliza prescurtarea OTAD pentru conjuncþia de scopuri ONTABLE(A)*ONTABLE(D), deoarece aceste scopuri ale starii finale sint deja indeplinite in starea iniþiala. In funcþie de ordinea de satisfacere a scopurilor, din starea iniþiala se pot crea doua stive de scopuri:
Stiva 1 Stiva 2



Se presupune ca se incepe cu investigarea alternativei Stiva 1 (alternativa Stiva 2 va gasi mai repede soluþia, dar nu pune in evidenþa problemele menþionate anterior). Sistemul STRIPS va executa paºii urmatori.
1. Se incearca satisfacerea scopului . Operatorul potrivit este . Acest operator inlocuieºte scopul in stiva, deoarece daca se aplica acest operator, rezultatul lui va fi sigur , deci satisfacerea scopului dorit. Conþinutul stivei devine:
/* pentru realizarea scopului */


2. Pentru a putea aplica operatorul trebuie indeplinite precondiþiile lui, acestea devenind la rindul lor scopuri ºi introducindu-se in stiva:
/* precondiþiile operatorului */





Ordinea de introducere a scopurilor in stiva este importanta. Se pot aplica diverse euristici pentru a ordona aceste scopuri. In cazul de faþa, a fost aplicata euristica conform careia, pentru a putea executa alte acþiuni, robotul trebuie sa aiba braþul liber, deci este bine ca scopul sa fie lasat ultimul.
3. Se verifica scopul . Acest scop nu este satisfacut in starea Si datorita axiomei

Se incearca satisfacerea scopului prin aplicarea operatorului , care va inlocui scopul in stiva. Stiva rezultata este:


ARMEMPTY







4. Scopul este satisfacut de starea iniþiala ºi se elimina din stiva. La fel scopurile ºi ARMEMPTY. Se face reverificarea precondiþiilor pentru operaþia , pentru a evita situaþia in care satisfacerea unui scop ar fi invalidat un alt scop. Conjuncþia de scopuri este satisfacuta, deci se elimina din stiva. In aceste condiþii se poate aplica operatorul ºi se modifica starea curenta Si, obþinindu-se noua stare S1 ºi planul indicat in continuare.


Stiva devine:





Pentru a putea realiza , se pot aplica doi operatori: ºi , deci exista doua ramuri alternative ale arborelui de cautare. Daca s-ar urmari alternativa atunci rezultatul ar fi:





ARMEMPTY

/* satisface */




Se observa ca apare o satisfacere circulara a scopurilor, in acest caz a scopului , deci aceasta cale trebuie abandonata.
6. Se alege deci prima alternativa, iar stiva devine:


ARMEMPTY

/* satisface */



.
7. In starea S1, scopurile ºi sint adevarate dar ARMEMPTY nu este adevarat datorita axiomei

Pentru a satisface scopul ARMEMPTY, exista doi operatori posibili: ºi . Aplicind o euristica de alegere, de exemplu euristica distanþei faþa de scopul iniþial, se va alege . Se pot alege ºi alte instanþieri pentru x ºi y, dar precondiþia a scopului este satisfacuta numai pentru , iar instanþa este cea mai aproape de scopul iniþial. Stiva devine:










Precondiþiile operatorului sint indeplinite in starea S1, deci operatorul poate fi aplicat ºi se face tranziþia in starea S2.


Procesul continua ºi se descopera starea finala S4 ºi planul care conduce in aceasta stare:


Ce se intimpla insa in cazul in care se aplica aceasta metoda pentru rezolvarea urmatoarei probleme, cunoscuta ºi sub numele de "anomalia lui Sussman" aSussman,1975i. Fie o alta instanþa a problemei de planificare in lumea blocurilor, descrisa anterior, in care starea iniþiala ºi starea finala sint cele prezentate in Figura 6.4.




ARMEMPTY
Figura 6.4 Anomalia lui Sussman
Se considera in continuare funcþionarea sistemului STRIPS pentru aceasta problema. Considerarea scopurilor de satisfacut pentru ajungerea in starea finala poate genera urmatoarele doua stive:
Stiva 1 Stiva 2



Pornind cu ordonarea scopurilor din Stiva 1, se genereaza secvenþa de operatori care determina tranziþia din starea iniþiala Si in starea Sk:



In starea Sk, scopul este realizat, scopul este eliminat din stiva ºi se trece la indeplinirea scopului . Pentru satisfacerea acestui scop, trebuie ca blocul A sa fie mutat pe masa, pentru a putea realiza mutarea blocului B peste blocul C. In momentul in care s-a realizat scopul , s-au mai aplicat in plus operatorii care au determinat tranziþia din starea Sk in starea St:



Deoarece scopul este satisfacut in starea St, se elimina acest scop din stiva; in stiva ramine conjuncþia de scopuri care nu este satisfacuta, deºi scopul fusese iniþial satisfacut. Scopul a fost invalidat datorita realizarii scopului . Diferenþa intre starea curenta ºi starea scop este acum . Acest scop este adaugat in stiva ºi satisfacut, prin aplicarea a inca doi operatori, care determina tranziþia din starea St in starea Sf:


In acest moment, scopul compus este din nou verificat, ºi de aceasta data este satisfacut. Planul complet care a fost sintetizat este:

Deºi acest plan va realiza scopul propus, el nu este deosebit de eficient. O situaþie similara apare ºi in cazul in care se porneºte din varianta Stiva 2. Metoda utilizata in sistemul STRIPS nu este capabila sa gaseasca o soluþie eficienta pentru aceasta problema. Dificultatea este generata de faptul ca nu exista nici o combinaþie de planuri care, rezolvind separat cele doua subscopuri, sa rezolve ºi conjuncþia celor doua subscopuri.
Pentru a genera un plan eficient exista doua abordari posibile. Prima abordare este aceea de a prelua planul existent ºi de a-l imbunataþi, de exemplu prin eliminarea operaþiilor care executa o acþiune pentru ca apoi sa o anuleze imediat. Pornind de la acest criteriu se pot elimina operatorii 4 ºi 5 ai planului, apoi, aplicind acelaºi criteriu pe planul rezultat, se elimina operatorii 3 ºi 6. Deci planul imbunataþit va fi format numai din operatorii 1, 2, 7, 8, 9, 10. Aceasta abordare poate fi deosebit de dificila pentru probleme complexe, in care operatorii care interfereaza sint separaþi prin secvenþe lungi de operatori. In plus, in procesul de construire a planului s-a pierdut deja o mare parte de timp pentru descoperirea acestor operatori nenecesari, ºi care au fost ulterior eliminaþi.
O alta posibilitate este utilizarea unei metode de planificare neliniara. Metoda prezentata in aceasta secþiune este o metoda de planificare liniara, in care programul incearca satisfacerea scopurilor la rind, unul dupa altul, deci liniar. Pentru eliminarea anomaliei lui Sussman este necesar ca programul sa ia in considerare, simultan, mai multe scopuri care interacþioneaza, deci sa execute o planificare neliniara. O astfel de abordare se va prezenta in Secþiunea 6.4.
6.3.2 Soluþii de implementare
In aceasta secþiune se prezinta un algoritm de funcþionare a sistemului STRIPS, impreuna cu implementarea sa in limbajul Lisp. Algoritmul utilizeaza urmatoarele structuri de date:
* Variabila S care memoreaza descrierea starii curente a universului problemei;
* Stiva care memoreaza stiva de scopuri satisfacute pe calea curenta de cautare;
* Scopuri care pastreaza lista scopurilor nesatisfacute pe calea curenta;
* Structura Operator avind cimpurile Acþiune, Precondiþii, ListaAdaugari ºi ListaEliminari.
Algoritm: Planificare liniara in STRIPS
SatisfacereScopuri (Scopuri, S, Stiva)
1. pentru fiecare executa
1.1.
1.2. daca atunci intoarce INSUCCES
2. daca toate scopurile din Scopuri sint satisfacute in starea StareNoua atunci intoarce StareNoua
3. altfel intoarce INSUCCES sfirºit.
RealizeazaScop (Scop S, Stiva)
1. daca Scop este marcat satisfacut in starea S atunci intoarce S
2. daca atunci intoarce INSUCCES
3.
4. pentru fiecare operator executa
4.1.
4.2. daca atunci
4.2.1. Marcheaza scopul Scop satisfacut in starea S
4.2.2. intoarce StareNoua
5. intoarce INSUCCES sfirºit.
AplicaOperator (Operator, Stare, Stiva)
1.
2. daca atunci
2.1. executa
2.2.
2.3. intoarce
3. altfel intoarce INSUCCES sfirºit.
Observaþii:
* In algoritm, referirea cimpurilor structurii unui operator se face cu ajutorul operatorului ..
* In pasul 3 al subprogramului RealizeazaScop operatorii din mulþimea OperatoriValizi sint acei operatori care pot satisface scopul Scop, deci care conþin Scop in cimpul ListaAdaugari.
Implementarea in limbajul Lisp a algoritmului prezentat anterior este descrisa in continuare. Variabila speciala *OPERATORI* memoreaza operatorii de rezolvare a problemei, fiecare operator fiind o structura Lisp avind cimpurile actiune, preconditii, lista-adaugari ºi lista-eliminari. Acþiunea fiecarui operator este reprezentata de o lista cu doua elemente, primul dintre acestea fiind atomul Lisp EXECUTA, al doilea fiind acþiunea asociata operatorului. Valoarea variabilei *OPERATORI* este stabilita prin apelul funcþiei utilizeaza cu parametrul lista de operatori specifici unei anumite probleme. Funcþia satisfacere-scopuri satisface fiecare scop din lista de scopuri primita ca parametru, asigurindu-se ca dupa satisfacerea tuturor scopurilor acestea sint in continuare satisfacute. Funcþia realizeaza-scop este cea care satisface un scop intr-o stare a problemei. O stare S a problemei este reprezentata printr-o lista formata din atomi Lisp, atomi ai caror nume descriu in limbaj natural trasaturile starii S, ºi acþiunile operatorilor executaþi pina la ajungerea in starea S. Un scop este reprezentat printr-un atom Lisp ºi este satisfacut intr-o stare a problemei daca el se afla inclus in starea problemei sau daca exista un operator potrivit prin aplicarea caruia scopul este inclus in starea problemei, i.e. scopul se afla inclus in lista de adaugari a operatorului. Funcþia aplica-operator intoarce o noua stare a problemei daca operatorul primit ca parametru este aplicabil, i.e. toate precondiþiile sale sint satisfacute. Noua stare a problemei este obþinuta din precedenta stare modificata in conformitate cu lista de eliminari ºi lista de adaugari ale operatorului in care se adauga acþiunea operatorului. Predicatul potrivit-p verifica daca un operator este potrivit pentru satisfacerea unui scop, verificind daca scopul se afla in lista de adaugari a operatorului. Funcþiile extrage, sterge ºi subsetp sint funcþii auxiliare ºi se regasesc in majoritatea implementarilor limbajului Lisp. Funcþia extrage primeºte ca parametri un element, o secvenþa ºi o funcþie de test ºi intoarce lista elementelor din secvenþa care sint similare elementului, potrivit testului efectuat cu funcþia de test, fara a altera secvenþa. Funcþia sterge primeºte ca parametri o funcþie de test ºi o lista ºi intoarce lista din care au fost indepartate toate elementele pentru care rezultatul testului efectuat cu funcþia de test a fost adevarat. Predicatul subsetp primeºte doua secvenþe ºi verifica daca elementele primului parametru se regasesc, in totalitate, printre elementele celui de-al doilea parametru.
(defvar *OPERATORI* nil

(defstruct operator
(actiune nil) (preconditii nil) (lista-adaugari nil) (lista-eliminari nil))

(defun strips (stare scopuri &optional (*OPERATORI* *OPERATORI*))
(sterge #'atom (satisfacere-scopuri (cons '(START) stare) scopuri nil)))

(defun satisfacere-scopuri (stare scopuri stiva-scopuri)
(let ((stare-curenta stare))
(when
(and (every #'(lambda (scop)
(setf stare-curenta (realizeaza-scop stare-curenta scop stiva-scopuri))) scopuri)
(subsetp scopuri stare-curenta :test #'equal)) stare-curenta)))

(defun realizeaza-scop (stare scop stiva-scopuri)
(cond ((member scop stare :test #'equal) stare)
((member scop stiva-scopuri :test #'equal) nil)
(t (some #'(lambda (operator)
(aplica-operator stare scop operator stiva-scopuri))
(extrage scop *OPERATORI* #'potrivit-p)))))

(defun aplica-operator (stare scop operator stiva-scopuri)
(let ((stare2 (satisfacere-scopuri stare
(operator-preconditii operator)
(cons scop stiva-scopuri))))
(when stare2
(append (sterge #'(lambda (x)
(member x (operator-lista-eliminari operator) :test #'equal)) stare2)
(list (operator-actiune operator))
(operator-lista-adaugari operator)))))

(defun potrivit-p (scop operator)
(member scop (operator-lista-adaugari operator) :test #'equal))

(defun utilizeaza (lista-operatori)
(length (setf *OPERATORI* lista-operatori)))

(defun extrage (element secventa functie-test)
(delete nil (mapcar #'(lambda (i) (when (funcall functie-test element) i)) secventa)))

(defun sterge (functie-test lista)
(delete nil (mapcar #'(lambda (elem) (unless (funcall functie-test elem) elem)) lista)))

(defun subsetp (subset set &rest args)
(every #'(lambda (element) (apply #'member element set args)) subset))
In continuare vor fi prezentaþi operatorii de rezolvare a unei probleme clasice, problema maimuþei ºi a bananei, prezentata in Secþiunea 5.5.1, cu urmatoarea ipoteza simplificatoare: in camera exista un singur cub ºi o singura banana. Poziþia maimuþei in interiorul camerei este specificata prin atomii Lisp la-usa, sub-banana, pe-podea, pe-cub, linga-banana ºi in-camera. Poziþia cubului in interiorul camerei este specificata prin atomii cub-la-usa ºi cub-sub-banana, iar starea maimuþei este descrisa prin atomii are-minge, are-banana, miini-libere, maimuta-flaminda ºi maimuta-satula. Starea problemei la un moment dat este definita prin poziþia maimuþei, poziþia cubului ºi starea maimuþei. Acþiunile pe care maimuþa le poate realiza sint: urca-pe-cub, impinge-cub-de-la-usa-sub-banana, merge-la-usa, merge-de-la-usa-sub-banana, apuca-banana, arunca-minge ºi maninca-banana.
(defparameter *operatori-maimuta*
`(,(make-operator
:actiune '(executa urca-pe-cub)
:preconditii '(cub-sub-banana sub-banana pe-podea)
:lista-adaugari '(linga-banana pe-cub)
:lista-eliminari '(sub-banana pe-podea)) ,(make-operator
:actiune '(executa impinge-cub-de-la-usa-sub-banana)
:preconditii '(cub-la-usa la-usa)
:lista-adaugari '(cub-sub-banana sub-banana)
:lista-eliminari '(cub-la-usa la-usa)) ,(make-operator
:actiune '(executa merge-la-usa)
:preconditii '(in-camera pe-podea)
:lista-adaugari '(la-usa)
:lista-eliminari nil) ,(make-operator
:actiune '(executa merge-de-la-usa-sub-banana)
:preconditii '(la-usa pe-podea)
:lista-adaugari '(sub-banana)
:lista-eliminari '(la-usa)) ,(make-operator
:actiune '(executa apuca-banana)
:preconditii '(la-banana miini-libere)
:lista-adaugari '(are-banana)
:lista-eliminari '(miini-libere)) ,(make-operator
:actiune '(executa arunca-minge)
:preconditii '(are-minge)
:lista-adaugari '(miini-libere)
:lista-eliminari '(are-minge)) ,(make-operator

:actiune '(executa maninca-banana)
:preconditii '(are-banana)
:lista-adaugari '(miini-libere maimuta-satula)
:lista-eliminari '(are-banana maimuta-flaminda))))
Stabilirea contextului ºi rezolvarea problemei particulare se realizeaza prin apelurile:
(utilizeaza *operatori-maimuta*)
(strips '(in-camera pe-podea are-minge maimuta-flaminda cub-la-usa)
'(maimuta-satula))
6.4 Planificare neliniara in sistemul TWEAK
Exemplul lui Sussman prezentat in secþiunea anterioara a pus in evidenþa faptul ca satisfacerea conjuncþiilor de scopuri care interacþioneaza poate crea dificultaþi in sinteza planului. Pentru anumite probleme, nu se poate garanta existenþa unei ordonari conjuncþiei de scopuri, in care planurile pentru realizarea unor scopuri sa nu interfereze cu planurile pentru realizarea celorlalte scopuri. Un plan eficient pentru rezolvarea problemei din exemplul lui Sussman ar putea fi urmatorul:
(1) Incepe lucrul pentru satisfacerea scopului prin eliberarea blocului A ºi aºezarea blocului C pe masa.
(2) Realizeaza scopul prin aºezarea blocului B peste blocul C.
(3) Realizeaza restul operaþiilor pentru satisfacerea scopului prin aºezarea blocului A peste blocul B.
Un astfel de plan nu poate fi sintetizat printr-o metoda de planificare liniara, cum ar fi cea utilizata in sistemul STRIPS. In schimb, el poate fi realizat printr-o metoda de planificare neliniara. Primul sistem de planificare neliniara a fost sistemul NOAH aSacerdoti,1974i. Ideea importanta a acestui sistem este aceea ca un plan, in timp ce este construit, nu trebuie sa specifice complet ordinea de executare a operaþiilor. Cu alte cuvinte, un plan specifica numai o ordine parþiala a operaþiilor lui, cel puþin pina in momentul in care planul este complet.
Sistemul de planificare neliniara TWEAK aChapman, 1987i, este un sistem de planificare independent de domeniu care foloseºte ca tehnica centrala a planificarii neliniare, inregistrarea restricþiilor. Utilizarea restricþiilor in rezolvarea problemelor de planificare a fost introdusa pentru prima oara de sistemul MOLGEN aStefik,1981a,bi.
Inregistrarea restricþiilor este procesul de definire a unui obiect, un plan in acest caz, prin specificarea incrementala a descrierilor parþiale (restricþiilor) pe care obiectul trebuie sa le satisfaca. Alternativ, inregistrarea restricþiilor poate fi vazuta ca o strategie de cautare in care se elimina succesiv porþiuni din spaþiul de cautare prin adaugarea unor restricþii. Restricþiile exclud stari ºi cai de cautare din acest spaþiu, pina ce, in final, toate alternativele ramase sint satisfacatoare. Avantajul tehnicii de inregistrare a restricþiilor consta in faptul ca proprietaþile obiectului cautat, i.e. ale planului, nu trebuie alese pina in momentul in care nu exista un motiv pentru alegerea acestora. Aceasta reducere a selecþiilor arbitrare determina de multe ori o reducere a numarului de reveniri necesare in procesul de cautare. Inregistrarea restricþiilor utilizata in sistemul TWEAK este o paradigma a strategiei deciziilor aminate de rezolvare a problemelor.
Sistemul TWEAK este primul sistem de planificare automata care prezinta o definire formala a planului ºi a corectitudinii unui plan. Autorul sistemului construieºte o formalizare matematica a principiilor planificarii neliniare. In acelaºi timp, sistemul este implementat intr-o varianta funcþionala. Din punct de vedere conceptual, sistemul TWEAK este construit din trei nivele:
* nivelul de reprezentare a planului;
* nivelul de modificare a planului pentru a obþine un plan care realizeaza scopul problemei;
* structura de control generala.
In continuare se vor prezenta elementele constructive ºi funcþionarea sistemului TWEAK, iar in final se vor descrie aspectele de baza ale formalizarii planificarii neliniare ºi limitarile sistemului.
6.4.1 Reprezentarea planului
Un plan dezvoltat de sistemul TWEAK este alcatuit dintr-o secvenþa de paºi de plan (operatori, acþiuni). Un pas de plan este reprezentat prin acþiunea care trebuie executata, o mulþime finita de precondiþii (echivalenta cu lista precondiþiilor din sistemul STRIPS) ºi o mulþime finita de postcondiþii. Analog sistemului STRIPS, mulþimea efectelor unei acþiuni, deci postcondiþiile, este alcatuita din Lista Adaugarilor ºi Lista Eliminarilor. Precondiþiile reprezinta aserþiuni despre starea curenta a problemei care trebuie sa fie adevarate pentru ca acþiunea sa poata fi executata. Postcondiþiile reprezinta aserþiunile validate ºi invalidate ca efect al executarii pasului de plan. Precondiþiile ºi postcondiþiile sint exprimate prin formule atomice in logica cu predicate de ordinul I, negate sau nu, care accepta ca argumente constante ºi variabile. Simbolurile funcþionale, operatorii ºi cuantificatorii sint interzise in precondiþii ºi postcondiþii. Postcondiþiile corespunzatoare aserþiunilor validate de o acþiune sint reprezentate prin formule atomice nenegate, iar cele corespunzatoare aserþiunilor invalidate de o acþiune, prin formule negate. Se observa ca puterea de reprezentare a sistemului TWEAK este echivalenta cu cea a sistemului STRIPS. In ambele cazuri, aceste restricþii restring capacitaþile generale de modelare a universului problemei, aºa cum se va discuta in Secþiunea 6.4.3.
Considerind lumea blocurilor ºi operatorii de plan definiþi in Secþiunea 6.3.1, o reprezentare a doi dintre aceºti operatori este urmatoarea, reprezentarea celorlalþi operatori obþinindu-se analog.
Acþiune:
Precondiþii:
Postcondiþii:
Acþiune: PICKUP(x)
Precondiþii:
Postcondiþii:
In timpul activitaþii de planificare, starea problemei este reprezentata printr-o mulþime de formule, considerate conjunctiv, de tipul celor descrise anterior. Pe masura ce se executa paºi de plan, starea problemei se modifica. Reprezentarea este similara cu cea din sistemul STRIPS. Un plan are asociate o stare iniþiala, i.e. starea problemei in momentul inceperii executarii planului, ºi o stare finala, i.e. starea problemei la terminarea executarii planului. Asemanator, pentru fiecare pas al planului se definesc starea de intrare, respectiv starea de ieºire, ca fiind mulþimile de formule adevarate la inceperea, respectiv la terminarea executarii pasului de plan. Chapman, autorul sistemului TWEAK, numeºte starile din sistem situaþii.
Sistemul TWEAK a preluat ºi imbunataþit ideea sistemului NOAH de a dezvolta planuri in care ordinea de executare a operatorilor nu este specificata complet. Pe parcursul procesului de rezolvare a problemei, sistemul TWEAK dezvolta un plan incomplet. Un plan incomplet este o descriere parþiala a unui plan capabil sa rezolve problema propusa. Informal, in fiecare moment, sistemul TWEAK are la dispoziþie o mulþime utila de paºi de plan, dar nu are o idee clara asupra modului in care va trebui sa ordoneze in final aceasta mulþime de ac&th