Ingineria sistemelor [605158]

Universitatea Tehnică Gheorghe Asachi din Iași
Facultatea de Automatică și Calculatoare
Domeniul: Ingineria sistemelor
Specializarea: Automatică și Informatică Aplicată

Proiect de diplomă

Specifica ții logice pentru mișcarea agenților mobili

Coordonator științific Student: [anonimizat].dr.ing. Marius Kloetzer Popa Alina Florina
Grupa 1402A

Scopul lucrării de licență
Lucrarea presupune validarea experimentală a unor strategii automate de planificare a
unei echipe de roboți mobili astfel încât ace știa să satisfacă o specificație logică privind vizitarea
sau evitarea unor regiuni de interes din spațiul de evoluție.

Introducere
Domeniul roboților mobili este de larg interes, căruia cercetătorii din domeniu continuă
să îi acorde o atenție sporit ă.
Un robot mobil reprezinta un sistem automon capabil să se deplaseze (de exemplu o
mașină), dotat cu diverși senzori (de exemplu de poziție, lumină, apropiere de obstacole) și
capabil să ruleze algoritmi computaționali pentru procesarea diverselor inform ații. Deși
capabilitatea de procesare este inclusă în multe sisteme robotice mobile, în cazul în care
algoritmii ce trebuie rulați au o complexitate crescută, sistemul robotic poate fi conectat la un
computer extern.
Bazele roboților de azi stau mult mai d eparte. Primele modele de mașini pot fi mai
degrabă numite automate. Acestea nu puteau executa decât câte un singur obiectiv, fiind
constrânse de construcție.
Matematicianul grec Archytas a construit, conform unor relat ări, unul dintre aceste prime
automate: un porumbel propulsat cu vapori, care putea zbura singur. Acest porumbel cavernos
din lemn era umplut cu aer sub presiune. Acesta avea un ventil care permitea deschiderea și
închiderea printr -o contragreutate.
Dezvol tarea electrotehnicii din secolul XX a adus cu sine și o dezvoltare a roboticii.
Printre primii roboți mobili se numără sistemul Elmer și Elsie construit de William Grey Walter .
Aceste triciclete se puteau îndrepta spre o sursă de lumină și puteau să recunoască coliziuni în
împrejurimi.

Probleme clasic e de navigare a roboților mobili
Acest capitol prezintă noțiuni și tipuri de probleme specifice roboțil or mobili. Mai întâi
vor fi discutate concepte precum spațiu de lucru, spațiu de configurare, punct de referință al unui
robot mobil, iar apoi vor fi prezentate patru clase importante de probleme întâlnite în robotică.
Robotul mobil reprezintă o structură ce conține componente me canice (roți,
brațe/articulații mobile), electrice (motoare, surse de energie, senzori) și computaționale
(microprocesor, memorie) și care poate executa o sarcină dorită (de exemplu deplasarea într -un
anumit punct). Pentru execu ția sarcinilor dorite se implementează un algoritm ce rulează pe robot
astfel incât să ducă la îndeplinirea acestor sarcini.
Algoritmii ce rulează pe robot pot fi de o complexitate computațională crescută, și de
aceea aceștia pot fi rulați pe un sistem d e calcul extern și static (de exemplu un computer) care
comunică cu robotul. În acest caz, sistemul extern joacă rolul unui controller, care primește
informații utile de la robot sau de la diverși senzori (de exemplu poziția robotului, detectarea
unor obst acole), procesează aceste informații și transmite robotului comenzi de mișcare.
Spațiul de lucru al unui robot mobil este spațiul în care acesta evoluează. Spațiul de lucru
este de multe ori mărginit iar in interiorul lui pot pot exista obstacole. Spațiu l de lucru liber este
subsetul spațiului de lucru în care nu există obstacole.
Spațiul de configurație al robotului este setul care cuprinde toate configurațiile sau stările
posibile ale robotului. Dimensiunea spațiului de configurație este de obicei mai mare decât cea a
spațiului de lucru.
Punctul de referință reprezintă punctul de pe robot pentru care se exprimă valoarea
configurației (stării) curente și acesta trebuie să rămână fix pentru robotul dat.

