Tehnici de planificare

Tehnici de planificare

Metodele tehnicilor de reglare din cursul 6-7 sunt adecvate pentru atingerea si stabilizarea starilor in spatiile de stare continui sau discretizabile. Aceste stari, de exemplu, se aproximeaza printr-o functie liniara, analitica, din care se calculeaza marimea de comanda, pornind de la marimea erorii.

Metodele tehnicilor de reglare nu se pot utiliza cand spatiul starilor nu este constant, ci variaza in trepte si starile se definesc, nu ca vectori, ci in domenii de variatie. In aceste cazuri tehnicile de planificare cu inteligenta artificiala sunt adecvate pentru atingerea si stabilizarea starilor.

Notiuni de baza ale sistemelor planificate

Metodele tehnicilor de planificare descriu o marime de reglare (starea actuala) nu ca un vector de stare, in cazul tehnicilor de reglare, ci ca un sir de atribute sau de caracteristici, care, pentru niste conditii date si la un anumit moment de timp, pot fi masurate sau constatate. Starile pot fi modificate prin evenimente sau actiuni. Actiunile sunt modificari ale starilor, care sunt initiate de catre agenti. Actiunile corespund unei stari initiale si unei stari finale. Spatiul starilor si modificarile starilor sunt discrete in timp. (fig 6.1b si 6.2b). O modificare a starii inseamna o modificare a sirului de atribute, respectiv de caracteristici.

Un modul de planificare realizeaza secvente sau grafuri de actiuni, care conduc de la o stare actuala, prin utilizarea cu scop a operatorilor, respectiv conduc, prin comanda executiei actiunilor, in starea tinta dorita. O planificare clasica (simpla) nu autosesizeaza tactul de timp si considera starile si modificarile de stari ca fiind nedependente de timp. Un asemenea modul de planificare se poate compara cu conducerea fara bucla de reglare inversa din tehnicile de reglare.

S-a stabilit deja ca procesul de modificare al starilor este atat de precis modelat incat se obtin exact modificarile de stare prevazute. Perturbatile, oscilatiile intre modificarile reale ale starilor si cele prognosticate nu pot verificate in raport cu timpul. Modulul de comanda al executiei secventelor se regaseste ca un intreg in modulul de planificare (fig. 8.1.a).

La planificarea cu reactie se stabilesc secventele sau grafuri ale actiunilor pentru atingerea sau stabilizarea starii tinta din starea actuala. De aceea, starea reala se identifica prin senzori si se reprezinta intr-un model al starilor. Daca, prin executia secventelor, se ajunge la oscilatii intre starile reale si cele prognosticate, atunci, se reia planificarea pe baza starilor reale. Modulul de planificare cu reactie se aseamana, de aceea, cu reglarea, cu bucla de reactie din tehnica reglarilor (Fig. 8.1b).

Fig. 8.1 Prelucrarea informatiilor a) sistem de planificare simpla b) sistem de planificare cu reactie

Metodele de planificare nu sunt activate la momente de timp discrete si nu calculeaza intre aceste momente de timp modificarile de stare necesare. Modulul de planificare este activat de catre modulul de supraveghere, care sesizeaza anumite stari sau evenimente. Generarea planulului si comanda executiei planului sunt, de aceea in principal, metode discrete generate de evenimente. Variabila k din marimea de comanda, respectiv din actiunea u (k) poate fi un moment de timp si o conditie dependenta de stare, care a fost definita inainte si care a fost sesizata de catre modulul de supraveghere. Cand k nu este un moment de timp, atunci nu trebuie neaparat sa se stabileasca in prealabil o ordine sau o succesiune pentru diferite conditii k_i. Tinta prestabilita x* ( k >==N ) contine starea tinta si evenimentul N, dupa aceste intrari, trebuie atinsa tinta. Daca se modifica constant tinta in cazul planificarii reactive, atunci se compara tinta cu marimea de comanda a executiei w( k

Se numeste plan, secventele sau grafurile de actiuni rezultate din modulul de planificare. Planul descrie, in spatiul starilor, sirul de modificari ale starilor: secvential, simultan sau coordonat simultan, care conduce la atingerea starii tinta. Un plan liniar se compara cu un sistem de reglare, la care marimea de comanda variaza liniar, in scopul minimizarii erorii de reglare.

In general se impart planele in subplane, acestea sunt segmente de plan (autonome) sau schelete de plan (neautonome). Se numeste o unitate de plan sau de actiuni, un segment de plan sau o transformare de stare care nu se mai poate diviza. Din caracteristicile subplanelor se pot determina diferite structuri de plan:

. plan secvential,

. plan alternativ cu ramificare determinista, stohastica sau haotica,

. plan iterativ,

. plan recursiv si

. plan simultan, respectiv cu desfasurare simultana.

Un aspect important al planificarii este legatura arbitrara a tranzitiei starilor din plan cu procedee, interactiuni si comportamente. Ordinea sau legarea transformarilor de stare intr-un plan pot fi clasificate, indiferent de tipul comenzii executiei. Este, de asemenea, posibila legarea directa a comportamentului unui agent cu transformarea de stare a acestuia.

Cunostintele sunt corespondenta dintre transformarile de stare din planificare si procedeele, interactiunile si comportamentele. Acestea intra in modelul procesului si constituie premise ale tuturor metodelor de planificare.

Exemplu: Transfomarea de stare ca procedeu, interactiune si comportament

Se modeleaza montajul unui ansamblu prezentat anterior in cursul 6, prin realizarea unui graf (Fig. 8.2) pe baza starilor de fixare (piesa, mod de fixare) ale reperelor ansamblului. O stare intermediara nu este modelata, de exemplu, un nit nu poate fi luat in considerare ca fiind 75% nituit. Starea modelata este: nituit sau nu.

Fig. 8.2 a) desen explodat b) legatura intre schimbarea starii cu procedee, interactiuni sau comportamente

