1 Studiul unor metodologii existente in literatura de ...dsplabs.cs.upt.ro › grants › melissevs...

Răzvan-Dorel CIOARGĂ Comportament emergent în medii colaborative robotizate

1 Studiul unor metodologii existente in literatura de specialitate aplicabile in domeniul mediilor asociative

1.1 Introducere

Sistemele distribuite, deşi au ajuns într-o fază de maturitate, prezintă o serie de probleme importante atunci când se încearcă aplicarea principiilor acestora la reţele de senzori, în principal din cauza numărului foarte mare de entităţi implicate care conduce la o creştere exponenţială a cerinţelor computaţionale precum şi a complexităţii algoritmilor folosiţi. Totodată, reţelele de senzori sunt formate din entităţi care prezintă capacităţi reduse de comunicare: lăţime de bandă mică, raza de transmisie mică (în cazul reţelelor de senzori fără fir). Sistemele distribuite prezintă o serie de algoritmi extremi de performanţi care rezolvă pentru sistemele distribuite artificiale uzuale o serie de probleme legate de: consistenţă şi replicare, sincronizare, servicii de nume, comunicaţie, pierdere de mesaje, fiabilitate şi retransmisie. Algoritmii care rezolvă aceste probleme sunt extrem de complecşi, necesită o putere computaţională mare (de ordinul sistemelor de calcul PC) şi o lăţime de bandă mare, folosită mai ales în cazul retransmisiei de mesaje. În general, sistemele de reţele de senzori prezintă următoarele caracteristici:

Număr mare de noduri; Puterea computaţională redusă; Lăţime de bandă redusă;

Datorită acestor caracteristici, folosirea tiparelor de comportament emergent este recomandată în cazul reţelelor de senzori şi al senzorilor inteligenţi. Pentru a identifica avantajele şi dezavantajele folosirii de tipare de comportamente emergente se prezintă un studiu comparativ între soluţiile de comportament emergent existente. Printre soluţiile prezentate se numără:

Comunicaţia bazată pe feromoni în sistemele distribuite: prin studiul coloniilor de furnici şi identificarea modului de comunicaţie între furnicile din acelaşi muşuroi s-a dezvoltat un model de comunicaţie destinat sistemelor distribuite.

Computere SPRAY: se prezintă un concept de reţele de sisteme de calcul, de dimensiuni suficient de mici pentru a fi incluse într-o suspensie lichidă care, apoi, să fie efectiv „vopsită” pe o suprafaţă a unui obiect pentru a-i mări acestuia funcţionalitatea.

Smart Dust: proiectul Smart Dust iniţiat la Berkeley şi sponsorizat de agenţia DARPA încearcă aducerea reţelelor de senzori la un nou nivel tehnologic.

După prezentarea comparativă a soluţiilor de comportament emergent se prezintă posibilităţile de utilizare a acestor soluţii pentru a surmonta problemele întâlnite la reţelele de senzori inteligenţi.

Comportament colaborativ 1

Comportament emergent în medii colaborative robotizate Răzvan-Dorel CIOARGĂ

1.2 K-TEAM K-Robots

Dispozitivele K-Robots create de Corporaţia K-TEAM [1] au fost iniţial proiectaţi pentru a fi folosite în centre de cercetare multidisciplinare în domeniul comportamentului emergent, colectivelor de roboţi şi a inteligenţei artificiale. Roboţii sunt bine echipaţi pentru folosirea într-o varietate de aplicaţii de cercetare cum ar fi: colectivele de roboţi, robotica bioinspirată şi robotică evolutivă. Robotul Khepera are dimensiunile cele mai mici dintre toţi roboţii produşi de Corporaţia K-TEAM. Este construit în jurul unui microcontroler Motorola 68331, două servo-motoare de curent continuu cu codificatoare incrementale, senzori de proximitate în infraroşu şi o magistrală de extensie proprietară – K-Extension Bus.

Figura 1: Robotul Khepera (Sursa [1])

Robotul Koala II este o versiune de dimensiuni mai mari, mai puternică şi reprezintă o platformă mai bună pentru implementarea de aplicaţii cum ar fi procesare video locală; robotul a fost construit pentru folosirea în mediul extern. Acesta conţine un microcontroler Motorola 68331, două servo-motoare de curent continuu cu codificatoare incrementale, senzori de proximitate, senzori de lumină ambientală, senzori acustici pentru sonar. Placa KoreBot este controller hardware modular care permite crearea de roboţi dedicaţi. Este construită în jurul unui microprocesor Intel PXA-255 400MHz, are memorie RAM, compact flash şi conectori USB. Toţi roboţii prezentaţi mai sus au prezintă şi o serie de module software:

GNU C Cross-Compiler: compilatorul gratuit de la K-TEAM care oferă posibilitatea scrierii de cod C pentru roboţii folosiţi;

KTProject: interfaţa pentru compilatorul descris mai sus; Pentru operarea la distanţă se recomandă folosirea mediilor LabVIEW şi / sau

MATLAB; Webots: simulator pentru toţi roboţii K-TEAM cu posibilitatea simulării

acestor roboţi în medii grafice 3D.

2 Comportament colaborativ


1.3 ANTH – ANtennary THings

ANTH (Antennary Things) [2] reprezintă un mediu de programare în spaţiu-real pentru medii de calculatoare omniprezente. Un astfel de mediu omniprezent este alcătuit dintr-o mulţime de obiecte care includ funcţii de comunicaţie şi calcul pe care le pun la dispoziţie, în comun, pentru a sintetiza servicii variate. La baza structurii ANTH stă un circuit integrat ANTH care pune la dispoziţia utilizatorului 3 funcţionalităţi importante:

Funcţia de interfaţare care controlează interconexiunea cu un alt dispozitiv; Funcţia de comunicaţie care construieşte o infrastructură de reţea pentru

cooperarea dispozitivelor; Funcţia de calcul computaţional pentru procesarea aplicaţiilor;

Obiectele ANTH sunt de trei tipuri: EN (Emitter Node, nod emiţător): reprezintă obiectul care anunţă un

eveniment (declanşarea unui întrerupător, declanşarea temporizatorului unei alarme etc.).

SN (Sympathizer Node, nod simpatetic): reprezintă entitatea care primeşte anunţul reprezentând declanşarea unui eveniment. Totodată, un astfel de obiect ANTH poate declanşa acţiuni pe baza evenimentelor pe care le primeşte.

Controlor: reprezintă un dispozitiv de legătură între un obiect EN şi un obiect SN.

Figura 2: Schema bloc a unui sistem ANTH (Sursa [2])

Asupra obiectelor ANTH descrise, un controlor poate efectua trei operaţii de bază:

Preluarea unui eveniment de la un obiect EN şi transmiterea acestuia la un obiect SN (operaţie de tipul „deschide uşa dacă întrerupătorul este apăsat”);

Preluarea apariţiei unui eveniment de la un obiect EN şi transmiterea acestuia la un alt obiect EN (operaţia de tipul „aprinde lumina dacă se deschide uşa” fiind executată după operaţia descrisă mai sus). Astfel evenimentul declanşator se poate propaga prin mai mulţi actuatori.



Preluarea apariţiei unui eveniment de la un obiect SN şi transmiterea acestuia la un alt obiect SN (operaţia de tipul „aprinde lumina dacă întrerupătorul este apăsat” fiind executată simultan cu prima operaţie). Astfel evenimentul declanşator poate fi recepţionat de mai mulţi actuatori.

1.4 Sisteme distribuite de comunicaţie bazate pe feromoni

Comportamentul emergent, caracterizat drept non-deterministic al sistemelor naturale poartă această denumire deoarece se formează din comportamentele multor agenţi simpli care urmăresc un set limitat de reguli simple bazate doar pe viziunea locală a acestora asupra sistemului. Agenţii individuali nu sunt conştienţi de starea globală a sistemului sau de scopurile funcţionale finale ale sistemului [3, 4, 5]. Comunicaţia (interacţiunea) este imperativă în ambele tipuri de sisteme distribuite, atât cel deterministic, artificial cât şi cel emergent, natural. În domeniul natural, studiul coloniilor de furnici a relevat faptul că schimbul de feromoni joacă un rol foarte important în comunicaţia în interiorul muşuroiului. In sistemele naturale, schimbul de feromoni este un element important care generează tipare de comportament emergent pentru întregul sistem. Furnicile individuale îşi formează o imagine localizată a întregului sistem bazată pe schimbul de feromoni dintre acestea şi celelalte furnici pe care le întâlnesc. Diferiţilor tipuri de feromoni le corespund diferite informaţii; de asemenea, furnicile extrag informaţii şi din intensitatea feromonilor. Extrăgând informaţiile din feromoni, furnicile determină comportamentul furnicilor vecine şi de aici îşi pot deduce propriul rol [4, 5], fără a mai stabili un dialog sau orice alt tip de negociere. Schimbul de feromoni prezintă o modalitate simplă de comunicaţie prin care informaţia este transmisă folosind o serie de mesaje chimice. Entitatea care recepţionează mesajul poate extrage informaţie chiar din însăşi mesajul chimic (tipul feromonului folosit indică tipul mesajului). Din mesajul chimic se pot extrage însă informaţii suplimentare (meta-data) cum ar fi importanţa mesajului (interpretată din frecvenţa de transmisiei feromonului) sau cât de recent este mesajul (dedus din puterea chimică a feromonului). În contextul comunicării în sisteme distribuite, comunicaţia pe baza feromonilor poate fi văzută ca având o serie de parametri similari cu cei asociaţi comunicaţiei digitale:

Tipul feromonului este analog cu tipul mesajului; Puterea chimică a feromonului este asociată cu vârsta mesajului; Rata de transmisie a feromonului este asociată importanţei mesajului,

priorităţii mesajului; Lăţimea de bandă este irelevantă în cazul comunicaţiei bazate pe feromoni

deoarece aceştia sunt într-o mare măsură persistenţi;

Comunicaţia bazată pe feromoni este în mare măsură semi-fiabilă deoarece mesajele chimice continuă să fie transmise până când cauza care le-a determinat încetează să existe (în cazul furnicilor această situaţie ar putea fi eliminarea inamicilor, terminarea unei surse de hrană). Datorită acestui mod de prezentare a mesajelor pierderea unor mesaje individuale este fără consecinţă.