I. Clase de probleme referitoare la roboți mobili

Există patru clase de probleme des întântite în operarea cu roboți mobili.

• Probleme de navigare:
Acestea își propun găsirea și urmărirea unei traiectorii pentru robotul mobil astfel
încât acesta să pornească din poziția sa inițială și să ajungă într -o poziție finală dorită,
fără a se lovi de obstacole.
• Probleme de acoperire:
Trebuie să s e producă o strategie de mișcare a robotului astfel încât acesta să viziteze
toate pozițiile neocupate de obstacole.
• Probleme de localizare:
Scopul unei probleme de localizare este de a determina poziția și eventual orientarea
robotului mobil în harta dat ă. Robotul poate fi dotat cu diverși senzori, și trebuie să
aibă la dispoziție o hartă (chiar dacă nu foarte completă) a domeniului de evoluție.
• Probleme de construire de hărți:

Aceste probleme au scopul de a explora, cu un robot dedicat, un mediu de evolu ție
necunoscut și de a construi o hartă a acestui mediu. La acestea mediul poate fi total
necunoscut, sau poate fi parțial cunoscut.

II. Soluții pentru probleme de navigare
Prezentarea unor algoritmi care permit rezolvarea problemelor de navigare pentru anumiți
roboți mobili.
• Algoritmi de tip insectă:
Algoritmii de tip insectă sunt dintre cele mai simple soluții pentru problemele de
navigare. Aceștia sunt însă fezabili doar pentru situații simpliste, când roboții acționează doar pe
baza senzorilor proprii, fără a fi coordonați de o unitate supervizoare. Traiectoriile sunt produse
în urma concatenării unor decizii locale, și nu utilizează întreaga hartă a mediului; astfel,
traiectoriile sunt deseori mult mai lungi decât cele rezultate prin folosirea altor metode.
• Funcții de potențial:
Funcțiile de potențial au drept scop construirea unei funcții definită pe mediul de
evoluție, cu cerința ca această funcție să aibă minimul în punctul de stop. După construirea
acestei funcții, mișcarea robotului se face conform ideii de descindere pe gradient. Un neajuns al
funcțiilor de potențial este acela de a prezenta minime locale, care dacă sunt atinse nu pot fi
părăsite ulterior de robot . O posibilitate de evitare a minimelor locale este utilizarea unor funcții
modificate, denumite funcții de navigare. Aceste funcții pot fi construite doar pentru domenii de
evoluție mărginite de un cerc, în care toate obstacolele sunt circulare. Trasforma rea unui
domeniul de evoluție dat într -un astfel de domeniu circular este deseori greoaie.
• Hărți:
O posibilă soluție a problemei de navigare poate fi dată de hărțile de evoluție robotică.
Acestea introduc ideea construrii unor reprezent ări reduse ale mediului de evoluție.
a) Grafuri de vizibilitate:
În cadrul hărților de evoluție au fost prezentate grafurile de vizibilitate, care sunt
construite adăugând segmente de dreaptă între vârfurile obstacolelor care sunt vizibile unul din
celălalt.
b) Diagrame Voronoi Generalizate:
Diagramele Voronoi Generalizate sunt alcătuite din setul de puncte aflate la distanță
egală de cele mai apropiate două obstacole. Construcția acestora este însă dificilă în cazul
domeniilor de evoluție specifice ro boților mobili.
c) Descompuneri în celule:
Ideea de bază a acestora este de a partiționa spațiul liber de evoluție (neacoperit de
obstacole) într -un set de forme geometrice de același tip, iar apoi de a construi un graf de

adiacență pe baza descompuneri i obținute. Astfel, problema inițială va fi redusă la o reprezentare
cu un număr finit de stări, iar o soluție a problemei de planificare poate fi obținută în urma unei
căutări în graful de adiacență.