Transformarea de stare poate fi formulata ca tinta sau ca procedeu sub forma 'realizarea asamblarii' (piese, tip de asamblare). Exista si alte posibilitati de formulare. De exemplu, pe baza de contacte: realizarea contactelor (piesa, suprafata, vecini, suprafata, vecini, ). Daca aici transformarea de stare este discreta, se poate defini o tranzitie oarecare pentru modelul direct si cel invers. La aceasta forma de transformari de stare pe baza de modificari externe de stare nu se poate face o predictie cu privire la tipul procesului de interactiune sau la un anumit agent care realizeaza transformarea.

Modificarile de tip treapta ale starilor discrete pot fi stabilite direct prin interactiunile intre agenti si mediu, in loc de descrierea abstracta a procedeelor. Sub alegerea unui tip de asamblare se pot ascunde diferiti agenti si interactiuni, care sunt influetate puternic din mediu.

Un procedeu de asamblare cu un automat de montare sau cu un robot de asamblare se diferentiaza considerabil. Chiar si numarul agentilor care participa poate sa varieze in functie de forma de interactiune. Numai la putine forme de interactiune este determinabil numarul de agenti. Pentru o transformare de stare pot sa existe multe alternative pentru tranzitie, alternative care depind de mediu si de numarul de agenti. Daca se modifica mediul in timpul executiei, atunci nu se pot genera plane general valabile pe baza de interactiuni.

Din punct de vedere formal, nu exista limite cu privire la formele de asamblare. Chiar si procedeele de planificare nu depind de ordinea actiunilor din transformarile de stare. O actiune necorespunzatoare, falsa sau care in practica, in sistemul dat, nu este reversibila este preluata de algoritm ca una buna. De asemenea, planificatorul nu face diferenta intre actiunile simbolice care implica legaturi intre agenti (de exemplu imbinarea cu robot) si transformarile de stare generale (de exemplu, realizarea asamblarii).

Pentru executia planului cu sisteme senzori-actuatoare, este, de aceea, necesar ca starile modelate din executiile anterioare in sistem, sa se cunoasca si sa se diferentieze cu adevarat. Altfel, este corect planul, dar nu este executabil cu sistemul prestabilit.

Starile si transformarile de stare trebuie modelate in asa fel, incat toate starile modelate sa fie tangibile si, prin transformarile de stare intr-un mediul oarecare, cu agentii si resursele prestabilite, sa se modifice in asa fel incat starea tinta sa fie atinsa.

Procedee de planificare simple

Procedeele de planificare realizeaza calcule, devieri, cautari sau alegeri pentru o inlantuire de transformari de stare, cu care dintr-o anumita stare sa se ajunga la o stare tinta dorita. Ele prelucreaza o serie de simboluri si pot sa produca plane necorespunzatoare, daca acestea contin stari eronate sau transformari de stare neexecutabile.

Primele doua procedee care exista sunt: 'planificare logica' si 'planificare prin cautare'. 'Planificarea prin alegere cu verificare' este utilizata in cele mai multe sisteme de planificare cu reactie, dar este rar denumita explicit astfel, de vreme ce este o planificare prin cautare in esenta. Fiecare procedeu este un punct de vedere diferit al aceleiasi probleme.

