1. Structuri holonice. Agenti inteligenti, utilitatea lor şi poziţionarea în cadrul domeniului mai larg al IA

Intotdeauna a existat perspectiva de a include sisteme computerizate autonome in viata de zi cuzi. Acest lucru a devenit acum posibil datorita progreselor din domeniul Inteligentei Artificiale(IA).In ultimii ani, tehnicile de IA au devenit mult mai robuste si mai complexe. Datorita succeselor obtinute in acest domeniu,cercetatorii din domeniul IA si-au castigat dreptul de a incepe sa examineze implicatiile sistemelor multiagent asupra lumii reale. Exista o multitudine de definitii ale agentilor inteligenti dar urmatoarele proprietati suntdefinitorii :-autonomia-proactivitate si/sau reactivitate-continuitate in timp

Autonomia se refera la posibilitatea unui agent de a-si controla propriile actiuni independent de alte entitati,interactionand cu acestea doar in cazul in care doreste.De obicei un agent autonom nu apeleaza la altcineva(alt agent sau fiinta umana)decat daca nu poseda suficiente cunostiinte pentru a indeplini de unul singur o anumita atributie.Reactivitatea se refera la capacitatea agentilor de a mentine o interactiune neintrerupta cu mediul inconjurator si de a raspunde in timp util la schimbarile ce apar in mediu adica de a se adapta la acestea.Pro-activitate se refera la capacitatea unui agent de a lua initiativa;el nu este condus deevenimente ci este capabil de a-si genera scopurile se de a actiona rational pentru a le indeplini.Continuitate in timp.Aceasta proprietate se refera la capacitatea agentilor de a-si suspenda,termina sau continua executia dar, daca starea unui agent este suspendata, aceasta trebuie sa fie memorata intr-o anumita maniera astfel incat sa poata fi recreata atunci cand agentul este reanimat .

Alte atribute ale agentilor-adaptarea-capacitatea de a comunica si de a coopera cu alti agenti in ordine de a-si indepliniatributiile-capacitatea de invatare.Agentii pot,in anumite circumstante,sa invete din evenimentelerepetitive ce au loc in mediul inconjurator astfel incat sa poata prezice evenimentele viitoare si in anumite cazuri,sa actioneze asupra mediului-mobilitate .capacitatea de a se misca de la un sistem la altul-negociere-task-oriented-flexibilitate,abilitate sociala,flexibilitate

Un sistem multiagent este un sistem care constã din cel putin doi agenti inteligenti capabili sã interactioneze între ei în vederea realizãrii unor scopuri individuale sau comune (scopuri globale) si care partajeazã acelasi mediu de lucru.

Sistemele multiagent (Multiagent Systems - MAS) constitue un subcamp al Inteligentei

1

Artificiale a carui scop este de a furniza principiile pentru constructia de sisteme complexe incluzand agenti multipli si mecanisme de control a comportarii agentilor independenti. Desi capacitatea de a controla comportarea agentilor autonomi este una noua,acest domeniu(al sistemelor multiagent) avanseaza rapid datorita faptului ca este construit pe baza unor informatii deja existente si anume acelea din domeniul Inteligentei Artificiale Distribuite(DAI).DAI a existat ca un subdomeniu al Inteligentei Artificiale de mai putin de 2 decade.DAI este impartit in doua subdiscipline: DSP(Distributed Problem Solving) si MAS(Multiagent Systems). Principalele teme considerate in DSP sunt problemele legate de managementul informatiilor cum ar fi descompunerea task-urilor si sinteza solutiilor. De exemplu,o problema poate fi descompusa in mai multe subprobleme,nu total independente ,care pot fi rezolvate de diferite procesoare.Apoi,solutiile rezultate pot fi sintetizate in solutia problemei originale. MAS permite ca aceste subprobleme sa fie distribuite agentilor - fiecare avand interesele si scopurile lui.

Desi exista multe moduri de a diviza MAS,acest studiu este organizat tinand cont de doua dimensiuni principale:heterogentitatea agentilor si cantitatea de comunicatii dintre agenti.Incepand cu cel mai simplu scenariu de multiagent, agenti omogeni si necomuniativi si pana la cele mai complexe sisteme multiagent heterogene,o intreaga gama de posibile sisteme multiagent este considerata.

Utilitatea sistemelor multiagentMotive pentru a utiliza sistemele multiagent:-unele domenii au nevoie de ele-paralelism-robustete-scalabilitate-programare simpla-pentru a studia inteligenta-rezolvare eficienta a problemelor

Ar fi ridicol sa pretindem ca MAS sa fie utilizate in proiectarea tuturor sistemelor complexe dar sunt domenii care cer aceasta solutie.In particular,un exemplu de domeniu care are nevoie de MAS ,este cel medical.Conform unui studiu,este nevoie de agenti care sa reprezinte interesele celor din personalul spitalului.Angajatii spitalului au diferite interese...de la asistente care vor sa minimizeze timpul de spitalizare a bolnavilor la operatori cu raze X care vor sa mareasca performantele masinilor.Datorita diferitelor criterii de evaluare a programului fiecarei persoane,acestea trebuie sa fie reprezentate de agenti separati in ordine de a fi luate in calcul interesele fiecareia.Chiar si in domenii in care pot se folosi sisteme ce nu sunt distribuite ,exista posibilitatea de a utiliza MAS.Avand agenti multipli ,se poate mari viteza de operare a sistemului prin utilizarea unei metode de calcul paralel.De exemplu,un domeniu care poate fi rapid divizat incomponente, un sistem care prezinta task-uri independente poate beneficia de agenti speciali.Si mai mult,paralelismul sistemelor multiagent poate ajuta atunci cand avem de-a face cu limitarile impuse de insuficienta timpului pe care il avem la dispozitie.Atata timp cat paralelismul este obtinut prin asignarea diferitelor task-uri unor agenti diferiti, robustnetea este un beneficiu al sistemelor multiagent care poseda agenti redundanti. Daca controlul si responsabilitatile sunt impartite suficient intre diferiti agenti,sistemul poate tolera ratari din partea unuia sau mai multi agenti. Dar in cazul in care exista un singur procesor sau agent care controleaza toata activitatea,o singura greseala poate duce la caderea intregului sistem.Desi un sistem multiagent nu are nevoie neaparat sa fie implementat pe multiple

2

procesoare,pentru a furniza o buna robustete impotriva greselilor ce pot apare,agenti ar trebui sa fie distribuiti pe mai multe masini. Un alt avantaj este acela ca noi agenti pot fi adaugati sistemului cu mai multa usurinta decat poate fi adaugata o noua capacitate unui sistem monolitic.Sisteme a caror capacitati si parametri este posibil sa aiba nevoie sa fie schimbati in timp sau intre agenti,pot deasemenea sa beneficieze de acest avantaj al sistemelor multiagent. Din perspectiva programatorului, modularitatea sistemelor multiagent poate conduce la o mai simpla programare. Decat sa asignezi intregul task unui agent centralizat, programatorii pot identifica subtask-uri si asigna controlul acestor subtaskuri unor agenti diferiti.In acest mod se poate rezolva problema divizarii timpului unui singur agent in mai multe parti diferite.

1.1 TaxonomiaConform taxonomiei oferite recent de Parunak ([8]),unele dintre cele mai importantecaracteristici ale sitsemelor multiagent sunt:- functia sistemului- arhitectura agentului(gradul de eterogen,reactivitate vs deliberare)- arhitectura sistemului(comunicatii,protocoale,implicarea omului)Alte taxonomii cred ca cele mai importante aspecte ale agentilor sunt: gradul de eterogenitate si gradul de comunicare. Orice alt aspect a agentilor in MAS este discutat in cadrul acestor domenii. De exemplu,gradul in care diferiti agenti joaca diferite roluri este cu siguranta o tema importanta a sistemelor multiagent dar aici ea este discutata in scenariul eterogenitatii sistemelor multiagent necomunicativi.Cele 3 combinatii de eterogenitate si comunicatie (agenti omogeni si necomunicativi, agenti eterogeni si necomunicativi,agenti eterogeni si comunicativi)sunt prezentati in ordinea cresterii complexitatii si puterii(vezi Figura 1).

Agenti omogeni necomunicativi:- agenti reactivi vs agenti deliberativi- perspectiva locala sau globala- modelarea starii altor agenti-modul in care acesti agenti pot afecta alti agenti

3

Agenti eterogeni necomunicativi:- bunavointa vs competitivitate- modelarea actiunilor,scopurilor si cunostiintelor altora- managementul resurselor- conventii sociale- agenti care evolueaza

Agenti eterogeni comunicativi:- se inteleg unii pe altii- planifica actiunii comunicative- bunavointa vs competitivitate- managementul resurselor- adevar in comunicatieAceste proprietati ale agentilor vor fi discutate pe parcursul lucrarii.

1.2 Sisteme cu un singur agent vs. Sisteme Multiagent

Inainte de a studia si de a categorisi sistemele multiagent trebuie mai intai sa avem in vedere sistemele centralizate cu un singur agent care ia toate deciziile .Vom considera pt acest studiu un sistem (cu un singur agent) complex,centralizat ,intr-un domeniu care ar putea permite si un sistem multiagent. Un sistem cu un singur agent ar putea avea mai multe entitati cativa actuatori sau chiar cativa roboti.Oricum,daca fiecare entitate trimite rezultatele spre, si isi primeste actiunile pe care trebuie sa le indeplineasca de la un singur proces central,atunci avem doar un singur agent . procesul central.Agentul central modeleaza fiecare entitate .Sectiunea ce urmeaza compara sistemele cu un singur agent cu cele multiagent.

1.2.1 Sisteme cu un singur agentDesi poate parea ca sistemele cu un singur agent ar trebui sa fie mai simple decat sistemele multiagent ,cand ai de-a face cu un task fix, complex , sistemele multiagent ofera mai multa usurinta de lucru.

Fig.1.2

In general,un agent dintr-un sistem cu un singur agent modeleaza el insusi mediul si interactiunile acestuia. Desigur, agentul insusi este parte a mediului dar daca exsita altiagenti, acestia sunt considerati parti ale mediului.

4

1.2.2 Sisteme MultiagentSistemele multiagent difera de cele cu un singur agent prin aceea ca exista mai multi agenti care isi indeplinesc propriile scopuri si actiuni.In cele mai complete sisteme multiagent,exista o interactiune directa intre agenti adica acestia comunica.Desi aceasta interactiune poate fi vazuta ca un stimul din mediu,vom prezenta comunicatia dintre agenti ca fiind separata de mediu inconjurator.Din perspectiva unui agent individual,sistemele multiagent difera de sistemele cu un singur agent mai mult datorita faptului ca in primul caz,dinamica mediului poate fi determinata de alti agenti.Figura de mai jos (Figura 1.3) ilustreaza faptul ca fiecare agent este o parte a mediului si ca este modelat ca o simpla entitate.Pot exista un numar variat de agenti ,cu diferite grade de eterogenitate si cu sau fara capacitatea de a comunica direct.Pornind de la cel mai general caz prezentat aici,incepem prin a elimina comunicatia si eterogenitatea pentru a descrie sistemele multiagent omogeni si necomunicativi.Vom prezenta mai apoi sisteme multiagent care posedaaceste proprietati.

Fig. 1.3

Rezolvarea Distribuita a ProblemelorEste indicat sa folosim DPS deoarece creste viteza procesului de obtinere a solutiei,expertiza si rezolvarea problemelor pot fi in mod inerent distribuite, cunostintele necesare rezolvarii problemelor pot fi distribuite si nu in ultimul rand, poate fi nevoie ca solutia sa fie distribuita pentru a fi executata.DAI se preocupa de Granularitatea Agentilor, Eterogenitatea Agentilor, Metode de controldistribuite (intre agenti) si de Posibilitati de Comunicare.

1.3 Tipuri de agentiAgenti colaborativiAgentii colaborativi rezolva o gama larga de probleme. Acesti agenti asigura interconectareasistemelor mai vechi, ofera solutii pentru problemele distribuite bazandu-se pe informatia colectata din sisteme distribuite.Pentru cresterea modularizarii aplicatiilor bazate pe acest tip de agenti, acestia trebuie sa

5

respecte urmatoarele principii: siguranta, viteza si flexibilitate.Cercetarea in acest domeniu poate fi extinsa in principal si prin observatiile din alte domeniide activitate, cum ar fi studiul despre modul cum functioneaza societatea umana. Societatea umana constituie baza de plecare in studiul multor alte domenii datorita exemplului pe care ni-l poate oferi (relatiile dintre oameni, comunicarea, interactiunea).Proiectarea sistemelor care au la baza agenti colaborativi trebuie sa ia in considerareurmatoarele aspecte:- comunicarea intre agenti- stabilitatea, scalabilitatea si performanta agentilor- integrarea cu tehnologiile si sistemele mai vechi- capacitatea de a invata a agentilor- evaluarea sistemelor cu agenti colaborativiAgenti pentru interfata ( Interface Agents)Acesti agenti sunt responsabili pentru interactiunea cu utilizatorul si au rolul de „PersonalAssistant”.Ei au rolul de a urmari utilizatorul si de a invata din comportamentul acestora dar pot invata si din schimbul de informatii cu alti agenti de interfata. Putem extinde astfel conceptul de agenti colaborativi in „Collaborative interface agents”.Agentii de interfata scutesc omul de munca plictisitoare si de rutina. Acestia pot inregistraactiunile tipice ale unui utilizator, luandu-i locul acestuia in citirea emailurilor neimportante(„junkmail”), in cautarea informatiei necesare si in locul altor activitati specifice. Agentii de interfata se adapteaza preferintelor si oboceiurilor utilizatorului actionand in consecinta cu profilul acestuia. Capacitatile acestor agenti pot fi extinse pana la alegerea modalitatilor si cantitatii de informatie ce poate fi impartasita intre diferiti utilizatori.Astfel agentii de interfata sunt in principal responsabili cu invatarea si adaptarea la cerinteleutilizatorului.

Agenti mobiliAgentii mobili sunt cei care sunt capabili sa se mute intre diferite sisteme in momentulexecutiei. Acesta este un nou concept menit sa inlocuiasca comunicarea bazata pe mesaje sau prin memorie partajata care se utiliza pana in acest moment.Agentii mobili opereaza mult mai bine cu sursele de informatii datorita capacitatii de a sedeplasa intre diferite sisteme. Ei ilustreaza cel mai bine principiile de baza ale agentilor : autonomia si proactivitatea.Avantajele agentilor mobili sunt urmatoarele:- costuri reduse pentru comunicarea dintre agenti- accesul redus la resursele locale ale sistemului- usurinta coordinarii- programul se executa asincron (“Asynchronous Computing”)- sporesc flexibilitatea arhitecturilor distribuite- regandirea conceptelor de design softLa Universitatea Tromso s-au dezvoltat deja niste proiecte care utilizeaza agenti mobili in laboratoarele Dag Johansen. S-au creat astfel prototipi “distributed crawling”( agenti mobili –crawlere – care se deplaseaza acolo unde se afla informatia dorita).

Agenti informationaliAcesti agenti ajuta utilizatorul in cautarea si adunarea informatiilor. Selectia si sintezainformatiilor cunoasterii se face pe baza informatiei. Abundenta informatiei din prezent face foarte dificila filtrarea si selectia si de aceea existenta acestor agenti este foarte utila in manipularea cantitatii uriase de informatii.Importante beneficii financiare pot fi obtinute prin dezvoltarea motoarelor de cautare ( ex.

6

Google) care ofera o viteza foarte mare atat la cautare cat si la transfer.

Agenti reactiviAgentii reactivi sunt agentii care reactioneaza la stimuli simpli. Reactiile pot fi foarte variatedatorita comportarii emergente a acestor agenti. Capacitatile sporite de invatare (comparabile cu retelele neuronale si “GP/Evolutionary computation”) constituie principalele avantaje ale acestor tipuri de agenti.

Agenti hibriziAgentii hibrizi combina mai multe tipuri de agenti pentru a obtine rezultate mai bune peransamblu. Se poate combina ceea ce este mai bun de la mai multe tipuri de agenti.De ex. se pot mixa agentii informationali cu agentii mobili.

Agenti eterogeniAgentii eterogeni pot fi vazuti ca sisteme care contin agenti de diferite tipuri: agenti mobili,agenti de interfata. Motivatia introducerii unor astfel de agenti ar fi ca aplicatiile “standalone” pot oferi servicii printr-un “wrapping agent”(un agent care impacheteaza mai multe functii alediferitilor agenti), sistemele vechi ar putea avea o viata mai lunga prin usurinta interactiunii cu alte sisteme iar ingineria software care are la baza agentii ar putea aduce mari beneficii printr-o abstractizare mai mare.

1.4 Arhitecturi multi-agent

