Implementação do Controle de Enxames de Robôs Utilizando a

Mateus Mendonça Bosque
Implementação do Controle de Enxames de Robôs
Utilizando a Hidrodinâmica de Partículas Suavizadas
Belo Horizonte
Dezembro de 2009
Mateus Mendonça Bosque
Implementação do Controle de Enxames de Robôs
Utilizando a Hidrodinâmica de Partículas Suavizadas
Monografia submetida à banca examinadora
designada pelo Colegiado Didático do Curso
de Graduação em Engenharia de Controle
e Automação da Universidade Federal de
Minas Gerais, como parte dos requisitos para
aprovação na disciplina Projeto Final de Curso.
Orientador: Renato Cardoso Mesquita
Co-Orientador: Luciano Cunha A. Pimenta
Supervisor: Luiz Chaimowicz
U NIVERSIDADE F EDERAL DE M INAS G ERAIS
E SCOLA DE E NGENHARIA
Belo Horizonte
Dezembro de 2009
Resumo
Um novo paradigma chamado Enxame de Agentes Autônomos tem sido estudado no campo
da robótica. Neste paradigma o objetivo é controlar grandes grupos de robôs (dezenas a centenas) muito simples. A idéia chave é que o sucesso na execução de uma tarefa dependerá dos
comportamentos que vão emergir das interações entre agentes. Neste contexto, cada agente
deve ser o mais simples possível com capacidades limitadas de comunicação, sensoriamento e
atuação. Outra característica importante de um enxame é a flexibilidade. Utilizando diferentes mecanismos de coordenação o mesmo enxame pode ser utilizado em diferentes problemas.
Um outro ponto importante é que a coordenação do enxame não deve depender de membros
específicos do grupo. Logo, soluções totalmente descentralizadas, onde os agentes podem ser
considerados anônimos e podem ser programados com o mesmo código, devem ser consideradas. Além disso, tais soluções devem ser robustas à adição e remoção dinâmica de robôs.
Este é um trabalho de foco prático. Nesse sentido, seu objetivo principal é implementar
técnicas de controle de enxames em robôs reais, os e-pucks. Espera-se com isso contribuir
para que conceitos teóricos existentes na literatura sejam validados na presença de efeitos que
normalmente são verificados nos sistemas robóticos reais, como ruídos de localização e atuação,
saturações, dinâmica, restrições mecânicas, atrasos de comunicação, etc.
A coordenação do enxame se dá através do acoplamento entre duas técnicas. O método
de Hidrodinâmica de Partículas Suavizadas (HPS) é utilizado para modelar as interações entre
robôs do grupo. Já o Método de Elementos Finitos (MEF) é utilizado para calcular os campos
vetoriais que determinam as forças externas que orientam os agentes até o alvo. Esta abordagem
é instanciada num problema de geração de padrões, onde um padrão geométrico desejado deve
ser obtido e mantido pelos e-pucks sem qualquer coordenação centralizada.
Abstract
A new approach named Swarm of Autonomous Agents has been studied in the field of robotics. In this context, the aim of this paradigm is to control large groups of very simple robots
(tens or hundreds). The main idea is that the success of executing a task depends on the behaviors that emerge from the interactions among agents. Each agent should be as simple as possible
with limited capabilities of communication, sensing, and actuation. An additional important
attribute of a swarm is its flexibility. By employing different coordination strategies, the same
swarm can be used in different tasks. Besides, the proposed strategies should not depend on a
specific member of the group. Therefore, completely decentralized solutions should be considered, in which agents can be considered anonymous and can be programmed with the same
code. Also, these solutions should be robust to dynamic addition and removal of robots.
This is a practical work. The main objective is to implement techniques of swarm control
in real robots, the e-pucks. We expect to contribute to the validation of theoretical concepts
described in the literature on the presence of effects, which are normally found on real robotic
platforms, as localization and actuation noise, saturations, dynamics, mechanical constraints,
communication delays, etc.
The coordination strategy is implemented by means of the coupling between two numerical techniques. The Smoothed Particle Hydrodynamics (SPH) method is applied to model the
interactions among robots. The Finite Element Method (FEM) is used to compute the vector
field which determines the external forces that drive the agents to the goal. This framework
is instantiated in a pattern generation problem, in which a desired geometric pattern must be
obtained and maintained by the e-pucks without any centralization.
Lista de Figuras
1.1
Configuração de um swarm-bot para vencer o espaço entre dois tijolos (SWARMBOTS, 2009). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2
Simulações de robôs EU-MOP retirando o petróleo derramado em um ambiente marinho (FRITSCH; WEGENER; SCHRAFT, 2007). . . . . . . . . . .
1.3
p. 14
Seqüência de fotos que confirmam a viabilidade da abordagem desenvolvida
(MARCOLINO; CHAIMOWICZ, 2008). . . . . . . . . . . . . . . . . . . .
2.1
p. 13
p. 14
Um robô é representado por um ponto em seu espaço de configurações (PEREIRA, 2003). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 16
2.2
Mínimo local causado por um obstáculo em forma de U. . . . . . . . . . . .
p. 17
2.3
Programa FEMM: ferramenta para solução numérica de problemas eletromagnéticos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 18
2.4
Gráfico da função núcleo W com h = 1. . . . . . . . . . . . . . . . . . . . .
p. 20
3.1
Diagrama representativo do controlador. . . . . . . . . . . . . . . . . . . . .
p. 26
4.1
Stage: uma ferramenta para simulação utilizada na robótica. . . . . . . . . .
p. 28
4.2
Dois e-pucks do VeRLab(GARCIA, 2008). . . . . . . . . . . . . . . . . . . .
p. 29
4.3
Sistema de localização por câmeras do VerLab (GARCIA et al., 2007). . . . .
p. 30
4.4
Exemplos de marcos visuais da biblioteca ARToolkitPlus (GARCIA et al.,
2007). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 30
4.5
Espaço de configurações, malha e campo elétrico do primeiro mapa. . . . . .
p. 31
4.6
Espaço de configurações, malha e campo elétrico do segundo mapa. . . . . .
p. 32
4.7
Espaço de configurações, malha e campo elétrico do terceiro mapa. . . . . . .
p. 32
4.8
Evolução do experimento no primeiro mapa: (a) 0%. (b) 33%. (c) 67%. (d)
4.9
100%. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 33
Trajetória descrita pelo enxame no primeiro mapa. . . . . . . . . . . . . . .
p. 34
4.10 Densidade dos robôs ao longo do experimento no primeiro mapa. . . . . . . .
p. 34
4.11 Evolução do experimento no segundo mapa: (a) 0%. (b) 33%. (c) 67%. (d)
100%. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 35
4.12 Trajetória descrita pelo enxame no segundo mapa. . . . . . . . . . . . . . . .
p. 35
4.13 Densidade dos robôs ao longo do experimento no segundo mapa. . . . . . . .
p. 36
4.14 Evolução do experimento no terceiro mapa: (a) 0%. (b) 33%. (c) 67%. (d)
100%. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 37
4.15 Trajetória descrita pelo enxame no terceiro mapa. . . . . . . . . . . . . . . .
p. 37
4.16 Densidade dos robôs ao longo do experimento no terceiro mapa. . . . . . . .
p. 38
4.17 Sequência de imagens de experimentos no segundo mapa evidenciando as
dificuldades de calibração da câmera. . . . . . . . . . . . . . . . . . . . . .
p. 39
4.18 Localização dos robôs baseada na odometria em um experimento com o segundo mapa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 39
Sumário
1 Introdução
p. 8
1.1
Enxames de robôs: a inteligência de enxames e a robótica cooperativa . . . .
p. 8
1.2
Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 11
1.3
Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 12
1.4
Estado da Arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 13
1.5
Organização da Monografia . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 14
2 Definições, nomenclatura e ferramentas
p. 15
2.1
Espaço de Configurações . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 15
2.2
Campos Potenciais Artificiais . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 16
2.3
Hidrodinâmica de Partículas Suavizadas . . . . . . . . . . . . . . . . . . . .
p. 18
3 Coordenação de Enxames Utilizando Modelos de Dinâmica dos Fluidos
p. 23
3.1
O Problema de Geração de Padrões . . . . . . . . . . . . . . . . . . . . . . .
p. 23
3.2
Considerações Práticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 24
3.3
Implementação do controlador . . . . . . . . . . . . . . . . . . . . . . . . .
p. 25
4 Simulações e Experimentos
p. 27
4.1
Player/Stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 27
4.2
Plataforma Experimental . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 29
4.2.1
E-pucks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 29
4.2.2
Sistema de Localização . . . . . . . . . . . . . . . . . . . . . . . . .
p. 29
Experimentos realizados . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 31
4.3
4.3.1
Experimentos com o primeiro mapa . . . . . . . . . . . . . . . . . .
p. 31
4.3.2
Experimentos com o segundo mapa . . . . . . . . . . . . . . . . . .
p. 33
4.3.3
Experimentos com o terceiro mapa . . . . . . . . . . . . . . . . . . .
p. 36
4.3.4
Análise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 36
5 Conclusões
p. 40
Referências Bibliográficas
p. 41
8
1
Introdução
Este capítulo está organizado da seguinte forma: na primeira seção define-se o que é a
inteligência de enxames, a robótica cooperativa e os enxames de robôs. Na segunda seção,
apresenta-se a motivação para os estudos com enxames e a importância de se realizarem experimentos com robôs reais. Na terceira seção, listam-se trabalhos relevantes em coordenação de
enxames. Por fim, apresentam-se os objetivos desta Monografia e a sua estrutura.
Este trabalho foi desenvolvido em dois Laboratórios da Universidade Federal de Minas Gerais (UFMG): o Laboratório de Otimização e Projeto Assistido por Computador - LOPAC1 , sala
2215 da Escola de Engenharia e o Laboratório de Visão Computacional e Robótica - VeRLab2 ,
salas 3020 e 3021 do Instituto de Ciências Exatas.
1.1 Enxames de robôs: a inteligência de enxames e a robótica
cooperativa
Inteligência de enxames
A inteligência de enxames é uma moderna disciplina de inteligência artificial que está voltada para a concepção de sistemas multiagentes com aplicações, por exemplo, na otimização
e na robótica. Ao invés de um controlador sofisticado que governa o comportamento global
do sistema, o princípio da inteligência de enxames é baseado em várias entidades simples que
cooperam entre si com o objetivo de exibir um comportamento desejado. A inspiração para
o projeto destes sistemas vem do comportamento coletivo de insetos sociais como formigas,
abelhas, cupins, vespas, bem como o comportamento de outras sociedades de animais, como
bando de pássaros ou cardume de peixes. Mesmo que cada membro destas sociedades seja um
indivíduo simples, eles são capazes de realizar tarefas complexas em cooperação.
Por exemplo, formigas, cupins e vespas são capazes de construir ninhos sofisticados em
1 http://gopac.cpdee.ufmg.br/.
2 http://www.verlab.dcc.ufmg.br/.
9
cooperação, sem que nenhum dos integrantes tenha um plano global de como proceder. Outro
exemplo é o comportamento de exploração que formigas ou abelhas exibem quando procuram
por comida. Enquanto as formigas utilizam uma estratégia de comunicação indireta através de
trilhas de feromônio, a fim de encontrar caminhos mais curtos entre os seus ninhos e as fontes
de alimento, as colônias de abelhas são mais eficientes na exploração de ricas fontes de comida,
realizando sua comunicação por meio de uma dança específica (BLUM; LI, 2008).
Cientistas têm aplicado esses princípios para novas abordagens, por exemplo, na otimização e no controle de robôs. Entre as propriedades que caracterizam os sistemas resultantes
estão a robustez a falhas e a flexibilidade para a execução de diferentes tarefas. O campo de pesquisa voltado para o comportamento coletivo em sistemas auto-organizados e descentralizados
é chamado inteligência de enxames.
Na otimização, há aplicações de sucesso como a otimização por colônia de formigas (ACO)
e otimização por enxame de partículas (PSO) (BLUM; LI, 2008). A ACO é uma técnica utilizada para procurar caminhos em grafos, baseando-se no comportamento observado em formigas
ao saírem de seus ninhos para encontrarem alimento. Já a PSO é aplicada em diversos tipos de
problemas, como o problema do caixeiro viajante, o treinamento de redes neurais, o controle de
tensão e potência reativa, etc.
Robótica cooperativa
A robótica cooperativa é o campo da robótica dedicado ao estudo de técnicas que permitem
que robôs agrupados em equipes cooperem entre si e com seres humanos para realizar uma dada
tarefa. Conforme (MARCOLINO; CHAIMOWICZ, 2008), ela é capaz de aumentar a robustez
e eficiência da execução de uma tarefa. O uso de times de robôs apresenta várias vantagens
sobre abordagens baseadas em um único robô. Primeiramente, dependendo do tipo de tarefa,
múltiplos robôs podem executá-la mais eficientemente mediante uma divisão do trabalho. Além
disso, grupos de robôs simples e com custo unitário mais baixo que trabalham cooperativamente
podem substituir um robô especializado cujo custo unitário é mais elevado. Ademais, aumentase a robustez em certas tarefas pelo uso de robôs que apresentam capacidade de redundância e
reconfiguração dinâmica em caso de falhas.
Na comunidade de robótica, a maioria das abordagens para planejar o movimento de grupos de robôs tem geralmente sido dividida em dois tipos: centralizada e descentralizada. As
abordagens centralizadas são aquelas que assumem a existência de uma entidade central, a qual
é capaz de planejar as ações de cada robô do grupo. Embora, em geral, se possa provar que a
utilização de tal abordagem garante sucesso na realização da tarefa, este tipo de técnica não é
10
escalável para grandes grupos de robôs por razão de limitações computacionais. Por outro lado,
abordagens descentralizadas fornecem soluções escaláveis uma vez que neste caso cada agente
do grupo planeja suas próprias ações baseadas em informações locais.
Enxames de robôs
A partir das idéias de inteligência de enxames e das abordagens de soluções descentralizadas da robótica cooperativa, surgiu o paradigma chamado enxames de robôs. Neste arcabouço,
estuda-se como um grande número de agentes relativamente simples pode ser coordenado de
modo a possibilitar um comportamento coletivo desejado a partir das interações locais entre os
agentes e o ambiente.
Conforme (SAHIN et al., 2008), a operação de um sistema de enxame robótico deve apresentar três propriedades funcionais que são observadas em enxames naturais e também são
desejáveis naqueles sistemas robóticos. Primeiramente, tem-se a robustez. O sistema de enxame robótico deve ser capaz de operar mesmo com perturbações do ambiente ou com o mau
funcionamento de seus indivíduos. Alguns fatores podem ser observados na robustez das operações dos insetos sociais: enxames são inerentemente sistemas redundantes (a perda de um
indivíduo pode ser imediatamente compensada por outro); a coordenação é descentralizada e,
conseqüentemente, é improvável que o enxame interrompa sua operação com a destruição de alguns membros; os indivíduos que compõem o enxame são relativamente simples (capacidades
limitadas de comunicação, sensoriamento e atuação), tornando-os menos propensos a falhas;
por fim, o sensoriamento é distribuído, e por isso o sistema é robusto à perturbações locais no
ambiente.
A segunda característica é a flexibilidade. Os indivíduos de um enxame devem ser capazes
de coordenarem seus comportamentos para realizar tarefas de natureza distinta. Por exemplo,
os membros de uma colônia de formigas podem encontrar o caminho mais curto para uma fonte
de comida ou transportar uma presa grande por meio da utilização de diferentes estratégias de
coordenação.
A terceira e última propriedade é a escalabilidade. O enxame deve ser capaz de operar para
uma grande faixa de tamanhos de grupos e suportar um grande número de indivíduos sem que
isso comprometa de forma considerável o desempenho. Ou seja, os mecanismos e estratégias
de coordenação a serem desenvolvidas para sistemas de enxames de robôs devem garantir o
funcionamento para diferentes tamanhos do grupo.
11
1.2 Motivação
De acordo com (SAHIN et al., 2008), até o momento a pesquisa com enxames robóticos
está principalmente voltada para a prova de conceitos em simuladores ou experimentos em
laboratórios. Na seqüência, serão descritos alguns dos problemas que têm sido abordados em
pesquisas de enxames robóticos (SAHIN et al., 2008).
Primeiramente, pode-se citar o desafio da agregação. A agregação auto-organizada (agrupamento dos indivíduos de um enxame utilizando o mínimo de informações do ambiente) é um
comportamento comum observado em organismos que vão desde bactérias até insetos sociais e
mamíferos. Comportamentos de agregação foram desenvolvidos para robôs míopes, que podem
perceber apenas uma pequena parte de todo o ambiente, confinados em uma grande arena, utilizando abordagens evolucionárias e um controlador probabilístico inspirado em insetos sociais.
Já a dispersão auto-organizada pode ser considerada como o oposto de agregação e de interesse em cenários de vigilância. Neste problema, o desafio é obter uma disseminação uniforme
do enxame de robôs no espaço, maximizando a área coberta.
O problema da exploração é inspirado pelo comportamento de formigas que procuram por
fontes de comida distribuídas ao redor de seu ninho. Aqui, o desafio é encontrar estratégias de
busca ótimas que maximizem a taxa de alimento encontrado em relação aos recursos utilizados
no ambiente.
O comportamento de automontagem é observado em formigas, onde elas formam cadeias
através de ligações entre si para construir estruturas como bóias para ficar sobre a água. O
problema da automontagem pode ser definido como a criação auto-organizada de estruturas
através da formação de conexões físicas entre os robôs do enxame.
No problema do movimento conectado, um enxame de robôs móveis, fisicamente conectados uns aos outros, devem coordenar os seus movimentos de maneira que o grupo se desloque
suavemente em ambientes com obstáculos desconhecidos, como buracos, de forma coordenada.
Cita-se também o desafio do transporte cooperativo. As formigas são conhecidas por transportar grandes presas até o seu ninho coordenando suas ações de empurrar e puxar. Essa capacidade de coordenação é útil para sistemas de enxames robóticos. Os membros do enxame
podem juntar forças de forma a gerar uma grande força resultante suficiente para puxar um objeto pesado. Esse problema está parcialmente relacionado com o movimento conectado, com a
diferença de que ele inclui um objeto passivo que precisa ser transportado.
Por fim, tem-se a formação de padrão. Este é um termo genérico para o problema de
12
como um padrão geométrico desejado pode ser obtido e mantido por um enxame de robôs sem
qualquer coordenação centralizada.
A partir das áreas de pesquisas mencionadas anteriormente, podem-se citar diversas aplicações no mundo real dos enxames robóticos: operações de pesquisa e resgate em ambientes
perigosos ou em lugares onde humanos não têm acesso, contenção de vazamento de óleo no oceano, transporte de objetos pesados, monitoramento de ambientes, vigilância, etc. Além disso,
através dos avanços esperados com o desenvolvimento da nanotecnologia, as possibilidades de
aplicações de enxames robóticos se ampliam consideravelmente. Pode-se pensar, por exemplo,
em milhões de nanorobôs sendo injetados dentro de um ser humano para combater células cancerígenas. Um enxame de nanorobôs poderia também ser útil para construir e manipular outras
nanoestruturas. Entretanto, para que se tenham aplicações bem sucedidas no futuro, é preciso
que as fundamentações teóricas sejam bem estabelecidas no momento. Além disso, é fundamental não apenas simular, mas também implementar em robôs reais as técnicas de controle de
enxames. Dessa forma, limitações de comunicação, de processamento, de sensoriamento e de
atuação podem ser evidenciadas, o que geralmente não ocorre no momento em que a teoria é
desenvolvida.
1.3 Objetivos
Este é um trabalho de foco prático. Nesse sentido, seu objetivo principal é implementar em
robôs reais a técnica de controle de enxames desenvolvida em (PIMENTA, 2009). Espera-se
com isso contribuir para que conceitos existentes sejam fortalecidos, o que possibilitará que
enxames robóticos sejam utilizados com maior freqüência em situações do mundo real.
Além disso, os objetivos específicos compreendem:
• Estudo de técnicas do estado da arte para o controle de enxames de robôs;
• Estudo de ambientes de simulação realísticas utilizados pela comunidade de robótica
mundial;
• Implementação de técnicas para o controle de enxames em simuladores;
• Estudo dos robôs para enxames e a plataforma experimental desenvolvida no VeRLab/DCC,
UFMG;
• Realização de experimentos e análise dos resultados.
13
1.4 Estado da Arte
Um projeto mundialmente conhecido na comunidade da robótica cooperativa é o chamado
Swarm-bots (SWARM-BOTS, 2009). Trata-se de uma nova abordagem para a concepção e implementação de sistemas auto-organizáveis e auto-montáveis. Esses sistemas são compostos por
robôs autônomos simples, chamados s-bots, com capacidades computacionais, sensoriais e de
atuação limitadas. Entretanto, os s-bots podem criar conexões físicas entre eles, formando um
swarm-bot que é capaz de resolver problemas que isoladamente não poderiam ser enfrentados,
tais como terrenos irregulares, passagens estreitas, buracos ou fendas, como ilustra a Figura 1.1.
Trabalhos como (TRIANNI; NOLFI; DORIGO, 2006) e (DORIGO et al., 2006) estudaram o
movimento coordenado de swarm-bots.
Figura 1.1: Configuração de um swarm-bot para vencer o espaço entre dois tijolos (SWARMBOTS, 2009).
Outro interessante projeto na área de enxames trata-se das Unidades de Eliminação de Poluentes derivados do Petróleo no Mar (EU-MOP - Elimination Units for Marine Oil Pollution)
(EU-MOP, 2009). O conceito básico do EU-MOP, conforme (FRITSCH; WEGENER; SCHRAFT, 2007), é o seguinte: após a detecção de um vazamento de óleo, os robôs EU-MOP são
transportados até a área operacional por um navio de apoio. Em seguida, eles começam a recolher o óleo até que seja atingido seu limite de capacidade ou energia. Quando isso ocorre,
os robôs EU-MOP se deslocam até o navio de apoio, recarregam suas baterias e esvaziam seus
reservatórios. Este processo se repete até que o óleo seja retirado do oceano. A Figura 1.2
apresenta uma simulação deste processo.
Uma nova abordagem na coordenação de grandes grupos de robôs foi desenvolvida por
(MARCOLINO; CHAIMOWICZ, 2008). Neste trabalho, os autores desenvolveram um algoritmo que permite um enxame de robôs navegar em um ambiente que contém obstáculos desconhecidos. Robôs que podem ficar parados em regiões de mínimo local são auxiliados por outros,
14
Figura 1.2: Simulações de robôs EU-MOP retirando o petróleo derramado em um ambiente
marinho (FRITSCH; WEGENER; SCHRAFT, 2007).
de resgate, após chegarem ao lugar desejado. Experimentos foram realizados utilizando-se um
simulador realístico e um grupo de robôs reais e os resultados obtidos mostraram a viabilidade
da abordagem proposta, conforme mostra a Figura 1.3.
Figura 1.3: Seqüência de fotos que confirmam a viabilidade da abordagem desenvolvida (MARCOLINO; CHAIMOWICZ, 2008).
Além das propostas apresentadas acima, existem inúmeras técnicas desenvolvidas para a
coordenação de enxames de robôs. As estratégias que serão discutidas, simuladas e implementadas neste trabalho foram desenvolvidas em (PIMENTA, 2009). O enxame foi modelado como
um fluido imerso numa região onde um campo de forças externas livre de mínimos locais é definido. Neste caso, o autor utilizou o método de Hidrodinâmica de Partículas Suavizadas (HPS)
para modelar o "fluido robótico", isto é, as interações entre robôs do grupo. O Método de Elementos Finitos (MEF) também foi utilizado para calcular os campos vetoriais que determinam
as forças externas.
1.5 Organização da Monografia
Esta Monografia está dividida em cinco Capítulos. O Capítulo 1 compreende a introdução
deste trabalho. O Capítulo 2 apresenta conceitos, definições e ferramentas utilizados ao longo
do texto e do trabalho. O Capítulo 3 apresenta as técnicas de controle utilizadas bem como a
sua implementação. O Capítulo 4 contém a descrição dos experimentos realizados e a análise
dos resultados obtidos. O Capítulo 5 trata das conclusões gerais e apresenta sugestões para
trabalhos futuros.
15
2
Definições, nomenclatura e
ferramentas
O objetivo deste capítulo é apresentar os conceitos, definições, metodologias e ferramentas que serão utilizados ao longo desta monografia. Na primeira seção define-se o espaço de
configurações. Na segunda seção, apresentam-se os campos potenciais artificiais que são utilizados na navegação de robôs. Por fim, é apresentada a Hidrodinâmica de Partículas Suavizadas,
técnica esta utilizada para a coordenação de enxames robóticos.
2.1 Espaço de Configurações
O espaço de trabalho W de um robô R compreende a região do mundo que ele pode, a
princípio, alcançar. No caso de robôs móveis, usualmente têm-se espaços de trabalho em duas
dimensões (2D) e três dimensões (3D). Normalmente, há algumas regiões proibidas dentro de
W que são chamadas obstáculos, O = {O1 , O2 , . . . , On }.
Já o espaço de configurações corresponde a um formalismo matemático para representar o
robô e seu espaço de trabalho. A configuração q de um robô R é um vetor capaz de caracterizar
completamente a localização de R em W. Por exemplo, considere a Figura 2.1, onde um robô
móvel, representado por um ponto de referência G, navega em uma superfície plana. A configuração q = [x, y, θ ]T do robô é composta pelas coordenadas x e y de G e a orientação θ do robô.
Por conseguinte, o espaço de configuração C é o conjunto de todas as configurações possíveis
do robô.
Os obstáculos são representados no espaço de configurações do robô como um conjunto de
configurações proibidas, Cobst . Já o espaço de configurações livre é dado por F = C \ Cobst , ou
seja, o que resta do espaço de configurações após a subtração de Cobst .
16
Figura 2.1: Um robô é representado por um ponto em seu espaço de configurações (PEREIRA,
2003).
2.2 Campos Potenciais Artificiais
Um dos problemas mais estudados na literatura robótica é o problema da navegação, que
consiste em levar um robô R com configuração q de sua configuração inicial, q0 , até a configuração desejada, qd , em um tempo finito, movendo-se apenas em seu espaço de configurações
livre F, ou seja, sem se colidir com obstáculos (LATOMBE, 1991).
Uma das técnicas mais populares para se tratar o problema da navegação é a baseada em
Campos Potenciais Artificiais (KHATIB, 1986). Esta técnica é baseada numa função de potencial, φ (q), que é projetada para ter um mínimo no alvo e um máximo nas fronteiras dos
obstáculos. A idéia chave é usar o gradiente descendente, −∇φ (q), para conduzir o robô até
o destino. O gradiente descendente pode ser tratado como uma força virtual que repele o robô
dos obstáculos e o atrai em direção ao alvo. Como os campos artificiais são definidos para todo
o espaço livre, são determinadas implicitamente trajetórias a partir de qualquer configuração
inicial até o objetivo.
Abordagens tradicionais de campo artificial apresentam o problema do mínimo local na
função de potencial, o que causa problemas na convergência paro o alvo. A Figura 2.2 apresenta
um exemplo de um mínimo local causado pela presença de um obstáculo em forma de U. Como
a força virtual de atração é igual em módulo mas possui sentido contrário à força virtual de
repulsão no ponto onde o robô se encontra, ele fica preso dentro do obstáculo e nunca atinge o
alvo.
Para lidar com este problema, foi desenvolvida uma técnica de construção de potenciais
artificiais sem mínimos locais, denominados funções de navegação (RIMON; KODITSCHEK,
1992). Uma função de navegação é definida como um mapeamento φ : F → [0, 1] que é:
1. suave em F, ou seja, ela possui derivadas de segunda ordem contínuas;
2. polar em qd , isto é, existe um único mínimo, localizado em qd ;
17
Figura 2.2: Mínimo local causado por um obstáculo em forma de U.
3. admissível em F, ou seja, na fronteira de F é uniformemente máxima;
4. uma função de Morse, isto é, os pontos críticos não são degenerados.
Em geral funções de navegação são difíceis de serem calculadas para ambientes genéricos.
De forma a contornar essa limitação, utilizam-se funções harmônicas projetadas de forma a
atender às propriedades das funções de navegação. As funções harmônicas são soluções da
Equação de Laplace, que é dada por
∇2 φ = 0,
(2.1)
onde φ é uma função harmônica e ∇2 é o operador Laplaciano. Para possibilitar o cálculo
das funções harmônicas de forma eficiente para geometrias quaisquer, utiliza-se o Método de
Elementos Finitos (MEF), através do FEMM, Finite Element Method Magnetics. O FEMM é
um conjunto de programas para resolver problemas eletromagnéticos no domínio bidimensional
(MEEKER, 2007). O programa abrange Problemas Magnéticos, Eletrostáticos e de Fluxos de
Calor e Corrente. O FEMM é dividido em três módulos. O primeiro é o módulo de interface,
através do qual o usuário define o seu problema (Figura 2.3). O segundo é composto pelo
programa Triangle (SHEWCHUK, 1996), que é utilizado para gerar uma malha na região de
solução segundo a triangulação de Delaunay. Por fim, há o módulo de resolução do sistema
linear resultante.
Para encontrar a função de navegação, responsável por gerar a força externa que conduz
cada membro do enxame até o alvo, utiliza-se o FEMM. O uso do programa é simples. Primeiramente, define-se o tipo de problema: eletrostático, uma vez que a Equação de Laplace governa
este problema na ausência de cargas. Em seguida, através de pontos e segmentos de retas e de
arcos, desenha-se o mapa. Em seguida, se estabelecem os valores dos potenciais dos compo-
18
Figura 2.3: Programa FEMM: ferramenta para solução numérica de problemas eletromagnéticos.
nentes do mapa: zero para os contornos da região alvo e um valor diferente de zero para os
demais contornos. Então, define-se a propriedade elétrica dos materiais que preenchem o mapa
e gera-se a malha de triângulos (o tamanho da malha pode ser ajustado). Por fim, gera-se a solução do problema: os potenciais para cada vértice dos triângulos que formam a malha. Como
saída, o FEMM gera um conjunto de arquivos com as soluções do problema. Tais arquivos são
utilizados posteriormente como entrada do programa de controle dos robôs.
2.3 Hidrodinâmica de Partículas Suavizadas
A Hidrodinâmica de Partículas Suavizadas1 (HPS) (LIU; LIU, 2003) é uma técnica numérica sem malhas, Lagrangiana, baseada em partículas, que foi primeiramente utilizada para
resolver problemas em astrofísica. Ela é uma técnica baseada em partículas porque utiliza um
conjunto de partículas distribuídas arbitrariamente para representar o estado do sistema. Ela é
sem malhas devido ao fato de que não é necessário gerar uma malha para providenciar a co1 Do
inglês, Smoothed Particle Hydrodynamics (SPH)
19
nectividade das partículas como no caso do método dos elementos finitos ou do método das
diferenças finitas. Ao invés disso, utiliza-se uma função de interpolação. Por fim, a HPS é
considerada um método Lagrangiano porque as partículas não são fixas no espaço enquanto o
material se move. Ao contrário, as partículas são ligadas ao material e se deslocam com o fluxo.
Devido a todas essas características, esta técnica tem sido amplamente utilizada para resolver
problemas de dinâmica de fluidos, nos quais questões como grandes deformações e fronteiras
móveis aparecem com muita freqüência. Na maioria das vezes esses problemas são de difícil
solução quando se adotam outros métodos numéricos, tais como elementos finitos e diferenças
finitas.
A HPS é baseada na representação integral de uma função:
Z
f (x) =
Ω
f (x0 )δ (x − x0 )dx0 ,
onde Ω é o volume que contém x e δ (x − x0 ) é a função delta de Dirac dada por

