Home

veja o trabalho - Projetos

1.
2. Ac mulo de erros Como existem erros nas leituras dos sensores e na movimenta o do agente isso pode ocasionar erro no c lculo da posi o do agente e o mapa por ele gerado O erro seria simples se estas leituras fossem independentes o que n o caso do problema do SLAM j que a posi o atual e o mapa gerado s o entradas para o novo c lculo Ou seja um erro gerado numa primeira leitura afetar as demais leituras O funcionamento do algoritmo consiste em estimar a posi o do rob num momento seguinte tendo apenas a sua posi o atual o vetor de orienta o e as leituras dos sensores Ao confrontar a posi o atual e a estimativa de onde o rob deveria estar feito o c lculo dos erros e os dados gerados servem como entrada para os c lculos de gera o do mapa O mapa gerado por sua vez usado para o c lculo da estimativa da pr xima localiza o do rob Ou seja a sa da do algoritmo de localiza o um dado de entrada para o c lculo do mapa e a sa da do c lculo do mapa usado como entrada para o c lculo de localiza o Isso acaba gerando um c rculo vicioso e o erro gerado conhecido como erro de acumula o Visualmente o que acontece que o mapa n o tem alta fidelidade com a disposi o do ambiente e pode haver deslocamento de objetos por conta disso Associa o de dados Como o agente inserido no ambiente estar navegando por ele pode ser que este rob passe pelo mesmo local diversas v
3. o com o USARSim Estas ferramentas de intera o s o conhecidas como controladores e elas s o as respons veis por inserir os agentes os dados e informa es necess rias para a competi o al m dos algoritmos de cada equipe Como os controladores s o respons veis pela comunica o entre um agente e o operador ele precisa ser de f cil acesso e de claro entendimento para qualquer pessoa Por m ao participarem de algumas edi es de eventos de simula o de resgate ligados Virtual Robot Competition da RoboCup muita gente percebe a dificuldade de aprender a linguagem ou a forma como entrar os dados nessas ferramentas Existem algumas em que a curva de aprendizado n o t o grande mas elas s o de certa forma incompletas pois n o trazem em si algumas das coisas que a categoria necessita deixando a cargo das equipes a implementa o de coisas que deveriam ser intr nsecas ao programa de controle Em algumas dessas competi es alguns alunos e professores do Instituto Tecnol gico da Aeron utica e da Universidade Estadual Paulista perceberam tamb m essa dificuldade em in troduzir e retirar informa es do ambiente simulado E eles conclu ram que essas dificuldades se d o pela forma como as ferramentas controladoras tratam as informa es de modo n o in tuitivo e muitas vezes nem mesmo visual Ao se depararem com este inconveniente decidiram que uma boa maneira de contornar essa situa o seria criar um controlador p
4. que no caso da competi o da RoboCup esta estaticidade n o pode ser garantida as abordagens tradi cionais tamb m foram descartadas e por isso foi escolhido o fastSLAM que usa como princ pio a fatora o de Cholesky considerando a simula o de Monte Carlo e o ou Extended Kalman Filter que uma evolu o do filtro de Kalman 40 5 2 FastSLAM E uma abordagem eficiente que se baseia numa simples fatora o para a resolu o do pro blema de mapeamento e localiza o simult neos Com o FastSLAM passam a ser considerados modelos n o lineares e distribui es n o gaussianas Em termos probabil sticos o problema do SLAM pode ser descrito na seguinte forma P xp m Z Ea Xo Figura 5 1 F rmula distribui o probabil stica NIETO JOSE GUIVANT 2003 Onde x representa o vetor de posicionamento do agente no tempo k m o vetor estado que representa o mapa Zg o conjunto de observa es do mundo at o tempo k Ug o conjunto de entradas de controle de movimenta o e o vetor xo que representa o ponto inicial onde foi inserido o agente Em termos probabil sticos o problema do SLAM um processo de Markov Ou seja um processo estoc stico portanto o estado do mapa no tempo k 1 engloba toda a informa o necess ria para propagar o sistema para o estado no tempo k O modelo de movimenta o do rob considerado um processo de Markov e em termos de distribui o probabil stica pode ser descrito assi
5. o apesar de promover ru dos nas leituras dos sensores O sensor GroundTruth tamb m permitido nesta etapa obrigat rio para conclus o deste teste que o time de rob s encontre e relate a localiza o de pelo menos uma v tima dentro do tempo previsto de dura o do teste 2 5 Cen rios Os cen rios usados durante a competi o s o providos pelo e atrav s do simulador o USARSim Com anteced ncia de um dia ao da competi o informa es sobre o cen rio s o fornecidas s equipes Um exemplo dessas informa es s o a dificuldade e o tipo de cen rio Existem tamb m informa es que devem ser divulgadas a priori por exemplo a localiza o de um evento como o derramamento de um elemento qu mico em determinado ponto do mapa ou simplesmente mapas do ambiente da execu o O formato do mapa em GeoTiff Deve se considerar que os mapas podem n o estar atualizados e podem portanto conter erros devido s renova es passagens bloqueadas etc 2 6 Antes da execu o Antes das execu es cada time recebe um documento de texto que cont m as coordenadas da posi o de in cio x y z e orienta o para cada rob As coordenadas de posicionamento s o expressas em metros e as orienta es s o em radianos O arquivo consiste em n mero de linhas iguais ao n mero de rob s sendo que cada linha composta pelo n mero dela seguido da coordenada do ponto de in cio e das orienta es do rob a que ela se
6. o de ru dos de controle ou seja ser atualizado o valor em V e em G Isso ocorre para cada part cula As part culas representam os estados do agente em todo o decorrer do algoritmo No pr ximo passo do FastSLAM s o buscadas as observa es do agente FastSlam DMatrixArray FastSlam get_observations DMatrix x DMatrix lm DMatrix idf double rmax DMatrixArray observations observations get visible landmarks x lm idf rmax lm observations array 0 DMatrix z zeros 2 2 z compute_range_bearing x lm observations array 0 z return observations Figura 5 11 Trecho de c digo getObservations Dando seqii ncia ao FastSLAM adiciona se ru dos nas leituras das observa es Ent o s o calculadas as associa es de dados Pelo tamanho do c digo para este caso apenas irei citar o que feito Primeiramente s o buscadas as associa es e novas caracter sticas essas novas caracter sticas s o adicionadas ao mapa e a tabela de associa o de dados devolvida 46 No momento seguinte se for encontrado algum landmark s o computados atrav s do m todo compute weight os pesos relativos cada landmark Pesos esses que garantem o n vel de confian a de cada posi o do rob Al m disso o m todo feature update chamado O pri meiro passo deste m todo calcular a matriz jacobiana que como foi explicado anteriormente usada no filtro de Kalman Veja abaixo na figura 5 12 al
7. b ai a ae A 2 2 Configura es de Software e Hardware uuu 2 3 Esquema da Competi o wu sara nal e e E e ee e OR 24A Testes Elementares ra oe ee E Pp E Gi iak Sie DS Za dE Mobilidade t dira wosa ae tie Zita E a EET GA E iee 2 4 2 Mapeamento Localiza o de Vitima 2 CENTOS e sus am drai Zai en ieta gatu e A guri Ze E Ra ee 20 ATEEN Bi ba HEK gr IRA PRA TT pala b iE pala wl eia dk EEE EEE ass Gu 2G d GG d Sur d Se SEE ERS gd p 12 p 12 p 14 p 14 p 15 p 15 p 15 p 16 p 17 p 17 p 17 p 18 Be ALEGRE EZ Sg E Ge KTE AED HD ALD EXO RO BD RTE Kb e 2 9 Pol tica de Open Source bed d Ss alpes Gte data duze datei d 210 Combina es de sensores apr dp b break eee ES 2 11 Combina es de rob s uau uau 3 Tutorial para participa o na Virtual Robots Competition 3 1 Instala o no windows ST soe d EETA een dk bak GIN Sak SEE a 4 O Problema Alo OproblemadoSEAM Ss ZT E E SS a E OE OE E a TE GU da 4 1 1 Aspectos intr nsecos ao SLAM AAA 5 Algoritmos e Implementa es Experimentos e Resultados 5 1 A abordagem escolhida 2422s bee DR espa sea DEZ o FastS LAM ai ea waits Bist a Bs STA ETa hy SA en E EE ees Se eae 5 3 Os passos do FastSLAM deste trabalho AAA 5 4 Trechos de c digos e devidas explica es uuu 6 Conclus es 6 1 Trabalhos futuros AAA Refer ncias Bibliogr ficas p 30 p 31 p 32 p 39 p 39 p 42 p 43 p 48 p 48 p 49 RoboCup U
8. contador de hits contador de misses O resultado arredondado para um ou para zero Caso haja no o de regi o inexplorada basta verificar quais c lulas pos suem ambos os seus contadores zerados Quando se trata de ocupa o usando ponto flutuante a taxa de acertos contra a taxa de acertos mais a taxa de erros guardada na pr pria c lula O grande problema desta abordagem a quantidade de dados que ela agrega al m do fato de n o ser boa para ambientes abertos Em resumo essa abordagem com grades excelente quando se necessita extrema precis o por m para ambientes abertos ou muito grandes pode ser dif cil de programar devido quantidade de dados que precisam ser processados Mapas topol gicos Grafos e Diagramas de Voronoi c Nessa abordagem s o usadas em geral duas formas de representar o ambiente grafos e diagramas de Voronoi A primeira coisa que pode ser ressaltada neste tipo de abordagem a facilidade que ela traz para os algoritmos de planejamento de caminho Dentro do ambiente 36 os agentes necessitam sair de um ponto em chegar a outro Com um mapa topol gico isso se torna f cil pois f cil extrair esse tipo de informa o de grafos ou de diagramas de Voronoi Outro ponto importante aqui que nesta abordagem os mapas s o representados de forma compactada por isso a quantidade de dados agregados menor O fato que essa abordagem uma forma de explorar a navegabilidade do mapa portan
9. de forma aut noma e segura partes significativas do ambiente proporcionando mapas de alta qualidade e demonstrando a capacidade de busca e localiza o de v timas usando modelos rob ticos consistentes Ou seja ganham pontos adicionais as equipes que mostrarem um desempenho superior ao esperado Fatores de m rito e Um sensor especial de localiza o de v tima disponibilizado para uso das equipes Por este sensor ser utilizado cinco pontos s o atribu dos para equipe a cada v tima que for corretamente localizada Uma boa localiza o significa encontrar a v tima no recinto correto e em um raio de at um metro do ponto exato em que esta se encontra Para v timas que estejam se movimentando a localiza o deve estar a um metro da trajet ria tra ada pela v tima Cinco pontos adicionais s o dados para quem prover uma imagem da v tima A imagem deve ter uma qualidade que seja no m nimo suficiente para avaliar estado da v tima Se uma equipe opta pela utiliza o de processamento de imagem para detectar v timas ent o dez pontos s o acrescidos por fornecimento de imagem e de informa es 20 de localiza o Como foi dito anteriormente a foto deve ter uma qualidade que possibilite uma avalia o do estado da v tima At 50 pontos s o concedidos por explora o As equipes s o obrigadas a fornecer ma pas consistentes com formato formalmente descrito Equipes que completam um bom percentual do ambiente recebem
10. e a matriz de covari ncia que representa a incerteza do posicionamento Assim que novos landmarks s o encontrados tanto o vertor estado quanto a matriz de covari ncia s o adequados para comportar as novas informa es A posi o dos primeiros landmarks est apenas co relacionados com a medi o da dist ncia entre o marco e o rob Essa medi o projetada num quadro global de coordenadas A covari ncia num primeiro momento segue apenas as incertezas nas medi es e no posicionamento Os landmarks inicialmente s o baseados apenas na posi o do rob medida que o mapa re estimado a correla o diminui e a posi o do landmark na ltima estimativa e na nova estimativa relacionada Para fazer apenas uma atualiza o no mapa s o necess rios v rios passos O primeiro passo deste processo atualizar a posi o do rob considerando um modelo linear de movimenta o que descreve como os atuadores afetam a pose do rob na fatia de tempo anterior e na atual fatia de tempo Quando um landmark encontrado isso pode gerar uma nova marca o no mapa ou uma remarca o j que pode ser apenas a releitura de um landmark anteriormente detectado Apena novos landmarks s o incorporados ao mapa Com a diminui o das releituras dos landmarks diminui tamb m a precis o do mapa dado que os atuadores do agente possuem falhas Essas falhas s o replicadas na matriz de covari ncia que faz que com o valor da posi o do rob sej
11. em mudan as de level e Renderiza o de projetor Neste caso al m de arrumar foram feitas algumas otimiza es e Suporte 64 bits com v rias modifica es e Textura antes a tela podia ser renderizada de cabe a para baixo e Ffeitos clim ticos no OpenGLDrv Ap s ter sido completada a instala o do patch 3369 alguns arquivos devem ser baixados de mirror optus net sourceforge u us usarsim Fa a o download de 1 USARSimBaseFiles 3 11 zip 2 USARSimFull 3 1 1 zip 3 AAA MapBaseFiles V3 1 zip 4 DM YellowArena V3 1 zip A instala o do US ARSim e seus respectivos mapas encontram se nestes zipados Descompacte todos os arquivos e copie seus conte dos para a pasta UT2004 sobrescre vendo o que for necess rio Dentro do diret rio UT2004 entre na pasta System e d um duplo clique no arquivo make bat Se tudo estiver correto ser gerada a seguinte mensagem Success O error s O warning s ao final da execu o do make Para testar a instala o execute o arquivo DM USAR yellow 250 bat que se encontra no diret rio do UT2004 na pasta USAR_Maps Files RunServer Se n o houver erros durante a execu o deste bat ent o a instala o do simulador foi conclu da com sucesso 29 O controlador Faz parte da instala o a escolha de um controlador Neste tutorial foi escolhido o SimpleUI 2 1 por m este requer a instala o de uma das vers es do Visual C Vers es do Visual C po dem ser enco
12. isso atrapalhe seu objetivo principal de mapear e localizar se simultaneamente Abordagens Como foi comentado anteriormente as formas de se lidar com SLAM podem ser agrupadas em quatros fam lias portanto neste ponto ser explicado de forma mais detalhada cada uma delas 1 i il a features by grid fe Voronoi diagram fd Hybrid Figura 4 2 Fam lias do SLAM PFINGSTHORN 2006 Mapas m tricos Grade de Ocupa o b Grades de ocupa o fornecem uma representa o intuitiva de ambiente simulado Os pri meiros a usarem essa abordagem para mapeamento foram Elfes ELFES 1987 e Moravec MORAVEC 1988 As grades de ocupa o s o compostas por c lulas cada uma delas possui um valor que define se a mesma est ou n o ocupada ou seja se a regi o da c lula mapeada est 35 ou n o ocupada Na forma mais simples o valor agregado s c lulas bin rio ou seja apenas garantido que naquela regi o mapeada pela c lula possui ou n o um obst culo sem considerar outras caracter sticas poss vel tamb m colocar um terceiro valor que defina regi es ainda desconhecidas aos agentes Numa outra abordagem usam se valores em ponto flutuante sendo que valores compreendidos entre zero e um representam a certeza da informa o se a c lula est ou n o ocupada A abordagem de grades de ocupa o possui muitos benef cios quando comparada com as demais O maior desses benef cios que a representa o fornecida do a
13. mapeamento do vetor estado numa observa o atual zt A matriz do ganho de Kalman Kt tem um tamanho 3 pelo tamanho do vetor estado e geralmente essa matriz n o esparsa Nos passos quatro e cinco o vetor estado e a matriz das incertezas s o atualizados afetando diretamente no conhecimento do ambiente que tem o agente A principal caracter stica da abordagem com filtro de Kalman que todo o estado posterior estimado sobre o mapa de forma on line Isso implica na manuten o em tempo integral das incertezas no mapa Outra caracter stica importante da abordagem de Kalman que todo ru do governado por uma distribui o Gaussiana Isso pode ser considerado como um problema que imp e severas limita es ao algoritmo j que com exce o da associa o dos dados os outros ru dos gerados s o governados por outras fun es ou distribui es como no caso do ru do do od metro onde as fun es s o trigonom tricas Em resumo filtro de Kalman uma solu o completa para SLAM que se baseia em um algoritmo incremental Al m disso ele tem v rias propriedades interessantes e relativamente f cil de compreender e aplicar No entanto alguns dos pressupostos que s o impostos pelo modelo Gaussiano s o claramente pouco precisos Al m disso a abordagem coloca alguns desafios significativos a ultrapassar antes de poder ser aplicado com sucesso O principal desafio envolve o esfor o significativo que se tem para colocar em p
14. representa a confian a ou a import ncia deste estado para a cria o do mapa 9 2 Neste ponto s o atualizadas os marcos Para cada umu calculado o ganho de Kalman Neste passo o agente cria o mapa com essas informa es 9 3 Se houver novos marcos estes ser o atualizados neste passo 5 4 Trechos de c digos e devidas explica es Como foi explicado a abordagem FastSLAM foi escolhida para resolver o problema do SLAM para o controlador que est sendo criado para a Virtual Robots Competition Por m foi adicionada a caracter stica de caminho decidido ou seja alguns pontos ser o passados em cada atualiza o para o rob de forma que se consiga fazer com que o agente passeie por todo o mapa descobrindo todo o ambiente As coordenadas passadas ao agente foram chamadas por conven o de waypoints e a menos que haja obst culos esses s o os vetores x y pelo qual o rob deve passar Antes de tudo necess rio explicar que a classe DMatrix BECERRA 2008 est sendo usada para manipular matrizes pois esta classe possui v rias f rmulas aplic veis elas Dentro da divis o do grupo formado pelas universidades fiquei respons vel por criar os algoritmos do SLAM sem preocupar me com a ordem de execu o deles A ordem e a parte gr fica do SLAM ficaram para outros membros da equipe portanto ser explicada a ordem em que s o chamadas as implementa es que fiz por m pode ser que por decis o do grupo a or
15. 50 pontos A quantidade definida pelos rbitros do evento Para porcentagens mais baixas o n mero de pontos sofre um decr scimo linear de zero a cinco pontos de pena at a penalidade atingir o valor m ximo dado pela explo ra o Por cada v tima n o reportada que esteja numa rea tida como completada zona marcada com a cor verde no arquivo de bitmap At 50 pontos s o concedidos por mapeamento O mapeamento julgado pelos seguintes crit rios Qualidade de m trica A precis o do arquivo de mapa comparado com o terreno real Fus o de leituras dos ve culos As equipes devem transformar todos os arquivos de mapa em um s arquivo As equipes que incluem as informa es de sa da de v rios rob s numa s t m um b nus na pontua o Atribui o Uma das raz es para se gerar um mapa transmitir informa es Esta informa o frequentemente representada como atributos no mapa Pontos s o acrescidos por inclus o de informa es sobre a localiza o de v timas localiza o de obst culos e os caminhos que os rob s tomaram Agrupamento A mais alta tarefa de mapeamento reconhecer que elementos dis cretos no mapa constituem outros elementos Por exemplo o fato de v rias paredes formarem um c modo ou um conjunto particular de obst culos serem um carro Pontos de b nus s o concedidos por notar tais grupos no mapa Qualidade no esqueleto do mapa O esqueleto
16. M sendo a segunda a utilizada como base para este trabalho e ser adiante melhor explicada Mapas baseados em caracter sticas Filtro de Kalman a a abordagem mais antiga de todas e segundo Bayu Slamet e Max Pfingsthorn a mais influente dentre as existentes Houve uma s rie de estudos em cima do filtro criado por Rudolf Emil K lm n que resultaram na abordagem atual utilizada pelo problema do SLAM Mapas em que se usa o Filtro de Kalman s o limitados apenas pela posi o atual do agente e pelas posi es estimadas das marca es chamadas aqui de landmarks A id ia b sica desta abordagem descrever o mapa como uma distribui o gaussiana usando se a combina o da posi o do rob e posi o dos landmarks O mapa representando por u que um vetor estado que possui todas as vari veis relevantes para a distribui o gaussiana Este vetor estado possui um 37 tamanho 3 2N que constitu do pelas informa es de posi o em 2D do rob x y 0 e a posi o representada por duas informa es x y de todos os N landmarks A covari ncia desta distribui o Gaussiana representa a incerteza sobre a combina o posi o atual do rob e posi o dos landmarks Atrav s da recurs o encontrada e atualizada a distribui o Gaussiana ou seja encontrando as solu es mais prov veis do mapa A princ pio o algoritmo possui um mapa sem landmarks Ent o o mapa consiste apenas na posi o do rob
17. SARSim VR ITA UFSC SLAM IA EKF Lista de abreviaturas e siglas Junta internacional em prol da rob tica inteligente Urban Search And Rescue Simulation Virtual Robots Instituto Tecnol gico da Aeron utica Universidade Federal de Santa Catarina Simultaneos Localization And Mapping Intelig ncia Artificial Extended Kalman Filter P P P V V VVP 2 1 2 2 23 2 4 2 5 2 6 2 7 2 8 4 1 4 2 5 1 52 5 3 5 4 5 5 5 6 5 7 5 8 5 9 Lista de Figuras Servidor de Comunica o Wireless VIRTUAL ooa aaa aaae p 16 Vito GGI oa ae RT d OU E A MA A A A p 23 Hammer dark Guk gar Sen a gd d dE Ea EEE SAE RAE SAS p 23 P2at acasos ams APS CADENA I DANI KE d ba bei bak b bo di ke EK p 24 PAG Au hh oe a E a een di QE dE Di UT A E rda p 24 TGAO GEG Si E EEK ei E OEE SEE OEE SRS p 25 Det lt a A ses pa qu EA tiei Ge aA Se O ara Sie Er pg ene ek p 25 BETE da eka Ea d GEk EN EEK Ek e p 26 SLAM BAILEY 2006 2 aca gre gupera ere uzu eit AA ait ep p 31 Fam lias do SLAM PFINGSTHORN 2006 p 34 F rmula distribui o probabil stica NIETO JOSE GUIVANT 2003 p 40 F rmula distribui o probabil stica considerando processo de Markov NIETO JOSE GUIVANT 2003 cu arado Gut pesto Br Gui du ES dE ES p 40 F rmula modelo de observa o probabil stico NIETO JOSE GUIVANT 2003 ca irae Gia Get Gi a Bx ee Sa Byte kd uai Gua GGE Su Sd p 40 F rmul
18. Saber o que poderia ser usado para o mapeamento do mundo quais controladores estavam dispon veis como interagir com o ambiente e com os agentes nele inseridos Para se atingir o objetivo da cria o do algo ritmo de FastSLAM foi necess rio passar por sua base que consistia nos primeiros algoritmos de SLAM entender as abordagens mais comuns e reaprender sobre alguns conceitos da ma tem tica O passo seguinte foi escolher de forma emp rica aquela que poderia ser a melhor abordagem considerando se o ambiente proposto pela Virtual Robots Competition E por fim houveram defini es de como implementar a abordagem e como fazer a integra o com o resto do sistema Acredita se que este trabalho ter relev ncia para a academia por se tratar de um assunto atual e de interesse comunidade cient fica e aos profissionais de Ci ncias da Com puta o automa o e Intelig ncia artificial Pois nele s o apresentados conceitos que podem servir de base para demais trabalhos usando t cnicas de mapeamento e localiza o simult neos 6 1 Trabalhos futuros Como este um trabalho evolutivo alguns dos trabalhos que poderiam ajudar neste pro cesso seriam e Criar as chamadas e gr ficos para testar visualmente o projeto e Testar em aut matos reais e Participar de competi es v nculadas Virtual Robots para testar e melhorar os algorit mos 49 Refer ncias Bibliogr ficas BAILEY T SLAM 2006 Dispon vel em lt ht
19. UNIVERSIDADE FEDERAL DE SANTA CATARINA DEPARTAMENTO DE INFORM TICA E ESTAT STICA BACHARELADO EM CI NCIAS DA COMPUTA O Tutorial para participa o na Virtual Robots Competitions da RoboCup e implementa o de um controlador para a categoria Marcelo Ribeiro Xavier da Silva Trabalho de conclus o de curso apresentada como parte dos requisitos para obten o do grau Bacharel em Ci ncias da Computa o Florian polis SC 2008 1 Marcelo Ribeiro Xavier da Silva Tutorial para participa o na Virtual Robots Competitions da RoboCup e implementa o de um controlador para a categoria Trabalho de conclus o de curso apresentada como parte dos requisitos para obten o do grau Bacharel em Ci ncias da Computa o Orientador Professor Doutor Mauro Roisenberg Banca Examinadora Professor Doutor Jovelino Falqueto Professor Doutor Ricardo Azambuja Silveira Professora Doutora Silvia Modesto Nassar Sum rio Lista de abreviaturas e siglas Lista de Figuras Resumo 1 Introdu o 1 1 Justificativa sus kd Eb Eno E guk RE ER E E EMS e E EES e 1 2 GRISEZ app Ea gira E a TR b Da biek Sie i E Ed big 12 gt Objetiy s Ger is nrs on EA ole be Zu Gaia da eio 1 2 2 Objetivos especificos gipu gir dire aite ab arre eb 1 3 Metodologia ss gun gg Ee iE egit dud edi ed E CA EA edge 2 Regras e funcionamento da Virtual Robots Competitions 2L Escopo e Defini o ae 48 E DE a ae we E db batai ke
20. a Posi o posterior na forma fatorada NIETO JOSE GUIVANT 2003 p 41 F rmula Predi o do pr ximo estado NIETO JOSE GUIVANT 2003 p 41 F rmula Estimando os N landmarks NIETO JOSE GUIVANT 2003 p 41 F rmula predi o BAILEY 2006 Au p 42 Trecho de c digo addControlNoise o ao p 44 Trecho de c digo multivariateGauss uuu p 44 5 10 Trecho de c digo predict aoe eo E a aks HS cet E ees p 45 5 11 Trecho de c digo getObservations 5 12 Trecho de c digo featureUpdate 5 13 Trecho de c digo KFCholeskyUpdate 0 0 Resumo A rea de Intelig ncia Artificial ainda est em estado de evolu o em raz o disso foi criada uma junta internacional conhecida como RoboCup que tem como principal objetivo incentivar este crescimento Isto feito atrav s da promo o de in meras competi es relativas rob tica inteligente Dentre essas competi es existe a Virtual Robots Competition por m esta ainda n o possui grande representatividade no Brasil Com o intuito de se divulgar esta competi o aqui v rias universidades se propuseram a criar uma ferramenta nacional para ser usada na Vir tual Robots Competition al m de servir como instrumento did tico para o aprendizado de IA Parte desta ferramenta trata da localiza o e mapeamento simult neos ou SLAM Este processo feito por meio de agentes inseridos em diversos ambientes E o aprendizado pr tico te rico
21. a cada vez maior isso acontece at que uma nova releitura seja feita Em geral as releituras fazem com que haja uma queda brusca no valor das incertezas E uma queda no valor das incertezas torna mais preciso o valor da posi o do agente que por sua vez faz com que o valor da posi o dos landmarks aumente a precis o tamb m O processo do SLAM baseado no filtro de Kalman pode ser resumido nos passos abaixo e Dado Estimativa anterior do mapa ut 1 e Xt 1 e Resultado Estimativa atualizada do mapa ut e Xt 1 ut ut 1 But 2 Yt Lt 1 Xatuador 3 Kt Xt C T GI Lmedi es 1 38 4 ut ut Kt zt Cut 5 Xt 1 Kt Ct t No primeiro passo o mapa atualizado considerando o modelo linear de movimenta o B e o comando de movimenta o que foi passado ao agente ut No segundo passo as incertezas do mapa s o atualizadas considerando o somat rio das incertezas dos atuadores Zatuador Nas equa es acima considerado que os landmarks s o fixos e por isso apenas a posi o do rob atualizada Em casos em que n o se assegura a est tica como caracter stica dos landmarks estes tamb m s o atualizados a cada nova observa o No terceiro passo calculado o ganho de Kalman aqui que s o propagadas as incertezas para o mapa Neste c lculo tamb m s o incorporadas as incertezas nas medi es medi es considerando a observa o atual zt A matriz C apenas uma conveni ncia que descreve o
22. ados em http www robocuprescue org wiki index php title Virtualrobots dando os devidos cr ditos aos autores O c digo fonte da competi o realizada no ano anterior pode ser encontrado nessa mesma p gina 2 10 Combina es de sensores Qualquer combina o dos sensores listados abaixo permitida por m combina es n o real sticas entre rob s e sensores podem ser vetadas Por exemplo um rob Zerg utilizando um sensor que ele n o possui como o SickLMS e Encoder codificador e GPS e Hokuyo e INS e Odometry odometria e RobotCamera c mera rob tica e SickLMS e Sonar e VictSensor sensor de v tima e RFIDSensor e TouchSensor sensor de toque 2 11 Combina es de rob s As equipes podem usar qualquer combina o dos rob s representados nas figuras ROB S 2 2 2 8 23 a Real ATRV r b Simulated ATRVIr Figura 2 2 atrvjr a Real HMMWV by Simulated HMMWV Figura 2 3 hammer 24 Figura 2 4 p2at a Real EGIA bi Simulated P2DK Figura 2 5 p2dx 25 bi Simulated Talon Figura 2 6 talon ee al Real Taleb bn hi Simulated Teena Figura 2 7 telemax a Real Zen Figura 2 8 zerg bi Simulated Zeng 26 27 3 Tutorial para participa o na Virtual Robots Competition Neste cap tulo ser o tratadas as instala es das ferramentas necess rias para que se possa ingressar na Virtual Robots Competition 3 1 Instala o no
23. azer com que um agente inserido num ambiente consiga gerar um mapa e ao mesmo tempo se localize neste mapa sem possuir informa es adicionais excetuando o ponto em que foi inserido no ambiente e a sua orienta o inicial Alguns autores definem o problema do SLAM como sendo uma forma de capacitar um rob a responder de forma adequada pergunta Onde eu estou importante ressaltar que a localiza o do agente e o mapa criado s o dependentes de forma c clica em outras palavras a entrada de dados de um sa da de dados do outro Ou seja como a localiza o depende do mapeamento e o mapeamento precisa da localiza o um erro em um deles vai gerar um erro no outro e portanto todas as informa es obtidas na sequ ncia v o ecoar este erro A figura 4 1 representa o SLAM em sua ess ncia Landmark Estimated Figura 4 1 SLAM BAILEY 2006 32 Considerando o modo como as informa es est o descritas num ambiente e a forma de intera o com estas informa es o SLAM se divide em quatro fam lias apresentadas abaixo 1 Abordagens que provem uma grade de ocupa o do mapa 2 Abordagens que organizam de forma topol gica o mapa 3 Abordagens que s o um h brido das outras abordagens de SLAM 4 Abordagens que empregam filtro de Kalman baseadas em caracter sticas do mapa como por exemplo marca es landmarks e ou obst culos 4 1 1 Aspectos intr nsecos ao SLAM Alguns aspectos que s
24. cais podem ser indicados com uma cruz um c rculo ou um s mbolo similar O tamanho do s mbolo deve ser de um tamanho que na escala do mapa n o seja superior a um metro quadrado Se uma 19 v tima for encontrada em movimento deve ser indicado que a mesma estava a p e deve ser apontado o seu caminho e Opcional Qualquer informa o recolhida durante a competi o Por exemplo scre enshots das v timas informa es adicionais relativas s v timas Em caso de scre enshots serem fornecidos o arquivo deve ser nomeado consistentemente com os nomes utilizados no arquivo de v timas a fim de fazer uma associa o imediata e Todas as informa es devem ser apresentadas ao rbitro em no mais tardar 15 minutos ap s o prazo de t rmino da execu o Informa es atrasadas n o s o aceitas para fins de pontua o importante deixar claro que mesmo que uma equipe utilize dez agentes ao final da etapa ape nas um arquivo deve ser enviado ao rbitro O operador que iniciou os rob s deve preparar este arquivo Qualquer outra pessoa que manipule os arquivos gerados pelos rob s ser contabili zada como um operador adicional Cabe equipe decidir qual dos arquivos deve ser entregue Se uma fus o dos arquivos gerados for mais abrangente permitido que seja entregue este arquivo 2 8 Pontua o O sistema de pontua o baseia se no crit rio de recompensar equipes que sejam capazes de explorar
25. ddControlNoise DMatrix FastSlam multivariate gauss DMatrix x DMatrix P int n DMatrix X tra P DMatrix Si Chol X DMatrix S zeros 2 2 S 1 1 Si l 3 S 2 2 Si 2 3 X randn 2 1 DMatrix s S X x ones 1 n return s Figura 5 9 Trecho de c digo multivariateGauss Neste trecho de c digo figura 5 9 a matriz de covari ncia transposta e em seguida fatorada usando se o m todo de Cholesky Depois multiplicada por uma matriz gerada de forma rand mica usando se uma distribui o normal com m dia zero e vari ncia unit ria Resumindo este m todo devolve uma amostra aleat ria de distribui o Gaussiana multivariada Na seqii ncia do FastSLAM o pr ximo m todo a ser chamado seria o de predi o 45 FastSlam Particle FastSlam predict Particle particle double V double G DMatrix Q double WB double dt int addrandom DMatrix VG zeros 2 1 DMatrix temp zeros 2 1 temp 1 1 V temp 2 1 G if addrandom 1 do enntral e VG multivariate_gauss temp Q 1 V VG 1 1 B G VG 2 1 DMatrix eu xv particle xv particle xv 1 particle xv 2 particle xv 3 return particle xv 1 1 V dt cos G xv 3 1 xv 2 1 V dt sin Gtxv 3 1 pi_to_pi xv 3 V dt sin G WB Figura 5 10 Trecho de c digo predict Neste m todo expresso na figura 5 10 fica a l gica da predi o do pr ximo estado ent o feita a adi
26. dem se modifique O primeiro passo do processo computar os valores de posicionamento ou seja conjunto de waypoints conjunto de landmarks posi o atual do rob e o seu respectivo ngulo Na seqii ncia s o adicionados os ru dos de controle Acima figura 5 8 temos G que o ngulo que indica o direcionamento do agente V re presenta a velocidade do agente que junto com G acumula os erros de controle e Q denota a matriz de covari ncia O algoritmo acima funciona da seguinte maneira primeiramente com puta os valores atuais tanto de V quanto de G na matriz VG que representa os erros de controle Na seqii ncia verifica se a necessidade nesta itera o de adicionar erros de controle isso decidido na chamada do m todo caso seja o algoritmo de multivaria o gaussiana calcular o erro no controle Os erros s o atualizados nas vari veis V e G e estas por sua vez s o retorna das em forma de matriz de erros de controle Para facilitar o entendimento vejamos abaixo na figura 5 9 o c digo da multivaria o gaussiana 44 DMatrix FastSlam add control noise double V double G DMatrix Q double addnoise se to nominal control values DMatrix C zeros 2 1 DMatrix VG zeros 2 1 A do e E Add andar VG 1 V VG 2 G if addnoise 1 C multivariate_gauss VG Q 1 if Q might be correlated V C 1 G C 2 VG 1 V VG 2 G return VG Figura 5 8 Trecho de c digo a
27. do SLAM o tema abordado por este trabalho sendo um dos objetos criar algoritmos para serem usados na nova ferramenta de controle alcunhada de BrasilVR Al m disso este trabalho servir de facilitador para ingresso na competi o atrav s de um tutorial de instala o e configura o das ferramentas necess rias 1 Introdu o A intelig ncia artificial a rea de pesquisa das ci ncias da computa o dedicada a estudar os problemas complexos aqueles cuja computa o convencional n o consegue ou tem grande dificuldade em resolver A express o rob vem do tcheco robota e significa trabalhador foi criada por Karel Capek em 1917 Ou seja um rob uma m quina que exerce um trabalho espec fico um trabalho para o qual fora justamente criada Com a inje o de Intelig ncia Artificial essas m quinas est o exercendo cada vez melhor suas fun es e est o se tornando cada vez mais abrangentes executando cada vez mais tarefas Com a finalidade de promover a Intelig ncia Artificial e a Rob tica Inteligente foi criada uma junta Internacional chamada de Para cumprir essa fun o de disseminar e fazer evoluir a cultura da rob tica a RoboCup promove v rias competi es que objetivam a integra o de in meras tecnologias algoritmos e m todos Dentre estas competi es existe a Virtual Robots Competition VIRTUAL 2006 que como induz o nome uma simula o de rob s A Virtual Robots Competition intr
28. do mapa reduz um mapa complexo em um conjunto de locais conectados Por exemplo quando se representa um corre dor com um n mero elevado de sa das um esqueleto pode representar esse corredor como uma linha e s mbolos ao longo dessa linha podem representar as portas Um mapa pode ser impreciso em termos de medidas um corredor pode ser representado com 20 metros de comprimento ao inv s de 15 metros mas pode ter uma estrutura ou esqueleto precisa j que as informa es contidas no esqueleto n o dependem da m trica A categoria permite que os ju zes d em pontos por qu o preciso o esqueleto do mapa est representado 21 Utilidade Um dos principais objetivos de fornecer um mapa criar a possibilidade de uma primeira resposta ao utilizar o mapa para determinar quais reas foram com pletadas onde os riscos podem ser localizados e onde as v timas foram capturadas Fatores de penalidade e Operadores se a equipe usa N operadores a pontua o ser dividia por N 1 Isso implica que cada equipe usar apenas um operador para n o perder pontos e Alarmes falsos Para cada v tima que for incorretamente reportada aplicada uma penali dade de cinco pontos Um alarme falso tido quando a v tima est posicionada a mais de um metro do local que fora relatado No caso de uma v tima que esteja se movimentando isso se aplica dist ncia da sua trajet ria e Choque Cada v tima tocada por um rob ir inco
29. ezes Essa redund ncia de informa o tem um valor inestim vel e pode ser um grande benef cio para diminuir o ac mulo de erros j que as informa es geradas podem ser comparadas e aproximadas Por m essa informa o pode ser interpretada de forma errada como por exemplo comparar duas leituras de coisas diferentes achando que se tratam da mesma informa o al m do fato de que com o aumento do n mero de vezes que um agente passa pelo mesmo ambiente aumentar tamb m progressivamente as compara es 34 Ambientes e obst culos din micos Dependendo do ambiente em que o agente seja inserido as informa es pr vias que ele possui podem estar desatualizadas Por exemplo em um cen rio em que haja pessoas ve culos ou at outros agentes estes podem ter se movido ou algum objeto pode ter sido retirado do local N o existe uma solu o geral para esse problema Nestes casos costuma se fazer com que os agentes explorem por uma faixa de tempo as localidades do mapa considerando que o ambiente seja est tico Explora o do desconhecido Tipicamente as informa es que s o passadas ao agente sobre o ambiente s o m nimas e o agente tem de estar preparado para lidar com situa es imprevistas como buracos ou escadas O rob precisa ter em seu conjunto de estrat gias algumas formas de lidar com situa es ines peradas podendo assim contornar problemas e continuar sua navega o de forma aut noma sem que
30. fazer isso considerando mo delos n o lineares de movimenta o al m de distribui es n o gaussianas para c lculo de erros nos sensores e atuadores 5 3 Os passos do FastSLAM deste trabalho O FastSLAM implementado tem a seguinte ordem de execu o Passo 1 S o computados os valores necess rios para o agente poder se movimentar e se loca lizar ou seja conjunto de waypoints conjunto de landmarks posi o atual do agente no mapa e o sua respectiva orienta o representada por um ngulo Passo 2 Na seqii ncia s o adicionados os ru dos de controle Passo 3 Predi o da posi o posterior do rob 9 3 Se houver novos marcos estes ser o atualizados neste passo Tupi HW AT coal Oe i tel Ara fy KZ D po UE Neg TE VAT sino i FR 5 AT ns E Ou TE SIDO Figura 5 7 F rmula predigao BAILEY 2006 Passo 3 Predi o da posi o posterior do rob Passo 4 V velocidade do agente e G ngulo do agente s o acrescidos de erros de controle calculados usando covari ncia Passo 5 Predi o do mapa no momento seguinte F rmula do passo 3 aplicado cada marco que comp e o mapa Passo 6 As observa es dos sensores do rob s o coletadas Passo 7 S o adicionados erros de observa o Passo 8 calculada a associa o de dados dos marcos coletados Passo 9 feita atualiza o do mapa 43 9 1 S o computados os pesos dos marcos Cada peso
31. foi encontrada Como toda v tima possui um sensor chamado de sensor da v tima o ltimo campo pode ter dois valores v lidos Se o sensor da v tima for usado para encontr la ent o o valor atribu do ao campo VSEN SOR por m se n o for usado esse sensor o valor que o campo recebe VISUAL A ltima linha do arquivo de v timas deve conter uma string com o valor END O campo ID pode receber qualquer valor de string pois serve nica e exclusivamente para identificar a v tima descoberta pela equipe na posi o relatada e Obrigat rio Um arquivo chamado de arquivo bitmap contendo o mapa e informa es adicionais Este arquivo deve conter m ltiplos mapas sobrepostos Todas as sobreposi es devem ser georeferenciadas isto devem possuir marca es que definam obst cu los e precisam estar tamb m no formato de arquivos GeoTiff ou Mif al m de cobrirem uma regi o por completo A sugest o que os mapas de sobreposi es representem pro babilidades ou agrupamentos de mapa ou reas cobertas por cada rob As sobreposi es devem representar a seguinte informa o com as dadas colora es N o atravess vel Preto RGB O 0 0 Completo atravess vel e livre de v timas Verde RGB 0 255 0 Incompleto atravess vel por m n o necessariamente livre de v timas Branco RGB 255 255 255 Inexplorado Azul RGB 0 0 255 Localiza o de V tima Vermelho 255 0 0 Lo
32. guns trechos do c digo do m todo feature update FastSlam Particle FastSlam feature update Particle particle DMatrix z DMatrix idf DMatrix R compute underline space weight v z complacobians array 0 DMatrixArray xfPf KF_cholesky_update xfl Pfl vaux R Hfaux xfl xfPf array 0 Pfl xfPf array 1 xfPf KE cholesky update xf2 Pfl vaux R Hfaux xf2 xfPf array lo Pf2 xfPf array 1 Pf Pfl amp amp Pf2 xf xfl amp amp xf2 particle xf xf particle pf Pf return particle Figura 5 12 Trecho de c digo featureUpdate 47 Neste trecho podemos ver que o valor verdadeiro da posi o passada como par metro z subtra do do valor que foi predito esse valor usado para recalcular as vari veis que ser o utili zadas no filtro de Kalman estendido O m todo KF cholesky update quem faz a simula o de Monte Carlo Ele utilizado para encontrar a matriz triangular inferior da matriz de covari ncia P aplicado P um vetor de choques n o co relacionados chamado aqui de u que produz um vetor de choques chamado de Lu Esse vetor possui as propriedades de covari ncia do sistema modelado O m todo KF cholesky update pode ser visto abaixo na figura 5 13 FastSlam DMatrixArray FastSlam KF cholesky update DMatrix x DMatrix P DMatrix v DMatrix R DMatrix H DMatrix PHt S SCholAux PHt Prtra H S H PHt R S S ttra S 0 5 make symmetric SCho
33. lAux Chol S DMatrix SChol zeros 2 2 SChol 1 1 SCholAux 1 3 SChol 1 2 SCholAux 2 1 SChol 2 1 0 SChol 2 2 SCholAux 2 3 DMatrix SCholInv zeros 2 2 SCholInv inv SChol Triangular matrix DMatrix Wl zeros 2 2 Wl PHt SCholInv DMatrix W zeros 2 2 W Mi tra SCholInv xX x Wy Update P P Wl tra Wl DMatrixArray cholesky cholesky array new DMatrix 2 cholesky array 0 x cholesky array 1 P return cholesky Figura 5 13 Trecho de c digo KFCholeskyUpdate Este m todo calcula o EKF considerando o estado anterior x e P a inova o v R e o modelo de observa o H devidamente linearizado Dando seqii ncia ao FastSLAM caso seja encontrado um novo landmark este landmark adicionado matriz de part culas E assim se reinicia o ciclo que s finalizado quando acabam os waypoints ou quando se esgota o tempo 48 6 Conclus es A cria o dos algoritmos do FastSLAM permitiu atingir parcialmente os objetos deste tra balho A parcialidade devida depend ncia do desempenho obtido pelas demais universidades envolvidas neste processo Por m o que foi delegado para a equipe da Universidade Federal de Santa Catarina foi atingido em sua completude Para que tudo que se previu seja alcan ado falta apenas integra o com os demais m dulos do projeto O primeiro momento neste projeto foi descobrir como funcionava a Virtual Robots Competition
34. m Piru Ur Figura 5 2 F rmula distribui o probabil stica considerando processo de Markov NIETO JOSE GUIVANT 2003 O modelo de observa o que diz respeito s observa es do estado do ambiente descrito por um modelo probabil stico que obedece tamb m propriedade de Markov Plznlan mo Figura 5 3 F rmula modelo de observa o probabil stico NIETO JOSE GUIVANT 2003 Para se atingir o mapeamento e localiza o simult neos usa se o filtro de Bayes Por m para mapas tridimensionais acaba se tornando uma op o muito custosa A alternativa para o filtro Bayessiano a utiliza o do Extended Kalman Filter O EKF lineariza fun es n o lineares e pode ser descrito da seguinte maneira 1 xk f xk 1 uk wk 41 2 zk h xk vk A fun o f calcula o pr ximo estado estado previsto considerando o estado anterior e a fun o h calcula a previs o de medi o considerando o estado previsto Por m essas fun es n o podem ser aplicadas diretamente covari ncia Ao inv s disso computada a matriz jaco biana Esta matriz atualizada a cada tempo k com os valores das predi es Essas matrizes por sua vez s o aplicadas no filtro de Kalman Ou seja lineariza se a fun o que depois filtrada com o filtro de Kalman O EKF por m pode ser fr gil e pode falhar catastroficamente em algumas situa es j que s lidam com distribui es unimodais distribui es que possue
35. m apenas um m ximo local A id ia por tr s do FastSLAM a fatora o Essa id ia baseada na observa o de que se o caminho do rob fosse realmente conhecido ent o todas as marca es landmarks seriam mutuamente independentes Na pr tica o caminho obviamente desconhe cido por m essa independ ncia condicional nos permite estimar a posi o posterior do rob da seguinte forma fatorada P a m Z U zo P m z Z U 29 P 2 Z U o N II pide SR ON 29 P 2 Z ON zo i 1 Figura 5 4 F rmula Posi o posterior na forma fatorada NIETO JOSE GUIVANT 2003 A fatora o a id ia fundamental por tr s do FastSLAM Com ela o problema decom posto em localiza o e estimativa da posi o dos N landmarks Para isso o FastSLAM necessita de um filtro de part culas para poder estimar a posi o posterior do agente P a Z U o Figura 5 5 F rmula Predi o do pr ximo estado NIETO JOSE GUIVANT 2003 Esse filtro pode ser atualizado de forma constante para cada part cula no filtro Isso implica em N Kalman filters para estimar os N landmarks Pilek Z UP xo Figura 5 6 F rmula Estimando os N landmarks NIETO JOSE GUIVANT 2003 Em MONTEMERLO S THRUN 2002 foi mostrado que o filtro inteiro pode ser atuali zado em tempo logar tmico em fun o dos N landmarks Claro que isso tamb m conseguido 42 atrav s de outras abordagens por m o diferencial do FastSLAM
36. mbi ente pode ser usada diretamente para a navega o do agente facilitando tamb m na cria o dos algoritmos de desvio de obst culos e dos algoritmos de aprendizado Outro grande benef cio de usar grades que a resolu o pode ser sintonizada at que seja poss vel detalhar ao m ximo o mapa por menores que sejam esses detalhes Na realidade a nica coisa que limita o n vel de detalhamento do mapa gerado a capacidade dos sensores e a sua taxa de erro Por essa raz o essa a abordagem mais usada quando se necessita de um mapa extremamente detalhado O algoritmo de mapeamento relativamente simples Ele usa apenas a t cnica de ray casting e dois contadores em cada c lula um para acertos hits e outro para erros misses Ao in cio do algoritmo os contadores est o zerados A t cnica de ray casting quem vai increment los A t cnica se utiliza de raios imagin rios que s o lan ados pelos sensores Quando um obst culo interceptado por essa reta tra ada pelo raio s o incrementados os contadores de misses de todas as c lulas que est o entre o rob e o obst culo por ele detectado No caso das c lulas que tiverem sido atingidas pelo raio os contadores de hits que s o incrementados Para o c lculo da ocupa o de cada c lula feito o c lculo de um limiar que define se a c lula receber o valor um ocupada ou o valor zero n o ocupada O limiar definido usando se o seguinte c lculo contador de hits
37. mo se encontra local depois da cat strofe ter ocorrido Quem prov o ambiente simulado o Unified System for Automation and Robot Simulation USARSIM O USARSim um simulador de ambientes baseado no motor do jogo Unreal Tournament UNREAL e pode conter tipos de objetos com caracter sticas variadas como a representa o de seres vivos objetos m veis como outros agentes por exemplo objetos es t ticos paredes escadas etc dentre outras coisas Dentro deste simulador poss vel interagir com os objetos atrav s dos sensores dos agentes ou seja fazer leituras de dist ncia leitura de caminho percorrido odometria etc Dentro da hierarquia da RoboCup existem as competi es simuladas e n o simuladas A Virtual Robots Competition se situa dentro da RoboCupRescue Simulation league que abriga outras competi es simuladas Um dos objetivos desta divis o promover a troca de algoritmos entre competi es de uma mesma categoria 15 2 2 Configura es de Software e Hardware Dentro da organiza o da competi o as equipes que participam da competi o t m di reito a dois conjuntos de tr s computadores chamados de cluster Como a competi o se d em v rios ambientes simulados Destes dois clusters providos pela organiza o um deve ser usado pelo time durante uma simula o enquanto o outro deve ser usado para que o time se prepare para a pr xima competi o para o segundo est o dispon veis senso
38. ntradas em http msdn microsoft com en us visualc default aspx Baixe de mirror optus net sourceforge u us usarsim o arquivo SimpleUI 2 1 zip Termi nado o download descompacte o arquivo e copie seu conte do na pasta do UT2004 Em System dentro do diret rio do UT2004 abra com um editor de texto o arquivo usar s bat Usando o comando rem comente a primeira linha que deve ficar assim e rem ucc server DM ARDA 250 game USARBot USARDeathMatch TimeLimit 0 GameStats False ini US ARSim ini log usar server log E descomente removendo o comando rem a segunda linha que deve ficar assim e ucc server DM USAR yellow 250 game US ARBot US ARDeathMatch TimeLimit 02 GameStats False ini US ARSim ini log usar server log Salve feche este arquivo Para testar a instala o d um duplo clique em System usar_s bat Se n o der nenhum erro ent o o server est funcionando Sem fechar a tela em que o server est rodando v em SimpleUI Release no diret rio do UT2004 e clique em SimpleUL exe Clique em Start Deve abrir uma tela com o UnrealTournament 2004 e em seguida uma tela explicando como navegar entre o simulador e o controlador Pronto daqui pra frente s usar o Visual C para inserir seu c digo no controlador e participar da Competi o 30 4 O Problema Como foi visto para se participar da Virtual Robots Competition necess rio utilizar se de muitas ferramentas como o simulador e uma ferramenta de intera
39. o trazidos com o problema de localiza o e mapeamento simult neo devem ser considerados entre eles est o Limita es dos sensores e ru dos nas medi es Erros de odometria e movimenta o Ac mulo de erros e Associa o de dados Ambientes e obst culos din micos Explora o do desconhecido Limita es dos sensores e ru dos nas medi es Os rob s em geral possuem uma gama de sensores que v o de raios infravermelhos at sen sores de udio sonares Dentre estes sensores alguns s o usados pelos algoritmos de SLAM Por m todos s o pass veis de erros e limita es podendo gerar leituras infi is realidade Esses erros podem ser causados tanto pela qualidade dos sensores quanto pelos ru dos do ambi ente Um exemplo comum est nas superf cies transl cidas onde n o funcionam corretamente os lasers 33 Erros de odometria e de movimenta o J que para explorar um ambiente um agente precisa naveg lo comum que alguns pro blemas de odometria equipamento destinado a medir a dist ncia percorrida e movimenta o surjam Entre os fatores que geram erros na movimenta o podem ser elencados alguns comuns como superf cies escorregadias terrenos desiguais buracos morros etc solavancos decorren tes de obst culos entre outros fatores Quando alguns destes problemas ocorrem a leitura real da dist ncia percorrida e a posi o em que o agente se encontra podem ser equivocadas
40. oduz um problema de busca e reconhecimento de pa dr es Dentro desta tem tica criada uma equipe rob tica que deve procurar e pr diagnosticar feridos em um mapa que simula um local p s cast strofe Esta competi o usa o Urban Search And Rescue Simulation USARSim USARSIM um simulador de alta fidelidade que usa o engine do jogo UnrealTournament comprado separadamente Dentro desse simulador s o gerados os mapas as v timas os obst culos os rob s al m de toda a intera o entre esses ob jetos Neste ambiente os sensores dos rob s tamb m s o simulados de forma semelhante aos reais Assim cabe aos usu rios criar a intelig ncia desta equipe de tal forma que encontrem da maneira mais r pida e eficaz os feridos para que possam aplicar ent o os algoritmos de reconhecimento de padr o Todas as regras RULES 2008 incluindo sensores permitidos podem ser encontradas no site da competi o Para fazer a inser o dos rob s no simulador existem ferramentas chamadas de controla dores Por m estas ferramentas n o servem apenas para inserir os rob s no simulador Como 10 o nome leva a pensar elas servem para fazer o controle de toda a informa o gerada e ou lida pela equipe de rob s ou seja servem para fazer toda intera o dos usu rios com os sensores dos rob s No manual de instala o do citado o Mobility Open Architecture Simulation and Tools MOAST MOAST que um dos controladores suportad
41. os pelo simulador O manual do USARSim cita ainda dois outros controladores por m a utiliza o destes controladores n o intuitiva al m do fato de ser necess rio ter profundo conhecimento sobre como fazer a entrada dos dados e a leitura de informa es devolvidas por eles tornando os n o muito did ticos Considerando todos os fatores que dificultam a utiliza o dos controladores para a pes quisadores do desenvolveram um controlador em C que deveria al m de servir para a com peti o suprir a necessidade de uma ferramenta eficiente para ensino de rob tica e intelig ncia artificial Para que esta ferramenta fosse eficiente ela deveria ser t o intuitiva que n o prenderia o aluno no funcionamento dela em si mas sim no seu objetivo ao utiliz la O controlador criado pelo ITA j pode ser usado na competi o por m ainda n o est completo para ser uti lizado como ferramenta did tica Portanto em parceria com eles e com outras institui es pretendemos finalizar este processo criativo Coube aos alunos da a tarefa de fazer a parte de localiza o e mapeamento simult neos SLAM Simultaneous Localization And Mapping O objetivo do algoritmo de encontrar um mapa do local por onde os rob s est o se movimentando sem perder as informa es da localiza o de cada rob envolvido no processo de constru o Como existem pouco tutoriais e manuais de como participar na categoria faz parte da solu o d
42. os problemas criar um tutorial em portugu s que possa vir ajudar no primeiro contato com as ferramentas e problemas da Virtual Robots Competition 11 1 1 Justificativa Para participar da categoria Virtual Robots Competition h uma grande dificuldade em saber o que precisa ser instalado o que precisa ser aprendido e como faz lo na ordem correta A escassez de tutoriais principalmente em portugu s motivou a cria o de algo deste g nero Existem in meros controladores para a Virtual Robots Competitions da RoboCup por m nenhum deles foi considerado satisfat rio por n o terem em suas interfaces uma forma simples para entrada e sa da de dados tornando o uso complicado e nada intuitivo A id ia inicial dessa parceria entre universidades criar um controlador que seja t o simples de ser usado que venha a ser uma ferramenta para o aprendizado de conceitos e t cnicas de Acreditamos que ao criar um controlador simples em termos de uso e completo em termos de entrada e sa da de dados n o apenas ir ajudar a aumentar o interesse das pessoas na rea de Intelig ncia Artificial como tamb m ir aumentar a participa o de brasileiros na Virtual Robots Competitions O ideal deste trabalho ajudar a longo prazo a desenvolver a rea de Intelig ncia Artificial criando e ou aumentando o interesse entre os estudantes brasileiros tanto na rea quanto em competi es que busquem o mesmo objetivo 12 1 2 Objeti
43. r prio O professor Alexandre da Silva Sim es da Universidade do Estado de S o Paulo e a pro fessora Esther Colombini do Instituto Tecnol gico da Aeron utica fizeram uma primeira vers o do controlador Brasil Virtual Robots o brasilvr Para uma nova vers o deste controlador foram chamadas pessoas de outras institui es foi criada uma nova arquitetura e foram delegadas as obriga es de cada membro na nova equipe dentre as institui es agregadas ao novo time est UFSC O objetivo da nova vers o do controlador ser multi plataforma escal vel e intuitivo o bastante para ser usado tamb m como ferramenta did tica de Intelig ncia Artificial O trabalho foi dividido entre as universidades considerando se o n mero de pessoas envol 31 vidas em cada institui o o conhecimento da rea e a motiva o de cada integrante Coube a UFSC na forma de trabalho de conclus o de curso e a alguns integrantes da UNESP a parte de localiza o e mapeamento simult neo SLAM Para que o algoritmo de SLAM fosse criado foi necess rio estudar como s o usadas as informa es dos agentes e como organizada a Virtual Robots Competition al m de estudar o problema do SLAM suas formas de abordagem as formas de trabalhar para chegar ao melhor caso claro considerando uma precis o de mapa que seja capaz de passar pela arbitragem do evento 4 1 O problema do SLAM O problema de localiza o e mapeamento simult neo consiste em f
44. r tica os detectores e sensores Outro desafio conseguir balancear o n mero de landmarks para que se alcance um mapa desejado 39 5 Algoritmos e Implementa es Experimentos e Resultados Neste cap tulo ser mostrado como foi feito o algoritmo de SLAM considerando as esco lhas e abordagens Para melhor entendimento sugere se que previamente seja feita a leitura do cap tulo que trata do problema do SLAM 5 1 A abordagem escolhida Para escolher qual abordagem seria usada no problema do SLAM dentro da Virtual Ro bots foi necess rio entender como s o tratadas as informa es por cada uma delas estudando inclusive aquelas que s o h bridas Al m das caracter sticas das abordagens outro fato impor tante que necessitou aprecia o foi a forma como s o disponibilizados os dados e como eles podem ser processados considerando se todas as regras e restri es impostas pela organiza o do evento Como no caso da Virtual Robots Competition s se sabido previamente o local do mapa em que ser o colocados os agentes e suas orienta es este fato foi quem peneirou as abordagens deixando como melhores op es aquelas baseadas em landmarks ou seja aquelas que usam obst culos para fazer marca es no mapa ajustando o gradativamente com embasa mento numa distribui o Gaussiana Nas abordagens tradicionais que se baseiam no estudo de Kalman os mapas n o podem ser din micos portanto obst culos devem ser im veis J
45. refere Essas opera es ter o in cio trinta minutos antes da execu o efetiva Cada time ir se preparar no cluster que n o est sendo utilizado A execu o come a no tempo programado Independente da equipe n o estar pronta o tempo come a a correr Os rob s usam baterias que operam de 20 a 25 minu tos No tempo prescrito os rob s devem ser inicializados dentro do simulador Dentro do mapa os rob s devem aguardar por um comando de start que deve ser emitido antes que eles co mecem a explorar a rea Quem monitora a condi o da bateria o pr prio rob Informa es n o relatadas e colocadas no arquivo de log antes da bateria expirar n o s o contabilizadas 18 no total de pontos Todos os rob s devem ser inseridos no mapa ao mesmo tempo embora os times possam decidir ativ los no momento que acharem mais conveniente 2 7 Depois da execu o Para fins de pontua o cada equipe deve prover os seguintes elementos e Obrigat rio Um arquivo de texto simples chamado de arquivo de v timas contendo as v tmas encontradas durante a explora o Este arquivo deve conter a localiza o x y z de cada uma das v timas em um referencial coerente com o mapa e as localiza es de in cio dadas O formato do arquivo de v timas dividido em linhas Cada linha cont m exatamente nesta ordem o identificador da v tima atribu do pela equipe a posi o em metros e a especifica o de como a v tima
46. res de relevo GroundTruth para que as equipes possam preparar melhor suas estrat gias Os c digos ge rados pelas equipes devem ser rodados em m quinas pr prias sendo que fornecido um cabo para que essas m quinas sejam conectadas ao cluster A organiza o do evento monta um ser vidor sem fio e as comunica es entre o membro da equipe que opera a m quina onde est o c digo e agente inserido no ambiente simulado devem usar esse servi o wireless Na figura 2 1 est representado esse esquema de comunica o Para acessar o v deo acessar visualmente o USARSim a esta o base operadora dever usar o WCS Dessa forma os v deos ser o obtidos apenas quando o rob mantiver contato com o r dio 2 3 Esquema da Competi o Para que haja uma filtragem de quem participar da competi o s o aplicados testes de qualifica o ou testes elementares e testes de cen rio Em outras palavras as equipes ter o de exibir compet ncia e habilidades b sicas como mapeamento e mobilidade dentro do USAR Sim Existem tr s n veis de dificuldade na competi o mapas f ceis tamb m chamados de zonas amarelas mapas intermedi rios zonas laranja e mapas vermelhos zonas dif ceis As equipes devem mostrar que possuem capacidade de para operar nas zonas f ceis e intermedi rias do ambiente de teste Essas habilidades ser o necess rias para ter sucesso nos cen rios da competi o As reas de maior dificuldade do ambiente de te
47. rrer numa penalidade de cinco pon tos Se um rob toca uma v tima a equipe penalizada com cinco pontos por m se o mesmo rob tocar a mesma v tima v rias vezes n o penalizado mais de uma vez Ou seja para sofrer mais de uma penalidade neste caso o rob teria que acertar v timas di ferentes Choques com as v timas s o detectados automaticamente pelo servidor e suas informa es s o guardadas no arquivo de log Bater nas paredes ou outras estruturas n o acarretam pena no entanto algumas estruturas podem ser inst veis e bater poderia causar um colapso Operadores Por quest es de pontua o um membro da equipe considerado um operador logo que e Inicia um rob entra com os dados de ponto de partida ou exer a qualquer opera o que seja necess ria para o sucesso do in cio da miss o dos agentes e Controla um rob de forma ativa e P ra um rob antes do t rmino da execu o Para por exemplo prevenir um choque do rob com uma v tima e Estiver envolvido de qualquer forma com o processo de reconhecimento de v tima De acordo com o descrito acima cada equipe deve ter pelo menos um operador para confi gurar os rob s 2 9 Pol tica de Open Source A equipe que for vencedora e as equipes que apresentarem implementa es de c digo con sideradas inovadoras devem disponibilizar para os organizadores uma c pia completa e funcio 22 nal dos softwares criados Os softwares serao compartilh
48. stala o de ferramentas quanto de algumas regras da competi o No cap tulo 4 traduzido o problema que se tenta resolver com este estudo al m das explica es de relev ncia para o entedimento das solu es escolhidas No cap tulo 5 mostrado e explicado o algoritmo de SLAM que foi implementado ressal tando a contribui o dos trabalhos estudados para que a implementa o final fosse alcan ada O trabalho termina com as conclus es ressaltando como foi se desenvolvendo o projeto 14 2 Regras e funcionamento da Virtual Robots Competitions Nesta se o ser explicado o funcionamento da Virtual Robots Competition passando por pontos relevantes desde testes nos quais as equipes devem passar at explica es sobre pontu a o 2 1 Escopo e Defini o A Virtual Robots Competition uma das competi es que a RoboCup ROBOCUP 1998 promove A RoboCup uma junta internacional que objetiva o desenvolvimento da Rob tica Inteligente e da Intelig ncia Artificial Virtual Robots Competition basicamente um jogo onde se devem inserir rob s aqui chamados de agentes dentro de um ambiente simulado Os mapas do ambiente caracterizam um local p s cat strofe como um pr dio depois de um in c ndio ou uma casa depois de um terremoto por exemplo A fun o dos agentes inseridos nesse simulador encontrar poss veis feridos criando um mapa que possua a posi o destes feridos al m de representar a forma co
49. ste podem ser usadas para testar solu es avan adas e inovadoras al m de mostrarem o poss vel rumo que a competi o tomar numa pr xima edi o 2 4 Testes Elementares Os testes elementares s o dividos em mobilidade e mapeamento cada um deles ser expli cado melhor a seguir 16 Figura 2 1 Servidor de Comunica o Wireless VIRTUAL 2 4 1 Mobilidade O teste de mobilidade consiste em iniciar um ou mais agentes no simulador em um ponto do mapa definido pela organiza o e a equipe deve fazer com que pelo menos um dos rob s chegue a um ponto do mapa definido pelos organizadores do evento Por m o tempo para que esse alvo seja atingido limitado portanto n o basta chegar ao alvo necess rio faz lo antes de expirar o tempo A princ pio o teste se d na zona amarela mapa f cil mas metas adicionais podem ser aplicadas em zonas laranja ou vermelha Durante esse teste as equipes podem usar sensores que capturem o relevo e o mapa comprimido isso permite que as equipes tomem outras formas de navega o do mapa 17 2 4 2 Mapeamento Localiza o de V tima Para o teste de mapeamento os rob s precisam criar um mapa de grande percentagem do mundo O mapa deve conter anota es de rea explorada localiza o das v timas e todo o caminho tra ado pelos rob s A organiza o usada no teste similar quela que ser usada durante a competi o real incorporando perfeita comunica
50. to foi realmente pensado em como seriam as melhores formas de se locomover nas melhores rotas e para isso tanto grafos quanto diagramas de Voronoi s o excelentes Neste caso de SLAM a nica diferen a entre os grafos e os diagrams de Voronoi a forma como as liga es s o tratadas Nos grafos as liga es s o constru das apenas para caminhos percorridos realmente j nos Diagramas de Voronoi elas s o estimadas e as suas posi es s o afixadas considerando as posi es dos obst culos Portanto grafos v o mostrar o caminho percorrido que ir garantir a sua consist ncia Por outro lado Diagramas de Voronoi s o capazes de generalizar para al m dos caminhos percorridos Na verdade com isso pode se inferir o percurso mais seguro com base em estimativas do obst culo Em suma usar a abordagem topol gica excelente para encontrar caminhos seguros por m essa abordagem n o possibilita a captura de informa es adicionais do ambiente e os detalhes da geometria do local s o poucos Mapas h bridos d Nessa abordagem podem surgir in meras combina es o importante aqui tentar agregar das outras abordagens as vantagens e minimizar as desvantagens como por exemplo mesclar uma mapa de grade com uma abordagem topol gica fazendo que se possam coletar informa es precisas do ambiente medida que os agentes fa am um caminho mais seguro e melhor Desta abordagem surgiram duas abordagens muito usadas o Atlas e o FastSLA
51. tp sourceforge net project showfiles php groupi d 145394 gt BECERRA V M DMATRIX A C Matrix Class 2008 ELFES A Sonar based real world mapping and navigation 1987 MOAST Dispon vel em lt http sourceforge net projects moast gt MONTEMERLO S THRUN D K e B W M FastSlam A Factored Solution to the Simultaneous Localization and Mapping Problem 2002 MORAVEC H Sensor fusion in certainty grids for mobile robots 1988 NIETO JOSE GUIVANT E N e S T J Real Time Data Association for FastSLAM 2003 PFINGSTHORN B S M ManifoldSLAM a Multi Agent Simultaneous Localization and Mapping System for the RoboCup Rescue Virtual Robots Competition 2006 Dispon vel em lt http www springerlink com content c554763j202202um gt ROBOCUP 1998 Disponivel em lt http www robocup org gt ROB6OS USARSim Dispon vel em lt http sourceforge net project showfiles php groupi d 145394 gt RULES of the Virtual Robots Competition 2008 Disponivel em lt http www robocuprescue org wiki images Rules2007V5 pdf gt UNREAL Tournament Disponivel em lt http www unrealtournament com gt USARSIM Dispon vel em lt http sourceforge net projects usarsim gt VIRTUAL Robots Competition 2006 Dispon vel em lt http www robocuprescue org rescuerobots html gt VIRTUAL Robots Competitions Rules Figura SW HW configuration Disponivel em lt http www robocuprescue org wiki images Rules2007V5 pdf gt
52. vos 1 2 1 Objetivos Gerais O objetivo deste trabalho auxiliar a cria o de um controlador cuja implementa o seja inovadora e cumpra as regras definidas na RoboCup para a Virtual Robots Competition Este controlador ser usado como ferramenta did tica para estudo de t cnicas de Intelig ncia Artifi cial para isso deve ser bastante intuitivo e f cil de usar tamb m objetivo deste trabalho construir um passo a passo simples o bastante para que qualquer pessoa possa ingressar na Virtual Robots Competition sem encontrar grandes dificul dades ao menos no que diz respeito instala o e utiliza o de ferramentas 1 2 2 Objetivos espec ficos Para alcan ar os objetivos gerais definidos para o trabalho os seguintes objetivos espec fi cos foram listados Fazer um levantamento de informa es para criar o tutorial de forma completa abran gendo todo o processo preparat rio para a participa o na VR Competition Fazer com que o controlador seja adaptado s regras da Virtual Robots Competition Estudar sobre SLAM Adaptar o controlador tornando o Multiplataforma Extensivel Escalavel F cil para inser o e testes de novos algoritmos 1 3 Metodologia O trabalho foi realizado e est organizado do seguinte modo No cap tulo 2 explicada a competi o para o qual est tentando se criar um controlador 13 No cap tulo 3 iniciado o tutorial passando por pontos relevantes tanto da in
53. windows Para que a instala o ocorra sem nenhum problema abaixo s o listados alguns requisitos desej veis de hardware E importante ressaltar que s o requisitos recomend veis isto s o apenas requisitos em que se garante a instala o de forma aceit vel j que n o foram testadas instala es para configura es inferiores Requisitos de hardware e Pentium IH ou AMD Athlon 1 0 GHz e Placa de v deo 32 MB compat vel com DirectX 9 e 128 MB RAM e Espa o no HD 6 Giga O primeiro passo fazer a instala o do jogo UnrealTournament 2004 Pois o simulador que utilizado na competi o baseado na engine deste jogo necess rio que seja a vers o completa do UT2004 Ap s a instala o do UnrealTournament 2004 necess ria a instala o do patch 3369 na mesma pasta onde foi instalado o UT2004 Esse patch pode ser encontrado em v rios endere os indexados pelo buscador do Google Este pacote conserta alguns problemas que influenciam o engine do jogo e esse engine usado pelo USARSim 28 Problemas de engine consertados pelo patch 3369 e Caso seja passada uma fonte inv lida o m todo UCanvas WrappedPrint faz um retorno de fun o ao inv s de fazer uma assertiva como era antes e Mod agora suporta exporta o apropriada de headers 2 E e E feita convers o de para I no nome dos players e Copiar e colar no MidGamePanel uc foi modificado como era antes podia causar proble mas

veja o trabalho - Projetos

Contents

Download Pdf Manuals

Related Search

Related Contents