Unioeste - Universidade Estadual do Oeste do Paraná CENTRO DE CIÊNCIAS EXATAS E TECNOLÓGICAS Colegiado de Ciência da Computação Curso de Bacharelado em Ciência da Computação Módulo Gerador de Planos de Rotas para um Sistema de Navegação Autônoma Baseado na Arquitetura AuRA Tiago Zilio Jesuino CASCAVEL 2012 TIAGO ZILIO JESUINO MÓDULO GERADOR DE PLANOS DE ROTAS PARA UM SISTEMA DE NAVEGAÇÃO AUTÔNOMA BASEADO NA ARQUITETURA AURA Monografia apresentada como requisito parcial para obtenção do grau de Bacharel em Ciência da Computação, do Centro de Ciências Exatas e Tecnológicas da Universidade Estadual do Oeste do Paraná - Campus de Cascavel Orientador: Prof. Adriana Postal CASCAVEL 2012 TIAGO ZILIO JESUINO MÓDULO GERADOR DE PLANOS DE ROTAS PARA UM SISTEMA DE NAVEGAÇÃO AUTÔNOMA BASEADO NA ARQUITETURA AURA Monografia apresentada como requisito parcial para obtenção do Título de Bacharel em Ciência da Computação, pela Universidade Estadual do Oeste do Paraná, Campus de Cascavel, aprovada pela Comissão formada pelos professores: Prof. Adriana Postal (Orientadora) Colegiado de Ciência da Computação, UNIOESTE Prof. Josué Pereira de Castro Colegiado de Ciência da Computação, UNIOESTE Prof. Suzan Kelly Borges Piovesan Colegiado de Engenharia com Ênfase em Controle e Automação, FAG Colegiado de Sistema de Informação, UNIPAR Prof. Fernando Schutz Colegiado de Ciência da Computação, UTFPR-Medianeira Cascavel, 4 de dezembro de 2012 A águia voa sozinha, os corvos voam em bandos. O tolo necessita de companhia, o sábio necessita de solidão. Friedrich Rückert AGRADECIMENTOS Agradeço em primeiro lugar a Deus que iluminou meu caminho e que me deu forças para superar os momentos difíceis ao longo desta caminhada. Agradeço a todos os professores que de alguma forma contribuiram com o meu aprendizado desde a pré-escola até o último ano de faculdade, em especial minha professora orientadora pelo apoio, dedicação e principalmente pela paciência durante o desenvolvimento deste trabalho. Agradeço meus pais pela educação que deram a mim e a minha irmã, por estarem presentes e por me darem apoio em todos os momentos da vida, e por terem sido minha base todos esses anos. Por fim agradeço a todos meu amigos que ao longo desta caminhada, de uma maneira ou de outra, acabaram contribuindo para a realização deste trabalho. Lista de Figuras 3.1 R Área de Trabalho do Software MATLAB . . . . . . . . . . . . . . . . . . . . 13 3.2 Smart Brick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 R R Sensores e Servo Motor do kit Lego Mindstorms NXT 2.0 . . . . . . . . . 16 3.4 Robô Utilizado nos Testes Realizados - Visão Geral . . . . . . . . . . . . . . . 17 3.5 Robô Utilizado nos Testes Realizados - Visão Sensores . . . . . . . . . . . . . 18 3.6 Arquitetura AuRA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.1 Interface de execução do módulo de controle reativo . . . . . . . . . . . . . . . 23 4.2 Diagrama de fluxo de execução do controle . . . . . . . . . . . . . . . . . . . 25 4.3 Mapa do ambiente de testes utilizado . . . . . . . . . . . . . . . . . . . . . . . 28 4.4 Caminhos Traçados na Execução dos Testes com o Módulo Reativo . . . . . . 29 5.1 Interface de execução do módulo de controle deliberativo . . . . . . . . . . . . 31 5.2 Mapa utilizado nos testes do módulo deliberativo . . . . . . . . . . . . . . . . 32 5.3 Exemplo de mapa e de sua representação . . . . . . . . . . . . . . . . . . . . . 32 5.4 Fluxograma do algoritmo de geração da matriz de adjacências . . . . . . . . . 34 5.5 Verificação de conexão com as quatro vizinhanças . . . . . . . . . . . . . . . . 35 5.6 Grafo traçado a partir do mapa de entrada . . . . . . . . . . . . . . . . . . . . 36 5.7 Fluxograma do algoritmo de verificação de conectividade e de geração da rota . 37 5.8 Fluxograma do algoritmo que converte o caminho da rota gerada . . . . . . . . 38 5.9 Exemplo de caminho convertido . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.10 Resultado da conversão da rota calculada . . . . . . . . . . . . . . . . . . . . 39 5.11 Fluxograma do algoritmo que executa a rota gerada . . . . . . . . . . . . . . . 40 5.12 Mapa utilizado no teste no 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.13 Mapa utilizado no teste no 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 vi 5.14 Mapa utilizado no teste no 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.15 Mapa utilizado no teste no 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.16 Mapa utilizado no teste no 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.17 Mapa utilizado no teste no 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 vii Lista de Tabelas 3.1 R Camadas de comandos da biblioteca RWTH-Mindstorms NXT toolbox . . . . 14 3.2 Principais comandos utilizados . . . . . . . . . . . . . . . . . . . . . . . . . . 15 viii Lista de Abreviaturas e Siglas A* AuRA ARIA COHBRA DAMN MAC NASREM NHC PDDL RCS RWTH SFX SSS AStar (Algoritmo de Busca) Autonomous Robot Architeture Advanced Robot Interface for Applications Controle Híbrido de Robôs Autônomos Distributed Architecture for Mobile Navigation Media Access Control The NASA/NBS Standart Reference Model Nested Hierarchical Controller Planning Domain Definition Language Realtime Control System Rheinisch-Westfälische Technische Hochschule Aachen Sensor Fusion Effects Servo, Subsumption and Symbolic ix Sumário Lista de Figuras vi Lista de Tabelas viii Lista de Abreviaturas e Siglas ix Sumário x Resumo xii 1 2 3 Introdução 1 1.1 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Organização do texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Robótica Móvel 7 2.1 Navegação Autônoma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Arquitetura de robôs móveis . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 Arquiteturas Deliberativas . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.2 Arquiteturas Reativas . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.3 Arquiteturas Híbridas . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Materiais e Métodos 12 3.1 R O software Matlab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 A RWTH-Mindstorms NXT toolbox . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.1 Sintaxe dos Comandos Utilizados . . . . . . . . . . . . . . . . . . . . 15 3.3 R R O Lego Mindstorms NXT 2.0 . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4 O modelo de Robô Utilizado . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.5 Conceitos Arquiteturais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.5.1 18 A Arquitetura AuRA . . . . . . . . . . . . . . . . . . . . . . . . . . . x 3.6 4 5 Nested Hierarchical Controller (NHC) . . . . . . . . . . . . . . . . . 20 3.5.3 A Arquitetura Seleção de Ação . . . . . . . . . . . . . . . . . . . . . . 21 O algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 O Módulo Reativo 23 4.1 Interface de Execução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 Lógica de Controle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3 Testes Realizados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.3.1 Estrutura do Ambiente . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.3.2 Resultados Obtidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 O Módulo Deliberativo 30 5.1 Interface de Execução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2 Estrutura do ambiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.3 Lógica do controle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.3.1 Matriz de adjacências . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.3.2 Geração da rota . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.3.3 Execução da rota . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Testes Realizados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.4 6 3.5.2 Considerações Finais 44 Referências Bibliográficas 46 xi Resumo Por lidar com problemas relacionados à operação e locomoção de robôs móveis nos mais variados tipos de ambientes, a robótica móvel é uma área de pesquisa que está em expansão. Os sistemas autônomos são aplicações da área da robótica móvel que lidam com atividades que envolvem locomoção e exploração em ambientes tanto estáticos quanto dinâmicos. Para navegar de maneira totalmente autônoma por um ambiente e realizar algum tipo de tarefa, um robô móvel precisa de um sistema de navegação autônoma robusto e eficiente, este sistema deve coordenar as ações do robô dentro do ambiente com base em informações como o mapa do ambiente ou a leitura dos sensores disponíveis no robô. Um sistema de navegação autônoma geralmente é construído adotando um tipo de arquitetura. As arquiteturas de robôs móveis definem como serão organizados os possíveis módulos do sistema de navegação e de um modo geral estão mais relacionadas ao software do que ao hardware do sistema. No presente trabalho foram desenvolvidos dois módulos de navegação autônoma: um módulo reativo, que foi desenvolvido baseando-se na arquitetura Seleção de Ação, e um módulo deliberativo, que foi desenvolvido baseando-se na arquitetura Nested Hierarchical Controller (Controlador Hierárquico Aninhado). Ambos os módulos foram desenvolvidos para o controle de um robô R R móvel construído a partir do kit Lego Mindstorms NXT 2.0. O funcionamento destes módulos foi validado através de testes em um ambiente estruturado estático. Palavras-chave: Robótica Móvel, Módulo Reativo, Módulo Deliberativo. xii Capítulo 1 Introdução A robótica móvel caracteriza-se por estudar e desenvolver máquinas que possuam a capacidade de interagir com ambientes que, na maioria das vezes, não são controlados ou até mesmo conhecidos. Por possuir ênfase nos problemas relacionados à operação e locomoção em ambientes variados, a robótica móvel está cada vez mais presente em áreas como transporte, exploração, automação industrial e em sistemas autônomos. Atualmente muitas são as atividades que envolvem robôs, tanto na área acadêmica como, por exemplo, a competição internacional de futebol de robôs ROBOCUP [1], quanto na área militar onde o uso de robôs para desarmar bombas ou efetuar operações em ambientes hostis é cada vez maior [2], ou ainda na área de pesquisa e exploração como, por exemplo, a NASA que desde 1996 envia robôs ao espaço para auxiliar em suas pesquisas [3]. É cada vez maior o número de robôs que estão entre os humanos auxiliando-os ou substituindo-os nas mais diversas atividades. Entretanto, para desempenhar tarefas com resultados satisfatórios, não basta apenas estar inseridos no mesmo ambiente que os humanos, esses robôs precisam de um sistema de navegação autônomo capaz de coordenar suas decisões para que suas tarefas sejam realizadas com o máximo de desempenho sem comprometer sua eficiência. Os sistemas de navegação autônoma se caracterizam por serem independentes da intervenção humana, sendo capazes de executar a tarefa a qual lhe foi destinada sem a interferência de qualquer mecanismo externo, além de possuírem a capacidade de se adaptar de forma a contornar situações imprevistas [4]. Nestes sistemas, o grau de complexidade da navegação pode variar conforme o tipo de sensores usados no robô, o poder de processamento, os objetivos impostos e o tipo de ambiente em que o robô irá navegar [5]. Ao longo do tempo muitos pesquisadores propuseram arquiteturas voltadas a tarefas a serem executadas e as características do robô de modo a auxiliar no desenvolvimento de sistemas de navegação autônoma para aplicações. Dentre as arquiteturas existentes, a Autonomous Robot Architecture, mais conhecida como arquitetura AuRA, é uma arquitetura de abordagem híbrida que foi desenvolvida em meados de 1980 por Ronald C. Arkin para ser aplicada na navegação robótica [6]. Esta arquitetura se caracteriza por possuir um planejador hierárquico que, através das informações sobre o ambiente e o conhecimento sobre os comportamentos disponíveis, configura a sua parte reativa a fim de que o robô execute determinada tarefa ou função. A arquitetura AuRA é bastante modular e flexível, permitindo que seus componentes sejam trocados de acordo com a aplicação ou evolução da tecnologia usada na implementação dos seus módulos, além de permitir que o sistema possa adaptar-se ao ambiente [7]. Neste trabalho foi implementado um módulo responsável pela geração de planos de rotas, baseado nos componentes deliberativos da arquitetura AuRA. Este módulo é capaz de planejar rotas para a execução de tarefas que são passadas ao robô, baseando-se no mapa de um determinado ambiente. O robô executa suas tarefas e alcança seus objetivos de maneira autônoma. Para isso, o módulo gerador de planos de rotas proposto recebe o mapa do ambiente, o entende e com base em uma tarefa específica calcula qual será a melhor rota para alcançar o seu objetivo. Feito isso, este módulo passa quais são os planos e quais os comportamentos para o módulo reativo, o qual é responsável por executar a tarefa. Existem inúmeras aplicações onde é possível usar robôs móveis para realização de alguma tarefa, por exemplo, no transporte, na inspeção, limpeza entre tantas outras. Entretanto, a falta de um sistema de controle e navegação robusto, flexível e ao mesmo tempo confiável, que permita que os robôs operem nos mais variados ambientes, pouco estruturados e habitados por seres humanos, limita o uso de robôs nestas aplicações [8]. Para que a navegação em ambientes internos de um robô móvel seja realizada de maneira confiável, este precisa saber sua localização (posição e orientação) dentro do ambiente ao qual está inserido. Através de seus sensores o robô deve ser capaz de saber qual a sua posição e orientação dentro de um mapa global. A localização do robô é importante tanto para a navegação 2 quanto para a exploração, auxiliando o robô a adaptar-se ao mapa do ambiente e a seguir suas rotas e planos. Usar os dados sensoriais do robô para estimar a sua localização em um ambiente é um problema comum da robótica móvel, por isso a integração de um módulo localizador no sistema de controle robótico amplia a capacidade e torna mais confiável a navegação do robô autônomo [8]. Neste projeto foi abordado apenas a navegação em espaços de trabalhos estruturados, ou seja, o espaço de trabalho será previamente conhecido pelo robô, não havendo necessidade de mapeamento do espaço durante a execução de tarefas; e por se tratar de um mapa que representa um ambiente estático, este não sofre mudanças quanto à posição de seus obstáculos. O ambiente considerado é plano, sendo desnecessário considerar as características topográficas do terreno. 1.1 Objetivos • Geral: Implementar um módulo gerador de planos de rotas para a navegação autônoma de robôs, baseado na arquitetura híbrida AuRA [6]. • Específicos: 1. Implementar um módulo reativo, que será responsável pela percepção e iteração direta com o ambiente, e um módulo deliberativo que será responsável por planejar rotas com base no conhecimento prévio do ambiente, ambos baseados na arquitetura R AuRA. Estes módulos serão desenvolvidos utilizando o software MATLAB atraR vés da biblioteca RWTH Mindstorms NXT toolbox que permite a iteração entre o R R R Lego Mindstorms NXT 2.0 e o software MATLAB . 2. Realizar testes com os módulos implementados a fim de validar o funcionamento dos mesmos. 1.2 Trabalhos Relacionados Farlei José Heinen [8] desenvolveu uma arquitetura híbrida chamada de COHBRA a fim de permitir o controle de robôs móveis. A arquitetura desenvolvida utiliza uma abordagem de três camadas: um controle reativo (seção 2.2.2) presente na camada vital (camada de mais alto 3 nível), um sequenciador de planos presentes na camada funcional e um controle deliberativo (seção 2.2.1) presente na camada deliberativa, que se comunicam através de uma área de memória compartilhada. Esta arquitetura possui representação do ambiente na forma poligonal, matricial e topológica. O controle desenvolvido pode operar ambientes estáticos e dinâmicos. Os planos para alcançar um objetivo são traçados pela camada deliberativa utilizando o algoritmo de busca A* [9], enquanto a camada vital utiliza os comportamentos do controle reativo para conduzir o robô até o objetivo. Nesta arquitetura, a camada funcional tem função de integrar a camada deliberativa e a camada vital, além de procurar se adaptar ao ambiente. Esta arquitetura possui ainda um módulo localizador capaz de estimar a posição do robô durante a navegação. O funcionamento da arquitetura COHBRA foi comprovado através da implementação de um simulador de robôs móveis chamado SimRob3D que permite visualização do mapa em três dimensões e o uso de diversos modelos de sensores e atuadores. Valdir Grassi Junior [7] desenvolveu um controle de navegação robótico semi-autônomo baseado em uma arquitetura híbrida onde o usuário humano tem a possibilidade de alterar localmente a trajetória que é previamente planejada pelo controle para o robô. Uma vez que o controle, de maneira autônoma, define uma rota para o robô seguir, ele é capaz de evitar colisões com obstáculos tanto estáticos quanto dinâmicos e é capaz de evitar obstáculos mesmo que durante a execução da navegação o usuário altere a rota em execução. A arquitetura desenvolvida por Grassi Junior [7] permite que o robô seja operado em níveis diferentes de autonomia, possibilitando que um usuário compartilhe o controle do robô de forma segura com o sistema de navegação. A validação desse projeto foi realizada implementando o sistema de navegação desenvolvido em uma cadeira de rodas adaptada e equipada com sensores de distância, sensores de laser e com um sistema de visão composto por duas câmeras. Kleber Roberto da Silva Santos [10] apresentou em seu trabalho a implementação de um sistema de navegação autônoma para robôs móveis simulado que foi desenvolvido baseado na arquitetura AuRA. Para que o módulo deliberativo desenvolvido planeje quais ações devem ser tomadas e qual trajetória deve ser seguida, foi realizada uma modelagem do ambiente na qual foram descritas as relações entre os diversos componentes do ambiente, as ações possíveis de serem realizadas, pré-condições e os efeitos desencadeados por cada ação tomada. 4 Esta modelagem foi implementada em uma linguagem de planejamento denominada PDDL (Planning Domain Definition Language). O sistema implementado seleciona o conjunto de ações necessárias para que o robô alcance seu objetivo. Com as ações definidas, o módulo deliberativo define qual é a melhor forma de realizar determinada atividade configurando a execução da ação e passando esta tarefa para o módulo reativo. Quando todas as atividades são cumpridas, o robô alcança seu objetivo final. O trabalho de Santos [10] foi desenvolvido utilizando a linguagem de programação C++ e as bibliotecas do software ARIA (Advanced Robot Interface for Applications). Os testes e a validação do sistema foram realizados em um simulador chamado MobileSim [11] do mesmo fabricante das bibliotecas de software. Renato Reder Cazangi [12] desenvolveu um sistema de navegação autônoma evolutivo aplicado ao controle de um robô móvel a fim de permitir a execução de tarefas em ambientes desconhecidos. O sistema desenvolvido é um sistema reativo que não possui nenhum tipo de conhecimento inicial e que a partir da interação do robô com o ambiente aprende a lidar eficientemente com o mesmo. O sistema de Cazangi [12] desenvolve estratégias gerais de navegação controlando a velocidade de navegação e a direção do robô de maneira totalmente autônoma. A abordagem evolutiva presente neste sistema foi desenvolvida baseando-se em sistemas classificatórios com aprendizado. Após os testes realizados utilizando simuladores computacionais o sistema foi transferido para um robô Khepera II onde foram executados testes e a validação do controle. 1.3 Organização do texto Esta monografia está organizada da seguinte forma: no capítulo 2, são apresentados os temas robótica móvel e navegação autônoma. No capítulo 3 são apresentadas as ferramentas utilizadas, o modelo de robô construído e utilizado e também os conceitos arquiteturais que foram empregados no desenvolvimento deste projeto. No capítulo 4 é apresentado o módulo reativo implementado, a lógica de funcionamento deste módulo, a estrutura do ambiente utilizado para testar e validar o seu funcionamento e os resultados dos testes realizados com este módulo. No capítulo 5 é apresentado o módulo deliberativo que foi implementado, o ambiente utilizado, a forma de representação desse ambiente, a geração de rotas, a navegação no am5 biente e os testes realizados para validação deste módulo. No capítulo 6 são apresentadas as considerações finais deste trabalho, incluindo trabalhos futuros. 6 Capítulo 2 Robótica Móvel A robótica móvel compreende a área da robótica que estuda e desenvolve máquinas capazes de se locomover em ambientes geralmente não controlados, dinâmicos, pouco estruturados e desconhecidos [13]. Um robô móvel caracteriza-se por ser um dispositivo mecânico montado sobre uma base não fixa que atua sob o controle de um sistema computacional. Este sistema define o modo como o robô irá interagir com o ambiente, essa interação se caracteriza pelo tipo de arquitetura utilizada para a criação do sistema [10]. Os robôs móveis podem ser classificados de acordo com o tipo de ambiente para o qual eles foram projetados, podendo ser aquáticos, aéreos ou terrestres. Dentre outras características um robô móvel possui quatro aspectos principais referentes a sua construção: locomoção, controle e inteligência, percepção e comunicação. A locomoção define como o robô irá se deslocar no ambiente, a percepção define como o robô irá perceber o ambiente, o controle e inteligência definem como o robô irá transformar os conhecimentos prévios sobre o ambiente e as percepções obtidas através dos sensores em ações que serão executadas e a comunicação define como o robô irá se comunicar com outros dispositivos ou até mesmo com um humano [14]. 2.1 Navegação Autônoma A navegação autônoma permite que um robô móvel explore o seu ambiente e seja capaz de interagir com o mesmo, permitindo a realização de tarefas como procurar objetos, desviar de obstáculos, escapar de labirintos ou ainda mapear ambientes. A navegação autônoma necessita entre outras características que o robô móvel possua a capacidade de aprender estratégias de navegação, adaptar-se a novas situações, checar e determinar sua posição dentro do ambiente ao qual está inserido e construir conhecimento a partir de informações obtidas do ambiente [15]. Essas características permitem que um robô móvel execute determinadas tarefas sem que haja a necessidade de interferência externa durante a execução da tarefa [4]. Para executar uma determinada tarefa, um sistema de navegação autônomo deve aceitar as descrições em alto nível das tarefas que deve desenvolver. Essas descrições especificam o que deve ser feito pelo robô e não como o robô deve proceder para fazê-lo. Dessa forma ao ser inserido em um ambiente externo, supostamente desconhecido, o sistema autônomo deve ser capaz de definir uma sequência ou sequências de ações a serem tomadas, dotado de um conjunto limitado de sensores e de atuadores, tendo que atender simultaneamente um ou mais objetivos previamente especificados [16]. 2.2 Arquitetura de robôs móveis O desenvolvimento de um sistema para um robô autônomo envolve primeiramente o desenvolvimento de um sistema computacional que gerencie os componentes e os possíveis módulos deste sistema. O desenvolvimento de sistemas robóticos que planejam e controlam a execução de tarefas são geralmente construídos a partir de uma arquitetura computacional de controle. A arquitetura de um sistema define como são organizados os possíveis módulos do sistema e de que forma é organizada a tarefa de gerar ações baseadas na percepção do robô que é realizada através de seus sensores [8]. Uma arquitetura para robôs móveis está mais relacionada ao software do que ao hardware do sistema de controle [17]. Uma arquitetura faz com que todas as percepções disponíveis pelos sensores sejam fornecidas a um programa que irá enviar aos atuadores as ações que foram geradas com base nas percepções. As arquiteturas para robôs móveis podem ser classificadas com relação ao uso da deliberação e da reatividade dentro do seu sistema de controle. Com base nestes critérios as arquiteturas dividem-se em [7]: Arquiteturas deliberativas: o foco principal está em formular um plano que permita da melhor maneira possível atingir os objetivos determinados; Arquiteturas reativas: o foco principal está na execução de ações em tempo real sem um plano específico, podendo interagir com um ambiente dinâmico sujeito a mudanças inesperadas; 8 Arquiteturas híbridas: procuram mesclar as principais características e funcionalidades das arquiteturas deliberativas e reativas. 2.2.1 Arquiteturas Deliberativas Um controlador deliberativo consiste na aplicação de um mecanismo de planejamento de ações baseadas no conhecimento prévio do ambiente que o sistema possui sobre o problema a ser resolvido, como por exemplo, o mapa do ambiente ou rotas disponíveis ou informações sensoriais fornecidas pelo robô. Os controles deliberativos assumem a existência de um processo de alto nível de raciocínio e tomada de decisões, na maioria das vezes mais complexo de ser implementado do que em um controle reativo. Este processo permite que sejam planejadas ações de modo a tratar e executar um nível de controle mais sofisticado [18]. Um robô empregando o raciocínio deliberativo necessita do conhecimento completo do mundo e utiliza esse conhecimento para prever o resultado de suas ações, essa habilidade permite que o desempenho do robô seja otimizado; em ambientes dinâmicos é arriscado utilizar informações que remetem ao passado já que essas informações podem ter sido alteradas e se tornado inválidas [19]. O raciocínio deliberativo na maioria das vezes necessita de um modelo muito forte de hipóteses sobre o mundo e principalmente que o conhecimento base seja confiável [10]. Um controle deliberativo possui limitações quando confrontado com eventos imprevistos como por exemplo um obstáculo que se moveu obstruindo a passagem do robô. Além disso os controles deliberativos de um modo geral são incapazes de operar fora de um ambiente controlado e são frágeis por necessitarem de um modelo exato do ambiente para decidir exatamente o que fazer além de estar sujeitos a ruídos ou imprecisões dos sensores e do modelo de mundo [8]. Dentre o princípio puramente deliberativo as arquiteturas deliberativas mais conhecidas e utilizadas são a arquitetura Nested Hierarchical Controller (NHC) desenvolvida por Meystel [20] e a arquitetura NIST Realtime Control System (RCS) desenvolvida por Albus e Proctor [21] seguindo a mesma ideia da arquitetura NASREM [22]. No desenvolvimento da parte deliberativa deste trabalho utilizou-se alguns conceitos e características da arquitetura NHC, descrita na seção 3.5.2. 9 2.2.2 Arquiteturas Reativas Na robótica móvel as arquiteturas reativas se caracterizam por definirem ações a serem tomadas pelo robô a partir das informações fornecidas pelos sensores deste robô, estas ações evitam o uso de um modelo interno do mundo seguindo o lema de que “o mundo é a melhor representação dele mesmo” [23]. O desenvolvimento das arquiteturas reativas1 baseou-se principalmente no estudo do comportamento de insetos dentro de seus ambientes naturais, onde cada adversidade do ambiente, ou cada alteração percebida por um inseto pode resultar em uma reação imediata, que é realizada enquanto a alteração do ambiente pode ser percebida pelo inseto e procura levar o inseto para longe da fonte de um estímulo. As ações tomadas por um controlador podem ser classificadas em reflexos ou ações fixas. As ações do tipo reflexo se caracterizam por serem respostas rápidas e automáticas que são ativadas involuntariamente por um estímulo do ambiente, esta ação dura apenas enquanto dura o estímulo. As ações fixas se caracterizam por serem ações com tempo fixo que podem ter duração maior ou menor do que a duração de um estímulo. Seguindo estas definições um controle reativo pode fornecer dois tipos de comandos ao robô. O primeiro gera ações reflexivas, ou seja o controle monitora o conjunto de sensores presentes no robô e diante de alguma mudança no estado de um ou mais sensores executa uma determinada ação, essa ação é executada enquanto o estado dos sensores ou de um determinado sensor permanecer alterado pelo ambiente. O segundo gera ações fixas, ou seja, o controle reativo monitora os sensores do robô e diante de alguma mudança no estado de um ou mais sensores dispara o comando para que seja executada uma determinada ação. Essa ação tem duração fixa, e não é alterada por conta de uma eventual mudança de estado de algum dos sensores robô,. Como as ações do robô surgem a partir da leitura sensorial na forma de respostas prédefinidas no controlador do robô, em geral a velocidade de processamento e de resposta de um sistema reativo é alta devido a simplicidade no tratamento das informações sensórias e devido a forma direta como a percepção ou estímulo está associada a uma resposta ou uma ação [7]. 1 A nomenclatura e as definições usadas nesta seção seguem as apresentadas por Arkin [19]. 10 Dentre vários exemplos de arquiteturas reativas existentes pode-se mencionar como as mais conhecidas a Arquitetura de Subsunção desenvolvida por Brooks [24], a arquitetura Esquema Motor desenvolvida por Arkin [19] e a arquitetura Seleção de Ação desenvolvida por Maes [25] que serviu como base para o desenvolvimento do módulo reativo, e será apresentada na seção 3.5.3. 2.2.3 Arquiteturas Híbridas Um controlador híbrido tem o objetivo de combinar as características dos sistemas deliberativos e reativos. Os sistemas híbridos geralmente se dividem em pelo menos dois módulos: um módulo é responsável pela parte deliberativa da arquitetura, ou seja, por executar o planejamento de ações a longo prazo, e o outro módulo é responsável pela parte reativa da arquitetura, responsável por lidar com situações de reação imediata [8]. Quando as ações a serem tomadas pelo robô móvel já foram planejadas pelo módulo deliberativo presente na arquitetura, a execução dessas ações é realizada utilizando o módulo reativo que responde rapidamente à mudanças do ambiente. Dessa maneira as arquiteturas híbridas buscam solucionar problemas complexos atingindo os objetivos necessários de maneira eficiente combinando deliberação e reação [10]. A maior dificuldade presente nos sistemas híbridos está em como integrar os módulos deliberativos e reativos de forma que os dois possam se comunicar sem qualquer tipo de conflito, para isso geralmente é necessário um terceiro módulo que gerencia a comunicação entre o módulo deliberativo e o módulo reativo [8]. Como exemplo de arquiteturas consideradas híbridas pode-se citar a arquitetura AuRA, a arquitetura SFX [26], a arquitetura DAMN, a arquitetura SSS [27] entre outras [10]. Por ser a base de desenvolvimento deste trabalho, a arquitetura AuRA será descrita na subseção 3.5.1. 11 Capítulo 3 Materiais e Métodos 3.1 O software Matlab R R O MATLAB é um ambiente interativo de linguagem de alto nível interpretada que per- mite a execução de tarefas intensivas em relação ao contexto computacional, sendo mais rápido do que as linguagens de programação tradicionais como o C, C++ e FORTRAN [28]. Além dessa característica, existem inúmeras bibliotecas que aumentam o seu poder de programação e interação. Sua linguagem é apropriada ao desenvolvimento de aplicativos de natureza técnica. Este software é adequado àqueles que desejam implementar e testar soluções com facilidade e precisão sem perder tempo com detalhes específicos de linguagem de programação. R O software MATLAB possui uma área de trabalho organizada basicamente em uma janela principal ou janela de comandos, e quatro subjanelas que servem de auxílio para o programador. As principais características dessa janela podem ser vistas na figura 3.1. R Figura 3.1: Área de Trabalho do Software MATLAB De um modo geral o núcleo de programação do MATLAB é formado por matrizes e vetores. Além da orientação matricial, este software fornece recursos de programação similares ao recursos fornecidos por outras linguagens de programação e possui uma ferramenta para desenvolvimento de interface gráfica com o usuário conhecida como GUI-Graphical User Interface [29]. A partir desta ferramenta foi possível desenvolver as interfaces de execução dos módulos reativo e deliberativo desenvolvidos neste trabalho. Dessa forma, as estruturas de dados, os reR cursos de programação e a ferramenta GUI combinados tornam o MATLAB uma ferramenta poderosa para solução de problemas em áreas diferentes. 3.2 A RWTH-Mindstorms NXT toolbox R A biblioteca RWTH Mindstorms NXT toolbox foi desenvolvida pela universidade RWTH Aachen (Rheinisch-Westfälische Technische Hochschule Aachen) [30] para fins educacionais. As funções dessa toolbox podem ser classificadas em uma estrutura de múltiplas camadas mostrada na tabela 3.1, adaptada da página da biblioteca [31]. 13 R Tabela 3.1: Camadas de comandos da biblioteca RWTH-Mindstorms NXT toolbox Na primeira camada estão as funções de ajuda e de conversão de parâmetros, palavras e bytes, todos determinados pela documentação dos comandos diretos fornecida pela própria R Lego . Na segunda camada estão os comandos diretos ao NXT que podem ser identifica- dos pelo prefixo NXT_*, além das funções para empacotamento de comandos BluetoothTM . Na terceira camada estão presentes as funções de alto nível para controlar os motores do NXT, TM seus sensores e a conexão Bluetooth . Na quarta e última camada se encontram funções de alto nível para regulação dos motores, ajustes de precisão e outras utilidades. Essas e outras informações estão disponíveis na documentação da biblioteca [31]. 14 3.2.1 Sintaxe dos Comandos Utilizados A tabela 3.2 apresenta a sintaxe dos principais comandos que foram utilizados na implementação dos módulos de controle reativo e deliberativo juntamente com uma descrição dos mesmos. Tabela 3.2: Principais comandos utilizados 3.3 O Lego Mindstorms NXT 2.0 R R R R Lançado em 2006 o kit Lego Mindstorms NXT possui um módulo controlador de pro- gramação intuitiva, também conhecido como Smart Brick, que é o ’cérebro’ do robô, tendo quatro entradas que manipulam os seus sensores e três saídas que manipulam os seus três servomotores1 . Sua arquitetura é simples, possui um microprocessador ARM7 de 32 bits, memória TM Flash de 256 Kbytes e memória RAM de 64 Kbytes, comunicação Bluetooth comunicação USB TM 2.0, porta de 2.0, uma tela LCD e um alto falante [32]. O Smart Brick está ilustrado na figura 3.2. Esse kit também conta com 619 peças da linha Lego Techinic [33] além de possuir sensor de toque, sensor de luz e de cor, sensor ultrassônico e três servo motores. No desenvolvimento deste projeto foram utilizados dois sensores de toque, um sensor ultrassônico e três servo motores. O sensor de toque, visto na figura 3.3(a), é um sensor de dois estados que detecta quando está livre ou quando está sendo pressionado por algum objeto. Este sensor pode ser utilizado para indicar choques com um obstáculo [32]. 1 As figuras apresentadas us/whatisnxt/default.aspx. nesta seção foram 15 adaptadas da página mindstorms.lego.com/en- Figura 3.2: Smart Brick (a) Sensor de Toque (b) Sensor Ultrassônico (c) Servo Motor R R Figura 3.3: Sensores e Servo Motor do kit Lego Mindstorms NXT 2.0 O sensor ultrassônico, mostrado na figura 3.3(b), permite a detecção de objetos, o cálculo da distância de um objeto ou a detecção de movimentos. O sensor ultrassônico é capaz de calcular distâncias entre 0 e 255 centímetros com uma precisão de aproximadamente 3 centímetros. 16 Este sensor calcula a distância para um objeto através do tempo que uma onda de som leva para atingir o objeto e retornar ao sensor [32]. R R O três servo-motores presentes no Kit Lego Mindstorms NXT 2.0 possibilitam a cons- trução de modelos de robôs móveis. Cada servo-motor, mostrado na figura 3.3(c), possui um sensor de rotação permitindo a execução de movimentos precisos, além de poder executar ações com diferentes velocidades ou ainda ações sincronizadas entre os motores [32]. 3.4 O modelo de Robô Utilizado Nesta seção é apresentado o modelo de robô que foi construído para a execução dos testes e para o desenvolvimento do projeto. O modelo, visto na figura 3.4, foi baseado nos modelos Rover Explorer Robot [34] e Shooterbot [35], e para sua construção foram utilizados dois sensores de toque, um sensor ultrassônico, três servo motores além de outras peças para montar a estrutura e para dar fixação. Este modelo possui comprimento de aproximadamente 18 cm, altura de aproximadamente 18 cm e largura de aproximadamente 14 cm. (a) Robô Visto de Frente (b) Robô Visto de Lado Figura 3.4: Robô Utilizado nos Testes Realizados - Visão Geral No modelo construído o sensor de toque da direita foi conectado à entrada 2, o sensor de toque da esquerda foi conectado à entrada 1 e o sensor ultrassônico foi conectado à entrada 4. O motor de tração da direita do robô foi conectado à saída C, o motor de tração da esquerda do robô foi conectado à saída B e o motor responsável pela rotação do sensor ultrassônico, para permitir que o robô possa verificar a presença ou não de obstáculos a sua direita e a sua esquerda sem que seja necessário que o robô gire, foi conectado à saída A. Além disso o robô possui dois pára-choques móveis, um na dianteira (figura 3.5(b)) e um na traseira (figura 3.5(a)) 17 que acionam os sensores de toque do robô indicando a presença de obstáculos. (a) Sensor de Toque e Pára-choque Traseiro (b) Sensor de Toque e Pára-choque Dianteiro Figura 3.5: Robô Utilizado nos Testes Realizados - Visão Sensores Um guia contendo todos os passos e as peças necessárias para a montagem deste modelo está disponível na página http://www.inf.unioeste.br/gpa/Projetos/Material/GuiaRoboTiago.PDF . 3.5 Conceitos Arquiteturais Na seção 2.2 foram definidos os conceitos de arquiteturas de robôs móveis assim como os três tipos de arquiteturas existentes na área da robótica. Nesta seção são apresentados os conceitos arquiteturais empregados no desenvolvimento dos módulos reativo, apresentado no capítulo 4, e deliberativo, apresentado no capítulo 5. 3.5.1 A Arquitetura AuRA Proposta por Arkin no ano de 1987, a arquitetura AuRA - Autonomous Robot Architeture foi uma das primeiras arquiteturas híbridas, isto é, arquiteturas que mesclam características deliberativas e características reativas, a ser desenvolvida. Essa arquitetura possui características e funcionalidades dos sistemas de controle das arquiteturas deliberativas, cujo foco principal está em formular um plano que defina a melhor maneira possível de atingir os objetivos determinados, e reativas, onde há execução de ações em tempo real sem um plano específico podendo interagir com um ambiente dinâmico sujeito a mudanças inesperadas. A arquitetura AuRA, mostrada na figura 3.6 (adaptada de Arkin e Balch [17]), funciona segundo a estrutura de um planejador hierárquico que utiliza as informações sobre o ambiente 18 e os conhecimentos sobre os comportamentos que foram definidos no sistema para configurar a parte reativa que fica encarregada de executar os planos ou tarefas que forem passados ao robô. Figura 3.6: Arquitetura AuRA No nível mais alto dos componentes deliberativos está o planejador de missão, no nível intermediário está o módulo de raciocínio espacial e no nível mais baixo está o sequenciador de planos. Abaixo, a descrição destes elementos, segundo Santos [10]: Planejador de Missão: nível mais alto da hierarquia, tem a função de estabelecer objetivos de alto nível para serem alcançados pelo robô, além de estabelecer as restrições dentro das quais o robô irá operar enquanto tenta alcançar seu objetivo. Raciocinador Espacial: nível intermediário da hierarquia, possui uma memória de longa duração que armazena informações que são obtidas a partir do mapa do ambiente. Estas informações são utilizadas para construir uma sequência de trechos de navegação, que serão executados para que a missão destinada ao robô seja completada. Sequenciador de Planos: nível mais baixo da hierarquia, aponta um conjunto de comportamentos motores que serão enviados para execução a fim de cumprir cada trecho de navegação gerado pelo módulo de raciocínio espacial. O sequenciador de planos se encarrega de enviar os comportamentos para o controlador de esquemas finalizando a participação da execução deliberativa da arquitetura e iniciando a 19 execução reativa ativando assim o controlador de esquemas. O controlador de esquemas é o responsável pelo controle e monitoramento dos comportamentos reativos do robô durante a execução da sua tarefa, possuindo um comportamento pré-definido para cada estímulo captado por um dos sensores do robô. Uma vez que os comandos são enviados ao controlador de esquemas ativando a parte reativa da arquitetura, a parte deliberativa fica monitorando o desenvolvimento da tarefa que foi destinada ao robô e só volta a ser completamente ativada caso alguma falha seja detectada durante a execução da mesma. Normalmente uma falha é caracterizada por ausência de evolução durante a execução da tarefa. Neste caso as camadas do planejador hierárquico são reativadas uma de cada vez conforme necessário, começando pelo sequenciador de planos até chegar ao planejador de missão [6]. Embora a arquitetura AuRA possua quatro módulos bem definidos e a ligação entre eles seja bem definidas, no desenvolvimento deste trabalho consideramos apenas os conceitos empregados nos módulos deliberativo e reativo desta arquitetura, dessa forma os módulos reativo e deliberativo desenvolvidos foram baseados nas arquiteturas Seleção de Ação, apresentada na seção 3.5.3, e Nested Hierarchical Controller (NHC), apresentada na seção 3.5.2, respectivamente. 3.5.2 Nested Hierarchical Controller (NHC) Na arquitetura Nested Hierarchical Controller (NHC) [20] o robô combina as informações provenientes de seus sensores juntamente com as informações fornecidas a priori em uma estrutura de dados que representa o modelo do mundo. Através deste modelo é possível realizar o planejamento das ações que devem ser tomadas. O planejador de ações é composto por três partes: Planejador de missão, Navegador e Piloto. O Planejador de missão tem a função de enviar partes da missão para o Navegador, que através das partes da missão recebidas, envia trechos de uma trajetória para o Piloto que então determina quais ações devem ser enviadas ao controlador de baixo nível para que o robô percorra o trecho da trajetória [7]. Conforme o robô se move no ambiente, novas informações dos sensores e da posição do robô são adquiridas mas o ciclo de planejamento não é repetido. Quando necessário, o Piloto realiza a correção do movimento local do robô a fim de lidar com eventuais divergências percebidas. 20 Caso isso não seja suficiente o Navegador gera outra trajetória e somente em último caso o Planejador de missão faz o replanejamento da missão [8]. 3.5.3 A Arquitetura Seleção de Ação Desenvolvida por Maes [25] em meados de 1989, a arquitetura seleção de ação utiliza um mecanismo dinâmico para selecionar quais comportamentos devem ser ativados em determinada situação. Essa arquitetura reativa não utiliza uma estratégia pré-definida como na arquitetura de subsunção desenvolvida por Brooks [36], e sim um nível de ativação para determinar em tempo de execução qual comportamento deve ser selecionado. O nível de ativação é influenciado pela situação atual em que o robô se encontra no ambiente, pelos objetivos de alto nível ou pela inibição de uma ação causada por comportamentos conflitantes. Quando mais de um comportamento possui uma pré-condição satisfeita, o comportamento com maior nível de ativação é escolhido, esse processo de seleção é repetido da maneira mais rápida possível alterando o estado e os níveis de ativação e consequentemente o comportamento emergente do robô conforme a navegação no ambiente. Como nesta arquitetura não há uma organização clara dos comportamentos em camadas, é difícil dizer qual o comportamento emergente que o robô apresentará em um ambiente dinâmico [7]. 3.6 O algoritmo de Dijkstra O algoritmo de Dijkstra foi concebido a fim de solucionar o problema de encontrar o menor caminho entre os vértices de um grafo, que pode ser ou não dirigido, e que possua os pesos de suas arestas positivo. Esse método não exige que as arestas estejam em nenhuma ordem específica se tornando assim mais geral do que outros métodos de busca por caminho em grafos como por exemplo o algoritmo de Kruskal e o algoritmo de Jarník-Prim [37]. Neste algoritmo é gerada uma árvore de conectividade que vai sendo expandida pela adição de arestas uma a uma. Se nesse processo um ciclo for detectado, uma aresta com peso máximo pertencente ao ciclo é descartada. Ao fim do processo é gerada uma árvore que representa o caminhamento entre cada nó do grafo e qual o menor caminho entre dois nós. Um pseudocódigo pode ser visto no Algoritmo 1. 21 Algoritmo 1 Algoritmo de Dijkstra 01: Algoritmo Dijkstra (Grafo G(V, E), vértice s); 02: Entrada: Um grafo G e o ponto de origem s. 03: Saída: Um conjunto P com os predecessores de cada 04: vértice no caminho mínimo até s 05: inicio 06: // inicialização dos dados 07: para cada vértice i em V faça 08: d[i] := INF; 09: pred[i] := null; 10: fim-para; 11: // vértices permanentemente marcados 12: P := emptyset; 13: // vértices marcados provisoriamente 14: L := emptyset; 15: // vértices não-marcados 16: U:=V; 17: // Inicia o percurso pelo vértice s 18: d[s] := 0; 19: mova s do conjunto U para o conjunto L; 20: enquanto (o conjunto L for não-vazio) faça 21: selecione o vértice i em L tal que 22: d(i) <= d(j) para todo j em L; 23: mova o vértice i de L para P; 24: para (todos os vértices j com (i,j) em A) 25: // A é a matriz de adjacência de G 26: se (d(j) > d(i) + l(i,j)) 27: // l(i, j) é uma função que retorna 28: // o custo da aresta (i,j) se a resta 29: // existe em A, ou INF caso contrário. 30: d(j) := d(i) + l(i,j); 31: pred(j) := i; 32: se (j está em U) então 33: mova j de U para L; 34: fim-se; 35: fim-se; 36: fim-para; 37: fim-enquanto; 38: retorne pred; 39: fim-djikstra; 22 Capítulo 4 O Módulo Reativo Neste capítulo será apresentado o módulo reativo desenvolvido durante este projeto. É importante lembrar que neste projeto o controle reativo não recebe nenhuma informação sobre um objetivo específico ou alguma tarefa que precisa ser executada. Nos testes realizados o robô foi inserido em um ambiente estruturado com obstáculos, apresentado na seção 4.3.1, onde o seu único objetivo foi navegar no ambiente detectando e reagindo a estes obstáculos. 4.1 Interface de Execução Para a execução do controle reativo foi desenvolvida uma interface gráfica através da ferraR menta GUI do software MATLAB . Esta interface foi criada a fim de facilitar a execução deste módulo e a mesma pode ser vista na figura 4.1. Figura 4.1: Interface de execução do módulo de controle reativo R Esta interface possui três botões associados à conexão do computador com o Lego , dois botões referentes ao início e ao fim da execução do controle e uma área de texto que serve para visualização de mensagens de status sobre a conexão ou a execução do controle. 4.2 Lógica de Controle R Antes de enviar qualquer tipo de comando do MATLAB , ou receber alguma informação R R ou parâmetro do Lego Mindstorms , primeiramente é necessário estabelecer uma conexão R entre o computador e o Smart Brick. A biblioteca RWTH-Mindstorms NXT toolbox possui TM um comando exclusivo para a busca de Smart Brick para a conexão via Bluetooth com os mesmos. Quando esse comando é disparado o computador busca e identifica um Smart Brick e imediatamente tenta estabelecer uma conexão entre ele e o computador utilizando o nome e o endereço MAC (Media Access Control) do Smart Brick. R R Uma vez estabelecida a conexão entre o computador e o Lego Mindstorms , são ins- tanciadas as variáveis toqdian, toqtras, dist, distesq e distdir permitindo que o controle reativo possa ser iniciado. No início da execução do controle cada uma das conexões de entrada dos sensores que será utilizada é associada a um sensor e cada uma das três conexões de saída é associada a um servo motor. Em seguida os estados dos sensores são verificados e seus valores são salvos nas variáveis toqdian que armazena o valor de estado do sensor de toque presente na dianteira do robô, toqtras que armazena o valor do estado do sensor de toque presente na traseira do robô e a variável dist que armazena o valor da distância de um obstáculo captada pelo sensor ultrassônico. Neste projeto, o controle reativo que foi desenvolvido é uma função que combina os valores obtidos a partir dos sensores do robô e então realiza comparações a fim de garantir a navegação autônoma do robô. As comparações realizadas chamam subfunções específicas que enviam ações para o robô. A execução deste controle é feita através da repetição de três testes que combinam a leitura dos sensores de toque e do sensor ultrassônico presentes no modelo de robô construído. Para o melhor entendimento do funcionamento deste controle é apresentado um diagrama de fluxo de execução, mostrado na figura 4.2, e o algoritmo de execução do mesmo. 24 Figura 4.2: Diagrama de fluxo de execução do controle Passo 1: O módulo reativo faz a leitura do sensor ultrassônico e do sensor de toque dianteiro, então testa se a distância captada pelo sensor ultrassônico é menor que 8 cm ou se o sensor de toque dianteiro do robô está pressionado, vai para o passo 2, se a distância captada pelo sensor ultrassônico é maior que 8 cm e se o sensor de toque dianteiro não está pressionado, vai para o passo 3. Passo 2: O módulo reativo entende que o robô está muito próximo ou está tocando um obstáculo, então envia um comando fazendo com que o robô recue aproximadamente 3 cm (essa distância é necessária para que o robô possa girar em seu próprio eixo para a direita ou para a esquerda sem que bata no obstáculo detectado) então vai para o passo 4. Passo 3: O módulo reativo entende que não existem obstáculos na frente do robô e envia um comando para que o robô se mova para frente enquanto a distância captada pelo sensor ultrassônico é maior que 13 cm e sensor de toque dianteiro não é pressionado. Se o sensor de toque dianteiro é pressionado volta para o passo 2, se não vai para o passo 4. Passo 4: O módulo reativo envia um comando para que o robô gire o motor responsável por 25 mover o sensor ultrassônico 90 graus no sentido horário, direcionando o sensor ultrassônico para a esquerda do robô, então faz a leitura da distância captada pelo sensor e armazena esse valor na variável distesq. Em seguida outro comando é enviado para que esse motor gire 180 graus no sentido anti-horário direcionando o sensor ultrassônico para a direita do robô, novamente é realizada a leitura do sensor e a distância captada é armazenada na variável distdir. Um último comando é enviado ao robô girando novamente o motor responsável por mover o sensor ultrassônico 90 graus no sentido horário alinhando novamente o sensor ultrassônico para a frente do robô. Em seguida, através da variável distdir, o módulo reativo verifica se a distância para um obstáculo à direita do robô é maior que 25 cm: se sim, vai para o passo 5; se não, passa para o passo 6. Passo 5: O módulo reativo entende que a direita do robô está livre então envia um comando fazendo com que o robô gire no seu próprio eixo 90 graus à direita e volta para o passo 1. Passo 6: O módulo reativo entende que a direita do robô não está livre, então testa o valor armazenado em distesq e verifica se a distância para um obstáculo à esquerda do robô é maior que 25 cm: se sim, vai para o passo 7; se não, vai para o passo 8. Passo 7: O módulo reativo entende que a esquerda do robô está livre então envia um comando fazendo com que o robô gire no seu próprio eixo 90 graus à esquerda e volta para o passo 1. Passo 8: Como foram detectados obstáculos à frente, à direita e à esquerda do robô, o módulo reativo envia um comando girando o motor responsável por movimentar o sensor ultrassônico 180 graus no sentido anti-horário direcionando o sensor para a traseira do robô e vai para o passo 9. Passo 9: É realizada a leitura do sensor ultrassônico e do sensor de toque traseiro do robô. Enquanto a distância captada é maior que 17 cm e o sensor de toque traseiro não é pressionando o módulo reativo envia um comando para que o robô recue. Se o sensor de toque traseiro é pressionado, vai para o passo 10, se não o módulo envia um comando direcionando a posição do sensor ultrassônico novamente para frente do robô e volta para o passo 4. Passo 10: O módulo reativo entende que o robô chocou sua traseira contra um obstáculo, então envia um comando para que o robô avance aproximadamente 3 cm (essa distância é necessária para que o robô possa girar em seu próprio eixo para a direita ou para a esquerda 26 sem que bata no obstáculo detectado) então volta para o passo 4. Como durante a execução do controle o mesmo tipo de situação pode acontecer várias vezes durante a exploração de um ambiente, uma vez iniciada a execução do controle o algoritmo apresentado anteriormente é executado até que o usuário, através da interface do controle (descrita na seção 4.1), interrompa a execução do mesmo e consequentemente a navegação do robô. 4.3 Testes Realizados Como os controles reativos dependem muito das informações locais obtidas por meio dos sensores disponíveis no robô, isso faz com que geralmente o ambiente ao qual o mesmo será inserido possua características que possam ser de alguma forma reconhecidas pelo robô para que seja possível a realização de tarefas no ambiente [7]. 4.3.1 Estrutura do Ambiente Para realizar os testes necessários quanto a capacidade de detecção de obstáculos e reação do robô controlado pelo módulo reativo que foi desenvolvido, foi construído um mapa na forma de labirinto. A figura 4.3 representa o ambiente e sua estrutura. 27 Figura 4.3: Mapa do ambiente de testes utilizado Este mapa possui dois tipos de obstáculos: paredes com altura de 25 cm que podem ser detectadas tanto pelo sensor ultrassônico quanto pelos sensores de toque do robô, e obstáculos com altura de 5 cm que não podem ser detectados pelo sensor ultrassônico mas que podem ser detectados pelos sensores de toque presentes no robô. 4.3.2 Resultados Obtidos A fim de ajustar e validar o funcionamento do módulo reativo foram executados vários testes no ambiente construído descrito na seção 4.3.1. Na figura 4.4 são apresentados quatro imagens do ambiente, estas imagens apresentam o resultado da navegação reativa realizada pelo robô em quatro testes. 28 (a) Resultado do Teste 1 (b) Resultado do Teste 2 (c) Resultado do Teste 3 (d) Resultado do Teste 4 Figura 4.4: Caminhos Traçados na Execução dos Testes com o Módulo Reativo Nas imagens, o ponto A indica o ponto inicial da navegação autônoma, o ponto B indica o ponto final e a linha vermelha traçada no mapa indica o caminho realizado pelo robô durante a sua exploração do ambiente. Embora nos resultados dos testes apresentados o robô tenha saído do labirinto, este não era o objetivo principal, e sim testar a reatividade do modelo no ambiente. 29 Capítulo 5 O Módulo Deliberativo Neste capítulo é apresentado o módulo deliberativo desenvolvido neste projeto. Como este módulo foi desenvolvido com base na arquitetura Nested Hierarchical Controller (NHC), apresentada na seção 3.5.2, ele é dividido em três partes ou três sub-módulos. Por tratar da tomada de ações que devem ser planejadas, o primeiro sub-módulo deste controle, apresentado na seção 5.3.1, é responsavél pela leitura do mapa do ambiente e pela geração da matriz de adjacências. A partir da matriz de adjacências e das coordenadas de origem e de destino, o segundo sub-módulo deste controle, apresentado na seção 5.3.2, é responsável pela geração da rota a ser executada pelo robô. O terceiro e último sub-módulo deste controle, apresentado na seção 5.3.3, é responsável pela execução da rota que foi gerada. Dessa forma, este controle recebe a priori o mapa do ambiente, uma posição de origem e uma posição de destino. A partir do mapa do ambiente é gerada a matriz de adjacências e a partir das coordenadas de origem e de destino o módulo deliberativo executa um algoritmo de busca de menor caminho que foi construído baseado no algoritmo de Dijkstra 1, a fim de encontrar a menor rota possível entre a posição de origem e de destino. Uma vez que a rota foi gerada com sucesso, a mesma é executada pelo módulo deliberativo, que a partir da orientação inicial do mesmo, envia os comando necessários para que ele execute a rota planejada e alcance seu objetivo. Ao longo deste capítulo o funcionamento de cada sub-módulo do controle deliberativo será explicado com mais detalhes. 5.1 Interface de Execução Assim como no módulo reativo, para a execução do módulo deliberativo foi desenvolvida uma interface gráfica de iteração com o usuário utilizando a ferramenta GUI do software R MATLAB . Esta interface, mostrada na figura 5.1, permite que o usuário carregue o mapa do ambiente, defina as coordenadas de origem e de destino, gere uma rota entre estas coordenadas e execute a mesma. Figura 5.1: Interface de execução do módulo de controle deliberativo A fim de permitir que o usuário acesse os recursos do módulo deliberativo, a inteface desenvolvida possui um botão que tem a função de carregar o mapa do ambiente, dois botões para definir ou redefinir as coordernadas de origem e de destino do robô no mapa, um botão para gerar a rota a partir do mapa carregado e das coordenadas definidas e um botão para executar a rota gerada. Esta interface possui ainda uma imagem que indica como será a rota executada pelo robô e qual sua posição no mapa segundo essa rota. 5.2 Estrutura do ambiente Para realizar os testes necessários quanto a geração de rotas do módulo deliberativo utilizouse como ambiente uma área retangular de 1,20 m x 1,80 m. Esta área foi dividida em quadrados de 30 cm de lado, dessa forma o mapa ficou dividido em 4 linhas e 6 colunas, resultando em 24 células iguais, como visto na figura 5.2. A adoção da representação do mapa em células se faz nescessário para garantir que o robô possa movimentar-se no ambiente sem esbarrar nos obstáculos do ambiente e também para poder estimar a posição do robô dentro do mapa. O tamanho das células foi definido a partir das 31 dimensões do modelo de robô utilizado, apresentado na seção 3.4. Considerando as dimensões do robô, 30 cm é uma distância adequada para que o mesmo execute manobras no ambiente sem ultrapassar os limites de uma célula evitando colisões com possíveis obstáculos. Figura 5.2: Mapa utilizado nos testes do módulo deliberativo A partir da disivão do mapa em células, o mesmo passou a ser representado na forma de uma matriz de dimensão 4x6 de inteiros, onde os obstáculos do ambiente são representados por células com o valor 1 e o restante do ambiente, ou seja os espaços livres, são representados por células com o valor 0. Um exemplo desse mapa com obstáculos inseridos e como ficará sua representação matricial podem ser vistos na figura 5.3. (a) Distribuição de obstáculos no mapa (b) Representação do mapa na forma de matriz Figura 5.3: Exemplo de mapa e de sua representação 32 5.3 Lógica do controle Como o módulo deliberativo baseia-se no conhecimento prévio do ambiente para planejar uma ação, antes de definir um ponto de origem e de destino e antes de gerar uma rota, é necessário carregar o mapa do ambiente para a memória do módulo deliberativo (computador). Este mapa é fornecido através de um arquivo .txt. Após o carregamento do mapa, o usuário deve definir a coordernada de origem, ou seja qual é a posição inicial do robô no mapa do ambiente, e a coordenada de destino, que indica qual a posição que o robô pretende alcançar no mapa. Estas informações ficam armazenadas em memória para serem usadas no cálculo da rota. 5.3.1 Matriz de adjacências Como o cálculo da rota utiliza o algoritmo de Dijkstra [38] e este se aplica a grafos, é necessário interpretar a matriz que representa o mapa do ambiente na forma de um grafo. Neste caso cada célula representará um nó no grafo, a distância entre os nós vizinhos será sempre igual a 1 e o grafo será bidirecionado. Dessa forma, uma vez carregado o mapa do ambiente, o módulo deliberativo varre a matriz que representa este mapa e assume que cada célula é um nó do grafo, criando uma segunda matriz, que armazena as adjacências ou seja, a conectividade entre os nós. A partir da matriz de entrada e de suas dimensões, o módulo deliberatvo calcula quantas células esse mapa possui e consequentemente quantos nós precisará considerar para a construção da matriz de adjacências, e então instancia uma matriz de dimensão igual ao número de células da matriz mapa. Esta matriz inicialmente possui todas suas células com o valor 0. A matriz mapa é varrida da primeira posição até a última executando o algoritmo representado no fluxograma apresentado na figura 5.4, o processo de criação da matriz de adjacências a partir da matriz mapa segue representado na forma de fluxograma apresentado na figura 5.4, e na sequência é descrito o algoritmo em alto nível utilizado no processo de conversão. 33 Figura 5.4: Fluxograma do algoritmo de geração da matriz de adjacências Passo 1: Lê o arquivo texto que contém a matriz que representa o mapa do ambiente, armazena essa matriz na variável mapa. A partir dessa variável identifica qual é a dimensão dessa matriz e a armazena no vetor dim. Vai para o passo 2. Passo 2: Instacia a matriz MatAdj de zeros, que irá armazenar as adjacências das células do mapa. Essa matriz possui dimensão N x N onde N é número total de células da matriz mapa. Vai para o passo 3. Passo 3: Percorre todas as células da matriz mapa e testa a conectividade de cada célula com as quatro vizinhanças. Para cada célula vizinha encontrada, seta o valor 1 na célula da matriz MatAdj de coordenadas célula testada célula vizinha. Neste fluxograma é verificado se o valor da célula atual é igual zero: se isso for verdadeiro, a célula, através de suas coordenadas, tem seu valor convertido para um valor que é guardado na variável Pos1. Este valor representará uma linha ou coluna na matriz de adjacências. As fórmulas usadas para a conversão das coordenadas de uma célula da matriz mapa para um valor de posição na matriz de adjacências variam conforme a posição da célula com relação a célula que está sendo avaliada. Assim, para cada célula livre que possui uma célula vizinha livre, a matriz de adjacências, nas coordenadas Pos1 e Pos2, receberá o valor 1 indicando que existe conectividade entre esses nós. Na figura 5.5 é dado um exemplo de como é verificado se uma célula possui ou não conexão com as suas células vizinhas. Nesta figura a célula que está sendo testada é a célula 34 que possui o valor zero. Figura 5.5: Verificação de conexão com as quatro vizinhanças Para converter o valor da célula cuja as vizinhanças estão sendo verificadas, neste caso a célula com o valor zero, é utilizada a fórmula 5.1, onde i representa a linha da célula, j representa a coluna e Co representa o total de colunas da matriz mapa. O valor da atual célula em teste é armazenado na variável Pos1. P os1 = (((i − 1) ∗ Co) + (j − 1)) + 1 (5.1) As direções consideradas para a vizinhança entre as células são à cima, à baixo, à frente e atrás, onde, para cada célula vizinha que possui valor igual a zero, indicando estar livre, é utilizado uma fórmula de conversão diferente. Esta fórmula varia conforme a posição da célula e o valor convertido é armazenado na variável Pos2. Para testar a conectividade da célula 0 quanto a célula 1 é utilizada a equação 5.2. Para testar a conectivade da célula 0 quanto a célula 2 é utilizada a equação 5.3. Para testar a conectividade da célula 0 quanto a célula 3 é utilizada a equação 5.4. E por fim, para testar a conectividade quanto célula 0 e a célula 4 é utilizada a equação 5.5. P os2 = (((i − 1) ∗ Co) + j) + 1 (5.2) P os2 = (((i − 2) ∗ Co) + (j − 1)) + 1 (5.3) P os2 = (((i − 1) ∗ Co) + (j − 2)) + 1 (5.4) P os2 = ((i ∗ Co) + (j − 1)) + 1 (5.5) 35 No exemplo de teste de conectividade entre a vizinhança apresentado na figura 5.5 a matriz de adjacências teria o valor 1 setado para as coordenadas obtidas após o uso de cada fórmula apresetada anteriormente. Assim sendo, o valor de Pos1 para a célula representada em 0 seria 8, os valores que Pos2 assumiria para as células representadas pelos números 1, 2, 3 e 4 seriam 9, 2, 7 e 14 respectivamente. Esses valores seriam os índices da matriz de adjacências MatAdj(Pos1,Pos2) que receberia o valor 1 nas posições MatAdj(8,9), MatAdj(8,2), MatAdj(8,7), MatAdj(8,14). Dessa forma após testadas as conectividades do mapa apresentado na figura 5.3(a), o mesmo será convertido para um grafo como visto na figura 5.6. Figura 5.6: Grafo traçado a partir do mapa de entrada 5.3.2 Geração da rota Uma vez que a matriz de adjacências foi construída a partir do mapa do ambiente, a rota que deverá ser traçada pelo robô é gerada. Para isso são usadas as coordenadas de origem e de destino do robô na matriz mapa. A geração de uma rota para que o robô alcance seu objetivo divide-se em duas etapas: teste de conectividade entre a origem e o destino definidos e menor caminho possível entre estes pontos no mapa. Este processo é apresentado no fluxograma mostrado na figura 5.7 e no algoritmo apresentado na sequência. 36 Figura 5.7: Fluxograma do algoritmo de verificação de conectividade e de geração da rota Passo 1: Adiciona nó de origem a lista de vértices e define esse nó como atual. Seta o custo acumulado como 0. Vai para o passo 2. Passo 2: Verifica se existem nós não visitados na lista de vértices. Se sim, seleciona dentre os nós não visitados o de menor custo acumulado. Define este nó como nó atual e vai para o passo 3. Se todos os nós da lista estiverem marcados como visitados vai para o passo 4. Passo 3: Visita os nós adjacentes ao nó atual adicionando-os a lista de vértices. Incrementa em 1 o custo acumulado de cada nó adicionado. Marca o nó atual como visitado e vai para o passo 4. Passo 4: Verifica se o nó de destino foi adicionado a lista de vértices. Se sim, vai para o passo 5. Se não vai para o passo 8. Passo 5: Adiciona nó destino ao caminho e define este nó como atual. Vai para o passo 6. Passo 6: Seleciona na lista de vértices o nó de menor custo acumulado que é adjacente ao nó atual. Adiciona este nó ao caminho e define este nó como nó atual. Vai para o passo 7. Passo 7: Verifica se o nó atual é o nó de origem. Se sim, fim da execução do algoritmo. Se não, volta para o passo 6. Passo 8: Caminho impossível, fim da execução. Ao fim do processo de geração da rota, se existir um caminho possível entre a origem e o destino, este caminho ficará salvo numa lista chamada listcam. Como os testes sobre as 37 adjacências entre as células do mapa utilizam as células com seus valores convertidos para um valor de posição e não de coordenada, é necessário converter os valores de posição novamente em coordenadas da matriz mapa. No processo de conversão desses valores, a listcam é percorrida executando o algoritmo apresentado na figura 5.8. Figura 5.8: Fluxograma do algoritmo que converte o caminho da rota gerada Passo 1: variável ind recebe 1. Vai para o passo 2. Passo 2: faz o mod do valor armazenado na posição ind da lista pelo número de colunas da matriz mapa. Se o resultado for igual a 0, vai para o passo 3. Se não, vai para o passo 4. Passo 3: divide o valor armazenado na posição ind da lista pelo número de colunas da matriz mapa e armazena o resultado na variável div. As coordenadas desse valor do caminho serão o valor armazenado em div para linha e o valor correspondente ao número de colunas para a coluna. Salva os valores das coordenadas e vai para o passo 4. Passo 4: divide o valor armazenado na posição ind da lista pelo número de colunas da matriz mapa e armazena o resto da divisão na variável div. Armazena o resultado da operação mod do valor da posição atual pelo número de colunas da matriz mapa na variável div2. As coordenadas desse valor do caminho serão o valor armazenado em div para linha e o número armazenado em div2 para coluna. Salva os valores das coordenadas e vai para o passo 5. Passo 5: Se o valor de i for igual ao número de posições da lista vai para o passo 6. Se não, incrementa i em 1 e vai para o passo 2. Passo 6: Fim do algoritmo, caminho convertido. Um exemplo da aplicação do algoritmo de conversão de rotas é apresentado na figura 5.9 onde a partir do ponto de origem identificado pela letra A e do ponto de destino identificado 38 pela letra B no mapa, é gerada a rota de menor distância estre estes dois pontos. (a) Origem e destino (b) Rota executada Figura 5.9: Exemplo de caminho convertido Como a rota gerada é calculada a partir do grafo representado pela matriz de adjacências, os valores dos vértices que fazem parte dessa rota precisam ser convertidos para coordenadas de célula, pois postetiormente essas coordenadas serão utilizadas para guiar o robô pelo mapa. O resultado da conversão da rota gerada no exemplo anterior segue apresentado na figura 5.10. Figura 5.10: Resultado da conversão da rota calculada 5.3.3 Execução da rota Uma vez que a rota entre a origem e o destino foi gerada, o próximo passo do módulo deliberativo é executar essa rota de modo que o robô navegue no ambiente e alcance a sua posição de destino. A execução da rota que foi gerada segue representada no fluxograma apresentado na figura 5.11. Inicialmente a célula atual é definida como a célula de origem e o sentido, ou seja a orientação do robô dentro do mapa, adotado como destino inicial da execução de uma rota será sempre oeste->leste. Essa orientação pode variar entre oeste->leste, leste->oeste, norte->sul e sul->norte, conforme a posição das células que fazem parte do caminho que deverá ser traçado até o destino. 39 Figura 5.11: Fluxograma do algoritmo que executa a rota gerada A partir da célula atual é verificado, com base na próxima célula que deve ser alcançada pelo robô dentro do mapa, se a direção, ou seja, o sentido do robô, deve ou não ser alterado, se o sentido precisar ser alterado o módulo envia os comandos necessários para que o robô execute a manobra de modo a ficar de frente para a célula que deverá alcançar no mapa. Após a realização da manobra, o sentido atual do robô é atualizado, o módulo envia um comando para o robô de modo que este navegue até a próxima célula do caminho e a célula atual é atualizada. Esse processo se repete enquanto a célula atual em que o robô se encontra não for a célula de destino. 5.4 Testes Realizados No intuito de testar e validar o funcionamento do módulo deliberativo, foram executados vários testes, assumindo o ambiente apresentado na figura 5.2. Em cada um dos testes foram distribuídos vários obstáculos pelo ambiente, esses obstáculos foram colocados em determinadas posições do mapa visando simular as várias situações que podem ser confrontadas durante a exploração de um ambiente real. Nas imagens que representam os resultados dos testes realizados, a célula que contém a letra A indica a célula de origem e a célula que contém a letra B indica a célula de destino. Nos testes de número 1, 2 e 3 apresentados nas figuras 5.12, 5.13 e 5.14 respectivamente, o módulo deliberativo calculou rotas e as executou de maneira eficiente de modo que o robô saiu do ponto de origem e chegou ao ponto de destino. 40 (a) Origem e destino (b) Rota executada Figura 5.12: Mapa utilizado no teste no 1 (a) Origem e destino (b) Rota executada Figura 5.13: Mapa utilizado no teste no 2 (a) Origem e destino (b) Rota executada Figura 5.14: Mapa utilizado no teste no 3 No teste de número 4, apresentado na figura 5.15, a fim de testar a correção automática de rotas em tempo de execução, foram adicionados dois obstáculos representados pelas células marcadas por um X. Esses dois obstáculos não foram mapeados no ambiente original, de modo que o módulo deliberativo não tivesse conhecimento dos mesmos. Dessa forma, a rota traçada pelo módulo deliberativo inicialmente, apresentada na figura 5.15(b), passava justamente pelas 41 células ocupadas pelos novos obstáculos. Ao tentar navegar até essas células, o robô reagiu ao obstáculo enviando essa informação para o módulo de controle deliberativo que atualizou o mapa do ambiente e calculou uma nova rota de navegação. (a) Origem e destino (b) Rota gerada (c) Rota executada Figura 5.15: Mapa utilizado no teste no 4 No teste número 5, apresentado na figura 5.16, definiu-se uma situação em que o módulo deliberativo não seria capaz de gerar uma rota entre a origem e o destino: foi utilizado um modelo de ambiente em que os pontos de origem e de destino ficaram separados por uma parede. Dessa forma o módulo deliberativo, com base na matriz mapa desse ambiente, gerou a matriz de adjacências e a partir da origem visitou todos os nós alcançáveis. (a) Origem e destino (b) Caminho impossível Figura 5.16: Mapa utilizado no teste no 5 42 A figura 5.16 apresenta o resultado da tentativa de construção da rota pelo módulo deliberativo executando o algoritmo descrito na seção 5.3.2. O número em cada célula, indica em qual iteração do algoritmo a mesma foi visitada. Por fim, todas as células alcançáveis a partir da origem foram visitadas e como a célula de destino não pôde ser alcançada, nenhuma rota pode ser gerada. A figura 5.17 apresenta o resultado do teste número 6. Neste teste existiam dois caminhos distintos possíveis para alcançar o ponto de destino a partir do ponto de origem no mapa, sendo que o módulo deliberativo calculou e executou a menor rota dentre as duas possíveis. (a) Origem e destino (b) Rota gerada (c) Rota executada Figura 5.17: Mapa utilizado no teste no 6 43 Capítulo 6 Considerações Finais A navegação de robôs vem se mostrando um problema muito interesante à pesquisa de sistemas inteligentes e suas propriedades, sendo algumas delas a adaptação e a autonomia. Neste trabalho foram apresentadas as principais arquiteturas de controle para robôs móveis autônomos. Baseados nas principais características das arquiteturas Seleção de Ação e Nested Hierarquical Controller, e na modularidade da arquitetura AuRA, foram desenvolvidos dois módulos de controle para a navegação autônoma de robôs. O primeiro módulo desenvolvido, o módulo reativo, navega em um ambiente sem possuir nenhuma informação referente ao mesmo, reagindo ao mesmo desviando de obstáculos e alterando a rota de navegação. A implementação deste módulo foi validada através dos testes realizados no ambiente construído. O segundo módulo desenvolvido, o módulo deliberativo, gera uma rota de navegação entre dois pontos, a partir do mapa do ambiente que irá explorar. A implementação deste módulo também foi validada através dos testes realizados no ambiente. Quanto a implementação do módulo reativo, por não tratar de informações quanto ao ambiente ou planejamento de rotas e por possuir o objetivo de reagir ao ambiente, esta foi a parte menos complexa do projeto, visto que o número de sensores disponíveis no kit utilizado na construção do robô era reduzido, diminuindo a precisão de percepção do ambiente pelo mesmo, o que levou ao desenvolvimento de um projeto de módulo mais simplificado. Quanto a implementação do módulo deliberativo, por tratar de informações iniciais quanto ao ambiente, possuir pontos definidos de origem e de destino e ter o objetivo de alcançar um ponto no mapa traçando a menor rota, foi a parte mais complexa do projeto, visto que o processo de navegação envolveu a conversão do mapa do ambiente em uma estrutura de grafos onde foi traçada a rota e após esse processo essa rota precisou ser convertida para as coordenadas do ambiente. Um ponto importante a ser considerado no desenvolvimento deste módulo é a precisão quanto ao mapeamento do ambiente onde será executada a navegação: uma vez que as dimensões do ambiente são imprecisas, o processo de navegação poderá ser comprometido. Quanto as ferramentas utilizadas: R • O MATLAB , suas ferramentas e funcionalidades foram eficientes no processo de de- senvolvimento deste projeto, sua programação simplificada facilitou a implementação dos módulos que foram desenvolvidos. R • A biblioteca RWTH Mindstorms NXT toolbox possui uma documentação de fácil entendimento, completa e de fácil acesso. Embora não foram explorados todos os seus comandos e suas funcionalidades, mostrou-se uma alternativa muito interessante na programação dos módulos. R R • O kit Lego Mindstorms NXT é uma alternativa interessante quanto a construção e programação de robôs, embora esse kit possua um número reduzido de sensores e motores, o kit permitiu a construção de um modelo de robô capaz de testar e validar os módulos. A integração dos dois módulos desenvolvidos em um único sistema de controle ainda não foi realizada. Esta integração poderá ser realizada em um projeto futuro juntamente com outras ideias de aplicação ou aprimoramento do sistema, como: • No processo de criação da matriz de adjacências, verificar as conexões com as oito vizinhanças de uma célula; • Utilização de um algoritmo heurístico para a geração de rotas; • Aumentar a capacidade sensorial do protótipo de robô utilizado, com o objetivo de aumentar o grau de percepção do mesmo; • Investigar outras formas de fornecer informações quanto ao mapa do ambiente; • Utilizar o módulo de controle reativo para mapeamento de ambientes; R R • Explorar outras formas de programação e comunicação entre o kit Lego Mindstorms NXT e o computador. 45 Referências Bibliográficas [1] The Robocup Federation. What is Robocup. Disponível em: http://www.robocup.org/aboutrobocup/, Acessado em: 08 Março 2012. [2] Irobot Corporation. Matlab - The language Of Technical Computing. Disponível em: http://www.irobot.com/gi/ground/510_PackBot/, Acessado em: 08 Março 2012. [3] DAUNA, C. Curiosity, The Stunt Double. Disponível em: http://mars.jpl.nasa.gov/msl/, Acessado em: 08 Março 2012. [4] FABRO, J. A. Grupos Neurais e Sistemas Nebulosos: Aplicação a Navegação Autônoma. Dissertação (Mestrado) — Universidade Estadual de Campinas - Departamento de Engenharia de Computação e Automação Industrial, Campinas - São Paulo, Fevereiro 1996. [5] SANTIN, G. Dispositivo de Navegação Autônoma. Dissertação (Monografia de Conclusão de Curso) — Universidade Regional Integrada do Alto Uruguai e das Missões - Departamento de Engenharias e Ciência da Computação, Frederico Westphalen, Novembro 2004. [6] ARKIN, R. C. Towards Cosmopolitan Robots: Intelligent Navigation In Extended ManMade Environments. Tese (Doutorado) — University of Massachusetts, Massachusetts, Setembro 1987. [7] JUNIOR, V. G. Arquitetura Híbrida para Robôs Móveis Baseada em Funções de Navegação com Interação Humana. Dissertação (Doutorado) — Escola Politécnica da Universidade de São Paulo - Departamento de Engenharia Mecatrônica e de Sistemas Mecânicos, São Paulo, Junho 2006. [8] HEINEM, F. J. Sistema de Controle Híbrido para Robôs Móveis Autônomos. Dissertação (Mestrado) — Universidade do Vale do Rio dos Sinos - Centro de Ciências Exatas e Tecnológicas, São Leopoldo, Maio 2002. [9] RUSSELL, S. J.; NORVIG, P. Artificial Intelligence: A Modern Approach. 3rd. ed. [S.l.]: Prentice Hall, 2009. [10] SANTOS, K. R. da S. Sistema de Navegação Autônoma para Robôs Móveis Baseado em Arquitetura Híbrida: Teoria e Aplicação. Dissertação (Mestrado) — Universidade Federal de Itajubá - Programa de Pós-Graduação em Engenharia Elétrica, Itajubá, Maio 2009. [11] MOBILEROBOTS, A. MobileSim. Disponível em: http://robots.mobilerobots.com/wiki/MobileSim, Acessado em: 15 Outubro 2012. [12] CAZANGI, R. R. Uma Proposta Evolutiva para Controle Inteligente em Navegação Autônoma de Robôs. Dissertação (Mestrado) — Universidade Estadual de Campinas - Faculdade de Engenharia Elétrica e de Computação, Campinas, Maio 2004. [13] SILVA, L. R. da. Análise e Programação de Robôs Móveis Autônomos da Plataforma Eyebot. Dissertação (Mestrado) — Universidade Federal de Santa Catarina - Programa de Pós-Graduação em Engenharia Elétrica, Florianópolis, Março 2003. [14] PEREIRA, J. Avaliação e Correção do Modelo Cinemático de Robôs Móveis Visando a Redução de Erros no Seguimento de Trajetórias. Dissertação (Mestrado) — Universidade Estadual de Campinas - Faculdade de Engenharia Elétrica e de Computação, Joinville, Dezembro 2003. [15] ARAúJO, S. A. de; LIBRANTZ, A. F. H. Visão e inteligência computacionais aplicadas a navegação autônoma de robôs. Exacta, v. 4, n. 002, p. 343–352, Jul./Dez. 2006. [16] JUNIOR, P. R. C. Sistema Inteligente de Navegação Autônoma: Uma Abordagem Modular e Hierárquica com Novos Mecanismos de Memória e Aprendizagem. Dissertação (Mestrado) — Universidade Estadual de Campinas - Faculdade de Engenharia Elétrica e de Computação, Campinas, Dezembro 2001. 47 [17] ARKIN, R. C.; BALCH, T. AuRA: Principles and Practice in Review. 1994. Disponível em: < http://smartech.gatech.edu/xmlui/bitstream/handle/1853/21633/jetai- final.pdf?sequence=1>. Acessado em: 21/03/2012. [18] JUNG, C. R. et al. Computação embarcada: Projeto e implementação de veículos autônomos inteligentes. In: XXV Congresso da Sociedade Brasileira de Computação. São Leopoldo: [s.n.], 2005. p. 49. [19] ARKIN, R. C. Behavior-based robotics. [S.l.]: The MIT Press, 1998. [20] MEYSTEL, A. Autonomous mobile robots : vehicles with cognitive contro. Singapore: World Scientific, 1991. [21] ALBUS, J. S. Rcs: a reference model architecture for intelligent control. Computer, v. 25, n. 5, p. 56 –59, may 1992. [22] ALBUS, J. S.; MCCAIN, H. G.; LUMIA, R. NASA/NBS Standard Reference Model for telerobot control system architecture (NASREM). Gaithersburg, MD: U.S. Dept. of Commerce, National Institute of Standards and Technology, 1989. [23] BROOKS, R. A. Intelligence without representation. Artificial Inteligence, v. 47, p. 139– 159, January 1991. [24] BROOKS, R. A. A robust layered control system for a mobile robot. In: IYENGAR, S. S.; ELFES, A. (Ed.). Autonomous Mobile Robots: Control, Planning, and Architecture (Vol. 2). Los Alamitos, CA: IEEE Computer Society Press, 1991. p. 152–161. [25] MAES, P. The dynamics of action selection. In: Proceedings of the 11th inter- national joint conference on Artificial intelligence - Volume 2. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1989. (IJCAI’89), p. 991–997. Disponível em: <http://dl.acm.org/citation.cfm?id=1623891.1623914>. [26] MURPHY, R. R. Introduction to AI Robotics. 1. ed. Cambridge, MA, USA: MIT Press, 2000. 48 [27] CONNELL, J. H. Sss: A hybrid architecture applied to robot navigation. In: IEEE Conference on Robotics and Automation. New York - EUA: [s.n.], 1992. p. 2719–2724. [28] The Mathworks. Matlab - The language Of Technical Computing. Disponível em:http://www.mathworks.com/products/matlab/description1.html, Acessado em: 20 Março 2012. [29] HANSELMAN, B. L. D. MATLAB 6: Curso completo. São Paulo: Prentice Hall, 2003. ISBN 85-87918-56-7. [30] RWTH Aachen University. About RWTH. Disponível em: http://www.rwth- aachen.de/aw/zentral/english/Themes/ lw/About_RWTH/. Acessado em: 18 Julho 2011. [31] LFB Lehrstuhl für Bildverarbeitung. RWTH-Mindstorms NXT Toolbox. Disponível em: http://www.mindstorms.rwth-aachen.de/trac/wiki/Documentation Acessado em: 04 Outubro 2012. [32] The Lego Group. What is NXT. Disponível em: http://mindstorms.lego.com/en- us/whatisnxt/default.aspx, Acessado em: 16 Março 2012. [33] The Lego Group. TECHNIC. Disponível em: http://technic.lego.com/en-us/Default.aspx, Acessado em: 09 Março 2012. [34] Rover Explorer Disponível Robot. em technology.blogspot.com.br/2012/05/rover-explorer-robot-building.html :http://notes-onAcessado em: 21 Maio 2012. R R [35] POSTAL, A. et al. Controles remotos alternativos para Lego Mindstorms NXT 2.0. In: IV Encontro Paranaense de Computação. Cascavel, PR: [s.n.], 2011. p. 31–40. [36] BROOKS, R. A. A robust layered control for a mobile robot. IEEE Journal of Robotics and Automation, v. 2, n. 1, p. 14–23, Mar 1986. [37] DROZDEK, A. Estruturas de Dados e Algoritmos em C++. São Paulo - SP: São Paulo: Pioneira Thomson Learning, 2002. 49 [38] SEDGEWICK, R. Algorithms in C - part 5: graph algorithms (3 .ed.). [S.l.]: AddisonWesley-Longman, 2002. I-XIII, 1-482 p. ISBN 978-0-201-31663-6. 50