Z
∞ se x = x0
0
δ (x − x ) =
e
δ (x − x0 )dx0 = 1.
0 se x 6= x0
Ω
(2.2)
(2.3)
Se a função delta for substituída por uma função de suavização W(x−x0 , h), a representação
integral é aproximada por
f (x) ∼
= h f (x)i =
Z
Ω
f (x0 )W(x − x0 , h)dx0 ,
(2.4)
onde h f (x)i é uma aproximação de f (x), W é chamada de função núcleo de suavização2 , núcleo
de suavização ou simplesmente núcleo na literatura HPS, e h é o raio de suavização3 que define
a área de influência de W.
A função núcleo é fundamental na HPS não apenas porque determina como funções devem
ser aproximadas e a dimensão do domínio de suporte das partículas, mas também por derivar
a consistência, e conseqüentemente a precisão, da aproximação das partículas. A escolha do
núcleo deve satisfazer:
Z
Ω
W(x − x0 , h)dx0 = 1
e
lim W(x − x0 , h) = δ (x − x0 ).
h→0
(2.5)
Além disso, a função de suavização deve ser diferenciável, já que seu gradiente é necessário em várias aplicações. Freqüentemente, escolhe-se uma função par e também com suporte
2 Do
3 Do
inglês, smoothing kernel function
inglês, smoothing length
20
compacto controlado pelo parâmetro h. As funções splines cúbicas (MONAGHAN, 1992) satisfazem as propriedades anteriores e para duas dimensões são dadas por:



1 − 32 κ 2 + 34 κ 3 se 0 ≤ κ < 1



10
1
3
W(r, h) =
se 1 ≤ κ < 2 ,
4 (2 − κ )
7π h2 



0
se κ ≥ 2
(2.6)
onde κ = krk/h. O suporte dessa função é dado por 2h. A Figura 2.4 apresenta essa função
quando ela está centrada na origem e o parâmetro h é igual a 1.
Figura 2.4: Gráfico da função núcleo W com h = 1.
A integral contínua em (2.4) pode ser convertida em um somatório de todas as N partículas
no domínio de suporte de x. Isso pode ser feito considerando que uma partícula j tem um
volume ∆V j que está relacionado com a massa m j da partícula por
m j = ∆V j ρ j ,
(2.7)
onde ρ j é a densidade da partícula. Assim, substituindo dx0 por ∆V j , temos que
N
h f (x)i ≈
mj
f (x j )W(x − x j , h).
j=1 ρ j
∑
(2.8)
21
Derivadas espaciais de f podem ser aproximadas. Utilizando integração por partes, é possível escrever a derivada espacial de f em termos do gradiente do núcleo
N
mj
f (x j )∇x W(x − x j , h),
j=1 ρ j
∑
h∇x f (x)i ≈
(2.9)
onde ∇x é o gradiente em relação a x.
É interessante observar que a aproximação por partículas em (2.8) e (2.9) introduz massa e
densidade nas equações. Como a densidade é uma variável chave em problemas hidrodinâmicos, essa aproximação pode ser convenientemente aplicada em muitos problemas. De acordo
com (LIU; LIU, 2003) essa é provavelmente uma das principais razões para que o método HPS
seja popular em problemas de dinâmicas de fluidos.
Três equações governam a dinâmica de fluidos: (i) conservação de massa; (ii) conservação
de momento; e (iii) conservação de energia. Para fluidos compressíveis, na ausência de fluxo de
calor, as equações de conservação HPS resultantes para a partícula i são (MONAGHAN, 1992):
ρj =
∑ m j Wi j ,
(2.10)
j=1
dvi
= − ∑ mj
dt
j=1
dei 1
=
dt
2
Ã
Ã
∑ mj
j=1
!
Pj
Pi
+
+ Πi j ∇i Wi j + fi ,
ρi2 ρ 2j
(2.11)
!
Pj
Pi
+
+ Πi j vi j · ∇i Wi j ,
ρi2 ρ 2j
(2.12)
onde Wi j = W(xi − x j , h), v é a velocidade, vi j = vi − v j , fi é a soma das forças externas normalizada pela massa mi , P é pressão hidrostática e e é a energia interna por unidade de massa. O
termo Πi j é uma viscosidade artificial adicionada para lidar com choques e pode ser dada por:


Πi j =
1
2
ρi j (−ξ1 ci j µi j + ξ2 µi j )
0
se vi j · xi j < 0
,
(2.13)
se vi j · xi j ≥ 0
onde
µi j =
hvi j · xi j
.
kxi j k2 + η 2
(2.14)
Em (2.13), ρi j é a média entre as densidades das partículas i e j, ξ1 e ξ2 são constantes de
viscosidade e ci j é a média das velocidades do som. Em (2.14), η 2 é um termo para evitar singularidades. Ele deve ser pequeno o suficiente para evitar grandes suavizações na viscosidade.
Usualmente, η 2 é feito igual a 0,01h2 .
22
A modelagem de fluidos incompressíveis pode ser feita utilizando a seguinte equação de
estado (MONAGHAN, 1994):
·µ
Pi = Bi
ρi
ρ0
¶γ
¸
−1 ,
(2.15)
onde ρ0 é a densidade de referência (1000 Kg/m3 no caso da água), γ é uma constante relacionada a calores específicos e Bi é o chamado módulo Bulk. Este módulo está relacionado à
compressibilidade do fluido e pode representado por (ROY, 1995):
Bi =
200ρi gH
,
γ
(2.16)
onde H é a profundidade máxima do fluido e g é a constante gravitacional.
A velocidade do som na partícula i, que representa a velocidade com que o som se propaga
através do elemento de fluido representado pela partícula, é dada por (ROY, 1995):
s
γ (Pi + Bi )
ci =
.
ρi
(2.17)
Essas são as equações base no que se refere a HPS para se utilizar a abordagem baseada em
fluidos para o controle de enxame de robôs (PIMENTA, 2009). Maiores detalhes sobre a HPS
e as equações apresentadas nesta seção podem ser encontrados em (LIU; LIU, 2003).
23
3
Coordenação de Enxames Utilizando
Modelos de Dinâmica dos Fluidos
Neste capítulo é apresentado um problema clássico de coordenação de enxames robóticos,
sua solução via modelos de dinâmica dos fluidos e a implementação do controlador. Na primeira
seção, definem-se o problema de geração de padrões, assim como sua solução. Na segunda
seção, fazem-se considerações acerca de restrições práticas do mundo real. Por fim, apresentamse detalhes da implementação do controlador.
3.1 O Problema de Geração de Padrões
O problema de geração de padrões pode ser definido como (PIMENTA, 2009):
Problema 3.1. Seja um grupo de N robôs com distribuição espacial inicial qualquer e o ambiente com obstáculos estáticos definindo um domínio compacto Ω ⊂ R2 e uma curva Γ : I → Ω,
onde I ⊂ R. Encontre um controlador que guie os robôs para formar o padrão descrito por Γ
sem colidir uns com os outros e sem colidir com os obstáculos estáticos.
Para simplificar o problema, o autor faz duas considerações. Primeiro, que o número de
robôs é suficientemente grande para aproximar-se adequadamente o padrão desejado e, ao
mesmo tempo, é suficientemente pequeno para garantir que haja espaço ao longo da curva
para todos os robôs. A segunda consideração é que os robôs são capazes de estimar posições e
velocidades deles mesmos e de outros robôs do grupo localizados a uma distância D.
Para resolver esse problema, considera-se que cada robô do time é uma partícula HPS
sujeita a uma força externa. Como as funções núcleo possuem suporte compacto, é possível
derivar leis de controle descentralizadas baseadas nas equações da HPS. Os controladores são
descentralizados no sentido de que apenas informação local é necessária: o campo externo na
posição do robô e posições e velocidades de robôs vizinhos. Para um robô i com configuração
24
qi = [xi , yi ]T , os robôs vizinhos são definidos como aqueles no conjunto de vizinhança Ni :
Ni = { j 6= i | kq j − qi k < D},
(3.1)
onde a distância D é determinada pelo tamanho do suporte da função núcleo.
Além disso, assume-se, inicialmente, que os robôs são pontuais e holonômicos com modelo
dado por:
q̈i = ui (q, q̇,t),
(3.2)
onde q = [qT1 , . . . , qTN ]T é a configuração do grupo.
Então, para resolver o problema de geração de padrões, (PIMENTA, 2009) propõem o
controlador:
ui (q, q̇) = k1 bi − k2 vi + k3 fi ,
(3.3)
onde k1 , k2 e k3 são constantes positivas de ajuste e
!
Ã
Pj
Pi
bi = − ∑ m j
+
+ Πi j ∇i Wi j ,
ρi2 ρ 2j
j
fi =

