Na egação Topológica Aplicada a
Agen es Robó icos Mó eis
Ped o Guilhe me San os Ca alho Bo ges Ramos
Coimb a, Se emb o de 2018
Na egação Topológica Aplicada a
Agen es Robó icos Mó eis
O ien ado :
P o esso Dou o Paulo Jo ge Ca alho Menezes
Co-O ien ado :
Dou o João Manuel Lei ão Quin as
Jú i:
P o . D . Rui Paulo Pin o da Rocha
P o . D . Jo ge Nuno de Almeida e Sousa Almada Lobo
P o . D . Paulo Jo ge Ca alho Menezes
Disse ação de Mes ado In eg ado em Engenha ia Elec o écnica e de Compu ado es,
amo de especialização em Au omação.
Coimb a, Se emb o de 2018
Ag adecimen os
Dedico es e ag adecimen o não só aos que me acompanha am no p esen e cu so, mas a odos
os que me acompanha am na minha ida académica e pessoal, e ajuda am na ealização des e
obje i o.
Em p imei o luga gos a ia de ag adece à minha amília, pa icula men e à pessoa dos
meus pais Guilhe me e Ma ia José e à minha i mã Diana pelo es o ço, apoio e incen i o ao
longo des e pe cu so. Ob igado po me da em semp e a mão nos momen os em que nem eu
ac edi a a em mim.
Ag adeço ao meu o ien ado , P o esso Dou o Paulo Menezes e ao meu co-o ien ado
Dou o João Quin as pelos conselhos, opiniões, dedicação, igo cien í ico e paciência os
quais pe mi i am o desen ol imen o des a disse ação. Ag adeço ambém aos meus colegas
de labo a ó io, em pa icula ao Gonçalo Ma ins pelo apoio e paciência com que semp e me
p esen eou. Aos meus es an es amigos po odos os momen os p opo cionados ao longo da
minha ida académica, e pela sua amizade e apoio ao longo da ida.
iii

i
Resumo
Ac ualmen e, na sociedade em que i emos, exis e uma c escen e necessidade de u iliza
obôs au ónomos pa a execu a di e en es a e as sem pe u ba o ambien e onde elas são
desempenhadas. Exis e uma g ande a iedade de obôs, como obôs guia ou obôs de se iço
e segu ança, desen ol idos pa a ajuda as pessoas a supe a as di iculdades sen idas na
ealização de di e en es ipos de a e as. Es es obôs es ão apidamen e a ganha um papel
impo an e no nosso dia-a-dia, e oluindo de me os abalhado es pa a companhei os. Es e
p ojec o isa c ia um obô ecepcionis a-guia, a se u ilizado no Ins i u o de Sis emas e
Robó ica da Uni e sidade de Coimb a. De modo a a ingi es e objec i o, desen ol emos
um sis ema que supo a a na egação de um obô em um ambien e conhecido, baseado nos
p incípios da na egação opológica. Fo am desen ol idas capacidades senso iais, de modo a
assim pode e i a obs áculos que possam apa ece ao longo da ajec ó ia. Pa a abo da
o ac o de que a es ima i a da posição do obô acumula e os ao longo do empo, um
conjun o de ma cado es isuais oi posicionado ao longo das ajec ó ias pa a auxilia na
localização do mesmo. Es es ma cado es isuais, o necem meios de posicionamen o em
elação a um sis ema de coo denadas globais, podendo es es se econhecidos numa ampla
gama de con igu ações de isualização. Es a é uma abo dagem simples, ba a a, obus a e
ácil de implemen a pa a a ob enção de uma localização global. De modo a in e agi com
o u ilizado , oi c iada uma in e ace g á ica, onde o u ilizado pode escolhe en e isi as
p é-planeadas ou i di e amen e a um de e minado local. Fo am ealizadas expe iências num
cená io cobe o, demons ando a iabilidade e desempenho do sis ema.
Pala as cha e: Odome ia, Na egação Topológica, Ma cado es Visuais, Des io
de Obs áculos, Robô de Se iços
i
Abs ac
In ou mode n socie y, he e is a g owing need o use au onomous obo s o execu e di e en
ypes o asks wi hou dis u bing he en i onmen whe e hey a e in oduced. The e is a wide
a ie y o obo s such as guide obo s o se ice and secu i y obo s, ha we e de eloped o
help people o e come hei di icul ies while pe o ming a mul i ude o di e en asks. Robo s
a e quickly ea ning an impo an ole in ou daily-li e, e ol ing om labo e s o companions.
This p ojec aims o c ea e a ecepcionis -guide obo o be used a he Ins i u e o Sys ems
and Robo ics, Uni e si y o Coimb a. To accomplish his goal, we ha e de eloped a sys em
ha suppo s he na iga ion o a obo in a known en i onmen , based on he p inciples o
opological na iga ion. In o de o a oid obs acles ha may appea along he ajec o y,
senso ial capabili ies we e added. To add ess he ac ha he es ima ion o he posi ion o
he obo accumula es e o h oughou ime, a se o isual ma ke s we e posi ioned along
he ajec o ies o aid in localizing he obo . These landma ks p o ide means o posi ioning
in e e ence o a global coo dina e sys em o e a wide ange o iewing con igu a ions. This
is a simple, inexpensi e, obus , and easy o implemen ap oach o global localiza ion. To
in e ac wi h he use a g aphical use in e ace was c ea ed we e he use can choose om
be ween p e-planned isi s o o go o a ce ain loca ion. We ha e pe o med expe imen s
in a indoo scena io, demons a ing he easibili y and pe o mance o he sys em.
Keywo ds: Dead Reckoning, Topological Na iga ion, Visual Ma ke s, Obs acle
A oidance, Se ice Robo
ii
xi

