1 definirea unor metrici pentru masurarea si evaluarea...

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

Comportament colaborativ 1

1 Definirea unor metrici pentru masurarea si evaluarea performantelor modelelor obtinute

1.1 Studiu de caz: punerea în aplicare a mişcării inspirate din bancul de peşti folosind roboţi lego NXT

O aplicaţie care foloseşte algoritmul de mişcare prezentat în secţiunea anterioară a

fost implementat pe un colectiv roboric compus din 6 roboţi LEGO Mindstorm NXT

[1, 2]. Roboţii LEGO Mindstorm NXT au fost programaţi folosind limbajul de

programare RobotC [13].

Un robot NXT este format dintr-o „cărămidă inteligentă” (Fig. 1 – (1) ) care

controlează o serie de acuatori şi senzori: (2) senzorul de atingere, (3) microfon, (4)

senzor de lumină, (5) senzor ultrasonic, (6) motoare DC. Cărămida inteligentă

prezintă de asemenea un dispozitiv de comunicare avansat bazat pe protocol

Bluetooth.

Fig. 1: Cărămida inteligentă Lego Mindstorm NXT, acuatori şi senzori [1]

Cărămida inteligentă NXT se caracterizează printr-un procesor principal ARM7

cu baza Atmel [3] care poate fi programat folosind RobotC, care este versiunea

limbajului C pentru NXT. Aplicaţia software, scrisă în RobotC [4], care a fost

încărcată pe cărămida inteligentă, are diagrama de stare arătată în Figura 2.

Un computer cu conexiune Bluetooth este folosit ca gateway / router pentru

comunicare dintre roboţi; computerul este transparent pentru toţi roboţii, astfel încât

aceştia nu sunt conştienţi de prezenţa lor (calculatorul lucrează la un nivel inferior al

unui protocol de comunicaţie stratificat).

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

2 Comportament colaborativ

Fig. 2: Diagrama de stare pentru aplicarea implementării algoritmului de mişcare a

bancului de peşti

Folosind piese LEGO şi cărămida inteligentă am creat 6 roboţi bazaţi slab pe

Castor Bot [5] (Fig. 3).

Fig. 3: Castor Bot [15]



Comportamentul sistemului de 6 roboţi a fost investigat pe baza unui număr de

scenarii create pentru a stresa algoritmul de mişcare. Pe baza experimentelor a fost

calculată o rată de succes şi această rată este caracterizată de Timpul necesar atingerii

ţelului. Timpul necesar atingerii scopului este suma dintre numărul paşilor grupaţi şi

numărul paşilor de mişcare paralelă.

Experimentele au inclus scenarii pentru a testa următoarele situaţii:

Deplasarea către ţintă a unui număr de roboţi, care nu au fost în raza vizuală a

grupului cel mai mare;

Deplasarea către centrul unui grup, a unui robot care nu a fost în raza vizuală

a grupului

Utilizarea a diferite stări iniţiale pentru algoritm: folosind unghiuri de 50˚ şi

60˚ pentru plasarea iniţială a roboţilor;

Mişcarea unui grup de 3, 4, 5 sau 6 roboţi pentru atingerea scopului;

Când se utilizează un unghi de 50˚ între direcţiile iniţiale a roboţilor, ei se împart

în 2 subgrupe egale care se mişcă independent pentru atingerea obiectivului, aşa cum

este arătat în Fig. 4.

Fig. 4: Mişcarea unui grup de 6 roboţi plasaţi inţial sub un unghi de 50˚

Experimentele folosind 3, 4, 5 sau 6 roboţi au fost efectuate cu scopul de a testa

prezenţa şi efectuarea modelelor de comportament emergent. Performanţa

algoritmului în acest caz este prezentat în Tabelul. 1.

Aşa cum se observă în Fig. 5, timpul necesar atingerii scopului scade pe măsură

ce numărul roboţilor creşte, ceea ce demonstrează proprietăţile emergente ale

sistemului: cu cât sunt mai multe entităţi, cu atât scopul este atins mai repede.