Sistemele BlackboardFunctionarea unui sistem Blackboard poate fi descrisa ca: “O colectie de agenti inteligenti seaduna in jurul unei “table”, se uita la informatia scrisa pe acea tabla, o analizeaza si trag concluzii”.O arhitectura Blackboard are trei componente majore:- o memorie globala ierarhica bine organizata sau o baza de date, numita “Blackboard” incare se salveaza solutiile generate de sursele de cunostinte- o colectie de surse de cunostinte care genereaza solutii independente pentru „Blackboard”folosind sisteme expert, retele neuronale si analiza numerica- un modul separat de control sau un Scheduler care verifica sursele de cunostinte si oselecteaza pe cea mai potrivita (Definitie luata de la: http://www.primenet.com/pcai/New_Home_Page/ai_info/blackboard_t echnology.html)Aceste sisteme pot avea si caracteristici aditionale: reprezentarea flexibila a informatieipentru salvarea in/pe Blackboard, ascunderea reprezentarii interne fata de utilizator, folosirea unui limbaj comun pentru intercomunicare. De asemenea unele „Blackboard” pot genera intern solutii care conduc la contradictii sau noi linii de rationament.Avantajele sistemelor „Blackboard” constituie in faptul ca ele permit separarea cunoasteriiin module independente deci permitand fiecarui modul sa foloseasca tehnologia cea mai potrivita pentru a ajunge la cea mai buna si eficienta solutie dar totodata si in faptul ca existenta modulelor independente faciliteaza distributia acestora pe mai multe procesoare.Toti agentii pot vedea toate „tablele” tot timpul, vizualizand de fapt starea curenta a solutiei.Fiecare agent poate scrie propriile concluzii pe „tabla” in orice moment fara a aparea coliziuni.Momentul scrierii pe „tabla” nu va afecta munca celorlalti agenti.

7

Conceptul .Actor.Obiectivele stabilite prin design in acest caz sunt: informatie distribuita si mutabila,reconfigurabilitate si concurenta inerenta.„Actorii” pot executa trei actiuni:- trimit informatie catre ei insisi sau alti actori- creeaza alti actori- specifica o comportare inlocuitoare( alt actor)Procesarea „actor” este reactiva. Actorul este adormit pana cand primeste comunicatia. Elproceseaza practic o secventa liniara de programe. Sosirea mesajelor nu este intotdeauna in aceeasi ordine cu cea in care au fost trimise.De asemenea nu exista variabile locale in modele „actor” simple, iar comunicarea se faceprin email, aceasta fiind o componenta importanta a sistemului.Dintre proprietatile „actorului” am putea aminti:- modelul actorului este asincron- comunicarea este explicita fara variabile comune- securitatea si controlul comunicarii sunt destul de slabe deoareace: fiecare mesaj trimiseste eventual livrat si fiecare algoritm eventual progreseaza

Scalabilitatea MAS (Multi-Agent Systems)Scalabilitatea se defineste ca abilitatea unei solutii a unei probleme de a functiona si atuncicand dimensiunea problemei creste.In cazul agentilor prin cresterea dimensiunii problemei ne putem referi la:- cresterea numarului total de agenti dintr-o platforma din MAS- cresterea numarului total de agenti de pe mai multe platforme dintr-un MAS- schimbari in topologiile de comunicatie intre platforme- cresterea numarului total de platforme dintr-un MAS- cresterea cantitatii de informatie pe care o utilizeaza agentii- cresterea diversitatii agentilorPrincipiul lui Gustavson despre accelerarea maxima in sistemele paralele spune ca dacatask-ul principal efectuat de un sistem multi-agent implica n agenti si timpul necesar pentru partea de executie secventiala din solutia problemei este s, iar proportia timpului cat executia se poate face in parallel este p, atunci acceleratia maxima este:(s + (p*n))/(s+p) = n + (1-n)*sAcceleratia este liniara daca timpul secvential s=0

Ca tehnici generale pentru a reliza sisteme multi-agent scalabile ar fi: micsorareaintarzierilor in comunicare, distribuirea aplicatiei sau replicarea.

Conceptul Agora

In gandirea unui sistem multi-agent se au in vedere urmatoarii pasi: identificarea unui set descenarii posbile, analiza scenariilor si identificarea setului de cerinte, integrarea suportului pentru impartirea si managementul informatiei pentru procesele cooperative, designul arhitecturii MAS care sa integreze toate cerintele, implementarea arhitecturii si aplicarea arhitecturii in rezolvarea problemelor specifice.In cazul arhitecturii Agora putem regasi informatii despre agentii inregistrati, informatii

8

despre sistemul Agora si informatii despre alte sisteme Agora si cunostinte comune. Informatiile despre agentii inregistrati contin obiectivele, credinte, dorinte si intentii(Beliefs, Desires and Intentions - BDI), taskurile active si agentii prieteni.

Agora vs Blackboards- Agora nu permite acces global- Agora permite crearea flexibila si are o unitate de control mai flexibila- Agora este orientata pentru suportul functionarii cooperative- Agora nu este atat de low-level ca Blackboards

1.5 Arhitecturi pentru agentiArhitecturile pentru agenti reprezinta miscarea de la specificatii la implementare. Suntfoarte importante in construirea sistemelor de calcul care satisfac proprietatile specificate de teoriile agentilor si in luarea deciziilor cu privire la ce structuri software sunt apropiate.Kaelbling definea arhitecturile agent ca ”O colectie specifica de module software( sauhardware), gandite ca niste cutii cu sageti indicand curgerea datelor si a informatiei de controlprintre module. O vizualizare mai abstracta a arhitecturii este ca o metodologie generala pentru conceperea modulelor pentru fiecare task in parte”.

Tipuri de arhitecturi pentru agentiExista trei mari tipuri de arhitecturi:1. Arhitecturi agent deliberative – sunt un fel de model simbolic al lumii, bazat pe inteligenta artificiala simbolica2. Arhitecturi reactive – nu sunt bazate pe o reprezentare simbolica centrala a lumii si nici peo motivatie complexa3. Arhitecturi hibride – o amestecare a arhitecturilor reactiva cu cea deliberativa

Arhitecturi deliberativeArhitecturile deliberative sunt un model simbolic explicit al lumii. Metodele de decizie sebazeaza pe motivatia logica, pattern matching si pe manipularea simbolica.Primele sisteme erau un fel de sisteme planificatoare ( Planning systems – STRIPS) careaveau legaturi logice foarte stranse.( De ex. Planificarea salilor intr-o universitate). Ele utilizeaza algoritmi foarte simpli de planificare . Sistemele trebuiau sa execute o secventa de actiuni care sa atinga scopul dorit. Totusi aceasta planificare era destul de ineficienta. Aceste sisteme se bazau pe o descriere simbolica a lumii, pe o reprezentare a societatii umane.

Arhitecturi reactiveArhitecturile inteligente pot fi generate fara o reprezentare explicita simbolica in AI.Comportamentul inteligent poate fi generat fara interventia mecanismelor abstracte implicate in procesul de rationament simbolic (inteligenta artificiala). Inteligenta este o proprietate emergenta a unor sisteme complexe. Ea rezulta ca un efect al combinarii componentelor. Inteligenta reala este situata in lumea reala, nu in sisteme impartite cum ar fi sistemele expert sau cele bazate pe demonstrarea de teoreme.Comportamentul inteligent apare ca un rezultat al interactiunilor dintre agent si mediul sauinconjurator. Reactivitatea este un model de activitate bazat pe trasaturi de comportament.Perceptia poate fi impartita in mai multe componente: semantica datelor de intrare pentru

9

agent, un set de fapte ( baza de cunostinte), o specificare a tranzitiilor si actiunile specificate prin semantica datelor de iesire( reactia de fapt). Un exemplu de arhitectura reactiva poate fi si urmatorul

Un alt exemplu poate fi cel al unui robot. De exemplu, obiectivul robotului este sa explore oplaneta indepartata ( Marte) si mai concret sa colecteze esantioane dintr-o roca rara. Specificarea tarnzitiilor ( algoritmul) ar arata in felul urmator:- daca detecteaza un obstacol atunci schimba directia- daca are esantioane si se afla la baza atunci le depoziteaza- daca are esantioane si nu se afla la baza atunci se duce la baza- daca detecteaza un esantion atunci il colecteaza- daca „true” atunci se misca aleator

ConcluziiAgentii si-au gasit o aplicare foarte buna in domeniul comertului electronic. Atribute generale ale agentilor ca delegarea taskurilor, personalizarea, functionarea continua, semi-autonomia se preteaza foarte bine in aceste aplicatii.Aspectele comertului electronic (E-Commerce)ca securitatea, increderea, reputatia, legile, mecanismele de plati, publicitatea, cataloagele on-line, suportul multimedia trebuie luate in calcul in gandirea si implementarea agentilor. Modelul de comportament al cumparatorului este foarte complex si trebuie sa includa toate etapele de la identificare, negociere, cumparare si livrare, servicii si evaluare.Domeniile in care isi gasesc astazi agentii inteligenti aplicabilitatea vor determina directiileviitoare in dezvoltarea acestui domeniu. Societatea umana constituie in orice caz o baza pentru orice cercetare in domeniul inteligentei artificiale si al agentilor inteligenti.

10

2. Modele matematice fuzzy pentru structuri holonice

Acest capitol isi propune minimizarea entropiei fuzzy privita ca o proprietate de independanţă a structurilor holonice. Cand este aplicată în contextul sistemelor multi-agent această proprietate conduce la gruparea automată a agenţilor în organizaţii holonice. Când modelăm software întreprinderile cu agenţi, proprietatea se întoarce în caracteristica inerenta ale organizaţiilor virtuale holonice care permit gruparea celor mai buni parteneri si/sau resurse la toate nivelurile întreprinderii holonice (virtuale). Aplicabilitatea metodelor de reconfigurare on-line ale organizatiilor dinamice virtuale este dovedita printr-un exemplu de simulare.

O structură holonică este o holarhie de entităţi colaborative, în care o entitate este privită ca un holon. (Aici termenul entitate este folosit generic: entitate,sistem, “lucru”, agent). Termenul holon a fost inventat de Artur Koestler pentru a denumi entităţi care exprimă în acelaşi timp capacitătea de autonomie si cooperare si care necesită un echilibru ale fortelor contradictorii care definesc fiecare din aceste proprietaţi ale nivelului de comportament. O principala caracteristică a holonului o reprezintă gradul de granulozitate manifestat prin intermediul copierii in sturcturi similare la niveluri multi-rezoluţie. Asemanator cu o descompunere heterarhică care reprezintă o grupare de entităţi - numită holarhie. O entitate holonică prezinta trei niveluri de granulatie :

2.1 Nivelul global de colaborare intre entitati

La acest nivel fiecare grup de entitati-holonice dintr-o holarhie colaborativă realizează un produs sau un serviciu. Criteriul de grupare suportă actiuni si eficienţa maximă. În mod normal acest nivel a fost privit ca un lant static de clienti si furnizori prin care fiecare actiune si informaţie a fost mutată catre ultimul client care solicită produsul ultimului furnizor care îl poate oferi. În interiorul entităţii holonice, modelul lantului de aprovizionare este înlocuit de modelul colaborarii holarhice. (Fig. 1)

11

Cu fiecare partener collaborator modelat ca un agent care înglobează toate anstractizările relevante a unei cooperari particulare, apare un grup dynamic virtual (Fig.1) care poate fi configurat on-line conform tintelor collaborative (prin gasirea celui mai bun partener în vederea colaborării). O astfel de holarhie dinamica de colaborare poate face fata unor perturbaţii neasteptate (inlocuirea unui partener colaborant care nu poate termina la timp ) prin intermediul reoconfigurarii on-line al sistemului deschis pe care îl reprezintă. Acesta furnizează sarcini on-line partenerilor disponibili precum si mecanismele de desfăşurare care asigură ordinea raportarii erorilor in timp real precum si ordinea cererilor.

2.2 Nivelul intra-entitate

Odata ce entitatea si-a asumat responsabilitatea pentru partea de lucru asignata, va trebui sa isi organizeze propriile sale resurse pentru a termina la timp in concordanta cu cerintele grupurilor colaborative. Planificarea si programarea dinamica a resurselor la acest nivel permite functionarea reconfigurarii si a flaxibilităţii prin intermediul selectarii unităţilor funcţionale, reasignarea locaţiilor sale, şi definirea interconexiunilor lor (ocolorea maşinii defecte, schimbarea funcţiilor masinii multi-funcţionale).

Acesta e realizată prin intermediul raspunsului mecanismului dinamic virtual de grupare care are acum fiecare resursă in interiorul entităţii clonate ca un agent care abstractizează aceste caracteristici functionale relevante taskului specific asignat de holarhia colaboranta la partener. Reconfigurarea programarii, pentru a face fata unor noi ordine sau perturbatii neasteptate () permite prin intermediul regruparii agentilor reprezintă resursele actuale ale entitaţii, Fig.2. Este prezentat principalul criteriu al realocarii resurselor atunci cand este realizata minimizarea costului prin criteriide optimizare.

2.3 Nivelul masina (agentul fizic)

12

Acest nivel este in legatura cu controlul distribuit al masinii care executa un task. Pentru o fabricatie rapida prin repartizarea reconfigurarii, elementele de automatizare inteligente distribuite ale fiecarei masini sunt clonate ca agenti care abtractizeaza toti parametrii necesari configurarii sistemului de control holonic , conducand productia distribuita.

Fig. 3: Nivele Fizice si logice ale unei entitati holonice

Un rol major in structura organizatorica a oricarei entitati holonice il joaca agentul mediator (fig.4). Prin urmare vom demonstra cu ajutorul incluziunii ca minimizarea entropiei fuzzy in interiorul agentului mediator se intinde de la nivelul logic pana la o structura holonica perfecta a nivelului fizic.

2.4 Aproximarea

Un sistem multiagent (MAS) este privit ca un sistem dinamic in care agentii schimba informatii organizate cu scopul de a atinge tinta stabilita. Cunostintele optime corespund unui nivel optim al organizarii informationale si al distributiei de-a lungul agentilor. Aceasta inseamna ca putem considera entropia ca o masura a gradului in care ordinea informatiilor se propaga de-a lungul agentilor. De obicei aceasta informatie este incerta, necesitand cateva modalitati de modelare pentru a face fata unor diferite aspecte ale incertitudinii. Setul de teorie fuzzy ofera un spaţiu de lucru adecvat care necesită folosirea entropiei fuzzy generalizate[5].

Putem privi agentii MAS ca fiind sub influenta campului informational care conduce interactiunile inter-agent catre realizarea “echilibrului” cu alti agenti cu respectarea acestei entropii. Entropia fuzzy generalizata reprezinta masurarea potentialului acestui camp si echilibru pentru agentii aflati sub aceasta influenta corespunde unei organizari optime a informatiei de-a lungul MAS cu respectarea realizarii tintei propuse. Cand obiectivul final al MAS se schimba (datorita unor evenimente neasteptate, precum si necesitatea de a schimba un partener, un defect la masina, etc) punctul de echilibru se schimba precum si o noua redistribuire a informatiei tuturor agentilor cu noi interactiuni intre agenti. Acest mecanism care permite reconfigurarea dinamica a sistemului cu redistribuirea prioritatilor reprezinta

13

esenta structurii dinamice holonice. In urmatoarele subcapitole, vom demonstra ca gruparea agentilor dintro structura holonica MAS ajunge la echilibru care asigura realizarea optima a taskului propus.

2.5 Modelarea vaga in MAS - Formularea Problemei

Este deja cunoscut faptul ca printre alte aspecte ale incertitudinii, vagi cu informatii care sunt necorespunzatoare. In contextual sistemelor MAS aceasta inseamna ca distingerea clara intre un posibil plan de extindere impus de tinta si o conducere a unui plan, pe de alta parte, la o tinta diferita sunt lucruri greu de distins. Noi o numim impartirea configurarii grupurilor in care asocierea tuturor grupurilor este identica setului unui agent atunci cand grupurile nu sunt suprapuse. Daca grupurile se suprapun ( niste agenti sunt in acelasi timp in doua grupuri ) configuraia gruparii se numeste acoperire. Definim un plan la inceputul succederii tuturor starilor de tanzitie ale MAS pana cand ajunge la scopul propus. Fiecare stare a MAS este descrisa de o configuratie sigura de grupare care acopera un set de agenţi.

Daca informatia de-a lungul MAS este vaga, unul poate construi numai o colectie de planuri-sursa (un set de configuratii de grupuri considerate ca surse pentru planuri) associate cu o tinta globala specifica. Exista doua diferente principale intre un plan si un plan-sursa. Prima, intrun plan, existenta configurarii la timp a grupurilor este clar specificata, in timp ce la un plan-sursa de obicei este necunoscuta. In al doilea rand , intrun plan, configuratiile pot fi repetate in timp ce la planul-sursa include numai configuratii diferite care pot fi extrase pentru a construe un plan, urmand niste strategii. Modelul nostru incepe cu urmatoarele ipoteze:

H1 Desi sistemele multi-agent (MAS) reprezinta o colectie de entitati deterministe (numiti agenti), comportamentul lor poate fi stochastic, datorita perturbatiilor interne si externe.H2 Nu e disponibila nici o cunostinta importanta despre MAS insa scopul general al sistemului(astfel este cunoscuta, cel putin o tinta globala care poate fi atinsa printro maniera clara) si numarul de agenti (notat cu N)H3 Sunt observabile structurile de configuratii ale grupurilor si aparitiile lor cot fi contorizate in timpul evolutiei MAS de la starea initiala la cea finala, pentru orice tinta data. Incepand cu aceasta informatie incerta, problema o reprezinta furnizarea modelelor fuzzy ale MAS, utilizate in selectarea celui mai putin incert (cel mai punin vag) plan-sursa.

2.6 Formularea matematica a problemei

Fie AN={an}n∈1 ,N setul de N≥1 agenti care apartin MAS. Bazându-ne numai pe

informatia incerta iniţială, se poate construi o familie P={Pk }k∈1 , K , care conţine K≥1

colecţii de configuraţii de grupuri, pentru o tinta globala presetata. Fiecare Pk (k∈1, K ) poate fi asociata ca un plan-sursă in sensul că poate fi o sursa ale partitiilor pentru un plan

MAS. Astfel, un plan sursă este exprimat ca o colecţie de M k≥1configuraţii de grupare

14

diferite acoperind AN , care pot aparea in timp de MAS evoluează către scopul final: Pk={Pk , m}m∈1, M k .

Singura informaţie disponibilă despre Pk este gradul de apariţie asociat fiecarei astfel de

configuratie, Pk , m , care poate fi asignat ca un număr α k , m∈[0,1 ].Astfel, corespondenţa gradelor

de apariţie este membră a unei familii bi-dimensionale {α k , m}k∈1 , K ;m∈1 , M k , care, precum o stare

anterioara, cuantifică toate informaţiile disponibile despre MAS.In acest context, dorim sa construim o masura a incertitudinii, V (de la vag), de tip fuzzy,

valoare reală, definită pe un set al tuturor planurilor sursa ale multimii AN si care sa

optimizeze in ordinea selectarii planului sursa cel mai putin vag din familia P={Pk }k∈1 , K :

Pk 0=arg opt

k ∈1, KV (Pk )

, where k o∈1 , K . (2.1)

Costul V al functiei ceruta in problema (2.1) va fi construit folosind o masura a fuzzificarii [6]. Prezentam in continuare pasii acestei constructii

2.7 Aparitia structurilor holonice

2.7.1 Relatii fuzzy intre agenţi

Vom modela interacţiunile agenţilor cu ajutorul relaţiilor fuzzy considerând că doi agenţi sunt în relaţie dacă au schimb de informaţii. Cand exista un schimb de informaţii intre 2 agenţi apartinand aceluiasi grup se pot descrie configruratiile grupurilor utilizând aceste relaţii

fuzzy. Famia de relatii fuzzy {Rk}k ∈1, K intre agenţii MAS ( AN ) este construită folosind numerele {α k , m}k∈1 , K ;m∈1 , M k si familia de planuri sursa {Pk}k ∈1, K . Considerând k∈1 , K si

m∈1 , M k fixate arbitrar.

15

In construirea relaţiilor fuzzy Rk , plecam de la observaţia că asocierea agenţilor in grupuri este asemanatoare cu gruparea lor in clase compatibile sau echivalente, dandu-le o relaţie de legatura (binara) intre ei. Proprietăţile compatibile ale reflexivităţii si simetriei sunt indeplinite.

Relaţia de corespondenţă dată de Rk , m poate descrisă de : doi agenţi sunt legati dacă fac parte

din acelaşi grup. Obtinem ca A şi respetiv B nu sunt in relaţie Rk , m (unde a,b∈ AN ) sunt

exprimati de aRk , mb si aRk , mb . Relatia Rk , m poate fi de asemenea descrisa de fiind o matrice

N×N , unde H k ,m∈ℜN×N

- matricea caracteristicilor – cu elementele Hk , m [i , j ]ce au valori 0 sau 1, depinzând dacă un agent este sau nu in acelasi grup. (Aici, ℜeste un set de numere reale). Astfel,

H k ,m[ i , j ]=def

¿ {1 , ai Rk , m a j¿ ¿¿, ∀ i , j∈1 , N . (2.2)

Această matrice este simetrică (evident dacă aRk , mb atunci bRk , ma ) iar diagonala principala are valoarea 1 (fiecare agent se gaseste in acelasi grup cu el insusi). Acest lucru ne permite sa

specificam complet configuraţia Pk , m , asa cum am demonstrat urmarind rezultatul (vezi Anexa )

Teorema 1. FieP={A1¿, A2 , .. . , AM }¿o configuratie de grupare a unui set de agenti AN unde Am

este un cluster, ∀m∈1 , M :AN= ¿

m=1

MAm

. Construim urmatoarea matrice H∈ {0,1}N×N

H [ i , j ] =def

¿ {1 , ∃ m∈1 , M astfelincat {ai¿, a j}⊆ Am ¿¿¿¿¿

Atunci P este unic determinat de H.

Acest rezultat arată că relaţia Rk , m definită de includerea agentilor in acelaşi grup este unic

asignată configuratiei gruparii Pk , m (nici o altă configuraţie nu poate fi descrisă de Rk , m ).

Astfel, fiecare relaţie de interconectare Rk , m poate fi in mod unic asociată gradului de apariţie

asignat configuratiei αk , m . Impreună, pot defini asa numita α -distinct al relaţiei fuzzy Rk ,

cu ajutorul egalităţii (=) in loc de (¿ ) in definitia clasica a α - distincta. Deci, relaţia Rk , m este

o relatie α - distincta a multimii Rk definita pentru α k , m

In consecință, putem constui o relatie fuzzy (binară) elementară Rk , m a carei matrice din care

face parte este exprimată ca un produs intre caracteristicile matricei H k ,m , definită de (2.2), si

16

gradul de apariție α k , m , care este: α k , m H k , m . Acest set fuzzy AN×AN este de asemenea in

mod unic asociat cu Pk , m .

Dacă k∈1, K este păstrat fix, dar m variază in domeniul 1 ,M k , atunci este generata o familie

de relatii fuzzy elementare: {Rk ,m}m∈1 ,M k . In mod natural Rk este apoi definite ca o reuniune

fuzzy:

Rk =def

∪m=1

M k

Rk,m (2.3)

De obicei, relatia (2.3) este calculată folosind operatorul max (altfel niste alte definitii ale reuniunii fuzzy pot fi considerate bune). Acest lucru implică ca matricea din care face parte Rk este exprimata după cum urmează(prin folosirea operatorului max)

M k=def

max⋅ ¿m∈1, M k

{αk , m H k ,m }∈ℜN×N ¿

(2.4)Unde max⋅¿ ¿are effect asupra elementelor matricei si nu la nivelul global pe matrici.Ecuatiile

(2.3) si (2.4) sunt apropiate de forma rezolutiei al Rk , așa cum este definit în [16]. Oricum,

niste coeficieni α k , m(in general cu valori mici) pot sa dispară din gradele de legatura ale Rk .

De obicei, până când toate matricile α k , m H k , m sunt simetrice, formaM k (2.4) este de asemenea

simetrică, ceea ce înseamnă că Rk este o relație fuzzy simetrică. Este evidentă reflexivitatea

fuzzy (elementele nenule pe diagonal principală). Astfel, Rk reprezintă cel puțin o relație apropiată. Maniera în care grasele de apariție sunt asignate partitiilor afectează foarte mult calitatea relatiei fuzzy. Desi toti α -sharp-cuts pot fi relații echivalente, nu este necesar ca rezultatul relatiei fuzzy să fie unul similar (reflexivitatea fuzzy, simetria si tranzitivitatea). Dar este cel putin o relatie apropiată, așa cum este exprimat in contnuare:

M k≥¿ (M k ∘M k ) , (2.5)

Este mult mai dificil de asigurat.

Aici “¿⋅¿ ¿” acționează asupra elementelor matricii, și “∘” relevă alcătuirea relațiilor fuzzy. În cazul tranzitiei max-min, aceasta este exprimat in mod similar la multiplicarea clasică a matricilor, unde operatorul max este folosit in loc de adunare si min in loc de produs:

M k [ i , j ]≥(M k ∘M k )[ i , j ]=maxn∈1 , N

min {M k[ i , n ] , M k [n , j ]}, (2.6)

Unde i , j∈1, N și M [ i , j ] este elementul curent al matricii M .

17

Ecuațiile (2.5) sau (2.6) exprimă o procedură interesantă de a crea relatii similaritate începând cu unele apropiate, prin folosirea noțiunii de final tranzitiv. Un final tranzitiv a unei relații fuzzyR este, prin definiție, ralatie fuzzy minimă tranzitivă care include R . (Aici minimul este considerat este luat în considerare prin respectarea incluziunii pe seturi fuzzy.)In mod interesant, compunerea relatiilor fuzzy păstrează relexivitatea si simetria, dacă relațiile nu sunt neapărat identice, si păstrează la acelasoi nivel tranzitivitatea, dacă relațiile sunt identice.

Teorema 2. Fie Q si R relații binare fuzzy și M Q , respectiv M R matricile lor de legătură

N×N . Notăm cu C compunerea: C=Q∘R . AtunciM C=M Q∘M R (produsul fuzzy) si:

1. Dacă Q și R sunt relații reflexive, atunci C este de asemenea reflexivă.2. Dacă Q și R sunt relații simetrice, atunci C este de asemenea simetrică.3. Dacă Q=R și R este o relație tranzitivă, atunci C este tranzitivă.

Este foarte important sa se pastreze vecinătatea relației Rk prin compunerea cu ea înseși, deoarece următoarea procedură simplă ne permită să generăm o relație de similaritate. Primul pas constă în 2 operații: o multiplicare fuzzy a matricei si o reuniune fuzzy.

1.Se calculează relația fuzzy : Qk=Rk∪(Rk ∘Rk ) .2. Dacă Qk≠Rk , înlocuim Rk cu Qk și mergem la pasul 1Altfel daca Qk=Rk este ultima

tranzitie pentru Rk initial

Exprimata de operatorii max si min ca in (2.6) și (2.4)). Al doilea pas este un test simplu si eficient al tranzitivitatii fuzzy, pentru orice relație, evitând inegalitățile (2.5) sau (2.6). Similaritatea este de asemenea important in acest context, până ce se arată caracterul holonic al MAS. Deocamdată, a fost construită o hartă bijectivă (corespunzătoare teoremei 1) între P={Pk }k∈1 , K si R={Rk}k∈1 , K , numită T.

2.8 Masura fuzificării

Urmatorul pas are ca scop construirea masurii de fuzificare a relațiilor fuzzy pe AN×AN , care va fi folosită pentru selectarea relației fuzzy minimizată in interiorul setului R={Rk}k∈1 , K .O clasă importantă constă în masuri care evaluează fuzificarea unui set fuzzy prin luarea în considerație a setului si a complementului. De la această clasă, am selectat Masura lui Shannon, derivată din functia lui Shannon generalizată:

(2.7)

18

[ S : [ 0,1 ]M →ℜ+

[ ( x1 ,. . . , x M )↦ S ( x )=def

−∑m=1

M

[ xm log2 xm+(1−xm) log2(1− xm )] .[

(2.8)

Această funcție are un maxim unic (egal cu M, pentru xm=1/2 , ∀m∈1 , M ) și 2M minim de nul (in vârful hipercurbei [0,1]M). De exemplu, dacă M=2, este generată suprafața descrisă mai

jos. În general, S generează un hiper-plan in interiorul spațiului Euclidian ℜM

, dar toate miminele sunt zero.Dacă argumentul acestei funcții este o distributie a probabilității, aceasta se referă la entropia Shannon. Dacă argumentul este o functie de legarură ce defineste un set fuzzy, aceasta se

referă la entropia fuzzy (Shannon).Rezultă entropia fuzzy Sμ . Apoi, conform ecuației (2.8), Sμ este exprimată, pentru toti k∈1, K

Sμ(Rk )=−∑i=1

N

∑j=1

N

M k [ i , j ] log2 M k [ i , j ]−∑i=1

N

∑j=1

N

[1−M k [ i , j ] ] log2 [1−M k [ i , j ]] . (2.9)

Evident, această funcție are un singur maxim iar toate minimele sunt nule, cu respectarea

variabilelor M k [ i , j ], dimeniunea sa fiind M=N2

Două argumente principale, motivează această alegere. Primul, Sμ ne ajută sa realizăm o

conexiune directă între how fuzzy este un set si câtă incertitudine conține. Astfel, de cândSμ

calculează cantitatea de informație a unei entități informaționale, denumită un set fuzzy, setul de funcții de minimizare fuzzy va conține informația minima a incertitudinii. Al doilea,

ignoranța totală (sau incertitudinea) informației este dată de singurul maxim al Sμ , cu toate că punctele minime multiple (acum, varfurile hiper-cubului) apartin unei zone de cunoștere perfectă (ca fiind posibil cel putin o informație incertă). Între ignoranța totală(care in mod interesant este unică) și zona de cunostere perfectă (care este întotdeauna multiplă) există multe puncte intermediare asociate cu diferite grade de incertitudine ale cunoșterii asupra entității.

Mai mult, se poate determina forța de conducere catre cunoaștere?, prin calculul gradientului entropiei fuzzy a lui Shanon. Este interesant de remarcat că amplitudinea acestei forțe (norma acesteia) are expresia

‖∇ Sμ(Rk )‖=√∑i=1

N

∑j=1

N [ log2

1−M k [ i , j ]M k[ i , j ] ]

2

, (2.10)

Creste foarte rapid in apropierea oricarui punct de cunoastere perfectă.(vezi figura 6.b de mai sus).

19

2.9 Masura Incertitudinii

Cu toate că există un singur maxim al entropiei fuzzy al lui Shannon, descrisă de relaţia (2.10), căutăm unul din minimul său. Măsură necesară a incertitudinii, V, este obţinută de

compunerea Sμ in (9) cu T în (7), care este: V=Sμ∘T . De remarcat că V nu este o masură a fuzzificării, deoarece, domeniul său de definiţie este setul planurilor sursă (seturi incrucisate) si nu setul relaţiilor fuzzy intre agenţi (seturi fuzzy). Dar, până când T este o bijecţie, problema optimizării este echivalentă cu:

Pk 0=T−1(argmin

k∈1 , KSμ(Pk ))

, where k o∈1 , K . (2.11)

Noua problema (2.11) nu necesită un algoritm deoarece k este un număr finit al tuturor

minimelor, cu tot cu multiplu, sunt zero şi localizate în vârful hyper-curbei [ 0,1]N2

. Probleme pot aparea numai dacă k este foarte mare. În acest caz, pot fi folositi algoritmi genetici sau

algoritmi de regenerare pentru a găsi minimul. Potrivit interpretărilor anterioare Pk 0 este cea

mai mică valoare fuzzy, cea mai mica incertitudine a familiei de forme a planului- sursă şi cea

mai atrasă de zona de cunoştinţe. Corespondenţa relaţiei fuzzy optime Rk 0 poate fi utilă în

construirea celui mai putin incert plan al MAS.

2.10 Aparitia grupurilor de holoni

Odată ce a fost selectată o pereche (Pk 0 ,

Rk 0 ) pentru rezolvarea problemei (2.11) (pot fi posibile mai multe optiuni, până de este disponibil un minim multiplu), ar trebui identificat un plan sursă corespunzător. Sunt posibile 2 variante:

Afişarea tuturor configuraţiilor al Pk 0 (prin extragerea, eventual, a acestor configuraţii pentru

care gradul de apariţie tinde către zero în Rk 0 )

Pk 0=¿¿

Construirea altor planuri sursă prin utilizarea lui Rk 0 şi nu a lui

Pk 0 .

Există un motiv pentru a doua optiune. De obicei, informaţia iniţială disponibilă referitoare la MAS este atât de vagă încât este imposibil să se construiască vreun plan-sursă solid. Acesta este cazul, de exemplu, când putem seta gradul de aparteneta corespunzător grupurilor create numai de cuplurile de agenti. Dar este de dorit identificarea a cel putin unui plan sursă pentru rezolvarea problemei.

Ideea principala pentru construirea diferitelor planuri-sursă este să se evaluezeα -

disponibilitate al Rk 0 şi aranjarea lor în ordine descrescătoare a relaţiilor lor. Această ordine

reprezintă tot ce poate specifica începând cu informaţia iniţială referitoare la MAS. Cand

20

construim un model, până cand nu este luată în consideratie perioada de evoluţie în MAS, nu este incă disponibil criteriul de ordonare după timp. Pentru acest aspect al cercetării vezi [7]. Astfel, planurile nu sunt construibile cu acest model. Oricum, este posibil ca un plan să coincidă cu plan sursă generat în această manieră (în special când relația este similară cu alta)

Potrivit teoremei 1, fiecare matrice H k 0 , α în (2.12) generează o singură configurație a gruparii

aginților peste AN . Astfel,apar doua categorii ale planului sursă: echivalența sau planuri

sursă holonice (atunci când Rk 0 e o relație de similitudine) și planuri sursă compatibile

(atunci când Rk 0 reprezintă doar o relație apropiată).

Când relația fuzzy associată Rk 0 este una de similaritate, atunci este evidențiată o proprietate

interesantă a MAS: grupurile sunt associate în ordinea formarii de noi grupuri, precum grup

în interiorul altui grup, ca o structură holonică. Mai mult, similaritatea relației Qk 0 poate fi

construita începând cu relația apropiată Rk 0 , urmarind procedura descrisă la pasul 2. Astfel, poate fi relevată potențiala structură a MAS, chiar dacă acesta înseamnă dezvoltarea întro maniera non-holonică.

Cand Rk 0 este doar o relație de aproximare, toleranța(compatibilitatea) claselor ce poate fi

construită ca o colecție de grupuri suprapuse. De această dată,faptul că grupurile pot fi suprapuse (interconectate) – unul sau mai mulți agenți pot să apartină în același timp diferitor grupuri – relevă capacitatea unor agenți de a juca roluri multiple prin implicarea în câteva taskuri în același timp.

α -disponibilitate al Rk 0 reprezintă relatiile

Rk 0 , α pentru gradul de apartenenta α∈[ 0,1 ].

Matricea caracteristicilor elementelor lui Rk 0 , α este definită de:

H k 0 , α [ i , j ]=def

¿ {1 , daca M k0[ i , j ]≥α ¿ ¿¿¿

, ∀ i , j∈1 , N . (2.12)

Aceast capitol a evidențiat că minimizarea entropiei fuzzy este mecanismul care organizează structurile în entități holonice. O zonă de aplicații reprezintă reconfigurarea automată a unei structuri eșuate cu restabilirea proprietăților holonice. In contextul întreprinderii holonice – principal aplicabilitate o reprezintă găsirea partenerilor celui mai apropiat din punct de vedere al colaborarii.

2.11 Sistem de control holonic

21

În acest paragraf vom examina cerinţele specifice de control şi de a arăta că mediul este compatibil cu această abordare multi-nivel. În primul rând, Figura 2.4 arată problemele de control atât de natură statică cât şi dinamică ce apar la orice nivel al fabricaţiei.

Nivel Tip Static Dinamic

Control Local

ContinuuModel bazat

pe setareModel bazat pe control

Control al Procesului

Discret/Continuu GraficReplanificare

dinamica

Management al procesului

DiscretPlanificarea Producţiei

Planificare dinamica

Fig 2.4 Probleme de control statice şi dinamice pe diferite nivele de productie

Deşi algoritmii şi domeniul problemei sunt în mod evident diferite, în fiecare caz există o problemă de reglare a variabilei de control, prin intermediul feedback-ul pentru a alinia o variabilă de ieşire la o setare dorită. În contextul holonic, cerintele algoritmilor de control statici si dinamici reprezintă tinta poziţionării, astfel, algoritmii de control ar trebui sa fie furnizaţi cu un set de cereri (conectate la un task sau un sub-task) iar acestea trebuie mai întâi convertite (la nivel înalt) în cerinţe ce pot fi soluţionate înainte de rezolvarea problemei.

Fig. 2.5 Model de control ce suportă cerintele stabilirii obiectivului pentru HMS

Sistemul de stabilire a obiectivului din figura 2.5 are proprietatea internă de a converti obiectivele (tintele) sau necesităţile întrun set de parametrii permişi sau traiectorii ale caracteristicilor prin anumite funcţii de decizie, D. Acţiunea de control este apoi trimisă procesului P. Parametrii din figura 2.5 sunt:

22

P- proces (+model+controller)D- problema de decizieΦ- principiul deciziilorM- set de decizii alternativeU- set de evenimente alternativeY- set de ieşiri posibilem∈M ,u∈U , y∈YP : MxU → Y

Dezvoltarea problemelor de decizie potrivite (flexibile) reprezintă cheia pentru integrarea activităţii controlului în sistemele holonice ale caror obiective pot diferi în funcţie de mediul în care operează. Optimizarea distribuită bazată pe principiul deciziei este adaptată perfect sitemelor holonice, iar metodele de cautare ale obiectivului pot ajuta la integrarea optimizărilor complexe bazate pe algoritmi de control în cadrul operaţiilor de fabricaţie.Figura 2.6 arată faptul că un algoritm de tipul H∞ este privit în mod obisnuit ca un motor de căutare a scopului. Principiul deciziei,Φ, reprezintă minimizarea lui H∞ norma funcției de cost, care este

unde G este modelul procesului sau funcția care trebuie controlată, W ponderea corespunzătoare funcției de cost, M este asa numitul H∞ standard al intreprinderii ce combină ponderile, modelul de proces și interconexiunile, K este conrollerul care trebuie proiectat și FL(∙) este Transformata Liniară Fracționară ce combină aceste elemente pentru a forma funcția de cost. Problema de decizie, D, este cea a selectării ponderilor optime corespunzătoare ce caracterizează necesitățile globale și determină un set corespunzător de controale care satisfac acestă necesitate. De aceea, referindu-ne la figura 2.6 procesul P, înglobează procesul real, un model al lui insusi precum și controlul reacției selectată.

Fig 2.6 Algoritmul H∞ in modelul de căutare al scopului

Ca un exemplu, obiectivul global de control al unui Holon la un nivel local sau de proces ar putea obține un punct al obiectivului până la 1% la starea de echilibru (frecvențele ma jos de 0.01 rad/sec), cu constrângere suplimentara că modelul procesului incorporat în holon este garantat pentru o acuratețe de pana la 10% din adevarata caracteristica a procesului (la frecvențe ridicate, unde cele mai multe moduri dinamice sunt neglijate). Procesul de decizie

23

trebuie să producă un controller Km dintro clasa fezabila de controlere K care vor atinge acest obiectiv.

2.12 Cerinte pentru diagnosticare

Sistemele holonice necesită o capacitate de diagnosticare încorporată pentru a mentine caracteristica lor de autonomie. Doua aspecte ale acestei capacități sunt necesare holonului pentru a detecta și a diagnostica problemele interne sau daca este necesar, prin cooperarea cu holonii vecini.Detecția implică semnalizarea dar nu este necesara trasarea problemei în sistemul holonic. Metoda propusă pentru un mediu holonic este utilizarea unei stari a sanatății prezentă în fiecare holon pentru a indica operațiile normale sau potențialele probleme.

Starea de sănătate este rezultatul unei defectoscopii locale în care holonul, care poate fi privit ca o varietate de instrumente sau aproximează analitic redundant (bazat pe model) fiecare, care este în mod fundamental o comparație între caracteristica actuală si cea ideală dată de model. (Este în mod precis compararea operațiilor în modelele interne astfel se determină starea de sănatate). Toți holonii calculează o stare de sănătate și înregistrează acestă stare la un holon local de diagnosticare. Starea de sănătate este o valoarea tipică între 0 și 1 (corespunzătoare gradului de nepotrivire a modelului), unde 1 înseamnă fără defecte iar 0 însemnă complet indisponibil pentru utilizare. La detecția erorii, holonul de diagnosticare initializează o procedură de interogare numită stări de sănatate a tuturor holonilor pentru a forma o semnătură a defectului (Figura 2.7) și dacă este necesar, extinde această procedură de interogare la sub-nivelele holonilor. Acest lucru este aratat în figura 2.8.

Fig. 2.7 Interogarea folosind Conceptul Stării de Sănătate pentru a forma Semnătura de Sănătate

În practică, este de neconceput ca, pentru motive de costuri sau configurare, să presupunem că orice holon singular va avea un număr suficient de senzori pentru a-i permite acestuia să izoleze fiecare condiție de defect.Noțiunea de senzor include de asemenea senzorii virtuali, prin care un semnal poate fi reconstruit utilizând modele interne ale holonilor valori deduse sau calculate din alți senzori reali/virtuali. Mai mult, asociate de asemenea cu cu fiecare senzor este gradul de încredere (de la 0 la 1) indică fiabilitatea de a citi. În general, mai mulți holoni vor avea nevoie să coopereze la identificarea cauzei comportării anormale care este evidențiată în figura 2.8 prin semnul ? la semnătura de sănătate.

24

Fig. 2.8 Exemplu de semnatura a defectului pe 2 nivele

2.13 Analiza problemei de racire a unei instalaţii de producere a oţelului

Scopul acestui capitol este de a arăta maniera în care poate fi încorporat controlul și diagnoza. Figura 2.9 ilustrează o cale de rulare, unde zona de racire cu apă este împărțită în 5 tancuri de răcire, fiecare având control separt al debitului de apa. Scopul este setarea și controlul debitului de răcire, astfel este obținută temperatura finală dorită TC(sfarsit), în timp ce un scop adițional reprezintă minimizarea în timpul răcirii a diferenței de temperatură de la suprafață la centru. Ambele scopuri sunt importante pentru proprietățile metalurgice finale ale barei de oțel. Sistemul curent furnizează numai un control rudimentar care este sensibil la blocările clapetelor si la defectul recipientelor de apa este incapabil să mențină garantarea proprietăților metalurgice in aceste circumstanțe.

Pe scurt, problemele și scopurile propuse în acest studiu sunt

PROBLEMESistemul este incapabil să manipuleze noi produseRigiditatea setării răciriiMentenanța ridicată a tancurilor de apa

SCOPURIIntegrare metalurgică bazată pe modele de răcire Negociere demonstrată pentru setare (Cooperare)Dezvoltare de strategie auto-diagnoza (Autonomie)

Fiecare scop în sine nu constituie cerințele unei soluții holonice, dar combinația acestor probleme permite analiza întrun cadru holonic. De asemenea, scopul studiului nu este îmbunătățirea performanței sistemului în funcționare normală ci de a extinde abilitatea de a opera efectiv în condiții anormale sau de schimbare.

25

Fig. 2.9 Diagrama holonica de racire

2.13.1 Soluția holonică

Structura holonică propusa pentru problema de răcire, cuprinde trei nivele ale funcțiilor de procesare fizice

- Nivelul ROD MILL – unitate (unități) – o unitate pe calea de procesare – responsabila pentru setarea si obtinerea scopului în raport cu caracteristicile produsului final si a cerințelor întâlnite în producție

- Nivelul de răcire – responsabil cu convertirea obiectivelor metalurgice în subobiective de răcire și negocierea aproximativă optimală

- Nivelul valvei – responsabil de alimentarea cu apa asa cum este cerut(unitate rudimentară)Mentenanța- funcții de interfațare cu omul care interacționează asa cum este cerut de functiile de răcire şi ale clapetelor.

2.13.2 Configurarea / Soluţie de control

Fiecare bloc de răcire are functii de control si setare (in PLC) iar mentenanta şi functiile de reparatie (operatorul uman) reprezintă un holon.(ca in fig.2.9)Este demonstrat faptul ca utilizand un algoritm (contract de licitaţie) poate fi obtinuta o co-operare simpla si efectiva pentru determinarea fluxului corespunzator in fiecare bloc de racire. Luarea deciziei este completata in termenii sub-obiectivelor a tuturor obiectivelor la nivelul holonului local, cu licitarea sistemului permitand holonilor negocierea celei mai bune solutii in scopul realizarii unei solutii consistente a obiectivului total.

26

Un set complet de rezultate pentru aceasta problema de co-operare este inregistrata in alta parte. Acest proces poate fi scris intr-un cadru ierarhic ilustrat in figura de mai jos. Diagrama reprezinta un exemplu de joc co-operativ, unde , in cazul holonului de baza a problemei de racire, functia de decizie globala este de fapt preluată in fiecare din holonii participanti in scopul asigurarii unei functionari sigure in cazul in care se inregistreaza erori la un singur holon.

Fig. 2.10 Problema de control a răcirii ca un sistem de hierarhic de gasire a obiectivuluiTrasatura importanta a acestei probleme este faptul ca analiza complet generica si asociata precum si tehnicile de sinteza ar putea fi aplicate la interactiunea dintre unitatile implicate in problema de fabricatie discreta, precum alocarea resurselor la masinile de stantare. O cercetare aprofundata in aceast domeniu este ceruta pentru a dezvolta un cadru sistematic pentru operatia holonilor, si in mod particular rezultatul manipularii multiplelor straturi de sub-holoni ce nu au fost adresate.

2.13.3 Soluţie de diagnosticare

Metodologia pentru diagnosticarea manipularii holonice pentru problema de racire a fost dezvoltata ca un exercitiu conceptual. Oricum, acest exercitiu este suficient pentru a ilustra mecanismul metodologiei de diagnostic holonic. Exercitiu a identificat cele mai importante trei erori care ce au loc in zona de racire. Acestea sunt aderenta valvei care controleaza nivelul jetului care regleaza pozitia fluxului, valva de rezistenta de fuga in paralel care directioneaza fluxul de apa pe si intr-o alta directie de la bare ca un sprijin cerut si uzura suprafetei interne a fluxului de ajutaj care conduce la deteriorarea graduala a fluxului si calitatii racirii. Este notat faptul ca, in interesul calitatii, un operator este curent utilizat full time pentru mentinerea cutiilor de racire. .Pentru o ilustrare completa a modului in care lucreaza holonul de diagnostic, corectorul se refera la o lucrare viitoare pe acest subiect. Oricum, daca consiedram cazul simplu al controlului jetului de aderenta , Figura 2.11 arata evolutia mapei defectelor pentru acest defect particular. Aceasta demonstreaza ca exista cel putin trei alte mecanisme pentru defecte care sunt declansate de acelasi semnal de detectie al erorii. In mod evident la nivelul holonului de racire local acesta creeaza anumite ambiguitati. Poate fi aratat faptul ca problema detectiei cere doua niveluri de semnaturi de defect si cateva co-operari externe intre holonii de racire.

27

DEFECT INDICATOR LOCATIA HOLONULUI

EROARE ALTE DEFECTE CANDIDATE

Control al valvei blocate

Tendinta usoara peste 0,5 Hr.

Harta si istoricul starilor

Eroare temporara consistenta ; posibil în directie greşită

Uzura clapeteiScurgere prin furtun sau colierPresiunea apei redusa

Fig. 2.11 Harta defectelor al procesului de răcire

28

3. Strategii optimale de conducere a sistemelor dinamice hibride – aplicaţie la sistemele de roboţi cooperativi -

Capitolul vizează studiul sistemelor de roboţi cooperativi (care execută împreună acţiuni pentru îndeplinirea unui scop global), în condiţiile extremizării unui indice de performanţă. Sistemul abordat în cazul de faţă este format din 2 roboţi mobili care execută transportul unui obiect în 2D, cu evitarea obstacolelor şi minimizarea timpului (a consumului energetic). Această problemă de optimizare se formulează ca minimizarea cu restricţii a unei funcţionale.

Se propune sinteza unei arhitecturi pe 2 niveluri pentru comanda optimală a sistemului de roboţi. Studiul vizează:

– modelarea nivelului ierarhic inferior, respectiv a comunităţii de roboţi, ca sistem dinamic hibrid (a cărui evoluţie este caracterizată atât de variabile de stare cu evoluţie sincronă cu timpul, continue sau discrete, cât şi de evenimente, cu apariţie asincronă), considerând în primă fază un nivel minim de inteligenţă şi autonomie a roboţilor, respectiv numai capacitatea de a prelucra informaţiile provenite de la senzori

– sinteza unei structuri de control centralizat (supervizor, cu rolul de planificator al traiectoriei) care să acţioneze pe nivelul ierarhic superior şi să asigure comportamentul optimal în raport cu indicele de performanţă definit.

În viitor se doreşte realizarea unui program de simulare în buclă închisă a sistemului de roboţi şi a supervizorului, premergător implementării unei aplicaţii de timp real de comandă a sistemului cooperativ de roboţi. Acest lucru necesită algoritmi performanţi de tratare a informaţiei de măsură (în speţă, a reacţiei video prin prelucrare de imagini).

29

3.1 Abordarea domeniului

Concepuţi pentru a extinde capacitatea umană de a executa anumite operaţii, folosirea roboţilor a dat naştere unui domeniu ingineresc interdisciplinar. Ca ramură a automaticii, robotica a cunoscut o dezvoltare rapidă între 1970 şi 1990, catalizată de cererea din domeniul sistemelor de fabricaţie, unde maşinile cu comandă numerică erau treptat înlocuite cu aşa-numitele sisteme inteligente de fabricaţie.

Câteva din domeniile de utilizare predilectă a roboţilor sunt: economia serviciilor, anumite aplicaţii speciale, cu risc crescut, şi în locuri greu accesibile (mânuirea materialelor radioactive, în spaţiul cosmic, în minerit, explorări marine), aplicaţii de mare precizie (de exemplu, în chirurgie) etc. În Raportul Comitetului Tehnic IFAC Manufacturing and Instrumentation pe anul 2002 [1] se sesizează redefinirea roboticii ca o conexiune inteligentă între percepţie şi acţiune. În sprijinul acestei afirmaţii vine tendinţa de creştere a gradului de autonomie (conferită de sistemele multimodale de percepţie şi de adaptare la medii variabile), dar şi capacitatea de interacţiune socială, care le permite roboţilor să acţioneze sinergic, să coopereze pentru atingerea unui scop comun. Roboţii devin astfel agenţi inteligenţi, dotaţi cu sisteme cognitive.

În concluzie, metodologia folosită în robotică se situează la confluenţa dintre domeniile conducerii automate clasice, al inteligenţei artificiale (sisteme autonome, sisteme multi-agent) şi al programării aplicaţiilor de timp real. Noi provocări sunt conceperea de micro-roboţi şi metodele şi tehnologiile de teleoperare a roboţilor.

3.1.1 Clase de probleme în conducerea roboţilor

Conducerea roboţilor se confruntă cu 2 mari categorii de probleme: cele legate de comanda fizică, în timp real, a fiecărui robot, şi cele legate de asigurarea sincronizării între entităţile unui sistem de roboţi căruia i se cere să îndeplinească o anume sarcină.

Prima clasă de probleme se situează în cadrul teoretic al aşa-zisei automatici clasice, în care se pot folosi binecunoscute metode de proiectare din teoria sistemelor continue (metode clasice – structurale şi frecvenţiale – şi metode avansate – adaptive şi robuste), pretabile la utilizare în conjuncţie cu modelele roboţilor, în general neliniare. Se rezolvă astfel probleme de următoarele tipuri: urmărirea unei traiectorii, evitarea obstacolelor etc., asigurând stabilitatea globală a sistemului, eventual cu respectarea unui set de restricţii şi/sau unele performanţe suplimentare. Clasele de metode sunt diverse (controllere PID clasice, reţele neuronale, tehnici bazate pe modelul invers [2] etc.). Controlul navigaţiei printre obstacole necesită sisteme senzoriale precise şi rapide şi poate fi formulat ca o problemă de optimizare cu restricţii [3]. Rezolvarea acestei probleme şi implementarea soluţiei este de domeniul aplicaţiilor de timp real pentru comanda roboţilor mobili [4].

Cât priveşte cea de a doua clasă de probleme, abordările sunt mai recente şi se referă la studiul comportării globale a unui sistem format din mai mulţi indivizi, în particular cooperativi. Sistemul global apare în primă fază condus de evenimente (care au o apariţie asincronă), deci el poate fi reprezentat printr-un automat finit (sau prin reţeaua Petri echivalentă) şi tratat ca un sistem cu evenimente discrete. Rafinând modelarea până la nivelul fiecăruia dintre roboţi (care au modele continue), atunci sistemul total este un sistem dinamic hibrid, care este caracterizat atât de variabile de stare cu evoluţie sincronă cu timpul, continue sau discrete, cât şi de evenimente asincrone. În acest caz, problemele de conducere vizează în esenţă optimizări multi-criteriale şi se rezolvă prin sinteza unui aşa-numit supervizor (plasat

30

pe un nivel ierarhic superior în raport cu dinamica roboţilor individuali). În literatură sunt raportate diferite tehnici de supervizare aplicate sistemelor de roboţi [5], [6].

3.1.2 Cooperarea în sistemele de roboţi

Pentru ca o mulţime de roboţi să coopereze pentru atingerea unui obiectiv comun este necesar să li se implementeze acestora un grad mai mic sau mai mare de inteligenţă (ceea ce îi transformă în agenţi) şi o anume capacitate de comportament social. S-a dezvoltat astfel teoria sistemelor multi-agent, fundamentată pe concepte aparţinând informaticii teoretice, dar care necesită o abordare interdisciplinară [7]. Conform cu [8], roboţii sociali sunt agenţi care fac parte dintr-un grup heterogen de roboţi şi fiinţe umane; ei sunt capabili să se recunoască între ei şi să se angajeze în interacţiuni sociale, percep şi interpretează lumea în termenii experienţei lor proprii, comunică între ei şi învaţă unii de la alţii.

Cooperarea implică într-adevăr un anume grad de socializare, dar, printr-un lejer abuz de limbaj putem numi cooperare şi situaţia când roboţii sunt comandaţi să execute acţiuni printr-un algoritm centralizat, fără ca aceştia să interacţioneze direct. Când este conceput să funcţioneze în timp real (on line), acest algoritm joacă rolul de supervizor şi rulează pe un calculator, eventual aflat la distanţă. În alte cazuri, algoritmul furnizează o soluţie off-line, ca rezolvarea unei probleme de optimizare. De exemplu, coordonarea fără coliziuni a traiectoriilor unui sistem de roboţi mobili poate fi tratată şi rezolvată în termeni de optimizări continue [9] sau discrete [10]. Noţiunea de cooperare s-a extins şi asupra coordonării acţiunilor părţilor unei aceleiaşi entităţi-robot (de exemplu, articulaţiile aceluiaşi braţ manipulator [11]), sau ale mai multor roboţi identici în scopul imitării acţiunilor umane (de exemplu, manipularea unui obiect cu 2 mâini [12]).

În modelarea şi controlul sistemelor de roboţi se poate face uz fie de abordarea orientată agent, care este predilect de natură informatică, fie de abordarea inspirată din teoria sistemelor dinamice, aparţinând automaticii. Cele două tendinţe nu sunt net delimitate, astfel încât formularea şi rezolvarea unei anumite probleme se poate uneori situa la confluenţa lor.

Abordarea orientată agent

Se ştie că agenţii acţionează conform modelului pe care îl au despre lume. Complexitatea modelului este legată de gradul de autonomie (în cazul roboţilor mobili acesta este perceput intuitiv ca libertate de mişcare, decizie şi acţiune) mai mare sau mai mic cu care este dotat un anume agent. Astfel, roboţii destinaţi acţiunii în medii complexe au nevoie de un grad mai mare de abstractizare în modelarea lumii [13].

Roboţii cooperativi pot fi total neautonomi, caz în care ei sunt total dependenţi de deciziile supervizorului. Dacă roboţilor li se atribuie un anume grad de autonomie, aplicaţiile de cooperare sunt tratate în teoria sistemelor multi-agent, al cărei instrument de analiză îl constituie reţelele de contractare (contract networks), bazate pe mecanismul negocierii. În aceste reţele, un agent poate juca 2 roluri: manager şi ofertant (bidder). Protocolul de funcţionare constă în următorii paşi principali. Managerul lansează cererea de ofertă (descrierea acţiunii de executat) către toţi ofertanţii potenţiali. Aceştia îşi întocmesc ofertele şi le trimit managerului, care îl alege pe cel mai bun executant posibil. Acesta din urmă poate fie să treacă la execuţia acţiunii, fie să o refuze; în ultimul caz managerul reevaluează ofertele rămase.

În [14] se propune o fuziune între reţelele de contractare şi reţelele Petri şi construirea de reţele Petri colaborative pentru modelarea şi controlul sistemelor de fabricaţie bazate pe holoni (cu analogii imediate cu sistemele de roboţi cooperativi). Protocolul de alocare dinamică a taskurilor prezentat mai sus poate fi folosit în timp real la cooperarea între

31

Obiect condus

ke

)(tx

ku

)(txm

Supervizor (sistemcu evenimente discrete)

GeneratorElement

de execuţie

Controller secvenţial

Sistem

dinamic hibrid

Interfaţă de proces

comportamentale restricţii

booleeneiabilevar

evenimente evenimente

variabilecontinue

încheieturile unui aceluiaşi manipulator [11]. Acest protocol nu este unicul posibil pentru modelarea interacţiunilor dintre agenţi. În [15] se propun 3 astfel de modele, în care gradul de interacţiune directă este diferit: modele comportamentale (behaviour-based – fiecare agent acţionează conform unor primitive simple de mişcare), subordonare faţă de leader (leader-follower) şi, în fine, interacţiunea indirectă, printr-un algoritm de control centralizat (virtual structure).

Supervizarea sistemelor de roboţi

Tehnica supervizării, ca domeniu al automaticii, are o istorie relativ recentă. Apariţia ei a fost necesară ca extindere a cadrului automaticii clasice pentru sistemele distribuite, organizate ierarhizat, în care întârzierile de comunicare pot perturba de manieră radicală proprietăţile structurale globale (în speţă, stabilitatea [16], [17], [18]). Natura semnalelor s-a îmbogăţit şi ea prin apariţia evenimentelor asincrone, în timp ce nivelele ierarhice inferioare continuau să evolueze sincron cu timpul. Astfel, sistemul global are o dinamică hibridă (un exemplu îl constituie sistemele cu structură variabilă (comutate), liniare pe porţiuni [19]).

Nu există încă un cadru unitar al teoriei sistemelor dinamice hibride, metodele folosite fiind preluate atât din teoria sistemelor conduse de timp, continuu sau discret, cât şi din teoria sistemelor cu evenimente discrete şi a optimizărilor discrete. Din prima clasă, metoda funcţiei Liapunov [20], [21] şi cea a inegalităţilor matriciale liniare LMI [22] în analiza stabilităţii sunt exemple des întâlnite. Din cea de a doua clasă, aplicaţiile cele mai uzuale se referă la controlul optimal, cu mixtarea metodelor exacte – programarea întreagă mixtă, branch-and-bound etc. – cu cele sub-optimale – de exemplu, meta-euristicile de tipul algoritmilor genetici [23], [24] etc.

Supervizarea utilizează reacţia bazată pe evenimente (event feedback). Evenimentelor li se asociază comenzi continue care acţionează asupra obiectului condus. Schema de principiu (figura I.1) presupune existenţa unei interfeţe între supervizor (care este un sistem cu evenimente discrete) şi obiectul condus, formată din generator (de evenimente discrete, ek, pe baza reacţiei de stare continuă, x(t)) şi element de execuţie (care converteşte simbolurile de control, uk, în acţiuni continue, xm(t)) [25], [6].

Fig. 3.1. Schema hibridă a lui Stiver [6]

Fig. 3.2. O arhitectură de supervizare optimală a unui sistem dinamic hibrid [29]

Reacţia bazată pe evenimente este utilizată în [26] pentru supervizarea de tip time-sharing a N controllere asociate cu câte un obiect condus. La un moment dat este în funcţiune un singur astfel de controller. Structura propusă este analizată din punctul de vedere al stabilităţii. O abordare asemănătoare se găseşte în [5], unde se tratează supervizarea unui set de controllere heterogene (proiectate în scopuri diferite) ale unui robot mobil jucător de fotbal, cu minimizarea timpului, a consumului de energie sau a costului şi precizie maximă. Supervizorul trebuie să ia decizia optimală în timp real în funcţie de dinamica mediului de

32

operare al robotului; la un moment dat, el alege un singur controller capabil să îndeplinească cerinţele. În mod speculativ, supervizorul s-ar putea asemăna cu managerul din teoria sistemelor multi-agent, cu deosebirea că relaţia cu agenţii este mai rigidă (în sensul că acestora nu li se permite să refuze îndeplinirea unei acţiuni).

Tehnicile de supervizare se pretează foarte bine la sinteza controlului optimal al sistemelor dinamice hibride. Una dintre metode este analiza grafului de accesibilitate asociat sistemului [27]. Printr-o metodă asemănătoare, în [28] se calculează ordonanţarea optimală (cu minimizarea timpului) pentru o aplicaţie de procesare multi-produs modelată ca sistem dinamic cu logică mixtă (MLD).

În [29] se prezintă modelarea unui reactor chimic ca sistem dinamic hibrid şi se studiază comparativ 2 metode de sinteză optimală a unui supervizor bazat pe evenimente discrete: prin minimizarea cu restricţii a unei funcţionale, respectiv prin extinderea principiului maximului al lui Pontriaghin la sistemele dinamice hibride controlate prin evenimente discrete. Bucla închisă are structura din figura I.2. Sistemul este modelat ca automat hibrid: traiectoria lui de stare este formată din tranziţii între stările discrete, înăuntrul cărora evoluţia este continuă (descrisă de un sistem de ecuaţii diferenţiale sau în diferenţe finite). Interfaţa de proces este de această dată unidirecţională: variabilele cu evoluţie continuă sunt „convertite” în evenimente discrete.

Organizarea lucrării

Se propune sinteza unei arhitecturi pe 2 niveluri pentru comanda optimală a unui sistem de 2 roboţi mobili care execută transportul unui obiect dreptunghiular în 2D, cu evitarea obstacolelor în timp minim (cu consum energetic minim).

Paragraful al 3.3 este dedicat modelării nivelului ierarhic inferior, respectiv a comunităţii de roboţi, ca sistem dinamic hibrid. Comportamentul unui astfel de sistem este caracterizat atât de variabile de stare cu evoluţie sincronă cu timpul, continue sau discrete, cât şi de evenimente, cu apariţie asincronă. Roboţii studiaţi au un nivel minim de inteligenţă şi autonomie, respectiv numai capacitatea de a prelucra informaţiile provenite de la senzori. Această problemă de optimizare se formulează ca minimizarea cu restricţii a unei funcţionale.

Paragraful 3.4 se prezintă sinteza unei structuri de control centralizat (supervizor) care să acţioneze pe nivelul ierarhic superior şi să asigure comportamentul optimal în raport cu indicele de performanţă definit. În esenţă, este vorba despre sinteza unui planificator de traiectorie optimală. Închiderea buclei presupune tratarea suficient de performantă (atât rapidă, cât şi precisă) a informaţiei de măsură, adică a reacţiei video. În §III.3 este detaliat un algoritm de prelucrare de imagini.

3.2 Modelarea unui sistem de roboţi cooperativi ca sistem dinamic hibrid

3.2.1 Descrierea sistemului abordat. Modele cinematice

Conceptul de cooperare între mai mulţi roboţi a fost propus ca o inspirare din acţiunile umane, pentru a îmbunătăţi flexibilitatea sarcinilor şi toleranţa la defectări [30], acolo unde se preconizează ca roboţii mobili să preia diverse sarcini (mai ales în medii ostile). Aici interesează roboţii care realizează sarcini de transport. Mai multe studii au fost realizate asupra transportului şi manipulării cooperative de către sisteme de roboţi, fie cu roboţi mobili

33

start

ţintă

obstacol 2

obstacol 1

obstacol 3

robot 1

robot 2

autonomi comandaţi descentralizat [31], [32], [33], care prelucrează informaţia provenită de la senzori, fie cu vehicule pe roţi [34], cu manipulatoare [35] etc.

Dificultatea problemei de planificare a mişcării rezultă din dimensiunile mari ale spaţiului de căutare a configuraţiei optime (engl. C-space). Au fost folosite diverse metode din domeniul cercetărilor operaţionale în scopul rezolvării acestui aspect [36], [37], câteodată combinate cu metode multi-euristice [38]. Dimensiunile lui C-space cresc şi mai mult dacă se consideră constrângerile asociate mişcării unui obiect (ceea ce înseamnă calculul explicit al forţelor de contact şi al celor de frecare). Problema planificării mişcării cu evitarea coliziunii pentru transportul unui obiect de dimensiuni mari în 2D de către o echipă de roboţi mobili a fost discutată în [39]. În [40] este propusă o metodă de reducere a gradului de libertate (DOF) a lui C-space pentru planificarea mişcării în medii 3D.

Sistemul studiat este format din 2 roboţi mobili de tip Micromouse (fotografia unui astfel de robot este dată în figura 3.3) care cooperează pentru transportul unui obiect dreptunghiular în 2D, cu evitarea obstacolelor şi minimizarea timpului (a consumului energetic).

Fig. 3.3. Imagine a robotului mobil de tip Micromouse

Fig. 3.4 Exemplu de hartă

Din puncte de vedere funcţional, un robot mobil Micromouse dispune de:- 2 servomotoare de curent continuu comandate în impulsuri (1-2 ms),- 2 senzori de poziţie (potenţiometru),- senzor cu infraroşu de urmărire a drumului,- comandă realizată cu micro-controller de tip PIC 16C56XT, dotat cu software de bază

Parallax PBasic 1.4 şi memorie EEPROM 93LC56,- sistem de control radio emisie/recepţie pe 868 MHz, 2.4 Kbaud, 100 m,- software STAMP pentru programarea robotului şi depanarea programelor.

Configuraţia obstacolelor („harta”) este cunoscută şi presupusă a nu se modifica în timp. Pentru studiul mişcării în plan este suficientă considerarea doar a proiecţiilor celor 3 obiecte (proiecţiile roboţilor în planul suprafeţei de mişcare pot fi realist asimilate cu dreptunghiuri – în figura 3.4 s-a desenat drept ţintă poziţia centrului de masă al obiectului). Roboţii execută sarcina de transport prin împingerea obiectului.

În continuare se prezintă demersul general de modelare al robotului mobil descris ca sistem dinamic, presupunându-se ca tip general de comandă impunerea vitezelor fiecăreia dintre roţi.

Se consideră că robotul se poate afla:– în mişcare de translaţie (când vitezele celor 2 roţi, vA si vB sunt egale)– sau în mişcare circulară (când vAvB).

34

Mişcarea rezultantă se raportează la un sistem de axe rectangular, în care coordonatele (absolute) ale robotului sunt (x,y). Unghiul de curs, , caracterizează schimbarea direcţiei de mişcare la trecerea de la translaţie la mişcarea circulară. Mişcarea circulară se raportează la un referenţial legat de robot şi este caracterizată de coordonata relativă R (raza vectoare, numită şi rază de giraţie, măsurată de la centrul traiectoriei circulare a robotului) (figura 3.5).

Fig. 3.5 Elementele mişcării de translaţie (stânga) şi ale mişcării de rotaţie (dreapta)ale unui robot mobil

Notându-se cu d distanţa dintre roţi, se obţine . Se notează cu v viteza de translaţie şi cu viteza unghiulară a mişcării circulare. Au loc relaţiile:

şi rezultă succesiv:

; ; ;Vitezele roţilor, vA şi vB, se consideră cunoscute; ele constituie mărimi de intrare (de

comandă) în sistem. Mişcarea robotului este complet caracterizată de x, y şi , care sunt mărimi de stare. Modelul de stare este neliniar:

(II.1)Modelul (II.1) este un model cinematic, deoarece s-a presupus în mod simplificator un

sistem de acţionare a roţilor ideal (fără dinamică) şi s-au neglijat interacţiunile disipative (în speţă, forţele de frecare). În realitate, urmărirea traiectoriei de către robot este afectată de erori, chiar în condiţiile unei modelări mai precise, din cauza eventualelor nesimetrii constructive, neuniformităţii suprafeţei de mişcare etc. De aceea, pentru determinarea poziţiei robotului este nevoie de o informaţie complementară: reacţia video.

Pentru scopuri de conducere în timp real este necesară discretizarea modelulului (II.1). Notându-se cu Te perioada de eşantionare, se obţin: modelul discretizat strict cauzal:

35

numele robotului

înainte pe loc mişcare circulară cu rază de giraţie nenulă

tipul de mişcare

distanţă unghi raportul vitezelor celor 2 roţi

(II.2) modelul discretizat la limită cauzal:

(II.3)

Un sistem de roboţi Micromouse poate fi comandat de către un algoritm rulând pe un PC prin intermediul a 3 octeţi transmişi serial prin radio. Scopul comenzii constă esenţialmente în urmărirea unei anume traiectorii. Semnificaţia celor 3 octeţi este dată în figura 3.6.

Fig. 3.6 Semnificaţia celor 3 octeţi de comandă a unui robot Micromouse

Se observă posibilitatea realizării a 3 tipuri de mişcare, codificate în octetul al doilea, în funcţie de care diferă semnificaţia conţinutului octetului al treilea. De fapt, tipul de mişcare cel mai general este al treilea (când vitezele celor două roţi nu sunt neapărat nenule), primele două fiind particularizări ale acestuia:

- dacă vitezele sunt egale (şi nenule), se obţine mişcarea de translaţie („înainte”);- dacă numai una dintre viteze este nulă, se obţine mişcarea circulară („pe loc”);Tipul de mişcare poate fi, deci, considerat ca fiind o mărime cu evoluţie discretă (ea

reprezintă o mărime de intrare, de comandă, pentru robot). Modificarea, pe parcursul urmăririi traiectoriei, a tipului de mişcare, determină, deci, tranziţia sistemului dintr-o stare discretă în alta. În interiorul fiecăreia din stările discrete evoluţia este continuă, caracterizată de câte un model de stare continuu neliniar (particularizare a modelului II.1). Conţinutul octetului al treilea reprezintă valoarea constantă a unei mărimi de intrare continue.

După cum se arată în secţiunea următoare, una din restricţiile impuse sistemului de 2 roboţi cooperativi este să păstreze mereu contactul cu obiectul pe care îl transportă. Deci ei se vor mişca „pe lângă” obiect când va fi necesar să-şi schimbe poziţia faţă de acesta. Pentru aceasta este suficient să se considere în modelare numai primele două tipuri de mişcare (înainte şi pe loc). Rezultă că dinamica hibridă a unui robot este formată dintr-un şir de tranziţii între 2 stări discrete, caracterizate de câte un model neliniar de tip (II.1).

Urmând demersul de formalizare prezentat în [23], se notează:

36

0 0t 1t 2t tn ft t

(0)x

( )ftx

1( )fx

2 ( )fx

vectorul de stare continuă al unui robot (unde X şi Y sunt dimensiunile suprafeţei de mişcare);

vectorul comenzilor continue pe porţiuni (unde este viteza maximă cu care poate fi comandat un robot);

vectorul comenzilor discrete (care codifică tipul de mişcare).

Notând cu 1 şi 2 stările discrete, cu numărul de tranziţii între ele şi cu momentul de timp la care se produce a k-a tranziţie, robotul mobil este un sistem dinamic hibrid descris de:

, , , , (II.4)

în condiţiile iniţiale (de start) şi finale (ţintă) (figura 3.7).

Fig. 3.7 Dinamică de stare hibridă: tranziţii între stări discretecaracterizate de modele de stare continue

Actualmente, roboţii sunt programaţi să se mişte cu viteza maximă. Reprogramarea se poate face numai cu oprirea experimentului curent, prin cablu, prin re-inscripţionarea memoriei. Se pot imagina şi alte moduri de comandă, a căror complexitate este limitată de capacitatea memoriei robotului.

3.2.2 Formularea problemei de optimizare

Cum mediul de operare al roboţilor este cunoscut (sau identificabil), rezultă că se cunosc traiectoriile spaţiale posibile.

Considerând fiecare din cei 2 roboţi ca fiind descris prin câte un model de tip (II.4):

, (II.5)

în condiţiile iniţiale (de start) şi finale (ţintă) (indicii superiori se referă la numărul robotului), problema transportului de către cei 2 roboţi a obiectului în timpul minim se poate formula ca o problemă de comandă optimală cu variabile mixte (mixed-integer optimal control problem – MIOCP [23]):

37

Să se găsească:

– vectorii de comandă, ,

– numerele tranziţiilor, , ,

– şi momentele de timp la care au loc tranziţiile, , şi ,astfel încât să se minimizeze indicele:

, (II.6)

unde .Dacă se doreşte în plus evitarea obstacolelor, atunci fezabilitatea unei soluţii a problemei

mai sus formulate se declară în urma verificării restricţiilor topologice, care privesc vectorul

de stare, .

Sistemul poate fi echivalent descris ca un automat hibrid [41], [29]:

(II.7)

unde:– S este spaţiul stărilor continue (presupus observabil) şi Q al stărilor (fazelor) discrete (SQ desemnează starea hibridă),

– este o mulţime de m câmpuri vectoriale asociate cu stările discrete,

– este o mulţime de restricţii pentru fiecare fază (inegalităţi liniare),

– este mulţimea de evenimente care definesc tranziţiile discrete între faze (din j în k),

– este o mulţime de funcţii asociate cu evenimentele , care definesc valorile stărilor continue când apare un eveniment,– Q0 şi Qf sunt stările discrete iniţiale, respectiv finale.

Scopul este, deci, de a sintetiza comanda care conduce sistemul în cel mai scurt timp dintr-o stare hibridă iniţială într-o stare hibridă finală. Traiectoria de stare, x(t), trebuie să respecte restricţiile asupra variabilelor continue şi secvenţa discretă de comandă aleasă. În [29] se propune o formulare echivalentă cu cea dată mai sus, ca problemă de optimizare cu restricţii:

Se caută un vector de comandă uU (U este o mulţime compactă) astfel încât:

,cu respectarea unui set de restricţii dependente de x(t), unde:

, (II.8)în care ns este numărul de stări discrete prin care este condus sistemul, înafară de cea

iniţială şi de cea finală, iar este timpul cât sistemul rămâne în starea i.

Tot în [29] se propune o rezolvare alternativă a problemei, folosind extinderea principiului maximului al lui Pontriaghin (PMP) la sisteme dinamice hibride controlate prin evenimente discrete, care constă în traducerea unei probleme de comandă optimală într-un sistem de ecuaţii algebro-diferenţiale şi relevarea condiţiilor necesare de existenţă şi unicitate a

38

comenzii optimale. PMP poate fi aplicat oricărui sistem dotat cu o comandă continuă pe porţiuni [42], deci se poate adapta la părţile continue ale sistemului (adică între momentele de comutare, când sistemul evoluează continuu).

3.3 Structura de conducere optimală a sistemului de roboţi cooperativi

3.3.1 Soluţia propusă

Rezolvarea problemei de optimizare formulate în capitolul al II-lea recurge la sinteza unui aşa numit planificator al traiectoriilor roboţilor, astfel încât aceştia să asigure transportul obiectului la destinaţie cât mai repede posibil şi să evite obstacolele (a căror configuraţie este cunoscută apriori şi considerată fixă). De asemenea, planificatorul trebuie să decidă ce mişcări vor efectua roboţii în acest scop. Deoarece aceste aspecte nu pot fi tratate laolaltă datorită dimensiunii mari a spaţiului soluţiilor şi, deci, a creşterii inadmisibile a timpului de calcul, problema a fost separată în două, urmând demersul propus în [40]:

1) obţinerea drumului optimal, considerându-se numai condiţiile geometrice şi topologice (formele obiectelor implicate),

şi 2) determinarea acţiunilor efective de comandă, considerându-se statica obiectelor (forţele de contact).

Se realizează astfel o structură ierarhică pe 2 niveluri: planificatorul corespunzător fazei 1) – de pe nivelul ierarhic superior – se numeşte global („în linii mari”), iar cel corespunzător fazei 2) – de pe nivelul inferior – se numeşte local („fin”).

Aceste planificatoare interacţionează în următorul mod: cel global decide momentul, locul şi modalitatea în care se realizează manipularea, pe baza rezultatului furnizat de către planificatorul local. Primul planificator furnizează drumul obiectului şi al roboţilor, care este optimal din punct de vedere al costului (timpului) de manipulare. Deoarece pot apărea erori de mişcare ale roboţilor, este foarte probabil ca roboţii să nu poată urmări precis traiectoria furnizată de către planificatorul global. Ca urmare, planificatorul local furnizează o metodă de manipulare şi informaţii despre cum se realizează aceasta.

Soluţia propusă pentru planificarea drumului trebuie să fie eficientă din punct de vedere al efortului de calcul şi în acelaşi timp fezabilă. Mişcările roboţilor trebuie să fie în concordanţă cu mediul real în care se află (evitarea coliziunilor). În planificarea mişcării se adoptă următoarele ipoteze:

– referitoare la mediu („harta”):1) mediul este 2D (bidimensional) cu obstacole reprezentate ca poligoane;2) forma, poziţia şi orientarea fiecărui obstacol sunt cunoscute şi presupuse fixe;– referitoare la obiect:3) obiectul este presupus dreptunghiular;4) coeficientul de frecare între obiect şi suprafaţa pe care se realizează mişcarea este

