In acest paragraf se vor analiza urmaroarele aspecte:

• Principii de elaborare a planificatoarelor
• Definirea domeniilor si a actiunilor
• Strategii de elaborare a planelor
• Folosire
• Exemple

Principii de elaborare a planificatoarelor(sus)

Prima idee de baza in planificare este de a cunoaste reprezentarea starilor telurilor si a actiunilor. Algoritmii de planificare folosesc descrieri in mai multe limbaje formale. Starile si telurile sunt reprezentate printr-o multime de propozitii, actiunile fiind reprezentate printr-o descriere logica a preconditiilor si a efectelor. Aceasta reprezentare permite planificatorului sa faca legaturi directe intre stari si actiuni.

A doua idee de baza in planificare este ca planificatorul este liber sa adauge actiuni planului oriunde este nevoie, mai degraba decat a le plasa intr-o ordine incrementala incepand cu starea initiala. De exemplu daca un agent doreste sa bea lapte, el poate decide sa cumpere laptele, chiar inainte de a decide de unde sa cumpere, cum sa ajunga acolo, sau ce sa faca dupa aceea. Nu este necesara o corelare intre ordinea de planificare a pasilor si ordinea de executie. Luand mai intai decizii "evidente" sau "importante", planificatorul poate reduce factorul de ramificare pentru optiunile urmatoare si reducand astfel nevoia de a reconsidera anumite actiuni arbitrare.

A treia idee importanta care sta la baza planificarii este aceea ca multe parti ale lumii sunt independente de altele. Aceasta face posibil sa consideram teluri in mod conjunctiv, cum ar fi " cumpara o sticla de lapte si o ciocolata si o bicicleta" si rezolva aceasta printr-o strategie de divide si cucereste. Algoritmii bazati pe strategia divide si cucereste sunt eficienti pentru ca aproape de fiecare data este mai usor sa rezolvi mai multe subprobleme decat o problema mai mare.Oricum, strategia divide si cucereste esueaza in situatiile in care costul combinarii solutiilor subproblemelor este prea mare.

Domeniile de planificare in acest SNLP sunt definite folosind limbajul STRIPS, aplicand principiile descrise mai sus. Acest limbaj determina o eficientizare a algorimilor. O problema de planificare este reprezentata prin expresii logice care descriu cele trei parti principale ale unei probleme :

• Stare initiala: o expresie logica referitoare la o anumita situatie.
• Teluri: o intrebare necesitand un anumit context, pe care planificatorul trebuie sa il realizeze.
• Operatori: o multime de descrieri de actiuni.

Definirea domeniilor si a actiunilor(sus)

Operatorii sunt specificati printr-o sintaxa predefinita. Formatul pentru a defini un operator este dupa cum urmeaza:

(defstep :action `(<nume-operator> <parametru1>...<parametrun>)
:preconditie `(<lista de propozitii care trebuie satisfacute pentru ca actiunea sa fie realizabila>)
:add `(<lista de propozitii care vor deveni adevarate dupa aplicarea operatorului >)
:delete `(< lista de propozitii care vor deveni false dupa aplicarea operatorului>)
:equals `(<lista aditionala de constranderi asupra variabilelor continant relatii de egalitate si inegalitate >))

Sa consideram un exemplu de domeniu pentru un o problema de planificare a unui robot, definind urmatoarele rutine.

(defun Robot-world ()
(reset-domain) ;elimina domeniul vechi prealabil definirii unui nou domeniu

;; definirea unui pas care permite robotului sa treaca pe usa

(defstep :action '(go-thru-dr ?x ?y ?z)
:precond '((is-room ?y) (connects ?x ?y ?z) (is-door ?x)
(dr-open ?x) (arm-empty) (next-to robot ?x)
(in-room robot ?z))
:add '((in-room robot ?y))
:dele '((in-room robot ?z) (next-to robot ?w))
:equals '((not (?x ?y)) (not (?x ?z)) (not (?y ?z))
(not (?x robot)) (not (?y robot)) (not (?z robot))
(not (?w ?y)) (not (?w ?z) ) (not (?w robot))))

;; definiprea unui pas care permite robotului sa mearga la o usa

(defstep :action '(goto-dr ?x ?y)
:precond '((is-door ?x) (connects ?x ?z ?y) (in-room robot ?y))
:add '((next-to robot ?x))
:dele '((next-to robot ?w))
:equals '((not (?x ?y)) (not (?x ?z)) (not (?y ?z))
(not (?x robot)) (not (?y robot)) (not (?z robot))
(not (?w robot)) (not (?w ?x)))))

O data ce un domeniu este definit, se defineste problema prin doua liste, reprezentand un set de conditii initiale, respectiv o multime de teluri. Problema poate fi definita dupa cum urmeaza:

(defun <nume-problema> ()
(<numele-functiei-care-descrie-operatorul>)
(plan `(<stare-initiala>)
`(<stare-finala>)
:rank-fun #'<numele-functie- folosite>))

Unde, rank-fun este o functie euristica care ghideaza cautarea planificatorului, in program (snlp.lisp) sunt declarate mai multe astfel de functii, cum ar fi DF-RANK (plan),RANK1 (plan),RANK2 (plan).

Planificatorul va returna doua valori: un plan si un obiect statistic.Pentru ambele structuri sunt definite functii specifice de afisare

De asemenea sunt definite urmatoarele variabile, care sunt folosite ca indicatori.

PLAN-UTILS:*SEARCH-LIMIT* - Limiteaza numarul planelor pe care planificatorul le va produce in incercarea de a rezolva problema, folosit pentru a evita cicluri infinite

PLAN-UTILS:*VERBOSE* -

• T - daca vrem sa afiseze intreg planul(implicit).
• NIL - pentru forma scurta.
  
  

Strategii de elaborare a planelor(sus)

Un drum prin spatiul solutiilor incepand cu starea initiala la starea tel constituie un plan. Pentru o problema descrisa intr-un limbaj STRIPS, un plan se poate obtine incepand cu starea initiala si aplicand operatori, cate unul in fiecare pas, pana obtinem un pas care satisface toate constrangerile telului. Un algoritm care realizeaza asa ceva va rezolva problema, si il putem considera un planificator, si il putem numi planificator in spatiul situatiilor pentru ca va cauta prin spatiul situatiilor. Un astfel de planificator este progresiv daca va cauta de la starea initiala spre tel. Problema pricipala a unui asemena planificator este ca are un factor de ramificare mare in spatiul de cautare.

Un mod de a reduce factorul de ramificare este de a cauta inapoi, de la tel spre starea initiala, cu o astfel de cautare avem un planificator regresiv. O astfel de abordare este posibila datorita faptului ca operatorii contin suficiente informatii pentru a regresa de la o descriere partiala a unei stari rezultat la o descriere partiala inainte ca un operator sa fie aplicat. Nu putem obtine o descriere completa a starii in acest mod. dar nici nu este necesar. O astfel de abordare este de dorit deoarece starea tel are cateva conjunctii, fiecare cu doar cativa operatori, in schimb starea initiala are semnificativ mai multi opearatori. Din nefericire, cautand inapoi este mai complicat deoarece, intr-un anumit sens, trebuie sa atingem o conjunctie de teluri, nu doar unul. Algoritmul STRIPS original era unul regresiv care nu era complet, adica se putea sa nu gaseasca un plan chiar daca exista unul. Aceasta eroare aparea datorita faptului ca avea un mod neadecvat de a manipula conjunctii complicate de teluri, rezolvand aceasta incompletitudine facea planificatorul ineficient.
O alternativa este sa se caute in spatiul planelor si nu in cel al situatiilor. Pentru aceasta vom incepe cu un plan simplu, incomplet, pe care il numim plan partial. Pe urma se cauta moduri de a extinde acest plan pana vom obtine unul complet, care rezolva problema. Operatorii in aceasta strategie de cautare sunt operatori pe plane, si anume : adaugare pas, impunerea unei canstrangeri de ordine asupra pasilor, etc . Solutia este planul final, si calea de a-l atinge este irelevanta. Aceasta ultima varianta fiind aplicata pentru cautarea unui plan in programul dat (snlp.lisp).

Folosire(sus)

Pogramul a fost rulat sub versiunea GCL (GNU Common Lisp) v 2.5.0., varianta pentru sistemul de operare Mandrake 9.2. Programul va furniza printre datele rezultat timpul CPU necesar obtineerii planului. Acesti timpi obtinuti prin rulare unor exemple sunt semnificativ mai mici decat cei dati datorita performantelor mai mari ale calculatoarelor pe care am rulate programele.

Pentru rezolvarea unei probleme reale trebuie specificate domeniile, operatorii si telul. Planificatorul va incerca determinarea unui plan bazandu-se pe aceste cunostinte si din care va obtine altele noi, ca urmare a intreprinderii anumitor actiuni.

Conditiile initiale si operatorii se specifica printr-o sintaxa prezentata mai sus si care se salveaza intr-un fisier .lisp impreuna cu functia care apeleaza algoritmul de planificare si care are ca parametrii conditiile initiale si telurile. Pentru executarea exemplului se parcurg urmatorii pasi:

• se incarca fisierul variable.lisp - in care se definesc tipuri de date algoritmului de planificare;
• se incarca fisierul plan-utils.lisp - care contine functii utilizate de planificator
• se incarca fisierul snlp.lisp - aici este descris algoritmul de planificare
• se incarca exemplul si se executa functia de planificare.

Exemple(sus)

Urmatorul exemplu este asemanator problemei turnurilor din Hanoi. Avem o configuratie initiala a blocurilor si una finala, vrem sa gasim un plan care sa ne genereze pasii necesari pentru a ajunge la configuratia finala, incepand cu configuratia initiala.

Domeniul va fi definit prin urmatoarele rutine:

(defun blocks-world-domain ()
- aceasta functie va schimba un domeniu vechi, daca era definit ,cu unul nou.
(plan-utils:reset-domain)

- definim pasul care pune un bloc pe masa.
(plan-utils:defstep :action '(newtower ?x) ; se creea o noua 'stiva' de obiecte pe masa care contine numai blocul X
:precond '((on ?X ?Z) (clear ?X)) ;se specifica faptul ca blocul X este deasupra blocului Z  si blocul X nu mare nimic                                                             ; deasupra lui : (clear ?x)
:add '((on ?X Table) (clear ?Z)) ; savarsirea acestei actiuni are ca efect crearea urmatoarelor predicate: (on ?X Table)                                                             ;-X va fi pe masa,
:dele'((on ?X ?Z))                      ;se 'sterge' faptul ca blocul X este deasupra blocului Z
:equals '((not (?X ?Z)) (not (?X Table)) (not (?Z Table))))

- definirea pasului care pune un bloc peste altul
(plan-utils:defstep :action '(puton ?X ?Y)      ; mutam blocul X peste blocul Y
:precond '((on ?X ?Z) (clear ?X) (clear ?Y)) ; actiunea se poate realiza numai daca blocurile X si Y nu au alte blocuri                                                                        ;;deasupra lor ( (clear ?X) , (clear ?Y) )
:add '((on ?X ?Y) (clear ?Z)) ; in urma executarii actiunii, se vor forma urmatoarele certitudini: X este deasupra lui Y, si Z nu                                               ;; va  mai avea nici un bloc deasupra sa
:dele '((on ?X ?Z) (clear ?Y))              ; X nu va mai fi deasupra lui Z si Y va avea un bloc deasupra lui;
:equals '((not (?X ?Y)) (not (?X ?Z)) (not (?Y ?Z))
(not (?X Table)) (not (?Y Table)))))

- planul se genereaza apeland urmatoarea functie, pentru care se specifica conditiile initiale si telurile.

(defun snlp-sussman-anomaly ()
(snlp:plan '((on C A) (on A Table) (on B Table) (clear C) (clear B)) ;; conditii initiale
'((on A B) (on B C)))) ;; teluri

USER(10): (snlp-sussman-anomaly)
#SNLP-Plan<S=3; O=0; U=0>
#Stats:<cpu time = 2>

Setand flagul PLAN-UTILS:*VERBOSE* la T rezulta se vor afisa urmatoarele date::

USER(15): (snlp-sussman-anomaly)

Initial : ((ON C A) (ON A TABLE) (ON B TABLE) (CLEAR C) (CLEAR B))

Pas 1 : (NEWTOWER C) Created 2
Pas 2 : (PUTON B C) Created 3
Pas 3 : (PUTON A B) Created 1

Goal : ((ON A B) (ON B C))
Complete!