Lis a de Figu as
1.1 Segway RMP 200 ................................. 2
2.1 Compa ação en e mapas mé icos e opológicos. . . . . . . . . . . . . . . . . 8
2.2 Exemplo do mapeamen o em g elhas de ocupação. . . . . . . . . . . . . . . . 8
2.3 Ilus ação do Alpha puzzle benchma k. . . . . . . . . . . . . . . . . . . . . . 9
2.4 Compa ação en e a pesquisa ealizada pelo algo i mo Dijks a e o algo i mo
A∗.......................................... 10
3.1 Compa ação en e o Bug-1 e o bug-2. . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Compa ação en e o Dis -bug e o IBA. . . . . . . . . . . . . . . . . . . . . . 16
3.3 Diag ama pola do algo i mo Bubble Rebound . . . . . . . . . . . . . . . . . 17
3.4 Rep esen ação da o ça a ac i a i ual . . . . . . . . . . . . . . . . . . . . 18
3.5 Rep esen ação da ans o mação en e o e e encial mundo e o e e encial da
pla a o mamó el.................................. 19
3.6 Sona HC-SR04.................................. 20
3.7 Senso de in a e melhos Sha p GP2Y0A02YK0F . . . . . . . . . . . . . . . 20
3.8 Compa ação en e a cu a de espos a do senso dada pelo ab ican e e da
cu aapósacalib ação. ............................. 21
3.9 Ajus e da cu a de espos a do senso de in a e melhos. . . . . . . . . . . . 21
3.10 Disposição dos senso es na pla a o ma mó el. . . . . . . . . . . . . . . . . . 23
3.11 Diag ama ep esen a i o da con ibuição dos ec o es epulsi os e a ac i o
pa a o calculo de uma no a di ecção de mo imen o. . . . . . . . . . . . . . . 24
3.12 Diag ama ep esen a i o da in eg ação do módulo de des io de obs áculos. . 26
4.1 Exemplo da codi icação biná ia dos ma cado es isuais. . . . . . . . . . . . . 30
4.2 Desc ição dos ma cado es u ilizados. . . . . . . . . . . . . . . . . . . . . . . 30
4.3 Ilus ação do modelo de câma a pinhole. .................... 31
4.4 Ilus ação dos di e en es pa âme os de uma câma a pinhole.......... 31
4.5 T ans o mações ealizadas a a és do uso dos pa âme os ex ínsecos e in ín-
secos......................................... 32
4.6 Ma cado isual colocado na pa ede do co edo do ISR. . . . . . . . . . . . 32
4.7 De ecção do ma cado isual. . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.8 Diag ama explica i o da ob enção da posição co igida da pla a o ma. . . . . 33
4.9 Diag ama explica i o das ans o mações necessá ias pa a a co ecção da es-
imaçãodaodome ia. .............................. 35
5.1 Vis a ge al dos módulos u ilizados. . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 Diag ama de ligações en e os di e en es nós de ROS. . . . . . . . . . . . . . 39
5.3 Máquina de es ados ep esen a i a do uncionamen o do módulo de na egação. 40
5.4 ComandoWii................................... 41
5.5 Exemplo de u ilização do p odu o in e no pa a a co ecção da di ecção a oma . 42
x
5.6 Supo e pa a os senso es de ul asom e de in a e melhos. . . . . . . . . . . . 43
5.7 Esquema de ligação dos senso es ao A duino. . . . . . . . . . . . . . . . . . . 43
5.9 Ilus ação do uncionamen o do planeado e in e acção com o módulo de na-
egação....................................... 44
5.8 Rep esen ação g á ica do mapa usado pelo planeado . . . . . . . . . . . . . . 45
5.10 Janela p incipal da in e ace g á ica. . . . . . . . . . . . . . . . . . . . . . . . 46
5.11 Janelas de escolha do si io des ino na in e ace g á ica. . . . . . . . . . . . . 46
5.12 Janelas in o ma i as do es ado do obô. . . . . . . . . . . . . . . . . . . . . . 46
6.1 Pe cu so ealizado du an e os es es expe imen ais . . . . . . . . . . . . . . . 48
6.2 Rep esen ação de uma das ajec ó ias ealizadas du an e os es es expe i-
men ais. ...................................... 50
6.3 E olução da posição do obô no eixo de coo denadas xey.......... 50
x i
Lis a de Tabelas
3.1 Qualidade da ap oximação da calib ação do senso . . . . . . . . . . . . . . . 22
3.2 Des asamen o e a anjo dos senso es. . . . . . . . . . . . . . . . . . . . . . . 22
6.1 Coo denadas xyz da posição dos ma cado es no e e encial do mundo. . . . . 48
6.2 Resul ados ob idos du an e a expe iência. . . . . . . . . . . . . . . . . . . . 49
6.3 E o na coo denada xem elação à igu a 6.3 (a), yem elação à igu a 6.3
(b) e xy em elação à igu a 6.2. . . . . . . . . . . . . . . . . . . . . . . . . . 51
x ii
Capí ulo 1
In odução
Es a disse ação desc e e e discu e o ema de "Na egação Topológica pa a Agen es Robó icos
Mó eis". O abalho oi desen ol ido no Labo a ó io de Robó ica Mó el si uado no Ins i u o
de Sis emas e Robó ica, Faculdade de Ciências e Tecnologia da Uni e sidade de Coimb a.
Exis e, cada ez mais, um c escen e núme o de obôs que abalham em p oximidade
com o se humano, in e agindo e ealizando a e as em pa ce ia com ele. O u u o passa po
uma elação simbió ica en e os dois mundos. Foi nes e âmbi o que es e p ojec o oi c iado,
endo como objec i o o desen ol imen o de um sis ema de supo e à na egação de um obô
num espaço conhecido, baseando-se pa a al nos p incípios de na egação opológica, c iando
assim o supo e básico pa a um obô guia. Es a abo dagem di e e da na egação geomé ica
usual, no ac o de que os mo imen os são planeados com base na selecção dos locais a
isi a e não nas p imi i as de mo imen o geomé ico que conec am os pon os inicial e inal.
Di o is o, a escolha do uso de mapas opológicos de e-se ao ac o de a isi a guiada se
ei a en e locais p é-de inidos (nós), e po isso adequados pa a a ep esen ação a a és de
g a os. A pesquisa de um caminho que ligue a posição ac ual à posição des ino, não é uma
pesquisa geomé ica, mas sim uma pesquisa num g a o de conec i idade. Nes e g a o, os
locais de maio impo ância encon am-se ligados en e si, o mando uma ede de caminhos
possí eis. Pesquisando es es caminhos, encon a-se uma ligação en e a posição ac ual e a
posição des ino, e consequen emen e uma ajec ó ia a segui . Du an e a na egação po es a
ajec ó ia, caso o obô não enha ce eza ace ca da sua localização exa a, ao e i ica uma
ca ac e ís ica isual sabe em que nó do g a o se encon a.
Tomemos po exemplo o cená io seguin e: se conside a mos um ambien e cons i uído
po salas que se ligam en e si e onde cada sala es á pin ada com uma co di e en e. En ão
pode-se sabe em que sala es amos sem conhece exa amen e a posição geomé ica a ual.
Pa a a ealização des a disse ação oi usado o Segway RMP 200, igu a 1.1, compos o
po uma pla a o ma ci cula , a qual pode e ec ua o mo imen o de anda em en e ou pa a
ás e oda em o no de um eixo e ical que se si ua no cen o ins an âneo de cu a u a,
o qual é de inido pelo di e encial de elocidades das odas da pla a o ma. A pla a o ma
é cons i uída po duas odas mo izes, colocadas num eixo que passa pelo seu cen o, as
quais do am a mesma de ca ac e ís icas de locomoção di e encial. Es e p imei o capí ulo
1

ap esen a o es ado da a e sob e os obôs de se iços desen ol idos ao longo dos empos e os
espec i os mé odos de na egação u ilizados, os objec i os e a es u u a des a disse ação.
Figu a 1.1: Segway RMP 200
1.1 Es ado da A e
Na sociedade mode na exis e cada ez mais con ac o diá io en e humanos e obôs. O campo
de in e ação homem-máquina, abo da ópicos desde o design, à comp eensão de sis emas
obó icos, que en ol am algum ipo de comunicação en e se es humanos e obôs [24]. E
po an o, o objec i o da in es igação oi da mais ên ase ao eal signi icado des as pala as,
usando sis emas obó icos pa a acili a e auxilia os humanos nas suas a e as quo idianas.
Como al, em 1997 oi in oduzido na Alemanha, no museu "Deu sches Museum Boon"o
obô guia de seu nome RHINO [13]. O objec i o p imá io des e obô e a o e ece uma na e-
gação segu a e iá el em ambien es públicos e bas an e populados. O u ilizado comunica a
com o obô a a és de bo ões, sendo que o obô espondia a a és de mensagens de oz p é-
g a adas. O RHINO o e ecia ambém uma in e ace web, a qual pe mi ia uma expe iência
in e ac i a pelas di e en es exposições. E a possí el eleope a o obô pelas di e en es salas
ou apenas assis i o obô a aze uma isi a guiada à dis ância. Pa a se localiza , u iliza a
uma e são do mé odo p opos o po Ma ko [51], man endo uma con iança p obabilís ica
ace ca da posição em que o obô se encon a. A na egação, híb ida, é ealizada a a és de
um mapa mé ico com a ajuda das lei u as senso iais. A du ação des a expe iência oi de seis
dias, e embo a o RHINO es i esse equipado com câma as, senso es de ul assom, senso es de
in a e melhos, lase - ange inde s e senso es de colisão, a na egação con inua a a se di ícil
2
dadas as ca ac e ís icas do ambien e o e ecido pelo museu. Is o e a de i ado, po exemplo,
à p esença de escul u as de dimensão in e io à al u a dos senso es colocados mais p óximos
do chão. O ambien e o na a-se dinâmico de ido aos isi an es e em bancos mó eis pa a
descansa em e es a em cons an emen e a deixá-los em sí ios di e en es. Du an e uma isi a,
e es ando o isi an e a se comandado pela sua p óp ia cu iosidade, es e não pode, nem que ,
espe a pelo obô. Caso is o acon ecesse o obô passa a de um guia pa a um es o o que
di icul a a a expe iência do isi an e, o nado-a menos in e essan e. Pa a al a elocidade de
locomoção chega a a se po ezes de 0.8 m/sec de modo a consegui acompanha o isi an e.
No en an o as maio es di iculdades, o am as impos as pelos humanos p esen es no museu,
que desa ia am cons an emen e o sis ema, le ando-o po ezes a i pa a sí ios não mapeados
onde exis iam pe igos eminen es como escadas.
Em 2002 oi in oduzido no exposição nacional da Suiça o RoboX [50]. Du an e cinco
meses uncionou se e dias po semana, onze ho as po dia, guiando pe o de um milhão de
pessoas. E a do ado de capacidades de comunicação com o se humano, sendo capaz de
sin e iza ases em qua o linguagens di e en es, segui a localização da ace das pessoas
usando uma câma a RGB, seguimen o do co po a a és de lase ange inde s e a é a ca-
pacidade de exibi exp essões aciais a a és de uma ma iz de leds colocada na sua cabeça.
O planeamen o da ajec ó ia e a baseado em mapas opológicos, sendo que u iliza a as ca-
ac e ís icas p esen es no ambien e em conjun o com um il o de kalman ex endido [4] pa a
es imação da localização. De modo a e i a obs áculos combina a o algo i mo dynamic
window app oach [20] (DWA) e o mé odo elas ic band [48] pa a a ge ação de ajec ó ias
sua es em o no dos mesmos.
O Jinny [30], oi desen ol ido no Ins i u o da Ciência e Tecnologia da Co eia em Se emb o
de 2004 com o objec i o de pe manece pe manen emen e nas ins alações do Museu nacional
do país. Pa a uma es adia p olongada no museu, a in e ação homem-máquina inha de
se simples e in ui i a de modo a que os emp egados do museu pudessem acilmen e aze
al e ações consoan e os e en os p esen es no museu. U iliza a dois lase ange inde s , dois
scanne s de in a e melhos e um gi oscópio de ib a op ica pa a uma localização mais p ecisa.
Caso algo alhasse inha como edundância, à sua ol a, senso es de colisão (bumpe s). A
localização e a ei a com base no mé odo p obabilís ico de Mon e Ca lo [19] e a planeamen o
a a és de mapas opológicos. U iliza a qua o ipos de algo i mos de na egação di e en es,
de en e os quais escolhia consoan e o ambien e em que se encon a a. No caso do obô es a
pe an e uma á ea abe a, usa a uma na egação baseada no mapa que inha ao seu dispo .
Caso es i esse em egiões con inadas basea a a sua locomoção nos senso es disponí eis,
u ilizando pa a al um algo i mo eac i o baseado em pa edes. Pa a cump i a unção de
guia, o obô inha de ca i a os seus isi an es e cap a a sua a enção. Capaz de se exp essa
emocionalmen e a a és de ícones ep esen ados numa ma iz de leds, de dois b aços com
um g au de libe dade e um pescoço com dois g aus de libe dade. Reconhecia e sin e iza a
exp essões e e a capaz de man e uma con e sação sob e uma gama de ópicos limi ada.
No inal acabou po implemen a com sucesso qua os a e as, de en e elas a ealização de
3
en egas, pa ulha, obô guia e limpeza do chão.
Em [37] oi usado o PR2 numa ma a ona de na egação obus a em ambien e de esc i ó-
io, pe co endo com sucesso 42km sem aciden es. A localização e a ei a de duas o mas.
Se exis isse um mapa à p io i a localização e a p obabilís ica e e ec uada a a és do uso
do algo i mo adap i e Mon e Ca lo localiza ion (AMCL) [18]. No caso de não exis i um
mapa, possuía um ine ial measu emen uni (IMU) que pe mi ia aze usão senso ial com
a odome ia podendo assim melho a a es imação da posição. O planeamen o e a e ec uado
a a és da cons ução de um mapa de cus o, com base na in o mação senso ial, onde e a
usado o algo i mo A* pa a planeamen o da ajec ó ia e o algo i mo DWA pa a des io de
obs áculos. O PR2 é um obô omnidi eccional, cons uido po dois b aços, cada um com um
g ippe possibili ando assim a manipulação de objec os. As a e as ealizadas e am di e sas,
como i busca ca és, i ens ao igo í ico ou limpa mesas.
1.2 Objec i os
Es e abalho em como objec i o o desen ol imen o de um sis ema simples e obus o de
supo e à na egação de uma pla a o ma, num espaço conhecido à p io i, usando écnicas de
na egação opológica, c iando assim a base pa a um obô guia. Pa a al o am omadas em
con a as seguin es a e as:
1. C iação de um algo i mo de na egação
2. Desen ol imen o de um módulo de localização a pa i dos já exis en es ma cado es
isuais da biblio eca OpenAR [40]
3. In eg ação des e módulo com a in o mação odomé ica
4. In eg ação e con igu ação de um planeado opológico
5. Equipa a pla a o ma com senso es de dis ância e desen ol imen o da capacidade de
des io de obs áculos
6. C iação de uma in e ace g á ica
7. Tes a a iabilidade do sis ema
1.3 O ganização do documen o
Es a disse ação é cons i uída po 7 capí ulos, es ando o es an e documen o o ganizado
da seguin e o ma: O capi ulo 2 abo da o planeamen o da ajec ó ia que le a o obô da
posição onde ele se encon a pa a a posição des ino, sendo que no capi ulo 3 é explicado o
algo i mo do calculo dos comandos de elocidade que pe mi am a ealização dessa ajec ó ia,
assim como o mé odo u ilizado pa a o des io de obs áculos que possam apa ece du an e o
4
pe cu so. No capi ulo 4 é explo ada a u ilização de ma cado es isuais pa a melho amen o
da es imação da posição ao longo do pe cu so, diminuindo assim o e o p o enien e da
es imação da posição a a és da odome ia. Já no capi ulo 5 é ap esen ada a a qui ec u a
do sis ema, implemen ação p á ica e a in e ace g á ica desen ol ida pa a uma comunicação
com o u ilizado do sis ema. Po im, no capi ulo 6 são ap esen ados os esul ados e no
capi ulo 7 as conclusões e possí el abalho u u o pa a es a disse ação.
5
12