cunoscut;– referitoare la roboţii mobili:5) roboţii sunt consideraţi ca fiind dreptunghiulari şi se pot deplasa în orice direcţie;6) roboţii păstrează tot timpul contactul cu obiectul pe care îl transportă folosind o acţiune

de împingere;– referitoare la manipulare:7) toate mişcările sunt cvasi-statice;8) toate interacţiunile de tip frecare ale obiectului sunt descrise prin intermediul legii lui

39

Coulomb.

În figura 3.8 este prezentată structura sistemului de comandă optimală a sistemului cooperativ de roboţi, sugerându-se modul de interacţiune a celor două planificatoare.

Prin analogie cu elementele unei scheme clasice de reglare, figura 3.8 arată că planificatorul global are rolul de a furniza off-line traiectoriile de referinţă ale roboţilor – acestea reprezintă soluţia problemei de optimizare cu restricţii formulate în paragraful 3.2 –

sub formă de şiruri de poziţii succesive ale centrelor de masă, pentru primul

robot şi pentru cel de-al doilea. În acest scop se utilizează algoritmul A* de căutare a drumului de cost minim într-un graf .

La un pas oarecare i de funcţionare on-line a planificatorului local, se verifică fezabilitatea

comenzii, care se aplică efectiv roboţilor. Apoi referinţa se compară cu

