Upload
others
View
2
Download
0
Embed Size (px)
Citation preview
Universidade de São Paulo – USP
Escola de Engenharia de São Carlos – EESC
Departamento de Engenharia Mecânica – SEM
Lucas Cabrini Scanavini
IMPLEMENTAÇÃO E COMPARAÇÃO DE ALGORITMOS DE
NAVEGAÇÃO COM ROS E SIMULAÇÃO COM VREP
São Carlos
2016
1
Lucas Cabrini Scanavini
IMPLEMENTAÇÃO E COMPARAÇÃO DE ALGORITMOS DE
NAVEGAÇÃO COM ROS E SIMULAÇÃO COM VREP
Monografia apresentada à Escola de
Engenharia de São Carlos da Universidade
de São Paulo, como trabalho de conclusão
do curso de Engenharia Mecatrônica.
Orientador: Prof. Dr. Marcelo Becker
São Carlos
2016
4
“Não crescemos quando as coisas ficam fáceis, e sim quando enfrentamos nossos desafios.”
(DESCONHECIDO)
5
AGRADECIMENTOS
Agradeço primeiramente à Deus. Ao meu falecido pai e futuro colega de profissão Carlos Eduardo Scanavini. Ao meu pai de coração Maurício e à minha mãe Adriane, por todo apoio e suporte durante todos esses anos de faculdade. À minha fiel companheira e melhor amiga Tatiana, por toda ajuda e suporte. Ao meu irmão Pedro, aos meus avós. Ao Rômulo e Juliano pelas inúmeras ajudas e conselhos durante execução deste trabalho. Ao meu orientador Becker pela oportunidade e conselhos.
6
RESUMO
Este trabalho teve como objetivo desenvolver, programar e comparar diferentes
algoritmos de navegação para o planejamento de trajetórias de robôs autônomos.
Foram abordados os algoritmos BUG 1, BUG 2 e A* (Astar). As soluções foram
desenvolvidos no Robot Operating System (ROS), utilizando a linguagem de código
C++. Para efeitos de validação, foram feitas simulações com um robô terrestre,
utilizando o, software V-REP (Virtual Robot Experimentation Plataform), da
companhia CoppeliaRobotics.
Para os diferentes algoritmos, verificaram-se as vantagens e desvantagens de cada um
quanto à sua eficiência, tempo de resolução, complexidade e estrutura do código.
Os resultados mostram que o algoritmo Bug1 acaba sendo lento devido à necessidade
de sempre contornar todo o obstáculo para poder rumar em direção ao objetivo. O
Bug2, assim como o Bug1, apresenta a mesma simplicidade de código e baixo custo
de execução. Entretanto, o Bug2 destaca-se em relação ao primeiro pelo desempenho,
pois não necessariamente necessita contornar o obstáculo.
O A*, com maior complexidade de código e custo computacional de execução,
mostrou-se um excelente planejador de trajetória global, mas que está atrelado a
necessidade de mapeamento prévio. Dessa forma, pode ser usado em conjunto com o
Bug para contornar obstáculos não previamente mapeados ou um algoritmo campos
potenciais.
Palavras-chaves: Algoritmos de navegação, ROS, Bug, A*, Astar, VREP, robô
autônomo.
8
ABSTRACT
The objective of this work was to develop, program and compare different algorithms
of autonomous navigation and path planning for autonomous robots. The Bug 1, Bug2
and A* (Astar) algorithms were developed. The codes were developed in C++
language using ROS platform (Robotic Operating System). To test the algorithms, it
was used a robot running on a simulation software VREP (Virtual Robot
Experimentation Platform) from CoppeliaRobotics company.
For all the algorithms used, it were verified its advantages and disadvantages for each,
comparing its efficiency, time to achieve the goal, complexity and code structure.
The results showed that Bug1 algorithm is slow because it needs to circumnavigate
the entire obstacle until start going through the goal again. Bug2 just like Bug1
presents the same code simplicity and low execution cost. However, it stands out in
relation to Bug1 for its good performance and its needlessness to circumnavigate the
entire obstacle, as it just needs to find the m-line again to pursue the goal.
The A* (Astar) besides presenting a complex code and higher computational cost of
execution, showed itself as an excellent global path planning, being the only negative
point the necessity to have a map previously passed to it. Thus, it can be used in
conjunction with the Bug to circumnavigate previously unmapped obstacles or a
potential fields algorithm, for the local path planning.
Keywords: Path Planning, ROS, Bug, A*, Astar, VREP, Autonomous Robot, Obstacleavoidance.
10
LISTA DE FIGURAS
Figura 1 – Representação da estrutura básica do Grafo Computacional do ROS. ...... 22
Figura 2 – Representação do funcionamento do Navigation Stack. ............................ 23
Figura 3 – Representação da visão geral do pacote nav_core. Fonte: WikiRos .......... 24
Figura 4 – Exemplo genérico de uma trajetória utilizando o algoritmo BUG ............. 29
Figura 5 – Exemplo de execução de trajetória de um robô utilizando o algoritmo BUG
0, resultando em um caminho falho para encontrar o ponto de chegada. .................... 30
Figura 6 – Exemplo de trajetória para robô utilizando o algoritmo BUG 2(CHOSET)
...................................................................................................................................... 32
Figura 7–Representação do melhor trajeto (menor distância) ..................................... 33
Figura 8–Representação do funcionamento do BUG 2 (CHOSET) ............................ 34
Figura 9 – Ambiente para o Exemplo do Algoritmo A*.. ........................................... 37
Figura 10 – Primeira iteração ....................................................................................... 38
Figura 11 – Segunda iteração ....................................................................................... 38
Figura 12 – Figura final – Células em cinza determinam o caminho encontrado,
células em vermelho são as que foram colocadas na lista fechada e azuis as que estão
na lista aberta. .............................................................................................................. 39
Figura 13–Mapa de simulação para algoritmos Bugs no simulador VREP ................. 41
Figura 14–Mapa de simulação para algoritmo A* no simulador VREP ..................... 41
Figura 15 – Robôs utilizados para simulação dos algoritmos. a) robô sonar; b) robô
laser .............................................................................................................................. 42
Figura 16 – Representação do robô e velocidades ....................................................... 43
Figura 17 – Interface do grafo de execução da classe BUG. ....................................... 49
11
Figura 18 – Arquivo move_base.launch: pai de planejamento de trajetória ............... 52
Figura 19 – Arquivo local_costmap_params.yaml ...................................................... 54
Figura 20 – Arquivo global_costmap_params.yaml .................................................... 54
Figura 21 – Arquivo costmap_common_params ......................................................... 54
Figura 22 – Arquivo base_local_planner_params.yaml .............................................. 55
Figura 23 – Arquivo move_base_params.yaml ........................................................... 56
Figura 24 – Grafo de execução do Navegation Stack funcionando no robô laser. ...... 61
Figura 25 – Simulação do BUG 1 no MAPA 1. .......................................................... 63
Figura 26 – Simulação do BUG 1 no MAPA 2. .......................................................... 64
Figura 27 –Simulação do BUG 1 no MAPA 3. ........................................................... 64
Figura 28 – Simulação do BUG 2 no MAPA 1. .......................................................... 65
Figura 29 – Simulação do BUG 2 no MAPA 2. .......................................................... 65
Figura 30 –Simulação do BUG 2 no MAPA 3. ........................................................... 66
Figura 31 – Simulação do algorítmo A* (Astar) no mapa 1.. ...................................... 70
Figura 32 – Simulação do algorítmo A* (Astar) no mapa 2.. ...................................... 70
Figura 33 – Simulação do algorítmo A* (Astar) no mapa 3.. ...................................... 71
12
LISTA DE TABELAS
Tabela 1 – BUG 1 versus BUG 2: Tempos de execução de trajetória ......................... 67
Tabela 2 – BUG 1 versus BUG 2: Distâncias percorridas ........................................... 68
Tabela 3 – Tempos de processamento e de execução de trajetória do algoritmo A* .. 72
Tabela 4 – BUG 1 versus BUG 2: Distâncias percorridas ........................................... 73
13
LISTA DE GRÁFICOS
Gráfico 1 – BUG 1 versus BUG 2: comparação de tempos de execução nos três mapas
diferentes ...................................................................................................................... 67
Gráfico 2 – BUG 1 versus BUG 2: Distâncias percorridas até alcançar o goal ........... 69
14
SÚMARIO
RESUMO ....................................................................................................................... 6
ABSTRACT ................................................................................................................... 8
LISTA DE FIGURAS .................................................................................................. 10
LISTA DE TABELAS ................................................................................................. 12
LISTA DE GRÁFICOS ............................................................................................... 13
1- Introdução ............................................................................................................ 16
2- REVISÃO BIBLIOGRÁFICA ................................................................................ 18
2.1 Programação emC++ ......................................................................................... 18
2.2 ROS – Robot Operating System ........................................................................ 18
2.2.1 Introdução ................................................................................................... 18
2.2.2 Conceitos ..................................................................................................... 20
2.3VREP .................................................................................................................. 27
2.4 Algoritmos BUG ................................................................................................ 27
2.4.1 BUG 0 ......................................................................................................... 29
2.4.2 BUG 1 ......................................................................................................... 30
2.4.3 BUG 2 ......................................................................................................... 33
2.5Algoritmo A* (A star) ......................................................................................... 35
3 – DESENVOLVIMENTO ........................................................................................ 40
3.1 Objetivo.............................................................................................................. 40
3.2 Materiais utilizados ....................................................................................... 40
3.3 Mapas utilizados ............................................................................................ 40
3.3 Robôs utilizados e sua modelagem .................................................................... 42
3.4 Arquitetura dos robôs .................................................................................... 45
3.5 DesenvolvimentoClasse BUG ....................................................................... 48
3.6 Desenvolvimento dos algoritmos A* estrela ................................................. 50
15
3.7 Arquitetura A* estrela ................................................................................... 61
4 – RESULTADOS E DISCUSSÕES ......................................................................... 63
4.1 Simulações BUG 1 ............................................................................................. 63
4.2Simulações BUG 2 .............................................................................................. 65
4.3 RESULTADOS BUG 1 versus BUG 2 ............................................................. 66
4.4 Simulações A* (Astar) ....................................................................................... 69
4.5 RESULTADOS A*(Astar) ................................................................................ 71
5- CONCLUSÃO ......................................................................................................... 73
REFERÊNCIAS ........................................................................................................... 75
16
Capítulo 1 1- INTRODUÇÃO
Um grande desafio na Robótica é o desenvolvimento de robôs autônomos. Estes
devem ser capazes de interagir com o ambiente a sua volta e tomar decisões de forma
autônoma de forma a completar a missão para a qual foram designados. O progresso
na área de robôs autônomos é de grande interesse para uma grande variedade de
aplicações, como por exemplo, automação industrial, construção, gestão de resíduos,
exploração espacial, trabalhos submarinos, assistência a deficientes e cirurgias
médicas (LATOMBE, 2012).
Os robôs já alcançaram grande sucesso na produção industrial, podendo citar como
exemplo os braços robóticos, que movimentam uma indústria de dois bilhões de
dólares. A utilização de braço robótico é de grande eficiência para uma linha de
montagem: fixado em uma posição específica na linha de produção, o braço robótico
pode mover-se com grande velocidade e precisão, superior a precisão humana,
permitindo a viabilidade da produção, por exemplo, de celulares e notebooks, que
necessitam de uma alta precisão em sua montagem. Apesar de todo esse sucesso, no
entanto, os robôs industriais sofrem de uma grande desvantagem: a falta de
mobilidade, ou melhor, falta da capacidade de se locomover. Um braço ou
manipulador fixo apresenta um alcance de trabalho limitado pelo local onde é fixado.
Em contrapartida, um robô móvel, com capacidade de se movimentar através da
planta de produção aplicando seus talentos seria muito mais eficiente
(Siegwart&Nourbakhsh, 2004).
17
Tendo em vista essa necessidade de locomoção autônoma de um robô e seu promissor
campo de desenvolvimento, este trabalho aborda a implementação de métodos de
planejamento de trajetórias. O planejamento de trajetórias permite que o robô se
desloque de um ponto a outro, de maneira autônoma, cabendo ao usuário determinar
apenas o ponto de onde o mesmo deve partir e chegar (LATOMBE, 2012).
As primeiras pesquisas no campo de planejamento de trajetórias datam do final dos
anos 60. No entanto, maiores progressos relacionados ao planejamento de trajetórias
em robôs autônomos foram feitos a partir dos anos 80. Nos últimos anos,
conhecimentos práticos e teóricos tem surgido mais rapidamente devido ao trabalho
conjunto de pesquisadores de diferentes áreas como Inteligência Artificial, Teoria da
Computação, Matemática e Engenharia Mecânica (LATOMBE, 2012).
Existem inúmeros algoritmos que tratam do planejamento de trajetória para robôs.
Neste trabalho, foram escolhidos os algoritmos da classe Bug, a qual está inserida
dentro dos simples e intuitivos algoritmos que requerem um mínimo de
conhecimentos matemáticos para a execução e análise (Dias, 2011) e funcionam em
tempo real. Além disso, utilizou-se o algoritmo A* (Astar) para o planejamento global
como plugin do pacote nav_core do sistema operacional ROS.
Todos os algoritmos foram implementados em C++ (linguagem de programação) e,
na plataforma ROS (Robot Operating System, um framework para escrita de controle
do robô). Para efeito de validação, foi utilizado o software V-REP. Este permite a
modelagem e simulação de robôs e cenários de maneira confiável e bastante fiel à
realidade em caso de modelagens adequadas.
18
Capítulo 2 2- REVISÃO BIBLIOGRÁFICA
2.1 Programação em C++
A linguagem de programação C/C++ é utilizada no desenvolvimento de inúmeras
áreas computacionais. Desenvolvido por Bjarne Stroustrup em 1983, a linguagem
C++ foi um adicional à linguagem C. Com elementos diferentes e propostas novas
para o mundo da programação, contribuindo para o reuso, manutenção e adição ao
código, C++ possui extensas bibliotecas-padrão que utilizam em grande quantidade as
características exclusivas da linguagem em relação à C. Códigos escritos em C++ são
de fácil leitura, pois a linguagem permite separar seu código em partes e arquivos para
que seja mais bem estruturado (SANTEE, 2005).
2.2 ROS – Robot Operating System
2.2.1 Introdução
Para realização deste trabalho, foi escolhido o ROS (Robot Operating System), um
sistema meta-operacional, ou framework, que serve para o controle do robô, incluindo
os nós de controle, periféricos (sensores e atuadores) e a comunicação entre eles. No
entanto, o ROS não é considerado um sistema operacional, pois ele não pode ser
instalado diretamente em um equipamento robótico, já que o ROS necessita de um
sistema operacional para funcionar (BOHREN,2010).
19
A utilização desse framework robótico permite a aplicabilidade de abstração do
hardware, assim como, por exemplo, acontece como uso dos sistemas operacionais de
computadores (KERR & NICKELS, 2012).
O ROS permite desde a abstração da camada de hardware e controle de dispositivos
de baixo nível, até comunicação entre processos e gerenciamento de pacotes. Ele
também fornece bibliotecas e ferramentas para escrever, compilar ou executar códigos
por meio de vários computadores (ROS Wiki, 2013).
Em tempo de execução, o ROS é uma rede peer-to-peer de processos, que assim
como um “grafo”, tem seus NÓS (nodes) fracamente acoplados usando a infra-
estrutura de comunicação ROS. Embora não garante o funcionamento em tempo real,
é possível integrar o ROS a códigos em tempo real (ROS Wiki, 2013).
O principal objetivo do ROS é dar suporte ao reuso do código no campo da robótica
visando pesquisas e desenvolvimentos nessa área. As soluções desenvolvidas podem
ser agrupadas em pacotes e pilhas, que podem ser facilmente compartilhados e
distribuídos. ROS também suporta um sistema de repositórios de código, que
permitem a colaboração e a distribuição por seus usuários (ROS Wiki, 2013).
Para dar suporte a esse objetivo primário de colaboração e compartilhamento de
códigos, existem vários outros objetivos do ROS:
• Ajustável: ROS é projetado para ser facilmente ajustável possibilitando que o
código escrito para ROS possa ser usado com outros frameworks.
• Bibliotecas ROS: o modelo de desenvolvimento preferido é escrever
bibliotecas ROS com interfaces funcionais “limpas”, bem estruturadas.
20
• Independência de linguagem: o ROS é fácil de implementar em qualquer
linguagem de programação moderna, como C++ e Python.
• Escalabilidade: ROS é apropriado para grandes sistemas de tempo de
execução e de processos de desenvolvimento de grande porte (ROS Wiki,
2013).
2.2.2 Conceitos
Os conceitos básicos do ROS são Nós, Mestres, parâmetro Server,
mensagens, serviços, tópicos e Bags, os quais fornecem dados para o Grafo de
execução de diferentes maneiras. Todos os conceitos a seguir tem como referência a
documentação do ROS, disponível em (ROS Wiki, 2013).
-Nós (nodes): nós são os processos responsáveis pela execução computacional. ROS é
projetado para ser modulável em uma escala refinada, um sistema de controle do robô
normalmente compreende muitos nós. Por exemplo, um nó controla um sensor de
laser; outro nó controla os motores das rodas; um nó executa localização; outro
executa planejamento de trajetória; um nó fornece uma visão gráfica do sistema, e
assim por diante.
- Mestre (Master): O ROS Mestre (nó mestre) fornece registro e pesquisa de nome
para o resto do Grafo computacional. Sem o Mestre, os nós não seriam capazes se
encontrar, invocar serviços e trocar mensagens.
- Paremeter Server: O parâmetro Server permite que os dados sejam armazenados
por chave em um local central. É atualmente parte do Mestre.
- Mensagens: os nós se comunicam uns com os outros, por meio de mensagens. Uma
mensagem é simplesmente uma estrutura de dados, que compreende campos
21
digitados. Tipos primitivos padrão (inteiro, ponto flutuante, booleano, etc.) são
suportados, assim como estruturas em C.
- Tópicos: As mensagens são encaminhadas através de um sistema de transporte com
semântica de publicação e assinatura (publish and subscribe). Um nó envia uma
mensagem publicando-a em um determinado tópico. O tópico é um nome que é usado
para identificar o conteúdo da mensagem. Um nó que está interessado em um
determinado tipo de dados irá assinar para o tópico apropriado. Pode haver vários
publicadores e assinantes simultâneos para um único tópico, e um único nó pode
publicar e/ou assinar para vários tópicos. Em geral, os publicadores e assinantes não
estão cientes da existência uns dos outros. A ideia é dissociar a produção de
informações de seu consumo. Logicamente, pode-se pensar em um tema como um
barramento de mensagens. Cada barramento tem um nome, e qualquer um pode se
conectar ao barramento para enviar ou receber mensagens, desde que eles são o tipo
certo.
- Serviços (services): O modelo de publicação/assinatura é uma comunicação muito
flexível, mas para casos que tenham muitas requisições/respostas com interações, que
são normalmente necessários em sistemas distribuídos, se torna não muito apropriado.
A requisição de pedidos/respostas é feita através de serviços, que são definidos por
um par de estruturas de mensagem: um para o pedido e um para a resposta. Um nó
oferece um serviço a partir de um nome e um cliente utiliza o serviço enviando uma
requisição de mensagem e esperando uma resposta.
- Bags: é um formato para guardar e reproduzir dados de mensagem do ROS. O Bag é
um importante mecanismo para armazenamento de dados, tais como dados de
sensores, que podem ser difíceis de coletar, mas são necessários para desenvolver e
testar algoritmos.
22
Além da comunicação entre nós pelo nó mestre, os nós podem se conectar a outros
nós diretamente; o Mestre só fornece informações de pesquisa, bem como um
servidor DNS. Os nós que subscrevem um tópico irão solicitar conexões a partir de
nós que publicam esse tópico, e estabelecerá a conexão sobre um acordo sobre
protocolo de conexão. O protocolo mais comum utilizado em uma ROS é
chamado TCPROS, que usa sockets TCP / IP padrão.
Esta arquitetura permite a operações dissociadas, onde os nomes são os principais
meios pelos quais os sistemas maiores e mais complexos podem ser construídos. Os
nomes têm um papel muito importante na ROS: nós, tópicos, serviços, e os
parâmetros têm nomes. Cada biblioteca do ROS suporta linhas de comandos para
mudanças de nomes, o que significa que um programa compilado pode ser
configurado novamente durante a execução para operar em uma topologia de Grafo
de computação diferente.
Na figura 1 é possível ter uma simples visualização da estrutura do Grafo
Computacional com que o ROS é executado.
Figura 1 - Representação da estrutura básica do Grafo Computacional do ROS.
- O ROS Wiki: A comunidade ROS Wiki é o principal fórum para documentar
informações sobre ROS. Qualquer um pode se inscrever para uma conta e contribuir
com a sua própria documentação, fornecer correções ou atualizações, escrever
tutoriais e muito mais.
23
2.2.2.1 Navigation Stack
Navigation Stack é um conjunto de bibliotecas do ROS. Ele traz uma base pronta para
a navegação autônoma, e conta com uma arquitetura organizada e com vários
recursos, que permitem uma implementação completa de algoritmos de planejamento
de trajetórias, como o A*, de maneira mais simples, podendo, assim, aproveitar do
que já foi feito e está disponível neste pacote.
O Navigation Stack é bastante simples a nível conceitual, no entanto, aplicá-lo a um
robô arbitrário pode ser trabalhoso. Seu funcionamento se baseia na aquisição de
informações a partir da odometria e dos sensores, e, como saída, envia comandos de
velocidade para uma base móvel. Para que este pacote possa ser aplicado a um robô, é
preciso garantir alguns pontos: 1) o robô deve estar rodando ROS, 2)a pose
(translação e orientação) do veículo deve ser publicada utilizando o formato tf, e 3) o
nó de atuação do veículo deve estar à espera de uma mensagem específica. Além
disso, ele deve ser configurado de acordo com o formato e dimensões do robô para
um funcionamento adequado e confiável.
Figura 2 - Representação do funcionamento do Navigation Stack. Fonte: WikiRos O Navigation Stack presume que o robô esteja configurado da maneira padrão para
poder executar. A Figura 2 representa uma visão geral desta configuração. Os
24
componentes brancos são componentes necessários que já estão implementados no
pacote; os componentes cinzas são componentes opcionais que já estão
implementados; e os componentes azuis devem ser criados particularmente para cada
plataforma de robô que irá executar esse pacote. Os pré-requisitos do Navigation
Stack, juntamente com o método utilizado para implementá-lo no robô, serão
descritos de forma detalhada na seção 3.6.1 – Configurando Navigation Stack no
robô.
2.2.2.2 Nav_core
Nav_core é um pacote (package) do Navigation Stack que fornece interfaces comuns
para navegação com robôs. Atualmente, este pacote fornece as interfaces
BaseGlobalPlanner, BaseLocalPlanner e RecoveryBehavior, que podem ser
substituídos por códigos do usuário. Para substituir tais interfaces os planejadores
devem ser passados como plugins do nó move_base aderindo a estas interfaces
(BaseGlobalPlanner, BaseLocalPlanner e RecoveryBehavior).
Figura 3 - Representação da visão geral do pacote nav_core. Fonte: WikiRos
Pode-se ter uma visão geral do pacote nav_core com suas interfaces fundamentais
para o Navigation Stack na Figura 3, onde as elipses em azul são as interfaces
passíveisdemodificaçãopormeiodeplug-ins.
25
2.2.2.3 Move_base
O pacote move_base fornece a implementação de uma ação que, dado um destino
(goal) no cenário, o robô tentará alcançá-lo. O nó move_base une um planejador
global e um local para realizar sua tarefa de navegação. Ele suporta qualquer tipo de
planejador global aderido à interface nav_core::BaseGlobalPlanner e qualquer
planejador local, aderido à interface nav_core::BaseLocalPlanner. Ambas as
interfaces estão especificadas no pacote nav_core. O nó move_base também mantém
dois mapas de custo (costmaps), um para o planejador global e um para o planejador
local, que são usados para realizar tarefas de navegação.
O nó move_base do pacote move_base, fornece uma interface no ROS para
configurar, executar e interagir com o Navigation Stack em um robô. Uma
representação de alto nível do nó move_base e a sua interação com os outros
componentes são mostradas na Figura 2, onde as elipses azuis variam de acordo com
a plataforma do robô, as cinzas são opcionais, mas são fornecidas para todos os
sistemas, e os nós brancos são necessários e fornecidos para todos os sistemas.
2.2.2.4 Map_server
O pacote map_server fornece o nó map_server, o qual permite a passagem de dados
de um mapa por meio de um serviço do ROS (service) e o map_server, uma linha de
comando que permite que mapas gerados dinamicamente possam ser salvos em
arquivos.
Os mapas manipulados pelas ferramentas deste pacote são armazenados em dois
arquivos. O arquivo YAML que armazena a descrição de informações como um log
de marcação e um arquivo de imagem, o qual codifica os dados de ocupação quanto a
obstáculos.
26
O arquivo de imagem descreve o estado de ocupação de cada célula do cenário criado
na cor do pixel correspondente. Pixels brancos são livres, os mais escuros
representam pixels ocupados, e pixels entre estas duas cores são desconhecidos.
Quando comunicado através de mensagens do ROS, o estado de ocupação de cada
célula é representado como um número inteiro no intervalo [0,100], sendo que 0
significa totalmente livre e 100 significado completamente ocupado, o valor especial -
1 para completamente desconhecido.
2.2.2.5 TF
TF é um pacote que permite que o usuário mantenha o controle de múltiplas
coordenadas ao longo do tempo, o qual mantém a relação entre coordenadas numa
estrutura em árvore processada em tempo de execução, e permite que o usuário
transforme pontos, vetores, entre quaisquer coordenadas em qualquer ponto desejado
no tempo. O que permite um rápido e fácil acesso, além das transformações entre as
coordenadas de posições relativas em diferentes partes do robô.
Outra vantagem do uso do TF é que este pode operar num sistema distribuído, ou seja,
todas as informações sobre as coordenadas de um robô estão disponíveis para todos os
componentes do ROS, em qualquer computador que use o sistema, não sendo
necessário nenhum servidor central para transformar as informações.
2.2.2.6 Rviz
O Rviz é um visualizador de imagens 3D para o ROS. Ele permite verificar e
visualizar como o robô esta se comportando e recebendo as informações dos sensores
como lasers, câmeras ou encoders, graficamente. Dessa forma facilita a
implementação de códigos robóticos.
27
Este visualizador foi utilizado para poder verificar a trajetória gerada pelo robô laser
durante execução do algoritmo A*.
2.3 VREP
V-REP é um ambiente de simulação robótico lançado ao público em março de 2010.
Este simulador robótico caracterizado por apresentar um ambiente de simulação de
desenvolvimento integrado é baseado em uma arquitetura de controle distribuída, ou
seja, cada objeto/modelo pode ser individualmente controlado via embedded script,
ROS, remote API cliente ou ainda uma solução customizada, o que torna o VREP
muito versátil para aplicações robóticas. Os códigos para controle do robô podem
ainda ser escritos em C/C++, Python, Java, Lua, Matlab, Octave ou Urbi (V-REP
Virtual Robot Experimentation Plataform, 2013)
Este software foi então escolhido para realização das simulações com os algoritmos
de planejamento de trajetória implementados, tanto pelas características acima
citadas, quanto pela facilidade em criar os cenários de teste quanto pela existência de
uma licença gratuita para fins educacionais (V-REP Virtual Robot Experimentation
Plataform, 2013)
2.4 Algoritmos BUG
Os algoritmos da classe BUG são aqueles que se enquadram nos tipos de códigos
mais simples e intuitivos, ou seja, eles requerem apenas um mínimo de conhecimento
matemático para serem executados e analisados (Dias, 2011).
28
A tarefa para um BUG consiste no deslocamento de um robô autônomo em um mapa
com obstáculos. Ele deve se locomover de um ponto de partida até um ponto
predeterminado chamado aqui de ponto de chegada (Dias, 2011). Para este tipo de
operação não se tem conhecimento do ambiente ou dos obstáculos, sabe-se apenas os
pontos de partida e chegada no ambiente; o restante das informações deve ser
adquirido por meio de sensoriamento (CHOSET, 2015).
Os algoritmos da classe BUG são estruturados por sensores, ou seja, o robô utiliza um
sensor para se locomover e reconhecer o ambiente (obstáculos), podendo esse, por
exemplo, ser um sensor de proximidade. Além desse sensor, o robô também tem a
necessidade de um sistema de odometria, capaz de indicar sua atual posição no
ambiente (mapa). O BUG pode realizar dois movimentos padrão para essa classe de
algoritmo: se movimentar em linha reta em direção ao objetivo e contornar um
obstáculo existente no mapa. Apesar de serem algoritmos simples, eles garantem que
se existirem caminhos válidos do robô ao alvo, com certeza ele será encontrado (Dias,
2011).
Inspirado nos deslocamentos dos insetos (Bugs) o ambiente para implementação dos
Bugs pode ser bidimensionalℝ(2) ou tridimensionalℝ(3), ou infinito ou fechado e
com obstáculos inicialmente desconhecidos representados por curvas fechadas de
comprimento finito e espessuras diferentes de zero. O caminho é gerado por meio de
constantes “hitsandleaves”, ou seja, encontros e partidas de obstáculos. Sabem-se
somente os pontos globais de partida, de chegada e da posição atual com relação a
estas. Dessa forma, de maneira ideal, inicia-se a trajetória e, toda vez que o robô
encontrar um obstáculo, ele deve seguir seu perímetro até encontrar um caminho livre
29
em direção ao ponto de chegada novamente, como visto na Figura 4 (CHOSET,
2015).
Figura 4 - Exemplo genérico de uma trajetória utilizando o algoritmo BUG (CHOSET, 2015)
Os algoritmos Bug mais conhecidos são o Bug 0, Bug1, Bug2 e Tangent Bug (Dias,
2011). Neste trabalho serão implementados os Bugs 1 e 2.
2.4.1 BUG 0
Para o caso específico do BUG0 (zero), seu algoritmo é muito simples. Ele se baseia
em traçar uma linha reta do ponto de partida em direção ao ponto de chegada, e dar
início a trajetória. Toda vez que o robô encontrar um obstáculo, ele deve seguir seu
perímetro até encontrar a linha traçada novamente, devendo seguir em direção ao
ponto de chegada (Dias, 2011).
Porém, o BUG0 apresenta deficiência de memória. Ele não apresenta implementação
para guardar a posição de onde deixou quando se depara com o obstáculo ou quando
chega a um novo, ou seja, ele pode retornar a trajetória em inúmeros cenários,
resultando em um caminho falho ou ausência de caminho entre ponto de partida e
ponto de chegada (CHOSET, 2015).
30
Um esboço simples do algoritmo seria (CHOSET, 2015):
Ø Vá até o ponto de chegada.
Ø Ao encontrar um obstáculo vire a esquerda ou direita e circunde-o até
conseguir seguir até o objetivo novamente.
Ø Continue.
Figura 5 - Exemplo de execução de trajetória de um robô utilizando o algoritmo BUG 0, resultando em um caminho falho para encontrar o ponto de chegada.
Dessa forma, este algoritmo nem sempre irá retornar um caminho possível devido às
razões acima apontadas, falhando em inúmeras ocasiões como, por exemplo, a
situação do cenário da Figura 5 (CHOSET, 2015).
2.4.2 BUG 1
O algoritmo BUG1 foi detalhado por Stepanov em 1987 e foi o primeiro algoritmo
desta categoria a ser desenvolvido (COSTA, 2011). Ele foi desenvolvido com o
intuito de suprir as falhas do Bug 0. Esse método apresenta uma espécie de
“memória” para garantir que o ponto de chegada seja alcançado. Assim, toma-se o
cuidado de armazenar os pontos de chegada em cada obstáculo (Hin) e partida (Hout)
(CHOSET, 2015).
Chegada
Partida
Chegada
Partida
31
Seu funcionamento dá-se da seguinte forma: o robô deve sair do ponto de partida e
mover-se em direção ao ponto de chegada, sempre que encontrar um obstáculo deve
armazenar essa posição como (Hin) e circunavegar o obstáculo enquanto armazena
como Hout sempre o ponto com menor distância entre a localização atual e o ponto de
objetivo. Ao terminar a circunavegação, quando reencontrar o ponto (Hin), o robô
deve mover-se novamente até o ponto Hout (de menor distância), circunavegando o
obstáculo e então partir deste e mover-se em direção ao ponto de chegada (CHOSET,
2015).
Um esboço simples do algoritmo seria:
Ø Vá até o ponto de chegada.
Ø Caso um obstáculo seja encontrado circumnavegue e lembre-se do
ponto mais próximo do objetivo que foi obtido.
Ø Retorne para o ponto mais próximo seguindo o obstáculo atual e seguir
até o ponto de chegada.
Um esboço do algoritmo mais detalhado seria (PLAKU):
• (Hout)0= inicial point; i=1;
• Loop:
• Repeat: Mova-se em linha reta de Houti-1 até ponto de chegada.
• Untill: ponto de chegada alcançado ou obstáculo encontrado em Hini.
• If: Ponto de chegada alcançado, then: EXIT com sucesso.
• Repeat: Circunavegue o obstáculo armazenando como Houti o ponto de
menor distância entre a posição atual e o ponto de chegada.
• Untill: Ponto de chegada alcançado ou Hini encontrado novamente.
32
• If: Ponto de chegada encontrado, then:EXIT com sucesso.
• Circunavegue o obstáculo de Hini até Houti pela menor rota
• If: mova-se em linha reta a partir de Houti até o ponto de chegada
encontrar um obstáculo, then: EXIT com falha.
• Else: i=i+1.
Na Figura 6 é mostrado um exemplo da implementação do algoritmo BUG 2.
Figura 6- Exemplo de trajetória para robô utilizando o algoritmo BUG 2 (CHOSET, 2015)
Pode-se notar que o robô quando se depara com um obstáculo necessariamente
percorre por todo o perímetro do mesmo, e, ao chegar num ponto em que ele
encontrou o obstáculo, ele retorna contornando-o para, enfim, encontrar o ponto de
menor distância entre sua posição e seu ponto de chegada e só então dá continuidade
para o seu trajeto (COSTA, 2011).
Para os casos e cenários abordados neste trabalho para os bugs, iremos assumir as
seguintes premissas: iremos tratar apenas de cenários bidimensionais, cada obstáculo
será tratado como uma curva fechada de comprimento finito e espessura diferente de
zero, uma linha reta cruza um obstáculo em um número finito de vezes, os obstáculos
não se tocam, numero de obstáculos finitos, localmente, e posições iniciais, finais e
atuais serão sempre conhecidas (CHOSET, 2015).
33
Podemos então estimar o melhor e pior cenário para o percurso necessário para
alcançar o ponto de chegada. Sendo D a distância da linha reta do ponto de partida ao
ponto de chegada e Pi os perímetros dos i obstáculos encontrados, tem-se que o
melhor trajeto possível será D (distância em linha reta do ponto de partida até a
chegada) e o pior trajeto será [D+1,5*Sum(Pi)], como ilustrado na Figura 7
(PLAKU).
Figura 7–Representação do melhor trajeto (menor distância)
2.4.3 BUG 2
Com a finalidade de melhorar o custo computacional e continuar com as vantagens do
Bug 1, foi desenvolvido o Bug 2, o qual tem como principal característica a
determinação de uma linha reta (m-line) que liga o ponto de partida ao ponto de
chegada. O robô deve seguir essa linha até encontrar um obstáculo, então conforme
determinação prévia o mesmo deve virar à esquerda ou à direta e continuar
circunavegando o obstáculo até encontrar a linha novamente (o ponto da linha que
transpassa o obstáculo chegando ao lado contrário do ponto de chegada no obstáculo)
e assim sucessivamente, até encontrar o ponto de chegada, conforme ilustrado na
Figura 8 (CHOSET, 2015).
34
Figura 8–Representação do funcionamento do BUG 2 (CHOSET, 2015)
Um esboço para o algoritmo Bug 2 seria:
1. Vá até o ponto de chegada através da “m-line”.
2. Caso um obstáculo seja detectado, contorne-o até encontrar a “m-line”
novamente no ponto mais próximo do ponto de chegada.
3. Deixe o obstáculo e continue até o ponto de chegada.
Um esboço mais detalhado do algoritmo seria:
• (Hout)0= inicial point; i=1;
• Loop:
• Repeat: Mova-se em linha reta de Houti-1 até ponto de chegada.
• Untill: ponto de chegada alcançado ou obstáculo encontrado em Hini.
• If: Ponto de chegada alcançado, then: EXIT com sucesso.
• Repeat: Circunavegue o obstáculo.
• Untill:
a. Ponto de chegada alcançado ou
b. m-liner encontrada em Q tal que Q != Hinie d(Q,Goal)<d(Hini,
Goal) ou
c. Hini encontrado novamente.
35
• If: Ponto de chegada encontrado, then:EXIT com sucesso.
• ElseIf:Hini encontrado, then: EXIT com falha.
• Else: Houti= Q, i=i+1. (CHOSET, 2015)
Verificamos aqui que o Bug2 é um algoritmo mais voraz que o Bug1, pois age de
maneira mais rápida que seu predecessor, sempre que encontra a m-line parte para em
direção ao Goal, o que confere a ele uma maior agilidade na resolução de muitos
casos com um menor trajeto necessário, porém para alguns casos isso não se verifica.
Na parte de resultados e discussões exemplificaremos estes casos limites com a
comparação entre os diferentes algoritmos apresentados (CHOSET, 2015).
2.5 Algoritmo A* (A star)
O algoritmo A* é um algoritmo que faz uso de heurística, algoritmos que usam de
informações para escolherem a sequência de pesquisa (com mapa conhecido). Para
ser planejar o melhor caminho, o algoritmo utiliza além das informações dos nós ao
seu redor, a distância que falta para chegar ao seu destino. “O algoritmo é completo,
ótimo e a complexidade de tempo e de espaço depende da heurística, principalmente
da qualidade da função heurística” (COSTA, 2011).
O algoritmo A* é um algoritmo que foi descrito pela primeira vez por Peter Hart, Nils
Nilsson e Bertram Raphael, em 1968. Seu funcionamento consiste em procurar, em
um mapa de grafos, o melhor caminho, entre o nó inicial e o nó de chegada, através
de cálculos por meio de uma função heurística f(n). Esta, por sua vez, é a soma de
duas funções: g(n) e h(n). A função g(n) é uma função que representa o custo
necessário para ir do ponto inicial até o ponto n que está sendo calculado. Enquanto a
função h(n) é uma função heurística que faz a estimativa do custo de trajetória a partir
36
do ponto n até o ponto de chegada. Utilizando da função heurística f(n) para explorar
o mapa e alcançar o ponto de chegada pelo melhor caminho, sempre é escolhida uma
das oito células (grafos) ao redor da célula atual (COSTA, 2011).
O pseudocódigo para o algoritmo A* pode ser:
• Para cada nó n no grafo, f(n) = infinito e g(n) = infinito.
• Criar lista aberta e lista fechada.
• g(início) = 0 e f(início)= h(início), adicionar início à lista aberta.
• Enquanto lista não está vazia:
o Faça atual = nó da lista com o menor f(n), remova-o da lista
aberta e adicione-o à lista fechada.
o Se atual = destino, saia com sucesso.
o Para cada nó n adjacente ao nó atual:
§ Se g(n) > g(atual) + custo de locomoção do atual até n e
n não esta na lista fechada:
§ g(n) = g(atual) + custo de locomoção do atual até n
§ f(n) = g(n) + h(n)
§ n(pai) = atual
§ Adicionar n à lista aberta se ele ainda não estiver nela.
Assim, o funcionamento do A* pode ser explicado da seguinte forma: partindo-se do
nó inicial, calcula-se o seu f(inicial) e coloca-se esse nó em uma lista aberta. Escolhe-
se o nó n da lista aberta cuja função f(n) tem o menor valor (menor custo). Este nó é
então removido da lista aberta, por ser considerado já analisado, e adicionado à lista
fechada, que contém todos os nós já processados. A partir de então se analisam todos
os nós adjacentes (nós que estão diretamente ligados ao nó atual): caso o nó adjacente
37
não pertença à lista fechada, seu valor f(n) é calculado e, caso ainda não pertença à
lista aberta, lá ele é inserido, e se já pertencer, seu valor é atualizado e modifica-se o
pai do nó. Caso o nó já esteja na lista fechada, nada é feito para este nó (COSTA,
2011).
A trajetória resultante é encontrada começando com o nó final e a partir dele vê-se
qual é o seu pai. Em seguida verifica-se nesse nó o seu Pai e assim sucessivamente até
se chegar ao nó inicial. Este algoritmo, tal como está apresentado, tem uma boa
eficiência, pois, com a utilização da lista fechada, o algoritmo previne que não se
visite o mesmo nó várias vezes (COSTA, 2011).
Para ilustrar seu funcionamento, pode-se demonstrar com as figuras a seguir, onde, na
figura 9, se tem um mapa em que a posição de início está representada pela célula em
verde e a posição de chegada em amarelo.
Figura 9 - Ambiente para o Exemplo do Algoritmo A*.Célula em verde determina a origem e em amarelo o destino, as células pretas são obstáculos.
Durante a primeira iteração a célula inicial é colocada na lista aberta e todas as células
vizinhas da inicial são visitadas e tem seus valores de G, H e F calculados, conforme
ilustrado na figura 10. Está célula (inicial) é então considerada já visitada e é retirada
da lista aberta e adicionada a lista fechada. Após serem visitadas, estas são incluídas
na lista aberta e dentre elas aquela com menor valor de F é escolhida e colocada na
38
lista fechada. Todas as células vizinhas são atribuídas como filhas da célula
predecessor, a partir da qual tiveram seu valor de G calculado.
Figura 10 - Primeira iteração - Valores de G em preto, valores de H em vermelho e F em branco. Todos os
quadrados em azul indicam que foram visitados e incluídos na lista aberta. O quadrado com F igual a 4 será o
escolhido por apresentar o menor F e será incluído n
Durante a segunda iteração os quadrados vizinhos da célula com menor F (que está
em vermelho), são então visitados, tem seus valores de G, F, H calculados e são
colocadas na lista aberta (azul) e aquela com menor valor de F é colocada na lista
fechada, (ficará em vermelho na próxima iteração), conforme mostrado na figura 11,
seus vizinhos serão visitados e colocados na lista vazia e assim por diante.
Figura 11 - Segunda iteração –Quadrados vizinhos do que está, em vermelho, são visitados e os valores de G, F, H
calculado, estas são colocadas na lista aberta (Azul) e aquela com menor valor é colocada na lista fechada, (ficará
em vermelho na próxima iteração)
39
Ao fim das iterações, quando encontra-se a célula de destino ou quando a lista aberta
esta vazia, o caminho é encontrado, retomando os pais de cada célula a partir da
célula de destino até a célula de partida. A trajetória é então concluída, como
mostrado na figura 12.
Figura 12 - Figura final – Células em cinza determinam o caminho encontrado, células em vermelho são as que
foram colocadas na lista fechada e azuis as que estão na lista aberta.
40
Capítulo 3 3 – DESENVOLVIMENTO
3.1 Objetivo
Este trabalho teve como objetivo desenvolver, implementar e comparar os diferentes
algoritmos de navegação para o planejamento de trajetórias de robôs autônomos
utilizando a plataforma ROS (Robotic Operating System).
Foram abordados os algoritmos BUG 1 e BUG 2, A* (A star), utilizando a linguagem
de código C++. Para a simulação do funcionamento do robô, foi utilizado o software
VREP (Virtual Robot Experimentation Plataform) em plataforma Linux.
3.2 Materiais utilizados
Para este trabalho foram utilizados os seguintes materiais e softwares:
ü Computador marca SONY VAIO, modelo VGN-FW560F, 2009. Processador
Intel Core 2 Duo CPU P7450 2.13 GHz. RAM 6,0 GB.
ü Sistema Operacional ubuntu 14.04 LTS. 64-bit.
ü V-REP PLAYER, Version 3.3.1 (ver. 1) 64bit.
ü ROS Jade, Version 1.11.16
3.3 Mapas utilizados
Para simulação dos algoritmos estudados neste trabalho, foram escolhidos seis
ambientes (mapas) no VREP. Destes, três foram usados para simulação dos
algoritmos Bug1 e Bug2 e outros três para simulação do A*(A star). O modelo para
41
construção destes mapas estava previamente estruturado com alguns obstáculos.
Tanto para os Bugs, quanto para o A* (Astar), os mapas possuem dimensão
10mx15m. Os mapas estão representados na Figuras13 e 14.
Figura 13 - Mapas de simulação para algoritmos Bugs no simulador VREP
Figura 14 - Mapas de simulação para algoritmo A* no simulador VREP
42
3.3 Robôs utilizados e sua modelagem
Para o desenvolvimento e teste dos algoritmos no V-rep foram utilizados dois robôs.
Ambos apresentam a mesma estrutura e princípio de locomoção, diferindo apenas nos
sensores presentes. Quanto à estrutura, são quadrados, com duas rodas, e apresentam
motores e acionamentos independentes, conferindo a eles capacidade de manobrar.
Quanto aos sensores, o primeiro, escolhido para a classe BUG, será chamado de robô
sonar (figura 15.a). Ele apresenta três sensores de proximidade do tipo ultrassom na
parte frontal do robô. O segundo, escolhido para implementação e teste do algoritmo
de planejamento de trajetória A*, chamado de robô laser (figura 15.b), apresenta um
único sensor a laser (Negri, Rodrigues, & Becker, 2016). Os robôs são apresentados
na figura 15.
3.3.1 Modelagem cinemática do robô e nó kinecontroller
Para a modelagem cinemática dos robôs, como ambos apresentam a mesma forma,
estrutura e princípio de locomoção, diferindo apenas nos sensores, os mesmos podem
ser representados pela modelagem descrita a seguir:
Figura 15 - Robôs utilizados para simulação dos algoritmos. a) robô sonar; b) robô laser
a b
43
Para que o robô possa se mover no mapa, é necessário que o sistema de controle envie
velocidades angulares para as rodas, de maneira a movimentar e direcionar o robô
para as posições desejadas, com as velocidades escalares desejadas. Além disso, essa
modelagem garante que o robô consiga manobrar ao longo do mapa, uma vez que, a
mudança de direção e “manobrabilidade” do robô, serão feitas utilizando-se os dois
motores independentes em cada roda por meio do envio de velocidades angulares
diferentes para cada uma delas.
3.3.1.1 Modelagem Cinemática
Para realizar esta modelagem do acionamento descrito, tanto para o robô sonar quanto
para o laser, usou-se o modelo que pode ser visto na Figura 16.
Figura 16 - Representação do robô e velocidades
Na figura16, tem-se as seguintes variáveis: Wf – velocidade angular passada ao robô
com relação a sua base; Vf – velocidade linear passada ao robô com relação a sua
base; Vr1 – velocidade linear da roda direita; Vr2 – velocidade linear da roda esquerda
do robô; b - largura do robô. Acrescenta-se a essas variáveis a variável r – raio de
44
cada roda do robô; Wr1 – velocidade angular da roda direita do robô; Wr2 – velocidade
angular da roda esquerda do robô.
Temos então que a velocidade resultante linear Vf com relação a base do robô será
igual a média entre as velocidades lineares de cada uma das rodas do robô 𝑉!! e 𝑉!!,
conforme demonstrado na equação 1. Temos também que a velocidade angular
resultante com relação à base do robô 𝑊!, será igual a diferença entre as velocidades
lineares de cada roda, dividido pela distância entre eixos, aqui tomada como a largura
do robô (b), conforme ilustrado na equação 2.
𝑉! =𝑉!! + 𝑉!!
2 [1]
𝑊! =𝑉!! − 𝑉!!
𝑏 [2]
Temos também que:
𝑉!! = 𝑤!! ∗ 𝑟 [3]
𝑉!! = 𝑤!! ∗ 𝑟 [4]
Assim:
𝑉!𝑊!
= 1/2 1/21/𝑏 −1/𝑏
𝑉!!𝑉!!
[5]
Podemos representar a equação [5] da seguinte forma:
𝑉!" = 𝐴 ∗ 𝑉!" [6]
Onde A representa a matriz 2x2 da equação [5], 𝑉!" a matriz das velocidades com
relação a base 𝑉!" a matriz de velocidades com relação as rodas.
Para que se possa calcular as velocidades 𝑉!! e 𝑉!! necessária para um determinado
𝑉! e 𝑊! faz-se:
45
𝐴!! ∗ 𝑉!" = 𝐴!! ∗ 𝐴 ∗ 𝑉!" [7]
𝐴!! ∗ 𝑉!" = 𝐼 ∗ 𝑉!! [8]
𝑉!" = 𝐴!! ∗ 𝑉!" [9]
Então:
𝑉!!𝑉!!
= 1/2 1/21/𝑏 −1/𝑏
!! 𝑉!𝑊!
[10]
A equação 10 é válida quando A não singular, ou seja, det A ≠0, o que pode-se
verificar facilmente que sempre ocorrerá, pois det A = − !!!− !
!!= − !
!!, e b igual a
largura entre eixos/largura do robô.
3.3.1.2 KINECONTROLLER
Para colocar em código a modelagem cinemática, foi criado o nó
KINECONTROLLER, o qual transforma a velocidade passada no tópico
/cmd_vel,em função da base do robô, para as velocidades angulares publicadas em
cada uma das rodas.
O nó /kinecontroler foi implementado no arquivo kinecontroller.cpp, o qual
assina/subscreve no tópico /cmd_vel, e transforma a velocidade, de acordo como foi
descrito na modelagem cinemática. Assim, as velocidades que devem ser passadas às
rodas do robô, são calculadas e enviadas através dos tópicos que acionam as rodas
/vrep/vehicle/LeftMotor e /vrep/vehicle/RightMotor.
3.4 Arquitetura dos robôs
Ambos os robôs são representados na arquitetura ROS pelo nó /vrep. O nó /vrep é
passado pelo programa VREP para o ROS por meio de uma configuração que não foi
implementada neste trabalho. O VREP permite que se configure o robô por meio de
46
um arquivo script no programa. Uma vez que se fez a integração do ROS com o
Vrep,por meio do V-REP RosPlugin, o ROS passa a enxergar o VREP como o nó
/vrep.
3.4.1 Robô sonar
O robô sonar foi implementado junto ao VREP por meio de um Script (documento no
VREP com códigos para o robô, o qual já estava implementado). Este documento
contém drivers para os sensores sonar, para a odometria e para os motores de cada
roda. Todas essas funcionalidades são disponibilizadas ao ROS por meio do nó /vrep,
o qual permite que sejam acessadas para receber informações ou atuadas usando os
algoritmos desenvolvidos.
O nó /vrep apresenta os principais tópicos utilizados:
- /vrep/vehicle/motorLeftSpeed
o Pode ser publicada a velocidade no formato [std_msgs/float32]
o Usado pelo nó /amr_kine_controller
- /vrep/vehicle/motorRightSpeed
o Pode ser publicada a velocidade no formato [std_msgs/float32]
o Usado pelo nó /amr_kine_controller
- /vrep/vehicle/leftSonar
o Pode ser adquirida a leitura do sonar no formato [std_msgs/float32]
o Usado pelo nó /bug
- /vrep/vehicle/RighttSonar
o Pode ser adquirida a leitura do sonar no formato [std_msgs/float32]
o Usado pelo nó /bug
- /vrep/vehicle/FrontSonar
47
o Pode ser adquirida a leitura do sonar no formato [std_msgs/float32]
o Usado pelo nó /bug
- /vrep/vehicle/odometry
o Pode ser adquirida a leitura da posição do robô (odometria) no formato
[nav_msgs/Odometry]
o Usado pelo nó /bug
- /tf
o Permite adquirir informações de diferentes coordenadas ao longo do
tempo [tf2_msgs/TFMessage]
o Não usado nesse robô, porém presente.
3.4.2 Robô laser
Assim como o robô sonar, o robô laser foi implementado junto ao Vrep por meio de
um Script (o qual já estava configurado). A única diferença entre eles é que, ao invés
dos sensores de ultrassom, o robô sonar apresenta um único sensor laser. O driver
laser utilizado foi o Hokuyo Modelo 04LX, 30lx - urg_node. Todas as
funcionalidades são disponibilizadas ao ROS por meio do nó /vrep.
O nó /vrep apresenta os principais tópicos utilizados seguintes tópicos:
- /vrep/vehicle/motorLeftSpeed
o Pode ser publicada a velocidade no formato [std_msgs/float32]
o Usado pelo nó /amr_kine_controller
- /vrep/vehicle/motorRightSpeed
o Pode ser publicada a velocidade no formato [std_msgs/float32]
o Usado pelo nó /amr_kine_controller
- /vrep/vehicle/scan
o Pode ser adquirida a leitura do laser no formato [std_msgs/float32]
48
o Usado pelo nó /move_base
- /vrep/vehicle/odometry
o Pode ser adquirida a leitura da posição do robô (odometria) no formato
[nav_msgs/Odometry]
o Usado pelos nós /rviz e /move_base
- /tf
o Permite adquirir informações de diferentes coordenadas ao longo do
tempo [tf2_msgs/TFMessage]
o Usado pelo nó /move_base e /rviz
3.5 Desenvolvimento Classe BUG
Para simulação dos algoritmos da classe BUG foi escolhido o robô sonar, conforme
descrito anteriormente e ilustrado na Figura 15.a.
Para implementação dos algoritmos Bug1 e Bug 2, além do nó /vrep, usou-se o nó
kinecontroler para ajustar a velocidade, e um nó responsável pela lógica do controle
de trajetória, bug_node.
3.5.1 Implementação do Bug Node
O bug_node tem como função criar os objetos das classes Bug1 e Bug2, gerenciando
e trabalhando com os nós /vrep e / kinecontrolerdo ROS. Por sua vez, os códigos que
possuem a lógica sequencial para os Bugs, permanecem nos arquivos Bug1.cpp e
Bug2.cpp com sua respectivas bibliotecas .h.
49
O bug_node “assina” (subscribe) aos três sensores sonares do robô(tópico
/vrep/vehicle/...Sonar) e à odometria(tópico /vrep/vehicle/odometry) do robô passados
pelo nó /vrep.Então um objeto do tipo Bug1 ou Bug2 é criado para lidar com a lógica
da melhor trajetória epublica a velocidade que deve ser executada pelo robô no tópico
/cmd_vel. Este tópico /cmd_vel será assinado pelo nó /kinecontroler, o qual ira
transformar essa velocidade da base do robô em velocidade para cada roda.
3.5.2 Implementação dos Bugs
Ambos os Bugs foram desenvolvidos seguindo a lógica dos pseudocódigos
apresentados na revisão bibliográfica. Devido às suas simplicidades de
implementação não há muito que citar quanto aos seus desenvolvimentos, portanto os
códigos serão apresentados ao final deste trabalho.
3.5.3 Arquitetura da classe Bug
Pode-se visualizar na Figura 17, a interface do grafo de execução da classe Bug.
Figura 17- Interface do grafo de execução da classe BUG.
Conforme a Figura 11, o nó /bug publica a velocidade adquirida, por meio do código
Bug1 ou Bug2, para o controle da trajetória através do tópico /cmd_vel. Esta
50
velocidade é publicada no nó /kinecontroller, o qual processa a velocidade e a
transformação cinemática, publicando-a no nó /vrep por meio dos tópicos
/vrep/vehicle/motorLeftSpeed e /vrep/vehicle/motoRightSpeed. O nó /bug também
“assina” (subscribe) ao nó /vrep nos tópicos /vrep/vehicle/rightSonar,
/vrep/vehicle/leftSonar, /vrep/vehicle/frontSonar e /vrep/vehicle/odometry, os quais
são usados nos códigos Bugs para as lógicas de controle da trajetória.
3.6 Desenvolvimento dos algoritmos A* estrela
Para simulação dos algoritmos A*, foi escolhido o robô laser, conforme descrito
anteriormente e ilustrado na Figura 15.b.
Para poder navegar de forma autônoma, um robô precisa de um mapa, de um módulo
de localização e de um módulo de planejamento de trajetória. Para alcançar tais
funcionalidades, foi escolhido trabalhar com o Navigation Stack. O Navigation Stack
trata-se de um pacote que funciona conforme descrito na seção da revisão
bibliográfica (2.2.2.1 Navigation Stack).
Para que o pacote Navigation Stack pudesse ser utilizado corretamente, foi necessário
preparar o robô laser para recebê-lo, conforme descrito na sessão 3.6.1 Configurando
Navigation Stack no robô.
Todas essas necessidades foram sanadas usando o Navigation Stack e usando os
métodos a partir daqui descritos. É importante ressaltar que, por se tratar de um robô
simulado no ambiente VREP, o módulo de localização, como por exemplo AMCL,
pôde ser suprimido da implementação, uma vez que, o simulador já disponibiliza
essas informações.
51
3.6.1 Configurando Navigation Stack no robô
Dentre os requisitos para que se pudesse utilizar o Navigation Stack no robô laser
temos:
o Garantir que o robô esteja rodando ROS.
o Garantir que todos os sensores do robô, no caso, o sensor laser, estivessem
transmitindo a mensagem de maneira adequada à configuração do pacote
(sensor_msgs/LaserScan). Este requisito foi atendido pelo script do robô em
sua implementação no simulador VREP, o qual já estava configurado.
o Garantir que o robô possuísse um nó capaz de transformar uma mensagem de
velocidade enviada pelo nó de planejamento do pacote Navigation Stack,
publicado sobre o tópico /cmd_vel na base do robô em (x, vy, vtheta) <==>
(cmd_vel.linear.x, cmd_vel.linear.y, cmd_vel.angular.z) para os motores
independentes em cada roda. Esse requisito foi cumprido implementando o
kinecontroler, que utiliza os princípios da modelagem cinemática para atuar.
o Garantir que a odometria do robô estivesse sendo acessada e publicada,
usando /tf e /nav_msgs/odometry. Este requisito foi suprido pelo script do
robô em sua implementação no simulador VREP, o qual já estava
configurado.
o Ter um mapa usando map_server, um nó que fornece os dados do mapa como
um serviço (Service) do ROS. Ele também fornece o map_saver,um utilitário
de linha de comando, que permite gerar dinamicamente mapas para serem
salvos em arquivo (bag). Este requisito foi atendido caminhando com o robô
pelo mapa e usando o map_saver para salvar as informações sobre o mapa
nos tópicos /scan, /odom e /tf. Depois de terminado, gerou-se uma imagem
52
com a planta do mapa e um arquivo com informações como um log de
marcação.
Após garantir que todos os requisitos foram atendidos, foi necessário ajustar o
Navigation Stack para funcionar com o robô laser. Para isso utilizou-se um tutorial no
ROS que pode ser acessado em http://wiki.ros.org/navigation/Tutorials/RobotSetup.
Seguindo este tutorial, criou-se o Pacote amr__2dnav no computador para armazenar
toda a configuração e lançar os arquivos para o Navigation Stack. Esta pasta contém
dependências de todos os pacotes necessários para cumprir os requisitos do programa
de configuração do robô e do pacote move_base, o qual contém a interface de alto
nível para o Navigation Stack. Dentre os arquivos que tiveram que ser criados dentro
do amr__2dnav estão CMakelist.txt, move_base.launch, package.xml,
base_global_planner_params .yaml, base_local_planner_params.yaml,
costmap_common_params.yaml, global_costmap_params.yaml,
local_costmap_params.yaml e move_base_params.yaml.
3.3.1.3 Configurando move_base.launch
O arquivo launch file (move_base.launch) traz à tona todos os nós do robô e configura
os parâmetros para que o Navigation Stack possa trabalhar corretamente.É mostrado
na Figura 18 o módulo pai de planejamento de trajetória.
Figura 18 – Arquivo move_base.launch: pai de planejamento de trajetória
53
Neste arquivo da figura 18, temos o move_base.launch, onde definiu-se o parâmetro
use_sim_time = true, que permite a utilização do tempo por meio do tópico /clock do
ROS, para contabilizar o tempo durante a simulação. Declarou-se o nó map_server
que é responsável por lidar com as informações sobre o mapa utilizado para o
planejamento da trajetória. Na parte param name = “base_global_planner” value=
“Astar_planner/...” estamos declarando que, ao invés de utilizar o planejador global
padrão do Navigation Stack, deve-se usar o algoritimo astarPlanner A* desenvolvido
neste trabalho. É também incluído o nó Kinecontroller, responsável por transformar a
velocidade linear passada pelo move_base em velocidade angular para as rodas, o nó
move_base, com os parâmetros necessários, e o nó rviz, responsável pela visualização
gráfica do mapa bem como suas respectivas localizações no computador (file= “$find(
...)).
3.3.1.4 Configurando costmaps
Foram configurados dois mapas de custo (Costmaps) para que os algoritmos de
planejamento de trajetória pudessem acessar os custos para poderem calcular as suas
trajetórias. O primeiro, chamado local_costmap, foi configurado para o planejamento
de trajetórias locais. O segundo, chamado global_costmap, para o planejamento de
trajetetórias globais. Para configurar os mapas de custo, primeiro foi necessário criar
o mapa em um formato que pudesse ser utilizado pelo Navigation Stack, a partir do
map_server. Então, para criar tal arquivo, usou-se o comando “rosbagrecord -O
mylaserdata /scan /tf”) e moveu-se o robô ao longo do mapa usando o Joystick do
teclado. Dessa forma, todo o mapa pode ser varrido pelo sensor, gerando um arquivo
contendo as informações das leituras do laser sobre o mapa (um Bag). Após
54
armazenar essas informações no Bag, usou-se o pacote slam_gmmaping para criar um
mapa a partir das informações do laser_scan. Após a criação do arquivo do mapa, foi
configurado os arquivos referentes aos mapas de custo (costmaps), mostrados nas
figuras 19, 20 e 21.
Figura 19–Arquivo local_costmap_params.yaml
Figura 20 - Arquivo global_costmap_params.yaml
Figura 21 - Arquivo costmap_common_params
55
Os principais parâmetros são: o global_frame, referente ao nome do mapa utilizado no
VREP, chamado world; o robot_base_frame, referente ao nome da base do robô no
VREP (AMR); Widht e Height referentes ao tamanho do costmap quanto à largura e
altura; resolution, referente a dimensão de cada célula de custo em metros;
Transform_tolerance, referente ao atraso na transformação de dados (TF) que é
tolerável em segundos; rolling_window referente a como o robô irá representar seus
arredores. No arquivo commom_params.yaml, temos o FootPrint, que são as
coordenadas que delimitam o tamanho do robô tendo como base o seu centro. A
configuração e a habilitação do obstaclelayer permitem a detecção de obstáculos e
remoção destes durante execução do programa para o uso do local_planner. A
configuração e a habilitação do inflation_layer permitemo cálculo do mapa de custos,
levando-se em conta a geometria do robô. E por fim, a confiruração e a habilitação do
static_layer, permitem a utilização do mapa estático para o global_planner.
3.3.1.5 Configurando base_local_planner
Para configurar o base_local_planner criou-se o arquivo
base_local_planner_params.yaml com os parâmetros mostrados na figura 22.
Figura 22 – Arquivo base_local_planner_params.yaml
56
Os principais parâmetros são max_vel e min_vel que determinam as máximas e
mínimas velocidades permitidas para o robô; acc_lim que determinam as máximas
acelerações em cada coordenada; meter_scoring em false permite o uso dos custos
para determinar qual a melhor das trajetórias geradas baseadas em células ao invés de
metros; pdist_scale determina o peso para quanto o planejador deve ficar próximo do
caminho que foi dado; gdist_scalescale determina o peso para quanto o planejador
deve tentar alcançar o caminho dado; occ_dist_scale determina o peso para quanto o
controlador deve evitar obstáculos; heading_scoring em false determina que o
planejador não deve tentar prever a trajetória, mas se basear na distância atual do robô
ao longo do caminho; publish_cost_grid determina se deve-se ou não publicar os
custos do caminho que o robô esta calculando; sim_time determina o tempo usado
para simular as trajetórias futuras; heading_lookahead determina o quanto olhar para
frente ao calcular trajetórias com rotações; oscilation_reset_dist determina o quanto o
robô deve andar para que o flag de oscilação seja resetado; sim_time determina o
tempo para avançar na simulação de trajetórias em segundos; e, por fim,dwa em false
indicando não irá se usar este tipo de planejador, usando o Trajectory Rollout.
3.6.1.1 Configurando move_base
Para configurar o move_base criou-se o arquivo move_base_params.yaml com os
parâmetros mostrados na figura 23.
Figura 23 - Arquivo move_base_params.yaml
57
Dessa forma, com todos os componentes do Navigation Stack configurados, com os
parâmetros e as características específicas do robô laser, bastou-se implementar os
algoritmos A* estrela e potencial fields como plug-ins, substituindo os arquivos
padrão para o global planner do Navigation Stack.
3.6.2 Implementação do algoritmo A* estrela
Para implementação do algoritmo A* como um planejador global do Navigation
Stack, inicialmente, realizou-se um curso sobre planejamento de trajetórias robóticas
no Pnncoursera e desenvolveu-se o algoritmo em Matlab para maior familiarização
com a escrita do código.Após essa implementação bastou-se transferir o
conhecimento adquirido para o ROS, conforme descrito no pseudo-código da seção
2.5.
Para implementar este algoritmo, teve-se que sobrescrever os métodos da classe de
planejamento de trajetória global, na interface nav_core::BaseGlobalPlanner,
definida no pacote nav_core do Navigation Stack. Após escrever-se o código teve-se
que adcioná-lo como um plugin do ROS, permitindo que fosse usado com o
move_base do Navigation Stack.
Para essa implementação precisou-se incluir as mesmas bibliotecas do ROS
necessárias para o path planner padrão do Navigation Stack:
<costmap_2d/costmap_2d_ros.h> e <costmap_2d/costmap_2d.h>. Estas são
necessárias para o uso do costmap_2d::Costmap2D que irá ser usado pelo A* como o
mapa de input. Este mapa sera acessado automaticamente pela classe do path planner
quando este é definido como um plugin. Dessa forma, não é necessário que se
subescreva ao costmap2d para acessar o mapa de custo.
58
Assim, a biblioteca <nav_core/base_global_planner.h> é usada para importar a
interface nav_core::BaseGlobalPlanner ao qual o plugin deve aderir.
Definiu-se o namespace da classe como Rastar_planner para a classe astarplannerRos
visando assim que ela herdasse da classe interface nav_core::BaseGlobalPlanner.
Todos os métodos, então, foram sobrescritospela classeAstarPlannerROS. Os
métodos subrescritos foram:
o AstarPlannerROS();
o AstarPlannerROS(std::stringname, costmap_2d::Costmap2DROS*
costmap_ros);
o Void initialize(std::stringname, costmap_2d::Costmap2DROS* costmap_ros);
o BoolmakePlan(constgeometry_msgs::PoseStamped& start,
constgeometry_msgs::PoseStamped&goal,
std::vector<geometry_msgs::PoseStamped>&plan );
No arquivo header (.h) do AstarPlanner foi necessário adicionar a biblioteca de plug-
ins <pluginlib/class_list_macros.h> e registrar esse arquivo como sendo um
planejador global para o BaseGlobalPlanner, isso foi feito através da linha de código
(Astar_planner::AstarPlannerROS, nav_core::BaseGlobalPlanner).
É interessante dar um enfoque especial para o método makePlan(), em que a posição
inicial e final são convertidos em índices de células criadas na implementação deste
algoritmo. Então esses índices são transmitidos para a função de planejamento A*.
Quando a função terminar sua execução irá retornar o caminho calculado em formato
dos índices de células. Após estes passos, basta apenas converter os índices para as
coordenadas x e y e inserí-las no vetor (plan.pushback(pose)). Estas coordenadas do
59
vetor serão então enviadas para o move_base do global planner, o qual sera enviado
ao move_base que irá publicá-lo por meio do tópico nav_msgs/Path, o qual será então
recebido pelo modulo do local planner.
Para poder compilar a classe A* como o global planner do Navigation Stack, teve-se
que adcionar a biblioteca no arquivo CMakelist.txt da pasta onde foi configurado os
arquivos necessários para o funcionamento do Navigation Stack. Foi então adcionado
o seguinte código: add_library(astar_lib src/Astar_ros.cpp). Por meio do comando
catkin_make o arquivo foi compilado para gerar os arquivos binários, ou seja, criar o
arquivo de cabeçalho/biblioteca no diretório lib do ROS.
Finalizada esta parte e após sua implementação a classe global planner do A* está
pronta, necessitando apenas criar o plugin para que este possa integrar o módulo
global planner do pacote move_base.
Registrou-se então a classe rastar planner como um plugin, exportando-a pormeio do
commando PLUGINLIB_EXPORT_CLASS (Astar_planner::AstarPlannerROS,
nav_core :: BaseGlobalPlanner), o qual, foi adcionado ao arquivo .cpp do
rastarplanner permitindo que esta classe seja carregada de forma dinâmica pelo
move_base como um plugin do tipo nav_core::BaseGlobalPlanner.
Teve-se que criar também um arquivo XML, o qual contém a descrição do plugin,
armazenando todas as informações importantes sobre ele em um log de marcação. Ele
contém informações sobre a biblioteca do plugin, o nome do plug-in, o tipo do plug-
in, etc. No caso deste trabalho, de um planejador global, precisou-se criar um novo
arquivo e salvá-lo em determinado local em meu pacote (astar) e dar-lhe um nome,
(astar_planner_plugin.xml). O conteúdo do arquivo de descrição de plugin
(astar_planner_plugin.xml), ficou da seguinte maneira:
60
<library path = "lib / libastar_lib">
<class name="/AstarPlanner/Astar_plannerROS"
type="Astar_planner::AstarPlannerROS" base_class_type="nav_core::
BaseGlobalPlanner">
</ Class>
</ Library>
Na primeira linha <library path="lib/libastar_lib"> especifica o caminho para a
biblioteca plugin. Neste caso, o caminho é lib/libastar_lib, onde lib é a pasta no
diretório ~/catkin_ws/devel/ do ROS. Nesta
linha <classname="Astar_planner/AstarPlannerROS" type="Astar_planner::
AstarPlannerROS" base_class_type="nav_core::BaseGlobalPlanner">, primeiro
especifica-se o nome do plugin do global_planner que vai ser usado mais tarde no
arquivo de lançamento (launch file) do move_base como um parâmetro que especifica
qual planejador global deve ser utilizado no nav_core do Navigation Stack. Foi
utilizado o nome (Astar_planner) seguido por uma barra e o nome da classe
(AstarPlannerROS) para especificar o nome do plugin.
O type especifica o nome da classe que implementa o plugin que, no caso, é
o Astar_planner::AstarPlannerROS, e o base_class_type especifica o nome da classe
base que implementa o plug-in que, neste caso, é o
nav_core::BaseGlobalPlanner. A <description>tag fornece uma breve descrição
sobre o plugin.
Finalmente, para que o pluginlib possa consultar todos os plugins disponíveis no
sistema em todos os pacotes do ROS, cada pacote (packeage), deve indicar
explicitamente quais plugins são exportados e quais bibliotecas dos pacotes contêm
esses plugins. Um provedor de plugin deve apontar para o arquivo de descrição do
61
plugin em seu package.xml. No planejador desenvolvido as linhas de código
relevantes ficaram da seguinte forma:
<export>
<nav_core plugin="${prefix}/astar_planner_plugin.xml" />
</export>
O ${prefix}/ irá determinar automaticamente o caminho completo para o arquivo
astar_planner_plugin.xml.
3.7 Arquitetura A* estrela
Como o A* estrela foi umplementado como um plugin do nav_core do Navigation
Stack, sua execução, depende de todo o grafo de execução do Navigation Stack,
sendo passado ao move_base por meio do arquivo astar_planner. Na figura 24, pode
ser visualizado o grafo de execução para o algoritmo citado.
Figura 24–Grafo de execução do NavegationStack funcionando no robô lase.Neste grafo temos todo o
funcionamento do Navigation Stack onde tem-se os nós /move_base, /map_server, /vrep e /kine_controller.
62
Conforme pode ser visualizado na Figura 24, o nó /move_base é responsável por
gerenciar toda a lógica de controle do robô, a partir do mapa passado pelo
/map_server através do tópico /map, e das informações passadas pelo /vrep através
dos tópicos /odom, /tf, /scan, o /move_base cria os mapas de custo e as trajetórias
locais e globais. Isto é feito por meio do acesso aos tópicos que podem ser vistos
dentro da caixa move_base. Após fazer a lógica da trajetória a velocidade para mover
o robô é passada ao nó /kinecontroler que publica nos tópicos /AMR/motorLeftSpeed e
/AMR/motoRightSpeed no nó /vrep.
63
4 – RESULTADOS E DISCUSSÕES
Ao escolher-se um algoritmo de planejamento de trajetória, deve-se analisar
características como o tempo de execução e trajetória. Assim , pode-se classificar o
desempenho do robô e verificar o melhor código para a aplicação desejada.
4.1 Simulações BUG 1
Para simulação do código BUG 1, três mapas foram utilizados. O código definia que
o robô circunavegasse por inteiro cada obstáculo, salvando qual o menor ponto de
distância para deixar o obstáculo. Os resultados de trajetórias nos 3 mapas estão
apresentados nas Figuras 25, 26 e 27 a seguir.
Figura 25 - Simulação do BUG 1 no MAPA 1, sendo o (1) o momento que o robô sai da posição inicial, e (16) o momento que o robô chega ao seu destino.
64
Figura 26 - Simulação do BUG 1 no MAPA 2, sendo o (1) o momento que o robô sai da posição inicial, e (14) o momento que o robô chega ao seu destino.
Figura 27 - Simulação do BUG 1 no MAPA 3, sendo o (1) o momento que o robô sai da posição inicial, e (18) o
momento que o robô chega ao seu destino.
65
4.2 Simulações BUG 2
Para simulação do código BUG 2, os mesmos três mapas do BUG 1 foram utilizados.
O código definia que o robô circunavegasse cada obstáculo até encontrar a linha m,
deixando assim o obstáculo. Os resultados de trajetórias nos 3 mapas estão
apresentados nas Figuras 28, 29 e 30 a seguir.
Figura 28 - Simulação do BUG 2 no MAPA 1, sendo o (1) o momento que o robô sai da posição inicial, e (8) o
momento que o robô chega ao seu destino.
Figura 29 -Simulação do BUG 2 no MAPA 2, sendo o (1) o momento que o robô sai da posição inicial, e (8) o momento que o robô chega ao seu destino.
66
Figura 30 –Simulação do BUG 2 no MAPA 3, sendo o (1) o momento que o robô sai da posição inicial, e (10) o
momento que o robô chega ao seu destino.
4.3 RESULTADOS BUG 1 versus BUG 2
As simulações utilizando as classes BUG 1 e BUG 2 foram realizados utilizando o
mesmo robô. Sendo assim, é possível fazer uma análise comparativa entre elas. Para
tal, foram escolhidos três mapas para simulação dos dois algoritmos, contendo o
mesmo tamanho, os mesmos obstáculos, e usando o mesmo ponto de início e ponto de
chegada para os mapas, a fim de se analisar comparativamente os tempos, as
distâncias percorridas e as trajetórias executadas. O mapa e as trajetórias estão
apresentados das figuras 25 a 30.
Foram registrados os tempos de cada etapa da trajetória, em cada um dos algoritmos:
- tempo necessário para o Bug1 alcançar o destino no mapa 1(B1M1T);
67
- tempo necessário para o Bug1 alcançar o destino no mapa 2(B1M2T);
- tempo necessário para o Bug1 alcançar o destino no mapa 3(B1M3T);
- tempo necessário para o Bug2 alcançar o destino no mapa 1(B2M1T);
- tempo necessário para o Bug2 alcançar o destino no mapa 2(B2M2T);
- tempo necessário para o Bug2 alcançar o destino no mapa 3(B2M3T).
Os resultados são mostrados na Tabela 1 e no Gráfico 1 a seguir.
Tabela 1 - BUG 1 versus BUG 2: Tempos de execução de trajetória
Tempo (s)
Mapa 1 Mapa 2 Mapa 3
BUG 1 3:04:09 (B1M1T)
3:22:06 (B1M2T)
4:32:02 (B1M3T)
BUG 2 1:46:04 (B2M1T)
2:29:03 (B2M2T)
1:28:06 (B2M3T)
Gráfico 1- BUG 1 versus BUG 2: comparação de tempos de execução nos três mapas diferentes
3:04:09 03:22:06
04:32:02
01:46:04
02:29:03
01:28:06
0:00:00
0:28:48
0:57:36
1:26:24
1:55:12
2:24:00
2:52:48
3:21:36
3:50:24
4:19:12
4:48:00
Mapa 1 Mapa 2 Mapa 3
Tem
po (s
)
BUG 1
BUG 2
68
O gráfico 1 demonstra o quão diferente foram os tempos de percursos nos mesmos
mapas usando cada um dos algoritmos. Pode-se notar que no mapa 2 temos uma
menor diferença entre os Bugs, pois este mapa denota um dos casos críticos para o
Bug2.Em todos os mapas podemos verificar a maior eficiência em relação ao tempo
do Bug2.
Já as distâncias percorridas até o ponto de chegada (goal) em cada caso, por sua vez,
foram registradas pelo simulador. Sendo:
- Distância Percorrida pelo Bug1 no mapa1 (B1M1D);
- Distância Percorrida pelo Bug1 no mapa2 (B1M2D);
- Distância Percorrida pelo Bug1 no mapa3 (B1M3D);
- Distância Percorrida pelo Bug2 no mapa1 (B2M1D);
- Distância Percorrida pelo Bug2 no mapa2 (B2M2D);
- Distância Percorrida pelo Bug2 no mapa3 (B2M3D).
Os dados são apresentados na Tabela 2 a seguir.
Tabela 2- BUG 1 versus BUG 2: Distâncias percorridas
Distância (m)
Mapa 1 Mapa 2 Mapa 3
BUG 1 52,50 (B1M1D)
60,48 (B1M2D)
83,30 (B1M3D)
BUG 2 19,32 (B2M1D)
44,83 (B2M2D)
30,53 (B2M3D)
Foi gerado um gráfico comparando o Bug1 e Bug2 em cada um dos mapas. Para o
Mapa 1, a trajetória ideal, em linha reta (caso não houvesse obstáculos no percurso)
69
entre o ponto de início e ponto de chegada, tem valor de distância igual a 6,9 metros,
para o Mapa2 7,67 metros e para o Mapa 3 8,52 metros, representadas nas figuras 25
a28 pela linha reta em azul claro.
Gráfico 2- BUG 1 versus BUG 2: Distâncias percorridas até alcançar o goal
Por meio dos resultados gráficos é possível notar a diferença de trajetória, tempo e
distâncias percorridas entre os algoritmos das classes BUG 1 e BUG 2. O BUG 2 se
mostra muito mais eficiente, em todos os quesitos. Isso comprova então a
melhoramento do BUG 2 em relação ao BUG 1, devido ao fato de saída do obstáculo
sempre quando encontra a m-line novamente, no entanto para cenários específicos
como os encontrados na literatura e discutidos na revisão bibliográfica, o Bug1 poderá
se mostrar mais eficiente.
4.4 Simulações A* (Astar)
Para simulação do código A*, três mapas diferentes dos utilizados nos Bugs foram
utilizados. O código definia que o robô encontrasse a melhor trajetória expandida da
posição inicial em direção a posição final, encontrando o melhor caminho possível.
52,50
60,48
83,30
19,32
44,83
30,53
0,00
10,00
20,00
30,00
40,00
50,00
60,00
70,00
80,00
90,00
Mapa 1 Mapa 2 Mapa 3
Dis
tânc
ia (m
)
BUG 1
BUG 2
70
Os resultados de trajetórias nos 3 mapas estão apresentados nas Figuras 19, 20 e 21 a
seguir.
Figura 31 - Simulação do algoritmo A* (Astar) no mapa 1. As imagens (a) representam a simulação no RViz (visualizador do global planner), onde a linha fina em azul representa a trajetória global projetada pelo A*, a linha verde a trajetória local, e a linha vermelha a trajetória percorrida pelo robô. As imagens (b) são representações do
VRep.
Figura 32-Simulação do algoritmo A* (Astar) no mapa 2. As imagens (a) representam a simulação no RViz (visualizador do global planner), onde a linha fina em azul representa a trajetória global projetada pelo A*, a linha verde a trajetória local, e a linha vermelha a trajetória percorrida pelo robô. As imagens (b) são representações do
VRep.
71
Figura 33 - Simulação do algoritmo A* (Astar) no mapa 3. As imagens (a) representam a simulação no RViz (visualizador do global planner), onde a linha fina em azul representa a trajetória global projetada pelo A*, a linha verde a trajetória local, e a linha vermelha a trajetória percorrida pelo robô. As imagens (b) são representações do
VRep.
4.5 RESULTADOS A*(Astar)
As simulações para o algoritmo A* (Astar) foram realizadas nos três mapas ilustrados
na seção anterior com o robô laser. Para poder avaliar seu desempenho foram aferidas
as distâncias percorridas pelo robô, a trajetória gerada(mostradas nas figuras 18-21), o
tempo necessário para planejar cada trajetória e tempo necessário para executar a
trajetória. Sendo assim, é possível fazer uma análise quantitativa do algoritmo
desenvolvido. Para a velocidade do robô, esta foi limitada a 0,4 m/s tanto para a
velocidade angular quanto para a linear. Teve-se que adotar tais velocidades muito
baixas devido a problemas de colisão quando o robô passava muito perto de
obstáculos com limites de velocidades maiores. Estas velocidades foram determinadas
72
no arquivo base_local_planner_params.yaml, para utilização do local planner default
do Navigation Stack.
Foram registrados os tempos de execução e planejamento de cada trajetória, em cada
um dos mapas:
- tempo necessário para o A*calcular a trajetória no mapa 1 (AM1TP);
- tempo necessário para o A* alcançar o destino no mapa 1 (AM1TE);
- tempo necessário para o A*calcular a trajetória no mapa 2 (AM2TP);
- tempo necessário para o A* alcançar o destino no mapa 2 (AM2TE);
- tempo necessário para o A*calcular a trajetória no mapa 3 (AM3TP);
- tempo necessário para o A* alcançar o destino no mapa 3 (AM3TE);
Os resultados são mostrados na Tabela 1 a seguir.
Tabela 3 - Tempos de processamento e de execução de trajetória do algoritmo A*
Tempo (s)
Mapa 1 Mapa 2 Mapa 3
Processamento 4,179 (AM1P)
10,1 (AM2P)
6,319 (AM3P)
Execução 156,91 (AM1E)
201,83 (AM2E)
242,55 (AM3E)
As distâncias percorridas até o ponto de chegada (goal) em cada caso foram
registradas. Sendo:
- Distância Percorrida pelo A* no mapa1 (AM1D);
- Distância Percorrida pelo A* no mapa2 (AM2D);
- Distância Percorrida pelo A* no mapa3 (AM3D);
73
Os dados são apresentados na Tabela 2 a seguir.
Tabela 4- BUG 1 versus BUG 2: Distâncias percorridas
Distância (m)
AM1D 13,93
AM2D 17,72
AM3D 15,74
Foram gerados gráficos comparando os tempos de planejamento e execução da
trajetória nos diferentes mapas, bem como as distancias percorridas.
5- CONCLUSÃO
Diante dos resultados obtidos verificou-se que o algoritmo Bug 2, por se tratar de um
algoritmo muito simples e fácil de ser implementado, que não necessita de
conhecimento prévio do ambiente para poder funcionar, apresenta uma interessante
opção para utilização em locomoção autônoma. Já o caso do Bug1, apesar de bastante
robusto, garante que sempre irá encontrar o destino independentemente do cenário, no
entanto, acaba sendo lento devido à necessidade de dar uma volta completa no
obstáculo. Ainda, vale ressaltar como ponto positivo que ambos não necessitam de
um conhecimento prévio do mapa para executarem.
Quanto ao A*, é uma opção excelente para o planejamento de trajetórias, pois apesar
de apresentar uma maior complexidade de código e um gasto computacional
considerável com execução, realiza a exploração do mapa para criação da trajetória de
forma inteligente. Entretanto, para que possa ser usado, há a necessidade de se
conhecer o mapa previamente, uma vez que, este planeja a trajetória a partir de um
74
mapa estático, e caso haja alguma alteração neste, ele não receberá esta atualização e
poderá falhar. Pode-se então realizar o planejamento de trajetória global com o A* e
caso ocorra alguma alteração no mapa durante execução, pode-se usar o Bug 2 para
solucionar o problema com obstáculos que foram inseridos após o planejamento ou
então algoritmos mais robustos como o campos potenciais.
Dessa forma, temos o Bug 2 excelente por sua simplicidade de código, baixo custo de
execução e bom desempenho para mapas simples e o A* como um excelente
planejador de trajetória global, mas que está atrelado a necessidade de mapeamento
prévio.
Para futuros trabalhos, fica a proposta de utilizar o algoritmo A* desenvolvido neste
trabalho para o planejamento global de trajetória no ROS, e desenvolver um algoritmo
campos potenciais como plugin para o planejamento local de trajetórias em um robô
real.
75
REFERÊNCIAS BIBLIOGRÁFICAS
Robot Motion Planning2012Springer Science
Planeamento Cooperativo de Tarefas e Trajectórias em Múltiplos Robôs Cidade do
PortoPortugalFaculdade de Engenharia da Universidade do Porto
CHOSET, H. (2015). Robotic Motion Planning:Bug Algorithms. Acesso em 12 de
Outubro de 2016, disponível em
https://www.cs.cmu.edu/~motionplanning/lecture/Chap2-Bug-Alg_howie.pdf
2011Comparação do Desempenho dos Algoritmos Bug2Universidade Federal de
Minas Gerais
Introduction to Autonomous Mobile Robots2004MIT Press
Introduction to Robotics - Bug Algorithms
MICHAELIS Dicionário Brasileiro da Língua Portuguesa2016
Negri, J., Rodrigues, R. T., & Becker, M. (Setembro de 2016). A V-REP/ROS Model
for Validating Motion Planning and Control Algorithms in Simulated Environment.
São Carlos, Brazil: In 24th USP International Symposium of Undergraduate Research
(SIICUSP).
Programação de Jogos em C++ e DIrectx2005Novatec
Robot operating systems: Bridging the gap between human and2012System Theory
(SSST)
ROS Crash-Course, Part I Introduction to ROS distribution, build system and
infrastructure2010
ROS Wiki2013
V-REP Virtual Robot Experimentation Plataform. (2013). Acesso em 16 de Agosto de
2016, disponível em Home V-Rep Virtual Robot Experimentation Plataform:
http://www.coppeliarobotics.com