Acest tip de comunicaţie este simplex (unidirecţional) urmele de feromoni fiind create de furnici pentru ca alte furnici să le urmeze. Comunicaţia de tip duplex nu există, apare doar o pereche de mesaje simplex care însă nu sunt corelate ca parte a unei conversaţii. Comunicarea naturală pe bază de feromoni este non-deterministică şi totuşi extrem de fiabilă, folosind un număr mic de mesaje simple, este stabilă, robustă şi scalabilă. Se încearcă astfel implementarea unui tip de comunicaţie destinat sistemelor distribuite în care mesajele să fie implementate ca feromoni; se elimină necesitatea stabilirii unei conexiuni între partenerii de comunicaţie. Dezavantajele folosirii unui sistem non-deterministic este determinarea empirică a condiţiilor optime de funcţionare: folosirea protocolului emergent de comunicaţie bazat pe feromoni nu este eficientă în cazul existenţei a unui număr mic de entităţi, după cum nici un muşuroi de furnici nu supravieţuieşte cu un număr limitat de indivizi. Totodată un număr exagerat de indivizi care comunică prin feromoni duce invariabil la gâtuirea reţelelor de interconexiune (în cazul coloniilor de furnici, când apare un număr mai mare de indivizi, colonia se împarte în două colonii, fiecare cu regina sa; colonia care aparţine de regina nouă părăseşte muşuroiul şi construieşte altul pe un alt teritoriu pentru a nu sufoca colonia originală).

1.5 Sisteme SPRAY cu auto-organizare

Ideea de computere SPRAY [6 - 8] a apărut mai întâi ca un concept de reţele futuristice în care acestea ar putea fi puse la dispoziţia utilizatorilor sub formă de cutii de aerosoli pentru a fi aplicate pe diferite obiecte pentru a le mări funcţionalitatea: haine inteligente, materiale auto-asamblante, auto-reparante. Deoarece stadiul tehnologic actual face ca implementarea unei astfel de reţele futuristice să fie prea îndepărtată, principiile de miniaturizare, control descentralizat şi auto-administrare ale sistemelor SPRAY sunt aplicate cu succes în domeniul reţelelor de senzori cu auto-organizare, formare ad-hoc: reţele de dispozitive mobile, reţele de micro-computere care se întind pe o suprafaţă de câţiva metri pătraţi, reţele de dispozitive conectate la Internet care acoperă suprafeţe mult mai mari (reţele metropolitane, backbone naţional etc.). Principiile computerelor SPRAY sunt aplicate în toate domeniile reţelelor cu auto-organizare:

Scară microscopică: computere SPRAY adevărate (proiectul Smart Dust – Praf Inteligent dezvoltat la Berkeley );

Scară medie: computere handheld şi haine inteligente (wearable computers); Scară globală: calcul global (întregul Internet este privit ca un sistem

heterogen distribuit);

Astfel de sisteme trebuie instalate cu efort nul de pre-configurare datorită numărului mare de entităţi prezente. Astfel de sisteme descentralizate, autonome, care operează în medii dinamice şi iau decizii pe baza informaţiilor disponibile din aceste medii, prezintă în mod constant comportamente non-deterministice, neaşteptate care sunt clasificate drept comportamente emergente.



Sistemele SPAY la scară microscopică

În stadiul actual de dezvoltare tehnologică se pot crea computere adevărate de dimensiuni de doar câţiva milimetri (proiectul Smart Dust – Praf Inteligent dezvoltat la Berkeley [7, 8]). Astfel de dispozitive pot fi înzestrate cu posibilităţi de comunicaţie fără fir (optice sau radio), pot avea proprietăţi senzoriale (termice, optice sau inerţiale) şi pot afecta local, într-o măsură bine determinată, mediul înconjurător (optic, mecanic). Computerele SPRAY propriu-zise sunt imaginate ca fiind „nori” de microcomputere de dimensiuni submicroscopice care pot fi instalate în mediul dorit cu ajutorul aerosolilor sau prin vopsire. Odată instalate aceste dispozitive vor forma reţele ad-hoc şi îşi vor coordona acţiunile în mod inteligent pentru a adăuga funcţionalităţi specifice mediului unde au fost instalate. O serie de proprietăţi necesare ale acestor dispozitive SPRAY derivă din faptul că acestea vor fi instalate în medii fizice. Computerele SPRAY sunt asemănătoare cu sistemele distribuite actuale în sensul că ambele sunt împărţite în mai multe entităţi distincte, individuale care conlucrează pentru atingerea unui scop comun [7 - 9]. Diferenţa principală este faptul că sistemele distribuite funcţionează în medii deterministice, stabile (computere de ultimă generaţie, sisteme de calcul digitale), pe când sistemele SPRAY se aşteaptă să funcţioneze în condiţii reale, complet aleatorii. Calculatoarele SPRAY trebuie să fie în stare să se conformeze unui mediu specific care prezintă următoarele proprietăţi:

Numărul de componente hardware / software implicate într-un astfel de sistem este extrem de mare şi imposibil de controlat. De aceea este imposibil de a prestabili o configuraţie pentru componentele implicate precum şi de a impune un comportament acestor componente.

Dispozitivele care formează un sistem SPRAY fac parte dintr-o reţea a cărei structură este complet aleatoare datorită procesului de instalare (aerosoli sau vopsire) şi care este extrem de dinamică (structura acestei reţele se poate modifica în timp datorită mediului în care au fost depuse, datorită simplei deplasări a componentelor sistemului pe care au fost depuse).

Proprietăţile descrise mai sus determină crearea unor sisteme de microcomputere capabile de auto-organizare, auto-ajustare într-un mod nepredictibil şi nesupervizat, adaptându-se la structura existentă a reţelei precum şi dinamicităţii mediului.

Sistemele SPRAY la scară medie

Computerele SPRAY există deja la dimensiuni medii. În mod curent, un utilizator poartă asupra lui un număr de sisteme de calcul: telefon celular, laptop etc. Locuinţele încep să conţină echipamente bazate pe microprocesoare: telefoane fără fir, televizoare, unităţi DVD etc. În momentul de faţă, cu ajutorul tehnologiilor existente, se pot crea următoarele tipuri de reţele inteligente:

Reţele personale: reţele stabilite pe baza conexiunii Bluetooth între telefonul celular şi PDA-ul personal, sau cu computerul de bord al unei maşini;



Reţele ad-hoc: formate între laptopurile sau dispozitivele PDA ale unei echipe aflate pe teren pentru a îmbunătăţi comunicaţia în interiorul echipei aflată în mediul real, în spaţii deschise;

Reţele tip „mobilă”: dispozitive electro-casnice conectate la Internet, având posibilitatea de a se interconecta şi aşi coordona activităţile;

Chiar dacă reţelele descrise mai sus funcţionează la o altă scară decât computerele SPRAY tradiţionale, aceste reţele sunt supuse aceloraşi probleme descrise în paragrafele precedente: reţelele depind de poziţia dispozitivelor care este aleatoare, nu se poate garanta existenţa dispozitivelor (acestea sunt efemere).

Sistemele SPRAY la scară globală

Metodele tradiţionale de control şi configurare a reţelelor distribuite nu pot fi aplicate în reţele distribuite care cresc cu adevărat într-un mod descentralizat cum este cazul Internetului sau a reţelei World Wide Web. Deşi scara este cu câteva ordine de mărime mai mare decât în cazul computerelor SPRAY, reţelele globale sunt similare cu computerele SPRAY în primul rând datorită numărului mare de entităţi componente, dar şi datorită topologiei dinamice a reţelei (informaţiile, serviciile sunt mobile, sunt replicate [9], adresele lor se pot schimba). Necesitatea de a accesa informaţii şi servicii mobile la nivelul unei reţele de tipul Internetului a dus la crearea de modele şi protocoale de comunicaţie specifice reţelelor Peer-To-Peer (P2P). Astfel, în locul alegerii unui control extrem de centralizat şi a unei supravegheri stricte a componentelor software şi a interacţiunilor dintre acestea (o acţiune practic imposibilă datorită nivelului de dinamicitate) se preferă ideea unei reţele de suprapunere (overlay network) care să prezinte posibilităţi de auto-organizare, care să prezinte un comportament emergent suficient de dezvoltat pentru a determina funcţionarea corectă a reţelei.

1.5.1 Dezvoltarea de aplicaţii distribuite pentru sisteme SPRAY

Dezvoltarea de aplicaţii distribuite pentru computere SPRAY presupune proiectarea unui comportament care derivă din cooperarea unui număr mare de componente, nefiabile, interconectate în modele necunoscute, dinamice. Acest fapt necesită dezvoltarea de algoritmi specifici care să permită reţelelor de computere SPRAY să se auto-organizeze pentru a atinge un scop comun fără o supraveghere a-priori sau un control centralizat. Mecanismul de nivel inferior folosit pentru a crea proprietăţile de auto-organizare este practic acelaşi, indiferent de scara folosită ( sisteme SPRAY sau reţele P2P):

descoperirea dinamică de resurse (parteneri, servicii, informaţii) prin broadcast (dacă reţeaua pune la dispoziţie servicii de broadcast, în caz contrar prin multicast sau unicast, în funcţie de serviciile oferite de reţea [9]);

localizare şi navigare [9] (fie într-un spaţiu fizic pentru sistemele SPRAY sau reţele de senzori, fie într-un spaţiu digital pentru reţelele P2P).



Proiectarea aplicaţiilor pentru sistemele SPRAY presupune folosirea unor tehnici speciale care ţin cont de caracterul profund emergent al acestor sisteme. Este extrem de important ca mecanismele implicate să fie cât mai simple, pentru ca sistemul să prezinte comportament emergent eficient, fiabil şi robust. Astfel de mecanisme simple, printre care se numără mecanismele de broadcast, localizare, replicare, navigare, împreună cu interacţiunile locale, necesare pentru a determina generarea tiparelor de comportament emergent, pot conduce la faptul ca anumite părţi din sistem sau chiar întreg sistemul de tip SPRAY să ajungă la o stare globală coerentă. Mecanismele simple amintite mai sus (broadcast, localizare, replicare etc.) conduc la apariţia unor algoritmi distribuiţi, simpli, eficienţi, care prezintă tipare de comportament emergent dar care sunt diferiţi în mod esenţial de algoritmii distribuiţi tradiţionali. Algoritmii emergenţi elimină necesitatea urmăririi principiilor de micro-management aplicate la algoritmii distribuiţi tradiţionali: ordonarea evenimentelor, sincronizarea proceselor, replicare, structura reţelelor [9]. Algoritmii emergenţi se bazează pe faptul că deşi sistemele SPRAY sunt non-deterministice, totuşi se poate demonstra o convergenţă către o stare generală stabilă în ciuda discrepanţelor de la nivel de micro-management. În funcţie de modalitatea de analiză şi specificare a aplicaţiilor pentru sistemele SPRAY (top-down sau bottom-up), se disting două tehnici de proiectare a acestor aplicaţii: proiectarea directă şi proiectarea inversă.

Proiectarea directă a aplicaţiilor pentru sistemele cu auto-organizare

Un exemplu simplu de proiectare directă a aplicaţiilor distribuite pentru sisteme de tip SPRAY este auto-localizarea distribuită. Un număr aleator de particule distribuite într-un mediu pot să îşi determine poziţia geografică pornind de la un set de particule baliză (determinate prin algoritmi de selecţie distribuiţi) şi apoi în mod recursiv să îşi determine poziţia prin triangulaţie referitor la poziţia particulelor vecine până se ajunge la o stare globală stabilă în care se cunosc poziţiile tuturor particulelor.

Figura 3: Sistem de particule cu poziţionare aleatoare



