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