In ultimul rand trebuie implementate toate procedeele in programe de calculator. Mai tarziu, la implementarea procedeelor si integrarea intr-un sistem de planificare reactiv, se vor lamuri domeniile de utilizare ale procedeelor.

Planificarea logica

In acest paragraf se vor prezenta numai notiuni de baza de planificare logica. Aici, introducerea planificarii logice monotone este limitata in cazul problemelor complexe sau a sistemelor de planificare reactive. Multe fenomene din realitate si din mediul real, in care agentii actioneaza, nu se conduc prin logica strict monotona. Pentru cele mai multe utilizari practice trebuie dezvoltata o logica nemonotona prin 'reguli de urmat'.

Se poate ca problema de planificare sa fie condusa printr-un calcul logic, cand aceasta poate fi definita prin: 'se poate ca starea tinta sa fie atinsa, pornind de la starea actuala?' Calculul utilizeaza o logica tipica predicativa de ordinul 1 sau un calcul de situatie.

Extragerea starilor tangibile (care se pot atinge) este denumita si planificarea prin inferenta.

Pentru a se determina, la o extragere posibila, daca o stare este derivata din alte stari, trebuie ca starile sa fie descrise formal: se presupune ca, daca exista un set de senzori, respectiv module de supraveghere care pot dovedi atributele indivizilor sau relatiile intre indivizi in proces, atunci se defineste un sir de atribute si relatii ale starii actuale a procesului. De asemenea, exista senzori, care stabilesc ca exista atribute sau relatii care nu se intalnesc in starea actuala a procesului.

Cand intr-o stare a procesului y este valabil un atribut x_j, atunci se poate scrie (holds=tine, cuprinde):

holds (x_j , y ), (adica starea y are atributul x_j) (8.1)

Se pot face predictii complexe, de exemplu asupra procesului y. Operatii logice sunt: 'nu', 'si', 'sau', 'daca-atunci', 'exact daca-atunci'. Exista si elemente care quantifica gradul de adecvare al atributelor sau al relatiilor unui individ. In logica predicativa de ordinul 1 se utilizeaza: 'valabil (exista) pentru toate x' si 'exista cel putin unul care este valabil pentru asta'. Se pot utiliza si constructii logice, ca de exemplu: 'daca atributele x_j si x_k sunt valabile, atunci este valabil si x_l'.

Aceasta inseamna ca, se pot deduce noi atribute intre indivizi si relatii, de la sine, atunci cand acestea nu se pot masura direct prin senzori. Daca deductia se face cu un program pe calculator, trebuie mai intai sa se verifice daca atributele x_j si x_k sunt valabile si atunci fie x_l sa fie reprezentat explicit, fie atributul x_l este legat direct de evaluarea termenilor respectivi.

In final se transpun acestea intr-un limbaj de programare, de exemplu Prolog. Se fac predictii nu numai asupra starii actuale, ci si asupra starilor ce apar dupa un procedeu (interactiune, actiune, comportament) si se ajunge intr-o situatie de calcul a unui operator cu atributul (result). Daca dintr-o stare a procesului y, se poate aplica un operator o sau o actiune u, atunci se ajunge intr-o noua situatie:

result( u, y) (8.2)

Planificarea prin cautare

Descrierea desfasurarii planificarii prin cautare, prin transformari de stare discrete intr-un spatiu discret al starilor, respectiv prin cautare intr-un graf cu noduri de stare si legaturi date de transformari, sunt bazele celor mai multe procedee de planificare.

Se cauta tranzitii, care reduc distanta pana la starea cautata. Cea mai raspandita reprezentare a starilor si transformarilor de stare este cea dezvoltata pentru STRIPS (Stanford Research Institute Problem Solver).

In STRIPS, se descrie o stare a procesului x( y) printr-o operatie logica SI a unei multimi de formule x, care descriu semantic atributele observabile, adecvate sau care pot aparea sau descriu relatiile procesului y:

Formulele x_i descriu stari reale ale procesului. Acestea se bazeaza pe informatii, care se obtin de la senzori, din baze de date sau se obtin din calcule (Fig. 8.4).

Fig. 8.4 Cunoasteri pe baza (a) senzorilor, (b) senzorilor si cunostintelor, (c) alte cunoasteri respectiv observatii