Exemplul următor se referă la poziţionarea spaţială a particulelor mobile în forme bine stabilite. Având un număr de particule distribuite într-un mediu (Figura 3), este posibilă proiectarea unui algoritm distribuit care, prin deplasarea locală a particulelor, să conducă la organizarea sistemului în forme dorite. Un algoritm simplu de alegere a unui lider care se poate organiza într-un centru de greutate a particulelor. Acest centru de greutate poate propaga apoi în toată reţeaua un „câmp gravitaţional” care să atragă particulele către acest centru (Figura 4), organizând întreg sistemul într-o structură circulară (Figura 5).

Figura 4: Sistem de particule în stadii incipiente de poziţionare

Figura 5: Sistem de particule poziţionare în formă circulară

Proiectarea directă a aplicaţiilor distribuite pentru sistemele de tip SPRAY este strâns legată de existenţa a-priori a acestor sisteme SPRAY, pentru a identifica în mod corect tiparele de comporament emergent. Acest mod de lucru nu se poate aplica decât unui număr limitat de aplicaţii. Datorită complexităţii comportamentelor emergente şi datorită caracteristicilor non-deterministice ale acestor sisteme, numărul



de tipare de comportament emergent care pot fi puse în aplicare este extrem de mic, iar aceste comportamente emergente sunt simple. Totodată necesită cunoştinţe a-priori despre configuraţiile posibile ale sistemului care îi limitează capacitatea de adaptabilitate. Astfel, dacă pentru sistemul din [7, 8] se propune o formă de poziţionare nesimetrică, atunci pentru funcţionarea corectă a sistemului SPRAY ar fi nevoie de un algoritm extrem de complex care să fie executat de toate particulele, sau ar fi nevoie ca anumite particule să deţină informaţii a-priori despre poziţionarea acestora.

Proiectarea inversă pentru sisteme cu auto-organizare

Proiectarea inversă pentru sistemele cu auto-organizare propune crearea de comportamente emergente prin recrearea condiţiilor necesare dezvoltării unor astfel de comportamente. În aceste cazuri, proiectanţii nu au nici un fel de control asupra dezvoltării ulterioare a sistemului, asupra evoluţiei sale viitoare datorită complexităţii comportamentelor emergente precum şi datorită non-liniarităţii şi non-determinismului pe care le implică. Proiectaţii sistemelor SPRAY se bazează în aceste condiţii doar pe presupuneri de ordin probabilistic asupra tendinţelor de evoluţie ale sistemelor respective. Simulările sunt elementul de bază al unor astfel de concepte de proiectare. Datorită comportamentului non-deterministic al sistemelor SPRAY, care este lipsit de suportul matematic pentru determinarea cu acurateţe a tendinţelor de evoluţie, simularea este singura posibilitate prin care se poate urmări într-o oarecare măsură evoluţia sistemului. Astfel, faza de modelare în sistemele proiectate prin această metodă este înlocuită cu cicluri consecutive de simulare şi rafinare a sistemului până când acesta îndeplineşte condiţiile cerute. Pentru sistemele distribuite artificiale au fost determinaţi o serie de algoritmi creaţi pe baza studiului intens al unor fenomene naturale emergente ( algoritmi de gossip – bârfă [9] folosiţi cu succes în sistemele distribuite au fost preluaţi din studiul coloniilor de furnici). Totodată acest tip de modelare a sistemelor SPRAY este util pentru determinarea poziţionării în structuri nesimetrice. Poziţionarea în structuri nesimetrice a fost realizată prin studiul poziţionării celulelor în decursul procesului de morfogeneză. Astfel, spre deosebire de procesul descris în paragraful anterior, în procesul de morfogeneză apar anumite forţe doar dacă celulele implicat depăşesc un număr dat. Conform acestui principiu nu se mai alege un centru de greutate în jurul căruia se pot grupa entităţile, se aleg anumite centre de poziţionare bazate pe densitatea entităţilor. În acest mod se pot crea forme nesimetrice (Figura 6).



Figura 6: Model nesimetric de poziţionare a particulelor

Tipul de proiectare prezentat are următoarele avantaje: Se poate baza pe cercetările din alte domenii pentru a explora o serie de

comportamente emergente. Odată ce au fost stabilite condiţiile pentru determinarea comportamentului

emergent, programarea sistemelor de tip SPRAY este simplă, fiind redusă la enunţul unor reguli locale după care este obligat sistemul să funcţioneze.

Acest tip de proiectare prezintă şi o serie de dezavantaje: Principiile non-deterministice care fac să funcţioneze comportamentele

emergente sunt extrem de greu de controlat. Sistemul poate ajunge la o serie de stări finite, globale extrem de complicat

de dedus. Uneori este necesar adoptarea unei forme nesimetrice specifice şi nu a unei

forme nesimetrice care a apărut ca rezultat al comportamentului emergent creat pentru sistemul respectiv.

Controlul comportamentului emergent

Pentru proiectarea unui sistem SPRAY cu adevărat eficient, robust şi fiabil este necesară găsirea unui model de proiectare care să îmbine ambele modele prezentate în paragrafele anterioare. Astfel se încearcă proiectare de tip inversă până la un punct de unde se foloseşte proiectarea directă. Introducerea unui control rezervat proiectării directe trebuie să fie făcută într-o măsură corespunzătoare astfel încât să nu interfereze cu condiţiile prestabilite pentru declanşarea comportamentului emergent. Pentru diferitele aplicaţii care se pot crea pe baza comportamentelor emergente este imposibil de a se proiecta un model general, o reţetă universală care să permită cunoaşterea a-priori a condiţiilor de declanşare a comportamentului emergent pentru o aplicaţie de uz general. Principiile de proiectare prezentate în paragrafele anterioare pot fi aplicate cu succes la număr mare de aplicaţii. Aceste aplicaţii trebuie să fie însă extrem de specifice pentru a se putea identifica cu exactitate condiţiile necesare declanşării comportamentului emergent. De asemenea, pentru a simplifica proiectarea unui astfel