Descompuneri in celule
Capitolul prezintă metode ce pot fi folosite pentru construcția reprezentărilor cu număr
finit de stări ale roboților mobili.
I. Noțiuni preliminare
• Grafuri
Un graf G este o colecție G = (N, A ) , unde N este un număr finit de noduri, iar A
⊆ N × N este un set de arce (legături posibile) între aceste noduri, adică (n1, n2) ∈ A dacă și
numai dacă există un arc ce leagă nodul n1 de n2. Grafurile pot fi atat adirecționale(Figura1, a.),
când legăturile între noduri pot fi parcurse în ambele sensuri, dar pot fi și direcționale(Figura1,
b.), iar convenția de reprezentare folosește săgeți pentru a sugera direcția arcelor respective.

Figura 1 a. Graf adirecțional; Figura 1 b. Graf direcțional.

• Domenii de evoluție robotică
Pentru explicarea tehnicilor de descompunere în celule vom presupune că domeniul în
care un robot mobil evoluează este bidimensional (planar), mărginit de un dreptunghi, și conține
mai multe obstacole. Fiecare obstacol e ste presupus a fi un poligon convex, o astfel de formă
geometrică fiind denumită și politop. Robotul mobil este considerat punctiform și „fully –
actuated ” (se poate deplasa în orice direcție la orice moment de timp).

Figura 2. Dom eniu de evoluție dreptunghiular, ce conține trei
obstacole politopale cu număr diferit de laturi.
Vom nota cu E ⊂ ℝxℝ domeniul dreptunghiular de evoluție, obstacolele le vom nota cu
O1,O2 ,…,On. Pentru orice formă politopală S ∈ {E, O1,O2,…,On} vom nota cu Vs = {vs^1, vs^2
, …, vs^|vs| } setul vârfurilor sale și cu Fs = {fs^1, fs^2 , …, fs^|vs| } setul fațetelor (laturilor)
sale. Vom denumi spațiu liber porțiunea din domeniul E care nu este acoperită de nici un
obstacol. Figura2 prezintă un mediu de evoluție ce respectă presupunerile de mai sus, ilustrând
totodată convențiile de notare ale vârfurilor și fațetelor .
• Politoape
Un p olitop în ℝxℝ este un poligon convex (iar într -un spațiu de orice dimensiune este un
poliedru mărginit și convex). Pentru un politop S vom nota cu Vs = {v s^1, v s^2 , …, v s^|vs| } setul
vârfurilor sale și cu Fs = {f s^1, f s^2 , …, f s^|vs| } setul fațet elor (laturilor). Pentru a reprezenta
matematic (inclusiv într -un program software) un politop există două metode posibile:
(i) reprezentarea V, care constă în enumerarea coordon atelor vârfurilor sale (setul Vs ).
Matematic, politopul S este setul tuturor combinațiilor convexe posibile ale elementelor din Vs ,
adică:

(ii) reprezentarea H, care constă în enumerarea unui număr |Vs| de semiplane din ℝxℝ a
căror intersecție este egală cu S. Matematic, S poate fi exprimat prin:

Centrul de greutate al unui politop este dat de media aritmetică a coordonatelor vârfurilor
sale, și acesta poate fi util în stabilirea semnului inegalităților din reprezentarea H, deoarece
centrul de greutate al unui politop apa rține întotdeauna acestuia.

• Probleme de programare lineară
Problemele Linear Programming (LP) au fost intens studiate, și la momentul actual există
algoritmi implementați în multe medii software pentru rezolvarea acestui tip de probleme. Un
astfel de algoritm poate fi util pentru a decide dacă un politop pentru care avem reprezentarea H
este sau nu vid. Dacă există o soluție, înseamnă că politopul este nevid, caz în care se pot
determina vârfurile sale; dacă algoritmul LP nu returnează nici o soluție, înseamnă că politopul
este vid.

