Systematic nonlinear planner - aspecte teoretice
In acest document se prezinta un algoritm sistematic simplu, robust, complet pentru planificare folosind domenii definite prin limbajul STRIPS. Simplitatea este realizata pornind cu un procedeu de baza urmat de o transformare geneala, independenta de domeniu. Aceasta procedeu de baza este o versiune a procedurii NONLIN a lui Tate. Sistematizarea planificatorului este o proprietate se refera la faptul ca un plan nu va fi examinat mai mult de o data, acesta fiind realizata printr-o simpla modificare a procedurii lui Tate.
Introducere(sus)
Planificarea folosind structuri STRIPS a fost introdusa ca un model pentru a rezolva probleme pe care oamenii le rezolva prin rationamente obisnuite. Planificarea STRIPS corespunde unei anumite probleme de cautare formala in graf. Jhon Canny a observat ca problemele formale de planificare STRIPS sunt PSPACE complete. Asta fapt inseamna, in esenta, ca orice plaificator complet si robust trebuie sa implementeze algoritmi de cautare. Este binecunoscut faptul ca anumite probleme NP complete si PSPACE complete pot fi rezolvate eficient pentru marea majoritate a problemelor care apar in practica. Desi este inca discutabil daca planificarea STRIPS poate fi aplicabila pentru probleme de dimensiuni mari, desi este clar ca unele metode de optimizare a cautarii pot imbunatatii dramatic performantele algoritmilor de planificare.
Procedurile de planificare au folosit trei tehnici de baza pentru a optimiza procesul de cautare. Mai intai, chiar si cele mai timpurii planificatoare au fost generalizate ("lifted"). Aceasta inseamna ca se foloseau expresii care contin variabile, de ex. PUTON(A x), pentru a reprezenta un numar mare de alte posibilitati., de ex. PUTON(A B). Marea majoritate a planificatoarelor sunt "nelineare" - ele mentin mai degraba o relatie de ordine partiala a pasilor planului decat o relatie de ordine totala. Aceasta relatie de ordine partiala este rafinata gradual in timpul planificarii. Unele planificatoare folosesc "abstractizarea spatiului" in care pentru inceput planificarea este facuta la un nivel inalt de abstractizare si pe urma detalii de nivel scazut sunt introduse, o data ce un plan de nivel inalt este gasit.
Planificatoarele neliniare sunt uneori denumite " planificatore cu angajamentul cel mai scazut". In general, principiul informal al starii cu angajamentul mai mic sustine ca trebuie sa se faca alegeri cu angajament mai mic inaintea celor cu angajamant mai mare. In cautarea unui plan putem selecta PUTON(A B) ca prim pas al planului, aceasta este o alegere cu angajament ridicat. O alegere de angajamant mai scazut este sa consideram ca prim pas al planului o expresie de forma PUTON(A x). Neliniaritatea este un alt exemplu al principiului angajamentului mai mic. In loc sa alegem o expresie de forma PUTON(A x) ca prim pas al planului, putem considera ca PUTON(A x) va aparea undeva in plan fara sa ne asumam angajamentul unde va fi plasat. Acesta este o alegere cu angajament scazut.
Vom prezenta un algoritm sistematic, neliniar, simplu, complet, si robust. La fel ca alti planificatori, algoritmul prezentat foloseste generalizarea si neliniarizarea pentru a optimiza cautarea. Acest algoritm are doua caracteristici inovatoare - simplitatea si sistematizarea. Pe langa faptul ca e simplu, procedeul prezentat realizeaza o cautare sistematica, adica acelasi plan nu este examinat decat o singura data. Sistematizarea este realizata printr-o simpla modificare a versiunii de baza a procedeului lui Tate.
Planificarea STRIPS(sus)
Definitie: Un operator STRIPS consta dintr-un nume, o lista de preconditii, o lista add, si o lista delete. Elementele listei de preconditii, a listei add si delete sunt expresii propozitionale. Lista de preconditii contine o serie de expresii, propozitii, care trebuie sa fie satisfacute pentru ca actiunea sa fie aplicabila, lista add este o lista de expresii care vor fi adevarate dupa aplicarea operatorului, delete este o lista de expresii care un vor mai fi adevarate dupa aplicarea operatorului. Folosirea listelor add si delete se justifica prin faptul ca actiunile modifica doar o mica parte a reprezentarii starilor, astfel fiind mai eficient sa retinem doar modificarile acestora.
Definitie: Daca o este un operator STRIPS, si S este o multime de expresii propozitionale, atunci, daca preconditiile pentru o sunt o submultime a multimii S, atunci rezultatul operatiei o in contextul S este S minus lista delete a lui o plus lista add a lui o. Daca lista de preconditii nu este inclusa in S, atunci rezultatul executiei lui o in contextul S este multimea vida.
Definitie: O problema de planificare STRIPS este un triplet <T,S,O> unde T este o multime de operatori STRIPS, S este o multime de propozitii initiale, si O este o multime de teluri.
Definitie: O solutie a unei probleme de planificare STRIPS <T,S,O> este o secventa w de operatii, fiecare fiind membra in O, astfel incat aplicand consecutiv opratiile din w incepand cu starea initiala S rezulta o multime care contine multimea de teluri G.
Dupa cum am mentionat mai inainte, pentru a determina daca un planificator STRIPS arbitrar are sau nu solutie, este o problema PSPACE completa. In sectiunea urmatoare se prezinta o versiune simplificata a procedeului de planificare neliniara a lui Tate.
Planificator neliniar(sus)
Un plan este o secventa de operatii. Intuitiv, doua plane sunt considerate echivalente daca unul poate fi obtinut din celalalt printr-o reordonare a posilor care nu interactioneaza. De exemplu, sa consideram un robot care trebuie sa execute un numar de actiuni in camera A si un numar de actiuni in camera B. Fiecarei actiuni ii este asociat un scop. Vrem sa atingem telurile P1,...,Pn,Q1,...,Qm. Se dau operatorii A1,...,An,B1,...,Bm unde actiunea Ai are ca tel scopul Pi care trebuie realizata in camera A si Bi are ca tel scopul Qi si trebuie atins in camera B. Mai formal, fiecare actiune Ai are ca singura preconditie predicatul IN(A), fiecare Bi are ca preconditie IN(B). De asemenea avem ca un operator GO(A) care nu are preconditii si are ca scop IN(A) si sterge propozitia IN(B). De asemenea mai avem un operator analog GO(B). Multimea de teluri {P1,...,Pn,Q1,...,Qm} poate fi atinsa de planul GO(A); A1;...;An; GO(B);B1;...;Bm. Bineinteles, ordinea pasilor Ai si ordinea pasilor Bi nu conteaza cat timp toti pasii Ai sunt efectuati in camera A si toti pasii Bi sunt efectuati in camera B. Acest plan este echivalent cu planul GO(A);An;...;A1;GO(B);Bm;...;B1, care efectueaza actiunile Ai si Bi in ordine inversa.
Fiecare plan liniar care este solutie a unei probleme date poate fi abstractizata la un "plan neliniar" unde planul neliniar contine doar o ordine partiala a pasilor planului. Doua plane liniare sunt considerate ca fiind echivalente daca sunt reprezentari diferite ale aceluias plan neliniar.
Pentru a defini un plan neliniar asociat unui plan liniar trebuie sa depasim o mica problema tehnica. Intr-un plan liniar putem sa referim pasii individual referindu-ne ca fiind primul pas, al doilea si asa mai departe. Intr-un plan neliniar este posibil sa nu se poata preciza cu exactitate un al doilea pas, nu putem denumi un pas al planului cu numele operatorului folosit la acel pas pentru ca mai multi pasi ai planului pot implica acelasi operator. Pentru a genera nume pasilor intr-un plan neliniar presupunem ca fiecarui pas ii este asociat un simbol distinct numit nume al acelui pasi.
Definitie: O tabela de simboluri este o mapare de la o multime finita de pasi la o multime de operatori. Fiecare tabela de simboluri trebuie sa contina doua nume distincte numite START si FINISH. START indica spre un operator care nu are preconditii, FINISH indica spre un operator care are o multime de preconditii numite "formule tinta", listele add si delete fiind vide.
Definitie: O legatura cauzala este un triplet <s,P,w> uned P este o propozitie, w este numele unui pas care il are pe P ca preconditie, si s este numele unui pas care il are pe P in lista add.
Definitie: Un pas v este numit amenintare (threat) a unei legaturi cauzale <s,P,w>, daca v este diferit de s si w si care are pe P fie in lista add fie in delete.
Definitie: O conditie sigura este o relatie de ordine s<w sau w>s unde s si w sunt nume de pasi ai planului.
Definitie: Un plan neliniar consta dintr-o tabela de simboluri, o multime de legaturi cauzale si o multime de legaturi sigure.
Definitie: Un plan neliniar este numit complet daca sunt indeplinite urmatoarele conditii
Definitie: O sortare topologica a unui plan neliniar este o secventa liniara a tuturor numelor pasilor din tabela de simboluri astfel incat urmatoarele conditii sunt indeplinite:
Definitie: O sortare topologica a unui plan neliniar este o solutie daca executand secventa de operatii intre pasii START si FINISH, incepand in starea data de lista add a starii START, oprindu-ne intr-o stare care contine toate preconditiile starii FINISH
Lema: Orice sortare topologica a unui plan complet neliniar este o solutie.
Este posibil sa se construiasca o procedura de planificare care cauta sistematic spatiul planelor neliniare. Cautarea este sistematica in sens tehnic, adica nu viziteaza acelasi plan, sau chiar plane echivalente, de doua ori - fiecare ramura a arborelui de cautare divide posibilitatile ramase in multimi disjuncte de solutii posibile.
Definitie: Un plan neliniar ( nu necesar complet) este numit inconsistent in ordine daca nu nu are o sortatre topologica.
Un algoritm de inchidere tranzitva poate fi folosit pentru a determina daca un planificator neliniar este inconsistent in ordine.Un plan neliniar este inconsistent in ordine daca si numai daca legaturile cauzale si conditiile sigure ale planului definesc un ciclu in pasii planului.
Pocedura pe care o folosim este una de cautare in adancime marginita care poate fi folosita cu adancire iterativa. Procedura se apeleaza pentru un plan neliniar si o margine de cost si cauta o completare a planului astfel incat costul total al pasilor sa nu fie mai mare decat marginea data. Initial procdura este apelata pentru un plan neliniar care contine doar pasii START si FINISH corespunzatori unei probleme de planificare STRIPS. De asemenea presupunem un set dat de operatii permise.
Procedura FIND-COMPLETION(b c)
FIND-COMPLETION(b+(v<s),c)
FIND-COMPLETION(b+(v<s),c)
FIND-COMPLETION(b+<s,P,w>,c);
Comentarii asupra procedurii(sus)
Procedura descrisa anterior este o simplificare a procedeului neliniar al lui Tate. Aceasta poate fi modificata sa manipuleze o serie de spatii de abstractizare. Vrem sa ne asiguram ca preconditiile abstracte sunt satisfacute inainte sa incercam sa satisfacem preconditii concrete. Pasii 3 si 4 ai procedurii selecteaza fie o preconditie care nu este implicata intr-o legatura cauzala, sau o amenintare a unei legaturi cauzale. Selectia preconditiilor legaturilor cauzale amenintate poate fi facuta arbitrar. Procedura poate fi modificata sa realizeze planificarea in diferite spatii de abstractizare, iar lema din sectiunea anterioara specifica faptul ca fiecare plan neliniar complet este sigur in sensul ca orice sortare topologica a planului este o solutie.Insa,reciproca axiomei nu este adevarata - pot exista plane partiale ordonate dupa pasi, dar care sa nu corespunda nici unui plan neliniar complet.
Este posibil sa se caute in mod sistematic toate relatiile de ordine partiala si sa se gaseasca cea mai abstracta ordine partiala care este sigura. Din pacate, se pare ca nu sunt moduri de a face asa ceva in mod eficient. Evaluand criteriul formal de adevar al lui Chapman la fiecare nod din spatiul de cautare ar fi foarte costisitor. Mai mult, tratand criteriul formal de adevar ca o procedura nedeterminista, asa cum este facut in TWEAK, distruge sistematizarea cautarii. Chiar daca cautarea este sistematica in spatiul de ordine partiala dupa numelor starilor, diferite ordini ale numelor de pasi poate corespunde unei aceleiasi ordini ale operatiilor executate in mod real. Aceasta implica faptul ca, spre deosebire de procedura data aici, cautarea inca va ramane o cautare nesistematica a succesiunii operatiilor.
Bibliografie :(sus)