de sistem este necesară identificarea domeniului din care se poate prelua descrierea comportamentului emergent, posibilităţile de adaptare la aplicaţia curentă.

1.6 Smart DUST

Scopul proiectului Smart Dust este de a crea o platformă autonomă, de scară milimetrică, pentru comunicaţie, cu avansate posibilităţi senzoriale pentru reţele de senzori masive distribuite [7, 8]. Acest dispozitiv va fi de dimensiunile unei granule de nisip şi va conţine senzori, abilităţi computaţionale, comunicaţie bidirecţională fără fir şi o sursă de energie. Se urmăreşte ca acest dispozitiv să fie suficient de ieftin pentru a putea fi folosit în reţele de senzori de ordinul miilor de noduri de reţea. Proiectul Smart Dust este sponsorizat de agenţia americană DARPA/MTO/MEMS a cărei scop principal este de a fuziona tehnologii de senzori, actuatori şi putere computaţională în sisteme realizate cu tehnologii de ultimă oră care să permită noi nivele de percepţie, control şi performanţă sistemelor de armament şi mediilor de război ([8]). Acest tip de dispozitive este preconizat a fi folosit la:

Monitorizare seisomologică şi meteo în cadrul misiunilor robotizate de pe planeta Marte;

Monitorizarea mediului intern al vehiculelor spaţiale; Reţele de comunicaţie terestre sau spaţiale; Senzori chimici / biologici; Monitorizarea stocurilor de armament; Reţele de senzori folosite în domeniul apărării; Controlul inventarului; Monitorizarea calităţii produselor; Tastaturi virtuale;

1.6.1 Descrierea modului de operare al senzorului Smart Dust

Senzorul Smart Dust este controlat de către un microcontroler care supraveghează consumul de energie al diferitelor componente pentru a conserva energia.



Figura 7: Schema bloc a unui senzor Smart Dust (Sursa [8])

În mod periodic, se colectează date de la senzori care măsoară un stimul fizic sau chimic (temperatură, lumina ambientală, vibraţii, acceleraţii, presiunea aerului, prezenţa anumitor substanţe chimice ), procesează informaţiile şi le stochează în memorie. Ocazional, senzorul Smart Dust porneşte receptorul optic pentru a identifica încercările de comunicare din partea senzorilor vecini. Această comunicaţie poate include încărcarea de noi programe din partea unui dispecer sau mesaje din partea altor senzori Smart Dust. Ca răspuns la aceste mesaje, sau ca reacţie la anumite informaţii senzorul Smart Dust foloseşte un retroreflector cub (corner cube retroreflector) sau o diodă laser pentru a transmite date staţiei de bază sau altor senzori.

Figura 8: Retroreflexia în colţul cubului (Sursa [8])

Constrângerea primară care apare la proiectarea senzorilor Smart Dust este volumul senzorilor ceea ce ridică probleme în ceea ce priveşte consumul de energie



deoarece nu este loc pentru includerea de baterii puternice sau celule solare. Astfel, senzorii Smart Dust trebuie să fie extrem de eficienţi în consumul energiei. În majoritatea timpului, componentele senzorului lucrează în moduri de lucru cu consum redus, sau sunt deconectate de la alimentarea generală. Singurele dispozitive interne active permanent sunt reprezentate de un ceas şi o serie de contoare. Atunci când expiră un astfel de contor, senzorul îşi porneşte o componentă, execută anumite operaţii asupra acestei componente, după care o deconectează sau o trece într-un mod de lucru cu consum redus. Acest set de contoare controlează direct senzorii care citesc stimuli exteriori. Atunci când un contor din acest set expiră, alimentează senzorul corespunzător, citeşte un eşantion pe care îl converteşte digital. Dacă informaţia îndeplineşte anumite criterii de importanţă aceasta fie este în memoria SRAM cu care este dotat senzorul, fie, dacă trebuie executate anumite operaţii, atunci se scoate microcontroler din modul de lucru cu consum redus printr-o întrerupere, i se transmite informaţia dorită împreună cu anumite informaţii de control şi se cedează controlul sistemului acestuia. Când operaţiile necesare au fost terminate toate dispozitivele sunt fie nu mai sunt alimentate, fie sunt introduse în moduri de lucru cu consum redus. Un set suplimentar de contoare controlează receptorul laser. Atunci când un astfel de contor expiră, porneşte receptorul care aşteaptă recepţionarea unei pachet de date. Dacă nu primeşte nici un pachet, după o perioadă prestabilită de timp, receptorul este trecut în modul de lucru cu consum redus. Senzorul laser poate primi o serie de tipuri de pachete, inclusiv un tip special de pachete care conţin segmente de cod pentru a fi stocate în memoria de program. În acest se poate modifica comportamentul senzorului Smart Dust de la distanţă. Pachete pot conţine mesaje de la alţi senzori sau de la o staţie de bază. Când un astfel de mesaj este primit, se porneşte microcontroler pentru a interpreta conţinutul mesajului. Pentru transmisie se foloseşte tehnica retroreflexiei prin care se transmite informaţii prin modificarea înclinării unor oglinzi care formează laturile unui cub şi care reflectă raza laser transmisă de staţia de bază. Această tehnologie este extrem de eficientă din punctul de vedere al consumului de energie deoarece nu se generează radiaţie luminoasă cum este în cazul folosirii unei diode laser. O altă metodă de transmisie este folosirea combinată a unei diode laser şi a unui set de oglinzi (Figura 8) pentru a putea transmite informaţia în orice direcţie, pentru a comunica şi cu alţi senzori laser.