II. Descompuneri în celule poligonale convexe
O descompunere în celule a fost definită ca un set de celule având aceeași formă
geometrică, uniunea tuturor celulelor fiind egală sau aproximând spațiul liber. Există două clase
de descompuneri în celule: exacte și aproximative. O descompunere este exactă dacă uniunea
celulelor rezultate este egală cu spațiul liber. O descompunere se numește aproximativă dacă
uniunea celulelor sale este inclusă în spațiul liber, și apro ximează acest spațiu cu o anumită
precizie.
• Descompunerea trapezoidală
Descompunerea trapezoidală este întâlnită în problemele de robotic ă cu scop ilustrativ,
fiind suficient de simplu de obținut. Ideea de bază este de a extinde o dreaptă verticală din fiecare
până când o latură din setul
este intersectată. Direcția pentru a extinde o linie verticală
este determinată de poziția relativă a vârfului curent în raport cu alte vârfuri ale aceluiași
obstacol. De exemplu, în domeniul din figura3 linia verticală pornind din va fi extinsă doar în
sus, în timp ce linia verticală din v o^1 va fi extinsă în ambele direc ții

Figura 3 a. Figura 3 b.
Primii doi pași ai construirii descompunerii trapezoidale. Fiecare dreaptă verticală construită la
pasul curent este marcată cu culoare roșie.

Figura 4. Descompunerea trapezoidală a domeniului din figura 2, constând în 16 celule.
Adiacența între celule este ilustrată prin linii albastre punctate.
Descompunerea trapezoidală tinde să aibă un număr mai mic de celule decât celelalte
descompuneri , fapt benefic deoarece complexitatea abstracției finite este redusă (graful
corespunzător are un număr redus de noduri ). Descompunerea trapezoidală este uneori
dezavantajoasă deoarece vârfurile obstacolelor nu trebuie să aibă aceeași coordonată pe axa Ox,
iar unele trapeze rezultate pot fi foarte înguste.
• Descompunerea triunghiulară
Descompunerea triunghiulară are drept scop partiționarea spațiului liber în triunghiuri.
Aceste triunghiuri au vârfurile în setul de vârfuri existente, prin urmare descompunerea este
echivalentă cu o alocare a câte trei vârfuri din setul amintit fiecărei celule. O consecință a acestui
aspect este faptul că oricare două triunghi uri adiacente rezultate au în comun o întreagă fațetă
O triangularizare Delaunay are drept intrări un set de puncte și conectează aceste puncte
cu scopul de a forma triunghiuri ce îndeplinesc două proprietăți adiționale – maximizarea
unghiului minim al u nghiurilor obținute în triunghiurile din descompunere, și cercul circumscris
fiecărui triunghi obținut nu include un al patrulea punct din setul de puncte dat. Spre
exemplificare, în figura5 este reprezentat cu roșu un triunghi care poate rezulta în urma u nei
triangularizări Delaunay .

Figura 5: Domeniul de evoluție și un triunghi (reprezentat cu roșu) al triangularizării Delaunay.
Acest triunghi taie un obstacol, prin urmare triangularizarea Delaunay nu poate fi aplicată în
situa ția de față.

Figura 6. Descompunerea în 20 de celule triunghiulare a domeniului de evoluție figura2. Liniile
punctate reprezintă adiacența între celule.

Descompunerile triunghiulare au un avantaj adițional, acela de a permite și
descompunerea obstacolelor o dată cu spațiul liber. Acest lucru poate fi folosit în cazurile în care
în spațiul de evoluție există regiuni predefinite, însă acestea nu sunt obstacole, ci de exemplu pot
fi zone de interes care trebuie vizitate într -o anu mită ordine.
• Descompunerea politopală
Ideea de bază pentru a obține o astfel de descompunere este de a extinde dreptele de
suport ale fațetelor obstacolelor, iar apoi de a căuta toate politoapele incluse în domeniul E și