− ∇φ (qi )
k∇φ (q )kβ
se ∇φ (qi ) 6= 0

0
se ∇φ (qi ) = 0
i
,
(3.4)
(3.5)
onde β é um número inteiro não-negativo.
Em (3.3), o termo bi , baseado nas equações HPS, é utilizado para controlar as interações
entre os robôs com o objetivo de se evitar colisões e fazer com que o enxame siga uma densidade
de referência. O termo k2 vi é dissipativo, vi é a velocidade do robô, e contribui para melhorar a
estabilidade do sistema. Por fim, o termo fi é responsável por guiar os robôs até o destino.
Deve-se mencionar que ui (q, q̇) em (3.3) pode ser calculado levando-se em consideração
apenas os robôs na vizinhança definida por Ni em (3.1). Isso acontece devido ao suporte compacto da função núcleo, W, que garante que os robôs fora da vizinhança em questão não contribuam para o somatório em (3.4).
3.2 Considerações Práticas
Devem-se realizar adaptações na solução para o problema de geração de padrões apresentada na seção anterior, de modo que ela possa ser implementada em robôs reais (PIMENTA,
2009). As considerações feitas são apresentadas a seguir.
25
Robôs não pontuais
O fato dos robôs reais não serem pontuais é tratado por meio de uma adaptação da viscosidade artificial, (2.13), página 21, uma vez que este termo garante termos repulsivos que evitam
colisões entre partículas. A adaptação é dada por:
µi j =
hvi j · qi j
,
(kqi j k − (2R + ε ))2
(3.6)
onde R é o raio do robô e ε é um fator de segurança.
Restrições não-holonômicas
As restrições não-holonômicas são tratadas através da técnica de linearização por realimentação de estados:
" #
υ
"
# " #
cos(θ ) sin(θ )
x˙d
=
·
,
ω
− sin(dθ ) cos(d θ )
y˙d
(3.7)
onde υ é a velocidade linear, ω é a velocidade angular e d é a distância do ponto de referência
da linearização ao centro do robô. O vetor de entrada [x˙d , y˙d ]T corresponde às velocidades
desejadas e para obtê-las é necessário integrar a aceleração calculada pelo controlador em (3.3).
Partículas virtuais
As partículas virtuais são colocadas sobre as fronteiras dos obstáculos. Tais partículas são
utilizadas para garantir que não existam colisões entre robôs e obstáculos, uma vez que as forças
externas podem ser insuficientes para evitar tais colisões.
3.3 Implementação do controlador
O controlador para os agentes do enxame foi escrito na linguagem de programação C++.
Como o objetivo é obter um controle descentralizado, o programa foi escrito para que todos os
robôs rodassem o mesmo código, sem a necessidade de um servidor central. Assim, além das
Classes que representam o método HPS e o Campo Vetorial, foi necessário implementar uma
forma de comunicação descentralizada entre os clientes.
Para se guiar, cada robô do enxame necessita de dois conjuntos de informações: o seu
campo vetorial e algumas propriedades HPS de seus vizinhos. Para se informar sobre o campo
vetorial, todos os robôs tem acesso a um mesmo mapa, gerado pelo FEMM. Já para receber e
26
enviar informações aos seus vizinhos, a estratégia utilizada foi um broadcast através de socket
UDP1 .
Quando o controlador é inicializado, cria-se uma thread, através da biblioteca boost, para
ficar recebendo as mensagens enviadas pelo enxame. O motivo de se utilizar um processo independente para receber informações é que os cálculos do controlador podem ser feitos concorrentemente. Quando um robô recebe um pacote de dados de outro membro, a primeira providência
é verificar se o remetente da mensagem está na vizinhança do robô. Caso não esteja, o pacote
é descartado. Essa foi a forma utilizada para simular o fato de que as interações entre os robôs
se limitam ao seu raio de ação. Dentre as informações que são trocadas entre os robôs, têm-se
os seguintes atributos: o identificador do robô, a posição (x, y), a velocidade (ẋ, ẏ), a massa, a
densidade e a pressão.
Figura 3.1: Diagrama representativo do controlador.
O diagrama da Figura 3.1 representa o funcionamento do controlador descentralizado. Para
instanciar o controlador, é necessário passar como parâmetro o identificador do robô. Em seguida, cria-se a malha, o fluido e as conexões. Para receber dados de broadcast, um processo
é criado. Então, dois processos ficam executando ciclicamente: o controlador (Figura 3.1 à
esquerda), que realiza os cálculos, e o receptor de dados (Figura 3.1 à direita), que recebe os
pacotes UDP de broadcast e atualiza a lista de vizinhos do robô.
1 User
Datagram Protocol
27
4
Simulações e Experimentos
Neste capítulo apresentam-se o simulador e a plataforma experimental utilizada, bem como
os resultados experimentais obtidos para o problema de geração de padrões. Três mapas diferentes foram propostos. Os vídeos dos experimentos apresentados neste capítulo encontram-se
no site http://www.cpdee.ufmg.br/~lucpim/mateusmb/.
4.1 Player/Stage
O Projeto Player oferece ferramentas de Software Livre para aplicações de robótica móvel,
especialmente em sistemas multi-robôs (GERKEY; VAUGHAN; HOWARD, 2003). O Player
proporciona uma interface de rede para uma variedade de sensores e robôs. O modelo cliente /
servidor do Player permite que programas para o controle de robôs sejam escritos em qualquer
linguagem de programação e rodem em qualquer computador que esteja conectado ao robô. O
Player suporta múltiplas conexões de clientes concorrentes, oferecendo a possibilidade para o
controle distribuído.
Para a realização de simulações, o Projeto Player oferece duas ferramentas: o Stage (Figura
4.1), para simulações em 2D, e o Gazebo, para simulações em 3D. Como o espaço de configurações deste trabalho é em duas dimensões, utilizou-se o Stage para a realização das simulações.
Entre as vantagens de se utilizar simuladores como Stage antes da implementação em robôs
reais, pode-se citar a necessidade de um tempo menor para o ajuste do controlador, o menor
desgaste dos acionamentos dos robôs e a facilidade para a transição simulação/experimento, já
que toda a comunicação é realizada via rede (é transparente se o controlador está conectado a
um robô de simulação ou um robô real).
As simulações realizadas neste trabalho foram utilizadas principalmente para se determinar
os valores das constantes do controlador (Tabela 4.1). Após esta etapa, foram realizados experimentos sem alterações nestes parâmetros e sem praticamente nenhuma alteração no código
do controlador: modificou-se o sistema de localização, para que câmeras (Seção 4.2.2) fossem
28
Figura 4.1: Stage: uma ferramenta para simulação utilizada na robótica.
utilizadas.
Tabela 4.1: Parâmetros do controlador
Parâmetro
k1
k2
k3
h
R
ε
d
ξ1
ξ2
γ
ρ0
m
H
Valor
0,001
1,5
0,04
11,6 cm
3,5 cm
3,5 mm
7 mm
1
2
1
1000 Kg/m3
26,33 Kg
0,01 m
29
4.2 Plataforma Experimental
4.2.1
E-pucks
Os e-pucks são robôs projetados para auxiliarem o ensino em disciplinas relacionadas à
robótica móvel (MONDADA et al., 2009). Alguns de seus componentes são: uma câmera com
resolução de 640x480 pixels, oito sensores infra-vermelho, dez LEDs, três microfones, um altofalante, um acelerômetro 3D, dois motores de passo, e duas portas seriais, sendo que uma delas
está ligada a um dispositivo bluetooth. O e-puck contém um dcPIC modelo 30F6014A, que é
programável por meio da interface bluetooth.
Figura 4.2: Dois e-pucks do VeRLab(GARCIA, 2008).
Para a realização de experimentos de enxames robóticos, o VerLab possui 12 e-pucks, como
os da Figura 4.2. Uma das formas de se construir programas para controlá-los é através da
biblioteca disponível em seu site oficial http://www.e-puck.org/. Entretanto, essa opção
apresenta algumas desvantagens, entre elas estão a capacidade limitada do dsPIC (64 MHz de
processamento, 8kB de RAM e 144 kB de memória flash) quando comparado a um PC, a única
linguagem de programação disponível é C, e o código dos programas que forem feitos não será
portável para outros robôs.
Uma forma de contornar estes problemas é construir o programa utilizando o Player. Foi
desenvolvido no VerLab um driver do Player para os e-pucks. Em (GARCIA, 2008), o autor
explica como utilizar o driver desenvolvido nos e-pucks. Dessa forma, o controlador roda em
PCs e se comunica com o driver do e-puck via dispositivo bluetooth.
4.2.2 Sistema de Localização
A localização na robótica móvel através da odometria apresenta limitações, pois é comum
que as rodas do robô derrapem devido a, por exemplo, pisos irregulares ou escorregadios e
30
grandes acelerações. Caso o mapa de navegação seja conhecido, pode-se combinar a odometria
com métodos probabilísticos para se estimar a posição do robô. Entretanto, isso requer alta
capacidade sensorial e computacional. No caso de ambientes externos, pode-se utilizar também
o GPS1 .
Figura 4.3: Sistema de localização por câmeras do VerLab (GARCIA et al., 2007).
Para a realização de experimentos com os e-pucks no VerLab, foi desenvolvido um arcabouço para a localização de enxames (GARCIA et al., 2007; GARCIA; CHAIMOWICZ, 2009),
como mostra o diagrama da Figura 4.32 . Ele é composto por um conjunto de câmeras fixado
sobre a área de trabalho e um sistema de software, Silvver (SILVVER, 2009), capaz de localizar
e identificar os robôs através de marcos geométricos (biblioteca ARToolkitPlus) colocados sobre
eles (Figura 4.4). Cada câmera possui uma calibração intrínseca (foco, distorção radial, etc) e
uma calibração extrínseca (matriz de transformação de coordenadas). A calibração intrínseca
foi feita utilizando-se a biblioteca OpenCV.
Figura 4.4: Exemplos de marcos visuais da biblioteca ARToolkitPlus (GARCIA et al., 2007).
1 Global
2 Projeto
Positioning System
parcialmente financiado com recursos do CNPq e da Fapemig
31
4.3 Experimentos realizados
Para a realização dos experimentos de geração de padrão com os 12 e-pucks, três tipos de
mapas foram propostos. As Figuras 4.5, 4.6 e 4.7 ilustram esses mapas, com suas malhas e
campos vetoriais, obtidos via FEMM. O primeiro mapa, Figura 4.5, foi construído para que o
enxame se espalhasse ao longo da região em forma de estrela. No segundo e terceiro mapa,
Figuras 4.6 e 4.7, o enxame deveria preencher uma região alvo circular (raio de 30 cm ± 2,5
cm). Enquanto o segundo mapa contém dois obstáculos retangulares (55 x 2,5 cm), um de cada
lado, o terceiro mapa contém apenas um obstáculo (também de 55 x 2,5 cm).
Figura 4.5: Espaço de configurações, malha e campo elétrico do primeiro mapa.
4.3.1 Experimentos com o primeiro mapa
No primeiro mapa, Figura 4.5, foram realizados experimentos com três configurações iniciais diferentes: 12 e-pucks no interior da estrela; 12 e-pucks no exterior da estrela; e 6 e-pucks no
interior e 6 no exterior da estrela. Todos os experimentos apresentaram resultados semelhantes
e por isso apenas o terceiro caso será descrito aqui.
A Figura 4.8 apresenta uma seqüência de imagens que ilustra a evolução do experimento.
A Figura 4.9 apresenta a trajetória dos e-pucks segundo o sistema a localização por câmeras. A
Figura 4.10 contém a densidade dos e-pucks ao longo do experimento. Como pode-se observar
32
Figura 4.6: Espaço de configurações, malha e campo elétrico do segundo mapa.
Figura 4.7: Espaço de configurações, malha e campo elétrico do terceiro mapa.
33
nas Figura 4.8d e 4.9, o enxame alcançou a região alvo. Já na Figura 4.10, vê-se que a densidade
converge para valores ao redor do valor de referência (1000 Kg/m3 ). Não houve colisões entre
os membros do enxame.
(a)
(b)
(c)
(d)
Figura 4.8: Evolução do experimento no primeiro mapa: (a) 0%. (b) 33%. (c) 67%. (d) 100%.
4.3.2 Experimentos com o segundo mapa
No segundo mapa, Figura 4.6, foram realizados experimentos com a seguinte configuração
inicial: 6 e-pucks do lado direito e 6 do lado esquerdo.
A Figura 4.11 apresenta uma seqüência de imagens que ilustra a evolução do experimento.
A Figura 4.12 apresenta a trajetória dos e-pucks segundo o sistema a localização por câmeras. A
Figura 4.13 contém a densidade dos e-pucks ao longo do experimento. Como pode-se observar
nas Figura 4.11d e 4.12, o enxame alcançou a região alvo. Já na Figura 4.13, vê-se que a
densidade converge para valores ao redor do valor de referência (1000 Kg/m3 ). Não houve
colisões entre os membros do enxame e, como mostra a Figura 4.12, também não houve colisões
com os obstáculos.
34
Figura 4.9: Trajetória descrita pelo enxame no primeiro mapa.
Figura 4.10: Densidade dos robôs ao longo do experimento no primeiro mapa.
35
(a)
(b)
(c)
(d)
Figura 4.11: Evolução do experimento no segundo mapa: (a) 0%. (b) 33%. (c) 67%. (d) 100%.
Figura 4.12: Trajetória descrita pelo enxame no segundo mapa.
36
Figura 4.13: Densidade dos robôs ao longo do experimento no segundo mapa.
4.3.3 Experimentos com o terceiro mapa
No terceiro mapa, Figura 4.7, foram realizados experimentos com a seguinte configuração
inicial: os 12 e-pucks lado direito, atrás do obstáculo.
A Figura 4.14 apresenta uma seqüência de imagens que ilustra a evolução do experimento.
A Figura 4.15 apresenta a trajetória dos e-pucks segundo o sistema a localização por câmeras. A
Figura 4.16 contém a densidade dos e-pucks ao longo do experimento. Como pode-se observar
nas Figura 4.14d e 4.15, o enxame alcançou a região alvo. Já na Figura 4.16, vê-se que a
densidade converge para valores ao redor do valor de referência (1000 Kg/m3 ). Não houve
colisões entre os membros do enxame e, como mostra a Figura 4.15, também não houve colisões
com os obstáculos.
4.3.4 Análise
Nos experimentos realizados, as iterações do controlador ocorriam a uma taxa de aproximadamente 10 Hz. Os e-pucks, durante os experimentos, deslocavam-se em uma mesa de
aproximadamente 1,5 x 0,9 m. Como os desenhos dos mapas feitos na mesa foram do espaço
de configuração (e não do espaço de trabalho), controlava-se o centro dos robôs. Ou seja, apenas
o centro dos robô não poderia colidir com os obstáculos.
37
(a)
(b)
(c)
(d)
Figura 4.14: Evolução do experimento no terceiro mapa: (a) 0%. (b) 33%. (c) 67%. (d) 100%.
Figura 4.15: Trajetória descrita pelo enxame no terceiro mapa.
38
Figura 4.16: Densidade dos robôs ao longo do experimento no terceiro mapa.
Conforme já mencionado, todos os experimentos foram realizados com sucesso: o enxame
alcançou e manteve o padrão desejado, a densidade dos robôs convergiu para valores ao redor
do valor de referência e não houve colisões entre os membros do enxame e nem do centro dos
robôs com os obstáculos.
Para realizar a comunicação entre o computador que executava o código do controlador e
o driver que rodava nos e-pucks, utilizou-se dois dispositivos bluetooth (cada um suporta até 7
conexões). Uma das maiores dificuldades da experimentação foi essa comunicação: algumas
vezes era difícil estabelecer uma conexão, outras vezes a comunicação falhava durante o experimento. Acredita-se que este problema possa estar relacionado a duas causas: a rede wireless
do VeRLab e/ou ao código do Player para o e-puck.
Outra dificuldade encontrada na parte experimental foi a calibração intrínseca das câmeras. Após o processamento das imagens capturadas pela câmera, ainda havia uma distorção
considerável. A Figura 4.17 apresenta uma sequência de imagens representando as trajetórias
em quatro experimentos realizados com o segundo mapa. Como pode-se observar, há uma
maior dispersão dos pontos nas partes esquerda das imagens. Isso era esperado devido a essa
dificuldade de calibração. Apesar disso, os experimentos não foram comprometidos.
Conforme mencionado na seção 4.2.2, utilizar apenas a odometria dos robôs como forma
de localização pode acarretar em grandes erros. A Figura 4.18 reforça esse fato.
39
Figura 4.17: Sequência de imagens de experimentos no segundo mapa evidenciando as dificuldades de calibração da câmera.
Figura 4.18: Localização dos robôs baseada na odometria em um experimento com o segundo
mapa.
40
5
Conclusões
Neste trabalho implementou-se uma técnica de controle de enxames de robôs baseada na
Hidrodinâmica de Partículas Suavizadas (HPS) e no Método de Elementos Finitos. Os experimentos realizados utilizaram 12 robôs e-pucks, um sistema de localização por câmeras e o
Player como interface entre o hardware dos robôs e o código do controlador. A comunicação
do controlador, implementado num computador, com os e-pucks se deu através de dispositivos bluetooth. Simulações para o ajuste dos parâmetros do controlador foram feitas através do
Stage. Foram realizados experimentos em três tipos de mapas. Em todos, buscou-se resolver
problemas de geração de padrões. Os experimentos foram bem sucedidos, tendo em vista que
a região alvo foi alcançada pelos e-pucks, a densidade do enxame convergiu para uma densidade próxima da referência e não houve colisões entre os membros do enxame nem do enxame
com os obstáculos. Com isso, a técnica de controle baseada na HPS estudada nesta monografia
mostrou-se eficaz para a coordenação de enxames robóticos.
Durante a implementação do controlador nos enxames, houve algumas dificuldades. Primeiramente, foi difícil conseguir uma calibração intrínseca das câmeras do sistema de localização. Posteriormente, ocorreram problemas de comunicação (via bluetooth) entre o computador
que executava o controlador e os e-pucks. Entretanto, essas dificuldades não impediram que os
experimentos fossem realizados com sucesso.
Para trabalhos futuros, sugere-se que sejam realizados experimentos em mapas maiores
(substituir a mesa onde o enxame se desloca por outra de tamanho maior), possibilitando que os
robôs percorram trajetórias maiores e complexas até atingirem o alvo. Além disso, pode-se tentar melhorar o sistema de localização por câmeras combinando-o com o sistema de localização
por odometria dos e-pucks.
41
Referências Bibliográficas
BLUM, C.; LI, X. Swarm intelligence. In:
. [S.l.]: Springer Berlin Heidelberg, 2008.
(Natural Computing Series), cap. Swarm Intelligence in Optimization, p. 43 – 85.
DORIGO, M. et al. SWARM-BOT: Design and Implementation of Colonies of SelfAssembling Robots. In: Computational Intelligence: Principles and Practice. New York:
IEEE Computational Intelligence Society, 2006.
EU-MOP. Elimination Units for Marine Oil Pollution. 2009. http://www.eumop.org/.
Acessado em maio, 2009.
FRITSCH, D.; WEGENER, K.; SCHRAFT, R. Control of a robotic swarm for the
elimination of marine oil pollutions. Swarm Intelligence Symposium, 2007. SIS 2007.
IEEE, p. 29 – 36, Abril 2007. Disponível em: <http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4223152&isnumber=4223144>.
GARCIA, R. F. E-puck Tutorial. 2008.
GARCIA, R. F.; CHAIMOWICZ, L. Uma infra-estrutura para experimentação com enxames
de robôs. In: SBAI2009. Brasília, DF - Brasil: [s.n.], 2009.
GARCIA, R. F. et al. Um arcabouço para a localização de enxames de robôs. In: SBAI2007.
Florianópolis, SC - Brasil: [s.n.], 2007.
GERKEY, B. P.; VAUGHAN, R. T.; HOWARD, A. The player/stage project: Tools for
multi-robot and distributed sensor systems. In: In Proceedings of the 11th International
Conference on Advanced Robotics. [s.n.], 2003. p. 317–323. Disponível em: <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.3914>.
KHATIB, O. Real-time obstacle avoidance for manipulators and mobile robots. International
Journal of Robotics Research, Sage Publications, Inc., Thousand Oaks, CA, USA, v. 5, n. 1, p.
90–98, 1986. ISSN 0278-3649.
LATOMBE, J. Robot Motion Planning. Boston, MA: Kluwer Academic Publishers, 1991.
LIU, G. R.; LIU, M. B. Smoothed Particle Hydrodynamics - a meshfree particle method. [S.l.]:
World Scientific Publishing Company, 2003.
MARCOLINO, L. S.; CHAIMOWICZ, L. Advances in artificial intelligence - sbia 2008. In:
. [S.l.]: Springer Berlin / Heidelberg, 2008. (Lecture Notes in Computer Science), cap.
Experiments in the Coordination of Large Groups of Robots, p. 268 – 277.
MEEKER, D. Finite Element Method Magnetics - Version 4.2 - User’s Manual. 2007.
MONAGHAN, J. J. Smoothed particle hydrodynamics. Annual Review of Astronomy and
Astrophysics, v. 30, p. 543–574, Setembro 1992.
42
MONAGHAN, J. J. Simulating free surface flows with sph. J. Comput. Phys., Academic Press
Professional, Inc., San Diego, CA, USA, v. 110, n. 2, p. 399–406, 1994. ISSN 0021-9991.
MONDADA, F. et al. The e-puck, a Robot Designed for Education in Engineering. In:
GONçALVES, P.; TORRES, P.; ALVES, C. (Ed.). Proceedings of the 9th Conference on Autonomous Robot Systems and Competitions. Portugal: IPCB: Instituto Politécnico de Castelo Branco, 2009. v. 1, n. 1, p. 59–65. Disponível em: <http://www.est.ipcb.pt/robotica2009/>.
PEREIRA, G. A. S. Motion Planning and Control of Cooperating Mobile Robots: A Graph
Connectivity Approach. Tese (Tese de Doutorado) — Universidade Federal de Minas Gerais,
Ciência da Computação, Belo Horizonte, 2003.
PIMENTA, L. C. A. Techniques for Controlling Swarms of Robots. Tese (Tese de Doutorado)
— Universidade Federal de Minas Gerais, Departamento de Engenharia Elétrica, Belo
Horizonte, 2009.
RIMON, E.; KODITSCHEK, D. Exact robot navigation using artificial potential functions.
Robotics and Automation, IEEE Transactions on, v. 8, n. 5, p. 501–518, Outubro 1992. ISSN
1042-296X.
ROY, T. M. Physically-Based Fluid Modeling using Smoothed Particle Hydrodynamics.
Dissertação (Master’s thesis) — University of Illinois at Chicago, Chicago, Illinois, 1995.
SAHIN, E. et al. Swarm intelligence. In:
. [S.l.]: Springer Berlin Heidelberg, 2008.
(Natural Computing Series), cap. Swarm Robotics, p. 87 – 100.
SHEWCHUK, J. R. Triangle: Engineering a 2d quality mesh generator and delaunay
triangulator. In:
. Applied Computational Geometry: Towards Geometric Engineering.
Berlin: Springer-Verlag, 1996. (Lecture Notes in Computer Science, v. 1148), p. 203–222.
Disponível em: <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.9874>.
SILVVER. Sistema de Localização por Visão VerLab. 2009. http://code.google.com/p/
silvver/. Acessado em setembro, 2009.
SWARM-BOTS. Swarm-bots project. 2009. http://www.swarm-bots.org/. Acessado em
maio, 2009.
TRIANNI, V.; NOLFI, S.; DORIGO, M. Cooperative hole avoidance in a swarm-bot. Robotics
and Autonomous Systems, v. 54, n. 2, p. 97 – 103, 2006. ISSN 0921-8890. Intelligent
Autonomous Systems. Disponível em: <http://www.sciencedirect.com/science/article/B6V164HNSB6B-1/2/60a4a10722f9c7299fe505051feb2712>.