poziţiile reale ale roboţilor de după aplicarea comenzii, , obţinute prin tratarea reacţiei video. Dacă eroarea este sub o limită maximă admisibilă, notată

cu , atunci se continuă cu pasul următor, i+1. Dacă eroarea depăşeşte limita maximă impusă, atunci se reia algoritmul A* din planificatorul global, considerând drept configuraţie de start configuraţia reală curentă.

40

DATE DE INTRARE:harta: poziţia obstacolelor, poziţia de start, poziţia ţintă,...

obiectul: masa, poziţia centrului de masă,...roboţii: dimensiunile, viteza maximă,...

1 1 1 1 1 11 1 2 22 2 2 2 2 21 1 2 2

, , , ,... ,

, , , ,... ,

i i

i i

x y x y x y

x y x y x y

MEDIUL DE OPERARE AL ROBOŢILOR

poz max referinţa la pasul i de comandă a roboţilor

1 1

1 1

1 1

2 2

,

,i i

i i

real real

real real

x y

x y

poz

Fig. 3.8 Sistemul de roboţi cooperativi comandat printr-o structură cu două niveluri ierarhice

3.3.2 Planificatorul global: calculul off-line al traiectoriei optimale în 2D

În această secţiune se prezintă sinteza planificatorului global, folosind algoritmul A* de căutare a drumului de cost minim într-un graf.