Tabelul 1. Performanţa algoritmului atunci când sunt utilizaţi un număr variat de

roboţi



Nr. de

roboţi

Gruparea

[numărul de

paşi]

Mişcarea

paralelă

[numărul de

paşi]

Atingerea scopului

[numărul de paşi]

Timpul necesar atingerii

scopului [%]

3 3 65 68 100

4 6 60 66 97,1

5 7 58 65 95,6

6 6 51 57 83,8

Fig. 5: Timpul necesar atingerii scopului la folosirea unui număr variat de roboţi

1.2 Studiu de caz: implementarea algoritmului emergent pentru explorare folosind roboţi lego NXT

1.2.1 Punerea în aplicare a algoritmului

Aplicaţia soft firmware, scrisă în RobotC [3], care a fost încărcată pe cărămida

inteligentă, are diagrama de stare prezentată în Fig. 6.

Algoritmul soft este bazat pe comportamentul furnicii de strângere a hranei. Când un

robot găseşte o resursă utilă, anunţă toţi roboţii despre poziţia sursei recente de hrană.

După aceea, începe explorarea drumului spre poziţia ACASĂ cu scopul de a găsi

calea cea mai scurtă posibilă pentru transportarea resursei. După alegerea căii care va

fi urmată pentru transportare, robotul îi anunţă pe toţi trimitându-le detaliile despre

drumul pe care trebuie să-l urmeze pentru a duce resursa la destinaţie. Transportul

continuă până când resursa este terminată. Roboţii vor continua după aceea căutarea

a noi resurse.

Câteva dintre caracteristicile principale ale aplicaţiei sunt: control descentralizat,

autonomie, omogenitate şi percepţie locală a mediului:

La fel ca şi la comportamentul coloniei de furnici, aici nu este un controlor

central. Fiecare robot are abilitatea de a decide individual ţinând cont de

informaţia adunată din mediu şi de asemenea de datele primite de la ceilalţi



roboţi. Controlul descentralizat permite o mai bună fiabilitate şi flexibilitate

sistemului.

Roboţii au abilitatea de a decide ei însăşi. Acesta le permite să răspundă

rapid la schimbările de mediu. Nu este necesar nici un factor uman care să

controleze roboţii spre soluţie.

Toţi roboţii au aceeaşi arhitectură hard la fel ca şi acelaşi rol în sistem.

Fiecare dintre ei este capabil să detecteze obieacte, să se mişte aleator sau de-

alungul unei direcţii specifice, să găsească calea cea mai scurtă, să transporte

o resursă, să comunice date pe Bluetooth, să depoziteze date în memoria lor

locală.

Nu există o informaţie iniţială furnizată roboţiilor cu privire la mediu şi la

resurse. Ei capătă date de-alungul explorării mediului. Împărtăşind informaţia

cu alţi roboţi, ei au acces la o perspectivă mai largă asupra mediului.

Fig. 6: Diagrama algoritmului de căutare a granei

Comunicarea dintre roboţi se bazează pe standardul Bluetooth, folosind un protocol

special. Situaţiile ce necesită transmisia de informaţie între roboţi sunt următoarele:

găsirea unei resurse, găsirea unui obstacol, găsirea celui mai bun drum pentru

transportarea resursei la locaţia acasă, anunţarea terminării resursei.

Fiecare robot are o poziţie în mediu care este înregistrată şi actualizată pe

parcursul deplasării. Poziţia obstacolelor găsite în timpul căutării resurselor sunt



comunicate celorlalţi roboţi şi sunt depozitate în harta internă a fiecărui robot.

Această hartă va fi folosită în scopul evitării zonelor „periculoase” fără ca senzorii să

le scaneze.

Poziţionarea sistemului se bazează pe două elemente: direcţia curentă şi poziţia

(x, y). Am definit 8 direcţii posibile: Nord, Nord-Est, Sud-Est, Sud, Sud-Vest, Vest şi

Nord-Vest.

Iniţial, toţi roboţii se mişcă aleator, căutând resurse şi ocolind obstacole.

Detectarea obiectului este un proces format din 2 paşi: detectarea sonoră a unui

