Programa de Pós Graduação em Engenharia ElétricaUniversidade Federal de Minas GeraisAv. Antônio Carlos 6627, 31270-901 Belo Horizonte, MG BrasilFone: +55 31 3409-3430

Segregação em Enxames de RobôsHeterogêneos com o uso de Abstrações

Edson Bernardes Ferreira Filho

Dissertação de Mestrado submetida à Banca Examinadoradesignada pelo Colegiado do Programa de Pós-Graduaçãoem Engenharia Elétrica da Escola de Engenharia da Uni-versidade Federal de Minas Gerais, como requisito paraobtenção do Título de Mestre em Engenharia Elétrica.

Orientador: Prof. Luciano Cunha de Araújo Pimenta, Doutor

Belo Horizonte, Novembro de 2015

Dedicatória

À minha mãeÀs minhas irmãs

i

Agradecimentos

Este trabalho não seria possível sem o apoio de todos meus amigos e familiares queme incentivaram e motivaram durante todo o tempo da elaboração do mesmo.

À minha mãe que sempre me apoiou e respeitou minhas decisões e por que sem elanada disto seria possível.

Ao meu pai (em memória) pela certeza de que ele se orgulharia muito ao ler estetrabalho.

Às minhas irmãs Aninha e Nina por confiarem em mim e por estarem presentes naminha vida.

À minha sobrinha Marina e minha afilhada Manuela.Ao Edu pela ajuda e confiança.À todos os outros parentes, tios, tias, primas e primas aos quais sempre tive uma

incomensurável relação de amizade.À todos meus amigos, de Ouro Branco, Ouro Preto e de Belo Horizonte por fazerem

parte da minha formação humana e tornarem meus dias de lazer mais alegres.À todos os colegas e professores do PPGEE com os quais tive o prazer de absorver

e compartilhar conhecimento.Ao meu orientador Luciano Pimenta por todos os ensinamentos e pela paciência.À todos os outros professores que tive em minha vida acadêmica por terem contri-

buído na minha formação acadêmica.Finalmente, agradeço ao CNPq, FINEP e FAPEMIG pelo suporte financeiro.

ii

Sumário

Resumo v

Abstract vi

Lista de Figuras viii

1 Introdução 1

1.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4 Organização do Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Revisão Bibliográfica 5

2.1 Navegação com Enxames de Robôs . . . . . . . . . . . . . . . . . . . . . . 6

2.1.1 Com Robôs Homogêneos . . . . . . . . . . . . . . . . . . . . . . . 7

2.1.2 Com Robôs Heterogêneos . . . . . . . . . . . . . . . . . . . . . . . 8

2.2 Segregação em Enxames de Robôs . . . . . . . . . . . . . . . . . . . . . . 10

3 Formulação do Problema e Conceitos Preliminares 14

3.1 Abstrações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.2 Função de Potencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.3 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.4 Estabilidade de Lyapunov . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.5 Problema de Segregação em Enxames de Robôs . . . . . . . . . . . . . . 20

iii

iv

4 Metodologia 22

4.1 Robôs do tipo integrador simples . . . . . . . . . . . . . . . . . . . . . . . 22

4.1.1 Tratamento de colisões . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.1.2 Análise do controlador . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.2 Robôs do tipo integrador duplo . . . . . . . . . . . . . . . . . . . . . . . . 29

4.2.1 Tratamento de Colisões . . . . . . . . . . . . . . . . . . . . . . . . 31

4.2.2 Análise do controlador . . . . . . . . . . . . . . . . . . . . . . . . . 35

5 Simulações e Resultados Experimentais 36

5.1 Simulações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.1.1 Robôs do tipo Integrador Simples . . . . . . . . . . . . . . . . . . 37

5.1.2 Robôs do tipo Integrador Duplo . . . . . . . . . . . . . . . . . . . 39

5.2 Plataforma de testes com Robôs Reais . . . . . . . . . . . . . . . . . . . . 40

5.2.1 Resultados Experimentais com Robôs do tipo Integrador Simples 42

5.2.2 Resultados Experimentais com Robôs do tipo Integrador Duplo . 42

6 Discussões Finais e Conclusões 45

6.1 Proposta para Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . 48

6.2 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Referências Bibliográficas 54

Resumo

O uso de enxames de robôs deve ser mais explorado em um futuro próximo devidoàs suas vantagens, como ser redundante por construção e a tendência da redução doscustos na fabricação de robôs. Para que o uso deste tipo de sistema seja viável, sãonecessários algoritmos de navegação eficientes para resolver os diversos problemas emaberto. Este trabalho aborda o problema de segregação em enxames de robôs. Esteproblema consiste na segregação de robôs heterogêneos, em que grupos menores ho-mogêneos devem ser formados a partir de um grupo maior heterogêneo e estes gruposmenores devem segregar-se. Para resolver o problema de segregação em enxamesde robôs devem-se formular leis de controle individuais para fazer com que todos osrobôs de um mesmo tipo agrupem-se enquanto mantêm distância dos outros grupos.Este trabalho propõe leis de controle para dois modelos de robôs diferentes: robôsdo tipo integrador simples (atuados em velocidade) e robôs do tipo integrador duplo(atuados em aceleração). O controlador proposto para os dois tipos são baseados namesma ideia. Esta ideia consiste em primeiramente formar abstrações que represen-tam cada grupo e depois separar as abstrações. Cada abstração é formada a partir deinformações sobre a posição de todos os robôs de um grupo. Depois de formadas asabstrações, os centros das mesmas são segregadas através de forças artificiais advindasde uma função de potencial artificial. São adicionados no espaço nulo de cada umdos dois controladores um outro controlador para evitar colisões. É mostrada a provade convergência para segregação tanto do controlador para robôs do tipo integradorduplo quanto para robôs do tipo integrador simples. Nos controladores mostradosexistem situações em que cada robôs não necessita de informações de todos os outrosrobôs do sistema para que ocorra segregação. Este trabalho é o primeiro a resolver esteproblema que pode não precisar de informações globais o tempo todo em que a provade convergência é mostrada. São mostrados simulações e experimentos que validama estratégia proposta para os dois controladores propostos na solução do problema desegregação em enxames de robôs.

v

Abstract

The use of robotic swarms might be better exploited in a near future due to its ad-vantages, such as the redundancy by construction and the tendency of cost reductionin robots fabrication. To this type of system became viable, we need efficient navigationalgorithms to solve many issues that are still open. This work tackles the problem of se-gregation in robot swarms. This problem consists in segregating heterogeneous robots,where smaller groups of homogeneous robots are formed from a bigger heterogeneousgroup and the smaller groups should segregate. To solve the problem of segregationin a robotic swarm one should design individual control laws to make all robots of onesame type form clusters while maintaining distance from other groups. We proposecontrol laws for two different robot models: single integrator robots (actuated in velo-city) and double integrator robots (actuated in acceleration). The proposed controlleris based in the same idea in both cases. This idea consists in creating abstractionsthat represent each group e then separate the abstractions. Each abstraction is formedusing information about the position of all robots of a group. After the abstractionsare created, the center of the abstractions are segregated through artificial forces thatcame from a artificial potential function. In the null space of each one of both con-trollers we add one controller responsible for collision avoidance. The convergenceproof of segregation is shown for the single integrator robots and for double integratorrobots. In the proposed controllers there are situations where each robot does not needinformation about all the robots in the system in order to segregation occur. This workis the first to solve this problem that may not need global information all the time inwhich convergence proof is shown. Simulations and experiments are shown and theyvalidate the proposed strategy for both controllers solving the problem of segregationin robotic swarms.

vi

Lista de Figuras

2.1 Pequenos robôs que formam um enxame de 1000 robôs [Rubenstein et al.,2014]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Enxame de robôs que flutuam [O’Hara et al., 2014]. . . . . . . . . . . . . 62.3 Enxame de robôs formando uma ponte [O’Hara et al., 2014]. . . . . . . . 62.4 Robôs com câmeras [Dorigo, 2013]. . . . . . . . . . . . . . . . . . . . . . . 92.5 Robôs com garras [Dorigo, 2013]. . . . . . . . . . . . . . . . . . . . . . . . 92.6 Robôs móveis simples [Dorigo, 2013]. . . . . . . . . . . . . . . . . . . . . 92.7 Exemplo do Brazilian nut effect. Da esquerda para direita, recipientes

sendo agitados verticalmente. . . . . . . . . . . . . . . . . . . . . . . . . . 102.8 Experimento com e-pucks baseado no Brazilian Nut Effect. Os quadro

mais à esquerda e mais à direita apresentam as configurações iniciaise finais do sistema, respectivamente. Os quadros do meio mostramsituações intermediárias [Chen et al., 2012]. . . . . . . . . . . . . . . . . . 11

2.9 Função de Potencial Artificial usada em Santos [2014]. . . . . . . . . . . . 132.10 Função de Potencial Artificial usada em Kumar et al. [2010]. . . . . . . . 13

3.1 Parâmetros: c = 0. 01, h = 0. 3, dα = 10, rα = 1. 8dα. (a) Potencial artificialentre dois agentes versus a distância entre eles. (b) Força artificial entredois agentes baseada no gradiente versus a distância entre eles. . . . . . 18

3.2 Dois grafos: G1 e G2. O grafo G1 é conexo e o grafo G2 é desconexo epossui dois subgrafos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.3 Robôs circulares divididos em M = 3 com 3 robôs em cada grupo. . . . . 20

4.1 Raio da abstração necessário para atingir segregação de acordo com adefinição do problema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.2 Estratégia para evitar colisões usada em Michael et al. [2007]. . . . . . . 254.3 Robôs em iminência de colisão. . . . . . . . . . . . . . . . . . . . . . . . . 274.4 Esquema exemplificando a estratégia para evitar colisões. . . . . . . . . . 34

5.1 Sequência de quadros de uma simulação. . . . . . . . . . . . . . . . . . . 375.2 (a) Evolução do “tamanho” de cada abstração. (b) Mínima distância

entre os centros das abstrações ao longo do tempo. . . . . . . . . . . . . . 38

vii

viii

5.3 Mínima distância entre robôs. . . . . . . . . . . . . . . . . . . . . . . . . . 385.4 Da esquerda para a direita: Quadros das simulações com 75, 50 e 25

robôs. De cima para baixo: Sequência de quadros de três simulações. . . 405.5 Quadros de uma simulação no ambiente ROS/Stage com 20 robôs distri-

buídos desigualmente em 4 grupos. Da esquerda para direita: Situaçãoinicial, situação intermediária e situação final. . . . . . . . . . . . . . . . . 41

5.6 Média da informação de quantos grupos vizinhos que cada robô precisaao longo do tempo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.7 Tamanho do robô considerado. . . . . . . . . . . . . . . . . . . . . . . . . 425.8 Um robô e-puck. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435.9 Sequência de quadros do experimento com robôs e-puck usando o algo-

ritmo do tipo integrador simples. . . . . . . . . . . . . . . . . . . . . . . . 435.10 Sequência de quadros do experimento com robôs e-puck usando o algo-

ritmo do tipo integrador duplo. . . . . . . . . . . . . . . . . . . . . . . . . 445.11 Gráficos referentes ao experimento mostrado na figura 5.10 (a) Evolução

do tamanho das abstrações. (b) Evolução dos centros das abstrações.(c) Distância mínima entre robôs ao longo do tempo. (d) Evolução daposição dos robôs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

6.1 (a) Algoritmo para robôs do tipo integrador simples. (b) Algoritmo pararobôs do tipo integrador duplo. . . . . . . . . . . . . . . . . . . . . . . . . 47

Capítulo 1

Introdução

“The most exciting phrase to hear in science, the one that heraldsnew discoveries, is not ’Eureka!’ but ’That’s funny...’ ”

Isaac Asimov

Enxames de robôs têm inspiração na natureza, no modo como os pássaros voamem formação ou na forma como cardumes de peixes se agrupam em busca de objetivoscomuns. Um sistema multi agente com um grande número de robôs autônomos échamado de enxame de robôs, usualmente cada um dos robôs de um enxame é umrobô mais simples se comparado com um robô no estado da arte da robótica. Istoporque aplicações com enxames de robôs focam no que o enxame pode fazer como umtodo, ao invés do que cada um de seus robôs consegue realizar individualmente.

Estes sistemas são caracterizados pelo controle descentralizado, comunicação limi-tada entre robôs, uso da comunicação local, e surgimento de um comportamento global[Dorigo, 2013]. Existem diversas vantagens em projetar um sistema deste tipo, comoa tolerância a falhas individuais, por existirem diversos agentes redundantes em suaconstrução [Trianni, 2008].

Enxames robóticos têm diversas aplicações e grande parte delas permanece aindaem fase de pesquisa. Existem aplicações possíveis em diversas áreas: pode-se imaginarenxames de robôs localizando vítimas em ambientes afetados por desastres naturaisou então, na área da engenharia biomédica, vários robôs dentro de um paciente paraverificar o funcionamento de seus órgãos internos.

Enxames de robôs heterogêneos são aqueles formados por diferentes tipos de robôs,sejam estas diferenças em sua construção ou na tarefa que eles devem desempenhar.Por exemplo, pode-se imaginar um sistema de robôs heterogêneos para vigilância deum perímetro em que alguns robôs possuem câmeras e são responsáveis pela vigilânciaenquanto outros robôs são projetados para avisar os humanos se existir algum intrusoneste perímetro.

Robótica de enxames é uma área da engenharia em crescente desenvolvimento ecom diversos problemas a serem resolvidos para que possam ter aplicações mais con-cretas em um futuro próximo. Um destes problemas é o de segregação de robôs. Esteproblema trata de quando é necessária a separação de enxames de robôs heterogêneosem grupos contendo apenas robôs homogêneos. Para resolver o problema de segre-gação em enxames de robôs deve-se formular leis de controle individuais para fazer

1.1 Motivação 2

com que todos os robôs de um mesmo tipo agrupem-se enquanto mantém distânciados outros grupos.

Diferente de outros trabalhos, este propõe técnicas distribuídas, para vários grupos,além de provar formalmente que o sistema converge para a segregação. A proposta foifeita tanto para robôs do tipo integrador simples quanto para robôs do tipo integradorduplo e as provas para ambos os casos são apresentadas. Esta proposta consisteprincipalmente em acoplar duas ideias: abstrações e campos potenciais artificiais. Sãoformadas abstrações simples para cada grupo como proposto em Belta and Kumar[2003]. É usada a média da posição de todos os robôs de um grupo e a matriz decovariância do mesmo para representar este grupo. A função potencial inicialmenteapresentada em Olfati-Saber [2006] é utilizada para que ocorra a segregação dos gruposde robôs que agora são representados por suas abstrações. Além disso, é proposta umaestratégia para se evitar colisões entre robôs de um mesmo grupo e de grupos diferentes.