Capí ulo 3
Na egação Local
Uma ez ge ada a ajec ó ia a segui pela pla a o ma, é necessá io começando do pon o
inicial, na ega ao longo das linhas que unem nós consecu i os, a é ao pon o des ino. A o ma
escolhida pa a ealiza a na egação no caso co en e, consis e em de ini o ças a ac i as
i uais que i iam puxa o obô em di eção a posições sucessi as da ajec ó ia ge ada a é
a ingi o pon o des ino. Essas o ças i uais, como se á explicado mais adian e, se em pa a
como o malismo de supo e à ge ação da sequência de comandos de elocidade necessá ios
pa a guia o obô. No en an o, em si uações eais há semp e a possibilidade de obs áculos,
não conside ados du an e a ase de planeamen o, pode em apa ece pelo caminho os quais
e ão de se con o nados se possí el. Todos os sis emas obó icos au ónomos u ilizam algum
ipo de sis ema com es e objec i o pelo que es e não se á excepção. O compo amen o em
p esença dos obs áculos pode se simplesmen e o de pa a e solici a o eplaneamen o da
aje ó ia, à u ilização de algo i mos e sis emas senso iais que pe mi am compo amen os
eac i os con o nando desde que possí el os obs áculos encon ados. A abo dagem u ilizada
nes e abalho co esponde ao uso de um planeamen o local discu ido an e io men e no
capi ulo 2.
Nas secções seguin es se ão analisados os mé odos usados adicionalmen e pa a a na-
egação na p esença de obs áculos, seguindo-se da ap esen ação do mé odo escolhido e sua
implemen ação. Os esul ados ob idos se ão pos e io men e ap esen ados no capí ulo 6.
3.1 Es ado da A e da Na egação na P esença de Obs-
áculos
3.1.1 Po encial Fields
Robus ez e segu ança são duas máximas de g ande impo ância que qualque sis ema obó-
ico de e e em con a. A o ma como se az a na egação, o planeamen o e se e i a obs áculos,
êm g ande in luência na o ma como as pessoas eagem a um sis ema au ónomo. And ews
and Hogan em [2] e mais a de Kha ib em [29], suge i am o concei o da exis ência de o ças
i uais com pon o de aplicação no cen o do obô, onde os obs áculos exe cem uma o ça
13
epulsi a enquan o que o pon o objec i o exe ce uma o ça a ac i a. A esul an e das o ças,
esul ado do soma ó io da o ça a ac i a com as epulsi as, é a no a di ecção que o obô
de e segui .
K ogh em [32], melho ou es e concei o endo em con a a elocidade do obô na p oximi-
dade dos obs aculos. No en an o B ooks em [11, 12], oi o pionei o na implemen ação de uma
a ian e des es mé odos numa pla a o ma mó el. Pa a al usou um a ay de sona es onde
cada lei u a dos senso es con ibuia com uma o ça epulsi a. Se a magni ude esul an e da
soma das o ças ul apassa-se um ce o limia , o obô pa a a, edi eciona a-se e con inua a
o mo imen o. Apoiados nes a abo dagem, Bo ens ein and Ko en em 1989 ap esen a am o
mé odo Vi ual Fo ce Field (VFF). Es e mé odo e e uma g ande p ocu a de ido à necessi-
dade de um baixo pode de compu ação, à ma emá ica u ilizada e às ajec ó ias sua es que
e a capaz de ep oduzi .
Pa a al, u iliza uma g elha ca esiana bidimensional (his og ama bidimensional) pa a
ep esen a os obs áculos de ec ados sendo que em cada célula da g elha ica egis ada a
con iança do algo i mo de como ealmen e exis e um obs áculo nessa localização. Es a
ce eza aumen a com cada lei u a do senso que indique a p esença de um obs áculo nessa
célula. Es a abo dagem de i a de uma écnica mais an iga chamada G elhas de Ce eza
(ce ain y g id) [42]. Começa-se en ão po de ini uma zona chamada egião ac i a em o no
do obô, caso se de ec e a p esença de um obs áculo nessa zona, essa célula con ibui com
uma o ça epulsi a sob e o obô. O alo dessa o ça é p opo cional ao alo do his og ama
bidimensional e in e samen e p opo cional à dis ância en e a célula e o obô, sendo que a
o ça a ac i a pa a o pon o des ino é cons an e.
No en an o o VFF não e a pe ei o e inha alguns p oblemas como ica encu alado em
mínimos locais, não encon a uma passagem possí el en e obs áculos com um espaçamen o
eduzido en e eles e ap esen a a oscilações em passagens es ei as como co edo es ou po as
[56][31]. De manei a a comba e es as limi ações oi desen ol ido pela mesma equipa de
in es igado es o Vec o Field His og am (VFH). Es e algo i mo elimina as limi ações do
VFF, en ando no en an o man e odas as suas an agens [9].
O uncionamen o e a amen o do dados pode-se esumi a duas e apas:
1. Cons ução de uma g elha de ocupação al como o VFF
2. Cons ução de um his og ama pola ela i o à dis ibuição de obs áculos em o no do
obô.
O his og ama pola é ob ido di idindo uma janela cen ada no obô em sec o es, e con-
abilizando o núme o de células ocupadas em cada sec o . Ob endo o his og ama pola ,
podemos en ão sabe qual di ecção o obô pode oma sem ha e pe igo de colisão. Pa a
al, e de ido à na u eza disc e a do his og ama pola , es e é il ado a a és de um il o
passa-baixo de ase nula. O esul ado des a il agem con ém picos que co espondem às
egiões com maio densidade de obs áculos, sendo que os ales co espondem a egiões onde
esses obs áculos são diminu os. Uma ez conhecida a posição des ino e posição ac ual do
14
obô, é escolhido o ale do his og ama, a a és de um limia , que mais se ap oxima dessa
o ien ação objec i o.
3.1.2 Bug algo i hms
Es a abo dagem combina planeamen o local com um c i é io de con e gência global. Inici-
almen e, o obô mo e-se di e amen e em di ecção ao pon o des ino. Quando um obs áculo
é de ec ado, es e começa a segui o seu con o no a é que uma condição se saída (que sal a-
gua da o c i é io da con e gência global) o cump ida. À posição que e i ica es a condição
de saída, dá-se o nome de pon o de saída. Uma an agens des es em compa ação aos Po en-
cial Fields é o ac o de es es não caí em em mínimos locais. Is o é de i ado do ac o des es
apenas e em em con a as pe cepções ac uais e não as passadas.
Na abo dagem Bug-1, quando de ec a um obs áculo começa a segui o con o no do
mesmo, ci cundado-o, a é chega ao mesmo pon o em que o obs áculo oi de ec ado e o
começou a con o na . Enquan o is o, encon a-se simul aneamen e a cada ins an e a cal-
cula a dis ância da posição ac ual ao pon o des ino, gua dando aquela que minimiza essa
dis ância. Após um ciclo comple o (con o no o al do objec o encon ado) o obô passa pa a
a segunda ase, de i pa a o des ino, onde o pon o de saída é o pon o p e iamen e gua -
dado como o pon o de meno dis ância ao pon o des ino, igu a 3.1 (b). Es a abo dagem é
bas an e ine icien e e le a a que po ezes o obô agueie pa a longe do objec i o ao en a
con o na o obs áculo [49, 1]. Ou a des an agem des e algo i mo é que aquando do inicio
do seguimen o do obs áculo, caso encon e um segundo pelo caminho pode colidi com ele,
caso o espaçamen o en e eles seja meno que o la gu a do obô.
O uncionamen o do Bug-2, que é uma i e ação do Bug-1, começa po inicialmen e se
calculado o segmen o de ec a que liga o pon o inicial ao pon o inal. O obô começa po
segui a di ecção desse segmen o a é se depa a com um obs áculo. Aí, começa po segui
o seu con o no, calculando a cada ins an e se já in e sec ou no amen e o segmen o de ec a
calculado inicialmen e. Quando es a condição se e i ica , abandona o modo de con o no
de obs áculo e passa pa a o modo de i de encon o ao pon o des ino, igu a 3.1 (c). A
di e ença da omada de decisão em abandona o modo de con o no de obs áculo, o na es e
algo i mo mais e icien e e mais ápido a con e gi pa a o des ino. Di o is o, e mesmo sendo
uma melho ia conside á el em elação ao seu an ecesso Bug-1, es e algo i mo não az um
uso op imo dos dados ecebidos pelos senso es pa a o calculo de uma ajec ó ia mais cu a
[36].
Es e oi o mo e pa a a c iação de mais uma e en e des a amília que oi o Dis -Bug
[28, 61]. Es a abo dagem enca a o p oblema de uma manei a um pouco di e en e. Quando
depa ado com um obs áculo e dado inicio ao modo de des io do mesmo, é calculada a
dis ância ao pon o des ino a pa i da posição ac ual e da posição seguin e. O pon o de
saída é quando a dis ância da posição seguin e ao pon o des ino é maio que a dis ância da
posição ac ual ao mesmo pon o (dseguin e > dac ual). Mesmo com es as melho ias, o dis -bug
não é um mé odo o ien ado ao des ino e po an o, enquan o ocupado a e i a obs áculos,
15
Figu a 3.1: Compa ação en e o Bug-1(b) e o bug-2 (c). Adap ado de [62]
Figu a 3.2: Compa ação en e o Dis -bug e o IBA. Adap ado de [62]
pode le a o obô pa a longe do mesmo.
Es e oi o mo i o impulsionado pa a Zohaib e Pasha c ia em o In eligen e Bug Algo i hm
(IBA) [62]. A p opos a des es in es igado es consis e em modi ica o Dis -bug o nando-o
um algo i mo o ien ado pa a o des ino e endo em con a o empo necessá io pa a chega ao
mesmo. Pa a al, inicialmen e é calculado uma ajec ó ia de e e ência que o obô segue a é
encon a um obs áculo. Quando is o acon ece, o obô começa a segui o seu con o no endo
em conside ação a posição do pon o des ino, sendo o pon o de saída do modo de des io de
obs áculos, decidido com base no caminho li e em di ecção ao des ino. Es e caminho li e
é de ec ado pelos senso es a bo do do obô. Uma ez omada a decisão de i no amen e
em di ecção ao pon o des ino, é calculada uma no a ajec ó ia de e e encia e o p ocesso é
epe ido a é chega ao local p e endido.
3.1.3 Bubble Rebound Algo i hm
O abalho que deu mo e a es e algo i mo oi p opos o po Quinlan em [48]. Quinlan de inia
a exis ência de uma "bolha"con endo o máximo de espaço li e à ol a do obô, que podia
se na egada em qualque di ecção sem pe igo de colisão. O amanho e o ma da bolha e a
16
Figu a 3.3: Diag ama pola ealizado a a és das lei u as dos sona es. Adap ado de [54]
de e minado a a és de um modelo simpli icado da geome ia do obô, e pelas dis âncias
de ol idas pelos senso es. Susnea [54], pegou nes e p incipio e c iou um algo i mo simples,
eac i o, capaz de e i a obs áculos em empo eal a a és do uso de senso es de ul asom ou
in a e melhos e com o objec i o de se implemen ado num mic ocon olado . Es e mé odo
de ine uma á ea em o no de obô, (bubble), que é igualmen e ajus ada de aco do com a o ma
do mesmo. Como os senso es es ão dis ibuídos uni o memen e pelo obô, pe azendo um
a co de 180º, as lei u as dos sona es podem se ep esen adas a a és de um diag ama pola ,
como pode se e i icado a a és da igu a 3.3. Aquando da de ecção de um obs áculo, o obô
analisa o ambien e à sua ol a, escolhendo a di ecção com meno densidade de obs áculos,
a é o pon o objec i o ica no amen e isí el ou ou o obs áculo apa ece .
3.2 Locomoção
O obô u ilizado oi ap esen ado no capí ulo 1, e o con olo dos seus mo imen os é eali-
zado a a és da de inição, a cada ins an e, de uma elocidade de linea , , e uma elocidade
angula , w. Pa a al é de inido um ec o em di ecção ao pon o objec i o, igu a 3.4, e os co-
mandos de elocidade são en ão calculados a a és da equação 3.1, onde α1eα2 ep esen am
cons an es e −→
Axe−→
Ay ep esen am a p ojecção desse ec o a ac i o no eixo de coo denadas
XeY espec i amen e. Es e mé odo pode se is o como um con olo p opo cional onde o
e o é a dis ância do obô ao pon o objec i o.
17