3.3.2.1 Descrierea algoritmului A*

Rolul planificatorului global este să planifice în mod continuu poziţia roboţilor şi poziţia şi orientarea obiectului manipulat dintr-o configuraţie dată, de pornire, într-o configuraţie finală dorită, în funcţie de geometria obstacolelor şi de centrul de masă al obiectului. Rezultatul planificatorului global este soluţia problemei de optimizare cu restricţii formulate în capitolul al II-lea: minimizarea costului de manipulare, adică a timpului necesar transportului, astfel încât să se evite obstacolele. Aceasta este o problemă de căutare pe graf a drumului de cost minim, care poate fi rezolvată optimal, spre exemplu folosind algoritmul lui Dijkstra [43]. Dar

41

jn

in ih n

ih n ,i jc n n

Fig. 3.9 Condiţia de consistenţă este similară inegalităţii triunghiului

atunci când timpul de calcul este restrictiv, se preferă să se găsească mai rapid o soluţie chiar dacă aceasta nu este cea optimală. În acest caz sunt folosite metodele euristice.

O metodă clasică şi în acelaşi timp eficientă de căutare euristică este furnizată de către algoritmul de căutare A* [44]. În fiecare nod n al grafului de căutare căutarea este ghidată de către funcţia de evaluare a costului notată cu f, care are două componente:

