Universitatea Tehnica“Gh. Asachi” din Iasi
Scoala Doctorala a Facultatii de
Automatica si Calculatoare
Dezvoltari Teoretice si Aplicativepentru Planificarea Miscarii
Robotilor Mobili
Rezumatul Tezei de doctorat
Conducator de doctorat:
Prof. univ. dr. ing. Octavian Pastravanu
Doctorand:
Ing. Ghita Narcis
Iasi - 2012
Teza de doctorat a fost realizata cu sprijinul financiar al
proiectului “Burse Doctorale pentru Performanta ın Cercetare
la Nivel European (EURODOC)”.
Proiectul “Burse Doctorale pentru Performanta ın Cercetare
la Nivel European (EURODOC)”, POSDRU/88/1.5/S/59410,
ID 59410, este un proiect strategic care are ca obiectiv gen-
eral “Dezvoltarea capitalului uman pentru cercetare prin pro-
grame doctorale pentru ımbunatatirea participarii, cresterii
atractivitatii si motivatiei pentru cercetare. Dezvoltarea la nivel
european a tinerilor cercetatori care sa adopte o abordare inter-
disciplinara ın domeniul cercetarii, dezvoltarii si inovarii.”
Proiect finantat ın perioada 2009 - 2012.
Finantare proiect: 18.943.804,97 RON
Beneficiar: Universitatea Tehnic “Gheorghe Asachi” din Iasi
Partener: Universitatea “Babes Bolyai” din Cluj-Napoca
Cuprins
1 Introducere 1
2 Considerente teoretice 4
2.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Modelarea matematica a robotului . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Abordarea vehiculului virtual . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4 Modelul unificat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.5 Abstractizarea mediului . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.6 Sistem de tranzitie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.7 Logica liniara temporala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.8 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Descompunerea celulara 8
3.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Descompunerea celulara . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3 Implementare si extensii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.4 Analiza comparativa a descompunerilor celulare . . . . . . . . . . . . . . . . 9
3.4.1 Analiza calitativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.4.2 Analiza cantitativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.5 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Problema de planificare clasica 12
4.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2 Solutionarea VRP clasica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3 Complexitatea algoritmilor de planificare bazati pe descompunerea celulara . 13
4.4 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5 Problema de planificare cu sarcini complexe 16
5.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
i
ii
5.2 Solutionarea problemei de planificare LTL�X . . . . . . . . . . . . . . . . . . 16
5.2.1 Constructia sistemului de tranzitie T . . . . . . . . . . . . . . . . . . 17
5.2.2 Gasirea unei rulari a lui T . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2.3 Algoritmul PLTLCon Car Like . . . . . . . . . . . . . . . . . . . . 17
5.3 Reducerea complexitatii ın planificarea LTL�X . . . . . . . . . . . . . . . . . 18
5.3.1 Modelul brut al robotului . . . . . . . . . . . . . . . . . . . . . . . . 18
5.3.2 Rulari individuale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.3.3 Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.4 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6 Planificarea vizuala a miscarii din imagini omnidirectionale 20
6.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.2 Reconstructia 2D a mediului . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.3 Planificarea vizuala a miscarii . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.4 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
7 Concluzii finale si directii viitoare de cercetare 24
7.1 Contributii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
7.2 Directii de cercetare deschise . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Bibliografie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Capitolul 1
Introducere
Largirea autonomiei robotilor mobili este o arie de cercetare care a polarizat un cert
interes ın ultimele doua decenii, dupa cum reiese din diverse publicatii, dintre care amintim
drept foarte relevante [Choset et al., 2005, Latombe, 1991, LaValle, 2006]. In acest sens
cercetarea s-a concentrat ın doua directii majore. O prima directie, maparea si localizarea
(SLAM - Simultaneous Localization and Mapping), se refera atat la captarea si modelarea
mediului ın care activeaza robotul ıntr-un format compatibil structurilor ce ıl utilizeaza, ın
cazul nostru, algoritmului de planificare, dar si la determinarea pozitiei acestuia. Cea de a
doua directie, planificarea sau navigarea, se refera la generarea controlului care sa conduca
robotul spre rezolvarea sarcinilor impuse.
Teza este motivata, ın primul rand, de prezenta unor limitari ale algoritmilor disponibili
ın literatura pentru planificarea miscarii robotilor asupra carora actioneaza constrangeri de
miscare (nonholonomice). Majoritatea algoritmilor de planificare pentru acest tip de robot
nu garanteaza gasirea unei solutii ın toate situatiile cand aceasta exista (motiv pentru care
se spune ca respectivii algoritmi nu sunt completi). Limitarea mentionata este indusa de
ipoteza frecventa cosiderata ın solutionarea VRP (Vehicle Routing Problem) conform careia
robotul este abstractizat la un punct material [Choset et al., 2005, LaValle, 2006]. Totodata
o serie de algoritmi nu sunt automatizati sau au un cost computational prea ridicat pentru
a fi practic implementabili [Conner et al., 2007, Backer and Kirkpatrick, 2007].
Teza intitulata Dezvoltari Teoretice si Aplicative pentru Planificarea Miscarii Robotilor
Mobili este structurata ın sapte capitole ce vor fi prezentate ın acest rezumat urmand,
ındeaproape, structura tezei.
Primul capitol intitulat Introducere prezinta stadiul actual ın domeniul solutionarii VRP
din domeniul WMR (Wheeled Mobile Robots) marcand contributiile lucrarii si punctand ın
finalul capitolului lucrarile publicate care le valideaza.
Capitolul urmator intitulat Considerente teoretice va prezenta fundamentele matematice
1
2
utilizate ın planificarea discreta a miscarii WMR referite pe parcursul lucrarii. In debutul
capitolul este detaliat modul de alegere a modelului matematic utilizat ın solutionarea prob-
lemelor de planificare pentru robotul de tip masina si a celui complet actionat. In sectiunea
imediat urmatoare strategia de control pentru urmarirea traiectoriei denumita abordarea
vehiculului virtual este prezentata. Sectiunea a patra este dedicata modelarii sistemului
senzorial catadioptric utilizat ın algoritmul SLAM ce va fi prezentat ın finalul lucrarii si,
totodata, a unor metode specifice domeniului pentru extractia liniilor verticale si calculul
tensorului trifocal 1D. Urmatoarele trei sectiuni prezinta la nivel teoretic modelarea matem-
atica a mediului, capabilitatilor de miscare ale robotului si a sarcinilor de miscare ıntr-un
format care sa permita rezolvarea VRP.
Capitolul 3 intitulat Descompunerea celulara prezinta, ın debutul sau, principalele abordari
de abstractizare geometrica a mediului ıntr-un sistem de tranzitie. In sectiunea a patra a
capitolului este prezentat un studiu comparativ ıntre cele mai uzuale descompuneri celulare
avand ca scop dezvoltarea unei metode numerice sau empirice utilizabila ın alegerea metodei
de partitionare a mediului care sa conduca la rezultate cat mai bune ın solutionarea unei
anumite probleme avand cunostinte minime despre abordarea utilizata ın solutionare.
Capitolul 4 intitulat Problema de planificare clasica prezinta, ın prima parte, o abordare
automata de generare si urmarire a traiectoriei pentru un robot de tip masina considerand
dimensiunea fizica a acestuia. Finalul capitolului include o analiza a performantelor algorit-
mului de planificare ın raport cu metodele de partitionare utilizate pentru un set amplu de
scenarii.
Capitolul 5 intitulat Problema de planificare cu sarcini complexe prezinta, ın Sec. 5.2,
solutia VRP pentru roboti de tip masina, avand sarcinile de miscare introduse ın forma unei
formule LTL peste un set de regiuni de interes. Abordare va genera rularea (secventa de stari
intermediare) care maximizeaza probabilitatea de a satisface formula pentru controlul con-
siderat. Finalul capitolului este dedicat prezentarii unei metode de reducere a complexitatii
algoritmilor de planificare cu sarcini complexe pentru echipe de roboti complet actionati.
Capitolul 6 intitulat Planificarea vizuala a miscarii din imagini omnidirectionale propune
solutia completa a VRP pentru WMR, ın cazul unui mediul poligonal, finit si presarat cu
obstacole statice luand ın considerare dimensiunea fizica a robotului. Totodata, un algoritm
SLAM din imagini omnidirectionale si metoda de interconectare cu algoritmii de planifi-
care ce folosesc geometria mediului, va fi prezentata ca parte componenta a algoritmului de
planificare complet bazat pe grafuri de vizibilitate tangentiale.
Ultimul capitol intitulat Concluzii finale si directii viitoare de cercetare va sublinia
contributiile lucrarii punctand cateva directii viitoare de cercetare.
3
Lista publicatiilor
Teza este construita ın jurul a sapte articole, dupa cum urmeaza: - patru lucrari de
revista, dintre care doua reviste cotate ISI (cu factor de impact si scor relativ de influenta)
si doua reviste indexate Zentralblatt MATH:
• N. Ghita and M. Kloetzer (2010), Motion planning and controlling a car-like robot
in an environment Cluttered with static obstacles, Bulletin of the Polytechnic Institute
of Iasi, Automatic Control and Computer Science Section, Tome LVI (LX), Fasc. 3,
class B+, Iasi, Romania, pp. 81-94.
• M. Kloetzer and N. Ghita (2012), On reducing complexity in LTL-based motion plan-
ning, Bulletin of the Polytechnic Institute of Iasi, Automatic Control and Computer
Science Section,Tome LVII (LXI), Fasc. 4, class B+, Iasi, Romania, pp. 9-20
• N. Ghita and M. Kloetzer (2012), Trajectory planning for a car-like robot by envi-
ronment abstraction, Robotics and Autonomous Systems, IF 1.313, 60(4):609–619
• M. Kloetzer and N. Ghita (2012), Automatic construction and comparative analysis
of cell decompositions, (IMACS) Mathematics and Computers in Simulation, IF 0.738,
under review
si trei lucrari publicate ın volume de conferinte indexate IEEE Xplore:
• N. Ghita and M. Kloetzer (2010), Cell Decomposition-Based Strategy for Planning
and Controlling a Car-like Robot, Proc. of the 14th International Conference on Sys-
tem Theory and Control(ICSTC), Romania, Sinaia, ISBN : 20680465, pp. 225-231.
• M. Kloetzer and N. Ghita (2011), Software tool for constructing cell decomposi-
tions, IEEE Conference on Automation Science and Engineering, Trieste, Italy, DOI
: 10.1109/CASE.2011.6042492, ISSN : 2161-8070, ISBN : 978-1-4577-1730-7, pp. 507-
512.
• N. Ghita, M. Kloetzer and O. Pastravanu (2011), Probabilistic car-like robot path
planning from temporal logic specifications, 15th International Conference on System
Theory, Control, and Computing (ICSTCC), Romania, Sinaia, ISBN:978-1-4557-1173-
2, pp. 1 - 6.
Capitolul 2
Considerente teoretice
Solutionarea VRP cu sarcini complexe impune abstractizarea spatiului liber si a capa-
bilitatilor de miscare ale robotului ıntr-un sistem de tranzitie fara stari de blocare denumit
ın literatura de specialitate structura Kripke. Maparea (cartografierea) ın solutionarea prob-
lemei clasice de navigare are atat rolul de a ımbunatati harta disponibila dar si de a semnala
algoritmului de planificare schimbarile ce apar ın mediu si care ar putea produce modificari
ale traiectoriei initiale.
2.1 Introducere
O notiune utilizata ın teza este aceea de traiectorie fezabila ca fiind traiectoria care
asigura robotului o miscare lipsita de coliziuni cu obstacolele ın rezolvare problemei clasice
de navigare.
2.2 Modelarea matematica a robotului
In solutionarea VRP, pentru robotul complet actionat si de cel tip masina, s-au utilizat
modelele care le descrie cinematica. O notiune utilizata ın teza este cea de cerc de ıntoarcere
bordura la bordura (wall-to-wall turning circle - cercul care include aria minima maturata de
robot atunci cand face o ıntoarcere de 360� ın jurul axei de rotatie) si a carui raza pentru
cazul robotului de tip masina poate fi obtinuta cunoscand unghiul maxim de comanda a
directiei si dimensiunile fizice ale robotului utilizand geometria lui Ackermann.
4
2.3. Abordarea vehiculului virtual 5
2.3 Abordarea vehiculului virtual
Metoda pe care o vom utiliza ın algoritmul de urmarire a traiectoriei are la baza abor-
darea vehiculul virtual [Egerstedt et al., 2001]. Abordarea vehiculului virtual presupune
gasirea unei strategii de control lateral si a uneia longitudinala care sa oblige robotul sa
urmareasca o traiectorie neteda. Presupunand un vehicul virtual ce se deplaseaza pe aceasta
traiectorie dupa legea de miscare, este proiectat controlerul care sa minimizeze eroarea dintre
configuratia robotului si configuratia vehiculului virtual la momente discrete de timp.
2.4 Modelul unificat
Modelul proiectiei utilizat ın teza pentru descrierea senzorului catadioptric (camera si
oglinda) este cel propus ın [Mei and Rives, 2007]. Un astfel de model reprezinta un com-
promis ıntre un model foarte general care poate fi dificil de calibrat si modele care nu iau
ın considerare factori importanti cum ar fi alinierea sau distorsiunile optice, avand la baza
asumptia realista a micilor erori comparat cu modelul teoretic ideal.
Modelul unificat permite modelarea senzorului catadioptric, astfel ıncat un punct din
spatiu poate fi proiectat ın planul imaginii si viceversa la o anumita scala, ın cazul ın care
parametrii asociati camerei si oglinzii sunt cunoscuti. In vederea calibrarii sistemul catadiop-
tric s-a utilizat pachetul software dezvoltat de Puig [Puig, 2011]. Presupunand cunoscuta
scala traiectoria robotului poate fi estimata, avand imaginile achizitionate la momentele de
timp consecutive [Aranda et al., 2010]. Un alt rezultat utilizat ın Cap. 6, si introdus ın acest
punct al lucrarii, este cel propus ın [Scaramuzza et al., 2009] pentru extractia liniilor verti-
cale din imagini omnidirectionale. Abordarea se bazeaza pe calculul gradientului imaginii
obtinut din convolutia imaginii de intrare cu o masca Sobel.
2.5 Abstractizarea mediului
Spre deosebire de algoritmii de explorarea unde mediul este necunoscut sau partial cunos-
cut ın cazul algoritmilor de planificare presupunerea care se face este aceea ca mediul este
complet cunoscut apriori iar miscarea WMR ın cazul VRP se desfasoara ın plan. O alta
ipoteza frecventa asupra mediului ın care activeaza robotul este ca este poligonal si este
presarat cu o multime finita de regiuni de interes (ın prima instanta vor fi considerate ob-
stacole) nu neaparat incluse ın mediului modelate prin poligoane convexe.
Metodele de planificare a miscarii pot fi grupate ın trei clase functie de modul ın
care mediul este abstractizat si anume: abordari bazate pe functii de potential, metode
2.6. Sistem de tranzitie 6
bazate pe harti rutiere si cele bazate pe descompunerea celulara. Cele mai utilizate harti
rutiere sunt: grafurile de vizibilitate (visibility graph) si grafurile retractare (retraction
graph) [Latombe, 1991, Choset et al., 2005]. In descompunerea celulara spatiul liber de
miscare a robotului este ımpartit ın regiuni numite celule [Choset et al., 2005, Latombe, 1991].
2.6 Sistem de tranzitie
In solutionarea problemelor de miscare cu sarcini complexe se construieste o reprezentare
discreta finita a capabilitatilor de miscare ale robotului ın mediu dat demunit sistem de
tranzitie. In solutionarea problemei de navigare cu sarcini complexe pentru robotul de tip
masina capabilitatile de miscare ale acestuia sunt transformate ıntr-un sistem de tranzitie
Markovian. Mentionam ca definitiile introduse ın acesta sectiune a tezei descriu complet
functionalitatea sistemului de tranzitie T utilizat pe parcursul lucrari.
2.7 Logica liniara temporala
In viziunea noastra un limbaj de specificatii este”bun” daca este apropiat de limbajul
natural (apropiat de cel uman), asigura expresivitatea necesara exprimarii unei game cat mai
variata de sarcini, iar costul computational necesar analizei si sintezei controlerului pentru
specificatiile date este scazut. Motivati de explicatiile date am ales utilizarea unei fractii
din LTL, denumita LTLX , care confera expresivitate specificatiilor de miscare la un cost
computational acceptabil.
Problema de control a unui sistem de tranzitie care sa satisfaca o formula LTLX porta
denumirea de problema de planificare LTLX . In gasirea solutiei a unei astfel de probleme, se
poate ıncerca utilizare unui algoritm de verificare a modelului deja existent cum ar fi SPIN
sau NuSMV considerand formula negata, contra exemplul returnat va reprezenta rularea care
satisface formula initiala. Un astfel de algoritm primeste la intrare un sistem de tranzitie T
fara stari de blocare si formula φ, furnizand starile initiale ale lui T pentru care formula este
satisfacuta.
Pentru orice formula LTLX , peste un set de predicate Π, exista un automat Buchi care
accepta doar siruri infinite peste Π ce satisfac formula [Wolper et al., 1983]. In abordarile
propuse de noi vom folosi algoritmul de conversie ıntr-un automat Buchi a formulelor LTLX
din [Gastin and Oddoux, 2001] si mai departe adaptat ın [Kloetzer and Belta, 2008] pentru
solutionarea sarcinilor de miscare din robotica.
2.8. Concluzii 7
2.8 Concluzii
Abordarile din panificarea si controlul robotilor mobili pot fi grupate ın doua categorii
functie de abordarea utilizata ın solutionarea VRP: top-down si bottom-up. In abordarile
top-down accentul este pus pe expresivitatea limbajului de specificatii, posibilitatea imple-
mentarii controlului necesar rezolvarii sarcinilor cazand ın plan secund. Pe cealalta parte ın
abordarile bottom-up se ıncearca solutionarea problemelor simple de planificare considerand
constrangeri de miscare sau elemente ce surprind dinamica robotului.
Capitolul 3
Descompunerea celulara
Descompunerile celulare permit modelarea spatiului initial continuu ıntr-o reprezentare
de stare finita. Ideea principala este de a descompune mediu marginit dat ıntr-un set de
regiuni care nu se suprapun. Reuniunea acestor regiuni, numite celule, acopera sau aprox-
imeza un subset de interes din mediu marginit dat, cum ar fi spatiul neocupat de obstacole.
Odata descompunerea obtinuta o reprezentare finita sub forma unui graf poate fi construita
pentru partea acoperita de celule din mediu. In acest sens, fiecarei celule ıi este asociat un
nod ın graf, arcele ıntre nodurile corespunzand relatiilor de adiacenta dintre celule.
3.1 Introducere
In abordarile propuse pentru solutionarea VRP se face asumptia ca mediului ın care
activeaza robotul este dreptunghiular E � R2 si presarat cu n obstacole (zone de interes)
poligonale Π. Este de remarcat ca asumptia obstacolelor poligonale nu este restrictiva,
d.p.d.v. al reprezentari, deoarece orice obstacol convex de forma non-poligonala poate fi
aproximat de un poligon convex, iar fiecare regiune de forma non-convexa poate fi divizata
ın regiuni adiacente convexe. Bine ınteles, cazul general ın care mediul este modelat printr-
un poligon oarecare poate fi modelat considerand mediul dreptunghiular si definind obstacole
interioare cu o fateta pe limitele dreptunghiulare ale mediului considerate initial. In Sec. 3.4
este propusa o analiza calitativa si una cantitativa pentru descompunerile celulare studiate.
Rezultatul analizelor fiind o metoda numerica de alegere a descompunerii celulare care sa
conduca la cele mai bune solutii pentru o problema data.
8
3.2. Descompunerea celulara 9
3.2 Descompunerea celulara
Algoritmii de descompunere celulara studiati au ca intrare E si Π (reprezentate prin
multimea varfurilor). Iesirea unui astfel de algoritm fiind multimea celulelor Q, si relatia
de adiacenta dintre acestea ın forma unei matrici simetrice A P R|Q|�|Q|, ın care Api, jq � 1
pentru celule adiacente si Api, jq � 0 ın caz contrar. Cazul amintit este cel al sistemelor de
tranzitie deterministe ın care pentru oricare doua celule adiacente exista un controler care
sa scoata robotul prin fateta comuna.
Sectiunea prezinta cele mai uzuale patru descompuneri celulare si anume trapezoidala,
triunghiulara, poligonala si dreptunghiulara la nivel constructiv si de pseudo-cod adaptate
problemelor din robotica.
3.3 Implementare si extensii
Descompunerile celulare prezentate ın Sec. 3.2 sunt implementate ca un pachet software,
care poate fi descarcat gratuit de la adresa indicata ın [Kloetzer and Ghita, 2011]. Rutinele
au fost implementatea si testate ın MATLAB 2010b ruland pe o platforma Windows 32 sau
64 de biti. De asemenea extensia metodelor de descompunere triunghiulara si poligonala sa
permita integrarea lor ın metodele de planificare cu sarcini complexe este detaliata.
3.4 Analiza comparativa a descompunerilor celulare
Scopul acestei sectiuni este de a furniza o metoda care poate fi utilizata ın alegerea
descompunerii celulare care sa conduca la cele mai bune solutii pentru o problema data.
In acest scop Subsec. 3.4.1 furnizeaza o comparatie calitativa ıntre descompunerile celulare
studiate, iar Subsec. 3.4.2 include tendintele cantitative ale unor criterii de cost, calculate
utilizand implementarile din sectiunea precedenta.
3.4.1 Analiza calitativa
Aspectul calitativ poate fi utilizat ın excluderea descompunerilor care nu au o anumita
proprietate necesara ın solutionarea problemei data. In aceasta analiza au fost consider-
ate patru aspecte diferite pe care le vom enumera ın continuare cu rezumatul concluziilor
aferente:
(i) Celule care au ın comun exact aceeasi fateta - este o proprietate a descompunerilor
triunghiulara si poligonala, proprietatea fiind utila atunci cand se doreste proiectarea
unui controler dupa reactie continuu ın fiecare celula
3.4. Analiza comparativa a descompunerilor celulare 10
(ii) Extensia la spatii de dimensiune mai mare - descompunerea poligonala si dreptunghi-
ulara pot fi generalizate direct la spatii de dimensiune.
(iii) Celule mici ımprastiate aleator - descompunerile trapezoidala, poligonala si dreptunghi-
ulara tind sa aiba un procent mare de celule cu suprafata mica. Celulele cu suprafata
mica pot fi dezavantajoase atunci cand controlul robotului mobil este proiectat cu o
lege de control dupa reactie pentru fiecare celula.
(iv) Harti ale mediului imprecise - datorita constructiei sale, descompunerea poligonala este
afectata de mici modificari ale mediului.
3.4.2 Analiza cantitativa
In cazul ın care aspectele calitative prezentate ın Subsec. 3.4.1 lasa multiple descompuneri
ce pot constitui optiuni fezabile, comparatiile din aceasta subsectiune confera o informatie
cantitativa cu privire la aspectele legate de fiecare descompunere. Pentru masurarea valorilor
criteriilor de cost, au fost considerate un numar de obstacole cuprinse ıntre 1 la 10, si pentru
fiecare numar i au fost generate 1000 de medii aleatoare. Pentru fiecare numar de obstacole,
valorile medii ale celor 1000 de teste au fost calculate, pentru fiecare criteriu de cost si pentru
fiecare descompunere. Criteriile de cost cosiderate vor fi eunumerate ın continuare incluzand
scurte comentarii pentru unele dintre ele:
(i) Numarul total de celule, |Q| - Fig. 3.1 (a): tendinta reprezentata arata ca numarul de
celule generate de descompunere poligonala creste cu numarul de obstacole mult mai
abrupt decat ın oricare din celelalte descompuneri.
(ii) Timpul de executie: au fost obtinuti prin efectuarea descompunerilor pe o masina de
calcul cu performante medii (procesor Dual Core 2GHz, 4GB RAM).
(iii) Numarul relatiilor de adiacenta,
(iv) Suprafata medie a celulelor descompunerilor,
(v) Deviatia standard a ariei celulelor,
(vi) Compactitatea celulelor (Fig. 3.1 (b)) este o masura a calitatii formei celulelor de-
scompunerii [Chang et al., 2001]. Compactitatea unei celule este definita ca raportul
4πcellarea{cell2perimetrul. In ceea ce priveste compactitatea descompunerea dreptunghi-
ulara este cea cu cele mai bune rezultate urmata de cea poligonala.
3.5. Concluzii 11
Trapezoidală
PoligonalăRectangulară
Număr de obstacole
(a)
Trapezoidală
PoligonalăRectangulară
Număr de obstacole
Com
pact
itate
a ce
lule
lor
(b)
Figura 3.1: Criteriile semnificative pentru compararea descompunerilor celulare obtinute prinefectuarea de teste asupra 1000 de medii generate aleator pentru fiecare numar de obstacolecuprins ıntre 1 si 10.
(vii) Diferenta rezultata ın numar de celule atunci cand aceeasi descompunere este efectuata
pentru acelasi mediu, dar ın cazul ın care varfurile obstacolelor sunt afectate printr-un
zgomot mic aditiv. Acest criteriu de cost este o masura a robustetii partitionarii la
mici schimbari ın mediu (datorat achizitiei senzoriale).
(viii) Procentul de celule mici: descompunerile triunghiulara si trapezoidala au, ın general,
procent scazut de celule mici, ın timp ce descompunerea poligonala are un procent
redus numai pentru cazul ın care sunt considerate unul sau doua obstacole.
3.5 Concluzii
Problema constructiei descompunerii celulare pentru un mediu dreptunghiular presarat
cu obstacole poligonale a fost studiata ın debutul acestui capitol. Au fost considerate patru
descompuneri celulare, rezultatul algoritmilor propusi fiind o multime de celule poligonale
convexe. Detalii de implementare ale descompunerilor considerate, si totodata, pseudo-
codul algoritmilor si exemple ilustrative sunt descrise. Implementarea pachetului software
care include descompunerile prezentate este utilizat ın comparatia tipurilor de descompunere
celulare. Criterii calitative si cantitative sunt propuse, rezultatele prezentate pot fi adaptate
pentru probleme usuale din practica. Implementarea descompunerilor celulare si valorile
numerice ale criteriilor prezentate sunt implementate ca un pachet MATLAB ce poate fi
descarcat de la adresa indicata ın [Kloetzer and Ghita, 2011].
Capitolul 4
Problema de planificare clasica
Un algoritm de planificare discreta a miscarii pentru roboti mobili, de regula, este alcatuit
din patru parti: ın prima instanta mediul este abstractizat la o multime finita, ceea de a doua
este reprezentata de algoritmul de planificare propriu-zis ın care se determina o secventa de
stari intermediare ıntre configuratia initiala si cea finala prin care robotul trebuie sa treaca,
ın cea de a treia se genereaza o traiectorie care sa conduca robotul prin regiunile determinate
anterior, iar ın ultima etapa se determina secventa de comanda care aplicata robotului sa
fie urmarita traiectoria gasita ıntr-un mod cat mai fidel.
4.1 Introducere
In cazul ın care asupra robotului actioneaza constrangeri de miscare de tip nonholonomice
atunci o atentie deosebita trebuie acordata modului ın care este construita traiectoria (ea
trebuie sa poata fi urmata fizic de robot). Problema clasica de navigare pentru roboti de tip
masina se formuleaza astfel:
Problema 4.1 Fiind dat un robot de tip masina care poate evolua ıntr-un mediu dreptunghi-
ular E, o pozitie initiala si una finala, sa se gaseasca o strategie de control care sa conduca
robotul ın pozitia finala fara a intra ın coliziune cu obstacolele.
4.2 Solutionarea VRP clasica
In solutionarea Prob. 4.1 se face asumptia ca orientare initiala a robotului poate fi aleasa
ın timp ce orientarea finala nu reprezinta interes. Algoritmul de planificare si control care
sa rezolve problema propus este alcatuit din patru parti si anume: abstractizarea mediului,
planificarea, generarea traiectoriei si controlul sau urmarirea traiectoriei (path following).
12
4.3. Complexitatea algoritmilor de planificare bazati pe descompunerea celulara 13
Abstractizarea: Abstractizarea unui mediu dreptunghiular se face dupa metodele
prezentate ın Sec. 3.2.
Planificarea: Apeland un algoritm de cautare de cost minim pe graful asociat sis-
temului, plecand din nodul qo si finalizand ın nodul qf , se obtine o succesiune de regiuni
adiacente.
Generarea traiectoriei: In prima instanta este construita o traiectorie angulara Pang
din mijloacele fatetelor comune regiunilor adiacente furnizate de algoritmul de cautare.
Deoarece traiectoria Pang nu poate fi urmata de robot, este netezita introducand arce de cerc
ıntre segmentele componente, raza acestora fiind restrictionata inferior de unghiul maxim de
comanda a rotilor viratoare.
Testul de fezabilitate: Testarea fezabilitatii se face pentru fiecare segment al traiec-
toriei netede aproximand aria maturata de robot cu un poligon, similar abordarii propusa
ın [Scheuer and Laugier, 1998], si rezolvand apoi o problema LP (Linear programming).
Algoritmul propus pentru solutionarea problemei de planificare gaseste iterativ o traiec-
torie angulara, una neteda si testeaza fezabilitatea traiectoriei netede. Daca traiectoria
neteda curenta este fezabila va fi folosita ca traiectorie de referinta, ın caz contrar sunt elim-
inate arcele corespunzatoare secventelor care conduc la imposibilitatea construirii traiecto-
riei fezabila din graful asociat sistemului. Pentru noul graf procedura este reiterata pana
la gasirea traiectoriei care solutioneaza Prob. 4.1 sau la declararea problemei nefezabila, ın
cazul ın care starea initiala devine deconectata de cea finala ın graf.
Urmarirea traiectoriei Pentru controlul robotului de tip masina astfel ıncat urmarirea
traiectoriei furnizata de algoritmul de planificare sa fie cat mai fidela este utilizata o adaptare
a abordarii vehiculului virtual.
Metoda de planificare si control este implementata ın MATLAB sub forma unui pachet
software, care poate fi descarcat de la adresa indicata ın [Ghita and Kloetzer, 2011].
4.3 Complexitatea algoritmilor de planificare bazati pe
descompunerea celulara
Sectiunea surprinde aplicabilitatea criteriilor descrise ın Sec. 3.4 pe cazul concret al
algoritmului de planificare prezentat ın Sec. 4.2. Complexitatea computationala (ın spatiu
si timp) a algoritmului este influentata ın principal de doi factori: de numarul de celule
rezultate ın urma partitionarii si de numarul de iteratii ale algoritmului pana la gasirea
solutiei, respectiv, ın cazul ın care una nu este gasita, la declararea problemei ca fiind
nefezabila.
In determinarea descompunerii care sa conduca la cele mai bune solutii pentru anumite
4.3. Complexitatea algoritmilor de planificare bazati pe descompunerea celulara 14
Număr de obstacole
Trapezoidală
PoligonalăRectangulară
Tim
pul d
e ex
ecuţ
ie a
l Alg
orit
mul
ui 3
(a)
Trapezoidală
PoligonalăRectangulară
Număr de obstacole
Pro
cent
aj d
e tr
aiec
tori
i fez
abil
e gă
site
(b)
Figura 4.1: Timpul scurs pana la gasire solutiei (a) (reprezentarea grafica pentru descom-punerea trapezoidala este identica cu cea dreptunghiulara), procentul de traiectorii gasite(b)
scenarii este definita functia de cost JDi,j care integreaza criteriile (i), (vi), (vii) si (viii) din
Subsec. 3.4.2. Pentru a compara evolutia functiei de cost, pentru mediile si descompuner-
ile prezentate in capitolul anterior, valorile medii ale lui JDi,j sunt calculate pentru un set
de scenarii propuse. Parametrii implicati ın JDi,j permit integrarea particularitatilor prob-
lemelor ın functia criteriu. Functia de cost JDi,j trebuie privita ca un criteriu numeric utit ın
determinarea descompunerii care ar putea conduce la cele mai bune solutii.
Pentru a determina calitatea analize propuse sunt efectuate teste cu privire la calitatea
solutiilor ıntoarse de algoritmul de planificare pentru aceleasi medii generate aleator. In-
vestigarea acestui aspect impune calculul procentajului de cazuri pentru care algoritmul
solutioneaza problema, si intervalul de timp necesar algoritmului sa se termine de executat
(Fig. 4.1). Timpii de rulare au fost obtinuti ruland implementari sub mediul Matlab pe un
PC cu performante medii (procesor Intel i3 la 2.13 GHz, 3GB RAM). Analizand Fig. 4.1
(a), putem trage concluzia ca descompunerea dreptunghiulara este cea mai eficienta pentru
cazul nostru, deoarece gaseste o traiectorie fezabila aproape de fiecare data, ıntr-un timp
foarte scurt.
Functii de cost CDi,j este construita sa incorporeze atat functia de cost JDi,j cat si rezultatele
prezentate ın Fig. 4.1 (a) si (b). Functia de cost CDi,j trebuie privita ca o nota obtinuta de de-
scompunere, pentru diversele situatii propuse, functie de calitatea solutiei Prob. 4.1 furnizata
de algoritmul de planificare. Utilitatea celor doua functii de cost este demostrata prin simu-
lari sub mediul MATLAB. Concluziile rezultate ın urma simularilor sunt: algoritmul prezen-
tat ın Sec. 4.2 are cele mai bune sanse de gasire a traiectoriei fezabila daca este utilizata
4.4. Concluzii 15
descompunerea dreptunghiulara pentru abstractizarea mediului, si, ın implementarile reale
ın care achizitia pozitiie obstacolelor se face senzorial, utilizarea descompunerii triunghiulare
ar conduce la solutia ce mai robusta.
4.4 Concluzii
Noutatea solutiei propusa pentru solutionarea VRP clasica pentru roboti de tip masina
consta ın dezvoltarea unei proceduri iterative automatizata care furnizeaza o traiectorie
neteda bazata pe metodele de descompunere celulara a mediului iar conexiunile dintre seg-
mente au ca sursa de inspiratie solutia propusa de Dubins. Cu toate ca metoda propusa de
noi nu este completa, existand cazuri cand solutia nu poate fi gasita, are avantajul unui cost
computational redus. Totodata analiza comparativa asupra performantelor solutiei propuse
ın raport cu metoda de descompunere celulara utilizata, ımpreuna cu modul de constructie
a functii de cost, a carei valoare numerica reprezinta o masura a potrivirii ıntre algoritmul
de planificare si metoda de descompunere. Algoritmul de planificare este implementat ın
forma unui algoritm complet computational implementat ın MATLAB, care poate fi gasit la
adresa specificata ın [Ghita and Kloetzer, 2011].
Capitolul 5
Problema de planificare cu sarcini
complexe
Logica Lineara Temporala (LTL) permite utilizatorului posibilitatea de a exprima specifi-
catii bogate apropiate de cele din limbajul natural ca o combinatie de propozitii atomice unite
prin conectorii Booleeni si temporali. In teza au fost considerate sarcinile de miscare pentru
roboti mobili date sub forma de formule LTL ce nu contin operatorul urmator, denumite
formule LTL�X .
5.1 Introducere
Problema de planificare LTL�X pentru roboti de tip masina se formuleaza dupa cum
urmeaza:
Problema 5.1 Fiind data o sarcina de miscare ın forma unei formule LTL�X , φ, peste
un set de regiuni Π, sa se gaseasca o strategie de control pentru robotul de tip masina care
maximizeaza probabilitatea ca formula φ sa fie satisfacuta.
5.2 Solutionarea problemei de planificare LTL�X
Abordarea propusa ın aceasta sectiune, pentru solutionarea Prob. 5.1, urmareste urmatorii
trei pasi. (i) Mediul si regiunile de interes sunt partitionate utilizand metode de descom-
punere celulara. (ii) Capabilitatile de miscare ale robotului ın mediu partitionat sunt ab-
stractizate ıntr-un sistem de tranzitie Markovian T . (iii) Formula LTL�X este convertita
ıntr-un automat Buchi B, produsul automat dintre T si B fiind apoi efectuat. Rularea
acceptata din acest produs, cea cu probabilitatea maxima de a satisface formula φ, este
16
5.2. Solutionarea problemei de planificare LTL�X 17
proiectata ıntr-o rulare a lui T , peste care se proiecteaza strategia de control pentru robotul
de tip masina.
5.2.1 Constructia sistemului de tranzitie T
Dificultatea constructiei lui T consta ın a determina probabilitatea tranzitiilor dintre
starile sale (P). Este propusa metoda de calculul a probabilitatii Ppqi, qjq de tranzitie
directa din starea qi ın starea qj , @qi, qj P Q. In mod evident Ppqi, qjq � 0 daca starile qi si
qj nu sunt adiacente, i.e. qj R δpqiq, si Ppqi, qjq � 1 daca qi � qj (ın acest caz, oprind robotul
ın celula qi este garantata tranzitia dorita).
Cazul general, ın care, qj P δpqiq este tratat determinandu-se numarul de cazuri N i,jctrl
pentru care este posibila conducerea robotului din celula qi ın qj. Notand cu N i,j numarul
total de secvente de patru stari q1 qi qj q”, ın care q1 P δpqiqztqju si q” P δpqiqztqju posibile
si verificand existenta traiectoriilor angulare si netede pentru toate cele N i,j cazuri, urmand
algoritmul descris ın Sec. 4.2, este determinat N i,jctrl (cu N i,j
ctrl ¤ N i,j). In al doilea pas
al constructiei Ppqi, qjq, sunt determinate numarul N i,jfeas de cazuri pentru care ın timpul
miscarii din qi ın qj toate regiunile din Πzthpqiq Y hpqjqu sunt evitate. In final Ppqi, qjq fiind
modelat de 5.1.
Ppqi, qjq �
$''''&''''%
�N i,j
feas
N i,j
p1�2�pN i,jctrl�N
i,jfeasqq
,daca qj P δpqiq
1 ,daca qi � qj
0 ,daca qj R δpqjq
(5.1)
5.2.2 Gasirea unei rulari a lui T
Pentru a gasi o rulare a lui T ce satisface formula LTL�X , φ, produsul automat AP
ıntre T si automatul Buchi corespunzator lui φ este construit. Definind functia de cost LA
peste tranzitiile lui AP ca fiind: LA : SA � SA Ñ r0 � 8q, ın care LA ppqi, sjq, pqk, slqq �
� log pPpqi, qkqq daca Ppqi, qkq ¡ 0, si LA ppqi, sjq, pqk, slqq � �8 ın caz contrar, se poate
utiliza un algoritm de cautare de cost minim ın determinarea secventei de stari care maxi-
mizeaza probabilitatea de satisfacere a formulei avand ın vedere proprietatile logaritmului.
5.2.3 Algoritmul PLTLCon Car Like
Algoritmul PLTLCon Car Like cauta iterativ o rulare optima a lui T ce satisface for-
mula φ, apoi bazandu-se pe aceasta rulare, traiectoria neteda ce poate fi urmata de robot
este determinata, sau ın cazul ın care una cu o probabilitate suficient de mare de a satisface
5.3. Reducerea complexitatii ın planificarea LTL�X 18
formula φ nu poate fi gasita, Prob. 5.1 este declarata nefezabila. Fezabilitatea algoritmul
propus este testat prin simulari sub mediul MATLAB.
5.3 Reducerea complexitatii ın planificarea LTL�X
Avand ın vedere rezultatele referitoare la controlabilitatea sistemelor afine ın medii
partitionate, problema de planificare LTL�X pentru echipa de roboti este formulata ast-
fel ıncat modelarea agentilor apartinand echipei sa fie facuta ıntr-un sistem de tranzitie
dupa stare finit T i:
Problema 5.2 Sa se gaseasca o rulare pentru orice T i, de asa maniera ıncat secventa de
observatii generata de multimea celor n sisteme de tranzitie sa satisfaca formula LTL�X .
Sincronizarea ıntre cele n rulari este obtinuta ca parte componenta a solutiei. Informal
sincronizarea va preveni miscari prea rapide, astfel ıncat sa se evite schimbarea starii curente
ınainte ca ceilalti roboti sa ajunga ın regiunile de interes care ar contribui la ındeplinirea
formulei LTL�X .
Complexitatea solutiei propuse ın [Kloetzer and Belta, 2010]
Limita superioara pentru numarul de stari ale sistemului de tranzitie asociat echipei de
roboti P a solutiei din [Kloetzer and Belta, 2010] este data de:
|P | ¤p|T i|qn
pnq!|Π|2|Π| (5.2)
O traiectorie optimala ın P este gasita prin utilizarea unui algoritm de cost minim, cum
ar fi Dijkstra; pentru gasirea acesteia, rezultand o complexitate a cautarii de ordinul Op|P |2q.
5.3.1 Modelul brut al robotului
In loc de a utiliza direct sistemul de tranzitiei T i, este propus utilizarea unui sistem
sintetizat cu mai putine stari. Definind o relatie de echivalenta α ıntre starile sistemului T i
se induce o sinteza a lui T i rezultand un sistm de trazitie sintetizat T i{α cu mai putine stari
decat T i. T i{α este o reprezentare bruta a sistemului de tranzitie T i si a capabilitatilor de
miscare ale robotului i, ın sensul ca nu se pot pondera tranzitiile din δα cu un cost dependent
de distanta parcursa sau de numarul de celule vizitate.
5.4. Concluzii 19
5.3.2 Rulari individuale
Sistemele T i{α, i � 1, . . . , n, vor fi folosite pentru constructia unei reprezentari globale G
a ıntregii echipe de roboti. Aceasta constructie este similara celei din [Kloetzer and Belta, 2010],
cu diferenta ca sunt utilizate sisteme de tranzitie de dimensiune mai mica si este permisa
existenta mai multor sisteme de tranzitie ın aceeasi stare. Utilizand abordarea propusa
ın [Kloetzer and Belta, 2008] este gasita o rulare a lui G care sa satisfaca formula LTL�X
impusa. In final rularea obtinuta este proiectata ın rulari individuale ale T i{α.
5.3.3 Experiment
Abordarea propusa este testata ın MATLAB printr-un exemplu, considerand patru
roboti complet actionati ce evolueaza ıntr-un mediul dreptunghiular ın care sunt definite cinci
regiuni de interes si o sarcina de miscare impusa. Timpul computational necesar obtinerii
solutiei este de aproape 2 sec., pe o masina de calcul cu performante medii (procesor Dual
Core 2GHz, 4GB RAM), utilizand abordarea propusa. Solutia obtinuta nu este optima ın
mod evident, d.p.d.v al numarului de stari vizitate de echipa de roboti, dar pentru a obtine
solutia optimala ar trebui utilizata abordarea din [Kloetzer and Belta, 2010], care ar avea
ca rezultat un sistem de tranzitie G 105 de stari. Timpul computational ın aceasta situatie
ar fi de mai bine de 50 h pentru crearea lui G si gasirea solutiei optimale!
5.4 Concluzii
In prima parte a capitolului solutia problemei de planificare a miscarii cu sarcini complexe
date ın forma unei formule LTL�X pentru WMR asupra carora actioneaza constrangeri
de miscare este prezentata. Cu toate ca abordarea propusa pentru solutionare problemei
de planificare cu sarcini complexe, prezentata ın Sec. 5.2, nu este completa, ea furnizeaza
traiectoria care maximizeaza probabilitatea de a satisface formula impusa considerand ca un
robot cu dimensiune fizica neneglijabila si asupra caruia actioneaza constrangeri de miscare
o va urma.
Solutia sub-optimala propusa ın Sec. 5.3 induce o reducere a complexitatii solutiei prob-
lemelor de planificare a miscarii cu sarcini complexe pentru sistemele multi robot bazate pe
specificatii LTL�X ce face posibila utilizarea abordarii ın medii dinamice.
Capitolul 6
Planificarea vizuala a miscarii din
imagini omnidirectionale
Un algoritm SLAM dupa cum reiese si din denumire este alcatuit din doi algoritmi:
primul, denumit SfM (Structure from Motion), reconstruieste 3D mediul dintr-un set de
imagini achizitionate (mapare), si unul care determina pozitia de la care s-a produs achizitia
imaginilor (localizarea). Utilizarea senzorilor optici atat pentru mapare cat si pentru lo-
calizare este o optiune fezabila deoarece se depaseste problema sincronizarii existenta ın
orice sistem senzorial. Algoritmii SfM existenti au la iesire o structura denumita nor de
puncte si nu o reprezentare geometrica a mediului, fiind inutilizabili ın abordarile standard
din planificare miscarii WMR.
6.1 Introducere
In determinarea hartii se face presupunerea ca mediul este marginit, static si presarat cu
obstacole poligonale. Asumptiile facute asupra mediului raman valabile si pentru algoritmul
de planificare prezentat ın finalul capitolului. Mediile dinamice pot fi integrate ın metoda
de mapare si planificare daca schimbarile ın mediu nu sunt prea rapide, ın acest caz sistemul
de tranzitie care va modela mediul ın care activeaza robotul, se va modifica lent, premitand
astfel modelarea si integrarea informatiilor ın controlul robotului.
6.2 Reconstructia 2D a mediului
Algoritmul propus pentru reconstructia 2D a mediului la nivel intuitiv are urmatoare
functionalitate: avand o harta initiala (care poate fi total necunoscuta) si o imagine, este
determinata pozitia la care a fost achizitionata imaginea, sunt extrase liniile verticale din
20
6.3. Planificarea vizuala a miscarii 21
imagine si liniile ce definesc frontiera spatiul liber de miscare. Din intersectia liniilor verticale
cu limitele planseului inferior sun extrase pozitiile varfurilor obstacolelor (plecand de le
premiza ca obstacolele sunt asezate pe planseul inferior). Prin integrarea noilor informatii
peste harta deja cunoscuta, rezulta o harta actualizata ce include si informatiile achizitionate
din imaginea curenta. Acesta procedura este iterata pentru fiecare imagine achizitionata.
Algoritmul de reconstructie poate fi rulat ın doua moduri: off-line, atunci cand este
determinat un set de imagini ıntr-o faza de explorarea condusa de utilizator, ın acest caz
algoritmul primeste la intrare multimea de imagini achizitionate iar la iesire de cele mai
multe ori va avea o harta incompleta a mediului ın care robotul activeaza. In cazul ın care
algoritmul este rulat online, achizitionarea imaginilor se face ın timpul deplasarii robotului
ın rezolvarea sarcinilor impuse, fiecare achizitie declansand o iteratie a algoritmul de asa
maniera ıncat harta sa fie completata cu fiecare imagine achizitionata.
6.3 Planificarea vizuala a miscarii
Sectiunea prezenta o abordare noua de solutionarea a problemei de planificare Dubins
(Prob. 6.1) ce considera robotul avand o dimensiune fizica neneglijabila si activand ıntr-un
mediu dreptunghiular presarat cu un set de obstacole poligonale.
Problema 6.1 (Problema Dubins:) Fiind dat un robot de tip masina si doua configuratii
una initiala si una finala, sa se gaseasca o strategie de control care sa conduca robotul ıntre
cele doua configuratii dupa o traiectorie continua fara varfuri (cusps).
Pe parcursul acestei sectiuni vom numi problema Dubins Prob. 6.1 completata cu specifica-
tiile mentionate ın primul paragraf al sectiunii curente. Solutia problemei Dubins propusa,
poate fi adaptata relativ usor la cazul WMR fara constrangeri de miscare ca un caz particular
al robotului de tip masina.
Un prim pas al algoritmului este constructia grafului de visibilitate tangential (graf - T)
ce abstractizeaza mediului ın care activeaza robotul la o multime discreta tinand cont de
dimensiunea robotului. Graful - T este construit utilizand o abordare similara celei propuse
ın [Liu and Arimoto, 1991], ın care se considera raza cercurilor tangentiale data de latimea
robotului. Traiectoria de lungime minima PTG generata ın solutionarea problemei impuse
utilizand algoritmul de cautare A*, pe graful - T obtinut, va asigura o miscare lipsita de
coliziuni pentru un robot rotund si complet actionat.
Dar PTG nu respecta constrangerile de miscare ale robotului de tip masina. Pentru a
genera o asfel de traiectorie, pentru fiecare cerc ce defineste un arc ın PTG, mai putin primul
si ultimul, sunt introduse cercuri de raza Rm (care ıi respecta constrangerile de miscare)
6.4. Concluzii 22
tangente cercurilor ce definesc PTG. Cercurile plasate sunt unite prin tangente, rezultand o
traiectorie P 0TG care respecta constrangerile de miscare care actioneaza asupra robotului dar
pentru care nu este garantata fezabilitatea.
Traiectoriei fezabila P FezTG este construita din P 0
TG iterand pentru fiecare element al sau,
de forma segment de dreapta si arc de cerc, urmatorii doi pasi:
• Pasul 1: se asigura o miscare lipsita de coliziuni ın timpul deplasarii pe arcul de cerc
curent introducand iterativ cercuri cu raza Rm de fiecare data cand ın deplasarea pe
cercul curent adaugat este detectata coliziunea. Pasul 1 are ca rezultat o traiectorie
fezabila, alcatuita din arce de cerc si segmente de dreapta, corespunzatore arcului de
cerc curent din traiectoria P 0TG.
• Pasul 2: consta ın interconectarea traiectoriei determinata la Pasul 1 de restul traiec-
toriei P FezTG print-un segment de dreapta dat de tangenta ce uneste ultimul cerc din
P FezTG de ultimul cerc adaugat la Pasul 1 si ın asigurarea fezabilitatii segmentului nou
introdus. Fezabilitatea este asigurata testand intersectia ariei maturata de robot ın de-
plasarea ın lungul segmentului nou introdus cu obstacolele, iar ın cazul unei intersectii
nevide nodul inclus ın aria maturata de robot este adaugat ın traiectoria P 0TG precedand
nodul curent.
6.4 Concluzii
In debutul capitolului este prezentat un algoritm de mapare 2D a mediilor poligonale
din imagini omnidirectionale. Abordarea propusa are neajunsul unui procedeul de extractie
a planseului inferior care nu poate fi aplicat pentru alte tipuri de texturi. Un alt dezavantaj,
mostenit ca urmare a utilizarii tensorului trifocal 1D ın determinarea pozitiei robotului la
momentele achizitie, este acela ca eroarea cumulativa este dependenta de unghiurile dintre
pozitiile de achizitie ale imaginilor.
Algoritmul de mapare ruland pe masina de calcul cu performante medii (procesor Intel
i3 3 GB RAM) necesita mai putin de 2 secunde pentru integrarea informatiei extrasa dintr-o
imagine de dimensiune 600x600 pixeli ın harta mediului cunoscuta. Aceste ultime mentiuni
implica faptul ca abordarea ar putea fi utilizata ın aplicatiile de timp real.
Cea de a doua parte a capitolului prezinta o metoda de planificare bazata pe grafuri
tangentiale de vizibilitate pentru roboti asupra carora actioneaza constrangeri de miscare si
care au o dimensiune fizica. In timpul deplasarii pe traiectoria determinata apriori, harta
poate fi actualizata cu informatiile extrase cu fiecare imagine achizitionata iar traiectoria
6.4. Concluzii 23
recalculata cu fiecare obstacol ce apare pe traiectorie, prin oprirea robotului si reiterarea
algoritmului de planificare.
Complexitatea algoritmului de planificare ın solutionarea problemei Dubins este de or-
dinul Opn6q, ın care n - este numarul de varfuri ce definesc obstacolele. Ordinul de com-
plexitate permite utilizarea algoritmului online atata timp cat numarul de noduri nu este
prea mare. O alta remarca ce trebuie facuta este aceea ca algoritmul de planificare va gasi
o solutie apropiata de geodezic, constructia traiectoriei plecand de a traiectoria de lungime
minima obtinuta considerand robotul complet actionat.
Capitolul 7
Concluzii finale si directii viitoare de
cercetare
Obiectivul central al lucrarii a constat ın a aduce un plus de robustete solutionarii VRP
prin integrarea dimensiunii si a constrangerilor de miscare ale robotului ın procedura de
planificare. In plan secund a fost tratata problema integrarii abordarilor teoretice din plan-
ificarea miscarii WMR ın sistemele senzoriale reale de asa maniera ıncat sisteme autonome
rezultate sa fie fezabile.
7.1 Contributii
Principalele contributii ale lucrarii graviteaza ın jurul domeniilor:
• Descompunerea celulara
– a fost dezvoltat un pachet software unitar, axat pe problemele din robotica, pentru
efectuarea celor mai frecvent utilizate descompuneri celulare - pachetul poate fi
descarcat gratis de la adresa indicata ın [Kloetzer and Ghita, 2011].
– este condus un studiu comparativ, experimental asupra performantelor descom-
punerilor celulare. Rezultatele obtinute sunt indicate a se utiliza ın alegerea de-
scompunerii celulare care sa se asocieze cat mai bine ın solutionarea unei probleme
date.
• Solutionarea problemei clasice de planificare pentru roboti de tip masina
– sunt prezentate doua solutii ale problemei de planificare clasice pentru roboti de
tip masina ce iau ın considerare dimensiunea neneglijabila a robotului.
24
7.2. Directii de cercetare deschise 25
– prima solutie, prezentata ın Cap. 4, are avantajul unui cost computational scazut
dar abordarea nu este completa. Un aspect important este acela ca abordarea
poate fi integrata ın solutionarea problemelor de planificare cu sarcini complexe.
– cea de a doua solutie, propusa ın finalul Cap. 6, rezolva problema Dubins con-
siderand robotul modelat geometric printr-un dreptunghi. Traiectoria generata
este ın general apropiata de geodezic, solutia este completa si poate fi utilizata ın
medii cunoscute partial sau chiar necunoscute, calitatea solutiei depinzand ınsa
de masura ın care mediul este cunoscut.
• Solutionarea problemei cu sarcini complexe
– solutia problemei de planificare cu sarcini complexe pentru roboti de tip masina ce
au dimensiune neneglijabila, sarcinile de miscare fiind date ın forma unei formule
LTL�X este prezentata ın Cap. 5.
– partea secunda a Cap. 5 include o metoda de reducere a complexitatii solutiei
problemei de planificare cu sarcini complexe pentru echipe de roboti. Reducerea
costului computational are drept pret obtinerea unei solutii neoptimale.
• Maparea din imagini omnidirectionale a mediilor poligonale
– este prezentata o abordare care produce o reconstructie 2D CAD a mediului
considerat poligonal si static. O astfel de modelarea a mediului este de cele mai
multe ori suficienta ın cazul VRP deoarece miscare se desfasoara de obicei ın plan.
7.2 Directii de cercetare deschise
• o prima directie de cercetare ar fi dezvoltarea solutiilor prezentate ın Cap. 4 si 5 pentru
roboti de tip masina, ın sensul garantarii unor algoritmi completi. Solutiile ar putea
include mai multe strategii de control care sa asigure constructia traiectoriei netede
din cea angulara.
• o alta directie de cercetare poate fi dezvoltarea solutiei problemei de planificare cu
sarcini complexe pentru echipe de roboti de tip masina.
• abordarea propusa ın reconstructia 2D CAD a mediului nu este generala, ea putand fi
utilizata doar ın cazul ın care planseul inferior are o anumita textura. Dezvoltarea unei
metode care sa extraga frontiera planseului inferior indiferent de textura la cresterea
portabilitatii procedurii de reconstructie.
Bibliografie
[Aranda et al., 2010] Aranda, M., Lopez-Nicolas, G., and Sagues, C. (2010). Omnidirec-
tional visual homing using the 1D trifocal tensor. In IEEE International Conference on
Robotics and Automation, pages 2444–2450. 2.4
[Backer and Kirkpatrick, 2007] Backer, J. and Kirkpatrick, D. (2007). Finding curvature-
constrained paths that avoid polygonal obstacles. SCG ’07 Proceedings of the twenty-third
annual symposium on Computational geometry. 1
[Chang et al., 2001] Chang, C., Wenyin, L., and Zhang, H. (2001). Image retrieval based
on region shape similarity. In Society of Photo-Optical Instrumentation Engineers (SPIE)
Conference Series, volume 4315, pages 31–38. vi
[Choset et al., 2005] Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W.,
Kavraki, L. E., and Thrun, S. (2005). Principles of Robot Motion: Theory, Algorithms,
and Implementations. MIT Press, Boston. 1, 2.5
[Conner et al., 2007] Conner, D. C., Kress-Gazit, H., Choset, H., Rizzi, A. A., and Pappas,
G. J. (2007). Valet parking without a valet. In Proc. of the 2007 IEEE/RSJ International
Conference on Intelligent Robots and Systems, pages 572–577, San Diego, CA, USA. 1
[Egerstedt et al., 2001] Egerstedt, M., Hu, X., and Stotsky, A. (2001). Control of mobile
platforms using a virtual vehicle approach. IEEE Transactions on Automatic Control,
46(11):1777–1782. 2.3
[Gastin and Oddoux, 2001] Gastin, P. and Oddoux, D. (2001). Fast ltl to buchi automata
translation. In in Proceedings of the 13th Conference on Computer Aided Verifica-
tion(CAV2001), pages 53–65. Springer. 2.7
[Ghita and Kloetzer, 2011] Ghita, N. and Kloetzer, M. (2011). MATLAB package for solving
classical VRP for car-like robots. http://www.ac.tuiasi.ro/~n_ghita/. 4.2, 4.4
26
[Kloetzer and Belta, 2008] Kloetzer, M. and Belta, C. (2008). A fully automated framework
for control of linear systems from temporal logic specifications. IEEE Transactions on
Automatic Control, 53(1):287–297. 2.7, 5.3.2
[Kloetzer and Belta, 2010] Kloetzer, M. and Belta, C. (2010). Automatic deployment of
distributed teams of robots from temporal logic motion specifications. IEEE Transactions
on Robotics, 26(1):48–61. 5.3, 5.3.2, 5.3.3
[Kloetzer and Ghita, 2011] Kloetzer, M. and Ghita, N. (2011). CELLDECOMP - A
MATLAB package for constructing cell decompositions. http://www.ac.tuiasi.ro/
~kmarius/cell_decomp.zip. 3.3, 3.5, 7.1
[Latombe, 1991] Latombe, J. (1991). Robot Motion Planning. Kluwer Academic Publishers.
1, 2.5
[LaValle, 2006] LaValle, S. M. (2006). Planning Algorithms. Cambridge. Available at http:
//planning.cs.uiuc.edu. 1
[Liu and Arimoto, 1991] Liu, Y.-H. and Arimoto, S. (1991). Proposal of tangent graph and
extended tangent graph for path planning of mobile robots. In Proceedings of the 1991
IEEE Intemational Conferenceon Robotics and Automation, pages 312–317, Sacramento,
Califomia. 6.3
[Mei and Rives, 2007] Mei, C. and Rives, P. (2007). Single view point omnidirectional cam-
era calibration from planar grids. In IEEE International Conference on Robotics and
Automation. 2.4
[Puig, 2011] Puig, L. (2011). DLT-like Calibration of Central Catadoptric Cameras. http:
//webdiis.unizar.es/~lpuig/index.html. 2.4
[Scaramuzza et al., 2009] Scaramuzza, D., Martinelli, A., and Siegwart, R. (2009). A ro-
bust descriptor for tracking vertical lines in omnidirectional images and its use in mobile
robotics. International Journal on Robotics Research, 2(28). 2.4
[Scheuer and Laugier, 1998] Scheuer, A. and Laugier, C. (1998). Planning sub-optimal and
continuous-curvature paths for car-like robots. In IEEE/RSJ Int. Conf. on Intelligent
Robots and Systems, Victoria, BC (CA). 4.2
[Wolper et al., 1983] Wolper, P., Vardi, M., and Sistla, A. (1983). Reasoning about infi-
nite computation paths. In Proceedings of the 24th IEEE Symposium on Foundations of
Computer Science, pages 185–194. Ed. Tucson. 2.7