Starile se modifica pe baza unor asa-numiti operatori o (de exemplu actiuni) sau prin operatorii continuti in plane p. Operatorii au 4 componente:

1. Descriere: Descrierea returneaza semnificatia semantica a operatorilor pentru modificarea starii. Descrierea poate fi o actiune a unui agent.

2. Conditii initiale: O conditie initiala este o formula logica, ce se refera la o stare, formula care indica, daca este posibila utilizarea operatorului sau executia unei actiuni in acea stare.

3. Multimea de atribute aditionale: Aceasta multime stabileste, prin formule suplimentare aditionale, prin ce anume se diferentiaza noua stare, obtinuta dupa utilizarea operatorilor, respectiv executia actiunilor, de starea anterioara.

4. Multimea de atribute reduse: Aceasta multime stabileste, prin formule reducatoare (de eroare), prin ce anume se diferentiaza noua stare, obtinuta dupa utilizarea operatorilor, respectiv executia actiunilor, de starea anterioara.

o= ( u ,cond, add, sub) (8.10)

Exemplu: reprezentarea STRIPS-a mutarii unor cuburi (blocuri)

Fig. 8.5 Exemplu de manipulare a unor blocuri inainte (a) si dupa (b) actiunea puton.

Cu notatia STRIPS se reprezinta starea actuala a blocurilor din figura 8.5ª, dupa cum urmeaza:

x (y)= + (8.11)

Un operator este un qvartet compus din descriere, conditii initiale, multimea de atribute aditionale si de atribute reduse:

(8.12)

Expresia de mai sus inseamna ca actiunea puton (A, B ) poate sa aiba loc, daca se ajunge la conditia initiala . In final sunt valabile clear (A) si o noua conditie on (A, B) . clear( B) nu mai este valabil, iar despre grey( B) nu se poate spune nimic In urma utilizarii operatorului obtinem:

x (y)= (8.13)

Din exemplu, se clarifica anumite caracteristici ale reprezentarii STRIPS:

1. Trebuie adaugate in lista aditionala toate formulele semnatice, care in noua stare trebuie sa fie valabil stabilite. Daca clear (A) nu apare in lista, atunci se deduce ca, operatorul puton (A, B) poate sa conduca la starea in care clear (A) nu trebuie sa fie valabila.

2. Trebuie adaugate in lista redusa toate formulele semantice, care nu au voie sa fie valabil stabilite in noua stare.

