Navegação Topológica Aplicada a Agentes Robóticos Móveis

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