Para estudar a viabilidade do método proposto, primeiramente foram feitas simula-ções no MATLAB [MathWorks, 2014] com o algoritmo de primeira ordem (robôs do tipointegrador simples) e de segunda ordem (robôs do tipo integrador duplo). Posterior-mente foi adicionado o controlador para evitar colisões, no espaço nulo do controladororiginal, de forma a não alterar a prova de convergência da tarefa principal. Apósestes testes, o método foi implementado em robôs reais e-pucks usando os algoritmosde primeira e de segunda ordem.

Os resultados obtidos nas simulações e nos experimentos com robôs reais mostramque os métodos desenvolvidos são eficientes na solução do problema de segregaçãoem enxames de robôs.

1.1 Motivação

Robótica de enxames é uma área nova se comparada com robótica para um únicorobô móvel e manipuladores robóticos e como tal, ainda existem diversos desafios aserem vencidos. Podem-se imaginar diversas aplicações em que o uso de enxamesde robôs é capaz de resolver problemas que apenas um robô não é capaz de resolver,para que isto possa ocorrer, é necessário que existam pesquisas na área de robótica deenxames. Os problemas de navegação, que são muito comuns em pesquisas com umúnico robô móvel, ainda carecem de um número maior de trabalhos quando existemvários robôs no sistema.

Quando se trata de robôs heterogêneos, ainda menos pesquisas existem.Pesquisas com enxames de robôs fazem com que seja possível o uso destes robôs

em diversas aplicações, sejam elas no dia-a-dia das pessoas, em usos militares, emindústrias ou em situações de eventuais desastres.

Assim sendo, a principal motivação deste trabalho é a carência de pesquisas paranavegação de enxames de robôs heterogêneos e a ausência de pesquisas que resolveme provam a convergência para segregação em enxames de robôs com mais de dois

1.2 Objetivos 3

grupos. Esta motivação é devido à importância que este tipo de sistema terá na áreade robótica e na vida das pessoas em um futuro próximo.

1.2 Objetivos

O objetivo geral do trabalho foi obter formas de resolver o problema de segregaçãode robôs heterogêneos em enxames de robôs compostos por vários grupos, em quefosse possível fazer a prova de convergência para segregação deste sistema.

Durante o desenvolvimento viu-se a possibilidade de usar algumas das mesmasideias em robôs cuja dinâmica é dada por integradores simples ou duplos, com isso, otrabalho foi desenvolvido para ambos os casos. Assim sendo, a dissertação teve comoobjetivos específicos:

1. Desenvolver o algoritmo de segregação para robôs do tipo integrador simples.

2. Desenvolver o algoritmo de segregação para robôs do tipo integrador duplo.

3. Acoplar controladores para evitar de colisões nos dois algoritmos citados.

4. Testar via simulações, a viabilidade dos algoritmos propostos.

5. Fazer experimentos com robôs reais utilizando os algoritmos desenvolvidos.

1.3 Contribuições

Do conhecimento destes autores, este trabalho é o primeiro com convergência ga-rantida para segregação de vários grupos de robôs heterogêneos. Isto foi feito paradois casos, usando robôs do tipo integrador simples e robôs do tipo integrador duplo.Ainda, este trabalho é o primeiro a resolver este problema que pode não precisar deinformações globais o tempo todo. Outra contribuição interessante é a estratégia paraevitar colisões mantendo o estado das abstrações, não importando o número de robôsenvolvidos nas colisões. Enquanto outros trabalhos possuíam problemas com gruposdesbalanceados, o método desenvolvido aqui não apresenta nenhum tipo de problemanesse quesito.

Durante o desenvolvimento desta dissertação, dois artigos foram produzidos esubmetidos para congressos. São eles:

1. Segregating Multiple Groups of Heterogeneous Units in Robot Swarms usingAbstractions (Apresentado na IEEE/RSJ International Conference on Intelligent Ro-bots and Systems 2015 (IROS) em Setembro de 2015, Hamburgo, Alemanha).

2. Segregação de Enxames de Robôs Heterogêneos do Tipo Integrador Simples emMúltiplos Grupos usando Abstrações (Apresentado para o Simpósio Brasileiro

1.4 Organização do Texto 4

de Automação Inteligente 2015 (SBAI) em Outubro de 2015, Natal, Rio Grandedo Norte, Brasil).

1.4 Organização do Texto

Esta dissertação está organizada da seguinte forma: O Capítulo 2 é dedicado àrevisão bibliográfica. No Capítulo 3 são apresentados conceitos iniciais e a formulaçãodo problema a ser resolvido. No Capítulo 4 é mostrada a metodologia do trabalhodesenvolvido para robôs do tipo integrador simples e robôs do tipo integrador duplo.São apresentados no Capítulo 5 as simulações realizadas, bem como os experimentoscom robôs reais. O Capítulo 6 discute os resultados e conclui o trabalho.

Capítulo 2

Revisão Bibliográfica

“The science of today is the technology of tomorrow.”

Edward Teller

Enxames de robôs têm tido cada vez mais atenção dos pesquisadores e da sociedadede forma geral. Essa atenção se deve às vantagens apresentadas por tal sistema, comoo fato de sistemas desse tipo serem intrinsicamente redundantes, i.e., se um robô falhar,existem ainda muitos outros pra cumprir a tarefa proposta ao enxame.

Robótica de enxames é o estudo de sistemas robóticos formados por um grandenúmero de robôs relativamente pequenos e simples que interagem e cooperam entreeles para que eles resolvam uma tarefa que está além de suas capacidades individuais[Dorigo and Sahin, 2004].

Alguns pesquisadores estão focando na construção de enxames de robôs altamenteescaláveis, devido ao baixo custo de cada um [Klingner et al., 2014]. Em Valentini et al.[2015] é usado um enxame composto por 100 robôs e em Rubenstein et al. [2014], pelaprimeira vez, é apresentado um enxame composto por 1000 robôs. Parte deste enxameé mostrado na figura 2.1.

Figura 2.1: Pequenos robôs que formam um enxame de 1000 robôs [Rubenstein et al.,2014].

Uma aplicação interessante de enxames de robôs é apresentada em O’Hara et al.[2014], em que um enxame formado por robôs que flutuam se agrupam, construindo

2.1 Navegação com Enxames de Robôs 6

Figura 2.2: Enxame de robôs que flutuam [O’Hara et al., 2014].

Figura 2.3: Enxame de robôs formando uma ponte [O’Hara et al., 2014].

assim uma ponte. A figura 2.2 mostra este enxame de robôs e a figura 2.3 mostra aponte que eles formam e um pequeno carro atravessando-a.

Outros trabalhos recentes estão focando em outras aplicações com enxames derobôs, como por exemplo, vigilância de perímetro [Pimenta et al., 2013a], detecção devazamentos [Zhang et al., 2014], captura de imagens para entretenimento [Remes et al.,2013] e interação dos enxames com humanos [Walker et al., 2014] e [Nagi et al., 2014].

Através destes exemplos, é possível constatar que aplicações com enxames de robôsterão muita utilidade para a sociedade no futuro. Para que seja possível o uso de taisenxames é necessária a formulação de leis de controle para guiar os robôs de formaeficiente. A seguir são apresentados alguns métodos para navegação com enxames derobôs.

2.1 Navegação com Enxames de Robôs

Nesta seção são discutidos métodos de navegação para enxames de robôs móveis.Problemas de navegação em enxames de robôs podem ser modelados como sendo

um problema de navegação diferente para cada robô. Desta forma, podem-se usarmétodos de planejamento de movimento para cada um dos robôs, modelando os

2.1 Com Robôs Homogêneos 7

outros robôs como obstáculos. Pode-se fazer isto tanto quando o mapa do ambiente éconhecido ou desconhecido, usando o algoritmo de acordo com o problema. Existemdiversos algoritmos para navegação de um robô móvel que pode ser utilizado destamaneira, desde os mais simples em que pouca informação é necessária como algoritmosdo tipo bug até algoritmos que discretizam o ambiente e realizam uma busca em grafoneste ambiente discretizado.

Estes algoritmos podem ser divididos do ponto de vista das informações necessáriaspara o controlador: em controle centralizado e controle distribuído. Na abordagemcentralizada, existe uma unidade responsável por enviar ações de controle para cadarobô a partir de informações globais. A grande vantagem deste tipo de sistema é amaior facilidade na solução de problemas de navegação, porque a unidade controladorapossui as informações de todos os robôs do sistema. No descentralizado, cada robôgera sua ação de controle a partir apenas de informações locais. Isto pode ser umagrande vantagem, visto que sistemas de comunicação e sensoriamento usualmentetêm alcance limitado. Existem ainda, propostas que misturam alguns aspectos de cadamétodo.

Modelar o problema de navegação de enxames em problemas de navegação indi-viduais com solução centralizada usualmente não é muito eficiente, porque deve-seplanejar o movimento de um sistema com uma dimensão muito grande, o que requeralgoritmos muito elaborados e com alto custo computacional. Além disso, a dimensãodo problema cresce ao serem adicionados robôs. Choset et al. [2005] e LaValle [2006]fazem uma revisão destes algoritmos de navegação para um robô, mas não tratamdiretamente de problemas de enxames de robôs.

Existem também trabalhos que tratam diretamente do problema de navegação paraenxames de robôs. Estes trabalhos usam diferentes métodos para formular leis decontrole que fazem com que os robôs naveguem de acordo com o problema estabelecido.Os métodos de navegação são divididos em dois tipos: com robôs homogêneos e comrobôs heterogêneos. Enxames de robôs heterogêneos são aqueles em que todos osrobôs do sistema são diferentes, seja em sua construção ou no papel que cada robô irádesempenhar em busca do objetivo do enxame. Enxames com robôs homogêneos sãoaqueles em que seus robôs não possuem nenhuma distinção.

2.1.1 Com Robôs Homogêneos

Modelos baseados em comportamentos (behavior-based) foram os primeiro tipos usa-dos na tentativa de controlar enxames virtualmente, no contexto de computação gráfica[Reynolds, 1987]. Estes modelos definem comportamentos que devem ser ativados emcondições pré-determinadas. Em Reynolds [1987], o objetivo é simular movimentosde animais em "bando"para fins de computação gráfica. É utilizado um modelo ba-seado em comportamento em que cada animal virtual possui três comportamentospossíveis: evitar colisões com animais ao seu redor, tentar ficar perto dos animais ao

2.1 Com Robôs Heterogêneos 8

seu redor e tentar atingir a mesma velocidade dos animais ao seu redor. Cada umdestes comportamentos é ativado ou desativado conforme necessário, fazendo emergirum comportamento global do "bando". Balch and Arkin [1998] também utiliza de ummodelo baseado em comportamentos, mas para controlar um grupo de robôs, fazendocom que eles mantenham formações desejadas, formações estas que são baseadas nasutilizadas pelos pelotões do exército americano nos campos de batalha.

Diferente dos modelos baseados em comportamentos, alguns trabalhos são basea-dos em forças artificiais derivadas de funções de potencial. Estes métodos que utilizamfunções de potencial normalmente fazem uso do gradiente desta função para guiar orobô até o objetivo. Desta forma, os objetivos de cada robô atuam como forças atrati-vas e os obstáculos como forças repulsivas, sendo que os outros robôs do enxame sãomodelados como obstáculos do ponto de vista do robô de interesse. Tanner et al. [2005]faz uso de forças baseadas em funções de potencial para evitar colisões entre robôs nãoholonômicos enquanto estes se agrupam. Chaimowicz et al. [2005] e Hsieh et al. [2008]usam tais forças artificiais para fazer com que robôs se espalhem em curvas complexas(em duas dimensões) enquanto mantém uma separação entre os robôs. Kumar et al.[2010] e Santos [2014] utilizam funções de potencial, que serão melhor descritas naSeção 2.2, para resolver o problema de segregação em enxames de robôs.

A metodologia deste trabalho também faz uso de forças artificiais e elas serão melhordetalhadas na Seção 3.2.

Há outras abordagens, como por exemplo, o uso de propriedades da hidrodinâmicade partículas suavizadas para controlar de forma distribuída os robôs, fazendo eles“escoarem” pelo ambiente, como em Perkinson and Shafai [2005], Pimenta et al. [2008b]e Pimenta et al. [2013b].

Ainda, pode-se utilizar algumas propriedades do enxame de robôs para criar ummapeamento com dimensão menor do que se considerada a dimensão total do espaçode configurações global do enxame. Belta and Kumar [2003] é o primeiro a fazer usodesta estratégia, criando estruturas virtuais chamadas de abstrações (serão detalhadasno Capítulo 3). Criando estas estruturas, pode-se controlar vários robôs como um todo,o que facilita problemas de navegação para múltiplos robôs, mas em contrapartidatem-se um menor controle sobre o comportamento de cada robô separadamente. EmSantos and Chairmowicz [2011] e Santos and Chaimowicz [2011] são usadas abstraçõesdeste tipo no contexto de enxames de robôs e em Chaimowicz and Kumar [2004] sãousados VANTs para controlar enxames de robôs como um todo em tarefas de dividir ereagrupar.

2.1.2 Com Robôs Heterogêneos

O uso de robôs heterogêneos tem atraído recentemente a atenção de pesquisadoresem robótica. Existem algumas vantagens em sistemas deste tipo, pode-se, por exemplo,projetar um sistema com alguns robôs possuindo apenas um tipo de atuador e sensor,

2.1 Com Robôs Heterogêneos 9

enquanto outros robôs possuem atuadores e sensores diferentes. Um sistema destetipo é altamente escalável, pois pode-se adicionar apenas os robôs que são necessáriosna expansão do sistema. Também possui alta tolerância a falhas, pela redundância derobôs de um mesmo tipo.

Um exemplo de sistema deste tipo é o projeto Swarmanoid [Dorigo, 2013]. Nesteprojeto, existem três grupos de robôs. Alguns possuem câmeras que agem comosensores do sistema (figura 2.4), alguns robôs possuem garras como atuadores (figura2.5) e ainda há robôs que têm a função de mover os robôs com garras (figura 2.6).

Figura 2.4: Robôs com câmeras [Dorigo, 2013].

Figura 2.5: Robôs com garras [Dorigo, 2013].

Figura 2.6: Robôs móveis simples [Dorigo, 2013].