Sistemele de planificare simple, ca de exemplu STRIPS, au ca sarcina sa genereze un plan, adica o secventa de operatori, care prin executia lor dintr-o stare a procesului y (k) sa conduca intr-o noua stare a procesului y*( k). Starea procesului y este definita de o multime de atribute valabile x( y) si starea tinta de o multime de atribute valabile x( y x*. Pentru planificare, o stare a procesului y contine multimea

O (y)=Uo_u cu o_u operatori cunoscuti/utilizabili pentru y (8.14)

Multimea O (y ) este modelul procesului si se prezinta ca baza de reguli sau de cunostinte.

Prelucrarea planului poate fi continuata cu procedeul de cautare in grafuri. Starile, respectiv multimea atributelor sunt noduri intr-un graf si operatorii sunt sagetile. Pe deasupra se stabilesc relatiile de vecinatate si metricile cu atributele suplimentare ale operatorilor (de exemplu, lungimile curselor) in spatiul starilor. Daca starile cu aceleasi multimi de atribute se accepta ca identice, atunci grafurile contin cicluri sau starile identice se ating prin diferite trasee (cai). Daca se ordoneaza planele continute, respectiv lanturile de operatori cu atribute asemenea, ca de exemplu suma lungimilor traseelor, atunci se diferentiaza starile cu atribute identice prin atributele planelor prin care aceste stari se ating. (Fig. 8.6).

Fig. 8.6 Tranzitii intre multimi de atribute prin utilizarea operatorilor

Planificarea prin cautare poate fi realizata prin mai multe feluri:

1. Cautare dupa stari: la cautarea dupa stari se vor verifica si testa individual toti operatorii posibili pentru nodurile de stare actuale Y , daca dupa succesiunea de stari

se atinge starea tinta. Starea tinta este definita printr-o multime de atribute valabile.

Pornind de la mai multe combinatii diferite de utilizare a operatorilor, cu care se poate atinge starea tinta, se pune problema cu privire la succesiunea sau simultaneitatea utilizarii operatorilor (Fig. 8.7).

Fig. 8.7 Atingerea unei stari tinta prin ordonarea diferita a utilizarii operatorilor, respectiv utilizarea lor in simultan

2. Cautare prin atribute: La cautarea prin atribute se vor verifica si testa toti operatorii pentru nodul de stare actual Y (0), daca prin succesiunea de stari cu atributele Y (n)

se vor gasi toate sau numai unele dintre atributele starii tinta. Succesiunea de stari este acea succesiune la care, orice urmare (operator) duce la disparitia atributelor tinta. Se vor respinge acele succesiuni de stari pentru care distanta la tinta se mareste sau nu se micsoreaza destul de repede. Pentru succesiunile ramase se vor utiliza din nou operatorii.

Daca se considera ca atributele individuale se ating independent unul fata de altul, atunci se imparte sarcina de planificare in tinte partiale si astfel se obtine o impartire a planului, respectiv a legaturii dintre operatori. Acestea sugereaza ca un plan sau un operator, care garanteaza atributul x_i si un plan sau un operator care genereaza un atribut x_j, impreuna, ambele atribute se obtin cu siguranta daca planul sau operatorul sunt executate ordonat sau simultan.

Atributele sunt atinse individual si subplanele sunt executate intr-o ordine oarecare sau simultan. (Fig. 8.8).

Fig. 8.8 Linearitate: atributele pot fi atinse independent una fata de cealalta

3. Cautare prin plane: Cautarea prin plane, respectiv prin atributele planelor este in general ca si cautarea dupa stari. Pe langa cerintele de baza, ca planul sa schimbe starea in modul dorit, se pot defini pentru plan si alte atribute, care in orice caz trebuie sa fie valabile. Un atribut necesar al planelor ar putea fi, de exemplu impartirea liniara in subplane.

Operatorii din plane, la cautarea prin plane nu descriu transformari de stare (executia actiunilor) in proces, ci transformari de stare din timpul stabilirii planelor (actiuni de generare a planelor). In realitate, se asambleaza, mai intai, in constructii mari, deja existentele subplane p_iI P sau operatorii o_iI O. Operatorii de plane o^pI O^p definesc cum se pot asambla subplanele (Fig. 8.9). Fie o stare a planului y^p. Multimea x^p (y ^p ) cuprinde atributele si relatiile care sunt valabile pentru y^p:

Operatorii o^p sunt in cel mai simplu caz 'ordonare secventiala", 'simultaneitate" si "alternativa". Sunt utilizate constructii, ca de exemplu: 'repeta atata timp cat' sau 'repeta de n ori'. La fiecare stare a planului, adica dupa fiecare utilizare a operatorilor de plan, se verifica daca s-au atins atributele de plan dorite.

Fig. 8.9 a) Multimea de plane si de operatori, b) transformari intre starile planelor in timpul generarii acestora, prin operatorii de generare ai planelor

Planificare prin prelucrarea planelor si verificarea atributelor acestora

Un plan poate avea:

. O conditie optionala de start si un singur procedeu, cu o conditie optionala de terminare (Fig. 8.11a),

. O conditie optionala de start si o secventa de mai multe procedee, cu conditii pentru transformare ca si de terminare (Fig. 8.11b),

. o simultaneitate optionala a mai multor procedee (Fig. 8.11c), cu conditii optionale, individuale sau generale de start si de terminare,

. o simultamenitate obligatorie a mai multor procedee (Fig. 8.11d) cu conditii optionale generale de start si de terminare,

. o simultaneitate alternativa a mai multor procedee (Fig. 8.11e) cu conditii optionale generale de start si de terminare si conditii de prioritate, individuale sau generale. Simultaneitatea alternativa poate sa conduca la simultaneitatea optionala, cand este activ mai mult de un procedeu alternativ.

Daca exista mai multe alternative pentru o succesiune prestabilita de plane, atunci se alege una din variante sau se iau in considerare toate alternativele. In cel de-al doilea caz, se alege mai intai, la momentul de timp al executiei, printr-o conditie de prioritate, o varianta de plan, respectiv se realizeaza o simultaneitate optionala a mai multor plane alternative.

Daca lipseste conditie de start, atunci se leaga procedeul in cauza de un procedeu anterior cu durata cea mai lunga sau se leaga de inceputul executiei planului. Daca lipseste conditia de terminare, atunci se leaga terminarea direct de procedeul care urmeaza, care are startul executiei cel mai devreme sau se leaga de terminarea executiei planului. Aceste legaturi trebuie sa se succeada dinamic. Ele contin coordonari, respectiv sincronizari ale procedeelor.