, (III.1)unde:

– g(n) conţine costul minimal al drumului începând din poziţia (nodul) de start până la nodul n,

– h(n) este partea euristică a lui f, reprezentând o estimare a costului de la nodul n până la (nodul) scop,

– iar este parametrul euristicii.O valoare mare a lui corespunde unei căutări puternic orientate către scop; astfel, o

soluţie poate fi găsită rapid, chiar dacă aceasta nu este cea optimală. În caz contrar, o valoare mică a acestui parametru dă mai multă importanţă optimalităţii (=0 reduce algoritmul A* la algoritmul lui Dijkstra).

În ceea ce urmează, sunt listate câteva rezultate importante ale căutării euristice.Se spune că orice algoritm care garantează găsirea unui drum optimal către scop este

admisibil. Un rezultat binecunoscut specifică faptul că există condiţii referitoare la grafuri şi la funcţia h care garantează admisibilitatea algoritmului A* [43]:

– fiecare nod în graf are un număr finit de succesori (dacă există);– toate arcele au costuri pozitive;

– pentru toate nodurile din graful de căutare, , unde este valoarea reală a celui mai bun drum către scop.

Ultima condiţie semnifică faptul că funcţia h nu supraestimează niciodată valoarea actuală H; din această cauză, h se numeşte estimator optimist. Ar fi ideal ca h să ia valoarea celei mai bune margini inferioare a lui H. Un alt rezultat util referitor la h îl reprezintă condiţia de consistenţă. Aceasta poate fi definită în acelaşi timp de manieră locală [43] sau global, într-o manieră echivalentă [44]. Definiţia locală este mai intuitivă: considerându-se două noduri în

graful de căutare astfel încât este unul din succesorii lui , se spune că h este consistentă (sau monotonă) dacă este îndeplinită următoarea condiţie:

. (III.2)

Condiţia (III.2) este reprezentată sugestiv în figura III.2 şi specifică faptul că de-a lungul fiecărui drum din graful de căutare estimarea diferenţei costului optimal până la scop nu poate scădea mai mult decât costul arcului de-a lungul

drumului.Alegerea funcţiei h este, deci, foarte importantă pentru eficacitatea căutării. Funcţia h

aleasă pentru problema prezentată este admisibilă, dar nu este consistentă, aşa cum se va prezenta în continuare.

Paşii algoritmului A* sunt listaţi mai jos.

1. Se construieşte un graf, G, care conţine un singur nod (de start), , şi se pune acest nod într-o listă numită OPEN.

2. Se creează o listă numită CLOSED, care este iniţial goală.

42

3. Dacă lista OPEN este goală, atunci se termină algoritmul cu eşec.4. Se selectează primul nod din OPEN, fie acesta n, se şterge din OPEN şi se pune în

CLOSED.5. Dacă n este nodul ţintă, atunci se termină algoritmul cu succes: soluţia este obţinută

prin trasarea drumului indicat de pointerii de la la în G (aceşti pointeri definesc un arbore de căutare, aşa cum se stabileşte la pasul 7).

6. Se expandează nodul n, generând mulţimea S al succesorilor care nu sunt deja predecesori ai lui n în G.

7. Se stabileşte un pointer spre n de la fiecare din membrii lui S care nu sunt deja în OPEN sau în CLOSED. Fie M mulţimea tuturor acestor noduri. Se pune mulţimea M în OPEN.

8. Pentru fiecare membru, m, al lui S–M, se redirectează pointerul acestuia spre n dacă cel mai bun drum de până atunci este prin n.

9. Pentru fiecare membru al lui S aflat deja în CLOSED se redirectează pointerii fiecăruia din descendenţii lui în G, astfel încât aceştia pointează înapoi de-a lungul celor mai bune drumuri găsite până în momentul actual către aceşti descendenţi.

10. Se reordonează lista OPEN în ordinea crescătoare a valorilor lui f.11. Salt la pasul 3.

Observaţie: Partea a doua a redirectării de la pasul 7 poate economisi din efortul de căutare, dar cu o posibilă creştere exponenţială a efortului de calcul. Un rezultat important stabileşte că, dacă h este consistentă, atunci când A* expandează un nod n, s-a găsit deja un drum optimal către n. În concluzie, în acest caz A* nu trebuie niciodată să redirecteze pointeri. În orice caz, chiar dacă nu este îndeplinită condiţia de consistenţă, partea a doua a pasului 7 este deseori neimplementată.

3.3.2.2 Funcţia de evaluare a costului

Funcţia de evaluare a costului asociată unui nod de căutare, n, trebuie să reflecte costul de manipulare, divizat în două componente, vizibile în relaţia (III.1): începând de la start – g(n) – şi până la scop – h(n). Este evident că aceste două funcţii vor avea o structură asemănătoare.