Existem outros trabalhos com aplicações com enxames de robôs heterogêneos. EmPimenta et al. [2008a] e Kantaros et al. [2015] são propostas leis de controle para tratardo problema de cobertura de espaços com robôs heterogêneos. Os robôs são diferentes

2.2 Segregação em Enxames de Robôs 10

no sentido de que seus sensores possuem diferentes capacidades de detecção. Estestrabalhos são interessantes para, por exemplo, usar tanto robôs aéreos quanto terrestresem cobertura de espaços.

Bezzo et al. [2014] apresenta redes de comunicação com um sistema de robôs hete-rogêneos, são usados robôs aéreos e terrestres como roteadores de sinal, estes robôs semovem em um ambiente enquanto mantêm a rede de comunicação conectada.

No uso de robôs heterogêneos uma habilidade importante para o sistema, quepode ser útil em diversas aplicações, é a capacidade de segregação autônoma. Estaé a habilidade de formar grupos, cada um contendo apenas robôs do mesmo tipo.Para que se possa fornecer esta capacidade ao sistema deve-se projetar leis de controleindividuais que fazem com que os robôs de um mesmo tipos formem clusters enquantomantém distância dos outros grupos.

2.2 Segregação em Enxames de Robôs

Esta seção relata os trabalhos da literatura que tentam resolver o problema desegregação autônoma em enxames de robôs heterogêneos. Poucos trabalhos tratamdiretamente deste problema. Os estudos mais relevantes na resolução deste problemasão Groß et al. [2009], Kumar et al. [2010], Chen et al. [2012], Szwaykowska et al. [2014]e Santos et al. [2014].

Groß et al. [2009] desenvolveu um algoritmo centralizado que é capaz de segregarrobôs baseados no Brazilian nut effect. Quando um recipiente contendo uma esferagrande e um grande número de pequenas esferas é agitado, a esfera maior sobe,mesmo quando ela é mais densa que as outras esferas. Similarmente, uma misturade partículas de tamanhos diferentes irá segregar pelo seu tamanho quando é agitada.Este efeito é chamado de Brazilian nut effect [Rosato et al., 1987]. A figura 2.7 mostraum sequência de quadros que ilustram este efeito.

Figura 2.7: Exemplo do Brazilian nut effect. Da esquerda para direita, recipientes sendoagitados verticalmente.

No trabalho de Groß et al. [2009], apesar dos robôs terem o mesmo tamanho, elessimulam o comportamento de partículas de tamanhos diferentes. Em Chen et al.

2.2 Segregação em Enxames de Robôs 11

[2012], esta abordagem é implementada em robôs e-puck com sucesso. A abordagemé interessante, são apresentadas simulações em ambiente virtual [Groß et al., 2009] ecom robôs reais [Chen et al., 2012], em ambas a segregação é atingida com sucesso.

A proposta é baseada em três comportamentos: movimentos aleatórios que simulama agitação do recipiente, atração para o centro de gravidade e repulsão aos outrosrobôs. Cada robô então necessita de uma informação exterior, que é o centro degravidade do sistema. Na implementação com e-epucks, para simular este ponto deatração gravitacional, é utilizada uma lâmpada como fonte de radiação. A figura 2.8mostra um dos experimentos presentes em Chen et al. [2012], onde é possível ver afonte de radiação usada.

A necessidade desta informação externa é uma desvantagem, visto que em muitasaplicações é inviável que cada robô obtenha esta informação. Ainda, não existe prova daestabilidade do controlador usado, o que serve de motivação para o desenvolvimento decontroladores que são estáveis e convergem para segregação independente do númerode robôs e de grupos que não precisem de informações exteriores.

Figura 2.8: Experimento com e-pucks baseado no Brazilian Nut Effect. Os quadro maisà esquerda e mais à direita apresentam as configurações iniciais e finais do sistema,respectivamente. Os quadros do meio mostram situações intermediárias [Chen et al.,2012].

Szwaykowska et al. [2014] estuda um enxame de robôs em que os robôs possuemdinâmicas diferentes. O enxame é dividido em dois grupos, um dos grupos possuiapenas robôs que são pouco "manobráveis"e o outro grupo possui apenas robôs quepodem ser acelerados mais rapidamente do que os robôs do primeiro grupo. São obser-vados que padrões segregativos emergem naturalmente com as dinâmicas propostas.Este é o único trabalho que trata de segregação encontrado na literatura em que a hete-rogeneidade do enxame se dá pela diferença nas dinâmicas dos robôs. É mostrada umasimulação em que a segregação ocorre, porém não é apresentada a prova de conver-gência. No trabalho de Szwaykowska et al. [2014], diferente dos outros trabalhos sobresegregação, o interesse maior é investigar o que ocorre em enxames de robôs com asdinâmicas propostas, os comportamentos segregativos surgem como uma consequên-cia destas dinâmicas. A segregação não é observada quando todos os robôs possuemas mesmas dinâmicas.

Os outros dois trabalhos que tentam resolver o problema de segregação em enxamesde robôs são Kumar et al. [2010] e Santos [2014]. Ambos são baseados no gradiente de

2.2 Segregação em Enxames de Robôs 12

funções potenciais. Nos dois trabalhos, são considerados N robôs com dinâmica dadapelo integrador duplo:

qi = vi, vi = ui i = 1,2,. . .N, (2.1)

em que ui, qi e vi são as entradas de controle, a posição e a velocidade do robô i,respectivamente.

Kumar et al. [2010] usa uma função de potencial artificial baseada no modelo deadesão diferencial de células biológicas. Este foi o primeiro trabalho a atingir segregaçãode forma distribuída a aparecer na literatura. É mostrada a prova de convergênciaassintótica para segregação e a análise de estabilidade para enxame de robôs comapenas dois grupos. A função de potencial artificial usada é:

Vi j

( ∥∥∥qi − q j

∥∥∥ )= a

(ln

( ∥∥∥qi − q j

∥∥∥ )+

d0∥∥∥qi − q j

∥∥∥), (2.2)

em que a é um ganho escalar e d0 é um parâmetro que define a qual distância opotencial será nulo. Como o trabalho trata apenas de dois grupos de robôs, esta funçãode potencial possui três partes: potencial entre robôs de um grupo, potencial entrerobôs do outro grupo e o potencial entre robôs de grupos distintos. Assim, o parâmetrod0 assume valores diferentes para cada parte desta função de potencial, sendo que d0

para o potencial entre robôs de grupos distintos deve ser maior que os d0 dos doisgrupos, que podem ser iguais.

No trabalho de Kumar et al. [2010] é apresentada uma simulação com dois gru-pos atingindo segregação. Além disso, são mostrados dados de pouco mais de 100simulações que também atingiram segregação conforme a definição proposta.

A função de potencial usada em Santos [2014] apresenta apenas um termo a mais:

Vi j

( ∥∥∥qi − q j

∥∥∥ )= a

(12

(( ∥∥∥qi − q j

∥∥∥ )− d0

)2+ ln

( ∥∥∥qi − q j

∥∥∥ )+

d0∥∥∥qi − q j

∥∥∥), (2.3)

o parâmetro d0 atua de forma um pouco diferente, por haver agora vários grupos aserem segregados, d0 será fixo com um valor para robôs do mesmo grupo e um valormaior que o primeiro para robôs de grupos distintos. Em Santos [2014] são mostradas3 simulações com 150 robôs no total divididos em grupos de 5, 10 e 15 robôs. Tambémsão mostradas a média e o desvio padrão de 100 outras simulações, também comgrupos de 5, 10 e 15 robôs. Em todas as simulações os grupos segregam com sucesso.A prova de estabilidade do sistema com o controlador proposto é mostrada, porémnão é apresentada prova de convergência para segregação, o que significa que existe apossibilidade do sistema convergir para uma situação estável, mas que os grupos nãoestejam segregados.

As figuras 2.9 e 2.10 mostram as funções potenciais artificiais usadas em Santos[2014] e Kumar et al. [2010] respectivamente. Ambas as figuras foram obtida usando

2.2 Segregação em Enxames de Robôs 13

Figura 2.9: Função de Potencial Artificial usada em Santos [2014].

Figura 2.10: Função de Potencial Artificial usada em Kumar et al. [2010].

os mesmos parâmetros: a = 0. 5, d0 = 2 para robôs do mesmo grupo e d0 = 5 para robôsde grupos distintos. Isto significa que na distância d0 = 2 não haverá forças artificiaisentre robôs de um mesmo grupo e na distância d0 = 5 não haverá forças artificiais entrerobôs de grupos distintos.

Nesta dissertação, é apresentada uma nova proposta de controlador capaz de atingirsegregação. A proposta difere das apresentadas em Kumar et al. [2010] e Santos [2014].O controlador, que será detalhado no capítulo 4, é baseado no uso de abstrações [Beltaand Kumar, 2003] e de uma função de potencial com finite cut-off, diferente das usadasem Kumar et al. [2010] e Santos [2014].

Capítulo 3

Formulação do Problema e ConceitosPreliminares

“Life is pleasant. Death is peaceful. It’s the transition that’stroublesome.”

Isaac Asimov

Neste capítulo, são detalhados os conceitos que serão úteis na metodologia destetrabalho e na formulação do problema a ser resolvido. Também é apresentado formal-mente este problema.

A metodologia deste trabalho apresenta dois algoritmos, um para modelos de robôsdo tipo integrador simples e um para modelos de robôs do tipo integrador duplo. Osconceitos aqui apresentados serão utilizados da mesma forma em ambos os casos, anão ser onde for explicitamente descrito o contrário.

3.1 Abstrações

Para ser viável o controle em um enxame de robôs, muitas vezes são utilizadasabordagens que tratam do enxame como um todo ao invés de controlar cada robô indi-vidualmente. Este tipo de abordagem tem a grande vantagem de facilitar as estratégiasde controle do enxame, porém tem como desvantagem o menor controle sobre cadarobô individualmente. Neste trabalho é utilizada uma abordagem deste tipo, que échamada de abstração.

Belta and Kumar [2003] apresentam pela primeira vez o controle de um grandenúmero de robôs por meio de uma abstração, mapeando o espaço de configuraçõesdos robôs para uma variedade de dimensão menor. Neste trabalho, definimos umaabstração como a apresentada em Belta and Kumar [2003] para representar um grupo.

Cada abstração utiliza como variáveis a média das posições dos robôs do grupo euma variável dependente da matriz de covariâncias das posições dos robôs deste grupoque dá a ideia da dispersão do grupo. A média da posição de cada grupo é dada por:

µ j =1

N j

N j∑k=1

qkj, (3.1)

3.1 Abstrações 15

em que j = 1,2,. . . ,M, M é o número de grupos no sistema, N j é o número de robôs dogrupo j e k = 1,2,. . . ,N j são os robôs do grupo j. O total de robôs do sistema então édado por:

M∑j=1

N j. (3.2)

Em todo este trabalho, será usada a nomenclatura como a da equação (3.1), os índicesk e l sobrescritos serão usados como índices dos robôs e os índices i e j subscritos serãousado como índices dos grupos (abstrações).

Neste trabalho são considerados sempre robôs no plano, assim, µ j possui duascomponentes

µ j =

µxj

µyj

, (3.3)

em que µxj e µy

j são as componentes x e y de µ j respectivamente.Faz-se cada abstração simétrica, dada por um círculo. A terceira variável de cada

abstração é dada por:

σ j =1

N j

N j∑k=1

[(xkj − µ

xj )

2 + (ykj − µ

yj )

2], (3.4)

e reflete a dispersão dos robôs em relação à média.O espaço de configurações do sistema com

∑ Mj=1N j robôs planares é dado por Q ≡

R2N j∗M [Choset et al., 2005].As variáveis de cada abstração são definidas pelo vetor:

φ j =

µx

j

µyj

σ j

. (3.5)

A partir destas variáveis tem-se o mapeamento:

φ j : Q→ G ≡ R3, (3.6)

onde a dimensão da variedade topológica G não é dependente da quantidade de robôsdo grupo.

As variáveis da abstração definem um círculo que contém todos os robôs do grupo.O centro do mesmo é dado pela média das posições de todos os robôs do mesmo grupoe o raio dado por

√N jσ j.

Note que∥∥∥qk− µ j

∥∥∥2≤

∑N j

k=1

∥∥∥qk− µ j

∥∥∥2= N jσ j ⇒

∥∥∥qk− µ j

∥∥∥ ≤ √N jσ j. Isto significa

que, por construção, todos os robôs associados com a abstraçãoφ j sempre permanecemdentro de sua abstração.

Outras formas de abstrações são possíveis, como elipses e quadrados no plano, como

3.2 Função de Potencial 16

apresentado em Belta and Kumar [2004]. Neste trabalho é usada uma abstração desimples construção por não haver necessidade de usar outros tipos de abstrações, alémdisso a abstração utilizada neste trabalho apresenta propriedades que possibilitam aprova apresentada no capítulo 4, como o fato de todos os robôs garantidamente estaremsempre dentro de sua abstração.

3.2 Função de Potencial

O uso de funções de potencial no controle de robôs já é algo consagrado na área derobótica. Uma das razões é a facilidade de usar o vetor obtido pela função de potencialdiretamente como um vetor a ser seguido por um controlador de mais baixo nível.

Esta seção apresenta a função de potencial proposta em Olfati-Saber [2006]. A leide controle a ser apresentada na metodologia deste trabalho será baseada no gradientedesta função. Esta função apresenta uma propriedade interessante que é possuir umfinite cut-off, isto significa que não haverá forças virtuais em agentes que estão muitodistante um do outro, o que pode ajudar a dar uma propriedade local ao algoritmo parasegregação em algumas circunstâncias. As funções de potencial utilizadas em Kumaret al. [2010] e Santos [2014] não possuiam esta propriedade.

No contexto original, esta função de potencial foi aplicada diretamente em umgrupo de robôs para que estes navegassem enquanto se mantinham agrupados. Nestetrabalho, esta função será aplicada para mover os centros das abstrações dos grupos derobôs.

Antes de apresentar a função de potencial, é necessária a definição de um mape-amento não negativo da norma para que a função de potencial seja diferenciável emtodos os pontos. Este mapeamento é chamado de σ-norm:

‖z‖σ =1ε

[√

1 + ε ‖z‖2 − 1], (3.7)

onde ε é um parâmetro que funciona como um ganho e permanece fixo neste trabalho ez é um escalar de qual está se calculando o σ-norm. Agora pode-se apresentar a funçãode potencial artificial:

V(µ) =12

∑j

∑i, j

ψα(∥∥∥µi − µ j

∥∥∥σ), (3.8)