X
Y
→
A
Pon o objec i o
Robô
Figu a 3.4: Rep esen ação da o ça a ac i a i ual ( e de) que i á puxa o obô em di ecção
ao pon o objec i o.
=α1·−→
Ax
w=α2·−→
Ay
(3.1)
Assim, caso 6= 0 ew= 0 o obô mo imen a-se em linha ec a, caso = 0 ew6= 0 o
obô desc e e uma o ação sob e o seu cen o, e po im, combinações de 6= 0 ew6= 0 dão
o igem a uma ajec ó ia com a o ma de um a co.
No en an o, pa a es a me odologia unciona é necessá io que as coo denadas do pon o
objec i o es ejam no e e encial do obô. O planeado de ol e os pon os objec i o em co-
o denadas do mundo, sendo en ão necessá io ans o ma o pon o objec i o localizado no
e e encial mundo Wp, num pon o no e e encial da pla a o ma mó el Rp, igu a 3.5. É de
salien a que es es pon os são em 2D, mas são aqui a ados em coo denadas homogéneas.
Es a ans o mação é conseguida a a és da equação 3.2, onde (W
RT)−1é a in e sa da
ma iz de ans o mação p esen e em 3.3, que po sua ez, ep esen a a ans o mação en e
o e e encial mundo e o e e encial do obô, onde θ,XeY ep esen am a posição ac ual da
pla a o ma p o enien e da localização es imada a pa i da odome ia.
Rp= (W
RT)−1·Wp (3.2)
W
RT=