Fig. 8.11 Combinatii de structuri elementare de plan

a)      Un singur procedeu

b)      Mai multe procedee

c)      Simultaneitate optionala a mai multor procedee

d)      Simultaneitate obligatorie a mai multor procedee

e)      Simultaneitate alternativa a mai multor procedee

Prelucrarea planelor inseamna o alegere a planului initiata de conditii, respectiv stabilirea inlocuirea unui plan abstract printr-o structura de retea de plane, intr-un alt nivel abstract. Planul abstract stabilit nu trebuie neaparat sa fie un element de plan singular, ci poate el in sine sa aiba o structura de retea, cu conditii de start si de terminare. Acestea se denumesc in continuare structuri de plan (Fig. 8.12).

Alegerea planului inlocuieste astfel o structura de plan pentru atingerea unui tel printr-o alta structura oarecare de plan. In cel mai simplu caz este inlocuirea unui element de plan, care se descrie prin etichete. Operatorii de plan se descriu astfel:

structuraoriginaladeplan, structurainlocuitadeplan

Fig. 8.12 Stabilirea structurilor mari de plan

Executia pe parti a planelor, interpretarea si prelucrarea planelor

Metodele de planificare pot fi analizate si comparate, independent de utilizarea si executia planelor. Planificarea in sistemele multi-agent se ocupa cu atingerea tintei si stabilizarea starilor.

Descrierea tintei intr-un plan este numai jumatate din scopul planificarii, respectiv din traducerea unei structuri de plan intr-o structura de prelucrare a informatiilor si a materialului (la agentii de prelucrare a informatilor, respectiv agenti din procese tehnice).

Din figura 8.16 este clar, ca se poate descompune: definitia tintei, planificarea, traducerea in comportamente, ordonarea in sistemul senzor-actuator, dar si executia planelor la un agent sau la mai multi agenti. Este posibil, de exemplu, ca planificarea sa se divizeze, subplanele obtinute sa se recompuna la un moment dat si apoi din nou sa se ordoneze divizat.

Metodele de planificare se definesc mai jos:

. Un plan central este obtinut cand, planificarea se face la un nivel, pe baza unei multimi de operatori reprezentati central (baza de date, model de transformare a starilor) si, de aici, se realizeza modificarea starilor procesului reprezentate central (model de stare). Planificarea centralizata este terminata cand planul intreg, cu structura sa insiruita se poate implementa.

. De un plan divizabil se poate vorbi atunci cand, planificarea se face pe mai multe niveluri, pe baza mai multor multimi de operatori reprezentati descentral si, de aici, se realizeaza modificarea starilor procesului reprezentate global, ca un intreg. Planificarea divizata este terminata cand planele obtinute pe parti, se pot implementa ca o structura generala, insiruita.

. De un plan decentralizat se poate vorbi atunci cand, planificarea se face pe mai multe niveluri, pe baza mai multor multimi de operatori reprezentati descentral si, de aici, se realizeaza modificarea starilor procesului reprezentate local. Planificarea descentralizata este terminata cand toate planele descentrale obtinute, se pot implementa ca o structura insiruita.

Fig. 8.16 Procedeul necesar la traducerea definirii tintei intr-o structura de executat

Coordonarea planului denumeste procedeul prin care, se verifica atributele determinate ale planelor sau subplane deja realizate, plane luate ca un intreg. Se minimizeaza aici blocajele si intepenirile rezultate din interactiuni prin modificari dupa caz si se verifica atributele necesare.

Planificarea centralizata, executia si interpretarea divizate ale planului

In literatura bogata de specialitate despre sistemele multi-agent si rezolvarea divizarii problemei, se face des diferenta intre planificarea centrala pentru un agent si planificarea centrala pentru mai multi agenti.

In acest paragraf despre planificarea centrala pentru executia pe parti a planului nu se vor face aceste diferentieri, de vreme se poate trece de la o structura a planului pentru un comportament singular independent la activitatea simultana a mai multor componente.

In cele ce urmeaza se va introduce mai intai simplificarea, privind ca un comportament este implementat ca un intreg pe un singur calculator si acesta este legat intern cu senzorii si actuatoarele necesare pentru cunoasterea mediului si modificarea acestuia. Comportamentul are acces exclusiv cu senzorii si actuatoarele si nu pot fi active doua comportamente in acelasi timp pe un calculator. Atata timp cat acest agent poate fi autonom, este luat in considerare. Combinatia dintre programe, sisteme de comunicare, calculator, senzori si actuatoare se numeste agent. Cu aceste conditii limita, un agent este solicitat dupa ordonarea unui comportament pentru aceasta executie ca un mijloc de productie.