Reducerea spaţiului configuraţiilor (C-space)

Pentru a obţine expresiile detaliate ale funcţiilor g şi h se analizează modurile posibile de manipulare. Se observă că particularităţile sarcinii (transport) pot fi folosite la reducerea spaţiului configuraţiilor de căutare a optimului (iniţial, dimensiunea lui C-space este dată de numărul total de grade de libertate ale sistemului de roboţi şi obiectului: obiectul dat se mişcă în 2D, deci are 3 grade de libertate, şi fiecare din roboţi au de asemenea câte 3 grade de libertate). De fapt, drumurile posibile şi mişcările sunt limitate, fiind diferite de drumurile (chiar şi restricţionate) ale unor obiecte zburătoare. Roboţii pot transporta obiecte în 2D numai în anumite configuraţii. În concluzie, poziţiile şi orientările roboţilor pot fi luate ca aranjamente în raport cu coordonatele obiectului manipulat şi codificate în consecinţă (figura 3.10).

43

1 2

5

3

4

6

7

81 1( , )r rx y

2 2( , )r rx y

( , )o ox y1r

2r

Fig. 3.10 Codificarea aranjamentelor roboţilor în jurul obiectului

a) b) c)

1

2

1 1( , )x y

2 2( , )x y

6 5

1 2

5

56

1

5

Se consideră că roboţii sunt întotdeauna plasaţi la colţurile obiectului pentru a folosi cu eficienţă maximă forţa de împingere atunci când execută o rotaţie a obiectului. În loc să se caracterizeze independent fiecare robot (prin coordonatele centrelor lor de masă şi unghiurile în raport cu centrul de masă al

obiectului, şi respectiv, ca în partea stângă a figurii

3.10), aranjamentul roboţilor este caracterizat global prim codificarea fiecărei poziţii posibile a roboţilor în jurul obiectului (ca în partea dreaptă a figurii 3.10). De asemenea, se consideră că roboţii pot fi plasaţi atât de aceeaşi parte a obiectului, cât şi pe părţi diferite la colţuri diferite. Având în vedere acţiunea lor cooperativă de transport al obiectului, anumite combinaţii sunt nefezabile (de exemplu [1,3] sau [7,4]).

În afară de schimbările de aranjament, mai sunt posibile schimbări de poziţie şi de orientare ale obiectului. Fiecare mişcare generală a obiectului şi a roboţilor poate fi, deci, descompusă în 3 mişcări independente. Corespunzător acestora, se definesc 3 operaţii primitive (figura 3.11):

a) roboţii schimbă poziţia obiectului în coordonate absolute printr-o operaţie de schimbare de poziţie;

b) roboţii schimbă orientarea obiectului printr-o operaţie de schimbare de orientare;c) roboţii îşi schimbă aranjamentul în jurul obiectului în timp ce îl manipulează.Fiecare din operaţiile de mai sus este independentă de celelalte două (de exemplu, pentru

schimbarea poziţiei, orientarea şi aranjamentul roboţilor în jurul obiectului sunt menţinute fixe etc.).

Fig. 3.11 Trei operaţii primitive ale unui obiect rectangular manipulat de către doi roboţi în 2D: a) schimbarea de poziţie; b) schimbarea de orientare; c) schimbarea de aranjament

În concluzie, numărul de grade de libertate ale sistemului (care dă dimensiunea lui C-space) a fost redus de la la numai 3, din care două sunt continue (poziţia centrului de masă şi unghiul de orientare) şi unul este discret (aranjamentul, restricţionat la 8 combinaţii posibile de poziţii ale roboţilor în jurul obiectului). Coordonatele obiectelor pe hartă sunt discretizate convenabil, astfel încât deplasarea are loc pe o hartă de pixeli (aşa cum este

44

sugerat în figura 3.11).

Alegerea funcţiei de cost

Deoarece se intenţionează să se ghideze căutarea în scopul minimizării costului (adică a timpului de manipulare), şi în acelaşi timp să se evite obstacolele, se propune ca cele două componente ale costului să fie definite astfel:

, (III.3)

unde componentele cu indicele „t” măsoară costul–timp. Componenta a lui ia în consideraţie posibilitatea de coliziune cu obstacolele. Această componentă reprezintă forţa de respingere de către obstacole şi a fost modelată ca un câmp de potenţial, aşa cum este prezentat în ceea ce urmează.

Funcţia trebuie să conţină costul (timpul) cumulat al unui drum de la nodul de start la nodul curent, n, adică suma costurilor tuturor arcurilor conţinute în acel drum. Costul unui arc

de la nodul la nodul este definit folosind notaţiile din figura III.4:

, (III.4)unde cele trei componente măsoară respectiv costul schimbării de poziţie (distanţa euclidiană):

, (III.5)costul schimbării de orientare:

, (III.6)şi costul schimbării de aranjament, exprimat în funcţie de distanţele pe care roboţii trebuie să le parcurgă pentru ca să-şi schimbe poziţiile (aşa cum este sugerat în figura III.4c)). Se observă că schimbarea de orientare trebuie să fie exprimată ca fiind o distanţă, şi anume lungimea segmentului de cerc corespunzător schimbării de unghi . Schimbările de orientare mai mari decât sunt reduse modulo . De aceea, o valoare aproximativă a costului de orientare ar putea fi:

, (III.6’)unde L este lungimea obiectului.

Funcţia are aceeaşi structură ca aceea a costului unui arc, considerând ca nod final nodul–scop, şi reprezintă o estimare a costului de manipulare până la scop.

Referitor la forţa de respingere a obstacolelor, , există mai multe modalităţi de definire a acesteia pe baza câmpurilor de potenţial [45], [46]. Funcţia folosită în această lucrare este:

, (III.7)unde d este distanţa de la punctul considerat la obstacol, iar r este o distanţă fixă (de exemplu,

, unde a şi b sunt dimensiunile robotului). Indiferent de forma câmpului de potenţial, se propune ca forţa totală de respingere exercitată de către un obstacol asupra ansamblului obiect–roboţi să fie suma câmpurilor de potenţial în toate colţurile ansamblului (sunt 8 colţuri indiferent de aranjamentul roboţilor – a se vedea figura III.3 – ale căror coordonate pot fi calculate dată fiind configuraţia nodului asociat). În concluzie:

45

110203040506070

11020304050607070

11020304050

11020304050

start

scop

0

/ 2 3 / 4

, (III.8)unde nb_obst este numărul obstacolelor.

Se poate concluziona că funcţia h(n) reprezintă un compromis între forţa de atracţie din partea scopului şi cea de respingere din partea obstacolelor. Pe de altă parte, se poate verifica uşor că funcţia h(n) nu este consistentă (datorită componentei care măsoară schimbarea de orientare, dependentă de unghiurile reduse modulo – vezi relaţia (III.6’)), deci harta de căutare nu este monotonă. Algoritmul se poate, deci, bloca în minime locale. De asemenea, a fost necesară o metodă suplimentară de evitare a coliziunilor cu obstacolele, pentru a rula efectiv algoritmul de căutare. Această metodă se bazează pe decizia dacă un punct dat este înafara sau înăuntrul unui poligon.

3.3.2.3 Discuţii asupra rezultatelor de implementare

Fig. 3.12 Drumul planificat în cazul unui exemplu de dimensiuni reduse.Săgeţile indică zonele de minim local

Această secţiune prezintă performanţele algoritmului A* propus pe un exemplu de dimensiuni mici.

Dimensiunile hărţii în pixeli sunt 70x50, harta conţine 4 obstacole, dimensiunile obiectului sunt 9x5 şi cele ale roboţilor 3x2 (figura III.5). Nodul de start este caracterizat de

coordonatele centrului de masă, (9,6), şi de unghiul de orientare al obiectului, .

Nodul–scop este reprezentat prin (65,26) şi . Algoritmul a făcut 194 de expansiuni ale nodurilor şi a necesitat 73.882 de secunde pe un Pentium II MMX la 233 MHz.

Se poate observa că, deşi cazul studiat are dimensiuni reduse, acesta are o caracteristică destul de restrictivă, şi anume raportul dintre dimensiunile hărţii şi dimensiunile obiectului.

46

Fig. 3.13 Imaginea iniţială

Din considerente de lizibilitate, aranjamentul roboţilor nu a fost reprezentat în figura 3.12. Datorită faptului că funcţia euristică, h, nu este monotonă, se pot observa comportări ciclice, datorate blocajului în minime locale. Săgeţile desenate în figura 3.12 corespund „salturilor” empirice introduse artificial în algoritm pentru a „evada” din minimele locale.

Traiectoria ilustrată în figura 3.12 corespunde în linii mari aşteptărilor. Este evident că o astfel de traiectorie necesită o filtrare preliminară transformării în secvenţe de comandă şi transmiterii acestora către roboţi. Această problemă priveşte sinteza planificatorului local şi interacţiunea acestuia cu planificatorul global, ceea ce reprezentă o problemă de investigare ulterioară.

3.4. Planificatorul local: urmărirea on-line a traiectoriei optimale. Tratarea reacţiei video

Planificatorul local are rolul de a realiza efectiv modul de manipulare rezultat din planificarea traiectoriei optimale de către planificatorul global, deci proiectarea lui aparţine domeniului aplicaţiilor de timp real de comandă a roboţilor. Aceasta este o sarcină destul de complexă, din care la momentul actual a fost realizată partea de traductor: prelucrarea reacţiei video.

3.4.1 Algoritmul de prelucrare de imagini

Sistemul de achiziţie şi prelucrare a imaginilor este compus din: cameră tip Webcam, PC, driver pentru cameră şi software de prelucrare.

Obiectele căutate sunt identificate cu ajutorul a două benzi colorate paralele (figura 3.13).

Paşii principali ai programului de achiziţie, prelucrare şi extragere a trăsăturilor sunt:a) achiziţia imaginii şi corectarea neliniarităţilor camerei;b) filtrarea zgomotului de pe imagine;c) selectarea culorilor obiectelor;d) stabilirea toleranţelor cu care se va decide dacă un anumit pixel este de culoarea căutată;e) determinarea tuturor obiectelor care au culorile stabilite la punctul c);f) eliminarea obiectelor care nu corespund din punct de vedere al dimensiunilor;

g) determinarea poziţiei şi orientării fiecărui obiect găsit.

În continuare se detaliază fiecare pas a) g).

a) Camerele de tipul celei folosite în experimentul nostru prezintă neliniarităţi, în speţă curbează imaginea către extremităţi (efect de „butoi”), introducând astfel erori de determinare a poziţiei. Erorile sunt cu atât mai mari cu cât poziţia respectivă este mai depărtată de centrul imaginii. Pentru a corecta aceste neliniarităţi s-a folosit o grilă de calibrare formată din repere echidistante. Astfel, pentru poziţia fiecărui reper s-au determinat coeficienţii care fac trecerea la poziţia reperului în imagine.

47

b) S-au folosit filtre liniare de dimensiune 3x3 şi 5x5, în funcţie de zgomotul din imagine.

c) Deoarece experimentul foloseşte de fiecare dată aceleaşi obiecte, culorile de căutat ar putea fi stabilite la începutul programului. Totuşi, datorită posibilităţii de schimbare a condiţiilor de iluminare, s-a preferat selectarea culorilor direct de pe imagine.

d) Datorită perturbaţiilor ca iluminarea neuniformă a imaginii, efectele de culoare la tranziţiile de la o culoare la alta şi chiar variaţiile în culorile obiectelor a trebuit să se aleagă un anumit interval de culoare în care un pixel să fie considerat de culoarea dorită. Acest interval poate fi impus manual, pe baza rezultatelor observate pe imagine, sau poate fi determinat automat, considerând drept criterii diferenţele dintre suprafeţele determinate ale obiectelor şi suprafeţele reale şi numărul de obiecte false. Parametrii după care se face căutarea sunt H, S şi V (tentă de culoare, saturaţie şi valoare – engl. Hue, Saturation, Value).

e) Datorită zgomotului imaginii, iluminării neuniforme a scenei sau alegerii greşite a pragurilor de recunoaştere a culorilor în obiecte pot apărea găuri (porţiuni din interiorul obiectului care nu apar ca fiind de culoarea obiectului). Algoritmul folosit consideră aceste găuri ca făcând parte din obiect, eliminând astfel erorile de determinare a poziţiei introduse de prezenţa găurilor. Din acest motiv se poate folosi numai în cazul obiectelor convexe, eventualele concavităţi fiind „umplute”.

S-a definit o structură obiect cu următorii membri:- nExtremStanga – este coordonata orizontală a celui mai din stânga pixel de pe ultima

linie a obiectului- nExtremDreapta – este coordonata orizontală a celui mai din dreapta pixel de pe ultima

linie- nExtremJos – coordonata verticală a celei mai de jos linii a obiectului- nCurentStanga – coordonata orizontală a celui mai din stânga pixel de pe linia curentă,

aparţinând obiectului- nCurentDreapta – coordonata orizontală a celui mai din dreapta pixel de pe linia

curentă, aparţinând obiectului- nCurentJos – coordonata verticală a liniei curente- nSuprafata – suprafaţa obiectului- nXCentru – la sfârşitul algoritmului este coordonata orizontală a centrului de masă al

obiectului; pe parcurs este coordonata orizontală a centrului de masă multiplicată cu nSuprafata

- nYCentru – la sfârşitul algoritmului este coordonata verticală a centrului de masă al obiectului; pe parcurs este coordonata verticală a centrului de masă multiplicată cu nSuprafata

- x – coordonata orizontală a pixelului curent- y – coordonata verticală a pixelului curent- nContor – numărul de obiecte cărora le aparţine pixelul curent

Algoritmul este detaliat în continuare.1. Pixelul curent are culoarea căutată? Dacă nu, salt la 19.2. Lista obiectelor este goală? Dacă nu, salt la 4.3. Se iniţializează un obiect nou.4. Se selectează următorul obiect.5. ((x >= nExtremStanga – 1) ŞI (x <= nExtremDreapta + 1) ŞI (y = nExtremJos + 1))?

48

Dacă da, salt la 8.6. ((y = nCurentJos) ŞI (x = nCurentDreapta + 1))? Dacă nu, salt la 4.7. nCurentDreapta = x; nXCentru = nXCentru + x;

nYCentru = nYCentru + y; nSuprafata = nSuprafata + 1. Salt la 14.8. nCurentJos = y.9. nCurentStanga = –1? Dacă nu, salt la 11.10. nCurentStanga = x11. nCurentDreapta = –1? Dacă nu, salt la 13.12. nCurentDreapta = x; nXCentru = nXCentru + x;

nYCentru = nYCentru + y; nSuprafata = nSuprafata + 1. Salt la 14.13. nXCentru = nXCentru + (nCurentDreapta + 1) + ... + x;

nYCentru = nYCentru + (x – nCurentDreapta) y;nSuprafata = nSuprafata + x – nCurentDreapta.

14. nContor = nContor + 1.15. E ultimul obiect din listă? Dacă nu, salt la 4.16. nContor > 1? Dacă da, se unesc cele două obiecte.17. Pixelul curent este ultimul de pe linie? Dacă nu, salt la 20.18. nExtremStanga = nCurentStanga; nExtremDreapta = nCurentDreapta;

nExtremJos = nCurentJos; nCurentStanga = –1;nCurentDreapta = –1; nCurentJos = –1.

19. Pixelul curent este ultimul din imagine? Dacă da, salt la 21.20. Se trece la pixelul următor. Salt la 1.21. Sfârşit.

f) În cazul unei imagini zgomotoase sau al prezenţei în scenă a altor obiecte decât cele căutate pot rezulta obiecte false, care vor fi eliminate după compararea cu dimensiunile cunosctue ale obiectului.

g) Poziţia fiecărui obiect se dă prin poziţia centrului său de greutate, situat la jumătatea segmentului care uneşte centrele de greutate ale celor două benzi colorate, iar orientarea obiectului este dată de orientarea acestui segment.

3.4.2 Rezultate experimentale

Pentru experiment s-a construit o scenă cu două obiecte ce pot fi identificate prin câte două benzi colorate. Unul din obiecte are o bandă roşie şi una albastră, iar celălalt o bandă roşie şi una galbenă. În continuare sunt prezentate rezultatele identificării fiecărei culori (fig. 3.14, 3.15, 3.16), apoi a obiectelor (fig. 3.17).

În urma mai multor experimente s-au înregistrat următoarele erori maxime în determinarea poziţiei şi a orientării obiectelor:

- la determinarea poziţiei eroarea maximă a fost de 1 pixel, atât pe verticală, cât şi pe orizontală; dimensiunile scenei văzute de cameră fiind de 1x0.75 m, iar rezoluţia de 320x240 pixeli, rezultă o eroare maximă de 0.31 cm, atât pe orizontală, cât şi pe verticală;

- la determinarea orientării s-au înregistrat variaţii de +/– 1 grad.

49

Fig. 3.17 Determinarea tuturor obiectelor căutate

Fig. 3.14 Determinarea obiectelor albastre

Fig. 3.15 Determinarea obiectelor galbene

Fig. 3.16 Determinarea obiectelor roşii

Condiţiile desfăşurării experimentelor au fost:- iluminare mixtă, în proporţie de

aproximativ 80% artificială şi 20% naturală;- rezoluţia camerei a fost impusă la

320x240 pixeli;- s-a folosit funcţia de corectare a