cos θ −sin θ X
sin θ cos θ Y
0 0 1



(3.3)
Assim ob em-se a equação 3.4, onde Xobjec i o eYobjec i o são pon os do e e encial mundo
18
.
.
Pon o
Objec i o
X
Re e encial
Robô
Re e encial
Mundo
p
R
T
W
R
p
W
Figu a 3.5: Rep esen ação da ans o mação en e o e e encial mundo e o e e encial da
pla a o ma mó el.
eXReYRsão os mesmos pon os ans o mados pa a o e e encial do obô.




XR
YR
1



= (W
RT)−1·




Xobjec i o
Yobjec i o
1



(3.4)
3.3 Des io de Obs áculos
Dando seguimen o à mesma iloso ia usada no calculo de elocidades e à semelhança de
B ooks [11, 12], nes a implemen ação cada senso que e o ne a in o mação da p esença de um
obs áculo, con ibui com um ec o epulsi o. O comp imen o desse ec o é in e samen e
p opo cional à dis ância en e o obô e o obs áculo, sendo o ec o a ac i o de comp imen o
cons an e. Uma ilus ação do p ocesso pode se encon ada na igu a 3.11.
Fo am u ilizados senso es de ul asom assim como senso es de in a e melhos pa a aze a
de ecção de obs áculos du an e o pe cu so a ealiza pela pla a o ma. A escolha da u ilização
de dois ipos di e en es de senso es, oi de i ada ao ac o de exis i em sí ios onde um deles
é ine icaz. Sí ios es es como id os, pa a os senso es de in a e melhos, e supe ícies onde a
onda sono a é e le ida pa a longe do ecep o , no caso dos sona es.
19
HC-SR04
Es e senso de ul asom é bas an e usado na comunidade da obó ica de ido à sua acilidade
de u ilização e ao cus o eduzido. O p incipio de uncionamen o baseia-se no ac o da elo-
cidade de p opagação da onda sono a no a se conhecida. Pa a al, o ansdu o emisso
en ia uma onda sono a, enquan o que o ansdu o ecep o ica à espe a da mesma. Quando
ecebida, é en ão p oduzido um pulso com a mesma du ação do empo de iagem da onda
sono a.
Figu a 3.6: Sona HC-SR04
Sha p GP2Y0A02YK0F
É um senso de dis ância po in a e melhos com um ci cui o de condicionamen o de sinal
in eg ado. Pa a adqui i a dis ância ao objec o de ec ado, o senso de ol e no seu e minal
in e médio uma di e ença de po encial, que ai co esponde à dis ância ao objec o. Pa a al,
o ab ican e disponibiliza uma cu a de espos a que az co espondência en e a ol agem
de ol ida e a espec i a dis ância. Quando ei os os es e iniciais u ilizando es a cu a,
epa ou-se que os alo es de dis ância de ol idos não e am os mais exac os.
Figu a 3.7: Senso de in a e melhos Sha p GP2Y0A02YK0F
P ocedeu-se en ão à calib ação do senso , ob endo a cu a de espos a dis ância- ensão
do mesmo. Pa a dis âncias espaçadas de dez cen íme os en e si, o am adqui idas dez
amos as de ensão, ei a a sua média e a mazenadas numa abela. A compa ação en e a
cu a de calib ação e a cu a do ab ican e podem se is as no g á ico da igu a 3.8.
20
0 50 100 150
Dis ancia [cm]
0
0.5
1
1.5
2
2.5
3
Vol agem [V]
Cu a ab ican e
Cu a calib ação
Figu a 3.8: Compa ação en e a cu a de espos a do senso dada pelo ab ican e e da cu a
após a calib ação.
Na igu a 3.8 emos uma ol agem em unção da dis ância. No en an o p ecisamos do
in e so, pois o senso de ol e uma ol agem e p ecisamos de ob e a dis ância co esponden e.
Ob e e-se en ão o g á ico da igu a 3.9, onde a unção que ap oxima a cu a é a p esen e na
equação 3.5.
0.5 1 1.5 2 2.5
Vol agem [V]
20
40
60
80
100
120
140
Dis ancia [cm]
Figu a 3.9: Ajus e da cu a de espos a do senso de in a e melhos.
d= 61.8·V−1.1
o(3.5)
Pode-se en ende po da dis ância do senso ao obs áculo e po V o a di e ença de po encial
de ol ida pelo senso .
A qualidade da ap oximação pode se comp eendida a a és da abela 3.1.
21
esponde ao p oblema do obô " ap ado", onde o obô é le ado pa a uma localização des-
conhecida, sem qualque ipo de in o mação sob e o meio onde se encon a, com o objec i o
de se localiza e na ega . No en an o, a localização absolu a é no malmen e usada com
o objec i o de mi iga o e o acumulado ao longo do empo pelas écnicas de na egação
ela i a.
4.1.1 Localização ela i a
Ac ualmen e a odome ia é um dos mé odos mais amplamen e u ilizados pa a e ec ua a es-
imação da posição. Is o de e-se ao ac o de se uma écnica ba a a, o nece bons esul ados
a cu o p azo, e pe mi i uma axa de amos agem ele ada. No en an o, a acumulação de
e os de o ien ação le a a e os na es imação da posição, os quais aumen am com a dis ancia
pe co ida [8]. No caso mais especi ico da obó ica mó el, a odome ia pode se es imada a
pa i da in eg ação ao longo do empo do deslocamen o p o ocado pelas elocidades linea es
e angula es com que o obô se mo imen a.
Es a in eg ação do deslocamen o le a à acumulação de e os que podem se sis emá icos
ou não sis emá icos [6]. Os e os sis emá icos são ca ac e ís icos do obô, ou dos senso es,
e são uma on e cons an e de e os adi i os. Exemplos disso são um diâme o desigual das
odas e a ince eza sob e o pon o de con ac o da oda com o piso. Os e os não sis emá icos
são ca ac e ís icos da elação do obô com o ambien e, logo não podem se con abilizados à
p io i pois são inespe ados. Esco egamen o das odas e mo imen o sob e solos não uni o mes
são alguns exemplos des es e os [10].
Exis em ainda ou os sis emas de es imação de posição, como os sis ema de na egação
ine cial, que usam gi oscópios e acele ôme os pa a medi espec i amen e a axa de o ação
e acele ação do obô. De modo a ob e a posição a pa i da acele ação é necessá io in eg a
a espos a do senso duas ezes, o nando-os sensí eis a des ios. Em alguns casos, u iliza-se
usão senso ial en e senso es odomé icos e ine ciais, sendo es a écnica conhecida como
gy odome y [7].
By ne em [14], es ou o uso de uma bússola ele ónica pa a medi a o ien ação do obô
ela i amen e ao campo magné ico da e a. No en an o, es e sis ema não é ecomendado
pa a o uso no in e io de edi icios, de ido às dis o ções do campo magné ico causadas pelos
cabos elé icos e me al nas pa edes.
4.1.2 Localização absolu a
Quando pensamos em localização absolu a o mé odo que nos em logo à memó ia é o global
posi ioning sys em (GPS). Es e é um mé odo já mui o es udado, bem undamen ado e acei e
pela comunidade cien i ica. No en an o, em ambien es cobe os, a sua u ilização não é uma
opção de ido à di iculdade que os sinais de GPS encon am em a a essa as pa edes dos
edi ícios [58].
Os mé odos de localização a a és de pon os de e e ência es ão cada ez mais p esen es
28