obiect urmată de o detectare a culorii cu senzorul de lumină. Al doilea pas permite

distingerea dintre obstacole şi resurse. Înainte de deplasarea la o nouă poziţie, robotul

va scana pentru detectarea obiectelor, 45 de grade la stânga şi la dreapta în jurul lui

(aşa cum se arată în Fig. 7). Deplasarea spre o nouă direcţie se bazează pe poziţia

actuală şi direcţia robotului.

Fig. 7. Scanarea după resurse

Robotul care a găsit o resursă va fi cel care va căuta cea mai scurtă cale în

scopul de a o transporta în poziţia ACASĂ. La fiecare pas, luând în considerare

coordonatele poziţiei curente şi coordonatele destinaţiei, robotul va calcula direcţia

care îl conduce la calea cea mai scurtă. El va încerca consecvent să se deplaseze în

direcţia cea mai apropiată de cea optimă. Dacă cea mai bună direcţie este liberă,

robotul se va deplasa până când detectează un obsatcol sau până când ajunge la

destinaţie. Dacă un obstacol este găsit în calea sa, robotul va evita obstacolul

schimbându-şi direcţia. După aceasta, va încerca să revină la direcţia cea mai bună,

cea corespunzătoare căii cele mai scurte de la poziţia curentă la destinaţie.

Algoritmul este reprezentat grafic în Fig. 8.



Fig. 8. Diagrama corespunzătoare punerii în aplicare a căutării cele mai bune căi

pentru transportarea resursei

La fiecare pas din procesul găsirii cele mai scurte căi de la poziţia resursei la

poziţia ACASĂ, robotul va salva direcţiile urmate într-o arie specială a drumului.

Ajungând la destinaţie, el va trimite calea prin Bluetooth la toţi ceilalţi roboţi.

Transportarea resurselor se realizează urmărind calea salvată atâta timp cât este

necesar. Robotul care descoperă că resursa este epuizată, va anunţa toţi ceilalţi roboţi

trimiţând un mesaj particular Bluetooth. După ce resursa este terminată, căutarea

începe din nou.

Folosind piese LEGO şi cărămizi inteligente am creat 6 roboţi prezentaţi în Fig.

9. Toţi roboţii au aceleaşi caracteristici specifice: 30 cm lungime, 18 cm lăţime, 3

motoare, 2 senzori şi comportamente identice.

Robotul LEGO NXT prezintă un mecanism de apucare care îi permite să

manipuleze resursa pentru transportare, şi capacităţi senzoriale variate cum este

sonarul pentru detectarea obstacolelor şi senzor de lumină pentru determinarea



tipului de ostacol. Pentru scopul acestui articol, au fost împrăştiate de-alungul unei

arii date, mingi roşii şi albastre; orice minge colorată albastru este considerată a fi un

obstacol normal, în timp ce orice minge colorată roşu este considerată a fi o resursă

utilă.

Fig. 9. Robot LEGO

1.2.2 Rezultate experimentale

O serie de experimente au fost realizate cu scopul de a evolua performanţa

algoritmului de explorare. Pentru primele noastre experimente am folosit doar 3

roboţi în scopul urmăririi mai bune şi măsurării comportamentelor lor de-alungul

testelor. Topologia folosită pentru teste a fost aleasă aleator. Valorile care au fost

înregistrate pentru experimente sunt: timpul transmisiei, timpul de mişcare şi timpul

de scanare.

În primul experiment am folosit 3 roboţi LEGO NXT (R1, R2, R3) poziţionaţi

aşa cum se arată în Fig. 10.

Fig. 10. Harta primului experiment

Resursa este găsită de robotul R1 în timpul căutării drumului cel mai scurt spre

casă.



Rezultatele sunt prezentate în Tabelul 1. Tcăutare reprezintă timpul necesar

robotului care a găsit resursa să găsească calea cea mai scurtă spre poziţia ACASĂ;

Ttransport este timpul necesar transportării resursei de la poziţia sa iniţială la destinaţie

(poziţia ACASĂ).