Fig. 8.17 Ordonare: a) Agent, b) echipa cu agenti cu comportamente diferite, c) echipa cu agenti cu acelasi comportament (redundant)

Se regaseste la un plan primitiv un procedeu inlocuitor :

. un agent dintr-o multime cu atributele corespunzatoare,

. o echipa cu comportamente diferite cu mai multi agenti cu atributele corespunzatoare sau

. o echipa cu agenti cu acelasi comportament cu mai multi agenti cu cu atributele corespunzatoare

care va fi coordonat (Fig. 8.17). Aceste coordonari pot sa fie considerate si ca alternative. In general sunt valabile pentru operatii inlocuitoare, conditii initiale determinate, care trebuie verificate. Daca conditiile initiale unei coordonari nu sunt realizabile, atunci se va verifiva o alta coordonare sau o alta impartire a planului.

Exemplu: posibilitati de inlantuire la vehicule

Fie cazul din figura 7.14b in care mobilele se deplaseaza un timp indelungat intr-o hala cu podeaua libera. Se pozitioneaza niste cutii de carton in hala, astfel incat sa formeze un coridor. Daca se deplaseaza ambele vehicule pe coridor, nu este loc pentru doua piste, respectiv pentru ocolire la dreapta, deci a aparut o intepenire (Fig. 8.18).

Fig. 8.18 Intepenire prin suprapunerea/micsorarea pistelor de deplasare, respectiv suprafetelor la sol a vehiculelor

Strategia de ocolire de pana acum cu compensare locala a atins problema ordonarii dinamice implicite a resursei 'cale de acces a vehicolelor' la apropierea instantanee a mobilelor. Prin restrangerea spatiului, vehiculul din stanga asteapta ca resursa sa fie eliberata de catre vehiculul din dreapta. vehiculul din stanga asteapta eliberarea spatiului de catre vehiculul din drepta. Blocarile de acest tip sunt intepeniri, care sunt greu de inlaturat, exista posibilitatea si ca ambele vehicule sa se retraga un pic. O posibilitate de analiza este aceea, de a stabili ca ambele procedee nu se vor aplica pe timp indelungat si ca agentii se gasesc in apropiere.

Ultimul exemplu arata clar ca intepenirea numai atunci se poate analiza si minimiza, cand este clar care dintre obiectele de interactiune utilizeaza resursa imputinata. Trebuie atunci, ca pentru toti potentialii agenti care utilizeaza obiectul de interactiune, sa se activeze un modul de supraveghere, care sa arate care obiect de interactiune se administreaza ca o resursa ingustata.

Coordonarea planului

Coordonarea planului denumeste procedeele, prin care se verifica atributele determinate din plane sau subplane, luate ca intreg. Dupa caz, coordonarea permite modificarea planelor sau subplanelor pentru a minimiza blocarile si intepenirile, permite asigurarea obtinerii unor eventuale atribute suplimentare.

Coordonarea planului este numai un ajutor in rezolvarea conflictelor, respectiv in compensarea optimala a influentelor negative si in utilizarea optimala a resurselor. Nu se poate asigura, prin coordonarea planului, posibilitatea de inlaturare a conflictelor aparute.

Un exemplu este situatia de fig. 8.18: mai intai, daca fiecare vehicul isi analizeaza situatia si constata ca este blocat si probabil se afla intr-o situatie de intepenire, se vor schimba planele de deplasare ale vehiculelor in scopul coordonarii. Schimbul de plane inseamna, verificarea la nivel central a dependentele planelor de un model global, general de stari si in functie de caz, realizarea coordonarii planelor pe baza multimii de operatori reprezentati clar la nivel central. Modelul general de stari este necesar, pentru a putea verifica, respectiv a recunoaste inainte de executie planelor, dependentele independent de planele realizate(Fig. 8.20).

Der Austausch der Plne dient dazu, zentral an einer Stelle gegenseitige Abhngigkeiten der Plne vor dem Hintergrund eines globalen, gemeinsam reprsentierten Zustandsmodells zu prfen und gegebenenfalls auf der Basis von genau einer zentral reprsentierten Operatormenge eine Koordination der Plne zu erreichen. Das gemeinsame Zustandsmodell ist erforderlich, um Abhngigkeiten unabhngig erstellter Plne vor einer Ausfhrung berhaupt prfen bzw. erkennen zu knnen