na in es igação, podendo se di ididos em pon os de e e ência na u ais ou a i iciais. Ao
u iliza pon os de e e ência na u ais não exis e a necessidade de modi ica o ambien e, mas
a escolha dos pon os de e e ência ísicos a usa pode se bas an e complexa [35]. Po ou o
lado, os pon os de e e ência a i iciais são cada ez menos in usi os no ambien e e o e ecem,
no en an o, uma melho de ecção o que é necessá io pa a uma localização idedigna.
Yoon e Kweon em [57] e Jang em [26], usa am écnicas de p ocessamen o de co em
imagens pa a de ec a ma cado es de di e en es co es. Os códigos de ba as [27] ambém
o am u ilizados como pon os de e e ência a i iciais . Em [52], uma equipa de in es igado es
po ugueses, desen ol eu um mé odo onde a localização é melho ada a a és do uso de
uma câma a pa a iden i icação de códigos de ba a e consequen e es imação da posição da
pla a o ma mó el.
Mais ecen emen e, com o apa ecimen o dos códigos Quick Response (QR), e de ido à
acilidade de c iação e de ecção dos mesmos, o am desen ol idas á ias abo dagens pa a
es ima a pose de uma pla a o ma mó el ela i amen e a códigos QR colocados em sí ios
es a égicos. Es es podem se is o como uma e são 2D dos códigos de ba as, com a
an agem de pode con e mui o mais in o mação. Exemplos de aplicação p á icos podem
se encon ados em [22, 60], onde os códigos QR são colocados no ec o. Ou as abo dagens
o am ei as usando écnicas como Wi-Fi [5], adio equency iden i ica ion (RFID) [45] e
ádios de banda ul a la ga [21]. Em [59] é medida a o ça do sinal wi- i ecebido e compa ado
com uma base de dados onde cons am o ças de sinal medidas em di e en es localizações do
mapa. Em [34] são usadas e ique as RFID onde cada um em uma iden i icação única. Es as
e ique as, usam um campo ele omagné ico pa a ansmi i in o mação e podem se ac i as
ou passi as, dependendo se es ão equipadas com uma ba e ia e cons an emen e a emi i ,
ou se apenas são ac i adas na p esença do ecep o . Quando o obô se ap oxima des as
e ique as, o ID é de ec ado e ob ida a posição ap oximada. Nes e caso, não se ob em a
posição absolu a mas sim uma ap oximação, pois apenas conseguimos conclui que es amos
no aio de de ecção possí el daquele emisso em especi ico.
4.2 Ma cado es isuais u ilizados
Os ma cado es isuais u ilizados são bidimensional, compos os po um quad ado/ ame p e o
em undo b anco, sendo assim cons i uídos po oi o pon os de e e encia, os qua o can os
ex e nos e ou os qua o can os in e nos, igu a 4.7. Es es possuem um código de iden i-
icação único que os dis ingue en e si, código es e que consis e numa dis ibuição biná ia
de oi o en adas no in e io de cada ma cado , igu a 4.1. É de salien a ambém o pon o
de o ien ação, igu a 4.2, que é essencial pa a a não oco ência de e os na localização e
es imação da o ação do ma cado [46].
29
(a) Ma cado núme o 135 (b) Ma cado núme o 255
Figu a 4.1: Exemplo da codi icação biná ia dos ma cado es isuais. Adap ado de [46].
Quad ado/ ame do ma cado
Pon os de iden ificação
Pon o de o ien ação
Figu a 4.2: Desc ição dos ma cado es u ilizados.
Pa a o co ec o uncionamen o do sis ema a calib ação da câma a é imp escindí el, pois
só assim é possí el a ex ação de in o mação mé ica a pa i de imagens 2D. Pa a al usou-se
um mé odo ambém disponí el na biblio eca OpenAR, onde se u iliza um pad ão de xad ez de
modo a assim ob e os pa âme os in ínsecos e os pa âme os de dis o ção da câma a. Es es
não a iam ao longo do empo, e são especí icos pa a cada câma a, po an o a calib ação só
p ecisa de se ealiza uma ez. Po ou o lado, é necessá io calcula os pa âme os ex ínsecos
da câma a em cada imagem da sequência de de ecção, pois a posição des a a ia em elação
aos ma cado es.
A câma a u ilizada unciona a a és do modelo pinhole. Es e modelo é uma boa ap o-
ximação do modelo de câma a con encional e consis e numa caixa cúbica, echada, com um
pequeno o i ício numa das aces, po onde os aios de p ojecção ão passa e o ma uma
imagem na ace opos a à do o i ício.
Es e ipo de modelo baseia-se essencialmen e em dois pa âme os, a dis ância ocal ( x, y)
e pon o p incipal (cx, cy). Es es ep esen am os pa âme os in ínsecos da câma a (K),
equação 4.1. A dis ância ocal é a dis ância que sepa a o plano imagem do plano ocal
de inido pelo cen o óp ico. O pon o p incipal é o pon o de in e secção do eixo óp ico com
o plano imagem, sendo o eixo óp ico o aio pe pendicula ao plano imagem.
30
Figu a 4.3: Ilus ação do modelo de câma a pinhole.
Figu a 4.4: Ilus ação dos di e en es pa âme os de uma câma a pinhole.
K=




x0cx
0 ycy
0 0 1



(4.1)
Ou seja, a cena que a câma a es á a obse a é egis ada a a és da p ojecção de pon os
3D do mundo eal no plano imagem usando uma ans o mação pe spec i a, equação 4.2.
s m =K[R| ]M
s




u
1



=




x0cx
0 ycy
0 0 1








11 12 13 1
21 22 23 2
31 32 33 3











X
Y
Z
1







(4.2)
Onde X, Y, Z são as coo denadas do pon o 3D no e e encial do mundo (M), ue são
as coo denadas do pon o p ojec ado no plano imagem (m), em pixeis, Ké a ma iz dos
pa âme os in ínsecos e a [R| ]dá-se o nome de ma iz dos pa âme os ex ínsecos. Es a é
usada, em conjun o com a ma iz dos pa âme os in insecos, pa a desc e e o mo imen o
da câma a em elação a uma cena es á ica ou de um objec o ígido (ma cado ) em elação à
câma a es á ica. Is o é, K[R| ] aduz as coo denadas de um pon o 3D no mundo pa a um
ou o sis ema de coo denadas com base nos pa âme os da câma a.
31
Coo denadas no
e e encial mundo
[X Y Z]
Coo denadas
no e e encial da
câma a
Coo denadas em
pixeis
[u ]
Rigida P ojec i a
3D -->3D 3D --> 2D
Pa âme os Ex ínsecos Pa âme os In ínsecos
Figu a 4.5: T ans o mações ealizadas a a és do uso dos pa âme os ex ínsecos e in ínse-
cos.
Assumindo que o modelo ísico do ma cado , que de ine um plano, se encon a em Z= 0
no e e encial do mundo, os pon os do modelo ísico do ma cado (
M) e os pon os da imagem
(em) encon am-se elacionados po uma homog a ia. Es a consis e numa ma iz 3×3de inida
a menos de um ac o de escala, equação 4.3.
sem=H
M(4.3)
Uma ez calculada a ma iz de homog a ia, é calculada a o ação e anslação que des-
c e em a ans o mação en e os pon os do ma cado e os pon os imagem.
Figu a 4.6: Ma cado isual colocado na pa ede do co edo do ISR.
32
Figu a 4.7: De ecção do ma cado isual.
4.3 Funcionamen o do sis ema
Re e encial
Mundo
T
W
R
T
W
M
T
C
M
T
R
C
Figu a 4.8: Diag ama explica i o da ob enção da posição co igida da pla a o ma.
Aquando da ap oximação da pla a o ma a um ma cado e consequen e de ecção do mesmo,
é en ão ex aída a es imação da posição da câma a em elação ao ma cado como explicado
an e io men e. Es a ans o mação é de inida po C
MT. De manei a a ob e a pose do obô
em elação ao ma cado R
MT, equação 4.4, p ecisamos de mapea a câma a no e e encial do
obô. Pa a al u iliza-se a ma iz de ans o mação ígida de inida po R
CT.
R
MT=R
CT·C
MT (4.4)
W
RT=W
MT·M
RT (4.5)
33

Pa a cada núme o iden i icado de um ma cado exis e uma ma iz de ans o mação
ígida associada. Ma iz de ans o mação essa que de ine a posição e o ien ação do ma cado
em elação ao e e encial mundo, de inida po W
MT. Es a ma iz é a e dade absolu a (g ound
u h) do sis ema. Ao echa mos o ciclo, como ilus ado na igu a 4.8, e a a és da equação
4.5, ob emos a ma iz W
RT.
4.4 Implemen ação
Explicado o mé odo u ilizado pa a a es imação da posição do obô no e e encial mundo,
a a és da de ecção de um ma cado isual, é ago a explicado como é ei a a in eg ação des a
es imação com a localização o necida pela odome ia do obô.
Quando se inicia o sis ema, a posição e o ien ação iniciais do obô em elação ao e e encial
mundo são ob idas a a és de um ma cado . Di o is o, e de modo a esol e a ques ão da
localização o necida pelo obô e um e e encial não coinciden e com o e e encial mundo, é
necessá io calcula a ans o mação en e o e e encial mundo e esse e e encial. Chamemos-
lhe e e encial da odome ia. Pa a isso oi usada a cadeia de ans o mações p esen e na
igu a 4.9. Sabendo que W
RTM ep esen a a posição e o ien ação do obô no mundo es imada
a pa i do ma cado , e que O
RT ep esen a a posição e o ien ação do obô no e e encial da
odome ia, ao echa mos o ciclo, ob emos a ans o mação W
OT. Es a an o mação ep esen a
a compensação necessá ia pa a mapea o e e encial da odome ia no e e encial do mundo,
sendo ob ida a a és da equação 4.6. Assim, a posição e o ien ação do obô podem se
es imadas de aco do com o e e encial do mundo, a a és da equação 4.7.
Aquando do inicio da ealização de uma ajec ó ia e de ecção de um no o ma cado , é
es imada uma no a ma iz W
RTM.
Es a no a ma iz co esponde a uma ac ualização da es imação da posição e dadei a do
obô no mundo. Assim, é calculada no amen e a ma iz W
OT, que em a o ma de 4.8, e a
compensação en e o e e encial mundo e o e e encial da odome ia é co igida.
W
OT=W
RTM·(O
RT)−1(4.6)
W
RT=W
OT·O
RT (4.7)
W
OT=