Tabel 1. Timpul măsurat pentru primul experiment

Measured time[s] Minimum Maximum

Tsearch(3 steps) 40,91 45,36

Ttransport (1 step) 12,84 13,05

În al doilea experiment am folosit 3 roboţi LEGO NXT poziţionaţi cum este

arătat în Fig.11.

Fig. 11. Harta celui de al doilea experiment

Tabel 2. Timpul măsurat pentru al doilea experiment

Measured time[s] Minimum Maximum

Tsearch (6 steps) 83,48 86,03

Ttransport (3steps) 41,04 44,10

Pe baza experimentelor pe care le-am efectuat, am observat o îmbunătăţire în

eficienţa sistemului pe măsură ce numărul resurselor de hrană creşte şi pe măsură ce

sunt depăşite numeric capacităţiile de transport a unuei singure entităţi robot.

Resursele de mâncare sunt transportate înapoi la regiunea de origine într-o manieră

aproape paralelă: în vreme ce primul robot care ajunge la mâncare începe transportul

înapoi, ceilalţi roboţi, care până acum au primit drumul prin conexiune wireless, se

deplasează deja spre obiectiv.

1.2.3 Fiabilitatea sistemului

Cele trei diagrame de stare Markov, în Fig. 12, au fost create cu privire la un sistem

de colaborare compus din 3 roboţi LEGO Mindstorm NXT. Diagrama Markov este

una teoretică, bazată pe ipoteze privitoare la comportamentul roboţilor.



Fig. 12. Cele trei diagrame de stare Markov reprezentând fiabilitatea unui sistem cu

trei roboţi

Diagrama Markov afişează următoarele stări: în S0 toţi roboţii sunt funcţionali în

interiorul parametrilor lor de funcţionare; în S1 cel puţin un robot nu este funcţional;

în S2 există doi roboţi care nu sunt funcţionali; aceasta este starea de funcţionare

defectuoasă a sistemului.

Stările sistemului pot fi reprezentate ca un set S = {S0, S1, S2}. Cele trei elemente

ale sistemului, corespunzătoare celor trei roboţi LEGO actuali, au distribuţia

exponenţială a funcţionării lor şi intervalele de reînnoire, λ şi μ.

Probabilităţiile asociate fiecărei stări sunt calculate folosind ecuaţii diferenţiale

finite.

)(2)(1)(

])2(1)[(3)()(

)(]31)[()(

22

101

100

tPttPttP

ttPttPttP

ttPttPttP

(1)

Derivând sistemul de ecuații (1) se obține:

)(2)(

)()2()(3)(

)()(3)(

12

101

100

tPdt

tdP

tPtPdt

tdP

tPtPdt

tdP

(2)

Prin rezolvarea sistemului (2) vom obţinem transformarea Laplace a funcţiei de

fiabilitate care reprezintă probabilitatea ca la momentul t sistemul este într-o stare

funcţională.

22

*1

*0

*

6)5(

5)()()(

ss

ssPsPsR (3)

Calculând inversa transformatei Laplace pentru (3) vom obţine funcţia de fiabilitate a

sistemului, care este prezentată în Fig. 13.

S1

3λΔ

t 2λΔ

t

1 - 3λΔt

μΔt

1 - (2λ+μ)Δt

S0

S2

1



Fig. 13. Fiabilitatea sistemului robot LEGO

0 100 200 300 400 0

0.2

0.4

0.6

0.8

rel(t)

t



Bibliografie

[1] LEGO Group, “LEGO MINDSTORMS NXT Hardware Developer Kit”, 2006.

[2] LEGO Group, “LEGO MINDSTORMS NXT Communication protocol”, 2006.

[3] ARM, “ARM7TDMI, Technical Reference Manual”, Rev. 3.

[4] T. Friez, D. Swan, “ROBOTC for LEGO® MINDSTORMS™ 1.30 - Users

Manual”, 2008.

[5] D. Parker, „Fun Projects for your LEGO® MINDSTORMS® NXT!”, 2008

1 definirea unor metrici pentru masurarea si evaluarea...

Documents