onde:

ψα(z) =

∫ z

dαγα(s)ds, (3.9)

γα = ρh(z/rα)c(z − dα)√

1 + (z − dα)2, (3.10)

onde c é uma constante e dα define o mínimo global de ψα, sendo que dα = ‖d‖σ. O

3.2 Função de Potencial 17

parâmetro rα define o finite cut-off rα = ‖r‖σ. Isto significa que se dois agentes estiveremà uma distância maior que rα um do outro, não haverá forças artificiais de atração nemde repulsão entre estes dois agentes.

A função ρh(z) é chamada de função bump e varia suavemente entre 1 e 0:

ρh(z) =

1, z ∈ [0,h)

12

[1 + cos(π( z−h

1−h ))]

z ∈ [h,1]0, caso contrário.

(3.11)

Usando a função de potencial artificial são obtidas forças artificiais a partir dogradiente:

Fi = −∇µiV(µ), (3.12)

Fi =∑j∈Bi

γα(∥∥∥µi − µ j

∥∥∥σ)ni j +

∑j∈Bi

ρh(∥∥∥µi − µ j

∥∥∥σ/rα)(µ j − µi)︸ ︷︷ ︸

consenso de velocidade

, (3.13)

onde,

ni j = (µ j − µi)/√

(1 +∥∥∥µi − µ j

∥∥∥2). (3.14)

Na equação (3.13), o termo indicado como consenso de velocidade é usado para quetodos os agentes tenham a mesma velocidade quando a força de potencial estiver pertode 0, este termo pode ser visto como termo de amortecimento. Bi é o conjunto devizinhos do grupo i. Estes vizinhos são os grupos cujo os centros de suas abstraçõesestão a uma distância menor do que r do centro da abstração do grupo i.

A figura 3.1 mostra um exemplo das equações (3.9) e (3.10). O parâmetro c atuacomo um ganho, enquanto o parâmetro h modifica a suavidade da força. Para doisagentes quaisquer, a força de atração/repulsão será zero quando estiverem à distânciadesejada d e quando a distância entre eles for maior que r.

Se d < r < 2d, todo mínimo local desta função de potencial implica na formação deα-lattices [Olfati-Saber, 2006]. Formações α-lattices são estruturas em forma de treliçaem que cada um de seus vértices está a uma mesma distância d de todos os outrosvértices pertencentes a sua vizinhança. Estas formações devem satisfazer o conjuntode restrições algébricas dadas por:∥∥∥µi − µ j

∥∥∥ = d ∀ j ∈ Bi. (3.15)

A formação de α-lattices, provada em Olfati-Saber [2006] é importante na prova deconvergência do sistema para segregação, apresentada no capítulo 4.

3.3 Grafos 18

0 5 10 15−0.015

−0.01

−0.005

0

0.005

0.01

0.015

||µj − µ

i||σ

γ α

(b)

0 5 10 150

200

400

600

800

1000

||µj − µ

i||σ

ψα

(a)

Figura 3.1: Parâmetros: c = 0. 01, h = 0. 3, dα = 10, rα = 1. 8dα. (a) Potencial artificialentre dois agentes versus a distância entre eles. (b) Força artificial entre dois agentesbaseada no gradiente versus a distância entre eles.

3.3 Grafos

No capítulo 4 são usados conceitos da teoria de grafos, no contexto de se evitarcolisões entre robôs. A seguir são definidos conceitos básicos da teoria de grafos.

Um grafo é definido por:G = (V,E) (3.16)

comV sendo o conjunto de vértices e E o conjunto de arestas. Um outro grafo

G′ = (V′,E′) (3.17)

é um subgrafo de G = (V,E) seV′ ⊂ V e E′ ⊂ E [Bollobás, 1998].Um caminho é uma sequência de vértices em que existem arestas entre cada um dos

vértices do caminho. Um grafo ou subgrafo é conexo se quaisquer dois de seus vérticespuderem ser conectados por um caminho, se existirem dois vértices que não podemser conectados então o grafo ou subgrafo é desconexo. Os componentes conexos deum grafo são os subgrafos conexos maximais deste grafo, i.e. são os subgrafos que nãoestão contidos em outros subgrafos conexos.

A figura 3.2 mostra um exemplo de grafo conexo e um exemplo de grafo desconexo.

3.4 Estabilidade de Lyapunov 19

Figura 3.2: Dois grafos: G1 e G2. O grafo G1 é conexo e o grafo G2 é desconexo e possuidois subgrafos.

3.4 Estabilidade de Lyapunov

A metodologia deste trabalho faz uso da teoria da estabilidade de Lyapunov, que écapaz de analisar a estabilidade e a convergência de sistemas dinâmicos sem calcularexplicitamente as soluções de suas equações diferenciais [Slotine et al., 1991], [Khaliland Grizzle, 1996]. Mais especificamente, é utilizado o Lema de Barbalat para análise deestabilidade, que é baseado no lema de estabilidade de Lyapunov original.

No trabalho original de Lyapunov é apresentada uma função W(x) chamada defunção de Lyapunov. Em um sistema que tenha um ponto de equilíbrio em x = 0,considerando a função W(x) : Rn

→ R e sua derivada W(x) em que

• W(x) ≥ 0;

• W(x) = 0 se e somente se x = 0;

• W(x) ≤ 0;

então o sistema é dito estável segundo Lyapunov.O lema de Barbalat, que é baseado na estabilidade de Lyapunov original, diz que

considerando uma função de Lyapunov dependente do tempo W(x,t)

• Se W(x,t) for limitada inferiormente,

• W(x,t) ≤ 0 para qualquer valor de x;

• W(x,t) for uniformemente contínua no tempo.

então teremos que W(x,t) → 0 quando t → ∞. Para que W(x,t) seja uniformementecontínua no tempo, é suficiente mostrar que W é limitada.

3.5 Problema de Segregação em Enxames de Robôs 20

3.5 Problema de Segregação em Enxames de Robôs

Figura 3.3: Robôs circulares divididos em M = 3 com 3 robôs em cada grupo.

Considere∑M

j=1 N j robôs holonômicos movendo livremente em um plano com aposição de cada robô dada pelo vetor

qkj

=

xkj

ykj

k = 1,2,. . . ,N j. (3.18)

Estes N j robôs pertencem a um grupo dentre M grupos possíveis. O índice j indicaa qual grupo o robô pertence, j = 1,2,. . . ,M e N j indica o número de robôs do grupo j,i.e. qk

j é o vetor posição do robô k que pertence ao grupo j.Considere o modelo do tipo integrador simples em que cada robô é atuado direta-

mente em velocidade:qk

j= uk

jk = 1,2,. . .N j, (3.19)

considere também modelo do tipo integrador duplo em que cada robô é atuado emaceleração:

qkj

= vkj, vk

j= uk

jk = 1,2,. . .N j, (3.20)

nos dois modelos, ukj é a entrada de controle.

Agora que as abstrações e os modelos foram apresentados, pode-se definir o pro-blema de segregação.

Definição do problema: Sejam N robôs de M tipos com dinâmica dada por (3.19) ou (3.20),derive leis de controle individuais para cada robô que façam com que estes robôs permaneçam nointerior das abstrações às quais eles estão associados e além disso cada abstração φ j associada a

3.5 Problema de Segregação em Enxames de Robôs 21

estes robôs convirja para um estado em que:⋂j=1,...,M

φ j = ∅. (3.21)

Isto significa que no estado dito segregado, os robôs de um mesmo tipo estarãoagrupados, enquanto estarão separados dos robôs de outros tipos. A Figura 3.3 mostraum sistema segregado de acordo com a nossa definição, nesta Figura robôs do mesmotipo são da mesma cor e estão dentro da mesma abstração e as linhas conectando oscentros das abstrações representam a formação do α-lattice.

Capítulo 4

Metodologia

“To be is to do.”

Immanuel Kant

Durante o desenvolvimento deste trabalho, viu-se a possibilidade de desenvolveralgoritmos tanto para robôs do tipo integrador simples (atuados em velocidade) quantodo tipo integrador duplo (atuados em aceleração). Apesar dos dois algoritmos trataremdo mesmo problema, existem aplicações específicas para cada um. Pode-se imaginarestes algoritmos sendo aplicados em robôs usando um modelo puramente cinemáticosem maiores problemas, o que faz com que seja ideal o uso do algoritmo para robôsdo tipo integrador simples e também pode-se imaginar casos em que a dinâmica dosrobôs está presente, com isso pode-se usar o algoritmo para robôs do tipo integradorduplo em conjunto com uma técnica de linearização por realimentação de estados.

Os dois algoritmos são baseados na mesma ideia principal, que consiste em usarabstrações (ver Seção 3.1) que representem os grupos e usar uma função de potencial(ver Seção 3.2) para separar os grupos representados pelas abstrações. As próximasseções detalham os dois algoritmos propostos.

4.1 Robôs do tipo integrador simples

Nesta seção são considerados somente robôs do tipo integrador simples, equação(3.19). Para propor leis de controle individuais destes robôs, deve-se relacionar omovimento da abstração com o movimento dos robôs. Assim, diferenciando a equação(3.5), tem-se:

φ j = dφ jq j, (4.1)

4.1 Robôs do tipo integrador simples 23

onde q j = [x1j ,y

1j ,. . . ,x

N j

j ,yN j

j ]. Com base nas equações (3.1), (3.4) e (3.5) pode-se obterdφ j:

dφ j =1

N j

1 0 2(x1j − µ

xj )

0 1 2(y1j − µ

yj )

1 0 2(x2j − µ

xj )

0 1 2(y2j − µ

yj )

......

...

1 0 2(xN j

j − µxj )

0 1 2(yN j

j − µyj )

T

. (4.2)

Note que dφ j é a matriz Jacobiana do sistema.Para obter as leis de controle individuais, propõe-se:

u j = dφTj (dφ jdφT

j )−1u j +N u j, (4.3)

Note que det(dφ jdφTj ) =

(2σ j)n3 , então contanto que σ j , 0, o determinante é diferente de

zero, o que significa que a inversa sempre existe.O vetor u j é dado por

u j =

(u1

j)T

...

(uN j

j)T

(4.4)

e N é tal que dφ jN = 0. Conforme será mostrado adiante este segundo termo seráusado para tratar colisões entre robôs.

A variável u j é dada por:

u j =

kµUµj

kσUσj

, (4.5)

em que kµ e kσ são ganhos positivos. Desta forma, como q j = u j, ao substituir (4.3) em(4.1) tem-se que a evolução da abstração j será governada por:

φ j = u j. (4.6)

Agora, pode-se propor Uµj

e Uσj de forma a obter as leis de controle para cada robô.

Para separar os centros das abstrações, formando α-lattices (veja seção 3.2), faz-se:

Uµj

= F j, (4.7)

em que F j são as forças artificiais definidas na seção 3.2. Como estamos tratando derobôs do tipo integrador simples, que são atuados diretamente em velocidade, o termoapontado como consenso de velocidade da equação (3.13) deve ser desprezado, assim

4.1 Robôs do tipo integrador simples 24

Figura 4.1: Raio da abstração necessário para atingir segregação de acordo com adefinição do problema.

temosUµ

j= F j =

∑j∈B j

γα(∥∥∥µi − µ j

∥∥∥σ)ni j, (4.8)

onde ni j = (µ j − µi)/√

(1 +∥∥∥µi − µ j

∥∥∥2), γα é dada pela equação (3.10) e B j é o conjunto

de vizinhos do grupo j.Desta forma, no mínimo desta função potencial, cada abstração terá seu centro em

um vértice do α-lattice.Para controlar o tamanho de cada abstração, iremos propor um controlador Uσ

j deforma que cada abstração convirja para o tamanho desejado. Iremos também definir otamanho desejado σdes

j para que quando cada abstração atingir este tamanho, o sistemaesteja segregado de acordo com a nossa definição. Sabemos que o raio de cada abstraçãoé dado por R j =

√N jσ j. Assim, deve-se especificar o σdes

j de forma que o raio R j decada abstração seja menor que metade da distância d que é o tamanho de cada arestado α-lattice. Sendo assim: √

N jσdesj <

d2, (4.9)

σdesj <

d2

4N j. (4.10)

Agora, pode-se propor Uσj :

Uσj = σdes

j − σ j. (4.11)

Isto faz com que o tamanho de cada abstração convirja para o tamanho desejado σdesj .

O esquema da figura 4.1 mostra duas abstrações com uma reta ligando o centrodas mesmas, esta reta é uma aresta do α-lattice. O raio R j necessário para que hajasegregação dos grupos de acordo com a definição do problema no capítulo (3) tambémé destacado.

4.1 Tratamento de colisões 25

Figura 4.2: Estratégia para evitar colisões usada em Michael et al. [2007].

4.1.1 Tratamento de colisões

As leis de controle propostas até aqui foram projetadas pensando em robôs pontuais,ou seja, não consideram o tamanho de cada robô. Para que a proposta possa ser usadana prática, deve-se considerar o tamanho de cada robô, com isso deve-se formularestratégias que tratem do problema de colisões entre robôs. Para que o tratamento decolisões não interfira na convergência para segregação, será considerado o controle noespaço nulo de dφ j. Este é o termo referente à matrizN apontado na equação (4.3).

Em Michael et al. [2007] é usada uma estratégia parecida, também no espaço nulo dedφ j, porém usando agrupamentos entre três robôs para evitar as colisões. Quando umrobô está em iminência de colisão, outros dois robôs do mesmo grupo são escolhidosarbitrariamente para “corrigir” o estado da abstração enquanto o robô em iminênciade colisão corrige sua rota afim de evitar a colisão. Estes agrupamentos são baseadosna distância entre os três robôs em questão tomada duas a duas.

Para o caso de robôs em duas dimensões, o espaço nulo para cada tríade de robôs(robôs 1, 2 e 3) é dado por:

N(dφ) = λ123

(x2 − x3)(y2 − y3)(x3 − x1)(y3 − y1)(x1 − x2)(y1 − y2)

(4.12)

em que λ123 deve ser escolhido de forma que as colisões sejam evitadas.Então o tratamento de colisão de Michael et al. [2007] funciona “escolhendo-se” um

vetor tal que o robô em iminente colisão possa escapar da colisão e adicionando nocontrolador dos outros dois robôs da tríade, vetores complementares ao primeiro. Oesquema da figura 4.2 ilustra estes vetores complementares com robôs de índices 1,2 e3, i.e. caso o robô R1 esteja em iminente colisão com algum outro robô e “escolha” ovetor u1 para escapar desta colisão, então os robôs R2 e R3 terão que adicionar em suaentrada de controle os vetores u2 e u3 respectivamente para compensar o movimento

