Controle de Tr´afego para um Enxame de Robˆos

Leandro Soriano Marcolino
Controle de Tráfego para um Enxame de Robôs
Belo Horizonte
2008/1
Leandro Soriano Marcolino
Controle de Tráfego para um Enxame de Robôs
Monografia apresentada como requisito da
disciplina Projeto Orientado em Computação
I do Curso de Bacharelado em Ciência da
Computação da UFMG.
Orientador:
Luiz Chaimowicz
U NIVERSIDADE F EDERAL DE M INAS G ERAIS
I NSTITUTO DE C I ÊNCIAS E XATAS
D EPARTAMENTO DE C I ÊNCIA DA C OMPUTAÇ ÃO
C URSO DE BACHARELADO EM C I ÊNCIA DA C OMPUTAÇ ÃO
Belo Horizonte
2008/1
Prof. Dr. Luiz Chaimowicz
Orientador
“The end is nothing; the road is all.”
Willa Cather
Resumo
Um enxame de robôs é composto por um grande número de robôs simples que trabalham
de forma coordenada para realizar uma determinada tarefa. Em geral, os membros do grupo devem trabalhar de forma distribuı́da e utilizar somente comunicação local. Durante a navegação
de um enxame, muitas vezes acontecem congestionamentos: um grande número de robôs se
dirige para a mesma região do ambiente em um mesmo intervalo de tempo, causando disputas
que desperdiçam tempo e recursos. Neste trabalho, é proposto um método de coordenação distribuı́da para evitar congestionamentos durante a navegação de um enxame. São apresentadas
simulações que demonstram a eficácia do algoritmo para dois e para quatro grupos de robôs que
se movimentam em direções opostas. Além disso, foram realizados experimentos em simulação
para analisar a escalabilidade do algoritmo proposto e para comparar o método com o uso exclusivo de forças locais de repulsão. Os resultados mostraram que o algoritmo proposto permite
uma melhor navegação do enxame, e deve ser escalável para um grande número de robôs.
Palavras-chave: Enxames, Coordenação Multi-Robô, Coordenação Distribuı́da, Inteligência
Artificial, Robótica
Abstract
A swarm of robots can be defined as a large number of simple robots that work together to
accomplish a certain task. Generally, a swarm must work in a distributed way and use only local
communication. During swarm navigation, congestion often happens: a large number of robots
move towards the same region of the environment in the same time interval, causing conflicts
that waste time and resources. In this work, we propose a distributed coordination method to
avoid congestion during swarm navigation. Simulations are presented to show the efficacy of
the algorithm in situations where two or four groups of robots move in opposite directions.
We also ran simulations to analyze the scalability of the proposed algorithm and to compare
the method with the exclusive use of local repulsion forces. Results show that the proposed
algorithm allows the swarm to have a smoother navigation, and might be scalable to a large
number of robots.
Keywords: Swarms, Multi-Robot Coordination, Distributed Coordination, Artificial Inteligence, Robotics
Sumário
Lista de Figuras
Lista de Tabelas
1
Introdução
2
Referencial Teórico
p. 11
3
Metodologia
p. 14
3.1
p. 14
Coordenação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 9
4
Resultados e Discussão
p. 17
5
Conclusões e Trabalhos Futuros
p. 23
Referências Bibliográficas
p. 24
Lista de Figuras
1.1
Exemplo de uma situação onde ocorrem congestionamentos durante a navegação
de um enxame. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 10
3.1
Passos da execução do algoritmo de coordenação proposto . . . . . . . . . .
p. 15
3.2
Controlador utilizado pelo robô para evitar um congestionamento. . . . . . .
p. 16
4.1
Execução com dois grupos utilizando forças de repulsão locais. . . . . . . . .
p. 18
4.2
Execução com dois grupos utilizando o algoritmo de coordenação. . . . . . .
p. 18
4.3
Execução com quatro grupos utilizando o algoritmo de coordenação. . . . . .
p. 20
4.4
Tempo utilizado pelos dois algoritmos. As barras indicam o desvio padrão
4.5
dos resultados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 21
Número de mensagens utilizadas para um número crescente de robôs. . . . .
p. 22
Lista de Tabelas
4.1
Principais constantes utilizadas. . . . . . . . . . . . . . . . . . . . . . . . .
p. 17
9
1
Introdução
Grandes grupos de robôs têm recebido muita atenção recentemente. Geralmente chamados
de enxames, esses sistemas utilizam um grande número de agentes simples para realizar as
mais diversas tarefas. Em geral, enxames de robôs devem trabalhar de forma distribuı́da e
usar recursos limitados de comunicação. Devido a essas caracterı́sticas, novos algoritmos para
controlar e coordenar esses grandes grupos de robôs têm sido desenvolvidos.
Umas das principais caracterı́sticas desejadas ao se desenvolver um algoritmo para um enxame é a escalabilidade. É necessário que o algoritmo possa ser executado com um número arbitrário de robôs. Para se atingir a escalabilidade, deve-se, em geral, utilizar apenas comunicação
local. Também é importante que o algoritmo seja tolerante a falhas: durante a navegação de
um número muito grande de robôs podem ocorrer, por exemplo, falhas de hardware em alguns
robôs. Geralmente, portanto, as soluções devem ser distribuı́das, sem depender de uma entidade
central.
Durante a realização de uma determinada tarefa, um enxame de robôs deve navegar no
ambiente. A navegação de um enxame consiste na movimentação dos robôs no ambiente, de
forma a atingir um determinado alvo. Normalmente, deseja-se que a navegação seja o mais
eficiente e o mais confiável possı́vel.
Uma das dificuldades encontradas durante a navegação de um enxame é o congestionamento: um grande número de robôs se dirige para a mesma região do ambiente em um mesmo
intervalo de tempo, causando disputas que desperdiçam tempo e recursos. Esse problema pode
acontecer tanto quando a região de congestionamento é um alvo para vários robôs, por exemplo
durante a navegação por waypoints, como também quando grupos de robôs se movimentam em
direções contrárias e por acaso se encontram durante a navegação.
Assim, pode-se perceber que soluções para realizar o controle de tráfego são de grande
importância para diminuir o desperdı́cio de tempo e recursos causados pelo congestionamento
durante a navegação de um enxame. Durante as simulações realizadas em [1], por exemplo,
observou-se um grande congestionamento quando os robôs se dirigiam ao mesmo waypoint ao
1 Introdução
10
Figura 1.1: Exemplo de uma situação onde ocorrem congestionamentos durante a navegação de
um enxame.
serem resgatados. Também foram observados congestionamentos quando um robô de resgate
se movimentava no ambiente em busca de robôs presos, mas acabava se encontrando com um
grande número de robôs se movimentando na direção oposta. Na Figura 1.1 pode ser vista uma
cena das simulações realizadas no trabalho onde essas duas situações acontecem: um robô de
resgate (representado por um triângulo apontado para a esquerda, na região inferior da imagem)
se movimenta em busca de robôs presos, enquanto um grande número de robôs se movimenta na
direção oposta, prejudicando a navegação do robô. Enquanto isso, vários robôs tentam chegar
no mesmo waypoint, localizado na região inferior do obstáculo. Essas situações aumentam
muito o tempo de convergência dos robôs.
O objetivo deste trabalho, portanto, é investigar e desenvolver metodologias para realizar o
controle de tráfego de um enxame de robôs. Pretende-se analisar e avaliar as soluções desenvolvidas através de simulações. Para isso, será utilizado o Player/Stage [2], um framework muito
popular em robótica. As soluções desenvolvidas neste trabalho deverão aprimorar a navegação
de um enxame, tornando-a mais eficiente e confiável.
11
2
Referencial Teórico
Nesta seção serão apresentados alguns dos conceitos básicos de navegação de robôs. Além
disso, serão discutidos alguns trabalhos relacionados ao controle de tráfego para grupos de
robôs. Mais detalhes sobre os conceitos de robótica móvel apresentados nesta seção podem ser
encontrados em [3].
A navegação de um robô consiste na movimentação do robô em um ambiente, de forma
a atingir um determinado alvo. Normalmente, esse ambiente contem obstáculos, que podem
ser previamente informados ao robô ou podem ser desconhecidos. Quando a posição dos
obstáculos é previamente informada, o robô pode realizar um planejamento de seu caminho.
Quando os obstáculos são desconhecidos, o robô deve utilizar seus sensores para perceber e
evitar os obstáculos dinamicamente. Pode-se utilizar soluções hı́bridas, onde o robô planeja a
sua navegação em um ambiente contendo obstáculos previamente informados, mas é capaz de
perceber novos obstáculos e adaptar a sua trajetória apropriadamente.
Um dos mecanismos que podem ser utilizados durante a navegação de um robô são os
waypoints. É especificado um conjunto de pontos ordenados no ambiente e o robô se movimenta
em direção a cada um desses pontos, na ordem estabelecida. A navegação por waypoints é
muito útil em situações onde a posição dos obstáculos é previamente conhecida. Os waypoints
a serem utilizados pelo robô para executar uma determinada trajetória podem ser gerados, por
exemplo, por algoritmos de planejamento, como Dijkstra ou A*. Outro mecanismo popular
para a navegação de um robô são os campos potenciais. Basicamente, o alvo atua como uma
região de atração para o robô, enquanto os obstáculos atuam como uma região de repulsão.
A superposição das forças de atração e repulsão guiam o robô em direção ao alvo, ao mesmo
tempo em que o obriga a evitar obstáculos.
Outro conceito importante é a configuração de um robô. A configuração de um robô pode
ser representada por um vetor de configurações q, cuja dimensão especifica o número de graus
de liberdade do robô. O número de graus de liberdade do robô representa o número mı́nimo de
variáveis independentes que, juntamente com a sua geometria, são necessárias para especificar
2 Referencial Teórico
12
completamente o robô. Para que um robô mude a sua configuração, ou seja, realize efetivamente
uma movimentação, pode-se considerar robôs holonômicos ou não-holonômicos. Em um robô
não-holonômico, o número de velocidades de atuação é menor do que o número de graus de
liberdade do sistema. Ou seja, existem restrições de movimento que não permitem o controle
independente de todas as variáveis do vetor de configurações. Um robô semelhante a um carro,
por exemplo, necessita realizar manobras para atingir uma determinada configuração. Já robôs
holonômicos, ou completamente atuados, possuem um número de velocidades de atuação igual
ao número de graus de liberdade do sistema. Portanto, podem controlar de forma independente
todas as variáveis do vetor de configurações. Mais detalhes sobre esses conceitos podem ser
encontrados em [4].
Neste trabalho, são desenvolvidos algoritmos para a navegação de um enxame de robôs. A
área de navegação de grandes grupos de robôs tem sido muito ativa ultimamente. Uma abordagem comum é controlar os robôs de forma descentralizada, misturando a descida do gradiente
com forças locais de repulsão [5]. Um dos primeiros trabalhos a lidar com o controle de movimento através de forças locais de iteração foi proposto em [6] para gerar animações realistas de
grupos de pássaros. Porém, como no método convencional de campos potenciais [7], a presença
de obstáculos e forças locais de repulsão entre os robôs pode prejudicar a convergência devido
a presença de mı́nimos locais. Em [1], é proposto um método de coordenação descentralizada
para superar esse problema. Notou-se, porém, que durante as simulações os robôs poderiam
demorar para convergir devido à problemas de congestionamento. É interessante, portanto,
coordenar os robôs para evitar o congestionamento.
Em [8], é feito um survey na área de robótica cooperativa. O controle de tráfego é identificado como uma área importante de pesquisa, além de ser caracterizado como um problema
de conflito de recursos. Existem trabalhos desde a década de oitenta, como por exemplo [9],
onde são propostas várias polı́ticas para evitar o congestionamento de robôs em uma fábrica.
Em [10] são propostas regras de trânsito para a navegação de um grupo de robôs. Em geral,
os trabalhos nessa área assumem que os robôs navegam em faixas delimitadas (como ruas ou
estradas). Essas faixas se encontram em interseções, onde podem ocorrer congestionamentos.
Portanto, em geral, o controle de tráfego é realizado apenas nessas interseções.
Trabalhos mais recentes podem ser encontrados tanto na área de robótica cooperativa como
na área de sistemas multi-agentes. Alguns trabalhos utilizam um agente para gerenciar o tráfego
nas interseções onde pode acontecer um congestionamento, como [11]. Uma abordagem semelhante, na área da robótica, pode ser vista em [12], onde uma rede de sensores é utilizada para
coordenar o tráfego dos robôs. Em [13] é proposto um algoritmo onde os robôs coordenam
2 Referencial Teórico
13
suas velocidades de forma a evitar uma colisão. A coordenação pode envolver não só os robôs
diretamente envolvidos na provável colisão, como também os robôs vizinhos, que podem ter
que alterar suas velocidades para auxiliar os robôs envolvidos. Já em [14] é proposto um mecanismo para evitar o congestionamento ao ser simulada uma multidão de pessoas. Os autores
propõe uma abordagem onde as pessoas planejam com antecedência para evitar um congestionamento, conseguindo uma trajetória mais suave do que ao se utilizar forças de repulsão locais.
O método, porém, é muito centralizado para ser utilizada em um enxame de robôs.
Neste trabalho é proposto um método de coordenação descentralizado que permite a um enxame de robôs navegar de forma suave, evitando situações de congestionamento. A abordagem
não assume que os robôs navegam em faixas delimitadas, nem necessita de meios externos ao
enxame, como redes de sensores ou agentes colocados nas interseções, para gerenciar o tráfego.
14
3
Metodologia
Ao navegar um enxame de robôs, costuma-se utilizar forças de repulsão locais para evitar
colisões. Portanto, dado um robô completamente atuado i, com modelo dinâmico dado por
q̇i = vi , v̇i = ui , onde qi = [Xi ,Yi ]T é a configuração do robô i, ui é entrada do controle e vi o
vetor velocidade, a seguinte lei de controle foi utilizada:
ui = α
f (qi , di )
−γ
|| f (qi , di )||
1
−Cq̇i
j∈Ni q j − qi
∑
(3.1)
As constantes α, γ e C são positivas. O primeiro termo é a força de atração do robô em
direção ao alvo. A função f calcula o vetor que aponta na direção do alvo do robô i, di .
O segundo termo representa as forças locais de repulsão. Os robôs vizinhos ao robô i são
representados pelo conjunto Ni . Define-se como vizinho todo robô que está dentro de um certo
limite, δ , de distância do robô i. O terceiro termo é uma força de amortecimento.
Quando se tem um número muito grande de robôs, porém, pode-se ter problemas ao se
utilizar apenas forças locais de repulsão. Quando grupos de robôs se movimentam em direções
contrárias, por exemplo, perde-se muito tempo até que um grupo consiga desviar completamente do outro. Portanto, é necessário uma maior coordenação entre os robôs para evitar esse
problema.
3.1
Coordenação
Nessa seção será explicado o mecanismo de coordenação proposto para evitar o congestionamento. Supõe-se que cada robô, i, utiliza o mesmo sistema de coordenadas e, portanto,
sabe qual é a direção de seu destino, di . Além disso, considera-se que os robôs são capazes
de se comunicar localmente com todos os vizinhos que estejam a uma distância máxima ρ. A
idéia geral do algoritmo é que os primeiros robôs a perceberem o risco de um congestionamento
avisem os outros, permitindo-os evitar o problema.
15
3.1 Coordenação
(a)
(b)
(c)
(d)
Figura 3.1: Passos da execução do algoritmo de coordenação proposto
Sempre que um robô, n, detecta a presença de outro, m, ele envia uma mensagem avisando
qual é sua direção de destino. Considera-se que um robô detectou a presença de outro quando a
distância entre eles é menor do que δ . Assim, caso dn 6= dm , o robô que recebeu a mensagem, m,
é capaz de perceber o risco iminente de acontecer um congestionamento. De modo análogo, m
também enviará uma mensagem para n avisando o seu destino, permitindo que ambos os robôs
percebam o risco do congestionamento. Para diminuir o número de mensagens necessárias para
a execução do algoritmo, cada robô só pode enviar uma mensagem avisando seu destino a cada
ε iterações. Essa etapa inicial do algoritmo pode ser vista na Figura 3.1(a).
Os robôs que perceberam o risco de um congestionamento enviam uma mensagem aos
seus vizinhos, como pode ser visto na Figura 3.1(b). Cada robô, ao receber essa mensagem,
a retransmite para seus respectivos vizinhos, como mostra a Figura 3.1(c). Dessa forma, a
informação do risco de um congestionamento é transmitida pelo enxame e cada grupo poderá
desviar de forma apropriada, como mostrado na Figura 3.1(d).
Assim que um robô percebe o risco de um congestionamento, seja encontrando um robô
do outro grupo, seja pelo aviso de outros robôs de seu próprio grupo, ele desvia do local onde
aconteceria o congestionamento. Para realizar o desvio, o robô utiliza como base a direção de
seu destino. Pode-se especificar, por exemplo, que cada robô desviará no sentido anti-horário,
de forma que um grupo que vai da esquerda para a direita desviará por baixo, e um grupo que vai
da direita para a esquerda desviará por cima. O controlador do robô durante o desvio, portanto,
pode ser dado por:
ui = α
g(qi , di )
−γ
||g(qi , di )||
1
−Cq̇i ,
j∈Ni q j − qi
∑
(3.2)
16
3.1 Coordenação
Figura 3.2: Controlador utilizado pelo robô para evitar um congestionamento.
onde g retorna um vetor que guiará o robô na direção do alvo, ao mesmo tempo em que o
faz desviar na direção apropriada. Para simplificar a fórmula, será considerado que o robô se
movimenta no eixo x e irá desviar no sentido negativo do eixo y. Assim, a função g pode ser
dada por:
g(qi , di ) = β (dix − qix ) + ψ(ciy − φ − qiy ),
(3.3)
onde β e ψ são constantes positivas e β < ψ, ciy é a posição do robô i no eixo y quando ele
iniciou o desvio e φ é uma constante positiva, que caracteriza a distância a ser percorrida no
eixo y durante o desvio. Quando a distância efetivamente percorrida no eixo y se aproxima
de φ , o robô retorna ao seu controlador normal de movimento, dado pela equação 3.1. Uma
representação gráfica do controlador de desvio pode ser vista na Figura 3.2.
17
4
Resultados e Discussão
O algoritmo proposto foi implementado no Player/Stage, um framework que permite realizar simulações realistas. Ao se utilizar esse framework, normalmente o mesmo código pode
ser utilizado tanto em simulações quanto na execução com robôs reais, sendo necessário fazer
apenas pequenas modificações. As constantes utilizadas mais importantes podem ser vistas na
tabela 4.1. Foram executadas simulações com dois grupos de robôs e com quatro grupos de
robôs. Na execução com dois grupos utilizou-se 4 como valor de φ . Na execução com quatro
grupos, utilizou-se 5 como valor de φ .
Foram executadas simulações com dois grupos de 24 robôs se movimentando em direções
opostas. Na Figura 4.1 pode ser visto o resultado utilizando apenas forças de repulsão locais
(NORMAL). Na Figura 4.2 o resultado utilizando o algoritmo de coordenação (COORDENADO) pode ser visto. Como pode ser observado visualmente, o comportamento dos robôs
foi melhor utilizando o algoritmo proposto. A navegação dos robôs foi mais suave, os grupos
mantiveram-se coesos e o risco de colisões foi baixo. Já na navegação utilizando apenas forças
locais de repulsão, os grupos se misturaram, ocorrendo um alto risco de colisões. Pode-se perceber uma aglomeração dos robôs na região central, caracterizando uma situação de congestionamento. Pode-se observar também que enquanto alguns robôs já conseguiram atingir o alvo,
outros continuam presos na região do congestionamento, desperdiçando recursos. Percebese, assim, que a navegação utilizando o método de coordenação proposto é mais eficiente e
confiável.
Também foram executadas simulações com quatro grupos de 12 robôs. O resultado pode
ser visto na Figura 4.3. Como pode ser observado, o algoritmo funcionou bem para quatro
δ
ρ
ε
ψ
β
2
2
50
0,1
1
Tabela 4.1: Principais constantes utilizadas.
18
4 Resultados e Discussão
(a)
(b)
(c)
(d)
(e)
Figura 4.1: Execução com dois grupos utilizando forças de repulsão locais.
(a)
(b)
(c)
(d)
(e)
Figura 4.2: Execução com dois grupos utilizando o algoritmo de coordenação.
4 Resultados e Discussão
19
grupos. Os robôs realizaram um movimento aproximadamente circular em torno da região
onde aconteceria o congestionamento, e cada grupo conseguiu chegar no destino especificado.
Para avaliar melhor a eficiência e a escalabilidade do algoritmo, diversas simulações foram
realizadas. Utilizou-se na avaliação o cenário em que dois grupos de robôs se movimentam em
direções opostas. Variou-se o número de robôs por grupo, e mediu-se o tempo de execução e o
número de mensagens utilizadas. Para um determinado número de robôs, rodou-se a simulação
10 vezes e calculou-se a média aritmética do resultado. Como medida do tempo de execução do
algoritmo, considerou-se o número de iterações necessárias para que o último robô ultrapasse
um determinado ponto na sua direção de movimento. Na Figura 4.4 pode ser visto o tempo
utilizado pelos dois algoritmos. Como pode ser observado, para um número muito pequeno
de robôs a eficiência dos algoritmos é semelhante, mas quando o número de robôs tornou-se
maior, o algoritmo COORDENADO mostrou-se melhor do que o NORMAL. Também pode ser
observado que o tempo gasto pelo algoritmo NORMAL foi muito instável, com um alto desvio
padrão, enquanto o algoritmo COORDENADO apresentou um desvio padrão menor.
Na Figura 4.5 pode ser visto o número de mensagens utilizadas pelo algoritmo proposto
para um número variável de robôs. Na Figura 4.5 (a) pode ser visto o ajuste de curva linear,
enquanto na Figura 4.5 (b) pode ser visto o ajuste quadrático. O melhor modelo linear encontrado foi y = 31, 5762x − 76, 8857, com um erro de 28, 4231. Já o melhor modelo quadrático
foi y = 0, 3413x2 + 21, 3381x − 12, 3857, com um erro de 3, 9301. Apesar do melhor modelo ter
sido uma função quadrática, o termo quadrático é pequeno.
20
4 Resultados e Discussão
(a)
(b)
(c)
(d)
(e)
Figura 4.3: Execução com quatro grupos utilizando o algoritmo de coordenação.
21
4 Resultados e Discussão
1800
Normal
Coordenado
1600
Número de Iterações
1400
1200
1000
800
600
400
5
10
15
Número de Robôs por Grupo
20
25
Figura 4.4: Tempo utilizado pelos dois algoritmos. As barras indicam o desvio padrão dos
resultados.
22
4 Resultados e Discussão
800
Dado
Modelo Linear
Número de Mensagens Enviadas
700
600
500
400
300
200
100
5
10
15
Número de Robôs por Grupo
20
25
(a)
800
Dado
Modelo Quadrático
Número de Mensagens Enviadas
700
600
500
400
300
200
100
5
10
15
Número de Robôs por Grupo
20
25
(b)
Figura 4.5: Número de mensagens utilizadas para um número crescente de robôs.
23
5
Conclusões e Trabalhos Futuros
Neste trabalho, foi proposto um algoritmo para realizar o controle de tráfego para um enxame de robôs, evitando o congestionamento. Foram apresentados resultados de simulações,
onde mostrou-se a eficácia do algoritmo em cenários com dois e com quatro grupos de robôs.
Além disso, comparou-se o algoritmo proposto com a utilização somente de forças locais de
repulsão. Os resultados foram melhores utilizando o algoritmo proposto, além dele ter se mostrado mais estável. Percebe-se, assim, a importância de se utilizar mecanismos de coordenação
durante a navegação de um enxame. Ao se analisar o número de mensagens utilizadas pelo
algoritmo, percebeu-se uma tendência quadrática, porém o termo quadrático não é grande.
Acredita-se, portanto, que esse algoritmo possa ser escalável para um número grande de robôs.
Pretende-se adaptar o algoritmo para lidar com um número maior de grupos de robôs. Foi
observado que os robôs devem executar um movimento aproximadamente circular em torno
da região onde aconteceria o congestionamento para que o desvio seja bem sucedido. Deve-se
estudar formas de se ter esse movimento para um número grande de grupos de robôs. Além
disso, nos cenários testados, os grupos de robôs eram parecidos e se movimentavam de forma
uniforme. Pode ser interessante testar cenários mais complexos, que apresentem uma menor
uniformidade. Também deve-se investigar um mecanismo de coordenação para o caso em que
um número muito grande de robôs deseja chegar no mesmo alvo, como pode acontecer durante
a navegação por waypoints.
Os trabalhos futuros também incluem a execução do algoritmo em robôs reais. Experimentos em robôs reais são muito importantes em robótica, por mostrar que um algoritmo pode
efetivamente funcionar em robôs atuando no mundo real, com todos os problemas causados
pelas incertezas geradas pelos erros dos sensores e dos atuadores, problemas de comunicação
e restrições de tempo real. Assim, pretende-se mostrar que o algoritmo proposto pode efetivamente ser utilizado para realizar o controle de tráfego de um enxame de robôs, permitindo ao
enxame navegar de forma coordenada e eficiente.
24
Referências Bibliográficas
[1] MARCOLINO, L. S.; CHAIMOWICZ, L. No robot left behind: Coordination to overcome
local minima in swarm navigation. In: Proceedings of the 2008 IEEE International Conference on Robotics and Automation. [S.l.: s.n.], 2008. p. 1904–1909.
[2] GERKEY, B.; VAUGHAN, R. T.; HOWARD., A. The player/stage project: Tools for multirobot and distributed sensor systems. In: Proceedings of the 11th International Conference
on Advanced Robotics. Coimbra, Portugal: [s.n.], 2003. p. 317–323.
[3] SIEGWART, R.; NOURBAKHSH, I. R. Introduction to Autonomous Mobile Robots. [S.l.]:
Bradford Book, 2004. ISBN 026219502X.
[4] PEREIRA, G. A. S.; CHAIMOWICZ, L. Robôs móveis. In:
tomática. [S.l.]: Blucher, 2007. v. 3, cap. 13.
. Enciclopédia de Au-
[5] BACHMAYER, R.; LEONARD, N. E. Vehicle networks for gradient descent in a sampled
environment. In: Proceedings of the 41st IEEE Conference on Decision and Control (CDC02). [S.l.: s.n.], 2002. p. 112–117.
[6] REYNOLDS, C. W. Flocks, herds and schools: A distributed behavioral model. In: Proceedings of the 14th annual conference on Computer graphics (SIGGRAPH 87). [S.l.]: ACM
Press, 1987. p. 25–34. ISBN 0-89791-227-6.
[7] KHATIB, O. Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Rob.
Res., Sage Publications, Inc., Thousand Oaks, CA, USA, v. 5, n. 1, p. 90–98, 1986. ISSN
0278-3649.
[8] CAO, U. Y.; FUKUNAGA, A. S.; KAHNG, A. B. Cooperative mobile robotics: Antecedents and directions. Autonomous Robots, v. 4, n. 1, p. 7–23, March 1997. Disponı́vel em:
<http://citeseer.ist.psu.edu/cao97cooperative.html>.
[9] GROSSMAN, D. Traffic control of multiple robot vehicles. Journal of Robotics and Automation, v. 4, p. 491–497, 1988.
[10] KATO, S.; NISHIYAMA, S.; TAKENO, J. Coordinating mobile robots by applying traffic rules. In: Proceedings of the IEEE International Conference on Intelligent Robots and
Systems. [S.l.: s.n.], 1992.
[11] DRESNER, K.; STONE, P. Multiagent traffic management: an improved intersection control mechanism. In: AAMAS ’05: Proceedings of the fourth international joint conference on
Autonomous agents and multiagent systems. New York, NY, USA: ACM, 2005. p. 471–477.
ISBN 1-59593-093-0.
Referências Bibliográficas
25
[12] VISWANATH, K.; KRISHNA, K. M. Sensor network mediated multi robotic traffic control in indoor environments. In: Proceedings of the International Conference on Advanced
Robotics. [S.l.: s.n.], 1997.
[13] KRISHNA, K. M.; HEXMOOR, H. Reactive collision avoidance of multiple moving
agents by cooperation and conflict propagation. In: Proceedings of the 2004 IEEE International Conference on Robotics and Automation. [S.l.]: IEEE, 2004. p. 2141–2146.
[14] TREUILLE, A.; COOPER, S.; POPOVIć, Z. Continuum crowds. In: SIGGRAPH ’06:
ACM SIGGRAPH 2006 Papers. New York, NY, USA: ACM, 2006. p. 1160–1168. ISBN
1-59593-364-6.