11 12 13 x
21 22 23 y
31 32 33 z
0 0 0 1







(4.8)
No en an o, num sis ema de isão po compu ado , a iluminação é um ac o impo an e
pa a o uncionamen o co ec o do mesmo. A de ecção dos ma cado es não é excepção, sendo
in luenciada pelas condições de luminosidade. Di o is o, o calculo da no a ma iz W
OT passa
34
T
W
R
T
W
O
T
O
R
Re e encial
Mundo
Re e encial
Robô
Re e encial
Odome ia
Figu a 4.9: Diag ama explica i o das ans o mações necessá ias pa a a co ecção da es i-
mação da odome ia.
p imei o po um il o passa-baixo. Es e il o em em conside ação que a ans o mação W
OT
de e a ia mui o de aga de aco do com o e o in oduzido pela odome ia. Ao de ec a um
ma cado , é espe ado ecebe um núme o conside á el de lei u as do mesmo, ou seja, á ias
es ima i as da ma iz W
RTM. No caso de algumas des as lei u as se em uidosas, o il o i á
da mais peso às lei u as an e io es, de modo a que pequenas a iações nas lei u as enham
pouco e ei o em W
OT.
O il o, exponen ally weigh ed mo ing a e age, em um pa âme o heu ís ico, de e mi-
nado expe imen almen e, α, e o mula-se do seguin e modo:
x[i+ 1] = α· x[i] + (1 −α)· x[i−1]
y[i+ 1] = α· y[i] + (1 −α)· y[i−1]
z[i+ 1] = α· z[i] + (1 −α)· z[i−1]
(4.9)
Onde x co esponde à anslação em x, y à anslação em ye zà o ação aplicado
sob e o eixo dos zz. Aplicado o il o, a ma iz W
OT é econs uida, e aplicada a equação 4.7
co igindo assim a es imação da posição da pla a o ma no e e encial do mundo.
4.5 Resumo
Nes e capi ulo oi abo dado o uso de ma cado es isuais, alando desde a sua de ecção, es i-
mação de posição e o ien ação, a é ao seu con ibu o pa a um sis ema mais obus o a a és
da co ecção da es imação da odome ia e do e o acumulado pela mesma com o deco e do
empo. O capi ulo seguin e desc e e a o ma como odo o sis ema oi implemen ado usando
35
a a qui ec u a ROS.
36
Capí ulo 5
A qui ec u a e In eg ação
5.1 A qui ec u a modula baseada em ROS
Com o objec i o de uma implemen ação obus a e es anda dizada com a comunidade, oda
a implemen ação oi ei a usando a a qui ec u a ROS. Es a a qui ec u a é open sou ce e
con ém uma gama de e amen as, li a ias e se iços cons uidos especi icamen e a pensa
no mundo da obó ica. Pe mi e a u ilização de di e en es linguagens de p og amação (C++,
Py hon, Oc a e e LISP) acili ando assim a adap ação do u ilizado ao sis ema. Aqui se á
dada um b e e in odução aos concei os necessá ios pa a a comp eensão des e capí ulo, sendo
que uma explicação mais ex ensi a pode se encon ada em [47]. Di o is o, a a qui ec u a
ROS c ia uma camada de comunicação que acili a a oca de mensagens en e múl iplos nós.
En ende-se po nó, um p og ama que u iliza as e amen as disponibilizadas pela a qui ec u a
ROS pa a comunica e ealiza as a e as p e endidas. A comunicação en e di e en es nós é
ob ida a a és de ópicos e se iços, sendo que ambos u ilizam mensagens pa a o e ei o. Os
ópicos uncionam de o ma assínc ona, sendo que quando um nó publica uma mensagem
num ópico odos os nós que subsc e e am a esse ópico i am ecebe a mensagem publicada.
Po ou o lado, os se iços, o e ecem uma o ma de comunicação sínc ona en e apenas dois
nós, sendo que é necessá io o en io de um pedido e a consequen e ob enção de uma espos a,
pa a a comunicação se bem sucedida.
5.2 Módulos
Pa a uma a qui ecu a mais o ganizada, onde as pa es, quando in e ligadas o mam um
odo, e de ido à simplicidade de c ia um sis ema modula a a és do uso do ROS, es a
oi a abo dagem omada. A igu a 5.2 p e ende ilus a as comunicações en e os di e en es
módulos c iados.
37
5.2.5 Módulo Planeado
Es e módulo é esponsá el pelo planeamen o da ajec ó ia e pela ep esen ação g á ica do
mapa, ajec ó ia a segui e posição do obô.
O planeado ecebe um mapa do ipo .xml. Es e ichei o na sua cons i uição em a
seguin e es u u a:
<map>
<segmen >
<poin ><x>0.0</x><y>0.0</y></ poin >
<poin ><x>0.0</x><y>20.4</y></ poin >
</segmen >
<segmen >
<poin ><x>0.0</x><y>20.4</y></ poin >
<poin ><x>−5.8</x><y>20.4</y></ poin >
</segmen >
<segmen >
. . .
</segmen >
. . .
</map>
Cada segmen o de ec a é cons i uído po dois pon os ca esianos. Es es segmen os são
conside ados como uma on ei a en e o espaço li e e o espaço ocupado. Po an o, es es
necessi am de se o ien ados. A o ien ação é de inida da seguin e o ma: indo do p imei o
pon o pa a o segundo, o espaço que ica à di ei a desse segmen o é conside ado espaço li e.
Uma ez de inido o mapa, a ep esen ação g á ica do mesmo oi ei a a a és da biblio eca
Pygame4e encon a-se ep esen ada na igu a 5.8.
Pa a ealiza o planeamen o de um ajec ó ia, o planado ecebe a posição ac ual e a
posição des ino, de ol endo uma pilha de pon os in e médios que se ão en iados pa a o nó
na iga ion a a és do se iço addpoin desc i o an e io men e.
Planeado
Localização
Ac ual
Pon o
Des ino
pilha com
pon os in e medios
Nó
na iga ion
se iço addpoin
Figu a 5.9: Ilus ação do uncionamen o do planeado e in e acção com o módulo de na e-
gação.
4Es a biblio eca pode se encon ada em h ps://www.pygame.o g/wiki/abou
44