Fig. 8.20 coordonarea planelor necesita un model general de stari, operatori de coordonare si un scop de coordonare

Nu este in general neaparat necesar ca verificarea dependentelor si coordonarea planelor sa se realizeze in acelasi loc. Procedeu de verificare si de cordonare se poate desfasura, de aceea in mai multe locuri. Aceasta forma de coordonare distribuita este diferita in functie de situatie, pentru ca in sistemele multi agent fiecare coordonare de plan se desfasoara tipic in mai multe locuri si din mai multe puncte de vedere ale coordonarii.

Astfel, in situatia de intepenire din fig 8.18, se va realiza cate un sir de coordonare propriu fiecarui vehicul, dupa schimbul de plane de deplasare. Problema coordonarii se va prelucra din mai multe puncte de vedere, intr-adevar in mai multe locuri, dar finalizarea va fi centrala (Fig. 8.21).

Fig. 8.21 Planificarea si coordonarea planelor dupa mai multe criterii diferite in doua locuri diferite

Fiecare vehicul trebuie sa decida, cu se rezolva problema coordonarii din punctul propriu de vedere. La final acestea trebuie sa ajunga la o intelegere. Negocierea intelegerii apartine teoriei jocului cooperativ, pentru ca coordonarea planului de deplasare se face numai cant participantii s-au inteles intre ei.

Prezentarea in continuare a coordonarii planelor se bazeaza pe presupunerea ca se utilizeaza plane potential simultane, care trebuie sa conduca unul sau mai multi agenti si pentru executia acestora sunt necesare resurse suplimentare. Toate planele utilizeaza acelasi model de stare. Trebuie luate in considerare numai problema recunoasterii centrale a necesarului de coordonare si a coordonarii centrale.

Identificarea necesarului de coordonare

Pentru a determina necesarul de coordonare al planelor, se vor utiliza relatiile dintre plane, respectiv subplane, care apartin clasificarii problemelor de coordonare. In cadrul acestor relatii o importanta mare au relatiile dependente de timp. Aici se prezinta utilizarea relatiilor in sir (Fig. 8.22): inainte (before), sincronizarea inceputului cu sfarsitul (meets), simultan (equal), suprapunere in timp (overlaps), in timpul (during), Start simultan (starts), Sfarsit simultan (finishes). Pentru aceste relatii exista si relatii inverse si se pot defini si alte relatii dependente de timp.

Fig. 8.22 Relatii dependente de timp intre plane dupa Allen

Relatiile dependente de timp se utilizeaza atunci cand este necesara utilizarea simultana a resurselor. Natural, se presupune ca se pot determina sau evalua momentele de start sau de terminare, respectiv un momente de terminare impreuna cu durata de executie a planelor, subplanelor si actiunilor.

Rezolvarea conflictelor si optimizarea planelor

Cei mai importanti operatori pentru modificarea unuia sau ambelor plane pentru stapanirea conflictelor aparute la utilizarea planificata a aceleiasi resurse sunt:

. indepartarea in timp, respectiv desfacerea executiei subplanelor care contin utilizarea aceleiasi resurse. Indepartarea se poate obtine prin conditii suplimentare de start si terminare (Fig. 8.23a).

. executia subplanelor, care contin utilizarea acelorasi resurse, in spatii de timp mai scurte pentru a rezolva suprapunerea. Aceasta inseamna o solicitare mai mare a sistemelor de executie, respectiv o exigenta mai mare in predictia de utilizare a mai multor tipuri de resurse (Fig. 8.23b).

. o lungire (marire) a executiei in timp a subplanelor, care contin utilizarea acelorasi resurse. Aceasta conduce la o incacare mai mica a sistemelor de executie si o scadere a exigentei in predictia de utilizare a mai multor tipuri de resurse (Fig. 8.23c).

. utilizarea unor resurse alternative pentru minimizarea conflictelor cu privire la resurse (Fig. 8.23d).

. modificarea subplanelor intr-un astfel de mod, in care sa se poata renunta in totalitate la utilizarea resurselor critice (Fig. 8.23e).

Fig. 8.23 Stapanirea conflictelor pe baza utilizarii simultane a unor resurse

Acesti operatori de modificare a planelor nu sunt o solutie pentru planele cu atribute tinta contradictorii. Asemenea combinatii de plane nu se pot coordona si se denumesc incompatibile. In cazul resurselor uzate nu se utilizeaza toti operatorii.