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]
Răzvan-Dorel CIOARGĂ Comportament emergent în medii colaborative robotizate
Comportament colaborativ 3
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
Comportament emergent în medii colaborative robotizate Răzvan-Dorel CIOARGĂ
4 Comportament colaborativ
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
Răzvan-Dorel CIOARGĂ Comportament emergent în medii colaborative robotizate
Comportament colaborativ 5
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
Comportament emergent în medii colaborative robotizate Răzvan-Dorel CIOARGĂ
6 Comportament colaborativ
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.
Răzvan-Dorel CIOARGĂ Comportament emergent în medii colaborative robotizate
Comportament colaborativ 7
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
Comportament emergent în medii colaborative robotizate Răzvan-Dorel CIOARGĂ
8 Comportament colaborativ
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ă.
Răzvan-Dorel CIOARGĂ Comportament emergent în medii colaborative robotizate
Comportament colaborativ 9
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.
Comportament emergent în medii colaborative robotizate Răzvan-Dorel CIOARGĂ
10 Comportament colaborativ
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
Răzvan-Dorel CIOARGĂ Comportament emergent în medii colaborative robotizate
Comportament colaborativ 11
Fig. 13. Fiabilitatea sistemului robot LEGO
0 100 200 300 400 0
0.2
0.4
0.6
0.8
rel(t)
t
Comportament emergent în medii colaborative robotizate Răzvan-Dorel CIOARGĂ
12 Comportament colaborativ
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