Figu a 5.8: Rep esen ação g á ica do mapa usado pelo planeado .
5.3 In e ace G á ica
Foi c iada uma in e ace g á ica com o in ui o de comunicação com o u ilizado inal. Es e
u ilizado pode se um isi an e ao ISR, ou um g upo de alunos que enha conhece os á ios
labo a ó ios exis en es. Com base nes es casos de uso, oi desen ol ida uma in e ace g á ica
simples e de en endimen o ácil, acili ando assim o p ocesso de u ilização da mesma.
Inicialmen e o u ilizado encon a a janela inicial p esen e na igu a 5.10. Aqui, pode
escolhe en e i pa a um si io em especi ico ou escolhe en e um dos i ine á ios de isi a
p é-de inidos. No p imei o caso a janela da igu a 5.11 (a) é exibida e o u ilizado escolhe o
des ino p e endido. Caso o u ilizado escolha a segunda opção, é exibida a janela da igu a
5.11 (b), e os i ine á ios disponí eis são exibidos.
Escolhido o des ino, e dada a indicação ao obô pa a inicia a iagem, a janela da igu a
5.12 (a) é exibida. Quando chega ao des ino, o u ilizado i á se a isado a a és da janela
da igu a 5.12 (b). Aqui é ques ionado sob e a p óxima decisão a oma . Caso se quei a
di igi a ou o si io, assim o pode aze , caso não quei a, pode en ia o obô pa a a sua
localização de epouso, onde i á espe a po ou o u ilizado .
45
Figu a 5.10: Janela p incipal da in e ace g á ica.
(a) Escolha do local a isi a (b) Escolha do i ine á io a ealiza
Figu a 5.11: Janelas de escolha do si io des ino na in e ace g á ica.
(a) Janela exibida quando o obô
se encon a em mo imen o
(b) Janela exibida quando o obô
chega ao des ino
Figu a 5.12: Janelas in o ma i as do es ado do obô.
46
Capí ulo 6
Resul ados e Discussão
De manei a a a alia o desempenho do sis ema, o am ealizados es es expe imen ais em
ambien e eal. Tendo em con a que o sis ema desen ol ido p e ende c ia a base pa a um
obô ecepcionis a, a manei a mais ap op iada pa a o es a se ia analisa o sucesso da a e a
de na egação, endo em conside ação a chegada do obô ao des ino e o e o associado. Ou a
análise impo an e se ia obse a a melho ia na localização esul an e do uso dos ma cado es
isuais.
6.1 Condições de Realização da Expe iência
A expe iência ealizada consis e na na egação a a és do pe cu so ilus ado na igu a 6.1.
O obô pa e da posição assinalada pela bandei a axad ezada, di igindo-se em di ecção ao
pon o A, seguido do pon o B, ol ando ao pon o A e e minando no si io de onde pa iu.
Em cada pon o mencionado an e io men e, o obô e ec ua uma pa agem e a dis ância da
posição eal de pa agem do obô em elação ao pon o p e endido pa a a pa agem é medida.
A condição de pa agem num pon o, é de inida a a és da dis ância euclidiana a esse pon o
se in e io a 20 cen íme os.
A posição dos ma cado es pa a co ecção da es imação da posição e o ien ação ao longo
da ajec ó ia, encon a-se p esen e na abela 6.1 e uma ilus ação da posição dos mesmos
em elação ao pe cu so e ec uado na igu a 6.1. O pe cu so oi ealizado qua o ezes, com
elocidades de 0.2, 0.3 e 0.6 m/s.
47
Labo a ó io de Robó ica Mó el
Sala de Tes es
Con abilidade
S
3
I Lab
Legenda:
Ma cado Visual Início/Fim Pon os de pa agem
A
B
Ida Vol a
y
x
(0,0)
6
3
7
21
4
5
89
Figu a 6.1: Pe cu so ealizado du an e os es es expe imen ais.
Tabela 6.1: Coo denadas xyz da posição dos ma cado es no e e encial do mundo, es ando
odos o ien ados pa a o in e io do co edo .
1 2 3 4 5 6 7 8 9
x
[m] 0.00 7.00 13.95 17.38 17.38 19.14 16.21 7.00 0.88
y
[m] 1.80 1.80 1.80 3.02 6.48 5.14 0.00 0.00 0.00
z
[m] 0.83 0.83 0.83 0.83 0.83 0.83 0.83 0.83 0.83
48
6.2 Resul ados
Pa a a análise dos dados da expe iência o am usadas como mé icas a média (µ) e o des io
pad ão (σ) da dis ância euclidiana do pon o eal de pa agem do obô ao pon o eal de des ino.
Tabela 6.2: Resul ados ob idos du an e a expe iência.
Dis ância Euclidiana
[cm] Tempo
Deco ido
[min]
%
Sucesso
µ σ des io
máximo
= 0.2
[m/s]
Pon o A 20.96 6.438 29.76
7:53:6 100%
Pon o B 17.01 9.115 30.06
Pon o A 25.64 12.235 36.49
Fim 23.18 9.979 31.95
= 0.3
[m/s]
Pon o A 14.84 7.536 23.19
5:01:4 100%
Pon o B 12.28 6.865 21.47
Pon o A 10.91 11.974 28.02
Fim 15.73 10.807 28.65
= 0.6
[m/s]
Pon o A 17.42 3.856 21.84
2:32:0 75%
Pon o B 32.55 4.569 35.46
Pon o A 20.66 13.721 36.40
Fim 29.82 8.096 38.27
Na abela 6.2 encon am-se os esul ados dos es es ealizados. Nes a pode-se e i ica que
pa a as elocidades de 0.2 e 0.3 m/s a dis ância euclidiana média de pa agem nos di e en es
pon os de es e es á p óxima do limia de inido, que é de 20 cen íme os. Já com a elocidade
de 0.6 m/s o obô icou a uma dis ância euclidiana média supe io ao limia , podendo es a
se jus i icada a a és do momen o que o obô possui na chegada ao pon o des ino, não
cessando o mo imen o imedia amen e após dada a indicação de pa agem, e caso enha um
pequeno e o de o ien ação, de ido ao núme o de lei u as e ec uada po ma cado a es a
elocidade se in e io , es e ai-se aduzi numa dis ância euclidiana ao pon o maio .
No en an o, o objec i o des e abalho é passa o su icien emen e p óximo dos pon os
objec i o de modo a possibili a a ealização da ajec ó ia, e não a passagem exa amen e
pelo pon o objec i o. Es a escolha oi omada, pois caso osse necessá io passa o mais
p óximo possí el do pon o, se ia necessá io aze um con olo mais ino e eduzi a elocidade
de modo a ob e essa exac idão. Assim, o c i é io adop ado oi um c i é io mais pe missi o.
Pos o is o, os esul ados mos a am-se bas an e sa is a ó ios.
49

0 5 10 15 20 25
X
4
2
0
2
4
6
8
10
Y
Localizacao
Localizacao Co igida
Figu a 6.2: Rep esen ação de uma das ajec ó ias ealizadas du an e os es es expe imen ais.
0123456
Amos as 1e11+1.5358819e18
0
5
10
15
20
25
X
T ajec o ia em X
X
X Co igido
hhhh
hhh 4.5x10^3
(a) E olução da posição em x
0123456
Amos as 1e11+1.5358819e18
4
2
0
2
4
6
8
10
Y
T ajec o ia em Y
Y
Y Co igido
4.5x10^3
(b) E olução da posição em y
Figu a 6.3: E olução da posição do obô no eixo de coo denadas xey, espec i amen e.
50
Tabela 6.3: E o na coo denada xem elação à igu a 6.3 (a), yem elação à igu a 6.3 (b)
exy em elação à igu a 6.2.
|µ|σmáximo
x
[m] 1.555 2.002 1.740
y
[m] 1.382 1.408 4.012
xy
[m] 2.319 2.223 4.579
Na igu a 6.2 encon a-se ep esen ada a ajec ó ia ealizada du an e o pe cu so de
es es, es ando ep esen ada a localização a a és da odome ia e a localização co igida
pelos ma cado es. É possí el e i ica a no ó ia melho ia p opo cionada pelos ma cado es
isuais colocados ao longo do pe cu so, e como a localização es imada a a és da odome ia
di e ge do mesmo, chegando a e e os de 1.74 mem xe4.012 mem y. Na igu a 6.3
(a) encon a-se ep esen ada a e olução da posição na coo denada xe na igu a 6.3 (b) a
e olução da posição na coo denada y. A abela 6.3 con em a média em módulo, o des io
pad ão e e o máximo en e a es imação de posição a a és da odome ia e a es imação
co igida pelos ma cado es.
51
52
Capí ulo 7
Conclusão e T abalho Fu u o
7.1 Conclusão
Ao longo des e abalho oi desen ol ido um sis ema com is a na c iação de um obô e-
cepcionis a pa a o piso 0 do Ins i u o de Sis emas e Robó ica, explo ando a u ilização de
ma cado es isuais pa a uma melho es imação da localização da pla a o ma mó el. Os
es es de desempenho e ec uados pe mi em conclui que as soluções implemen adas em um
desempenho sa is a ó io e que o uso dos ma cado es isuais é uma abo dagem iá el, não
in usi a e ba a a. No en an o, pa a condições de ambien e noc u no, onde a luminosi-
dade é baixa, a solução implemen ada não é ecomendada. Os algo i mos u ilizados não
se encon am op imizados, sendo que uma implemen ação na linguagem C++ i á melho a
conside a elmen e os empos de p ocessamen o.
7.2 T abalho Fu u o
Pa a abalho u u o exis em alguns melho amen os e di e en es abo dagens que se podem
ealiza . En e elas es ão:
•O melho amen o do algo i mo de na egação pa a a ealização de uma ajec ó ia mais
sua es, u ilizando po exemplo o mé odo de bandas elás icas [48]
•Es uda a u ilização de ou o ipo de il agem pa a a es imação da localização co i-
gida, como o il o de Kalman, explo ando os modelos de e o dos senso es
•Melho amen o da apa ência do in e ace g á ico
No en an o, no desen ol imen o de um obô in e ac i o, az odo o sen ido exis i em
ainda ou as uncionalidades ex a que se podem implemen a u u amen e como:
•A u ilização de uma câma a a de ec a o u ilizado e a a ia a elocidade de locomoção
do obô de aco do com a elocidade da pessoa
•A comunicação com o u ilizado se ei a po oz pa a uma in e ação mais na u al
53
[61] Muhammad Zohaib, M Pasha, RA Riaz, Nadeem Ja aid, Manzoo Ilahi, and RD Khan.
Con ol s a egies o mobile obo wi h obs acle a oidance. a Xi p ep in a -
Xi :1306.1144, 2013.
[62] Muhammad Zohaib, Syed Mus a a Pasha, Nadeem Ja aid, and Jamshed Iqbal. Iba:
In elligen bug algo i hm–a no el s a egy o na iga e mobile obo s au onomously. In
In e na ional Mul i Topic Con e ence, pages 291–299. Sp inge , 2013.
60