4.1 Tratamento de colisões 26

do robô R1.Nesta dissertação estes agrupamentos não são necessários, é considerado o espaço

nulo de todos os robôs do grupo. Para este sistema o espaço nulo de dφ j é gerado por:

NullSpace(dφ j) = (I − dφTj (dφ jdφT

j )−1dφ j)u j = N u j, (4.13)

onde I é a matriz identidade. Este termo do controlador só será ativado quando fordetectada uma colisão iminente: ∥∥∥∥qk

i− ql

j

∥∥∥∥ < 2Rb + δ, (4.14)

em que os índices i e j indicam a quais grupos estes robôs pertencem, e os índices k e lindicam quais dos robôs estão em iminente colisão. Neste trabalho, são consideradosrobôs circulares de raio Rb. Um pequeno fator de segurança δ é adicionado para efeitospráticos. Então, as leis de controle individuais em situações de colisão iminente paraum grupo são determinadas a partir de:

u j = dφTj (dφ jdφT

j )−1u j + (I − dφTj (dφ jdφT

j )−1dφ j)u j. (4.15)

O vetor u j é escolhido para garantir que não haverá uma colisão. Para que a interfe-rência da estratégia proposta nos estados dos robôs seja energeticamente eficiente, u j éminimizado. Define-se o problema de otimização:

min∑j∈Ωp

∥∥∥u j

∥∥∥2,

s. t. (uki− ul

j)T(qk

i− ql

j) ≥ 0,para qualquer qk

i− ql

jsatisfazendo (4. 14).

(4.16)

Esta restrição tem o efeito de fazer com que os robôs se repilam quando estiverem àuma distância menor que 2Rb + δ.

O conjunto Ωp é o conjunto de grupos nos quais existem robôs em iminente colisão,sendo que o índice p é dado pelo número de componentes conexos no grafo de colisões(ver Figura 4.3 e Seção 3.3). Neste grafo cada abstração é um nó e existe aresta entrenós que contenham colisões iminentes entre robôs dos grupos.

A Figura 4.3 mostra uma situação em que o grafo possui dois componentes conexos(p = [1,2]), nesta situação, há dois problemas de otimização independentes, um comdois grupos envolvidos e outro com três grupos envolvidos.

Em cada problema de otimização, na função objetivo são considerados todos osgrupos em que há robôs envolvidos na colisão iminente, e são considerados todos osoutros robôs destes grupos. De posse de todas estas informações, cada robô pode rodaro problema de minimização internamente.

Para cada par de robôs envolvidos é adicionada uma nova restrição responsávelpor garantir que este par de robôs não irão colidir com as novas leis de controle.

4.1 Análise do controlador 27

Figura 4.3: Robôs em iminência de colisão.

As colisões entre robôs de um mesmo grupo também são consideradas da mesmaforma, adicionando uma nova restrição para cada par de robôs em iminência de colisão.

A estratégia proposta é parecida com a estratégia proposta em Michael et al. [2007],porém, ao invés de apenas dois outros robôs serem usados para compensar os movi-mentos do robô escapando da colisão, todos os robôs do grupo são usados.

4.1.2 Análise do controlador

Nesta seção apresentamos a análise formal do controlador proposto.

Teorema 1. Aplicando a lei de controle individual dada por (4.5), (4.8), (4.11) e (4.15) em∑Mj=1 N j robôs com dinâmica dada por (3.19) divididos em M grupos e assumindo que as colisões

são resolvidas de acordo com (4.16) e que não há situações em que todos os robôs do mesmogrupo estão em um mesmo ponto ao mesmo tempo e o sistema não começa em um ponto de selaou máximo global de V(µ), o sistema irá convergir para um estado no qual todos os robôs deum mesmo grupo estão agrupados enquanto estão separados de robôs de outros grupos, i.e, oproblema definido na Seção 3.5 será resolvido.

Demonstração. A prova da convergência é feita em duas partes. Primeiro deve-se provarque o sistema de malha fechada de cada abstração converge para o tamanho desejado(σdes

j ). Depois deve-se provar que os grupos se afastam o suficiente.Para a prova de convergência, fazem-se três suposições:

1. O sistema não começa em um ponto de sela ou um máximo local de V(µ) [Olfati-Saber, 2006].

2. Não há situações em que todos os robôs de um mesmo grupo estão em um mesmoponto.

3. Todas as colisões podem ser resolvidas, i.e., o problema de minimização (4.16),sempre tem solução viável.

4.1 Análise do controlador 28

Sabemos que det(dφ jdφTj ) =

2σ j

(N j)3 , e com a suposição 2 sabemos que σ j , 0, assimdφ jdφT

j sempre terá inversa e o movimento das abstrações será dado pela equação (4.6),além disso, como o controlador de evitamento de colisões opera no espaço nulo dedφ j tem-se que a evolução das abstrações não será alterada por esta componente. Asuposição 3 apenas garante que a evolução das abstrações não será perturbada pelaocorrência de colisões entre robôs, de tal forma que um possa impedir o movimentodo outro.

Para a primeira parte da prova, sabe-se que para qualquer valor positivo de kσ adinâmica dada por σ j = kσ(σdes

j −σ j) sempre fará σ j convergir exponencialmente para σdesj

[Slotine et al., 1991], além disso, sabemos pela seção 3.1 que todos os robôs associadoscom uma abstração sempre permanecem dentro da mesma.

Para a segunda parte da prova considere,

W = V(µ), (4.17)

onde µ = [µT1,µT

2,. . . ,µT

M]T e V(µ) é dada por (3.8).

Calculando W:W = ∇VTµ. (4.18)

Porém, conforme definido em (3.12) e (4.7), temos que as forças artificiais são aplicadasno centro das abstrações, isto é:

µ = −∇V. (4.19)

Logo,W = − ‖∇V‖2 ≤ 0. (4.20)

Por outro lado, tem-se que W ≥ 0, ou seja, W é limitado inferiormente. Para que sepossa concluir que W é uniformemente contínuo, W deve ser limitado. Temos que,

W = −∇VT∇V. (4.21)

W = −2∇VT d∇Vdt

, (4.22)

Calculando d(∇V)dt :

d(∇V)dt

=ddt

∇µ1V∇µ2V...

∇µMV

=

∂∂µ (∇µ1V)T

∂∂µ (∇µ2V)T

...∂∂µ (∇µMV)T

︸ ︷︷ ︸J

µ︸︷︷︸∇V

(4.23)

4.2 Robôs do tipo integrador duplo 29

Substituindo na equação (4.22),

W = 2∇VT J∇V, (4.24)

como∇µ jV(µ) =

∑j∈B j

γα

( ∥∥∥µi − µ j

∥∥∥σ

)ni j, (4.25)

através da definição das funções γα (equação (3.10)) e ni j (equação (3.14)), tem-se que

∇µ jV(µ) = 0 se∥∥∥µi − µ j

∥∥∥σ> r, (4.26)

i.e. ∇µ jV(µ) = 0 é limitada pelo finite cut-off r. A derivada parcial de ∇µ jV(µ) é dada por:

∂∂µ

[∇µ jV(µ)

]=∂∂µ

[∑j∈B j

γα

( ∥∥∥µi − µ j

∥∥∥σ

)ni j

], (4.27)

podemos perceber com a definição das funções γα e ni j que a derivada da equação(4.27) existe e não se torna ilimitada na região

∥∥∥µi − µ j

∥∥∥σ< r. Isto significa que J

também é limitado, então podemos concluir que W é limitado e consequentemente Wé uniformemente contínuo.

Portanto, utilizando o Lema de Barbalat (Lema 4.3 em Slotine et al. [1991]) conclui-seque W → 0 quando t→ ∞. Como W = 0 implica em ∇V = 0 e assumindo a suposição1 como verdadeira, isto só ocorre se os grupos estiverem a uma distância maior quer (finite cut-off da função de potencial) ou se estiverem numa formação tipo α−latticea uma distância d (ponto onde ocorre o mínimo de V(µ), veja Olfati-Saber [2006]).Ou seja, o sistema converge para uma situação em que as abstrações estarão a umadistância maior ou igual a d.

Como as abstrações atingem um tamanho especificado respeitando a equação (4.10),então o problema de segregação como definido na seção 3.5 é resolvido.

4.2 Robôs do tipo integrador duplo

Foi desenvolvido também um algoritmo para robôs do tipo integrador duplo. Aabordagem também consiste em acoplar o uso de abstrações (ver seção 3.1) com umafunção de potencial (ver seção 3.2).

Como os robôs têm dinâmica do tipo integrador duplo, deve-se relacionar o movi-mento da abstração com a aceleração dos robôs. Diferenciando a equação (3.4) duas

4.2 Robôs do tipo integrador duplo 30

vezes, temos

σ j =2

N j

x1j − µ

xj

y1j − µ

yj

x2j − µ

xj

y2j − µ

yj

.

.

.

xN j

j − µxj

yN j

j − µyj

T

¨q j + 2σ′j, (4.28)

onde,

σ′j =1

N j

N j∑i=1

(xi − µxj )

2 + (yi − µyj )

2, (4.29)

em que ¨q j = [x1j ,y

1j ,. . . ,x

N j

j ,yN j

j ]. Agora, podemos escrever

φ j = dφ j ¨q j +

00

2σ′j

, (4.30)

em que dφ j é o mesmo definido na seção 4.1. Para propor leis de controle para cadarobô de um mesmo grupo de forma a guiar a dinâmica da abstração correspondentefazemos

uk = dφTj (dφ jdφT

j )−1

−

00

2σ′j

+ u j

, (4.31)

em que φ j é a abstração à qual o robô k pertence e u j deve ser projetada para controlaro estado da abstração. Como foi mostrado anteriormente, det(dφ jdφT

j ) =(2σ j)

n3 , entãocontanto que σ j , 0, a inversa desta matriz sempre existe. A partir da equação (4.30),aplicando a lei de controle da equação (4.31) em todos os robôs, cada abstração semoverá de acordo com

φ j = u j, (4.32)

em que u j é uma entrada virtual para a abstração j e será dada por:

u j =

kµUµj

Uσj

. (4.33)

onde Uµj

é a força artificial que guia a média do grupo, Uσj determina a evolução do

tamanho da abstração e kµ é um ganho positivo. A escolha adequada de Uµj

e Uσj

4.2 Tratamento de Colisões 31

determinará o sucesso da abordagem.Assim como na seção 4.1, fazemos

Uµj

= F j, (4.34)

com a intenção de que os centros das abstrações formem α-laticces. Como nessa seçãoestamos tratando de robôs atuados em aceleração, usamos a força F j exatamente comodescrita na seção 3.2.

Utilizamos também o mesmo tamanho desejado para cada abstração da seção 4.1:

σdesj <

d2

4N j. (4.35)

Propomos agora um novo controlador Uσj :

Uσj = σdes

j + k1(σdesj − σ j) + k2(σdes

j − σ j), (4.36)

Podemos fazer σdesj constante, σdes

j e σdesj iguais a zero, para que o tamanho da

abstração tenha velocidade e aceleração igual a zero quando t→∞.Então, cada robô individual será guiado pelas leis de controle dadas pelas equações

(4.33), (4.34), (4.35) e (4.36), como se segue:

uk = kµUµj

+(qk − µ j)

σ j[2σ′j − k1σ j + k2(σdes

j − σ j)], (4.37)

Os parâmetros kµ,k1 e k2 podem ser fixados e iguais em todas as abstrações.A lei de controle individual (equação (4.37)) é dependente do número de robôs de

cada abstração, do estado do próprio robô, do estado da abstração a qual este robôpertence e do estado das abstrações vizinhas.

4.2.1 Tratamento de Colisões

Na lei de controle individual (equação 4.37) são considerados robôs pontuais, paraque possam ser considerados robôs com tamanho real deve-se propor uma estratégiapara evitar colisões entre os robôs. Da mesma forma que na seção 4.1 (ver equação(4.15)), o controlador para evitamento de colisões será no espaço nulo do controladororiginal. Apesar destas semelhanças, a estratégia para robôs do tipo integrador duplodifere da estratégia para robôs do tipo integrador simples.

Analoga à seção 4.1, as leis de controle individuais em situações de colisão iminente

4.2 Tratamento de Colisões 32

é dada por:

uk = dφTj (dφ jdφT

j )−1

−

00

2σ′j

+ u j

+ (I − dφTj (dφ jdφT

j )−1dφ j)u j. (4.38)

Por ser uma estratégia computacionalmente mais cara que a estratégia da seção 4.1e por estarmos tratando de robôs atuados em aceleração, para evitar alguns cálculosdesnecessários, fazemos uma nova consideração em relação ao tratamento de colisãoda seção 4.1. Agora, para que o controlador de evitamento de colisões seja acionado,os robôs em iminente colisão devem satisfazer a mesma condição da seção 4.1,∥∥∥∥qi

k− q j

l

∥∥∥∥ < 2Rb + δ, (4.39)

condição esta que diz se este par de robôs está suficientemente perto. Além disso, paraque o controlador de evitamento de colisões seja acionado, este par de robôs deve estarem uma rota que gerará uma colisão, i.e.

(qik− q j

l)T(qi

k− q j

l) < 0. (4.40)

Como os robôs agora são do tipo integrador duplo, atuados em aceleração, o contro-lador para evitamento de colisões deve buscar novas acelerações que gerem trajetóriaslivres de colisão. O evitamento de colisões é baseado na equação de Torricelli de movi-mento uniformemente variado:

v2f = v2

0 + 2a∆s, (4.41)

em que v f é a velocidade final do robô em questão, v0 é a velocidade inicial, a é aaceleração e ∆s é a diferença no deslocamento em um determinado período de tempo.Para obter uma aceleração a em que os robôs em iminência de colisão não colidam,consideramos uma abordagem conservadora fazendo v f = 0. Isto significa que no piorcenário possível, ambos os robôs deverão parar completamente no instante antes dapossível colisão. Então fazemos ∆s igual à metade da distância entre os dois robôs emquestão, menos o raio do robô:

∆s =12

∥∥∥∥qki− ql

j

∥∥∥∥ − Rb, (4.42)

considerando que ambos os robôs possuem raio Rb. Considerando a aceleração a dorobô i do grupo k na direção oposta à do robô j do grupo l:

a = (uki)T

(qlj− qk

i)∥∥∥∥ql

j− qk

i

∥∥∥∥ , (4.43)

4.2 Tratamento de Colisões 33