Figura 9: Sistem de transmisie cu diodă laser ( Sursa [7])



1.6.2 Generaţii de senzori Smart Dust

În continuare se prezintă câteva generaţii de senzori Smart Dust.

Clever Dust

Această generaţie este realizată cu ajutorul unui microcontroler cu consum scăzut care a fost proiectat special pentru senzorii realizaţi în tehnologia Smart Dust:

Consumă în medie 12pJ / instrucţie Este realizat în tehnologie CMOS de 0.25 µm.

Golem Dust cu Deputy Dust

Un senzor din această generaţie de senzori Smart Dust are următoarele proprietăţi: Funcţionează cu energie solară; Comunicaţie bidirecţională; Capacităţi senzoriale pentru acceleraţie şi lumină ambientală; Tehnologie CMOS ASIC; 6.6 mm3 volum total

Figura 10: Senzor Smart Dust de generaţie Golem Dust (Sursa [7])

Golem Dust

Un senzor din această generaţie de senzori Smart Dust are următoarele proprietăţi: Funcţionează cu energie solară; Comunicaţie bidirecţională; Capacităţi senzoriale pentru acceleraţie şi lumină ambientală; Tehnologie CMOS ASIC; 11.7 mm3 volum circumscris; ~4.8 mm3 volum total;


Comportam

16

Daft Dust

U

1.7 Teh

Vvo12coco viA

ment emergen

F

t

Un senzor din Funcţ Comu Folos Tehno 63 mm

hnologiile

Viitoarele mior baza pe a2]. Misiuniompletate colaborează î

Este extiitoare să f

Aplicarea con

nt în medii co

Figura 11: D

n această geţionează cu unicaţie bidsit în principologie CMOm3 volum c

Figura 1

e ”roi” al

isiuni spaţiaaplicarea tipile tradiţioncu concepteîn moduri sptrem de impfie de pe dnceptelor d

olaborative r

Dimensiuni

eneraţie de energie sol

direcţională;pal ca şi nodOS ASIC; circumscris;

12: Senzor d

le NASA

ale ale NASparelor de cnale bazatee care implpecifice roiuportant din deplin auto

de comporta

obotizate

ile unui senz

senzori Smlară; ; d de comun

;

de generaţie

A

SA vor implomportamee pe nave lică nave durilor de inspunctul de

onome, să ament emerg

zor Smart D

art Dust are

nicaţie;

e Daft Dust

lica noi tehnent emergen

spaţiale dde dimensiusecte din navedere al Ndeţină un

gent în aces

Răzvan

Comport

Dust (Sursa

e următoare

(Sursa [7])

nologii de ent specifice dde mari dimuni reduse catură. NASA ca mgrad mărit

ste misiuni

n-Dorel CIOA

tament colab

[7])

le proprietă

)

explorare cade tip ”roi”mensiuni vcare operea

misiunile spt de inteligpermite lan

ARGĂ

borativ

ăţi:

are se [10 -

vor fi ază şi

paţiale genţă. nsarea


de echipamente de foarte mici dimensiuni, specifice explorării spaţiului (spre deosebire de marile nave spaţiale a căror folosire pentru explorare se poate dovedi nepractică), de cost redus, cu puţină inteligenţă încorporată dar care pot realiza sarcina cerută cu o mai mare eficienţă. Aplicarea conceptelor de comportament emergent este necesară în acest caz pentru mărirea gradului de autonomie al echipamentelor în condiţiile in care timpul de călătorie al semnalului radio până la Pământ este de peste 30 minute. Odată cu mărirea gradului de autonomie al echipamentelor de explorare, luarea deciziilor se poate face mai curând in situ decât la sol.

1.7.1 Misiunile ANTS

”Autonomous Nano Technology Swarm” (ANTS) reprezintă o colaborare dintre Goddard Space Flight Center şi Langley Research Center destinată dezvoltării unei arhitecturi emergente de misiuni spaţiale.

SARA : The Saturn Autonomous Ring Array

Misiunea SARA va lansa 1000 de nave spaţiale de clasă pico organizate sub forma a 10 roiuri, fiecare conţinând instrumente specializate care vor executa in situ explorarea inelelor lui Saturn pentru a determina compoziţia acestora precum şi modul lor de formare. Această misiune va necesita structuri auto-configurabile pentru propulsie nucleară şi control, pentru navigarea prin inelele lui Saturn şi detectarea / evitarea coliziunilor.

PAM: Prospective Asteroid Mission

Misiunea PAM va lansa un roi de nave spaţiale de clasă pico (cu o greutate de aproximativ de 1 Kg) care vor explora centura de asteroizi căutând asteroizi cu anumite caracteristici.



Figura 13: Misiunea PAM (Sursa [11, 12])

Figura 13 prezintă o privire generală a misiunii PAM. În această misiune, o navă spaţială de transport va fi lansată de pe Pământ spre un punct din spaţiu unde forţele gravitaţionale care acţionează asupra obiectelor spaţiale de clasă pico sunt neglijabile (acesta este denumit punct Lagrange). Din acest punct se vor lansa cele 1000 de pico-nave stelare asamblate în cursul zborului. Se estimează ca peste 70% din aceste nave să fie pierdute în timpul misiunii ca urmare a coliziunii cu asteroizii sau între ele. Navele spaţiale vor avea la dispoziţie doar vele solare care le vor reduce considerabil mobilitatea, ceea ce implică faptul că folosirea unor algoritmi complicaţi de detectare / evitare de obstacole este nepractică de vreme ce nava nu va fi în stare ca să le ocolească în timp util. Din cauza dimensiunilor reduse, fiecare navă spaţială va fi dotată doar cu un singur instrument specializat de măsură (magnetometru, spectrometru etc.). Aproximativ 80% din toate navele vor fi configurate să lucreze ca şi simpli colectori de date. O parte din navele rămase vor fi folosite ca şi lideri care vor şti reguli de alegere a asteroizilor precum şi datele de care misiunea are nevoie. Al treilea tip de nave vor fi mesagerii care vor coordona comunicaţia dintre lideri şi muncitori precum şi comunicaţia cu staţiile terestre. Cele 1000 de nave se pot împărţi apoi în sub-roiuri conduse de un lider care va coordona muncitorii care, la rândul lor se vor folosi de instrumentele specializate din dotare pentru a investiga tipurile de asteroizi. Pe baza datelor conţinute, liderul va determina tipul de asteroid necesar spre a fi investigat, muncitorii vor încerca să găsească un asteroid de tipul cerut prin investigaţii aleatoare ale asteroizilor din zona în care au fost lansaţi.




1.8 Referinţe bibliografice

[1] K-TEAM K-Robots: Khepera I, II, III, Koala, I, II, online: http://www.k-team.com/kteam/home.php?rub=0&site=1&version=EN;

[2] Takuya Kashima, Shunsuke Saruwatari, Hiroyuki Morikawa, Tomonori Aoyama, „A Bind Control Model For Real-space Programming in Ubiquitous Computing Environment”, The Sixth International Conference on Ubiquitous Computing, Ubicomp 2004, 7-10 September, 2004;

[3] Richard John Anthony, Natural Inspiration for Self-Adaptive Systems; Database and Expert Systems Applications, 2004. Proceedings. 15th International Workshop on 30 Aug.-3 Sept. 2004 Page(s):732 – 736;

[4] Marco Dorigo, Luca Maria Gambardella; Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, Vol.1, No.1, 1997;

[5] Marco Dorigo, Luca Maria Gambardella; Ant colonies for the traveling salesman problem, BioSystems, Elsevier, 1997;

[6] Smart Dust, Autonomous sensing and communication in a cubic millimeter; on-line: http://robotics.eecs.berkeley.edu/~pister/SmartDust/;

[7] Smart Dust Project, online: http://www-bsac.eecs.berkeley.edu/archive/users/warneke-brett/SmartDust/;

[8] DARPA / MTO / MEMS, DARPA Agency, online: http://www.darpa.mil/mto/mems/

[9] Andrew S. Tanenbaum & Maarten van Steen. Distributed Systems: Principles and Paradigms; Prentice Hall 2002;

[10] W. Truszkowski, M. Hinchey, J. Rash, and C. Rouff; NASA’s swarm missions: The challenge of building autonomous software. IEEE IT Professional, 6(5):47–52, September/October 2004;

[11] W. F. Truszkowski, M. G. Hinchey, J. L. Rash, and C. A.Rouff. Autonomous and autonomic systems: A paradigm for future space exploration missions. IEEE Transactions on Systems, Man and Cybernetics, Part C, 2006 (to appear).

[12] M. Hinchey, C. Rouff, J. Rash, Requirements of an Integrated Formal Method for Intelligent Swarms, FMICS’05, September 5–6, 2005, Lisbon, Portugal, Page(s) 125 – 133;

http://www.k-team.com/kteam/home.php?rub=0&site=1&version=ENhttp://www.k-team.com/kteam/home.php?rub=0&site=1&version=ENhttp://robotics.eecs.berkeley.edu/%7Epister/SmartDust/http://www-bsac.eecs.berkeley.edu/archive/users/warneke-brett/SmartDust/http://www-bsac.eecs.berkeley.edu/archive/users/warneke-brett/SmartDust/http://www.darpa.mil/mto/mems/

1 Studiul unor metodologii existente in literatura de specialitate aplicabile in domeniul mediilor asociative1.1 Introducere1.2 K-TEAM K-Robots1.3 ANTH – ANtennary THings1.4 Sisteme distribuite de comunicaţie bazate pe feromoni1.5 Sisteme SPRAY cu auto-organizareSistemele SPAY la scară microscopicăSistemele SPRAY la scară medieSistemele SPRAY la scară globală1.5.1 Dezvoltarea de aplicaţii distribuite pentru sisteme SPRAYProiectarea directă a aplicaţiilor pentru sistemele cu auto-organizareProiectarea inversă pentru sisteme cu auto-organizareControlul comportamentului emergent

1.6 Smart DUST1.6.1 Descrierea modului de operare al senzorului Smart Dust1.6.2 Generaţii de senzori Smart DustClever DustGolem Dust cu Deputy DustGolem DustDaft Dust

1.7 Tehnologiile ”roi” ale NASA1.7.1 Misiunile ANTSSARA : The Saturn Autonomous Ring ArrayPAM: Prospective Asteroid Mission

1.8 Referinţe bibliografice

1 Studiul unor metodologii existente in literatura de ...dsplabs.cs.upt.ro › grants › melissevs...

Documents

Transcript of 1 Studiul unor metodologii existente in literatura de ...dsplabs.cs.upt.ro › grants › melissevs...