delimitate de aceste drepte. Fiec are politop determinat nu trebuie să fie intersectat de alte drepte
care provin din laturile obstacolelor. O reprezentare grafică a acestei idei este dată în figura7,
unde un politop din domeniul de evoluție din figura7 este delimitat de dreptele cărora le aparțin
unele fațete ale obstacolelor.

Figura7. Politopul alb este delimitat de dreptele de suport ale fațetelor fo1^1, fo1^3, fo2^4.
Semiplanele delimitate de dreapta de suport a fațetei f o1^3 sunt reprezentate cu bleu și verde.

Figura 8. Descompunerea politopală a domeniului din figura 2, constând în 42 celule. Adiacența
între celule este ilustrată prin linii punctate.

Descompunerile în politoape au în general un număr mare de celule, ceea ce duce la o
complexitate crescută. Însă, aceste descompuneri au avantajul de a putea fi ușor extinse la spații
de dimensiune mai mare decât 2.

• Descompunerea dreptunghiulară
Descompunerea dreptunghiulară este o descompunere aproximativă, în care o parte a
spațiului liber va fi acoperită de dreptunghiuri, rămânând mici porțiuni neconținute în celule.
Aceste porțiuni vor fi localizate în apropierea obstacolelor – acest aspect va constitui un avantaj
când vom plan ifica un robot mobil prin celule ale descompunerii, deoarece se vor evita mișcările
în imediata apropiere a obstacolelor.
Dreptunghiurile din descompunere au același raport lațime/înălțime ca și domeniul de
evoluție E, însă vor avea arii diferite. Algori tmii de partiționare în dreptunghiuri sunt inspirați de
tehnici „quad -tree”, care sunt descompuneri ierarhice folosite pentru organizarea datelor sau
pentru compresia imaginilor. Un quad -tree este un arbore ale cărui noduri fie sunt frunze, fie au
câte pat ru descendenți. Fiecare nod din quad -tree-ul ce va fi creat va corespunde unui dreptunghi
conținut în E, și poate fi etichetat cu una din următoarele trei variante: ocupat (dreptunghiul este
conținut în întregime într -un obstacol sau într -o uniune de obsta cole), liber (dacă dreptunghiul se
află în spațiul liber), mixt (dacă unele porțiuni ale dreptunghiului sunt incluse în obstacole și
unele porțiuni sunt în spațiul liber) Ideea de bază a descompunerii dreptunghiulare este de a
împărți recursiv (începând cu dreptunghiul E) fiecare dreptunghi mixt în patru dreptunghiuri
egale, înjumătățind fiecare latură. Un dreptunghi nu va fi împărțit dacă este liber, ocupat, sau este
mixt dar are o arie mai mică decât o precizie impusă. În ultimul caz, dreptunghiul este et ichetat
drept ocupat. Astfel, la sfârșitul creării quad -tree-ului, frunzele vor fi etichetate liber sau ocupat,
iar frunzele libere vor corespunde celulelor din descompunerea dreptunghiulară.
Primele iterații ale algoritmului de descompunere în dreptungh iuri aplicat domeniului din
figura 2 sunt ilustrate prin reprezentările din figura 9.

Figura 9. Primele iterații ale descompunerii dreptunghiulare a domeniului din figura 2.

Figura 10 prezintă descompunerea dreptunghiulară a dom eniului de evoluție prezentat în
figura 2, unde preciziile ε x și εy au fost alese de 32 de ori mai mici decât dimensiunile lui E pe
axa Ox, respectiv Oy. Datorită acestei precizii, spațiul din jurul obstacolelor nu este acoperit cu
dreptunghiuri libere, ce ea ce arată că descompunerea dreptunghiulară este o descompunere
aproximativă.

Figura 10. Descompunerea dreptunghiulară cu 129 celule a domeniului din figura 2 . Aria de
culoare gri din jurul obstacolelor este considerată drept ocupată din punct de vedere al
descompunerii, aceasta nefiind acoperită de celulele rezultate.

Bibliografie

[1] Marius Kloetzer – Strategii de planificare a robotilor mobili .