e considerando a velocidade v0 do robô i em direção ao robô j

v0 = (qki)T

(qlj− qk

i)∥∥∥∥ql

j− qk

i

∥∥∥∥ . (4.44)

Substituindo v f = 0 na equação de Torricelli, temos

a =0 − v2

0

2∆s. (4.45)

A figura 4.4 mostra um exemplo com dois robôs em iminência de colisão (robô k erobô l) que podem ou não fazer parte de um mesmo grupo. Nesta figura, são destacadoso ∆s (equação (4.42)), a aceleração a (equação (4.43)) e a velocidade v0 (equação (4.44))referentes ao robô k.

Substituindo ∆s, a e v0 em (4.45), temos uma restrição do robô i em relação ao robôj:

(uki)T

(qki− ql

j)∥∥∥∥qk

i− ql

j

∥∥∥∥ ≥[(qk

i)T (ql

j−qk

i)∥∥∥∥∥ql

j−qk

i

∥∥∥∥∥]2

∥∥∥∥qki− ql

j

∥∥∥∥ − 2Rb

, (4.46)

analogamente temos para o robô j em relação ao robô i:

(ulj)T

(qlj− qk

i)∥∥∥∥ql

j− qk

i

∥∥∥∥ ≥[(ql

j)T (qk

i−ql

j)∥∥∥∥∥qk

i−ql

j

∥∥∥∥∥]2

∥∥∥∥qlj− qk

i

∥∥∥∥ − 2Rb

. (4.47)

Com isso, temos duas restrições que se forem respeitadas a todo momento, nuncahaverá colisões entre robôs. Apesar de serem usados índices k e l para tratar dosgrupos, caso dois robôs de um mesmo grupo estejam em iminente colisão, estas mesmasrestrições são usadas para tratar desta iminente colisão.

Para que a estratégia seja energeticamente eficiente, definimos o problema de mini-

4.2 Tratamento de Colisões 34

Figura 4.4: Esquema exemplificando a estratégia para evitar colisões.

mização:min

∑s∈Ωp

‖us‖2 ,

s. t. (uki)T

(qki− ql

j)∥∥∥∥qk

i− ql

j

∥∥∥∥ −[(qk

i)T (ql

j−qk

i)∥∥∥∥∥ql

j−qk

i

∥∥∥∥∥]2

∥∥∥∥qki− ql

j

∥∥∥∥ − 2Rb

≥ 0,

(ulj)T

(qlj− qk

i)∥∥∥∥ql

j− qk

i

∥∥∥∥ −[(ql

j)T (qk

i−ql

j)∥∥∥∥∥qk

i−ql

j

∥∥∥∥∥]2

∥∥∥∥qlj− qk

i

∥∥∥∥ − 2Rb

≥ 0,

(4.48)

em que Ωp é o mesmo definido na seção 4.1, assim, o índice s indica qual dos gruposem que há robôs em iminente colisão está sendo tratado. As restrições do problema deminimização (4.48) são adicionadas para cada par de robô que atenderem as condiçõesdas equações (4.39) e (4.40). Se dois robôs dos grupos i e j estiverem em iminentecolisão, por exemplo, a função objetivo do problema de minimização (4.48) se torna

min ‖ui‖2 +

∥∥∥u j

∥∥∥2, (4.49)

com as restrições dadas pelas equações 4.46 e 4.47.As outras considerações sobre o problema de otimização da seção 4.1 também são

válidas, o que difere as abordagens são as restrições propostas para o problema deotimização e as condições de acionamento do tratamento de colisões.

4.2 Tratamento de Colisões 35

4.2.2 Análise do controlador

Nesta seção analisa-se formalmente o controlador proposto para demonstrar suaeficiência na resolução do problema de segregação em enxames de robôs.

Teorema 2. Aplicando a lei de controle individual dada pela equação (4.37) em∑M

j=1 N j robôscom dinâmica dada por (2.1) divididos em M grupos e assumindo que as colisões são resolvidasde acordo com (4.48) e que não há situações em que todos os robôs do mesmo grupo estão em ummesmo ponto ao mesmo tempo e o sistema não começa em um ponto de sela ou máximo globalde V(µ), o sistema irá convergir para um estado no qual todos os robôs de um mesmo grupoestão agrupados enquanto estão separados de robôs de outros grupos, i.e, o problema definido naseção 3.5 será resolvido.

Demonstração. O método foi construído de forma a garantir a solução do problema, oque significa que a prova é apresentada de forma direta. Assim como na seção 4.1 aprova é feita em duas partes. A primeira parte é muito parecida com a primeira parteda seção 4.1, com exceção do controlador Uσ

j (equação (4.36)) que é diferente, mas quetambém apresenta convergência exponencial se os ganhos k1 e k2 forem projetados paraque o sistema de malha fechada da equação (4.36) tenha todos os pólos no semi-planoesquerdo [Slotine et al., 1991]. Além disso, é importante que os ganhos k1 e k2 sejamprojetados de forma que não haja muito overshoot para tentar reduzir rotas que podemgerar colisões. O resto da primeira parte da prova é omitida por ser idêntica à seção4.1, isto inclui as 3 suposições feitas.

A segunda parte da prova é mostrar que as abstrações estarão suficientementeseparadas, i.e. não haverá interseção entre elas. Consideramos a prova do teorema1 em Olfati-Saber [2006], neste teorema o princípio de invariância de LaSalle é usadopara mostrar que um grupo de agentes com dinâmica dada pela equação (2.1) sujeitoà função de potencial artificial dada pela equação (3.13) (ver Algorithm 1 em Olfati-Saber [2006]) converge assintoticamente para uma configuração que é um equilíbrio dafunção V(µ).

Como assumimos que o sistema não começa em um máximo local ou em um pontode sela de V(µ) e estes são pontos de equilíbrio instáveis, podemos garantir que osistema converge assintoticamente para um mínimo local de V(µ).

Usando o Lema 3 em Olfati-Saber [2006], sabemos que todo mínimo local de V(µ)forma um α−lattice e vice-versa. Especificando-se outros parâmetros (ver equação 4.35)de forma a garantir ausência de interseções entre as abstrações, então o problema desegregação como definido na seção 3.5 será resolvido quando t→∞.

Sabemos que o controlador para evitamento de colisões opera no espaço nulo docontrolador original. Assim, se o controlador para evitamento de colisões for utilizadoe o problema de otimização da equação (4.48) sempre tiver solução viável, então aprova do teorema 2 continua válida e o sistema também converge para segregaçãoneste cenário.

Capítulo 5

Simulações e Resultados Experimentais

“The true delight is in the finding out rather than in the knowing.”

Isaac Asimov

Existem diversas plataformas que permitem simular o comportamento de robôscomputacionalmente. Algumas destas plataformas permitem a simulação de enxamesde robôs. Em Kramer and Scheutz [2007] e Craighead et al. [2007] são discutidasalgumas plataformas tanto comerciais quanto open-source.

A plataforma descrita em Pinciroli et al. [2012] foi desenvolvida com o propósito desimular robôs heterogêneos e, além disso, esta plataforma possui uma arquitetura quepermite fazer uso de todos os núcleos dos atuais processadores de mútiplos núcleos.

Neste trabalho foram escolhidas duas plataformas diferentes para realizar as si-mulações. Primeiro, utiliza-se o MATLAB [MathWorks, 2014], ambiente que permiteque várias ferramentas de visualização de dados sejam facilmente usadas e possui umgrande número de bibliotecas com funções úteis já implementadas.

Posteriormente, com o intuito de analisar os dois algoritmos em um ambiente maispróximo da realidade, os algoritmos foram implementados no ROS (Robot OperatingSystem) [Quigley et al., 2009]. O ROS é um conjunto de ferramentas computacionaisque permitem simular robôs de diferentes tipos. Dentro do ROS existe uma ferramentachamada Stage que facilita na simulação de robôs móveis em duas dimensões. Usandoo ROS/Stage é possível fazer com que o mesmo código usado nas simulações rodeem robôs reais com apenas algumas modificações, isto faz com que a transição dasimulação para o uso com robôs reais seja muito simples se comparado com outrosambientes.

Tanto no ROS/Stage quanto no MATLAB, uma grande vantagem em relação a outrossimuladores é a vasta popularidade entre pesquisadores, o que possibilita recorrer àajuda da comunidade científica na implementação dos algoritmos. No trabalho deVaughan [2008] são feitos benchmarks com enxames de robôs de modo a avaliar tempode processamento do projeto Player com este tipo de sistema. Para testar os algoritmosaqui propostos não havia necessidade de usar plataformas dedicadas ao uso de enxamesde robôs, com isso as plataformas MATLAB e ROS/Stage foram adequadas.

5.1 Simulações 37

Após todas as simulações os dois algoritmos foram aplicados em robôs reais paraanalisá-los mesmo com os ruídos, dinâmicas não modeladas e os erros de localizaçãodos robôs, que são problemas comuns em situações reais.

Nas próximas seções serão mostradas algumas simulações e experimentos.

5.1 Simulações

Em todas as simulações todos os robôs começam parados e a posição inicial dosrobôs é de acordo com uma distribuição aleatória Gaussiana. A escolha desta distribui-ção inicial visa mostrar os algoritmos propostos em situações em que os robôs começambem misturados. Cada grupo é representado por uma cor específica e os robôs perten-centes a este grupo são desta mesma cor. Todas as simulações foram paradas quandonão havia mais forças artificiais entre os centros das abstrações e as abstrações haviamatingido o tamanho desejado (σdes

j ), i.e. quando o problema de segregação foi resolvidoconforme a definição do capítulo 3.

O tamanho desejado das abstrações (σdesj ) é especificado de modo a respeitar mini-

mamente a equação (4.10):

σdesj =

d2

4N j− δσ ∀ j, (5.1)

em que δσ é um pequeno valor positivo.Em todas as simulações, tanto em ambiente MATLAB quanto em ambiente ROS/Stage,

a solução do problema de minimização das equações (4.16) e (4.48) é obtido com ajudada função f mincon do MATLAB. O f mincon é um popular solver de programaçãonão-linear. Na simulação em ROS/Stage, a função f mincon do MATLAB roda simulta-neamente com o programa em C++ do ROS/Stage.

5.1.1 Robôs do tipo Integrador Simples

Figura 5.1: Sequência de quadros de uma simulação.

Uma simulação que exalta os aspectos qualitativos da proposta em ambiente MA-TLAB é mostrada na figura 5.1. Neste exemplo são usados 6 grupos com 6 robôs emcada.

5.1 Robôs do tipo Integrador Simples 38

Figura 5.2: (a) Evolução do “tamanho” de cada abstração. (b) Mínima distância entreos centros das abstrações ao longo do tempo.

Figura 5.3: Mínima distância entre robôs.

Cada robô é modelado como um círculo e é usado o modelo cinemático da equação(3.19). O tamanho de cada abstração é representado pelos círculos maiores. Cadaabstração é identificada por uma cor, seus robôs por esta cor.

No último quadro da figura 5.1 também é destacada a formação do α-lattice.Os ganhos c, kµ e kσ usados foram 1; 10 e 0,5 respectivamente. Os ganhos c e kµ se

fundem e usando c = 1, temos que o ganho kµ é o único que controla a intensidade daforça artificial aplicada nos centros das abstrações. O parâmetro h usado foi 0,4 e foiusado d = 1,5r. O raio dos robôs foi definido Rb = 15 e foi usado δσ = 0,1. Os outrosparâmetros como a distribuição dos robôs e o finite cut-off r foram definidos para quese possa melhor avaliar visualmente a proposta.

5.1 Robôs do tipo Integrador Duplo 39

A figura 5.2 mostra a evolução do tamanho (σ) de cada abstração e a mínimadistância entre os centros das abstrações ao longo do tempo. Pode-se observar que asabstrações atingem o tamanho desejado antes de chegarem à distância desejada d, istopode ser alterado regulando os ganhos kµ e kσ. Através da figura 5.1 com ajuda dosgráficos da figura 5.2, pode-se perceber que a segregação é atingida com sucesso. Umaanálise da figura 5.1 e do gráfico da figura 5.3 permite concluir que não houve colisõesentre robôs, apesar de que com os parâmetros escolhidos, principalmente o δσ usado,vários robôs ficam muito próximos em muitos momentos.

5.1.2 Robôs do tipo Integrador Duplo

O controlador proposto foi testado em duas plataformas diferentes, ROS/Stage eMATLAB. No ROS/Stage foram usados robôs à tração diferencial e no MATLAB foiusado um modelo de robô holonômico. Nesta seção são apresentadas uma simulação noROS/Stage e três simulações no MATLAB. No MATLAB o intuito era testar a viabilidadeda proposta com um variado número de robôs e grupos. No ROS/Stage o interesseera analisar o controlador em um ambiente de simulação mais próximo da realidade, eainda servir como base para a implementação em robôs reais.

A figura 5.4 mostra três simulações feitas no MATLAB usando o algoritmo pararobôs do tipo integrador duplo. Nestas simulações cada grupo possui 5 robôs e sãofeitas simulações com 5, 10 e 15 grupos de robôs. No último quadro de cada simulaçãotambém é destacado a formação dos α-lattices e o tamanho das abstrações.

Os ganhos c, kµ, k1 e k2 foram ajustados juntamente com o passo de integração dasimulação para que se pudesse evitar erros numéricos e ainda ter um baixo tempo deprocessamento. Os outros parâmetros foram variados em cada simulação de formaque fosse visualmente possível ver a segregação ocorrendo.

A figura 5.5 mostra quadros de uma simulação em ROS/Stage. Foi usada a técnicade linearização por realimentação de estados [Desai et al., 1998] para que fosse possívelusar o controlador proposto com robôs à tração diferencial. Esta simulação é importantepara servir de ponte entre as simulações feitas no MATLAB e a implementação em robôsreais. Esta simulação serve também para demonstrar o algoritmo proposto em umasituação em que os grupos estão desbalanceados.

Para destacar melhor a propriedade “local” do controlador proposto comparadoaos trabalhos de Kumar et al. [2010] e Santos [2014], a figura 5.6 mostra a média donúmero de grupos na vizinhança Bi ao longo do tempo, isto é, a média de informaçõesque cada robô precisa do instante inicial até a segregação ser obtida. Pode-se observarque nas três simulações após a iteração 10000 cada robô precisa de informações de até4 grupos, em média, em sua vizinhança.

5.2 Plataforma de testes com Robôs Reais 40

Figura 5.4: Da esquerda para a direita: Quadros das simulações com 75, 50 e 25 robôs.De cima para baixo: Sequência de quadros de três simulações.