neliniarităţilor camerei, cu o grilă de corecţie de 32x24 puncte, coeficienţii de corecţie pentru pixelii aflaţi între aceste puncte obţinându-se prin interpolare.

50

3.5 Concluzii şi perspective

Cercetările sintetizate în acest raport propun o arhitectură pe 2 niveluri pentru comanda optimală a unui sistem de 2 roboţi mobili care execută transportul unui obiect dreptunghiular în 2D, cu evitarea obstacolelor în timp minim (cu consum energetic minim).

Nivelul ierarhic inferior este constituit de către cei 2 roboţi şi este modelat ca sistem dinamic hibrid. Comportamentul unui astfel de sistem este caracterizat atât de variabile de stare cu evoluţie sincronă cu timpul, continue sau discrete, cât şi de evenimente, cu apariţie asincronă. Roboţii consideraţi sunt dotaţi cu un nivel minim de inteligenţă şi autonomie, respectiv numai capacitatea de a prelucra informaţiile provenite de la senzori. Problema de optimizare mai sus enunţată se formulează ca minimizarea cu restricţii a unei funcţionale reprezentând un indice de performanţă de timp. În esenţă, scopul este de a planifica traiectoria şi modul de manipulare optimale ale obiectului de către cei 2 roboţi.

Pe nivelul ierarhic superior este plasată structura de control centralizat (supervizor) care asigură comportamentul optimal în raport cu indicele de performanţă definit. În esenţă, este vorba despre sinteza unui planificator de traiectorie optimală, care a fost numit planificator global. Închiderea buclei presupune transmiterea comenzilor efective de schimbare a poziţiei către roboţi în vederea urmăririi traiectoriei optimale. Aceasta se realizează de către planificatorul local.

Prin analogie cu elementele unei bucle de reglare clasice, planificatorul global calculează referinţa, care se transmite planificatorului local. După executarea comenzii de către roboţi, se estimează eroarea faţă de poziţiile reale atinse de roboţi, calculate pe baza reacţiei video. A fost prezentat un algoritm de prelucrare de imagini care permite tratarea suficient de performantă (atât rapidă, cât şi precisă) a acestei informaţii de măsură. Dacă eroarea de poziţie depăşeşte un anume prag maxim admisibil, atunci se reiniţializează planificatorul global pentru calcularea traiectoriei din poziţia curentă reală. Pentru minimizarea acestei erori este necesar un model cât mai precis al nivelului inferior, respectiv considerarea cât mai completă a interacţiunilor roboţilor şi obiectului transportat cu mediul. Planificatorul local înglobează astfel elementul de comparaţie şi elementul de execuţie.

Planificatorul global se bazează pe un rezultat clasic din cercetările operaţionale: algoritmul A* de căutare al drumului de cost minim într-un graf. Acest planificator furnizează momentul, locul şi mişcarea care trebuie realizată, considerându-se că roboţii pot urmări ideal traiectoria impusă. Erorile de poziţionare a roboţilor, ca şi explicitarea modelului static al acestora vor fi considerate în sinteza planificatorului local în cadrul unor cercetări ulterioare.

Cât priveşte eventualele îmbunătăţiri ale planificatorului global, o sarcină de investigare constă în definirea unor funcţii euristice care să se supună condiţiei de consistenţă pentru evitarea minimelor locale în calculul traiectoriei optimale. Ar putea fi utilă combinarea funcţiilor euristice cu alte tipuri de câmpuri de potenţial pentru a obţine o hartă de căutare monotonă.

Pe viitor, se intenţionează implementarea metodei de planificare propuse ca aplicaţie de timp real, care să funcţioneze eventual în cazul unui mediu variant. În acest caz, reprezentarea hărţii este obţinută în mod continuu prin reacţie video. Astfel, metoda de planificare necesită robustificare la erori, întârzieri şi schimbări de mediu.

51

Bibliografie

http://www-2.cs.cmu.edu/afs/cs.cmu.edu/usr/pstone/public/papers/96ieee-survey/http://www.ici.ro/ici/revista/ria2003_3/art4.htmhttp://www-2.cs.cmu.edu/~softagents/multi.html

[1] Ollero, A., G. Morel, P. Bernus, S.Y. Nof, J. Sasiadek, S. Boverie, H. Erbe, R. Goodall (2002). IFAC 2002 Milestone Report on Manufacturing and Instrumentation: from MEMS (Micro Electro-Mechanical Components) to Enterprise Systems, Preprints of the 15th IFAC World Congress – Plenary papers, survey papers and milestones (Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), Barcelona, Spain, pp. 195-205.

[2] Pham, D.T., S. Yildirim (2002). Comparison of four methods of robot trajectory control, Preprints of the 15th Triennial IFAC World Congress (CD-ROM - Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), July 21-26 2002, Barcelona, Spain.

[3] Montano, J.M.L. (2002). Robot navigation in very complex, dense and cluttered indoor/outdoor environments, Preprints of the 15th Triennial IFAC World Congress (CD-ROM - Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), July 21-26 2002, Barcelona, Spain.

[4] Jones, J.L., A.M. Flynn, B.A. Seiger (1999). Mobile robots – inspiration to implementation (second edition), A.K. Peters-Natick, Massachussets.

[5] Figueras, A., J. Colomer, J.L. de la Rosa (2002). Supervision of heterogeneous controllers for a mobile robot, Preprints of the 15th Triennial IFAC World Congress (CD-ROM - Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), July 21-26 2002, Barcelona, Spain.

[6] Garcia, C.E., R. Carelli, J.F. Postigo, C. Soria (2003). Supervisory control for a telerobotic system: a hybrid control approach, Control Engineering Practice, 11, pp. 805-817.

[7] Fong, T., I. Nourbakhsh, K. Dautenhahn (2003). A survey of socially interactive robots, Robotics and Autonomous Systems, 42, pp. 143–166.

[8] Dautenhahn, K., A. Billard (1999). Bringing up robots or—the psychology of socially intelligent robots: From theory to implementation, Proceedings of the Autonomous Agents.

[9] Balestrino, A., A. Landi (2002). High path coordonation for multiple vehicles and reciprocal root locus, Preprints of the 15th Triennial IFAC World Congress (CD-ROM - Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), July 21-26 2002, Barcelona, Spain.

[10] Bernabeu, E.J., J. Tornero (2002). Cooperative motion planning for multiple vehicles in automated storage systems, Preprints of the 15th Triennial IFAC World Congress (CD-ROM - Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), July 21-26 2002, Barcelona, Spain.

[11] Mitidieri, C., C.E. Pereira, L.L. Penz (2002). On coordinating multi-agent systems using a time constrained contract network protocol, Preprints of the 15th Triennial IFAC World Congress (CD-ROM - Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), July 21-26 2002, Barcelona, Spain.

52

[12] Uzmay, I., R. Burkan, H. Sarikaya (2004). Application of robust and adaptive control techniques to cooperative manipulation, Control Engineering Practice, 12, pp. 139-148.

[13] Fernandez, J.A., J. Gonzalez (2002). Task-driven, multiple abstraction for modeling mobile robot large-scale space, Preprints of the 15th Triennial IFAC World Congress (CD-ROM - Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), July 21-26 2002, Barcelona, Spain.

[14] Hsieh, F.-S. (2004). Model and control holonic manufacturing systems based on fusion of contract nets and Petri nets, Automatica, 40, pp. 51-57.

[15] Tanner, H.G., G.J. Pappas (2002). Formation input-to-state stability, Preprints of the 15th Triennial IFAC World Congress (CD-ROM - Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), July 21-26 2002, Barcelona, Spain.

[16] Branicky, M.S. (1997). Stability of hybrid systems: state of the art, Proceedings of the 36th IEEE Conference on Decision & Control.

[17] Zhang, W., M.S. Branicky, S.M. Philips (2001). Stability of networked control systems, IEEE Control Systems Magazine, 21(1).

[18] Davrazos, G.N., N.T. Koussoulas (2002). Stability analysis of networked hybrid systems, Preprints of the 15th Triennial IFAC World Congress (CD-ROM - Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), July 21-26 2002, Barcelona, Spain.

[19] Lin, H., X.D. Koutsoukos, P.J. Antsaklis (2002). Hierarchical control for a class of uncertain piecewise linear hybrid dynamical systems, Preprints of the 15th Triennial IFAC World Congress (CD-ROM - Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), July 21-26 2002, Barcelona, Spain.

[20] Branicky, M.S. (1998). Multiple Lyapunov functions and other analysis tools for switched and hybrid systems, IEEE Transactions on Automatic Control, 43(4).

[21] Rubensson, M., B. Lennartson (2000). Stability and robustness of hybrid systems using discrete-timed Lyapunov functions techniques, Proceedings of the American Control Conference.

[22] Petterson, S. (1999). Analysis and design of hybrid systems, Ph.D. Thesis, Chalmers University of Technology, Sweden.

[23] Glocker, M., O. von Stryk (2002). Hybrid optimal control of motorized traveling salesmen and beyond, Preprints of the 15th Triennial IFAC World Congress (CD-ROM - Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), July 21-26 2002, Barcelona, Spain.

[24] Stursberg, O., S. Engell (2002). Optimal control of switched continuous systems using mixed-integer programming, Preprints of the 15th Triennial IFAC World Congress (CD-ROM - Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), July 21-26 2002, Barcelona, Spain.

[25] Stiver, J., P. Antsaklis (1992). Modelling and analysis of hybrid control systems, Proceedings of the 31st Conference on Decision and Control, Tucson, Arizona, pp. 3748-3751.

[26] Xie, G., L. Wang, P. Yang (2002). Stability of a class of hybrid dynamic systems, Preprints of the 15th Triennial IFAC World Congress (CD-ROM - Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), July 21-26 2002, Barcelona, Spain.

[27] Bemporad, A., L. Giovanardi, F.D. Torrisi (2000). Performance driven reachability analysis for optimal scheduling and control of hybrid systems, Proceedings of the 39th IEEE Conference on Decision and Control, Sidney, Australia, pp. 969-974.

53

[28] Potocnik, B., A. Bemporad, F.D. Torrisi, G. Music, B. Zupancic (2002). Scheduling of hybrid systems: multi product batch plant, Preprints of the 15th Triennial IFAC World Congress (CD-ROM - Eds. E.F. Camacho, L. Basanez, J.A. de la Puente), July 21-26 2002, Barcelona, Spain.

[29] Manon, Ph., C. Valentin-Roubinet, G. Gilles (2002). Optimal control of hybrid dynamical systems: application in process engineering, Control Engineering Practice, 10, pp. 133-149.

[30]Arai, T. and J. Ota (1996). Let us work together – Task planning of multiple mobile robots. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 298-303.

[31]Rus, D, B. Donald and J. Jennings (1995). Moving furniture with teams of autonomous robots. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 235-242.

[32]Sawasaki, N. and H. Inoue (1996). Cooperative manipulation by autonomous intelligent robots. JSME International Journal, C, 39(2), pp. 286-293.

[33]Kosuge, K., T. Osumi and K. Chiba (1997). Load sharing of decentralized controlled multiple mobile robots handling a single object. In: Proceedings of the IEEE/RSJ International Conference on Robotics and Automation, pp. 3373-3378.

[34]Hashimoto, M., F. Oba and S. Zenitani (1995). Object transportation control by multiple wheeled vehicle planar Cartesian manipulator systems. In: Proceedings of the IEEE/RSJ International Conference on Robotics and Automation, pp. 2267-2272.

[35]Sugar, T.G. and V. Kumar (2002). Control of cooperating mobile manipulators. IEEE Transactions on Robotics and Automation, 18(1), pp. 94-103.

[36]Barraquand, J. and J.-C. Latombe (1991). Robot motion planning: A distributed representation approach. Int. J. Robot. Res., 10(6), pp. 628-649.

[37]Gupta, K.K. and Z. Guo (1992). Motion planning for many degrees of freedom: Sequential search with backtracking. In: Proceedings of the IEEE International Conference of Robotics and Automation, pp. 2328-2333.

[38]Kondo, K. (1991). Motion planning with six degrees of freedom by multi-strategic bidirectional heuristic free-space enumeration. IEEE Transactions on Robotics and Automation, 7(3), pp. 267-277.

[39] Ota, J., N. Miyata, T. Arai, E. Yoshida, D. Kurabayashi and J. Sasaki (1995). Transferring and regrasping a large object by cooperation of multiple mobile robots. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 543-548.

[40] Yamashita, A., T. Arai, J. Ota and H. Asama (2003). Motion Planning of Multiple Mobile Robots for Cooperative Manipulation and Transportation. IEEE Transactions on Robotics and Automation, 19(2), pp. 223-237.

[41] Asarin, A., O. Maler, A. Pnueli (1995). On the analysis of dynamical systems with piecewise constant derivatives, Theoretical Computer Science, 138, pp. 35-65.

[42] Pontryagin, L.S., V.G. Boltyanskii, R.V. Gamkrelidze, E.F. Mishchenko (1964). The mathematical theory of optimal processes, Pergamon, New York.

[43] Miller, R.E. (1999). Optimization: Foundations and Applications, John Wiley and Sons.[44]Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving,

Addison-Wesley Longman Publishing Co., Inc., Boston, MA, U.S.A.[45]Latombe, J.-C. (1991). Robot motion planning, Kluwer, Norwell MA, U.S.A.[46]Hwang, Y.K. and N. Ahuja (1992). A potential field approach to path planning. IEEE

Transactions on Robotics and Automation, 8(1), pp. 23-32.

54

[47] Ulieru, M. et.al. (2001) Holonic Enterprise as an Information Ecosystem, Proc. Workshop on “Holons – Autonomous and Cooperative Agents for the Industry”, Autonomous Agents International Conference, Montreal, Canada, May 2-6, 2001, pp. 3-20.

[48] Mihaela Ulieru and S. Ramakhrishnan, “An Approach to the Modelling of Multi-Agent Systems as Fuzzy Dynamical Systems”, Advances in Artificial Intelligence and Engineering Cybernetics, Vol. V: Multi-Agent Systems/Space-Time Logic/Neural Networks (George Lasker, Ed.), IIAS-68-99, ISBN 0921836619, 1999.

[49] Werner E (1996); ‘Logical Foundations of Distributed Artificial Intelligence’ in Foundations of Distributed Artificial Intelligence (eds. O’Hare G.M.P. and Jennings N.R.) (1996) John Wiley & Sons Interscience.

[50] Subramanian, R. and Mihaela Ulieru, “Behavioral analysis of multi-agent systems by dynamic modeling with application to technical and social systems”, InterSymp’99, International Conference of the Institute for Advance Studies in Systems Research, Informatics and Cybernetics, Baden-Baden, Germany, August 2-7, 1999.

[51] Zimmermann, H-J, – Fuzzy Set Theory And Its Applications, Kluwer Academic (1991).

[52] Klir, G. and Folger, Tina, Fuzzy sets, Uncertainty, and Information, Prentice Hall, (1988).

[53] Stefanoiu, D., Ulieru, Mihaela and Norrie, D., Multi-Agent Systems Planning by Ambiguity Minimization, Symposium on Computational Intelligence (CI’2000), ISA’2000 Congress, Wollongong, Australia, December 2000.

[54] Goldberg, D.E., Simple Genetic Algorithms, University of Michigan, Dept. of Civil Engineering, Ann. Arbor MI (1982).

[55] S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi – Optimization by Simulated Annealing, Science, 220:671-680 (1983).

[56] D. A. Pormerleau, Neural Network Perception for Mobile Robot Guidance. KluwerAcademic Publishers, 1993.

[57] S. J. Russell and P. Norvig, Artificial Intelligence: A Modern Approach. EnglewoodCliffs, NJ: Prentice Hall, 1995.

[58] G. Weiß and S. Sen, eds., Adaptation and Learning in Multiagent Systems. Berlin:Springer Verlag, 1996.

[59] AAAI, Adaptation, Coevolution and Learning in Multiagent Systems: Papers from the 1996 AAAI Spring Symposium, (Menlo Park,CA), AAAI Press, March 1996. AAAITechnical Report SS-96-01. Sandip Sen-Chair.

[60] M. Benda, V. Jagannathan, and R. Dodhiawala, ‘‘On optimal cooperation ofknowledge sources - an empirical investigation,’’ Tech. Rep. BCS-G2010-28, BoeingAdvanced Technology Center, Boeing Computing Services, Seattle, Washington, July1986.

55

[61] V. R. Lesser, ‘‘Multiagent systems: An emerging subdiscipline of AI,’’ ACM Computing Surveys, vol. 27, pp. 340-342, September 1995.

[62] K. S. Decker, ‘‘Distributed problem solving: A survey,’’ IEEE Transactions on Systems, Man, and Cybernetics, vol. 17, pp. 729-740, September 1987.

[63] H. V. D. Parunak, ‘‘Applications of distributed artificial intelligence in industry,’’ inFoundations of Distributed Artificial Intelligence (G. M. P. O’Hare and N. R. Jennings,eds.), pp. 139-164, Wiley Interscience, 1996.

[64] E. H. Durfee, ‘‘What your computer really needs to know, you learned inkindergarten,’’ in Proceedings of the Tenth National Conference on Artificial Intelligence,(Philadelphia, PA), Morgan Kaufman, 1992. Invited Talk.

[65] K. S. Decker, ‘‘Task environment centered simulation,’’ in Simulating Organizations: Computational Models of Institutions and Groups (M. Prietula, K. Carley,and L. Gasser, eds.), AAAI Press/MIT Press, 1996.

56