5.2 Plataforma de testes com Robôs Reais

Para os testes com robôs reais foi utilizada a plataforma experimental descrita emGarcia and Chaimowicz [2009], situada no laboratório de Visão e Robótica (VeRLab) doDepartamento de Ciência da Computação da Universidade Federal de Minas Gerais.Esta plataforma possui uma câmera para localização dos robôs através de tags colocadasacima dos mesmos. Em Bosque [2009], é utilizada esta mesma plataforma aplicando oalgoritmo proposto em Pimenta et al. [2013b].

5.2 Plataforma de testes com Robôs Reais 41

Figura 5.5: Quadros de uma simulação no ambiente ROS/Stage com 20 robôs distribuí-dos desigualmente em 4 grupos. Da esquerda para direita: Situação inicial, situaçãointermediária e situação final.

Iterações ×104

0 0.5 1 1.5 2 2.5 3

Núm

ero

de g

rupo

s na

viz

inha

nça

Bi

4

6

8

10

12

14

16

5 grupos10 grupos15 grupos

Figura 5.6: Média da informação de quantos grupos vizinhos que cada robô precisa aolongo do tempo.

Foram usados robôs e-puck [Cianci et al., 2007], como o mostrado na figura 5.8. Porserem de pequeno porte e possuirem diferentes sensores embarcados, estes robôs sãomuito utilizados pela comunidade científica e para fins didáticos. Nesta plataforma,estes robôs são atuados diretamente em velocidade.

Os robôs e-puck são à tração diferencial, ou seja, possuem apenas duas rodas. Apesardos diversos sensores e da possibilidade de processamento embarcado, todo o proces-samento foi feito por um computador externo e a localização pela câmera externa, porjá estar implementado desta forma na plataforma usada.

Como os robôs utilizados são movidos à tração diferencial, é usada a linearização porrealimentação de estados [Desai et al., 1998] para que seja possível utilizar a estratégiaproposta em robôs deste tipo. Os robôs são modelados como sendo um quadradoinscrito em um círculo de raio igual à metade da diagonal do quadrado. Para efeito dametodologia proposta o tamanho dos robôs é considerado como sendo o tamanho doscírculos. A figura 5.7 mostra dois dos robôs e-puck usados, em um deles são indicadoso raio e o tamanho considerados na abordagem proposta.

Todo o processamento é feito em um computador com ajuda dos pacotes do ROS

5.2 Resultados Experimentais com Robôs do tipo Integrador Simples 42

Figura 5.7: Tamanho do robô considerado.

e a solução dos problemas de minimização das equações (4.16) e (4.48) são obtidoscom ajuda da função f mincon do MATLAB, rodando simultaneamente com o ROS. Umoutro computador é utilizado para ajudar na comunicação entre computador e robôssimplesmente pelo limite de conexões bluetooth que cada computador consegue receber.O segundo computador recebe informações processadas no primeiro computador poruma rede Wi-Fi local e repassa para os robôs a ele conectados.

5.2.1 Resultados Experimentais com Robôs do tipo Integrador Sim-ples

Um experimento com 9 robôs e-puck [Mondada et al., 2009] é apresentado a seguir.Os 9 robôs são divididos em 3 grupos com 3 robôs em cada um dos grupos. Quadrosdeste experimento são mostrados na figura 5.9.

Um vídeo com o experimento mostrado na figura 5.9 e com a simulação mostradana figura 5.1 pode ser encontrado em https://youtu.be/BH5Hk_NVNxc.

5.2.2 Resultados Experimentais com Robôs do tipo Integrador Duplo

Também foi feito um experimento com algoritmo para robôs do tipo integradorduplo. Foram usados 6 robôs e-puck divididos igualmente em três grupos. Quadrosdeste experimento são mostrados na figura 5.10.

O algoritmo para robôs do tipo integrador duplo necessita de informações sobre avelocidade dos robôs, essa informação não pôde ser obtida de forma confiável por causados pequenos erros na localização dos robôs. Assim, no problema de minimizaçãoda equação (4.48) foram utilizados a máxima velocidade que os robôs eram capazesde atingir ao invés de sua velocidade real, para que se pudesse fazer o tratamento decolisões. Obviamente esta é uma solução conservadora, mas que não provoca nenhumaalteração na prova de convergência para segregação do sistema..

5.2 Resultados Experimentais com Robôs do tipo Integrador Duplo 43

Figura 5.8: Um robô e-puck.

Figura 5.9: Sequência de quadros do experimento com robôs e-puck usando o algoritmodo tipo integrador simples.

Na figura 5.11(b) tem-se a evolução do centros das abstrações, em que os círculossão o tamanho das abstrações no instante final e na figura 5.11(d) tem-se a evoluçãodos próprios robôs, em que o asterisco indica a posição final dos mesmos. Nas figuras5.11(a) e 5.11(c) são mostrados a evolução do tamanho das abstrações e a distânciamínima entre robôs ao longo do tempo, respectivamente.

Com ajuda dos gráficos mostrados na figura 5.11 é possível concluir que a segregaçãofoi atingida com sucesso e nenhuma colisão ocorreu durante este processo.

Um vídeo contendo o experimento mostrado na figura 5.10 e também uma ou-tra simulação no MATLAB destacando os aspectos qualitativos da proposta pode serencontrado em http://youtu.be/uAkKKgeyN8k.

5.2 Resultados Experimentais com Robôs do tipo Integrador Duplo 44

Figura 5.10: Sequência de quadros do experimento com robôs e-puck usando o algoritmodo tipo integrador duplo.

Iterações0 1000 2000 3000 4000

Tam

anho

das

Abs

traç

ões

0

0.02

0.04

0.06

0.08

0.1

0.12

0.14(a)

Tamanho desejado

x-0.4 -0.2 0 0.2 0.4

y

-0.5

0

0.5(b)

Iterações0 1000 2000 3000

Dis

tânc

ia m

ínim

a en

tre

robô

s

0

0.05

0.1

0.15

0.2

Evitamento de colisões ligado

Robôs em colisão

(c)

x-0.4 -0.2 0 0.2 0.4 0.6

y

-0.4

-0.2

0

0.2

0.4

0.6(d)

Figura 5.11: Gráficos referentes ao experimento mostrado na figura 5.10 (a) Evoluçãodo tamanho das abstrações. (b) Evolução dos centros das abstrações. (c) Distânciamínima entre robôs ao longo do tempo. (d) Evolução da posição dos robôs.

Capítulo 6

Discussões Finais e Conclusões

“The saddest aspect of life right now is that science gathers know-ledge faster than society gathers wisdom.”

Isaac Asimov

Neste trabalho foram propostos dois controladores que segregam grupos de robôsheterogêneos usando abstrações. Um dos controladores foi desenvolvido para robôsdo tipo integrados simples e o outro controlador foi desenvolvido para robôs do tipointegrador duplo. A prova de convergência para segregação foi mostrada para ambosos controladores. Os dois controladores se baseiam em uma mesma proposta, queconsiste no uso de abstrações para representar cada grupo de robôs e em uma funçãode potencial artificial para separar os grupos. Foram propostas estratégias para evitarcolisões dentro dos controladores para segregação propostos com uso do espaço nulo.

O principal objetivo deste trabalho foi desenvolver um controlador para segregaçãode múltiplos grupos de robôs em que fosse possível provar a convergência do mesmo,visto que nenhum dos controladores com este propósito encontrados na literatura (Großet al. [2009], Kumar et al. [2010] e Santos [2014]) mostra a prova de convergência paramúltiplos grupos.

Os experimentos mostrados no capítulo 5 validam a estratégia proposta para solu-ção do problema de segregação em enxames de robôs. Tanto nas simulações quantonos experimentos com robôs reais, pode-se perceber por uma análise visual que a se-gregação foi atingida com sucesso. No trabalho de Santos [2014] é proposto um métodoobjetivo para analisar se a segregação realmente foi obtida. O método consiste em tra-çar o fecho convexo de cada grupo usando todos os robôs do grupo em questão. Assim,caso não haja interseção entre estes grupos a segregação está concluída. Em todas assimulações e experimentos deste trabalho é possível perceber que não há interseçãoentre os fechos convexos formado pelos robôs dos grupos, o que significa que houvesegregação de acordo com a definição de Santos [2014].

A estratégia proposta também apresenta uma vantagem em relação aos controla-dores propostos em Kumar et al. [2010] e Santos [2014]: em muitas situações os robôsnão precisam de informações globais todo o tempo para convergir para segregação.Na estratégia proposta cada robô precisa das seguintes informações: Sua posição, a

CAPÍTULO 6. DISCUSSÕES FINAIS E CONCLUSÕES 46

posição de todos os robôs de sua abstração, o número de robôs da sua abstração e aposição do centro de cada abstração vizinha. A informação da posição do centro dasabstrações vizinhas pode ser obtida sabendo a posição de todos os robôs pertencentesà estas abstrações. Além de todas estas informações, os robôs em iminência de colisãoprecisam também da posição e da velocidade dos outros robôs envolvidos na iminentecolisão. No algoritmo para robôs do tipo integrador duplo, além de todas as informa-ções supracitadas, os robôs também precisam da informação sobre a velocidade dasabstrações vizinhas e os robôs em iminência de colisão também precisam da aceleraçãode todos os outros robôs envolvidos nesta iminente colisão. Isto significa que o únicomomento em que um robô precisa de informações referentes à outros robôs que nãosejam de seu grupo, é quando este robô está em iminência de colisão com um outrorobô de outro grupo. Nos outros momentos as informações necessárias são apenas dasabstrações dos grupos vizinhos e não diretamente dos robôs pertencentes a estas abstra-ções. Não é necessária nenhuma informação de robôs cujos centros de suas abstraçõesestão distantes da abstração do robô em questão, fora de sua vizinhança. No caso de seaplicar esta proposta de forma distribuída, cada robô deve guardar internamente todasas informações necessárias, não há um agente que controla cada abstração.

Vale notar que todas as simulações e experimentos mostrados no capítulo 5 foramfeitos com robôs distribuídos de acordo com uma distribuição aleatória Gaussiana, oque faz com que provavelmente os centros de todas as abstrações em um primeiromomento fiquem bem próximos. Neste caso são necessárias muitas informações paraatingir segregação se compararmos com alguma outra distribuição inicial em que jáexista algum tipo de segregação no primeiro momento.

O controlador é robusto a adição/subtração de novos robôs se as condições sobretamanho desejado das abstrações forem sempre respeitadas.

Uma limitação desta proposta referente à formação das abstrações é que cada abs-trações precisa ter dois ou mais robôs para ser criada. Caso uma abstração tenhaapenas um robô, este é um caso degenerado conforme citado em Belta and Kumar[2003], isto significa infringir a suposição 2 usada nas provas de convergência para oalgoritmo para robôs do tipo integrador simples e duplo mostrada nas seções 4.1.2 e4.2.2 respectivamente.

A estratégia de evitar colisões funciona fazendo com que todos os robôs de ummesmo grupo se movimentem de forma a manter a abstração dos robôs envolvidosna colisão. Para que a estratégia funcione, um problema de minimização precisa serresolvido. Existem situações em que não há solução viável para este problema deminimização. Nestes casos, não há garantias que não ocorrerá colisões e ainda torna-seinválida a prova de convergência para segregação, porque os estados das abstraçõespodem não ser mantidos.

Apesar dos dois algoritmos serem baseados na mesma ideia, cada um foi desen-volvido tendo em mente aplicações diferentes. Normalmente é mais fácil projetarcontroladores para modelos atuados em velocidade, mas estes modelos nem sempre

CAPÍTULO 6. DISCUSSÕES FINAIS E CONCLUSÕES 47

(a) (b)

Figura 6.1: (a) Algoritmo para robôs do tipo integrador simples. (b) Algoritmo pararobôs do tipo integrador duplo.

representam bem a realidade. Rôbos reais possuem dinâmica de segunda ordem, atu-ados em torque. Tendo isto em mente, a figura 6.1 mostra uma comparação entre osdois algoritmos aplicados em 6 robôs divididos igualmente em 2 grupos. O objetivodesta comparação não é decidir se um algoritmo é melhor que o outro, porque cadaum é melhor se aplicado nas circunstâncias para que fora projetado. Para robôs emque o modelo de primeira ordem representa bem a sua dinâmica, como normalmenteé o caso de pequenos robôs móveis, é melhor que se aplique o algoritmo de primeiraordem por serem necessárias menos informações dos outros robôs. Existem robôs emque a dinâmica deve ser representada pelo modelo de segunda ordem (imaginemos aestratégia desenvolvida sendo aplicada em uma frota de carros autônomos), neste casodeve-se aplicar o algoritmo do tipo integrador duplo para que seja possível atingir asegregação.

Na figura 6.1 são mostradas as trajetórias dos robôs, na figura 6.1(a) é aplicado oalgoritmo para robôs do tipo integrador simples e na 6.1(b) é aplicado o algoritmo pararobôs do tipo integrador duplo. Os círculos maiores mostram a posição final dos robôse seu tamanho e as linhas pontilhadas mostram as trajetórias do instante inicial até asegregação ser atingida. Nesta comparação tentou-se ajustar os parâmetros para que oscontroladores ficassem o mais parecidos possível. Pode-se perceber que as trajetóriasdos robôs de primeira ordem são mais “suaves”. Isto se deve ao fato de que o algoritmode evitamento de colisões entre robôs atuados em aceleração muitas vezes deve acelerarbastante os robôs para que as colisões sejam evitadas e a abstração mantida. Muitasvezes isto faz com que os robôs fiquem “em órbita” dentro de suas abstrações, o quefaz com que mais situações de iminência de colisão apareçam. Uma das sugestões detrabalho futuro é fazer com que os robôs desacelerem, enquanto mantêm a abstração,depois de ter acelerado para evitar a colisão.

6.1 Proposta para Trabalhos Futuros 48

6.1 Proposta para Trabalhos Futuros

Para melhorar os algoritmos aqui propostos, sugerem-se alguns pontos que podemser investigados para dar continuidade ao trabalho:

Desacelerar robôs atuados em aceleração: Para evitar que os robôs “orbitem” em altasvelocidades atingidas após terem evitado uma colisão, sugere-se desenvolver umterceiro controlador, em que o primeiro é o controlador para segregação e osegundo é o controlador para tratamento de colisões. Este terceiro controladorseria ainda no espaço nulo do primeiro controlador fazendo uso da estruturapara coordenar múltiplas tarefas em sistemas altamente redundantes propostapor Siciliano and Slotine [1991]. Este terceiro controlador estaria no mesmo nívelhierárquico do controlador de evitamento de colisão, entrando em ação somentequando o controlador para tratamento de colisão estiver desligado. Este terceirocontrolador atuaria de modo que quando um ou mais robôs de uma mesmaabstração estiver em alta velocidade, com muita energia, este terceiro controladorseja capaz de dissipar as altas velocidades entre os robôs com velocidade maisbaixa ainda mantendo a abstração. Assim, sempre que o algoritmo de tratamentode colisões for desligado, este terceiro algoritmo entraria em ação para desacelerarpossíveis altas velocidades obtidas pelos robôs ao evitar colisões. Isto previniriamais situações de colisões iminentes além de diminuir o gasto energético dosistema.

Desenvolver uma função para resolver os problemas de minimização: Durante todoeste trabalho, foi utilizada a função fmincon do MATLAB para resolver todos osproblemas de minimização a serem resolvidos para se evitar colisões. Porém, porser uma função muito geral, algumas vezes não era encontrada a solução parao problema a ser resolvido em tempo hábil, o que faz com que haja uma colisãoou então a abstração não mantenha seu estado. Em algumas destas situações,era possível observar que claramente existia uma solução viável. Outras funçõesjá implementadas no MATLAB, como a função que utiliza algoritmos genéticos,também foram testadas, encontrando resultados piores do que a função fmin-con. É possível que este problema seja resolvido se for desenvolvida uma funçãoespecífica para este fim.

Tornar a estratégia totalmente local: Enxames de robôs tem como principal vantagema inerente robustez a falhas individuais. Neste trabalho, cada robô necessita dainformação de todos os robôs de sua abstração, além das informações de todos osrobôs de abstrações vizinhas. Para que os algoritmos aqui presentes possam usaresta robustez plenamente, sugere-se que se utilizem técnicas para que cada robôfaça uso somente de informações locais. Para isso, podem ser usadas técnicaspara a estimação do estado da abstração à qual estes robôs pertencem.

6.2 Conclusão 49

Uma desvantagem encontrada simulando o algoritmo para robôs do tipo integradorduplo foi a necessidade de muito espaço entre os robôs para que todas as colisõesfossem evitadas com sucesso. Desenvolvendo uma função de minimização própria edesacelerando os robôs após as colisões terem sido evitadas pode fazer com que nãohaja mais esta necessidade de muito espaço entre os robôs.

6.2 Conclusão

O objetivo principal deste trabalho foi resolver o problema de segregação em enxa-mes de robôs provando a convergência para tal segregação. Foram propostos e testadosalgoritmos para dois modelos de robôs em que este objetivo foi alcançado com sucesso.Estes testes foram conduzidos tanto em ambiente virtual através de simulações comum variado número de robôs quanto em ambiente real com robôs e-puck.

Outras contribuições foram obtidas como a emergência de uma propriedade “local”nos algoritmos. Do conhecimento deste autor, este trabalho é o primeiro a resolver esteproblema que pode não precisar de informações globais o tempo todo e apresenta aprova de convergência para segregação.

Ainda, outra contribuição interessante são as estratégias para evitar colisões man-tendo o estado das abstrações, não importando o número de robôs envolvidos nascolisões. Estas estratégias para evitar colisões podem até ser utilizadas em outroscontextos de enxames de robôs com o uso de abstrações ou não.

Referências Bibliográficas

Balch, T. and Arkin, R. (1998). Behavior-based formation control for multirobot teams.IEEE Transactions on Robotics and Automation, 14(6): 926-939.

Belta, C. and Kumar, V. (2003). Towards abstraction and control for large groups ofrobots. Control Problems in Robotics, STAR 4: 169-182.

Belta, C. and Kumar, V. (2004). Abstraction and control for groups of robots. IEEETransactions on Robotic, 20(5): 865-875.

Bezzo, N., Griffin, B., Cruz, P., Donahue, J., Fierro, R., and Wood, J. (2014). A coopera-tive heterogeneous mobile wireless mechatronic system. IEEE/ASME Transactions onMechatronics, 19(1): 20-31.

Bollobás, B. (1998). Modern graph theory. Springer Science & Business Media, vol. 184.

Bosque, M. M. (2009). Implementação do controle de enxames de robôs utilizando ahidrodinâmica de partículas suavizadas. Trabalho de Conclusão de Curso (Graduaçãoem Engenharia de Controle e Automação), Universidade Federal de Minas Gerais.

Chaimowicz, L. and Kumar, V. (2004). Aerial shepherds: Coordination among uavsand swarms of robots. Distributed Autonomous Robotic Systems 6, pp. 242-252.

Chaimowicz, L., Michael, N., and Kumar, V. (2005). Controlling swarms of robots usinginterpolated implicit functions. Proceedings of the 2005 IEEE International Conferenceon Robotics and Automation (ICRA), pp. 2487-2492.

Chen, J., Gauci, M., Price, M. J., and Groß, R. (2012). Segregation in swarms of e-puckrobots based on the brazil nut effect. Proceedings of the 11th International Conference onAutonomous Agents and Multiagent Systems. vol. 1: 163-170.

Choset, H., Lynch, K., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L., and Thrun,S. (2005). Principles of Robot Motion-Theory, Algorithms, and Implementation.

Cianci, C., Raemy, X., Pugh, J., and Martinoli, A. (2007). Communication in a swarmof miniature robots: The e-puck as an educational tool for swarm robotics. In SwarmRobotics, pages 103–115. Springer.

REFERÊNCIAS BIBLIOGRÁFICAS 51

Craighead, J., Murphy, R., Burke, J., and Goldiez, B. (2007). A survey of commercial& open source unmanned vehicle simulators. In Robotics and Automation, 2007 IEEEInternational Conference on, pages 852–857. IEEE.

Desai, J. P., Ostrowski, J., and Kumar, V. (1998). Controlling formations of multiplemobile robots. In Robotics and Automation, 1998. Proceedings. 1998 IEEE InternationalConference on, volume 4, pages 2864–2869.

Dorigo, M. (2013). Swarmanoid: A novel concept for the study of heterogeneous roboticswarms. IEEE Robotics & Automation Magazine, 20(4): 60-71.

Dorigo, M. and Sahin, E. (2004). Swarm robotics - special issue editorial. AutonomousRobots, 17(2): 111-113.

Garcia, R. and Chaimowicz, L. (2009). Uma infra-estrutura para experimentação comenxames de robôs. Submetido para o Simpósio Brasileiro de Automação Inteligente (SBAI).

Groß, R., Magnenat, S., and Mondada, F. (2009). Segregation in swarms of mobilerobots based on the brazil nut effect. IEEE/RSJ International Conference on IntelligentRobots and Systems. pp. 4349-4356.

Hsieh, A., Kumar, V., and Chaimowicz, L. (2008). Decentralized controllers for shapegeneration with robotic swarms. Robotica, Cambridge Univ Press, 26(05): 691-701.

Kantaros, Y., Thanou, M., and Tzes, A. (2015). Distributed coverage control for concaveareas by a heterogeneous robot-swarm with visibility sensing constraints. Automatica,Elsevier, vol. 53, pp. 195-207.

Khalil, H. and Grizzle, J. (1996). Nonlinear systems, volume 3. Prentice hall - New Jersey.

Klingner, J., Kanakia, A., Farrow, N., Reishus, D., and Correll, N. (2014). A stick-slipomnidirectional powertrain for low-cost swarm robotics: Mechanism, calibration,and control. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS),pp. 846-851.

Kramer, J. and Scheutz, M. (2007). Development environments for autonomous mobilerobots: A survey. Autonomous Robots, 22(2):101–132.

Kumar, M., Garg, D., and Kumar, V. (2010). Segregation of heterogeneous units in aswarm of robotic agents. IEEE Transactions on Automatic Control, 55(3): 743-748.

LaValle, S. M. (2006). Planning algorithms. Cambridge university press.

MathWorks (2014). version 8.3.0.532 (R2014a). The MathWorks Inc., Natick, Massachu-setts.

REFERÊNCIAS BIBLIOGRÁFICAS 52

Michael, N., Fink, J., and Kumar, V. (2007). Controlling a team of ground robots via anaerial robot. Proceedings of the IEEE/RSJ International Conference on Intelligent Robotsand Systems (IROS), pp. 965-970.

Mondada, F., Bonani, M., Raemy, X., Pugh, J., Cianci, C., Klaptocz, A., Magnenat, S.,Zufferey, J.-C., Floreano, D., and Martinoli, A. (2009). The e-puck, a robot designedfor education in engineering. Proceedings of the 9th conference on autonomous robotsystems and competitions, vol. 1: pp. 59-65.

Nagi, J., Giusti, A., Gambardella, L. M., Di Caro, G., et al. (2014). Human-swarm inte-raction using spatial gestures. Proceedings of the 2014 IEEE/RSJ International Conferenceon Intelligent Robots and Systems (IROS), pp. 3834-3841.

O’Hara, I., Paulos, J., Davey, J., Eckenstein, N., Doshi, N., Tosun, T., Greco, J., Seo, J.,Turpin, M., Kumar, V., et al. (2014). Self-assembly of a swarm of autonomous boatsinto floating structures. IEEE International Conference on Robotics and Automation(ICRA), pp. 1234-1240.

Olfati-Saber, R. (2006). Flocking for multi-agent dynamic systems: Algorithms andtheory. IEEE Transactions on Automatic Control, 51(3): 401-420.

Perkinson, J. and Shafai, B. (2005). A decentralized control algorithm for scalable roboticswarms based on mesh-free particle hydrodynamics. Proc. IASTED International. Conf.on Robotics and Appl, pp. 1-6.

Pimenta, L., Kumar, V., Mesquita, R., and Pereira, G. (2008a). Sensing and coverage fora network of heterogeneous robots. Proceedings of the 47th IEEE Conference on Decisionand Control, pp. 3947-3952.

Pimenta, L., Michael, N., Mesquita, R., Pereira, G., and Kumar, V. (2008b). Control ofswarms based on hydrodynamic models. IEEE International Conference on Roboticsand Automation (ICRA), pp. 1948-1953.

Pimenta, L., Pereira, G., Gonçalves, M., Michael, N., Turpin, M., and Kumar, V. (2013a).Decentralized controllers for perimeter surveillance with teams of aerial robots. Ad-vanced Robotics, 27(9): 697-709.

Pimenta, L., Pereira, G., Michael, N., Mesquita, R., Bosque, M., Chaimowicz, L., andKumar, V. (2013b). Swarm coordination based on smoothed particle hydrodynamicstechnique. IEEE Transactions on Robotics, 29(2):383-399.

Pinciroli, C., Trianni, V., O’Grady, R., Pini, G., Brutschy, A., Brambilla, M., Mathews,N., Ferrante, E., Di Caro, G., Ducatelle, F., et al. (2012). Argos: a modular, parallel,multi-engine simulator for multi-robot systems. Swarm intelligence, 6(4):271–295.

REFERÊNCIAS BIBLIOGRÁFICAS 53

Quigley, M., Conley, K., Gerkey, B., Faust, J., Foote, T., Leibs, J., Wheeler, R., and Ng,A. Y. (2009). Ros: an open-source robot operating system.

Remes, B., Hensen, D., Tienen, F. v., Wagter, C., Horst, E. v. d., and Croon, G. d. (2013).Paparazzi: how to make a swarm of parrot ar drones fly autonomously based on gps.International Micro Air Vehicle Conference and Flight Competition (IMAV2013), Toulouse,France.

Reynolds, C. W. (1987). Flocks, herds and schools: A distributed behavioral model.Computer Graphics, pages 25-34.

Rosato, A., Strandburg, K., Prinz, F., and Swendsen, R. (1987). Why the brazil nutsare on top: Size segregation of particulate matter by shaking. Physical Review Letters,APS, (58)10.

Rubenstein, M., Cornejo, A., and Nagpal, R. (2014). Programmable self-assembly in athousand-robot swarm. Science, American Association for the Advancement of Science,345(6198): 795-799.

Santos, V. and Chaimowicz, L. (2011). Uso de hierarquias no controle de enxamesrobóticos. Anais do X Simp. Brasileiro de Automação Inteligente, pp. 557-562.

Santos, V. and Chairmowicz, L. (2011). Hierarquical congestion control for roboticswarms. Proceedings of IEEE International Conference on Intelligent Robots and Systems(IROS), pages 4372-4377.

Santos, V., Pimenta, L., and Chaimowicz, L. (2014). Segregation of multiple heteroge-neous units in a robotic swarm. Proceedings of the 2014 IEEE International Conferenceon Robotics and Automation (ICRA), pp. 1112-1117.

Santos, V. G. (2014). Comportamentos segregativos em enxames robóticos. Dissertaçãode Mestrado PPGEE (Pós-Graduação em Engenharia Elétrica), Universidade Federal deMinas Gerais.

Siciliano, B. and Slotine, J.-J. E. (1991). A general framework for managing multiple tasksin highly redundant robotic systems. Advanced Robotics, 1991.’Robots in UnstructuredEnvironments’, 91 ICAR., Fifth International Conference on, pp. 1211-1216.

Slotine, J.-J. E. et al. (1991). Applied nonlinear control.

Szwaykowska, K., Romero, L. M.-y.-T., and Schwartz, I. B. (2014). Collective motionsof heterogeneous swarms. arXiv preprint arXiv:1409.1042.

Tanner, H., Jadbabaie, A., and Pappas, G. (2005). Flocking in teams of nonholonomicagents. Cooperative Control, Ed. Springer, pp. 229-239.

REFERÊNCIAS BIBLIOGRÁFICAS 54

Trianni, V. (2008). Evolutionary Swarm Robotics: Evolving Self-organising Behaviours inGroups of Autonomous Robots.

Valentini, G., Hamann, H., and Dorigo, M. (2015). Self-organized collective decision-making in a 100-robot swarm. Twenty-Ninth AAAI Conference on Artificial Intelligence.

Vaughan, R. (2008). Massively multi-robot simulation in stage. Swarm Intelligence,2(2-4):189–208.

Walker, P., Amraii, S., Chakraborty, N., Lewis, M., and Sycara, K. (2014). Human controlof robot swarms with dynamic leaders. Proceedings of the 2014 IEEE/RSJ InternationalConference on Intelligent Robots and Systems (IROS), pp. 1108-1113.

Zhang, G., Fricke, G., and Garg, D. (2014). Spill detection and perimeter surveillancevia distributed swarming agents. IEEE/ASME Transactions on Mechatronics, 18(1):121-129.