Análise dos Efeitos de Perturbações na Manutenção da Conectividade Global de um Sistema de Robôs

Disserta¸ca˜o apresentada a` Pr´o-Reitoria de P´os-Gradua¸c˜ao e Pesquisa do Instituto Tecnol´ogico de Aeron´autica, como parte dos requisitos para obten¸ca˜o do t´ıtulo de Mestre em Ciˆencias no Programa de P´os–Gradua¸c˜ao ´ em Engenharia Eletrˆonica e Computa¸ca˜o, Area de Inform´atica

Vin´ıcius Antonio Battagello

´ ˜ ANALISE DOS EFEITOS DE PERTURBAC ¸ OES ˜ DA CONECTIVIDADE NA MANUTENC ¸ AO ˆ GLOBAL DE UM SISTEMA DE ROBOS

Tese aprovada em vers˜ao final pelos abaixo assinados:

Prof. Dr. Carlos Henrique Costa Ribeiro Orientador

Prof. Dr. Luiz Carlos Sandoval G´oes Pr´o-Reitor de P´os-Gradua¸c˜ao e Pesquisa

Campo Montenegro S˜ao Jos´e dos Campos, SP - Brasil 2014

Dados Internacionais de Cataloga¸ c˜ ao-na-Publica¸ c˜ ao (CIP) Divis˜ ao de Informa¸ c˜ ao e Documenta¸ c˜ ao Battagello, Vin´ıcius Antonio An´ alise dos Efeitos de Perturba¸c˜ oes na Manuten¸c˜ao da Conectividade Global de um Sistema de Robˆ os / Vin´ıcius Antonio Battagello. S˜ ao Jos´e dos Campos, 2014. 102f. ´ Disserta¸c˜ ao de Mestrado – Curso de Engenharia Eletrˆonica e Computa¸c˜ao. Area de Inform´atica – Instituto Tecnol´ ogico de Aeron´ autica, 2014. Orientador: Prof. Dr. Carlos Henrique Costa Ribeiro. . 1. Robˆ os. 2. Dinˆ amica de Robˆ os. 3. Controle Adaptativo. 4. Sistemas de Computadores Embarcados. 5. Redes de Comunica¸c˜ao. 6. Rob´otica. 7. Transmiss˜ao de Dados. 8. Engenharia de Computa¸c˜ ao. 9. Engenharia Eletrˆ onica. I. Centro T´ecnico Aeroespacial. Instituto Tecnol´ogico de Aeron´ autica. Divis˜ ao de Ciˆencias da Computa¸c˜ao. II. T´ıtulo.

Referˆ encias BATTAGELLO, Vin´ıcius Antonio. An´ alise dos Efeitos de Perturba¸co ˜es na Manuten¸c˜ ao da Conectividade Global de um Sistema de Robˆ os. 2014. 102f. Disserta¸ca˜o de Mestrado – Instituto Tecnol´ogico de Aeron´autica, S˜ao Jos´e dos Campos. ˜ DE DIREITOS CESSAO NOME DO AUTOR:

Vin´ıcius Antonio Battagello

TITULO DO TRABALHO:

An´alise dos Efeitos de Perturba¸c˜oes na Manuten¸ca˜o da

Conectividade Global de um Sistema de Robˆos. TIPO DO TRABALHO/ANO:

Disserta¸ca˜o / 2014

´ concedida ao Instituto Tecnol´ogico de Aeron´autica permiss˜ao para reproduzir c´opias E desta tese e para emprestar ou vender c´opias somente para prop´ositos acadˆemicos e cient´ıficos. O autor reserva outros direitos de publica¸ca˜o e nenhuma parte desta tese pode ser reproduzida sem autoriza¸c˜ao.

Vin´ıcius Antonio Battagello Av. Aboli¸c˜ao, 87 - Torre 3, Apto. 125 CEP 12.245-500 – S˜ao Jos´e dos Campos–SP

iii

´ ˜ ANALISE DOS EFEITOS DE PERTURBAC ¸ OES ˜ DA CONECTIVIDADE NA MANUTENC ¸ AO ˆ GLOBAL DE UM SISTEMA DE ROBOS

Vin´ıcius Antonio Battagello

Composi¸ca˜o da Banca Examinadora:

Prof. Dr.

Roberto Kawakami Harrop Galv˜ao

Presidente

-

ITA

Prof. Dr.

Carlos Henrique Costa Ribeiro

Orientador

-

ITA

Prof. Dr.

Luiz Gustavo Bizarro Mirisola

Membro Interno

-

ITA

Prof. Dra. Silvia Silva da Costa Botelho

ITA

Membro Externo -

FURG

iv

A Deus, pela continuidade da Vida, a minha fam´ılia, por dar sentido a ela.

Agradecimentos A minha m˜ae Lucile, que muito mais que a fun¸c˜ao de genitora, cumpriu com o papel de educadora, psic´ologa, professora e terapeuta, abdicando de seu pr´oprio tempo e bem estar. Tamb´em a meu pai Vicente, que com otimismo e perseveran¸ca me ensinou a enfrentar as batalhas da vida, sempre com transparˆencia e honestidade. Aprendi e aprendo muito com o exemplo de ambos. A minha irm˜a L´ıgia, cuja amizade me ensinou a ser mais objetivo e a me superar, e a meu irm˜ao Andr´e, que me mostrou a importˆancia da leveza e da alegria. Sou muito grato pela presen¸ca de vocˆes a meu lado. A todos os colegas integrantes do AIR (Artificial Intelligence Research) Group no ITA, pelo conhecimento compartilhado e pelo aprendizado conjunto. Em especial, aos colegas de Mestrado Lu´ısa Amaral e Marcos M´aximo, que com bom humor e paciˆencia me ajudaram com ideias e conceitos no desenvolvimento e corre¸ca˜o deste trabalho. A meu orientador, Prof. Dr. Carlos Henrique Costa Ribeiro, pelas discuss˜oes e id´eias que guiaram e enriqueceram o desenvolvimento das an´alises aqui feitas. Al´em disso, ao Prof. Dr. Elder M. Hemerly e ao Prof. Dr. Roberto Kawakami H. Galv˜ao pelas d´ uvidas esclarecidas e pelos conceitos que consolidaram o desenvolvimento deste estudo. A todos os amigos e colegas pelo companheirismo durante o desenvolvimento desta tese. Especialmente, a Parth Bhatt, Alexandre Machado e Marcelo Tokarnia, que participaram de forma mais pr´oxima dos momentos iniciais de sua concep¸ca˜o, e tamb´em a Vin´ıcius Sartori, Bruno Bueno e D´ebora de Deus, pela presen¸ca amiga de sempre.

vi Finalmente, ao CNPQ, pelo apoio e suporte financeiro durante o desenvolvimento desta pesquisa.

“Prefira afrontar o mundo servindo a sua consciˆencia, a afrontar a sua consciˆencia servindo ao mundo.” — Humberto de Campos

“Se as coisas s˜ao inating´ıveis... ora! N˜ao ´e motivo para n˜ao querˆe-las... Que tristes os caminhos se n˜ao fora A presen¸ca m´agica das estrelas!” ´ rio Quintana — Ma

“Embora ningu´em possa voltar atr´as e fazer um novo come¸co, qualquer um pode come¸car agora e fazer um novo fim.” — Chico Xavier

Resumo Para desempenhar tarefas cooperativas de maneira descentralizada, exige-se que sistemas multi-robˆo comuniquem-se entre si. Portanto, manter a conectividade do grafo de comunica¸ca˜o ´e uma quest˜ao fundamental. Neste trabalho, n´os analisamos o efeito de diferentes tipos de perturba¸ca˜o na estrat´egia de controle para manuten¸ca˜o de conectividade descrita em (SABATTINI et al., 2012), avaliando o impacto de falha, atraso e ru´ıdo na comunica¸c˜ao entre os agentes. Os resultados mostram que a estrat´egia para garantir a conectividade nem sempre ´e resiliente aos efeitos negativos de tais perturba¸co˜es em configura¸co˜es realistas que consideram um limite de banda para o esfor¸co de controle. Contudo, caracter´ısticas inerciais inerentes da maioria dos sistemas aqu´aticos e terrestres abrem perspectiva de aplica¸ca˜o da estrat´egia de manuten¸ca˜o de conectividade a sistemas adaptativos que consideram, por exemplo, adapta¸ca˜o autˆonoma a restri¸c˜oes outras al´em da pr´opria conectividade, como eficiˆencia na comunica¸c˜ao ou capta¸c˜ao de energia.

Palavras–Chave: Sistemas Multi-agente, Manuten¸ca˜o de Conectividade, Controle de Robˆos Multi-cooperativo, Robˆos em Rede, Ve´ıculos e Robˆos M´oveis, Perturba¸ca˜o, Falha, Atraso, Ru´ıdo

Abstract To accomplish cooperative tasks, robotic systems are often required to communicate with each other. Therefore, maintaining the communication graph connectivity is a fundamental question. In this work, we analyse the effect of different types of disturbances in the connectivity maintenance control strategy described in (SABATTINI et al., 2012), evaluating the impact of failure, delay and noise in the communication between agents. The results show that the connectivity strategy is not resilient to the negative effects of failure and delay under realistic settings that consider a bandwidth limit for the control effort. However, the inherent inertial characteristics of most terrestrial and aquatic robots opens the perspective of applying the connectivity maintenance strategy to adaptive schemes that consider, for instance, autonomous adaptation to constraints other than the connectivity itself, e.g. communication efficiency and energy harvesting.

Keywords: Multi-agent Systems, Connectivity Maintenance, Multi Cooperative Robot Control, Networked Robots, Mobile Robots and Vehicles, Disturbance, Failure, Delay, Noise

Sum´ ario

1

˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Introdu¸ ca

18

1.1

Contextualiza¸c˜ ao Hist´ orica . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.2

Problema estudado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2

˜ o Teo ´ rica . . . . . . . . . . . . . . . . . . . . . . . Fundamenta¸ ca

25

2.1

Fundamentos em Teoria dos Grafos . . . . . . . . . . . . . . . . . . . . 25

2.2

Manuten¸c˜ ao de Conectividade e Procedimento de Estima¸c˜ ao para um Grupo de Agentes Integradores . . . . . . . . . . . . . . . . . . . . 26

2.2.1

Estrat´egia de Controle Centralizada

2.2.2

AMC Descentralizado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.3

. . . . . . . . . . . . . . . . . . . . . 26

Descri¸c˜ ao do Modelo de Perturba¸c˜ oes Estudado . . . . . . . . . . . . 40

2.3.1

Falha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.3.2

Atraso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.3.3

Ru´ıdo

3 3.1

4

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

´ rio de Simula¸ ˜o . . . . . . . . . . . . . . . . . . . . . . . . Cena ca

44

Estrat´ egia de Controle na Presen¸ca de Perturba¸co ˜es . . . . . . . . . . 45

Resultados Experimentais . . . . . . . . . . . . . . . . . . . . .

48

4.1

Experimentos Realizados . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.2

Modelo de Conectividade na Ausˆ encia de Perturba¸co ˜es . . . . . . . . 49

´ SUMARIO 4.2.1

xi

An´alise do Impacto do Esfor¸co de Controle na Manuten¸c˜ao da Conectividade entre os Agentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.3

Modelo de Conectividade na Presen¸ca de Perturba¸co ˜es . . . . . . . . 60

4.3.1

Falha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.3.2

Atraso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4.3.3

Ru´ıdo

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusa

91

ˆncias Bibliogra ´ ficas . . . . . . . . . . . . . . . . . . . . . . . Refere

94

ˆndice A – Modelagem do Problema . . . . . . . . . . . . . Ape

96

ˆndice B – Ana ´ lise dos Erros de Estima¸ ˜o . . . . . . . Ape ca

98

5

B.1

Erro na Estima¸c˜ ao de λ2 na presen¸ca de perturba¸c˜ oes . . . . . . . . . 98

B.2

˜ 2 na presen¸ca de perturba¸c˜ Erro na Estima¸c˜ ao de λ oes . . . . . . . . . 100

ˆndice C – V´ıdeos Demonstrativos . . . . . . . . . . . . . . 101 Ape C.1

Rela¸c˜ ao dos V´ıdeos das Simula¸co ˜es . . . . . . . . . . . . . . . . . . . . . 101

ˆndice D – Materiais e Me ´todos . . . . . . . . . . . . . . . . 102 Ape D.1

Ambiente de Simula¸c˜ ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

D.2

Dom´ınio do problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

´ rio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Glossa

Lista de Figuras FIGURA 1.1 – Cen´ ario do P roblema . . . . . . . . . . . . . . . . . . . . . . . . . . 20 FIGURA 1.2 – Colm´ eia de Abelhas

. . . . . . . . . . . . . . . . . . . . . . . . . . 21

FIGURA 2.1 – V (λ2 ) = coth(λ2 − ) . . . . . . . . . . . . . . . . . . . . . . . . . . 30 FIGURA 2.2 –

∂V (p) = csch2 (λ2 − ) . . . . . . . . . . . . . . . . . . . . . . . . . 31 ∂λ2

FIGURA 2.3 – Dinˆa mica do Sistema de Estima¸c˜a o . . . . . . . . . . . . . . . . . 34 FIGURA 2.4 – Identif ica¸c˜a o de agentes cr´ıticos. A a ´rea hachurada representa Nif eaa ´rea sombreada representa Nkc . . . . . . . . . . . . . . . . . . 37 FIGURA 2.5 – Diagrama de Blocos do M odelo Original . . . . . . . . . . . . . . 40 FIGURA 2.6 – Diagrama de blocos do modelo contendo as perturba¸c˜oes estudadas . 41 ¯ i para pf alha = δ = η = 0 e Nobst = 0 . . . . . . . . . . . . . . 50 FIGURA 4.1 – λ2 e λ 2 FIGURA 4.2 – Esf or¸c o de Controle T otal para pf alha = δ = η = 0 e Nobst = 0 . . 50 ¯ i para pf alha = δ = η = 0 e Nobst = 1 . . . . . . . . . . . . . . 51 FIGURA 4.3 – λ2 e λ 2 FIGURA 4.4 – Esf or¸c o de Controle T otal para pf alha = δ = η = 0 e Nobst = 1 . . 52 FIGURA 4.5 – λ2 e λi2 para pf alha = δ = η = 0 e Nobst = 150 . . . . . . . . . . . . . 54 FIGURA 4.6 – uc para pf alha = δ = η = 0 e Nobst = 150 . . . . . . . . . . . . . . . . 55 FIGURA 4.7 – Espectro de Amplitude ampliado de uc . . . . . . . . . . . . . . . . 56 FIGURA 4.8 – λ2 e λi2 com pf alha = δ = η = 0 e Nobst = 150 para agentes com um controlador f act´ıvel de implementa¸c˜a o no mundo real . . . . . . . 57 FIGURA 4.9 – ucf ilt ampliado para pf alha = δ = η = 0 e Nobst = 150 . . . . . . . . . 58

LISTA DE FIGURAS

xiii

FIGURA 4.10 –Espectro de Amplitude unilateral ampliado de ucf ilt para pf alha = δ = η = 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 ¯ 2 com pf alha = 0, 2 e δ = η = 0 para agentes com controladores FIGURA 4.11 –λ2 , λi2 e λ ideais e Nobst = 150 . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 FIGURA 4.12 –uc para pf alha = 0, 2 e δ = η = 0 em agentes com controladores ideais e Nobst = 150 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 FIGURA 4.13 –Espectro de Amplitude unilateral ampliado de uc para pf alha = 0, 2 e δ = η = 0 em agentes com controladores ideais e Nobst = 150 . . 64 ¯ 2 com pf alha = 0, 2 e δ = η = 0 para agentes com controladores FIGURA 4.14 –λ2 , λi2 e λ tipicamente reais e Nobst = 150 . . . . . . . . . . . . . . . . . . . . 65 FIGURA 4.15 –ucf ilt para pf alha = 0, 2 e δ = η = 0 em agentes com controladores tipicamente reais e Nobst = 150 . . . . . . . . . . . . . . . . . . . . 66 FIGURA 4.16 –Espectro de Amplitude unilateral ampliado de ucf ilt para pf alha = 0, 2 e δ = η = 0 em agentes com controladores tipicamente reais e Nobst = 150 . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 ¯ 2 com δ = 0, 005 s e pf alha = η = 0 para agentes com FIGURA 4.17 –λ2 , λi2 e λ controladores ideais e Nobst = 150 . . . . . . . . . . . . . . . . . . . 69 FIGURA 4.18 –uc para δ = 0, 005 s e pf alha = η = 0 em agentes com controladores ideais e Nobst = 150 . . . . . . . . . . . . . . . . . . . 71 FIGURA 4.19 –Espectro de Amplitude unilateral ampliado de uc para δ = 0, 005 s e pf alha = η = 0 em agentes com controladores ideais e Nobst = 150

72

¯ 2 com δ = 0, 010 s e pf alha = η = 0 para agentes com FIGURA 4.20 –λ2 , λi2 e λ controladores tipicamente realiz´a veis e Nobst = 150 . . . . . . . . . 74 FIGURA 4.21 –ucf ilt para δ = 0, 010 s e pf alha = η = 0 em agentes com controladores tipicamente reais e Nobst = 150 . . . . . . . . . . . . . . . . . . . . 78 FIGURA 4.22 –Espectro de Amplitude unilateral ampliado de ucf ilt para δ = 0, 01 s e pf alha = η = 0 em agentes com controladores tipicamente reais e Nobst = 150 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

LISTA DE FIGURAS

xiv

¯ 2 com η = 0, 5 e pf alha = δ = 0 para agentes com controladores FIGURA 4.23 –λ2 , λi2 e λ ideais e Nobst = 150 . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 FIGURA 4.24 –uc para η = 0, 5 e pf alha = δ = 0 em agentes com controladores ideais e Nobst = 150 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 FIGURA 4.25 –Espectro de Amplitude unilateral ampliado de uc para η = 0, 5 e pf alha = δ = 0 em agentes com controladores ideais e Nobst = 150 . 84 ¯ 2 com η = 0, 5 e pf alha = δ = 0 para agentes com controladores FIGURA 4.26 –λ2 , λi2 e λ tipicamente realiz´a veis e Nobst = 150 . . . . . . . . . . . . . . . . . 86 FIGURA 4.27 –ucf ilt para η = 0, 5 e pf alha = δ = 0 em agentes com controladores tipicamente reais e Nobst = 150 . . . . . . . . . . . . . . . . . . . . 87 FIGURA 4.28 –Espectro de Amplitude unilateral ampliado de ucf ilt para η = 0, 5 e pf alha = δ = 0 em agentes com controladores tipicamente reais e Nobst = 150 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

Lista de Tabelas TABELA 4.1 – Parˆametros Usados no Problema . . . . . . . . . . . . . . . . . . . . 48 TABELA 4.2 – Valores de Dom´ınio do Problema Estudados . . . . . . . . . . . . . 49

TABELA C.1 –Endere¸co eletrˆonico dos v´ıdeos dos principais casos estudados neste trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

TABELA D.1 –Valores de Dom´ınio do Problema N˜ao-Estudados . . . . . . . . . . . 102

Lista de Abreviaturas e Siglas CL

Conectividade Local

CG

Conectividade Global

AMC

Algoritmo de Manuten¸ca˜o de Conectividade

ADO

Algoritmo de Desvio de Obst´aculos

Lista de S´ımbolos L

matriz laplaciana do sistema

λn

n-´esimo menor autovalor de L

υn

autovetor correspondente a λn

λ2

medida da conectividade de um grafo G

λi2

estimativa de λ2 feita pelo agente i

ˆ2 λ

vetor contendo as estimativas de λ2 feitas pelos N agentes

υ˜2i

estimativa de uma componente de υ2 feita pelo agente i

υ˜2

˜2 autovetor correspondente a λ

˜2 λ

segundo menor autovalor de L

λ02

medida da conectividade de um grafo na presen¸ca de perturba¸co˜es

0

λi2

estimativa de λ02 feita pelo agente i

ˆ0 λ 2

vetor contendo as estimativas de λ02 feitas pelos N agentes

uc

esfor¸co de controle realizado pelos agentes

0

uc

esfor¸co de controle na presen¸ca de perturba¸co˜es

ucf ilt

esfor¸co de controle na presen¸ca de Filtro Passa-Baixas

1 Introdu¸ c˜ ao O desenvolvimento e aperfei¸coamento dos sistemas eletrˆonicos e computacionais nas u ´ltimas d´ecadas, atrav´es do uso de comunica¸c˜ao sem fio, tem aumentado em grande quantidade o uso de sistemas rob´oticos. Seja em atividades de explora¸ca˜o em ambientes in´ospitos e inacess´ıveis ao homem (como o fundo de oceanos ou em viagens a Marte) ou em atividades de busca, vigilˆancia e resgate, o uso de sistemas rob´oticos tem se ampliado e mostrado a sua grande importˆancia. Nesse sentido, o uso de sistemas multi-robˆo apresenta diversas vantagens em rela¸ca˜o ao uso dos sistemas de um u ´nico robˆo (SICILIANO; KHATIB, 2008):

• m´ ultiplos robˆos podem realizar tarefas que s˜ao complexas demais para um u ´nico robˆo; • robˆos diferentes podem juntos reunir habilidades diferentes e complementares; • dado que algumas tarefas s˜ao inerentemente distribu´ıdas, seja no tempo ou no espa¸co, um grupo de robˆos pode trabalhar simultaneamente resolvendo problemas paraleliz´aveis em menos tempo; • a redundˆancia oferecida por m´ ultiplos robˆos pode aumentar a robustez do sistema.

Definimos ent˜ao um sistema multi-robˆo como sendo um conjunto de agentes m´oveis,

˜ CAP´ITULO 1. INTRODUC ¸ AO

19

dotados de sensores e atuadores, que devem atuar sobre um determinado ambiente. Neste contexto, um dos objetivos essenciais para garantir a troca de informa¸co˜es no sistema ´e mantˆe-los sempre conectados, e para isso duas abordagens s˜ao poss´ıveis: garantir a conectividade local (CL) ou a conectividade global (CG) entre os robˆos. A primeira estrat´egia assume que todo par (i, j) de agentes mant´em entre si uma linha de comunica¸c˜ao ativa ao longo de toda a dinˆamica do sistema. Exemplos desta abordagem podem ser encontrados em (JI; EGERSTEDT, 2007), (HSIEH et al., 2008) e (SAVLA; NOTARSTEFANO; BULLO,

2009). Na pr´atica, uma unidade de controle central recolhe as

informa¸c˜oes de todo o grupo e faz a computa¸ca˜o, emitindo em seguida as ordens de controle para todos os agentes. Assim, embora garanta-se formalmente a conectividade no sistema em qualquer instante de tempo, exigem-se, em contrapartida, condi¸c˜oes muito restritivas para isso. A segunda estrat´egia, por sua vez, aceita que algumas liga¸c˜oes redundantes entre as unidades sejam removidas (e outras estabelecidas, caso necess´ario), sem que isso impe¸ca a troca de informa¸co˜es entre as mesmas. Nesse caso, cada unidade computa sua lei de controle apenas a partir de informa¸co˜es de sua vizinhan¸ca. Como exemplo, podemos citar a abordagem exposta em (YANG et al., 2010) e (SABATTINI; CHOPRA; SECCHI, 2011). Mais especificamente, neste trabalho estudaremos o impacto de alguns tipos de perturba¸c˜ao sobre um algoritmo distribu´ıdo que garante a manuten¸c˜ao da CG (referente, portanto, a` segunda estrat´egia acima exposta) em um sistema de agentes n˜ao-holonˆomicos linearizado com t´ecnicas baseadas em retroalimenta¸c˜ao (segundo (SABATTINI et al., 2012)) e com dinˆamica integradora simples (controlados por p), ˙ enquanto eles atravessam um territ´orio bidimensional desviando de um conjunto de obst´aculos. Como ilustrado na Figura 1.1, que representa um instante t´ıpico de execu¸c˜ao do algoritmo, um conjunto de 5 agen-

˜ CAP´ITULO 1. INTRODUC ¸ AO

20

tes (representados por asteriscos em vermelho), a partir de uma dada configura¸ca˜o inicial, assume uma forma¸c˜ao espec´ıfica e come¸ca a deslocar-se para a direita, desviando de obst´aculos pontuais em posi¸co˜es aleat´orias (representados pelos pontos em azul ) na Figura 1.1.

FIGURA 1.1 – Cen´ ario do P roblema

Dado que cada agente apresenta um raio de comunica¸c˜ao limitado (R = 2, no caso), devemos coordenar de forma descentralizada seu movimento, uma vez que este agente deve manter-se conectado a seus pares, sem um controle central, enquanto desvia dos obst´aculos a seu redor.

1.1

Contextualiza¸c˜ ao Hist´ orica

De fato, tomando como base exemplos da Natureza (como ´e feito com frequˆencia em Inteligˆencia Artificial), a maioria dos animais organiza-se e interage em comunidades,

˜ CAP´ITULO 1. INTRODUC ¸ AO

21

realizando tarefas de elevada complexidade com entidades razoavelmente simples, atrav´es da coopera¸c˜ao. Consideremos, por exemplo, um enxame de abelhas, como representado na Figura 1.2 1 .

FIGURA 1.2 – Colm´ eia de Abelhas

A rapidez com que o enxame constr´oi sua colm´eia, aliada a sua alta capacidade de adapta¸ca˜o ao ambiente e frente a amea¸cas (como incˆendios), mostra as grandes vantagens de um sistema cooperativo descentralizado. Outro aspecto em que os sistemas distribu´ıdos se destacam ´e a tolerˆancia a falhas. Se prosseguirmos com nossa analogia com o mundo animal, veremos que a morte de uma abelha n˜ao causa um preju´ızo consider´avel ao funcionamento de uma colm´eia, sendo ela, neste caso, imediatamente substitu´ıda por sua companheira. Seguindo o exemplo citado, coordenar a a¸ca˜o de unidades de a¸ca˜o independentes para um mesmo fim ´e de elevado interesse em Rob´otica, em face da crescente aplica¸c˜ao de sistemas rob´oticos m´oveis em ve´ıculos terrestres, aqu´aticos ou mesmo a´ereos. O principal objetivo de estrat´egias de controle distribu´ıdo ´e garantir a coopera¸ca˜o de cada um dos 1

Fonte: http://goo.gl/n3VLrE

˜ CAP´ITULO 1. INTRODUC ¸ AO

22

elementos do grupo sem a necessidade de conhecimento, por cada um deles, do estado global do sistema, mas apenas atrav´es da comunica¸ca˜o de uns para com os outros.

1.2

Problema estudado

Em (YANG et al., 2010) foi apresentado um m´etodo para a estima¸ca˜o e o controle da conectividade de um grupo de agentes de forma descentralizada. Neste trabalho, apresentase um procedimento de estima¸c˜ao distribu´ıdo que permite a cada agente monitorar a conectividade alg´ebrica de um grafo variante no tempo. Os resultados, que inicialmente s˜ao apresentados para sistemas com controle centralizado, s˜ao estendidos na sequˆencia da referˆencia em quest˜ao para sistemas com controle distribu´ıdo, adotando a conven¸c˜ao de nomenclatura de usar sobrescritos para indexar os agentes e as componentes de um vetor e usar subscritos para indicar os autovalores, autovetores e as suas estimativas. Por exemplo, dada uma matriz L, os seus n autovalores ser˜ao denotados λ1 , . . . , λn , e seus n autovetores, υ1 , . . . , υn . Dado um autovetor υi , seus componentes ser˜ao representados por υi = {υi1 , υi2 , . . . , υin }. Para garantir que eles continuem conectados, cada agente deve ser capaz de obter uma medida da conectividade alg´ebrica do grafo que representa o conjunto de agentes (dada por λ2 , como esclareceremos mais adiante), escolhendo assim uma dire¸c˜ao de movimento para maximiz´a-la. Para obter λ2 , a estrat´egia proposta ´e a de estimar o autovetor correspondente υ2 , e a partir da rela¸ca˜o entre eles (L.υ2 = λ2 .υ2 ), obter λ2 . Estudando o mesmo problema, (SABATTINI; CHOPRA; SECCHI, 2011) descreve uma estrat´egia de controle baseada na descida do gradiente para a estima¸ca˜o da medida de

˜ CAP´ITULO 1. INTRODUC ¸ AO

23

conectividade, garantindo a CG do sistema sem exigir que os agentes estejam localmente conectados durante toda a dinˆamica. Nesse caso, ´e desenvolvido um novo algoritmo inteiramente descentralizado e escal´avel, no qual cada agente atualiza apenas O(1) estados estimadores. Al´em disso, esta abordagem apresenta erro de estima¸ca˜o limitado e garante a manuten¸ca˜o de conectividade entre os agentes mesmo na presen¸ca de erros limitados de estima¸ca˜o. Provas anal´ıticas e simula¸co˜es tamb´em s˜ao apresentadas para validar os resultados apresentados. Outros trabalhos estenderam esta estrat´egia considerando a presen¸ca de atrasos de comunica¸ca˜o entre os robˆos. Em (SECCHI; SABATTINI; FANTUZZI, 2012), a garantia de conectividade para o sistema ´e obtida atrav´es de uma estrat´egia de passiva¸ca˜o em que introduz-se na lei de controle um termo amortecedor βi p˙i para dissipar a energia produzida pela adi¸c˜ao de atraso ao sistema. Esta estrat´egia ´e ampliada em (SECCHI; SABATTINI; FANTUZZI, 2013) para lidar com qualquer tipo de corrup¸ca˜o de dados no sistema atrav´es da defini¸c˜ao de uma fun¸c˜ao potencial de conectividade ν. A conectividade passa a ser estudada atrav´es de uma abordagem energ´etica e os agentes ligam-se de forma a preservar a energia do sistema. Em (BATTAGELLO; RIBEIRO, 2014), uma investiga¸c˜ao inicial a respeito dos impactos de alguns tipos de corrup¸ca˜o nos dados foi feita, e ao longo desta disserta¸ca˜o, estudaremos de forma mais abrangente o impacto e os desdobramentos de diferentes formas de perturba¸c˜ao no funcionamento da estrat´egia de manuten¸ca˜o da CG de um conjunto de robˆos m´oveis, avaliando sua influˆencia tanto em λ2 quanto no esfor¸co de controle uc feito pelos agentes. Este trabalho est´a organizado da seguinte forma: no Cap´ıtulo 2, a partir de uma abordagem centralizada, introduzimos a estrat´egia de controle distribu´ıda que permite a agentes integradores simples computar suas estimativas de λ2 e de seu gradiente (le-

˜ CAP´ITULO 1. INTRODUC ¸ AO

24

vando em conta os poss´ıveis erros de estima¸ca˜o) e descrevemos o modelo de perturba¸co˜es estudado. No Cap´ıtulo 3, apresentamos a estrat´egia de controle adotada frente a esse modelo de perturba¸c˜oes, bem como an´alises quanto ao erro de estima¸ca˜o. No Cap´ıtulo 4, investigamos a eficiˆencia da solu¸ca˜o proposta por (SABATTINI; CHOPRA; SECCHI, 2011) a diferentes tipos de perturba¸ca˜o, atrav´es da an´alise do comportamento de λ2 e de uc , e conclu´ımos as an´alises no Cap´ıtulo 5, avaliando o desempenho do referido algoritmo a diferentes tipos de perturba¸ca˜o existentes no mundo real.

2 Fundamenta¸ c˜ ao Te´ orica

2.1

Fundamentos em Teoria dos Grafos

Nesta se¸ca˜o faremos um resumo com as principais no¸co˜es de Teoria dos Grafos usadas como base para o desenvolvimento deste trabalho. Detalhes adicionais podem ser encontrados em (GODSIL; ROYLE, 2001). A comunica¸ca˜o entre um conjunto de N robˆos m´oveis frequentemente ´e modelada atrav´es de um grafo, comumente denominado grafo de comunica¸c˜ao G. Cada um dos robˆos ´e representado como um n´o, e a comunica¸ca˜o existente entre cada par deles ´e representada atrav´es de uma aresta. A vizinhan¸ca Ni define, portanto, o conjunto de todos os robˆos com os quais o n´o i se comunica. A representa¸ca˜o de um grafo pode ser feita atrav´es de grafos dirigidos ou n˜ao-dirigidos. • Grafos Dirigidos (ou Digrafos): os digrafos s˜ao aqueles em que as arestas que o comp˜oem apresentam uma dire¸ca˜o. Geralmente sua representa¸c˜ao ´e feita por meio de uma seta que indica o sentido de troca de informa¸c˜ao (→ ). Ligando um par de v´ertices u e v, ´e poss´ıvel existirem at´e duas arestas: u → v e v → u. • Grafos N˜ao-Dirigidos (ou Digrafos Sim´etricos): s˜ao aqueles em que a troca de informa¸c˜ao d´a-se em ambos os sentidos. Ent˜ao, ligando os v´ertices u e v, existe apenas

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

26

uma aresta: a aresta uv, que ´e an´aloga `a aresta vu. Neste trabalho, modelamos o problema atrav´es do uso de Grafos N˜ao Dirigidos. Mais informa¸c˜oes sobre o embasamento te´orico utilizado no desenvolvimento do mesmo podem ser encontradas no Apˆendice A.

2.2

Manuten¸c˜ ao de Conectividade e Procedimento de Estima¸c˜ ao para um Grupo de Agentes Integradores

Dados N agentes, a arquitetura de comunica¸ca˜o entre eles ser´a modelada atrav´es de um grafo de comunica¸c˜ao. Como exposto anteriormente, λ2 ´e a medida de conectividade de um grafo, e iremos descrever nesta se¸ca˜o um procedimento de estima¸ca˜o descentralizado que permite a cada agente a estima¸ca˜o de λ2 apenas com informa¸co˜es locais.

2.2.1

Estrat´ egia de Controle Centralizada

Em (YANG et al., 2010), a comunica¸ca˜o entre um grupo de agentes ´e modelada por um grafo de comunica¸ca˜o com peso nas arestas. A partir disso, para grafos conectados, temos que λ2 > 0 e que λ2 sempre aumenta ou a` medida que cres¸ca o n´ umero de arestas (com a reuni˜ao de mais agentes) ou que o peso delas aumente (`a medida que eles se aproximem). A estima¸ca˜o de λ2 ´e feita a partir da estima¸c˜ao do correspondente autovetor υ2 . Segundo o processo descrito em (TREFETHEN; BAU, 1997) ´e poss´ıvel obter a seguinte

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

27

lei de atualiza¸c˜ao:

  
2 
υ2 υ2 − k3 . Ave { υ˜2i } − 1 .˜ υ˜˙ 2 = −k1 .Ave {˜ υ2i } .1 − k2 .L.˜

(2.1)

onde k1 , k2 , k3 > 0 s˜ao os ganhos de controle e Ave(.) ´e a opera¸ca˜o de c´alculo de m´edia. υ˜2i ´e definido como a estimativa do i-´esimo agente de v2i , que ´e a i-´esima componente do  T autovetor υ2 , e υ˜2 = υ˜21 , · · · , υ˜2N . Outros detalhes podem ser encontrados em (YANG et al.,

2010).

Para implementar a Equa¸ca˜o (2.1) de forma a permitir a computa¸ca˜o descentralizada 

2 i em cada agente, ´e necess´ario calcular as m´edias Ave υ˜2 e Ave υ˜2i apenas com informa¸c˜ao local. Isso ´e feito atrav´es de dois estimadores de consenso m´edio PI, propostos em (FREEMAN; YANG; LYNCH, 2006):

X X
z˙ i = γ. αi − z i − Kp . (z i − z j ) + Ki . (wi − wj ) jNi i

w˙ = −Ki .

X

i

jNi

(2.2)

j

(z − z )

jNi

em que αi indica a posi¸c˜ao desejada para o agente i, z i e wi indicam a posi¸c˜ao e a orienta¸ca˜o do agentes i e [z i wi ]T  R2 s˜ao estimadores internos de estados. No caso, γ > 0 ´e o parˆametro estimador global e Kp e Ki s˜ao os ganhos de estima¸c˜ao. Detalhes adicionais podem ser encontrados em (FREEMAN; YANG; LYNCH, 2006). Nesse caso, as duas opera¸co˜es de m´edia da Equa¸ca˜o (2.1) foram implementadas com dois operadores de consenso PI:

• O primeiro, com entrada αi,1 = υ˜2i , calcula, de acordo com a nomenclatura adotada em (YANG et al., 2010), z1i como a estimativa do i-´esimo agente de Ave υ˜2i




˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

28


2 • O segundo, com entrada αi,2 = υ˜2i , calcula, de acordo com a nomenclatura ado
 2 tada em (YANG et al., 2010), z2i como a estimativa do i-´esimo agente de Ave υ˜2i

Assim, como exposto em (SABATTINI et al., 2012), cada agente pode computar, de forma descentralizada, a sua vers˜ao da Equa¸c˜ao (2.1), a saber:

υ˜˙ 2i = −k1 .z1i − k2 .

X


i
υ2 aij . υ˜2i − υ˜2j − k3 . z2i − 1 .˜

(2.3)

j Ni

De acordo com (YANG et al., 2010), cada agente i pode calcular a sua estimativa de λ2 ˜2 ∂λ ∂λ2 e , denotadas por λi2 e , da seguinte forma: ∂pi ∂pi
k3 k3 .(1 − z2i ) = .(1 − Ave (υ2i )2 k2 k2 X ∂aij ˜2
2 ∂L ∂λ = υ˜2T . .˜ υ2 = υ˜2i − υ˜2j ∂pi ∂pi ∂pi jN

λi2 =

(2.4)

i

Assumindo que cada agente consegue obter as suas estimativas de Ave((υ2i )) e Ave((υ2i )2 ), temos que a convergˆencia do sistema para o real valor de λ2 ficou comprovada em (YANG et al.,

2010). A fim de lidar com os erros de estima¸ca˜o, um estimador modificado foi

introduzido em (SABATTINI et al., 2012), de acordo com uma nova lei de atualiza¸ca˜o:

υ˜˙ 2i = −k1 .z1i − k2 .

X



i aij . υ˜2i − υ˜2j − k3 . z2i − 1 .˜ υ2 − k4 .|˜ υ2i |˜ υ2i

(2.5)

j Ni

para uma nova constante k4 > 0. A adi¸ca˜o deste termo, como indicado na referˆencia em quest˜ao, ´e importante para que o erro de estima¸c˜ao de λ2 seja limitado, atrav´es da deteriora¸ca˜o do sinal de acordo com a lei de atualiza¸c˜ao original dada na Equa¸c˜ao (2.3). Assim, pode-se garantir a manuten¸ca˜o da conectividade entre os agentes em quest˜ao.

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO 2.2.1.1

29

Manuten¸c˜ ao de Conectividade para Agentes Integradores Simples

Neste t´opico descreveremos um algoritmo de manuten¸c˜ao de conectividade (AMC) para grupos de agentes integradores simples inicialmente de forma centralizada (na qual cada agente tem acesso a` informa¸ca˜o total do sistema), removendo essa hip´otese na sequˆencia para explorar o procedimento de estima¸ca˜o descrito na se¸ca˜o anterior. Suponhamos, assim, que cada agente pode computar o valor real de λ2 . Assim, dado um conjunto de N agentes integradores simples, isto ´e, que podem ser descritos por

uci = p˙i

(2.6)

em que uci ´e a entrada de controle, pi  Rm ´e a posi¸c˜ao do i-´esimo agente, p = [pT1 , . . . , pTN ]T  RN.m ´e o vetor de estados do sistema multiagente e R ´e definido como o alcance m´aximo de comunica¸ca˜o para cada agente. Nesse contexto, um dado j-´esimo agente pertence `a vizinhan¸ca Ni de i se ||pi − pj || ≤ R. Seja L a matriz laplaciana do grafo. Sabemos que a conectividade ´e garantida se λ2 for estritamente maior que zero. Portanto, seja  > 0 o limite inferior desejado para λ2 . Assim, a estrat´egia de controle ser´a formulada para garantir que λ2 seja limitado inferiormente por . Para isso, foi definida uma fun¸ca˜o de energia Potencial de conectividade ν(·): Defini¸c˜ ao 2.2.1. Uma fun¸c˜ao de energia V (λ2 (p)−) : RN.m → R apresenta as seguintes propriedades:

´ continuamente diferenci´avel, ∀λ2 > ; 1. E ´ n˜ao-negativa; 2. E

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

30

´ n˜ao-crescente com respeito a λ2 , ∀λ2 > ; 3. E 4. Aproxima-se de um valor constante quando λ2 aumenta; 5. Cresce repentinamente `a medida que λ2 tende a  > 0. Ou seja:

lim V (λ2 (p)) = ∞

λ2 →

(2.7)

Em (SABATTINI et al., 2012) foi adotada a seguinte fun¸c˜ao de energia Potencial de Conectividade: V (λ2 (p)) = coth(λ2 − )

(2.8)

que ´e estritamente positiva e n˜ao crescente quanto a λ2 .

FIGURA 2.1 – V (λ2 ) = coth(λ2 − )

A lei de controle para o sistema assume a seguinte forma:

uci = −

∂V (p) ∂pi

(2.9)

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

31

e, a partir da Equa¸ca˜o (2.8), podemos obter:

∂V (p) = csch2 (λ2 − ) ∂λ2

(2.10)

que assume a forma dada pela Figura 2.2.

FIGURA 2.2 –

∂V (p) = csch2 (λ2 − ) ∂λ2

Assim, `a medida que λ2 diminui, aproximando-se de ,

∂V cresce rapidamente, ten∂λ2

dendo ao ∞. Seguindo a estrat´egia definida em (YANG et al., 2010), o peso das arestas aij para o grafo de comunica¸ca˜o foi assim definido:

aij =

  −(||pi −pj ||)2    e 2.σ2

caso ||pi − pj || ≤ R

   0,

caso contr´ ario

(2.11)

−R2

onde o parˆametro escalar σ ´e escolhido para satisfazer a condi¸ca˜o e 2.σ2 = ∆, em que ∆ ´e um limiar pr´e-definido. Isso assegura que o peso entre os agentes ´e n˜ao-nulo se a distˆancia

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

32

entre eles ´e igual a R. Usando a defini¸ca˜o dos pesos aij entre os agentes, temos que a lei de controle dada na Equa¸ca˜o (2.9) pode ser expressa por:

uci = −csch2 (λ2 − ).

X

aij .(v2i − v2j )2 .

jNi

pi − pj σ2

(2.12)

A partir das Equa¸c˜oes (2.9) e (2.6), temos:

V˙ (p) =

N X ∂V T i=1

∂pi

.p˙i = −p˙T .p˙ ≤ 0

(2.13)

ou seja, a varia¸ca˜o temporal da fun¸ca˜o de energia ´e negativa. Logo, V (p) n˜ao aumenta com o tempo.

2.2.2

AMC Descentralizado

Embora o valor real de λ2 n˜ao esteja dispon´ıvel de forma distribu´ıda, atrav´es dos procedimentos descritos na Se¸c˜ao (2.2.1) cada agente i pode computar ao longo da dinˆamica a sua estimativa do autovetor υ2 , chamada υ˜2i . Definimos υ˜2 = [˜ υ21 · · · υ˜2N ]T como sendo ˜2 uma matriz contendo todas as N estimativas dos autovetores feitas pelos agentes e λ como sendo o valor do segundo menor autovalor que a matriz laplaciana L assumiria caso υ˜2 fosse o autovetor correspondente. ˜ 2 de acordo com: Analogamente ao feito com λi2 na Equa¸c˜ao (2.4), podemos computar λ

  ˜ 2 = k3 . 1 − Ave((˜ λ υ2i )2 ) k2

(2.14)

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO A estimativa de

33

˜2 ∂λ feita pelo i-´esimo agente, de acordo com os procedimentos descri∂pi

tos em (YANG et al., 2010), ´e dada pela Equa¸ca˜o (2.15), em que Ni representa a vizinhan¸ca do i-´esimo agente:

X ∂aij ˜2
2 ∂λ ∂L = υ˜2T . .˜ υ2 = . υ˜2i − υ˜2j . ∂pi ∂pi ∂pi jN

(2.15)

i

e da defini¸ca˜o do peso das arestas dada pela Equa¸ca˜o 2.11, temos que:

˜2 X
2 pi − pj ∂λ = −aij υ˜2i − υ˜2j . ∂pi σ2 jN

(2.16)

i

˜ 2 n˜ao pode ser computado por cada agente apenas com informa¸c˜oes O valor real de λ
locais, uma vez que o valor real de Ave {(˜ υ2i )} n˜ao est´a dispon´ıvel. No entanto, uma estimativa desta m´edia, dada por z2i , pode ser calculada localmente por cada agente de acordo com a Equa¸ca˜o 2.2. Como mostrado em (SABATTINI; CHOPRA; SECCHI, 2011), λi2 ´e uma boa estimativa ˜ 2 . Ou seja, ∃Ξ, Ξ0 > 0 tal que: tanto de λ2 quanto de λ

|λ2 − λi2 | ≤ Ξ, ∀i = 1, . . . , N (2.17) ˜2 − |λ

λi2 |

0

≤ Ξ , ∀i = 1, . . . , N

Da´ı, da condi¸c˜ao de existˆencia expressa pelas Equa¸c˜oes (2.17) temos:

˜ 2 | ≤ Ξ + Ξ0 |λ2 − λ

(2.18)

˜ 2 ´e uma boa aproxima¸ca˜o de λ2 . Assim, embora o valor real de λ ˜ 2 n˜ao esteja Ou seja, λ

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

34

dispon´ıvel para cada agente, suas derivadas parciais podem ser computadas apenas com informa¸c˜ao local, de acordo com a Equa¸ca˜o (2.2), o que permite a sua implementa¸ca˜o de forma descentralizada. Considerando a dinˆamica do sistema de estima¸ca˜o como um sistema linear Σ com retroalimenta¸c˜ao negativa ψ(), n˜ao-linear e sem mem´oria, como mostrado na Figura 2.3, ´e poss´ıvel provar que a norma do erro de estima¸ca˜o ν(t) de λ2 ´e limitada. r(t) ≡ 0 −

ν(t)

y(t) Σ

Ψ(y) Ψ() FIGURA 2.3 – Dinˆa mica do Sistema de Estima¸c˜a o

Ou seja, dadas as condi¸c˜oes apropridadas, garantimos que o erro de estima¸c˜ao ´e limitado e a intera¸c˜ao entre os agentes ´e sustent´avel com o tempo. Mais detalhes podem ser encontrados em (SABATTINI et al., 2012).

2.2.2.1

Manuten¸c˜ ao Descentralizada de Conectividade

Como a lei de controle introduzida na Equa¸c˜ao (2.9) exige dos agentes os valores de λ2 e

∂λ2 , que n˜ao est˜ao dispon´ıveis localmente, os agentes ir˜ao implementar a seguinte ∂pi

lei de controle, de forma an´aloga `a anterior:

˜2
∂λ uci = csch2 λi2 − ˜ . ∂pi

(2.19)

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

35

O parˆametro ˜ ´e definido como:

˜ =  + Ξ + Ξ0

(2.20)

no qual  ´e o limite inferior desejado para λ2 e Ξ e Ξ0 s˜ao definidos na Equa¸c˜ao (2.17). A fun¸c˜ao de energia para o sistema assume ent˜ao a seguinte forma:

˜ 2 − ˜) V˜ (p) = coth(λ

(2.21)

que ser´a implementada de forma descentralizada.

2.2.2.2

Estrat´ egia de Controle Aprimorada: a¸c˜ ao de controle seletivo

A atividade de controle descrita na Se¸ca˜o 2.2.2 utiliza-se de uma estrat´egia de controle seletivo para reduzir o esfor¸co global de controle na manuten¸ca˜o da conectividade. Ao mesmo tempo, ela reduz a interferˆencia desta com a tarefa global espec´ıfica de atua¸c˜ao do sistema. A lei de controle implementada nesta disserta¸c˜ao ´e an´aloga a` proposta por (SABATTINI et al.,

2012) e estende a que foi introduzida na Equa¸ca˜o (2.6), considerando a adi¸ca˜o de

um novo termo udi :

p˙i = uci + udi

(2.22)

onde uci ´e o termo de controle definido na Equa¸c˜ao (2.6) e udi ´e usado na obten¸ca˜o do comportamento desejado, podendo ser uma fun¸ca˜o limitada qualquer. A express˜ao do gradiente de controle introduzida em (2.12) ´e modificada da seguinte

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

36

maneira:

˜2
∂λ uci = γi .csch2 λi2 − ˜ . ∂pi

(2.23)

onde o coeficiente γi ´e usado para modular a a¸c˜ao de controle como explicaremos a seguir: Considere G como sendo um grafo modelando a arquitetura de comunica¸ca˜o. Segundo (GODSIL; ROYLE, 2001), um conjunto de arestas de corte ´e definindo como sendo um conjunto de arestas cuja remo¸c˜ao aumenta o n´ umero de componentes conectadas para G. Dizemos que, quando um conjunto de arestas de corte ´e constitu´ıdo por apenas um aresta, ent˜ao ela ´e denominada uma ponte. Ou seja, a remo¸ca˜o de uma ponte causa a desconex˜ao de um grafo. Para melhor estudar as rela¸c˜oes entre as pontes e a desconex˜ao de G, definamos Ni como a vizinhan¸ca do agente i. Assim, seja

Ni = Nic + Nif

(2.24)

Nic = {j  Ni tal que ||pi − pj || ≤ δ.R}

(2.25)

em que

´e o conjunto dos vizinhos pr´oximos ao i-´esimo agente e

Nif = {j  Ni tal que ||pi − pj || > δ.R}

(2.26)

´e o conjunto dos vizinhos distantes do i-´esimo agente, onde δ  (0, 1) ´e um limiar pr´e-

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

37

definido. Notar que, de acordo com a defini¸ca˜o, Nic e Nif s˜ao conjuntos complementares, pois (Nic ∩ Nif ) = ∅. A partir deste conceito, apresenta-se a defini¸c˜ao de Agente Isolado e de Agente Cr´ıtico: Defini¸c˜ ao 2.2.2. A partir da perspectiva de um agente i, considera-se o agente j como isolado se ele pertence a Nif e n˜ao existe nenhum k  Nic tal que j  Nkc . Defini¸c˜ ao 2.2.3. Dizemos que o i-´esimo agente ´e cr´ıtico se pelo menos um de seus vizinhos ´e isolado.

Por simetria, caso todos os agentes tenham o mesmo raio de comunica¸ca˜o R, se o agente i identificar-se como cr´ıtico por estar ligado a um agente isolado j, o agente j tamb´em considera-se como um agente cr´ıtico por identificar i como isolado. O conceito de agentes cr´ıticos e isolados pode ser mais bem elucidado atrav´es da Figura 2.4, na qual a ´area sombreada representa Nkc e a ´area hachurada Nif . a.

b.

k i

j

k

j

i

FIGURA 2.4 – Identif ica¸c˜a o de agentes cr´ıticos. A a ´rea hachurada representa Nif eaa ´rea sombreada representa Nkc

Na Figura 2.4a n˜ao h´a identifica¸ca˜o de agentes cr´ıticos, pois mesmo embora j  Nif , temos que k  Nic e k  Njc (ou seja, k ´e vizinho pr´oximo de ambos). Na figura 2.4b, o agente i considera o agente k como cr´ıtico (e vice-versa), uma vez que j ´e isolado. Deseja-se ent˜ao que a estrat´egia de manuten¸ca˜o de conectividade atue apenas nos casos

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

38

em que a desconex˜ao possa causar a perda de conectividade global entre os agentes. Essa ´e a fun¸ca˜o do coeficiente γi na Equa¸c˜ao (2.23), que fica assim definido:

γi =

     1 , caso o i−´ esimo agente seja cr´itico    ρ

(2.27)

, caso contr´ ario

em que ρ  (0, 1) ´e um n´ umero arbitrariamente pequeno.

2.2.2.3

Controle de Forma¸c˜ ao e de Encontro

Nesta se¸ca˜o modificaremos a a¸ca˜o de controle voltada para a manuten¸c˜ao de conectividade para tratar dos problemas de controle de forma¸c˜ao e de encontro entre os agentes, reescrevendo-a em forma vetorial. Sejam os pesos de liga¸ca˜o entre os agentes definidos da seguinte forma:

a ¯ij (λi2 ) = γi .csch2 (λi2 − ¯).


2 1 . υ˜2i − υ˜2j .aij 2 σ

(2.28)

A adi¸c˜ao de uma lei de controle altera a dinˆamica do sistema de intera¸ca˜o entre os ¯ a matriz de graus modificada que descreve o grafo de intera¸ca˜o e que agentes. Seja D N X
¯ ¯ ¯ pode ent˜ao ser definida como D = diag di , onde di = a ¯ij . Dessa forma, a matriz j=1

¯=D ¯ − A. ¯ laplaciana pode ser definida por L A nova vers˜ao da lei de controle assume, ent˜ao, a seguinte forma:

¯ + ud p˙ = −L.p

(2.29)

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

39

em que ud ´e o vetor contendo as leis de controle para cada um dos N agentes. Tendo em mente que a dinˆamica de comportamento do sistema ´e vetorial com dimens˜ao m, apresentaremos at´e o final deste item os resultados no formato unidimensional, bastando replic´a-lo para as outras (m − 1) dimens˜oes, caso desejado. Temos ent˜ao dois casos de controle a serem estudados: o de encontro entre agentes e o de controle de forma¸c˜ao entre os mesmos.

Encontro baseado no Consenso

Este caso trata do problema em que os agentes devem todos reunir-se em um ponto qualquer. Segundo (SABER; MURRAY, 2003), a lei de controle que garante a convergˆencia dos agentes para o mesmo ponto pode ser expressa por:

ud = −L ∗ p

(2.30)

em que ∗ ´e definida como a opera¸ca˜o de multiplica¸ca˜o.

Controle de Forma¸c˜ ao baseado no Consenso

Esta ´e a forma final do algoritmo implementado. Neste caso, ao inv´es de reunirem-se em um mesmo ponto, os agentes devem deslocar-se segundo uma forma¸c˜ao espec´ıfica. Analogamente ao caso de encontro entre agentes e dado que o grafo de comunica¸ca˜o ´e conectado, podemos introduzir a seguinte estrat´egia de controle, adicionando um termo de vi´es b a` lei de controle dada pela Equa¸c˜ao (2.30), de acordo com (FAX; MURRAY, 2004):

ud = −L ∗ p + bi (p)

(2.31)

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

40

em que:

bi (p) =

  X
   1+a ¯ij (λi2 ) . (¯ pi − p¯j )  

, se λi2 > k.˜

jNi

(2.32)

 X    (1 + a ¯ij (k.˜)) . (¯ pi − p¯j ) , caso contr´ ario   jNi

para algum k > 1. Assim, quando uma estimativa da conectividade alg´ebrica ´e suficientemente maior que ˜, ou seja, quando λi2 > k.˜, o termo de vi´es ´e computado com a matriz laplaciana ˜=L ¯ + L∗, em que L∗ ´e a matriz laplaciana prevista na Equa¸ca˜o (2.30). Quando o valor L da conectividade alg´ebrica cai e se aproxima de ˜, o termo de vi´es dado pelo segundo caso da Equa¸ca˜o (2.32) assegura que udi ´e limitado e, assim, garante a conectividade entre os agentes.

2.3

Descri¸c˜ ao do Modelo de Perturba¸ c˜ oes Estudado

Vimos, na Se¸ca˜o 2.2.2 que cada agente i calcula a sua estimativa de υ2 , dada por υ2i , e a partir dela obt´em a sua estimativa da varia¸ca˜o espacial do autovalor correspondente, dada ˜2 ∂λ na Equa¸ca˜o (2.16). O sistema de intera¸ca˜o entre os agentes pode ser representado por ∂pi simplificadamente pelo diagrama de blocos dado na Figura 2.5.

υ2i

f

˜2 ∂λ ∂pi

FIGURA 2.5 – Diagrama de Blocos do M odelo Original

Todo o processo descrito consiste basicamente em garantir aos agentes uma estimativa v´alida da conectividade global do sistema, de modo que eles possam tomar suas decis˜oes

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

41

(para maximiz´a-la) apenas com suas estimativas locais. No entanto, assume-se para isso que o sistema ´e bem comportado e que n˜ao h´a fontes externas de dist´ urbio interferindo na dinˆamica. Em geral, atrasos de comunica¸ca˜o dividem espa¸co com outras fontes de corrup¸ca˜o na informa¸c˜ao. Falhas de diferentes intensidades na recep¸c˜ao de dados digitais concorrem com ru´ıdos ao longo de sua transmiss˜ao, por exemplo. Espera-se, em todo caso, que o sistema seja capaz de manter-se conectado, mesmo na presen¸ca dessas fontes de corrup¸c˜ao. O modelo proposto neste trabalho adiciona falha, atraso e ru´ıdo como fontes de perturba¸c˜ao ao arranjo proposto em (SABATTINI et al., 2012) para estudar os seus efeitos no desempenho final do sistema e pode, ent˜ao, ser representado pelo diagrama de blocos da Figura 2.6, em que f representa o modelo do sistema de estima¸ca˜o na ausˆencia de perturba¸c˜oes.

υ2i

f alha

f

z −1

ru´ıdo

˜2 ∂λ ∂pi

FIGURA 2.6 – Diagrama de blocos do modelo contendo as perturba¸c˜oes estudadas

2.3.1

Falha

Um processo cr´ıtico para manter o sistema conectado ´e a estima¸ca˜o local de υ2 por cada um dos agentes. Assim como expresso em (BATTAGELLO; RIBEIRO, 2014), a falha nesta ˜ 2 , que podem implicar em estimativa implica automaticamente em valores incorretos de λ λ2 = 0, ou seja, na perda de conectividade para o sistema. Dados N agentes interagindo em pares em um ambiente desconhecido, conceitualmente o modelo de falha adotado ´e o de falha na recep¸c˜ao dos dados. Uma escolha razo´avel ´e

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

42

supor que, na ocorrˆencia de uma falha, o agente em quest˜ao estipula um valor padr˜ ao 0

constante υ2∗ (0 ou 1, por exemplo) para a estimativa υ2i pendente. Logo,

0

υ2i =

     υ2∗

, com p = pf alha

    υ2i

, com p = 1 − pf alha

(2.33)

Por padr˜ao de projeto, adotou-se υ2∗ = 1 (para o caso υ2∗ = 0, o resultado seria qualitativamente an´alogo).

2.3.2

Atraso

Um dos pontos-chave para garantir a manuten¸ca˜o de conectividade em um grupo de agentes ´e permitir a computa¸c˜ao descentralizada, atrav´es da troca de informa¸c˜oes entre vizinhos (SABATTINI; CHOPRA; SECCHI, 2011). Mas quando se tratam de sistemas reais, nem sempre podemos garantir que essa troca ´e feita instantaneamente. Seja por problemas na emiss˜ao dos dados ou por latˆencias relacionadas a seu processamento, em algumas situa¸co˜es os agentes devem reagir a dados antigos do ambiente. Dados N agentes comunicando-se na explora¸ca˜o de um ambiente desconhecido, adotouse o modelo de atraso na recep¸c˜ao dos dados. Como o agente computa com base em dados que refletem o passado do sistema, a presen¸ca de latˆencias na comunica¸ca˜o representa uma fonte uma fonte de corrup¸ca˜o nos dados. Dessa forma, a estimativa de υ2 feita pelo agente i em um dado instante de tempo t ´e

˜ TEORICA ´ CAP´ITULO 2. FUNDAMENTAC ¸ AO

43

dada por:

0

υ2i (t) = υ2i (t − δ), para δ > 0

(2.34)

em que δ ´e o atraso adicionado ao sistema.

2.3.3

Ru´ıdo

O ru´ıdo ´e uma das fontes prim´arias de perturba¸ca˜o no sinal (e consequentemente, nos dados) de qualquer componente eletrˆonico. Ao lidar com sistemas reais, qualquer processo de troca de informa¸ca˜o n˜ao-digital entre agentes envolve o uso de sensores, que adicionam intrinsecamente ru´ıdo ao sinal medido. O modelo adotado para simular os efeitos do ru´ıdo foi o de ru´ıdo branco gaussiano aditivo (AWGN), comumente usado em Teoria da Informa¸c˜ao para simular os efeitos de processos aleat´orios comuns na Natureza. 0

Seja υ2i a estima¸ca˜o de υ2 feita pelo agente i na presen¸ca de ru´ıdo independente e identicamente distribu´ıdo Zi . Assim, analogamente ao feito em (BATTAGELLO; RIBEIRO, 2014), temos que:

0

υ2i = υ2i + Zi

(2.35)

em que Zi ∼ N (0, η) (Zi ´e uma representa¸ca˜o do ru´ıdo gaussiano, que distribui-se de acordo com uma distribui¸ca˜o normal com µ = 0 e σ 2 = η).

3 Cen´ ario de Simula¸ c˜ ao A comunica¸c˜ao digital entre um par qualquer de agentes se d´a atrav´es do envio de pacotes, que s˜ao por¸c˜oes quantizadas de dados. Em geral, os pacotes trocados entre um grupo de agentes podem ser classificados quanto a sua fun¸c˜ao da seguinte forma:

• Pacotes de Controle: s˜ao mensagens referentes a` dinˆamica de funcionamento do sistema, necess´arias para a manuten¸c˜ao da conectividade entre os agentes; • Pacotes de Informa¸c˜ ao: est˜ao ligados `a tarefa principal do conjunto de agentes, como, por exemplo, vasculhar e proteger um determinado territ´orio.

Em geral, a perda dos Pacotes de Informa¸c˜ao durante uma dinˆamica de intera¸ca˜o entre agentes, apesar de indesejada, pode ser contornada seja pela ado¸c˜ao de algum protocolo de comunica¸ca˜o, como o TCP 3-way handshake (quando adota-se o reenvio dos dados em caso de perda, o que torna o sistema mais ineficiente), seja pela diminui¸ca˜o da confiabilidade dos Pacotes de Informa¸c˜ao caso a estimativa da conectividade seja negativa. A perda dos Pacotes de Controle, por sua vez, ´e altamente indesejada porque pode causar o n˜ao-cumprimento da tarefa principal dos agentes e at´e mesmo a perda de conectividade do grupo.

´ ˜ CAP´ITULO 3. CENARIO DE SIMULAC ¸ AO

45

Como vimos na Se¸ca˜o 2.2.2, cada agente i calcula λi2 para sua tomada de decis˜ao. No ˜ 2 ´e uma boa estimacaso ideal, em que pf alha = δ = η = 0, vimos na Equa¸c˜ao (2.18) que λ tiva de λ2 . A eficiˆencia dessa solu¸ca˜o para situa¸c˜oes sujeitas a algum tipo de perturba¸ca˜o (como ocorre comumente no mundo real), no entanto, ainda n˜ao foi investigada, e esse ´e o principal tema da Se¸ca˜o 3.1.

3.1

Estrat´ egia de Controle na Presen¸ ca de Perturba¸co ˜es

Consideremos um grupo de N agentes integradores simples, cuja dinˆamica ´e descrita pelas Equa¸co˜es (2.22), (2.23) e (2.31). A estimativa de υ2 calculada pelo agente i, na presen¸ca de perturba¸co˜es, pode ser expressa ent˜ao da seguinte forma:

0

υ˜2i =

     υ˜2∗ (t − δ) + Zi

, com p = pf alha

    υ˜2i (t − δ) + Zi

, com p = 1 − pf alha

(3.1)

Como υ2∗ (t − δ) = υ2∗ (pois independe de t por defini¸ca˜o), temos:

0

υ˜2i =

0

0

     υ˜2∗ + Zi

, com p = pf alha

    υ˜2i (t − δ) + Zi

, com p = 1 − pf alha

(3.2)

Seja υ˜20 = [˜ υ21 . . . υ˜2N ]T a matriz definida pelas estimativas dos autovetores de L e seja

´ ˜ CAP´ITULO 3. CENARIO DE SIMULAC ¸ AO

46

˜ 0 o valor do segundo menor autovalor desta, correspondente ao autovetor υ˜0 . Similarλ 2 2 ˜ 0 pode ser computado mente ao feito para o caso livre de perturba¸co˜es na Equa¸ca˜o (2.14), λ 2 de acordo com a Equa¸ca˜o (3.3):

h i i0 2 ˜ 0 = k3 .(1 − z 0 ) = k3 . 1 − Ave((˜ λ υ ) ) 2 2 2 k2 k2

(3.3)

Representemos o valor da medida de conectividade na presen¸ca de perturba¸co˜es por λ02 . A Proposi¸c˜ao B.1.1, contida no final deste trabalho, mostra que, na presen¸ca de perturba¸c˜oes limitadas, o erro de estima¸c˜ao de λ02 tamb´em ´e limitado. J´a a Proposi¸ca˜o 0

˜ 2 | (o valor absoluto da diferen¸ca entre cada B.2.1 nos d´a que o erro de estima¸ca˜o |λi2 − λ ˜ 2 ), tamb´em estimativa de conectividade e o segundo menor autovalor de L, dado por λ ˜ 0 para estimar localmente o valor real de λ2 , que ´e ´e limitado. Assim, podemos usar λ 2 inacess´ıvel aos agentes. Vale lembrar que, al´em de n˜ao ser poss´ıvel garantir que o erro de estima¸ca˜o de λ02 tenda a 0 (da mesma forma que no caso livre de perturba¸co˜es), ele ´e t˜ao maior quanto maior for o impacto de um ou mais tipos de perturba¸c˜ao na comunica¸ca˜o entre os agentes.

˜ 0 implementada pelos agentes, a partir de uma Descentralizadamente, a estimativa de λ 2 condi¸ca˜o inicial, ´e dada pela Equa¸c˜ao (3.4):

 0 2 p − p X ˜0 ∂λ i j j0 2 i = −aij υ˜2 − υ˜2 . 2 ∂pi σ jN

(3.4)

i

De forma semelhante ao visto na ausˆencia de perturba¸c˜oes na Se¸c˜ao 2.2.2, temos que ˜ 0 n˜ao est´a dispon´ıvel para nenhum agente. De fato, da Equa¸ca˜o (3.3), o valor o valor de λ 2   i0 2 real de Ave {(˜ υ2 ) } n˜ao pode ser calculado pelos agentes apenas com suas informa¸co˜es

´ ˜ CAP´ITULO 3. CENARIO DE SIMULAC ¸ AO

47 0

locais. No entanto, uma estimativa dessa m´edia, dada por z2i , pode ser obtida de forma descentralizada por eles. 0

Localmente, cada agente i tem posse de λi2 , e como mostrado em (SABATTINI et al., 2012), esta ´e uma boa referˆencia em condi¸co˜es ideais (uma vez que ´e poss´ıvel garantir limites Ξ e Ξ0 pequenos, de acordo com as Proposi¸co˜es B.1.1 e B.2.1). Para pequenas perturba¸c˜oes, ainda ´e poss´ıvel garantir erros pequenos de estima¸ca˜o. No entanto, na presen¸ca de perturba¸co˜es quaisquer, nem sempre podemos assegurar que os erros de estima¸ca˜o ficam confinados a valores razo´aveis (o que significa que n˜ao mais podemos garantir a manuten¸c˜ao da conectividade em todos os casos).

A seguir temos os resultados e as an´alises dos experimentos realizados neste trabalho.

4 Resultados Experimentais

4.1

Experimentos Realizados

Para avaliar o desempenho da estrat´egia de manuten¸c˜ao de conectividade na presen¸ca de diferentes tipos de perturba¸ca˜o, diversas simula¸co˜es com o ambiente Mathworks MaR tlab foram implementadas, com a posi¸c˜ao inicial dos agentes escolhida aleatoriamente.

No total, foram feitas simula¸c˜oes para as diferentes combina¸c˜oes de valores dos parˆametros da Tabela 4.1. Vari´ avel

Valor

Nsim

1, 2, 3, 5, 10, 30, 50 simula¸c˜o es

N

3, 4, . . . , 10 agentes

Nobst

0, 1, 2, 3, 5, 10, 30, 50, 100, 150 obst´a culos

tsim

2, 3, 5, 10 s

TABELA 4.1 – Parˆametros Usados no Problema

O modelo proposto foi testado para os parˆametros dispon´ıveis na Tabela 4.2, e os v´ıdeos dos principais casos relatados neste trabalho est˜ao dispon´ıveis online 1 (uma descri¸c˜ao mais detalhada dos mesmos pode ser encontrada no Apˆendice C). Mais informa¸c˜oes sobre o dom´ınio do problema s˜ao dadas no Apˆendice D. 1

no endere¸co http://goo.gl/DbT8Sj

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

49

Dado

Dom´ınio estudado

pf ail

0, 0.05, . . . , 0.70

δ

0 s, 10−5 s, 5.10−5 s, 10−4 s, 5.10−4 s, 0.001 s, 0.005 s, 0.01 s, 0.05 s, 0.1 s, 0.5 s

η

0, 0.1, 0.3, 0.5, 1.0, 5.0 TABELA 4.2 – Valores de Dom´ınio do Problema Estudados

4.2

Modelo de Conectividade na Ausˆ encia de Perturba¸c˜ oes

A estrat´egia proposta foi testada inicialmente em uma tarefa de controle de forma¸ca˜o ao longo de um terreno livre de obst´aculos (Nobst = 0) e na ausˆencia de qualquer tipo de perturba¸c˜ao (pf alha = δ = η = 0). Ou seja, para valida¸c˜ao do modelo os agentes deveriam atravessar um territ´orio sem obst´aculos, comunicando-se de acordo com o algoritmo descrito em (SABATTINI et al., 2012) e a partir de posi¸c˜oes iniciais aleat´orias. Na Figura 4.1 temos a evolu¸ca˜o m´edia das estimativas de conectividade feitas pelos agentes (em linhas tracejadas) em compara¸ca˜o ao valor real de λ2 , em azul, para um total de 50 simula¸co˜es sem qualquer tipo de perturba¸ca˜o e na ausˆencia de obst´aculos no ambiente (Nobst = 0). Como podemos notar, a soma do valor absoluto m´edio das estimativas de conectividade feitas pelos agentes ´e ligeiramente inferior ao de λ2 inicialmente, ultrapassando-o em t ≈ 0, 3 s, at´e convergirem ambos para λ2 ≈ 2, 1 em t ≈ 4, 75 s. Uma medida do esfor¸co de controle exigido pelo conjunto de agentes ao longo da dinˆamica pode ser definida como a ´area delimitada pelas curvas representando o esfor¸co de controle total para manuten¸ca˜o de conectividade. Ou seja:

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

50

¯ i para pf alha = δ = η = 0 e Nobst = 0 FIGURA 4.1 – λ2 e λ 2

c

u¯ =

N X

|uci |

(4.1)

i=1

Na Figura 4.2 plotamos o gr´afico de u¯c para a dinˆamica da Figura 4.1. Nesse caso, verificamos que a a¸ca˜o de controle, ap´os a fase de ajuste inicial, cresce e estabiliza-se em aproximadamente u¯c ≈ 0, 5 para manter a forma¸c˜ao entre os agentes.

FIGURA 4.2 – Esf or¸c o de Controle T otal para pf alha = δ = η = 0 e Nobst = 0

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

51

Para obter o comportamento de desvio de obst´aculos, analisamos os efeitos de um campo potencial artificial repulsivo no sistema, composto pela soma de uma componente → − para evitar colis˜oes e manter o grupo coeso e outra para regular a velocidade V i de um agente segundo a m´edia ponderada da velocidade de seus vizinhos, segundo (TANNER; JADBABAIE; PAPPAS,

2003).

Como resultado, na Figura 4.3 temos a evolu¸ca˜o m´edia das estimativas de conectividade feitas pelos agentes (em linhas tracejadas) em compara¸ca˜o com o valor real de λ2 , em azul, para um total de 50 simula¸co˜es sem qualquer tipo de perturba¸c˜ao, mas com um obst´aculo posicionado em uma posi¸ca˜o do ambiente de forma a ficar no caminho do primeiro agente em tobst ≈ 2 s.

¯ i para pf alha = δ = η = 0 e Nobst = 1 FIGURA 4.3 – λ2 e λ 2

Diferentemente da simula¸ca˜o na ausˆencia de obst´aculos estudada na Figura 4.1, o valor m´edio das estimativas de conectividade foi sempre maior ou igual ao valor de λ2 para o sistema. No exemplo de simula¸ca˜o feita em um ambiente na presen¸ca de um obst´aculo, o agente que liderava a forma¸ca˜o diminuiu a sua velocidade enquanto o contornava. Esse pequena

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

52

redu¸ca˜o feita pelo l´ıder causou uma leve aproxima¸ca˜o dos agentes, e consequentemente, ¯ i . No entanto, assim que o l´ıder desviou-se do obst´aculo, um breve e sutil aumento de λ 2 seguiu o seu curso e deixou os outros agentes para tr´as, aumentando levemente a distˆancia ¯ i quanto de λ2 . Em t ≈ 2, 25 s, o valor da entre eles, resultando na queda tanto de λ 2 conectividade ´e igual ao de de suas estimativas, e ap´os os u ´ltimos agentes passarem pelo obst´aculo, a conectividade recupera o mesmo valor em regime que o estudado na Figura 4.1, de λ2 ≈ 2, 1, mas agora o faz em t ≈ 2, 5 s. Este melhor resultado pode ser explicado levando em considera¸ca˜o a evolu¸ca˜o do esfor¸co total de controle para o conjunto de agentes, observada na Figura 4.4. Na Figura 4.2, em um ambiente com a ausˆencia de qualquer campo potencial, em virtude da inexistˆencia de obst´aculos, observamos que o controle atuava no in´ıcio da dinˆamica para conduzir os agentes a` sua posi¸ca˜o e voltava a agir na sequˆencia para mantˆe-los em forma¸ca˜o. Por isso observamos o valor elevado para o m´aximo inicial de u¯c , seguido por um controle que assumia um valor constante no decorrer da dinˆamica.

FIGURA 4.4 – Esf or¸c o de Controle T otal para pf alha = δ = η = 0 e Nobst = 1

Na Figura 4.4, na presen¸ca de um obst´aculo, o ambiente assume um valor de campo

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

53

potencial que n˜ao se anula mais, e podemos observar, portanto, um pico inicial de menor amplitude (¯ uc ≈ 1, 9 para t ≈ 0, 06, em valores n˜ao mostrados), respons´avel pelo controle de forma¸c˜ao dos agentes, seguido pela forma¸ca˜o de um platˆo a partir de t ≈ 1, 5 s em u¯c ≈ 0, 5. A presen¸ca do obst´aculo faz com que a a¸ca˜o de controle atue mais fortemente para garantir a forma¸c˜ao entre os agentes, acarretando no aumento de u¯c e na forma¸ca˜o do pequeno morro ao redor de t ≈ 2, 25 s (quando u¯c ≈ 0, 62, em resultados n˜ao mostrados), instante em que o centro de gravidade da forma¸ca˜o passava mais pr´oximo ao obst´aculo. Em seguida, o esfor¸co m´edio de controle volta a seu valor padr˜ao de u¯cregime = 0, 5, an´alogo aos valores em regime observados para a a¸ca˜o de controle em (SABATTINI et al., 2012). Como feito no referido trabalho, iremos analisar a partir de agora o desempenho do AMC na presen¸ca de um ambiente repleto de obst´aculos, verificando o impacto destes no esfor¸co de controle realizado pelos agentes.

4.2.1

An´ alise do Impacto do Esfor¸co de Controle na Manutenc˜ ¸ ao da Conectividade entre os Agentes

A partir de agora, iremos estudar a influˆencia do esfor¸co de controle no desempenho do AMC entre os agentes. Para abarcar a pluralidade dos casos envolvendo todos os diferentes tipos de perturba¸ca˜o, iremos considerar apenas an´alises para 1 simula¸c˜ao, fazendo referˆencia ao caso m´edio quando for necess´ario.

4.2.1.1

Esfor¸co de Controle em Agentes com Controladores Ideais

Para estudar o impacto do esfor¸co de controle no desempenho do algoritmo, simulamos inicialmente a intera¸ca˜o de 6 agentes comunicando-se na ausˆencia de perturba¸c˜oes em um

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

54

ambiente com 150 obst´aculos, atuando cada um deles com um controlador ideal. Na Figura 4.5 a seguir, temos a evolu¸ca˜o da conectividade (em linha pontilhada preta) e de suas estimativas (em linhas cont´ınuas e coloridas) ao longo da dinˆamica para este caso.

20 λ2 λ i2

λ2

15

10

5

0 0

1

2

3

4

5

t FIGURA 4.5 – λ2 e λi2 para pf alha = δ = η = 0 e Nobst = 150

Como notamos, a conectividade (em pontilhado) e suas estimativas s˜ao positivas ao longo de toda a dinˆamica, com estas sempre maiores que aquela para t > 0, 07 s. Em t ≈ 1, 05 s os robˆos come¸cam a percorrer a regi˜ao dos obst´aculos, e o fazem at´e t ≈ 3, 71 s quando a forma¸ca˜o e os valores de λ2 e λi2 iniciam o processo de estabiliza¸c˜ao em 2, 35 e 2, 53, aproximadamente, que s˜ao os seus valores de regime. Notamos tamb´em que a presen¸ca de obst´aculos faz com que os robˆos deixem momentaneamente suas posi¸c˜oes na forma¸c˜ao (para contorn´a-los), ocasionando aumentos (ou quedas) abruptos no valor das estimativas e principalmente no valor de λ2 , em virtude da aproxima¸ca˜o (ou afastamento) eventual dos agentes. Na Figura 4.6, o valor de uc relativo a essa simula¸ca˜o ´e representado. Lembrando que

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

55

2

u ¯c

1.5

1

0.5

0 0

1

2

3

4

5

t FIGURA 4.6 – uc para pf alha = δ = η = 0 e Nobst = 150 o esfor¸co de controle atua para evitar a perda de conectividade entre os agentes, temos que seus principais m´aximos ocorrem nos instantes em que os agentes tendem a se afastar, o que ocorre devido ao desvio dos obst´aculos. No caso, a a¸ca˜o de controle assume seus principais m´aximos nos instantes t1 ≈ 2, 42 s e t2 ≈ 3, 46 s, correspondentes na Figura 4.5 a` revers˜ao da queda e a um leve aumento do valor de λ2 . Na Figura 4.7 temos a representa¸c˜ao ampliada do espectro de amplitude unilateral de uc , contendo a magnitude de cada uma das componentes espectrais que comp˜oem o sinal de controle da Figura 4.6 (o diagrama completo apresenta a mesma forma prolongada, com magnitude m´axima de |uc | ≈ 0, 038 para f = 0 e |uc | ≈ 0 para f = 5kHz, em dados n˜ao mostrados). A an´alise das frequˆencias componentes do sinal de controle nos mostra que ele ´e constitu´ıdo principalmente por frequˆencias mais baixas, mas cont´em participa¸c˜oes de frequˆencias elevadas (no caso, at´e 5 kHz), que mesmo sendo muito altas para um sistema mecˆanico,

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

56

−3

5

x 10

4

|u c |

3

2

1

0 0

50

100

150

200

250

300

f ( Hz )

FIGURA 4.7 – Espectro de Amplitude ampliado de uc s˜ao importantes para garantir a manuten¸c˜ao de conectividade na presen¸ca de perturba¸co˜es. A seguir, simularemos o impacto de atua¸ca˜o do algoritmo proposto em controladores que podem ser implementados no mundo real.

4.2.1.2

Esfor¸co de Controle em Agentes com Controladores Implement´ aveis no Mundo Real

No mundo real, um agente reage de maneira distinta a`s componentes de altas e baixas frequˆencias de um esfor¸co de controle, principalmente devido a suas caracter´ısticas inerciais. Tomando por base alguns exemplos na literatura, temos que um sistema real envolvendo a velocidade de robˆos f´ısicos apresenta um controle atuando com uma frequˆencia da ordem de aproximadamente 10 rad/s ≈ 1, 59 Hz, sejam eles terrestres (de acordo com (YAN et al., 2006)) ou aqu´aticos (segundo (TAN et al., 2006)). Por isto, adicionamos

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

57

um filtro passa baixas de primeira ordem ao sinal de controle, com fun¸ca˜o de transferˆencia dada pela Equa¸c˜ao (4.2), atenuando as frequˆencias mais altas que 10 rad/s para verificar qual seria o desempenho da estrat´egia proposta em robˆos f´ısicos no mundo real.

H(s) =

10 s + 10

(4.2)

Os valores da conectividade e de suas estimativas relativos a uma dinˆamica num ambiente com 150 obst´aculos em que 6 agentes interagem na ausˆencia de perturba¸co˜es, cada um deles com um controlador fact´ıvel de ser implementado no mundo real, dado pela Equa¸ca˜o 4.2, podem ser vistos na Figura 4.8.

20 λ2 λ i2

λ2

15

10

5

0 0

1

2

3

4

5

t FIGURA 4.8 – λ2 e λi2 com pf alha = δ = η = 0 e Nobst = 150 para agentes com um controlador f act´ıvel de implementa¸c˜a o no mundo real

Como notamos, o sistema se manteve conectado ao longo de toda a intera¸c˜ao (λ2 > 0, ∀t > 0), mesmo com a atua¸ca˜o do filtro proposto. A conectividade (em pontilhado) e suas estimativas s˜ao positivas ao longo de toda a dinˆamica, com estas sempre maiores

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

58

que aquela para t > 0, 08 s. Em t ≈ 1, 05 s, os robˆos come¸cam a percorrer a regi˜ao dos obst´aculos, e o fazem at´e t ≈ 4, 15 s, quando a forma¸c˜ao e os valores de λ2 e λi2 iniciam o processo de estabiliza¸ca˜o em 2, 28 e 2, 49, aproximadamente, que s˜ao os seus valores de regime. Se compararmos os valores de λ2 e λi2 da Figura 4.8 `aqueles assumidos na Figura 4.5, veremos que o controlador proposto mant´em as caracter´ısticas da conectividade na dinˆamica do grupo de agentes. A evolu¸ca˜o temporal do esfor¸co de controle para um controlador tipicamente realiz´avel pode ser observada na Figura 4.9.

2

u ¯c

1.5

1

0.5

0 0

1

2

3

4

5

t FIGURA 4.9 – ucf ilt ampliado para pf alha = δ = η = 0 e Nobst = 150

Na Figura 4.9 notamos que os m´aximos de controle, em compara¸c˜ao com a Figura 4.6, s˜ao suavizados devido `a filtragem adicionada para as componentes de alta frequˆencia. A transi¸ca˜o entre m´aximos e m´ınimos, antes feita em pequenos intervalos de tempo (formando os diversos spikes observados na Figura 4.6) passam a ser feitas de forma mais branda, diminuindo inclusive a participa¸ca˜o do m´aximo inicial do esfor¸co de controle para

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

59

organiza¸c˜ao dos agentes. Na compara¸c˜ao com a Figura 4.8 vemos que o controle cresce (ocasionando, por exemplo, os m´aximos de uc1 ≈ 1, 22 em t1 ≈ 2, 52s e de uc2 ≈ 0, 97 em t2 ≈ 3, 34s) em resposta a`s quedas no valor de λ2 , mas agora o faz com uma in´ercia introduzida pelo Filtro da Equa¸ca˜o 4.2. −3

5

x 10

4

|u c |

3

2

1

0 0

50

100

150

200

250

300

f ( Hz )

FIGURA 4.10 – Espectro de Amplitude unilateral ampliado de ucf ilt para pf alha = δ = η = 0

A distribui¸ca˜o de frequˆencias de ucf ilt , dada pela Figura 4.10, nos mostra uma redu¸ca˜o da contribui¸c˜ao de frequˆencias mais altas no sistema (verificada pela atenua¸c˜ao das componentes na “cauda a` direita” do gr´afico, a partir da frequˆencia de corte). Assim, de acordo com os resultados apresentados nesta se¸c˜ao, verificamos que o sistema proposto por (SABATTINI et al., 2012) ´e vi´avel para ser implementado em um ambiente tipicamente real livre de perturba¸c˜oes.

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

4.3

60

Modelo de Conectividade na Presen¸ ca de Perturba¸c˜ oes

Estudaremos a partir de agora o impacto dos diversos tipos de perturba¸ca˜o e suas consequˆencias na manuten¸ca˜o da conectividade para o grupo de agentes regido pela dinˆamica descrita na Se¸c˜ao 2.2.2. Faremos ent˜ao a an´alise do impacto de Falha, Atraso e Ru´ıdo na comunica¸ca˜o entre os robˆos para obter um modelo que descreva as caracter´ısticas encontradas em um sistema do mundo real. Por motivos de clareza, daqui em diante iremos nos referir `a medida de conectividade, a suas estimativas e ao esfor¸co de controle na presen¸ca de perturba¸c˜oes (representados at´e 0

0

ent˜ao por λ02 , λi2 e uc ) apenas como λ2 , λi2 e uc . Tamb´em reportaremo-nos a` estimativa de uma componente de υ2 feita pelo agente i (at´e ent˜ao denotada por υ˜2i ) apenas como υ2i . A medida de conectividade na ausˆencia de perturba¸co˜es (at´e aqui representada por ¯ 2 , apenas para efeitos de compara¸ca˜o. λ2 ) ser´a representada nos gr´aficos como λ

4.3.1

Falha

4.3.1.1

Falha em Agentes com Controladores Ideais

Relataremos a seguir os resultados para a intera¸c˜ao entre agentes com controladores ideais em que pf alha > 0, sem a presen¸ca de outras perturba¸c˜oes na dinˆamica (δ = η = 0). Na Figura 4.11 temos a evolu¸ca˜o da conectividade e de suas estimativas para N = 5 agentes interagindo em um ambiente com Nobst = 150 obst´aculos para pf alha = 0, 2. Como pode-se observar, apesar da adi¸ca˜o de falhas ao processo de comunica¸ca˜o, o sistema manteve-se conectado durante toda a dinˆamica (λ2 > 0, ∀t > 0). A conecti-

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

61

20 λ2 ¯2 λ λ i2

λ2

15

10

5

0 0

1

2

3

4

5

t ¯ 2 com pf alha = 0, 2 e δ = η = 0 para agentes com controladores FIGURA 4.11 – λ2 , λi2 e λ ideais e Nobst = 150 vidade dos agentes cresce at´e atingir um m´aximo inicial (de λ2 ≈ 4, 07 em t = 0, 06 s), enquanto suas estimativas oscilam em um padr˜ao aproximadamente per´ıodico (de frequˆencia f20% ≈ 13, 91Hz), atingindo um m´aximo inicial de λi2 = 12, 92 em t ≈ 0, 02s. Os robˆos percorrem o territ´orio com obst´aculos entre tobst0 ≈ 0, 81 s e tobst1 ≈ 3, 19 s, com separa¸co˜es tempor´arias dos agentes durante o processo de desvio (que podem ser verificadas por trˆes vales no valor de λ2 na Figura 4.11). Neste caso, a existˆencia de falha no sistema n˜ao altera substancialmente os resultados de λ2 obtidos at´e ent˜ao em rela¸ca˜o ao caso livre de perturba¸co˜es da Figura 4.5. Para pf alha = 0, 20, o valor das estimativas deteriora-se um pouco mas termina a dinˆamica oscilando em torno de λi2 ≈ 2, 31, enquanto λ2 ≈ 2, 03. Na Figura 4.12, temos o comportamento do esfor¸co de controle referente a essa intera¸ca˜o. O arranjo aleat´orio inicial caracteriza-se por dois agentes que come¸cam a dinˆamica

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

62

muito pr´oximos uns dos outros, e por isso o m´odulo do esfor¸co de controle m´edio apresenta um m´aximo elevado (uc ≈ 34.8 em t = 0, em valor n˜ao mostrado). Em t ≈ 0, 05 s, enquanto as estimativas atingem o seu menor valor (na oscila¸ca˜o negativa subsequente ao overshoot inicial), o algoritmo de manuten¸ca˜o de conectividade atua para colocar os agentes em forma¸ca˜o, observando-se o m´aximo local (de uc approx1, 18) na Figura 4.12. A seguir, o esfor¸co de controle apresenta um m´aximo (de uc ≈ 2, 06 em t ≈ 1, 93 s) para estabelecer a forma¸c˜ao dos agentes, que percorrem a regi˜ao dos obst´aculos (entre tobst0 ≈ 0, 81s e tobst1 ≈ 3, 19s).

2.5

2

u ¯c

1.5

1

0.5

0 0

1

2

3

4

5

t FIGURA 4.12 – uc para pf alha = 0, 2 e δ = η = 0 em agentes com controladores ideais e Nobst = 150

A compara¸c˜ao do controle da Figura 4.12 com aquele observado na Figura 4.6 (em que pf alha = 0) nos mostra que uc ´e consideravelmente suscet´ıvel `a presen¸ca de falhas, adquirindo um comportamento altamente ruidoso nesse caso. Se considerarmos que a gera¸ca˜o de n´ umeros pseudoaleat´orios (feita com o ambiente de simula¸c˜ao descrito na Se¸ca˜o 4.1) pode ser aproximada para a de n´ umeros aleat´orios,

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

63

temos que a probabilidade de falha ´e independente e igualmente distribu´ıda para todos os robˆos. Assim, a probabilidade de falha para o sistema (ou seja, de qualquer um dos agentes que o comp˜oem) em cada itera¸c˜ao pode ser expressa pela Equa¸c˜ao 4.3.

psist f alha = N.pf alha

(4.3)

Para o caso em quest˜ao, temos que psist c˜a o de simula˜ ao f alha = 5 . 0, 2 = 1 f alha/itera¸ . Ou seja, mesmo com robˆo falhando em m´edia por itera¸ca˜o, os resultados observados na Figura 4.11 mostram que o modelo consegue responder bem a esse tipo de perturba¸ca˜o para agentes com controladores ideais. Na compara¸c˜ao com os resultados para o caso livre de perturba¸co˜es da Figura 4.5, vemos que a adi¸c˜ao de falha ao sistema causa muito mais oscila¸c˜oes em uc , exigindo um controle que atue de forma r´apida para recuperar os efeitos das informa¸co˜es incorretas. De forma geral, a perturba¸ca˜o prejudica os valores de λi2 , que levam o agente a calcular um valor incorreto de uc , podendo fazer com que a conectividade do sistema se anule (λ2 = 0) durante a dinˆamica. Na Figura 4.13 temos a distribui¸ca˜o ampliada de frequˆencias do sinal de controle para caso de falha estudado (pf alha = 0, 20). Da mesma forma que nos casos anteriores, h´a uma maior participa¸c˜ao de componentes de baixa frequˆencia, mas a compara¸c˜ao com os resultados do caso livre de perturba¸co˜es da Figura 4.6 mostra que a presen¸ca de falhas de comunica¸c˜ao acaba por aumentar levemente a influˆencia de componentes de alta frequˆencia no esfor¸co de controle. No caso da Figura 4.13, temos um aumento das contribui¸co˜es principalmente para f1 = 10, 7 Hz e f2 = 17, 6 Hz (em que |uc1 | = 1, 02.10−3 e |uc2 | = 8, 71.10−4 ).

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

64

−3

5

x 10

4

|u c |

3

2

1

0 0

50

100

150

200

250

300

f ( Hz )

FIGURA 4.13 – Espectro de Amplitude unilateral ampliado de uc para pf alha = 0, 2 e δ = η = 0 em agentes com controladores ideais e Nobst = 150 0

Isso se explica pelo chaveamento de υ2i entre υ2i , quando h´a a estima¸ca˜o normal dos pa∗

rˆametros, e υ2i , na ocorrˆencia de falha, o que ocasiona as mudan¸cas mais frequentes no valor de λ02 observadas na Figura 4.11 e acaba por contribuir para a participa¸c˜ao de frequˆencias mais altas para uc . No entanto, mesmo na presen¸ca de psist c˜ a o, f alha = 1 f alha/itera¸ em m´edia, podemos afirmar que o algoritmo proposto por (SABATTINI et al., 2012), para controladores ideais, ´e resiliente a uma pf alha pequena (igualmente distribu´ıda) no envio da informa¸ca˜o, preservando a conectividade dos agentes.

4.3.1.2

Falha em Agentes com Controladores Implement´ aveis no Mundo Real

Relataremos a seguir os resultados para a intera¸c˜ao entre agentes com controladores tipicamente implement´aveis na realidade, em que pf alha > 0 e sem a presen¸ca de outras perturba¸c˜oes na dinˆamica (δ = η = 0). Na Figura 4.14 temos a evolu¸ca˜o da conectividade

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

65

e de suas estimativas para N = 5 agentes, com controladores tipicamente reais, interagindo em um ambiente com Nobst = 150 obst´aculos para pf alha = 0, 2.

15 λ2 ¯2 λ λ i2

λ2

10

5

0 0

1

2

3

4

5

t ¯ 2 com pf alha = 0, 2 e δ = η = 0 para agentes com controladores FIGURA 4.14 – λ2 , λi2 e λ tipicamente reais e Nobst = 150

Na Figura 4.14 notamos que o comportamento de um controlador tipicamente real (atrav´es da adi¸ca˜o do Filtro Passa Baixas ao sinal) n˜ao altera consideravelmente o comportamento do sistema, pois tanto o valor de λ2 quanto o de λi2 mantiveram-se positivos na dinˆamica. As estimativas iniciais (λi2 ≈ 10, 2 em t = 0) atingem um m´aximo no in´ıcio (λi2 ≈ 14, 9 em t ≈ 0, 02 s), enquanto o valor da conectividade decresce (a partir de λ2 ≈ 4, 40 em t = 0) e estabiliza-se temporariamente em um patamar (λ2 ≈ 2, 32 de t1 ≈ 0, 44 s at´e t2 ≈ 1, 07 s), decaindo lentamente enquanto os agentes assumem a sua forma¸c˜ao. O trajeto percorrido pelos agentes frente aos obst´aculos ´e o mesmo que o percorrido ¯ 2 apresentam o pelos agentes na ausˆencia de perturba¸co˜es, e por isso as curvas de λ2 e λ mesmo aspecto (com um leve deslocamento no tempo, em virtude da existˆencia de falhas

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

66

na comunica¸ca˜o). No caso, λ2 ≈ 2, 36 em tobst0 ≈ 0, 88 s, quando os agentes come¸cam a percorrer o conjunto de obst´aculos, at´e λ2 ≈ 1, 18 em tobst1 ≈ 3, 40 s, quando o terminam de fazˆe-lo. A partir de t ≈ 3, 91 s os agentes aproximam-se e entram em forma¸ca˜o novamente, e a dinˆamica termina com λ2 ≈ 2, 02 e λi2 ≈ 2, 29 em t = 5 s. O desempenho de λ2 na execu¸c˜ao com um controlador tipicamente real (dado pela Figura 4.14) apresenta transi¸c˜oes mais suaves que o caso de um controlador ideal (dado pela Figura 4.11), uma vez que a “in´ercia” do sistema `as varia¸c˜oes de ucf ilt (e consequentemente, `as varia¸co˜es de λ2 ) ´e muito maior que aquela referente `as varia¸co˜es de uc para o caso de um controlador ideal. Como notamos, para obst´aculos pontuais e em condi¸co˜es bem comportadas, o sistema parece adaptar-se bem `a atenua¸c˜ao das componentes de alta frequˆencia para o esfor¸co de controle.

1

0.8

u ¯c

0.6

0.4

0.2

0 0

1

2

3

4

5

t FIGURA 4.15 – ucf ilt para pf alha = 0, 2 e δ = η = 0 em agentes com controladores tipicamente reais e Nobst = 150

A evolu¸ca˜o de ucf ilt pode ser vista na Figura 4.15. Podemos observar na Figura 4.14 que λi2 come¸ca estipulando valores elevados para a conectividade, e por isso ucf ilt adquire

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

67

valores pequenos inicialmente. ` medida que as estimativas diminuem, o valor de uc aumenta enquanto os agentes A f ilt max

atravessam o territ´orio com obst´aculos (entre tobst0 e tobst1 ), atingindo o m´aximo de ucf ilt ≈ 0, 90 em tmax ≈ 1, 38 s para manter a forma¸ca˜o dos agentes. Em regime, o esfor¸co de min

max

controle varia entre ucf ilt ≈ 0, 36 em t1 ≈ 3, 35 s e ucf ilt ≈ 0, 68 em t2 ≈ 3, 91 s. Se compararmos a evolu¸ca˜o de ucf ilt (Figura 4.15) com a de uc (Figura 4.12), notaremos que a adi¸ca˜o de um filtro ao esfor¸co de controle diminuiu a quantidade de chaveamentos na dinˆamica, resultando em um gr´afico “menos denso”, uma vez que as componentes de alta frequˆencia tiveram a sua participa¸c˜ao atenuada. Analogamente ao caso anterior, temos que a probabilidade de falha ´e independente e igualmente distribu´ıda para todos os robˆos, o que mostra que o modelo consegue responder bem `a presen¸ca de falhas para psist c˜a o, mesmo para agentes com f alha = 1 f alha/itera¸ controladores tipicamente implement´aveis no mundo real. Na Figura 4.16 temos a distribui¸ca˜o ampliada de frequˆencias do sinal de controle para pf alha = 0, 2 em agentes com controladores tipicamente reais. Assim como no caso de Falha em agentes com controladores ideais (ver Figura 4.13), h´a uma maior participa¸ca˜o de componentes de baixa frequˆencia no sinal, e a atua¸c˜ao do filtro da Equa¸ca˜o 4.2 em ucf ilt limita a influˆencia das componentes acima da frequˆencia de corte escolhida. Como resultado, a magnitude da cauda a` direita do gr´afico na Figura 4.16 foi atenuada em compara¸c˜ao com o da Figura 4.13 (chegando a uma atenua¸c˜ao de mais de 3.885 vezes para f = 5 kHz, em dados n˜ao mostrados). Na an´alise do gr´afico da Figura 4.16, notamos que ´e predominante a participa¸ca˜o de frequˆencias baixas, pois o gr´afico tem aproximadamente o formato de uma hip´erbole com um m´aximo em f ≈ 7, 86Hz (de

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

68

−3

5

x 10

4

|u c |

3

2

1

0 0

50

100

150 200 f (Hz)

250

300

FIGURA 4.16 – Espectro de Amplitude unilateral ampliado de ucf ilt para pf alha = 0, 2 e δ = η = 0 em agentes com controladores tipicamente reais e Nobst = 150 |ucf ilt | ≈ 9, 06.10−5 , em dados n˜ao mostrados).

Para pf alha = 0, 30, os resultados foram qualitativamente semelhantes ao caso j´a analisado, havendo manuten¸c˜ao da conectividade tanto para agentes com controlador ideal quanto para agentes com controlador tipicamente realiz´avel (em resultados n˜ao mostrados). Para pf alha = 0, 40 (em an´alise n˜ao mostrada), a conectividade manteve-se positiva para agentes com controlador ideal, sendo observada apenas uma latˆencia maior na convergˆencia das estimativas, devido a` maior taxa de perturba¸ca˜o. No entanto, a conectividade n˜ao se sustentou para agentes com controlador tipicamente realiz´avel. Nesse caso, ap´os as estimativas λi2 atingirem seu valor m´aximo, elas deca´ıram e acabaram tornando-se negativas por um per´ıodo de tempo, fazendo com que λ2 (que era positivo) declinasse e

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

69

acabasse se anulando na sequˆencia. Uma vez perdida a conectividade entre os agentes, as estimativas perdem a validade e os valores calculados pelos agentes passam a ser distintos e aleat´orios.

4.3.2

Atraso

4.3.2.1

Atraso em Agentes com Controladores Ideais

Relataremos a seguir os resultados para a intera¸c˜ao entre agentes com controladores ideais em que δ 6= 0, sem a presen¸ca de outras perturba¸c˜oes na dinˆamica (pf alha = η = 0). Na Figura 4.17 temos a evolu¸ca˜o da conectividade e de suas estimativas para N = 5 agentes interagindo em um ambiente com Nobst = 150 obst´aculos para δ = 0, 005 s e com uma frequˆencia de amostragem Fs = 10 kHz.

20 λ2 ¯2 λ λ i2

λ2

15

10

5

0 0

1

2

3

4

5

t ¯ 2 com δ = 0, 005 s e pf alha = η = 0 para agentes com FIGURA 4.17 – λ2 , λi2 e λ controladores ideais e Nobst = 150

Como podemos observar na Figura 4.17, apesar da adi¸ca˜o de atrasos pequenos na

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

70

comunica¸ca˜o, o sistema manteve-se conectado em toda a dinˆamica (λ2 > 0, ∀ t > 0). A conectividade dos agentes inicia a dinˆamica em decl´ınio (a partir de λ2 ≈ 3, 92 em t = 0 s) mas atinge o seu valor m´aximo (de λ2 ≈ 3, 93 em t ≈ 0, 06 s), enquanto as max

estimativas oscilam e a acompanham, ap´os atingirem um m´aximo inicial de λi2

= 19, 46

em tmax ≈ 0, 02 s. Os robˆos percorrem o territ´orio com obst´aculos entre tobst0 ≈ 0, 84 s e tobst1 ≈ 3, 30 s, provocando separa¸co˜es tempor´arias entre os agentes (que podem ser verificadas por dois vales no valor de λ2 ), com a conectividade atingindo seu m´ınimo (de λmin ≈ 0, 89) em tmin ≈ 2, 49 s. 2 Nesse caso, a existˆencia de atraso na comunica¸ca˜o n˜ao altera substancialmente a dinˆamica de conectividade at´e ent˜ao obtida para o caso de agentes com controladores ideais livre de perturba¸c˜oes da Figura 4.5. Para δ = 0, 005 s, as estimativas acompanham razoavelmente o valor de λ2 no gr´afico da Figura 4.17, e para t = 5 s, a intera¸c˜ao se encerra com λi2 ≈ 2, 35 e λ2 ≈ 2, 05. Na Figura 4.18, temos o comportamento do esfor¸co de controle referente a essa intera¸c˜ao. Inicialmente, uc atinge um m´aximo elevado enquanto os agentes colocam-se em max

forma¸c˜ao (uc

≈ 5, 09.105 em tmax ≈ 0, 05 s), referente ao instante em que as estimativas

atingem seu valor m´ınimo (de λi2 ≈ 0, 69) na Figura 4.17, ap´os o overshoot inicial. Ap´os essa a¸c˜ao, as estimativas voltam a subir e ap´os a oscila¸ca˜o, passam a ser maiores que a conectividade (λi2 > λ2 para t > 0, 16 s), antes de os agentes atravessarem o territ´orio com obst´aculos (entre tobst0 ≈ 0, 83 s e tobst1 ≈ 3, 30 s), conservando a conectividade ao longo de toda a dinˆamica. Em valores n˜ao mostrados, a compara¸c˜ao do caso estudado na Figura 4.18 com o referente a` Figura 4.6 (no caso em que δ = 0, para controladores ideais) nos mostra que o esfor¸co de controle apresenta um m´aximo inicial, na presen¸ca de atraso, aproximadamente

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

71

2

u ¯c

1.5

1

0.5

0 0

1

2

3

4

5

t FIGURA 4.18 – uc para δ = 0, 005 s e pf alha = η = 0 em agentes com controladores ideais e Nobst = 150 7.107 vezes maior para colocar os agentes em forma¸c˜ao. Ao atuar com retardo em rela¸c˜ao a`s informa¸co˜es do ambiente, o AMC perde o instante adequado de a¸ca˜o (que garante uc o´timo), o que exige uma a¸c˜ao muito maior para trazer os agentes a sua posi¸c˜ao na sequˆencia. Na Figura 4.19 temos a representa¸c˜ao ampliada do espectro de amplitude unilateral de uc , contendo a magnitude de cada uma das frequˆencias que comp˜oem o sinal de controle da Figura 4.18 (o diagrama completo apresenta assintoticamente a mesma forma estendida, com um m´aximo de |uc | ≈ 0, 49 para f = 0 e |uc | ≈ 1, 49.10−7 para f = 5 kHz, em dados n˜ao mostrados). Se compararmos o espectro de amplitude da Figura 4.19 com o caso de agentes com controlador ideal visto anteriormente (Figura 4.7), veremos que a presen¸ca de atraso no sistema modifica o car´ater da distribui¸c˜ao de frequˆencias em uc . Anteriormente, as

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

72

0.5

|u c |

0.45

0.4

0.35

0

50

100

150

200

250

300

f ( Hz )

FIGURA 4.19 – Espectro de Amplitude unilateral ampliado de uc para δ = 0, 005 s e pf alha = η = 0 em agentes com controladores ideais e Nobst = 150 frequˆencias distribu´ıam-se aproximadamente de acordo com uma hip´erbole, com maior participa¸ca˜o de componentes de frequˆencia f < 10 Hz. Nesse caso, para garantir a manuten¸ca˜o de conectividade com δ > 0, os agentes tˆem menos tempo para agir enquanto desviam dos obst´aculos, o que aumenta a presen¸ca de frequˆencias elevadas (que passam a se distribuir aproximadamente de acordo a forma da metade positiva de uma par´abola invertida, como pode-se observar na Figura 4.24). Mais especificamente, ´e poss´ıvel observar que aumenta principalmente a contribui¸ca˜o das componentes de frequˆencia f em que 0 < f < 1, 4 KHz na dinˆamica, com |uc | ≈ 0, 49 para f = 0 Hz e |uc | ≈ 1, 5.10−2 para f = 1, 4 kHz (em magnitudes n˜ao discriminadas). Para 0 < δ < 5 ms, em todos os casos estudados (com resultados n˜ao relatados), o comportamento do algoritmo foi o mesmo, mantendo λ2 > 0 ao longo de toda a intera¸ca˜o (embora o comportamento de λi2 e uc variasse nas diferentes dinˆamicas, em virtude da forma¸ca˜o assumida pelos agentes. Em geral, o aumento da participa¸c˜ao de altas frequˆencias

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

73

em uc pode ser explicado pela existˆencia de retardo na comunica¸c˜ao frente ao processo de desvio de obst´aculos, uma vez que o algoritmo necessita agir em um tempo cada vez menor - usando-se, portanto, de frequˆencias mais altas - `a medida que os agentes atravessam o territ´orio com as informa¸co˜es atrasadas. Para δ > 5 ms, o retardo entre a detec¸ca˜o da situa¸ca˜o ambiente e a a¸ca˜o dos agentes sobre a mesma fez com que a dinˆamica n˜ao se sustentasse enquanto os robˆos atravessavam o territ´orio entre obst´aculos. Veremos mais informa¸c˜oes sobre este fenˆomeno na Se¸ca˜o 4.3.2.2. Portanto, podemos afirmar que o algoritmo proposto por (SABATTINI et al., 2012), para controladores ideais, ´e resiliente apenas a pequenos valores de δ na transmiss˜ao da informa¸c˜ao. H´a uma vers˜ao do algoritmo robusta e tolerante a atrasos maiores que garante a manuten¸c˜ao da conectividade entre agentes, descrita em (SECCHI; SABATTINI; FANTUZZI, 2012), com resultados apresentados que envolvem δ ≈ 0, 3 s.

4.3.2.2

Atraso em Agentes com Controladores Implement´ aveis no Mundo Real

Trataremos agora da intera¸c˜ao entre agentes com controladores tipicamente realiz´ aveis e com δ 6= 0, sem a presen¸ca de outras perturba¸c˜oes na dinˆamica (pf alha = η = 0). Analisaremos agora o desempenho do algoritmo proposto por (SABATTINI et al., 2012) frente a` presen¸ca de atrasos maiores na comunica¸ca˜o, relatando no final desta se¸ca˜o os resultados para valores menores de δ para agentes tipicamente realiz´aveis. Na Figura 4.20 temos a evolu¸c˜ao da conectividade e de suas estimativas para N = 5 agentes interagindo em um ambiente com Nobst = 150 obst´aculos para δ = 0, 01 s e com uma frequˆencia de amostragem Fs = 10 kHz.

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

74

15 λ2 ¯2 λ λ i2

λ2

10

5

0 0

1

2

3

4

5

t ¯ 2 com δ = 0, 010 s e pf alha = η = 0 para agentes com FIGURA 4.20 – λ2 , λi2 e λ controladores tipicamente realiz´a veis e Nobst = 150 Podemos observar que a conectividade (em linha preta tracejada na Figura 4.20) n˜ao se sustenta, uma vez que λ2 = 0 ao final da intera¸c˜ao. Inicialmente ela oscila e atinge o seu valor m´aximo (λ2 ≈ 4, 83 em t = 0, 15 s), estabilizando-se na sequˆencia em um patamar (λ2 ≈ 2, 0 de t1 ≈ 0, 70 s a t2 ≈ 0, 92 s) enquanto as estimativas entram em movimento de oscila¸c˜ao `a medida que a informa¸ca˜o atrasada ´e captada pelos agentes. Os agentes come¸cam a atravessar o territ´orio com obst´aculos em tobst0 ≈ 0, 93 s, ap´os as estimativas min

passarem a oscilar entre λi2

max

≈ −18, 7 (em valor n˜ao mostrado) e λi2

≈ 11, 1, em um

padr˜ao aproximadamente peri´odico (de frequˆencia f ≈ 20, 7 Hz), o que causa uma queda progressiva da conectividade at´e a desconex˜ao dos agentes (em tdisc ≈ 1, 97 s). Mesmo com a conectividade desfeita, os agentes continuam a opera¸ca˜o, o que leva os mesmos a separarem-se em dois grupos: como pode ser visto no v´ıdeo relativo a esta simula¸ca˜o, dois agentes afastam-se de seus pares ao desviar de uma fileira de obst´aculos (em t ≈ 1, 62 s), e ocasionam a queda observada em λ2 na Figura 4.20 (de λ20 ≈ 0, 63

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

75

para λ21 ≈ 0, 27). H´a ent˜ao a separa¸ca˜o dos agentes em dois grupos (um de 3 e outro de 2 robˆos), que passam a percorrer o territ´orio paralelamente, fora do raio de comunica¸ca˜o uns dos outros. Os dois grupos terminam de atravessar o territ´orio com obst´aculos em tobst1 ≈ 3, 97 s. Como visto na Se¸ca˜o 2.2.2, cada agente i estima o valor de λi2 a partir de

˜2 ∂λ , que ∂pi

envolve a soma da diferen¸ca na posi¸c˜ao de todos os agentes (ver Equa¸c˜ao 2.16). Uma vez que λ2 = 0, cada agente obt´em valores inv´alidos para a posi¸c˜ao de seus pares que est˜ ao ˜2 ∂λ fora de seu raio de comunica¸c˜ao, e portanto, valores inv´alidos para , que levam a ∂pi estimativas incorretas de λi2 . Nas simula¸co˜es com agentes situados em uma posi¸c˜ao inicial aleat´oria maior que o raio de comunica¸c˜ao previsto em (TANNER; JADBABAIE; PAPPAS, 2003) (em resultados n˜ao descritos), o comportamento do algoritmo previsto em (SABATTINI et al., 2012) foi an´alogo (e semelhante ao caso de Falha na comunica¸c˜ao com pf alha = 0, 40, relatado ao final da Se¸ca˜o 4.3.1.2): a partir do momento em que λ2 se anula, as estimativas perdem o valor real e algumas entram em movimento de oscila¸ca˜o. Tal fenˆomeno, comumente conhecido como chattering, ocorre com o algoritmo proposto por (SABATTINI et al., 2012) sempre que a conectividade global ´e perdida (λ2 = 0), mas robˆos pr´oximos continuam trocando informa¸ca˜o (o que pˆode ser verificado em outras simula¸co˜es, quando um robˆo foi posicionado muito distante dos outros, em resultados n˜ao mostrados). Assim, os robˆos passam a percorrer o ambiente globalmente desconectados de seus pares, mas com comunica¸ca˜o local entre robˆos pr´oximos. Nesse caso, o processo de desvio de obst´aculos fez com que houvesse a divis˜ao dos agentes em dois grupos: 2 robˆos tomaram trajet´orias distintas e acabassem saindo do raio de comunica¸c˜ao de seus pares. Como a manuten¸c˜ao da conectividade (λ2 > 0) ´e uma condi¸c˜ao necess´aria ao processo

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

76

de estima¸ca˜o para o referido algoritmo, uma vez perdida, n˜ao ´e mais poss´ıvel confiar nos valores locais estimados (λi2 ). De volta `a situa¸c˜ao analisada na Figura 4.20, temos que, devido a` presen¸ca de atraso, o grupo de agentes se separa em dois. Tal fenˆomeno pode ser entendido da seguinte forma: Para δ > 0, com abuso de nota¸c˜ao, se representarmos como λi2 (t) as estimativas de λ2 feitas pelo agente i com os dados do sistema no tempo t, teremos:

0

υ2i (t) = υ2i (t−δ) 6= υ2i (t) −→

∂λ2 (t − δ) ∂λ2 (t) ∂λ02 (t) 0 = 6= −→ λi2 (t) = λi2 (t−δ) 6= λi2 (t) ∂pi ∂pi ∂pi (4.4)

0

A estimativa υ2i feita pelos agentes difere do real valor assumido por υ2i em um dado 0

instante t, o que faz com que o λi2 obtido seja distinto de λi2 para o mesmo instante de 0

tempo. Como resultado, o valor de ucf ilt (esfor¸co de controle tipicamente realiz´avel na presen¸ca de perturba¸c˜oes) ´e distinto de uc (esfor¸co de controle necess´ario para garantir a manuten¸ca˜o de conectividade). Em decorrˆencia do atraso na dinˆamica, os agentes julgam que λ2 ´e positivo, e ao desviar dos obst´aculos, n˜ao atuam para movimentar-se na regi˜ ao onde a conectividade ´e conservada, o que faz com que ela n˜ao se sustente na execu¸ca˜o.

0

ucf ilt (t) 6= uc (t)

(4.5)

Da mesma forma que para a perda de conectividade no caso de Falhas na comunica¸ca˜o em agentes com controladores realiz´aveis (descrita ao final da Se¸ca˜o 4.3.1.2), na presen¸ca de atrasos ela ocorreu ap´os as estimativas feitas por alguns agentes assumirem valores negativos, um indicativo de que neste caso o algoritmo n˜ao prevˆe a manuten¸c˜ao

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

77

da forma¸ca˜o. Em outros testes realizados nas mesmas condi¸c˜oes (com resultados n˜ao mostrados), por´em na ausˆencia de obst´aculos, os agentes mantiveram-se conectados, o que mostra que a manuten¸c˜ao da conectividade, em si, n˜ao ´e prejudicada pelo atraso em um terreno livre, mas sim o seu comportamento aliado ao processo de desvio. A separa¸ca˜o do sistema se d´a ap´os os agentes come¸carem a atravessar a regi˜ao com os anteparos (o que ´e feito em tobst0 , mostrando que nesse caso o algoritmo de manuten¸ca˜o de conectividade n˜ao atua de maneira suficiente para garantir a coes˜ao do grupo frente ao efeito do campo potencial repulsivo caracter´ıstico dos mesmos, segundo (ZAVLANOS; PAPPAS, 2007). Este processo de desvio, no entanto, ´e uma funcionalidade inerente (e necess´aria) a um agente autˆonomo no mundo real. Portanto, podemos concluir que, segundo o algoritmo proposto por (SABATTINI et al., 2012), a conectividade entre agentes tipicamente reais na presen¸ca de obst´aculos n˜ao fica garantida na presen¸ca de atrasos de comunica¸c˜ao, mesmo para valores pequenos de δ. Na Figura 4.21 temos o comportamento do esfor¸co de controle referente a` simula¸c˜ao dada na Figura 4.20. No in´ıcio da opera¸ca˜o, o algoritmo de manuten¸ca˜o de conectividade n˜ao atua no sistema, pois as estimativas prevˆeem uma conectividade crescente enquanto os agentes se posicionam (como podemos ver na Figura 4.20, logo no in´ıcio da intera¸ca˜o). No entanto, as estimativas oscilam e, assim que elas se anulam (em t ≈ 0, 04 s), o algoritmo de mamax

nuten¸ca˜o de conectividade atua (ucf ilt ≈ 110, 6 em t ≈ 0, 04 s, na tentativa de garantir a manuten¸ca˜o de conectividade. Ao operar com informa¸ca˜o passada no sistema, o algoritmo perde o instante ´otimo de a¸ca˜o, e os agentes passam a operar de forma quase independente (com uc < 10−3 para t > 0, 36 s), at´e sa´ırem do raio de comunica¸ca˜o uns dos outros.

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

78

120 100

u ¯c

80 60 40 20 0 0

1

2

3

4

5

t FIGURA 4.21 – ucf ilt para δ = 0, 010 s e pf alha = η = 0 em agentes com controladores tipicamente reais e Nobst = 150 A an´alise da Figura 4.21 nos mostra que a existˆencia de atrasos (mesmo que pequenos) na comunica¸ca˜o acaba por modificar a dinˆamica do sistema, o que impede a atua¸c˜ao do esfor¸co de controle de forma gradual entre agentes tipicamente reais. Em suma, a existˆencia de atrasos na comunica¸ca˜o faz com que os agentes computem com informa¸c˜oes que refletem o passado do sistema e acreditem que est˜ao conectados (λi2 > 0). Cria-se um descompasso entre a medi¸c˜ao da situa¸ca˜o do ambiente (c´alculo de υ2i e de λi2 , feito localmente) e a a¸ca˜o adequada do robˆo sobre ele, e como a dinˆamica do sistema muda razoavelmente no intervalo considerado ( υ2 (t − δ) 6= υ2 (t) → λi2 (t − δ) 6= λi2 (t) ), o sistema passa a n˜ao responder a ucf ilt mais. Na Figura 4.22 temos a representa¸c˜ao ampliada do espectro de amplitude unilateral de ucf ilt , contendo a magnitude de cada uma das frequˆencias que comp˜oem o sinal de controle da Figura 4.21.

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

79

0.03 0.025

|u c |

0.02 0.015 0.01 0.005 0 0

50

100

150 200 f (Hz)

250

300

FIGURA 4.22 – Espectro de Amplitude unilateral ampliado de ucf ilt para δ = 0, 01 s e pf alha = η = 0 em agentes com controladores tipicamente reais e Nobst = 150 Mesmo sob a¸ca˜o do filtro, h´a uma grande participa¸ca˜o de componentes de altas frequˆencias, havendo aumento na contribui¸c˜ao para todas elas em rela¸ca˜o a` situa¸ca˜o sem perturba¸co˜es da Figura 4.10. No caso da Figura 4.22, h´a uma participa¸c˜ao de ucf ilt ≈ 2, 98.10−2 para f = 0 Hz e de ucf ilt ≈ 4, 74.10−5 para f = 5 kHz, em dados n˜ao mostrados).

Se a maior frequˆencia B de um sinal amostrado ´e conhecida, o Teorema da Amostragem de Nyquist-Shannon nos diz que o limite inferior da frequˆencia de amostragem para que assegure-se a reconstru¸ca˜o perfeita do mesmo ´e 2B. Ou seja, considerando o filtro passa-baixas como ideal, um sinal de controle com espectro de frequˆencias de at´e 10 Hz consegue amostrar (no caso, atuar sobre) um sinal de frequˆencia de at´e 5 Hz (e n˜ao 5 kHz, como no caso analisado). A participa¸c˜ao de frequˆencias elevadas no diagrama da Figura 4.27 pode ser entendida da seguinte forma: com a

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

80

conectividade interrompida no sistema, os agentes passam a se deslocar exclusivamente em fun¸ca˜o do algoritmo de desvio de obst´aculos, e na ausˆencia de um v´ınculo que garanta a manuten¸ca˜o da conectividade, componentes com frequˆencias mais elevadas come¸cam a atuar sobre ucf ilt . Portanto, podemos dizer que o resultado est´a de acordo com o esperado.

Para δ > 5.10−3 , os resultados foram an´alogos aos descritos na Se¸ca˜o 4.3.2.2, com separa¸c˜ao (t˜ao mais r´apida quanto maior o valor de δ) do conjunto de agentes em todos os casos estudados. Para δ ≤ 5.10−3 , os resultados foram an´alogos aos descritos na Se¸ca˜o 4.3.2.1, tanto para agentes com controladores ideais quanto para agentes com controladores tipicamente realiz´aveis (em resultados n˜ao mostrados). Nesse caso, mesmo obtendo informa¸c˜oes antigas do ambiente, os agentes conseguem operar de forma a manter λ2 > 0 ao percorrerem um territ´orio com obst´aculos. Em geral, notamos que a contribui¸ca˜o de componentes de alta frequˆencia em uc (ou ucf ilt ) ´e t˜ao maior quanto maior for o valor de atraso em quest˜ao. Assim, quanto maior o atraso, menor era a efic´acia na previs˜ao de λ2 , ficando mais suave a varia¸ca˜o de λi2 frente a`s mudan¸cas (muitas vezes abruptas) da conectividade.

Portanto, podemos afirmar que o algoritmo proposto por (SABATTINI et al., 2012), seja para controladores ideais ou para controladores tipicamente reais, n˜ao ´e resiliente a valores de δ ≥ 10−2 na transmiss˜ao da informa¸c˜ao.

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

4.3.3

Ru´ıdo

4.3.3.1

Ru´ıdo em Agentes com Controladores Ideais

81

A seguir est˜ao os resultados para a dinˆamica de agentes com controladores ideais em que η = 0.5, sem a presen¸ca de outras perturba¸co˜es na dinˆamica (pf alha = δ = 0). Na Figura 4.23 temos a evolu¸ca˜o da conectividade e de suas estimativas para N = 5 agentes interagindo em um ambiente com Nobst = 150 obst´aculos para η = 0.5, com uma frequˆencia de amostragem Fs = 10 kHz.

20 λ2 ¯2 λ λ i2

λ2

15

10

5

0 0

1

2

3

4

5

t ¯ 2 com η = 0, 5 e pf alha = δ = 0 para agentes com controladores FIGURA 4.23 – λ2 , λi2 e λ ideais e Nobst = 150

Como ´e poss´ıvel notar, o sistema manteve-se conectado ao longo de toda a dinˆamica (λ2 > 0, ∀ t > 0), mesmo com a existˆencia de ru´ıdo na comunica¸c˜ao. A conectividade entre os agentes cresce (a partir de λ2 ≈ 3, 84 em t = 0 s) at´e atingir o seu valor m´aximo (λmax = 4, 38 em tmax ≈ 0, 06 s), enquanto as estimativas oscilam e a acompanham ap´os 2 max

atingirem um m´aximo local (λi2

= 13, 09 em t ≈ 0, 03 s). Os agentes percorrem o

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

82

territ´orio com obst´aculos entre tobst0 ≈ 0, 80 s e tobst1 ≈ 3, 25 s, com 3 vales no valor da min

conectividade (que atinge o valor m´ınimo λi2

≈ 0, 61 em tmin ≈ 1, 59 s) enquanto os

obst´aculos s˜ao contornados, como podemos observar na Figura 4.23. A distribui¸c˜ao assumida pelo ru´ıdo ´e uniforme, o que acaba por “mascarar” para os agentes as quedas no valor de λ2 . Apesar de as estimativas aproximarem-se razoavelmente do valor da conectividade nos 2 u ´ltimos vales de λ2 , notamos que a existˆencia de ru´ıdo na informa¸c˜ao insere um grau de imprecis˜ao no processo de estima¸ca˜o (como j´a era esperado, λi2 varia com uma frequˆencia maior). Como podemos notar, o AMC mostra uma leve dificuldade em detectar a separa¸c˜ao dos agentes devido a` informa¸ca˜o ruidosa em agentes ideais. Os agentes estabilizam a forma¸ca˜o a partir de t ≈ 3, 82 s e, finalmente, terminam ¯ i ≈ 2, 40. a intera¸ca˜o com λ2 ≈ 2, 06 e λi2 oscilando em torno de λ 2 No caso estudado, a existˆencia de ru´ıdo na comunica¸c˜ao n˜ao altera substancialmente a dinˆamica da conectividade at´e ent˜ao obtida para o caso de agentes com controladores ideais livre de perturba¸co˜es da Figura 4.5 (na verdade, os agentes apenas assumem a sua posi¸ca˜o na forma¸ca˜o com uma latˆencia ligeiramente maior, em dados n˜ao mostrados). Na Figura 4.24 temos o comportamento do esfor¸co de controle referente a essa intera¸ca˜o. Podemos observar na Figura 4.23 que os agentes come¸cam a intera¸ca˜o estipulando valores elevados para λi2 , e por isso inicialmente o valor estabelecido para uc ´e reduzido (enquanto os agentes colocam-se em forma¸ca˜o, uc atinge um m´aximo local de uc ≈ 0, 07 em t ≈ 0, 07 s). As estimativas caem e a partir de t ≈ 0, 40 s, uc come¸ca a atuar mais intensamente para garantir a manuten¸c˜ao da forma¸c˜ao, observando-se os m´aximos de max1

uc

max2

≈ 7, 00 em tmax1 ≈ 2, 26 s e uc

≈ 6, 77 em tmax2 ≈ 2, 42 s.

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

83

8 7 6

u ¯c

5 4 3 2 1 0 0

1

2

3

4

5

t FIGURA 4.24 – uc para η = 0, 5 e pf alha = δ = 0 em agentes com controladores ideais e Nobst = 150 A compara¸c˜ao da Figura 4.24 com a Figura 4.6 (referente ao caso em que η = 0, para controladores ideais) mostra que o esfor¸co de controle apresenta um m´aximo inicial, na presen¸ca de ru´ıdo, aproximadamente 9, 8 vezes menor para colocar os agentes em forma¸ca˜o. Em compensa¸ca˜o, enquanto os agentes atravessam o territ´orio com obst´aculos, o valor de uc para manter a conectividade positiva ´e cerca de 4, 96 vezes maior do que na ausˆencia de perturba¸c˜oes. Ao atuar na presen¸ca de ru´ıdo, o AMC identifica a situa¸ca˜o inicial do ` ambiente de forma imprecisa, e por isso o esfor¸co de controle inicialmente ´e menor. A medida que os agentes avan¸cam e percorrem o territ´orio com os anteparos, a a¸c˜ao do algoritmo de desvio de obst´aculos (ADO, que ocorre em paralelo com a de manuten¸c˜ ao de conectividade e, por quest˜oes de modelagem, n˜ao ´e afetada pelo ru´ıdo) se d´a, e como a trajet´oria assumida pelos agentes ´e menos “´otima”, devido a` presen¸ca da perturba¸c˜ao, necessita-se de um esfor¸co de controle maior para manter a forma¸c˜ao.

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

84

Na Figura 4.25 temos a representa¸c˜ao ampliada do espectro de amplitude unilateral de uc , contendo a magnitude de cada uma das frequˆencias que comp˜oem o sinal de controle da Figura 4.24 (o diagrama completo apresenta a mesma forma estendida, com um m´aximo de |uc | ≈ 4, 4.10−2 para f = 0 kHz e |uc | ≈ 2, 44.10−4 para f = 5 kHz, em dados n˜ao relatados). −3

5

x 10

4

|u c |

3

2

1

0 0

50

100

150

200

250

300

f ( Hz )

FIGURA 4.25 – Espectro de Amplitude unilateral ampliado de uc para η = 0, 5 e pf alha = δ = 0 em agentes com controladores ideais e Nobst = 150

Da mesma forma que nos outros casos analisados, h´a uma maior contribui¸ca˜o de componentes de baixa frequˆencia, mas a compara¸c˜ao com o caso livre de perturba¸co˜es da Figura 4.7 nos mostra que a existˆencia de ru´ıdo na comunica¸ca˜o acaba por aumentar sensivelmente a influˆencia de componentes de m´edia e alta frequˆencia no esfor¸co de controle, com contribui¸c˜ao aproximadamente constante para f > 100 Hz. O aumento t˜ao expressivo para a atua¸c˜ao de componentes de alta frequˆencia ´e devido a` taxa de ru´ıdo do caso estudado: como η = 0.5, `a informa¸c˜ao original ´e acrescentado

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

85 0

um sinal ruidoso Zi ∼ N (0, 0.5), o que faz com que os valores assumidos por υ2i passem a distribuir-se aleatoriamente de acordo com uma distribui¸ca˜o normal. Como uc atua sobre um sinal que se altera mais frequentemente, aumenta em uc a participa¸ca˜o de componentes com f > 10 Hz, como notamos na Figura 4.25, em que a participa¸ca˜o de componentes para f > 30 Hz pode ser considerada aproximadamente constante. Assim, podemos afirmar que o algoritmo proposto por (SABATTINI et al., 2012), para controladores ideais, ´e resiliente a` influˆencia de um sinal com η pequeno na informa¸c˜ao, preservando a conectividade dos agentes.

4.3.3.2

Ru´ıdo em Agentes com Controladores Implement´ aveis no Mundo Real

Trataremos a seguir dos resultados para a intera¸ca˜o de agentes com controladores tipicamente realiz´aveis em que η 6= 0, sem a presen¸ca de outras perturba¸c˜oes na dinˆamica (pf alha = δ = 0). Na Figura 4.26 temos a evolu¸ca˜o da conectividade e de suas estimativas para N = 5 agentes interagindo em um ambiente com Nobst = 150 obst´aculos para η = 0, 5 e com uma frequˆencia de amostragem Fs = 10 kHz. Quanto ao comportamento da conectividade na Figura 4.26, verificamos que o desempenho de um controlador tipicamente real (simulado atrav´es da adi¸ca˜o de um Filtro Passa Baixas ao sinal) n˜ao altera consideravelmente o comportamento do sistema, pois mesmo na presen¸ca de ru´ıdo na comunica¸ca˜o, λ2 manteve-se positivo na dinˆamica (λ2 > 0, ∀t > 0). A conectividade entre os agentes inicialmente decresce (a partir de λ2 ≈ 4, 00 em t = 0 s), mas atinge o seu valor m´aximo na sequˆencia (λ2 ≈ 4, 52 em t ≈ 0, 13 s) enquanto min

as estimativas oscilam entre λi2

max

≈ 0 e λi2

≈ 9, 05. A conectividade varia de λ2 ≈ 3, 32

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

86

15 λ2 ¯2 λ λ i2

λ2

10

5

0 0

1

2

3

4

5

t ¯ 2 com η = 0, 5 e pf alha = δ = 0 para agentes com controladores FIGURA 4.26 – λ2 , λi2 e λ tipicamente realiz´a veis e Nobst = 150 em tobst0 = 1, 04 (quando os agentes come¸cam a percorrer a regi˜ao com obst´aculos) at´e λ2 ≈ 3, 88 em tobst1 ≈ 3, 63 s (quando terminam de fazˆe-lo). Sob a influˆencia do ru´ıdo, a a¸ca˜o de controle para manuten¸ca˜o de conectividade ´e prejudicada e n˜ao se estabiliza em um valor espec´ıfico ao fim da dinˆamica, como pode-se observar pela evolu¸c˜ao de λ2 na Figura 4.26. Como o ru´ıdo ´e uniformemente distribu´ıdo, a sua influˆencia sobre υ2i (e consequentemente sobre λi2 ) acaba“mascarando”para os agentes o movimento tempor´ario de separa¸c˜ao (e a consequente queda em λ2 ) para o algoritmo de manuten¸ca˜o de conectividade `a medida que a regi˜ao com obst´aculos ´e atravessada. Portanto, λ2 varia principalmente como consequˆencia do ru´ıdo ao longo da intera¸c˜ao (sem apresentar nenhuma queda significativa dada pelo processo de desvio de obst´aculos (n˜ao h´a nenhum vale em λ2 entre tobst0 e tobst1 ). Finalmente, a dinˆamica se encerra com λ2 ≈ 3, 12 e 0, 62 < λi2 < 6, 89 em t = 5 s.

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

87

Enquanto no caso de ru´ıdo em agentes com controladores ideais da Figura 4.23 as estimativas adquirem um aspecto levemente ruidoso (em compara¸ca˜o com o caso livre de perturba¸c˜oes da Figura 4.8), as varia¸c˜oes das estimativas em decorrˆencia de ru´ıdo para agentes tipicamente reais s˜ao acentuadamente maiores, como notamos na Figura 4.26. Ao filtrarmos as componentes de alta frequˆencia em ucf ilt , de acordo com a Equa¸c˜ao (2.19), estamos tamb´em limitando o espectro de frequˆencias de

∂λ2 , o que, al´em de tornar a ∂pi

trajet´oria dos agentes “menos o´tima”, faz com que λ2 varie de forma mais “brusca” de acordo com mudan¸cas na posi¸ca˜o entre os agentes (como notamos na Figura 4.26). Na Figura 4.27 temos a evolu¸ca˜o de ucf ilt relativa `a simula¸ca˜o da Figura 4.26, para o caso de ru´ıdo em agentes com controladores implement´aveis no mundo real.

100

80

u ¯c

60

40

20

0 0

1

2

3

4

5

t FIGURA 4.27 – ucf ilt para η = 0, 5 e pf alha = δ = 0 em agentes com controladores tipicamente reais e Nobst = 150

No in´ıcio da intera¸ca˜o, enquanto os agentes colocam-se em forma¸ca˜o, observa-se um m´aximo local no esfor¸co de controle (ucf ilt ≈ 88, 2 em t ≈ 0, 07 s), seguido pelo esfor¸co de max

controle m´aximo (ucf ilt ≈ 3, 07.103 em tmax ≈ 0, 52 s, em valor n˜ao exibido), a` medida que

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

88

os agentes entram em forma¸c˜ao. Devido `a influˆencia de ru´ıdo na comunica¸c˜ao, os agentes identificam imprecisamente o seu pr´oprio estado e, `a medida que a dinˆamica se inicia, aproximam-se ao inv´es de tomar o seu lugar na forma¸ca˜o (como pode ser visto no v´ıdeo relativo a esta simula¸c˜ao, referenciado na Se¸c˜ao 4.1), o que explica o alto valor assumido por ucf ilt para garantir a forma¸ca˜o de agentes. Na sequˆencia, a regi˜ao com obst´aculos come¸ca a ser atravessada (entre tobst0 e tobst1 ) e o valor de ucf ilt diminui de intensidade devido ao movimento de separa¸ca˜o imposto pelo ADO, mas ainda exige m´aximos locais (como ucf ilt ≈ 275 em t ≈ 3, 13 s), a fim de garantir a manuten¸ca˜o de conectividade. Finalmente, ap´os atravessar a regi˜ao com obst´aculos, os valores assumidos por ucf ilt diminuem de intensidade (com um m´aximo local de ucf ilt ≈ 275 em t ≈ 3, 13 s, por exemplo). Finalmente, ap´os passar pelos obst´aculos, os valores assumidos por ucf ilt diminuem de intensidade (com um m´aximo local de ucf ilt ≈ 50, 4 em t ≈ 4, 98 s), mas terminam a intera¸c˜ao assumindo outros m´aximos para evitar a desconex˜ao na presen¸ca de ru´ıdo. A existˆencia de ru´ıdo no processo de comunica¸c˜ao n˜ao afeta diretamente o AMC porque, por ser uma perturba¸ca˜o identicamente distribu´ıda, altera de forma estatisticamente 0

sim´etrica a estima¸ca˜o de λi2 em comunica¸c˜oes distintas. No entanto, o ru´ıdo em υ2i acaba por prejudicar a manuten¸ca˜o de forma¸ca˜o entre os robˆos, que passam a ter dificuldades em distribuir-se regularmente desde o in´ıcio da intera¸ca˜o. A compara¸c˜ao da Figura 4.27 com a Figura 4.9 (referente ao caso em que η = 0, para controladores tipicamente realiz´aveis) nos mostra que o AMC realizou um esfor¸co total de controle aproximadamente 438, 6 vezes maior na presen¸ca de ru´ıdo. Nesse caso, a a¸c˜ao do ADO (que ocorre paralelamente a` de manuten¸c˜ao de conectividade e n˜ao ´e afetada pelo ru´ıdo) acontece, e como a trajet´oria assumida pelos agentes ´e menos “´otima”, devido a` presen¸ca da perturba¸c˜ao, necessita-se de um esfor¸co de controle maior para distribuir os

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

89

agentes regularmente. Na Figura 4.28 temos a distribui¸ca˜o ampliada do espectro de frequˆencias do sinal de controle para η = 0, 5 em agentes com controladores tipicamente reais.

4 3.5 3

|u c |

2.5 2 1.5 1 0.5 0 0

50

100

150 200 f (Hz)

250

300

FIGURA 4.28 – Espectro de Amplitude unilateral ampliado de ucf ilt para η = 0, 5 e pf alha = δ = 0 em agentes com controladores tipicamente reais e Nobst = 150

O gr´afico completo apresenta a mesma forma prolongada, com maior contribui¸c˜ao de baixas frequˆencias (|ucf ilt | ≈ 3, 82 para f = 0 Hz) e uma participa¸c˜ao m´edia aproximadamente constante para frequˆencias mais elevadas (no caso, |ucf ilt | ≈ 4, 60.10−3 para f = 5 kHz, em valores n˜ao discriminados). Mesmo embora o sistema tenha se mantido conectado na dinˆamica (como verificamos a partir da evolu¸ca˜o de λ2 na Figura 4.26), uma an´alise do espectro de frequˆencias da Figura 4.28 nos mostra que um sistema tipicamente real (com resposta limitada ao espectro de ucf ilt ) exige, para a manuten¸ca˜o da conectividade na presen¸ca de ru´ıdo, um esfor¸co de controle com elevada participa¸ca˜o de altas frequˆencias.

CAP´ITULO 4. RESULTADOS EXPERIMENTAIS

90

Nesse caso, como η = 0.5, a` informa¸c˜ao original ´e acrescentado um sinal ruidoso 0

Zi ∼ N (0, 0.5), o que faz com que os valores assumidos por υ2i passem a distribuir-se aleatoriamente de acordo com uma distribui¸ca˜o normal. Como ucf ilt atua sobre um sinal que se altera mais frequentemente, aumenta no esfor¸co de controle a participa¸c˜ao de componentes com f > 10 Hz, como podemos observar na Figura 4.28, onde se nota uma contribui¸c˜ao significativa de componentes de frequˆencia f em que f < 238 Hz. Dessa forma, ´e poss´ıvel afirmar que a estrat´egia descrita em (SABATTINI et al., 2012) ´e resiliente a` influˆencia de ru´ıdo na transmiss˜ao da informa¸ca˜o.

Em todos os casos de ru´ıdo estudados (η = 0.1, 0.3, 0.5, 1.0 e 5.0, seja para agentes ideais ou tipicamente realiz´aveis), os resultados foram an´alogos, com manuten¸ca˜o de conectividade em todas as situa¸co˜es analisadas. Como pudemos verificar no caso de agentes tipicamente reais, no entanto, a menor participa¸ca˜o de componentes de alta frequˆencia no esfor¸co de controle prejudicou o processo de manuten¸ca˜o de forma¸c˜ao para o caso de ru´ıdo analisado. Em geral, para valores crescentes de η, maiores eram a dispers˜ao das estimativas de conectividade calculadas pelos agentes e maiores eram os valores assumidos por uc , com maior participa¸ca˜o de componentes de alta frequˆencias para η crescente. Em geral, a conectividade foi mantida em todos os casos de ru´ıdo analisados.

5 Conclus˜ ao Fizemos neste trabalho um estudo dos efeitos de diferentes tipos de perturba¸co˜es sobre um algoritmo de controle que, atrav´es da estima¸ca˜o descentralizada da conectividade alg´ebrica de um grafo de comunica¸ca˜o, garante a manuten¸c˜ao da conectividade entre um conjunto de robˆos na ausˆencia de qualquer tipo de perturba¸ca˜o, dada uma condi¸ca˜o inicial aleat´oria. Na referida an´alise, para os mesmos parˆametros de referˆencia adotados em (SABATTINI et al.,

2012), com a excess˜ao do caso de atraso na comunica¸c˜ao, a conectividade do grupo

se manteve em todos os casos para agentes com controladores ideais, (em que h´a resposta equˆanime tanto para as baixas quanto para as altas frequˆencias do esfor¸co de controle). Como visto na Se¸c˜ao 4.3, por´em, a atua¸ca˜o das altas frequˆencias tem papel importante para garantir a manuten¸ca˜o da conectividade entre os agentes na presen¸ca de perturba¸co˜es em um sistema tipicamente realiz´avel. Nesse caso, podemos sumarizar as an´alises feitas da seguinte forma: Para Falha na comunica¸c˜ao, o modelo ´e tolerante at´e uma probabilidade pmax ıf alha espec´ fica, a partir da qual os valores estimados se degeneram (no caso estudado, pmax f alha < 40%). A partir desse valor, as estimativas de υ2 feitas pelos agentes n˜ao s˜ao suficientes para assegurar λ2 > 0 enquanto eles percorrem um terreno entre obst´aculos.

˜ CAP´ITULO 5. CONCLUSAO

92

Para qualquer valor sens´ıvel de Atraso durante a transmiss˜ao da informa¸ca˜o, a conectividade n˜ao se mant´em na dinˆamica (no caso, o atraso ´e o u ´nico dos fenˆomenos em que a perda de conectividade ´e totalmente n˜ao detect´avel pelos agentes). Uma vez que λ2 = 0, cada um deles obt´em valores incorretos para a posi¸ca˜o dos vizinhos fora de seu raio de comunica¸ca˜o, e portanto, valores incorretos de λi2 . Neste caso, verificamos o fenˆomeno de chattering nas estimativas para os robˆos que continuam pr´oximos uns dos outros, mesmo com o fim da conectividade global. Para Ru´ıdo na comunica¸ca˜o, o modelo se mostrou tolerante para todos os casos analisados, uma vez que este tipo de perturba¸ca˜o n˜ao degenera completamente o valor de υ2 usado no processo de c´alculo de λi2 . Assim, ´e poss´ıvel a cada um dos agentes, ainda que imprecisamente, computar de forma a manter λ2 > 0 durante a intera¸ca˜o. Em suma, como a manuten¸ca˜o da conectividade ´e uma condi¸ca˜o necess´aria ao processo de estima¸ca˜o do algoritmo proposto por (SABATTINI; CHOPRA; SECCHI, 2011), uma vez perdida, n˜ao ´e mais poss´ıvel confiar nos valores locais estimados pelos agentes (λi2 ) na presen¸ca de elevadas taxas de Falha ou de qualquer valor percept´ıvel de Atraso na comunica¸ca˜o. Finalmente, podemos relatar como propostas de trabalhos futuros: a an´alise do desempenho dos algoritmos descritos em (SECCHI; SABATTINI; FANTUZZI, 2012) e em (SECCHI; SABATTINI; FANTUZZI,

2013) perante os diferentes tipos de perturba¸ca˜o relatados, estu-

dando a evolu¸c˜ao de λ2 frente ao comportamento do esfor¸co de controle e a seu espectro de frequˆencias; valida¸c˜ao dos resultados dos diferentes tipos de perturba¸c˜ao aqui estudados em robˆos reais, investigando a pertinˆencia das hip´oteses feitas para situa¸co˜es verific´aveis na realidade; estudar modelos mais realistas de perturba¸ca˜o (que, ao inv´es de supor υ2∗ = 1 para o caso de Falha, repete a u ´ltima estimativa: υ2∗ = υ2i (t − 1), por exemplo); an´alise dos

˜ CAP´ITULO 5. CONCLUSAO

93

resultados referentes a um modelo em que o ru´ıdo ´e acrescentado diretamente nas medidas de posi¸c˜ao (sendo propagado at´e as estimativas de υ2 e λ2 , e n˜ao atuando diretamente sobre elas); estudo do desempenho do sistema sob a influˆencia de uma combina¸c˜ao de diferentes tipos de perturba¸c˜oes (presen¸ca conjunta de Falha e Ru´ıdo ou qualquer outra combina¸c˜ao de perturba¸co˜es na comunica¸ca˜o, por exemplo) e verifica¸c˜ao dos resultados para conjuntos diferentes de parˆametros de simula¸ca˜o, comparando-os aos obtidos nesta disserta¸ca˜o.

Referˆ encias Bibliogr´ aficas BATTAGELLO, V. A.; RIBEIRO, C. H. C. Analysis of the effects of failure and noise in the distributed connectivity maintenance of a multi-robot system. In: INTERNATIONAL SYMPOSIUM ON COMPUTATIONAL INTELLIGENCE AND INFORMATICS, 15., Budapest. Proceedings... Piscataway: IEEE, 2014, p. 427–432, 2014. Dispon´ıvel em: . FAX, J. A.; MURRAY, R. M. Information flow and cooperative control of vehicle formations. IEEE Trans. Automat. Contr., v. 49, n. 9, p. 1465–1476, 2004. Dispon´ıvel em: . FIEDLER, M. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, v. 23, n. 98, p. 298–305, 1973. FREEMAN, R.; YANG, P.; LYNCH, K. Stability and convergence properties of dynamic average consensus estimators. In: IEEE. Decision and Control, 2006 45th IEEE Conference on. [S.l.]: IEEE, 2006. p. 338–343. GODSIL, C.; ROYLE, G. Algebraic Graph Theory. [S.l.]: volume 207 of Graduate Texts in Mathematics. Springer, 2001. (Graduate Texts in Mathematics., v. 207). HSIEH, M. A. et al. Maintaining network connectivity and performance in robot teams. J. Field Robotics, v. 25, n. 1-2, p. 111–131, 2008. Dispon´ıvel em: . JI, M.; EGERSTEDT, M. Distributed coordination control of multiagent systems while preserving connectedness. IEEE Transactions on Robotics, v. 23, n. 4, p. 693–703, 2007. Dispon´ıvel em: . SABATTINI, L.; CHOPRA, N.; SECCHI, C. On decentralized connectivity maintenance for mobile robotic systems. In: CDC-ECE. IEEE, 2011. p. 988–993. ISBN 978-1-61284-800-6. Dispon´ıvel em: . SABATTINI, L. et al. Distributed global connectivity maintenance for multi-robot systems. In: AUTOMATICA IT Congress, Benevento, Italy. [S.l.: s.n.], 2012. SABER, R. O.; MURRAY, R. M. Consensus problems in networks of agents with switching topology and time-delays. IEEE Transactions on Automatic Control, v. 49, n. 9, p. 1520–1533, 2003.

ˆ ´ REFERENCIAS BIBLIOGRAFICAS

95

SAVLA, K.; NOTARSTEFANO, G.; BULLO, F. Maintaining limited-range connectivity among second-order agents. SIAM J. Control and Optimization, v. 48, n. 1, p. 187–205, 2009. Dispon´ıvel em: . SECCHI, C.; SABATTINI, L.; FANTUZZI, C. Decentralized global connectivity maintenance for interconnected lagrangian systems with communication delays. Proceedings of the IFAC Workshop on Lagrangian and Hamiltonian Methods for Non Linear Control (LHMNLC), Bertinoro, Italy, 2012. SECCHI, C.; SABATTINI, L.; FANTUZZI, C. Decentralized global connectivity maintenance for interconnected lagrangian systems in the presence of data corruption. European Journal of Control, Elsevier, v. 19, n. 6, p. 461–468, 2013. SICILIANO, B.; KHATIB, O. (Ed.). Springer Handbook of Robotics. Berlin, Heidelberg: Springer, 2008. ISBN 978-3-540-23957-4. Dispon´ıvel em: . TAN, X. et al. An autonomous robotic fish for mobile sensing. In: Intelligent Robots and Systems, 2006 IEEE/RSJ International Conference on. [S.l.: s.n.], 2006. p. 5424–5429. TANNER, H.; JADBABAIE, A.; PAPPAS, G. J. Stable Flocking of Mobile Agents, Part I: Fixed Topology. IEEE, 2003. Dispon´ıvel em: . TREFETHEN, L. N.; BAU, D. Numerical Linear Algebra. [S.l.]: SIAM, 1997. ISBN 0898713617. YAN, S. et al. A 3-dofs mobile robot driven by a piezoelectric actuator. Smart Materials and Structures, v. 15, n. 1, p. N7, 2006. Dispon´ıvel em: . YANG, P. et al. Decentralized estimation and control of graph connectivity for mobile sensor networks. Automatica, v. 46, n. 2, p. 390–396, 2010. Dispon´ıvel em: . ZAVLANOS, M. M.; PAPPAS, G. J. Potential fields for maintaining connectivity of mobile networks. IEEE Transactions on Robotics, v. 23, n. 4, p. 812–816, 2007. Dispon´ıvel em: .

Apˆ endice A - Modelagem do Problema Seja G = (V, E) um grafo n˜ao dirigido, em que V ´e o seu conjunto de v´ertices (ou n´os) e E ⊆ (V × V ) ´e o seu conjunto de arestas. Sejam i, j dois n´os de G. Um caminho ´e definido como sendo uma sequˆencia de arestas em E, e dizemos que os n´os i e j est˜ao conectados se G cont´em um caminho entre eles. G est´a conectado se todo par de n´os em V est´a conectado. A vizinhan¸ca Ni de um n´o ´e definida como sendo o conjunto de n´os que se ligam a ele, ou seja, Ni = j  V | (i, j)  E. Um grafo de comunica¸ca˜o G pode ser descrito atrav´es de sua matriz de adjacˆencias A  RN xN , na qual aij representa o peso da aresta entre os n´os i e j. Assim, aij > 0 se j  Ni ou aij = 0, caso contr´ario. Para grafos n˜ao-direcionados, temos que aij = aji . A estrutura de um grafo tamb´em pode ser descrita atrav´es da sua matriz de graus N X D = diag({di }), em que di = aij se i = j, ou 0, caso contr´ario. A matriz laplaciana j=1

(ponderada) de um grafo ´e dada por L = D − A, e a matriz laplaciana n˜ao-ponderada ´e um caso especial de matriz laplaciana em que todas as entradas n˜ao-nulas de L s˜ao iguais a um. Finalmente, L apresenta algumas propriedades not´aveis:

ˆ APENDICE A. MODELAGEM DO PROBLEMA

97

• Sendo 1 um vetor de uns, temos que L.1 = 0; • Sejam λi , i = 1, ... , N, os N autovalores de L. Ent˜ao:

1. λi  R, ∀ i = 1, ..., N. 2. Os autovalores podem ser ordenados de forma que

0 = λ1 ≤ λ2 ≤ . . . ≤ λN

(A.1)

3. λ2 > 0 se e somente se o grafo ´e conectado; ent˜ao, λ2 ´e definido como sendo a conectividade alg´ebrica do grafo. Maiores detalhes podem ser encontrados em (FIEDLER, 1973).

Apˆ endice B - An´ alise dos Erros de Estima¸ c˜ ao

B.1

Erro na Estima¸ c˜ ao de λ2 na presen¸ ca de perturba¸c˜ oes

Proposi¸c˜ ao B.1.1. Seja o sistema de estima¸c˜ao descrito pelas Equa¸c˜oes (3.3) e (2.5). Ent˜ao, o erro de estima¸c˜ao de λ02 ´e limitado. ˆ 0 = [λ10 , . . . , λN 0 ]  Rn o vetor contendo as estimativas de λ2 feitas pelos Prova: Seja λ 2 2 2 agentes na presen¸ca de algum tipo de perturba¸ca˜o. De acordo com a Equa¸ca˜o (3.3) e a partir das estimativas de λ2 feitas por cada um dos agentes na presen¸ca de perturba0 ˆ 0 fica definido da seguinte forma, em que z 0 ´e o vetor contendo as ¸co˜es, dadas por λi2 , λ 2 2


estimativas de Ave {(˜ υ2i )} feitas por todos os agentes:

ˆ 0 = k3 . (1 − z 0 ) λ 2 2 k2

(B.1)

Analogamente ao caso livre de perturba¸c˜oes estudado em (SABATTINI et al., 2012) e assumindo que a norma das perturba¸co˜es existentes no sistema s˜ao limitadas (isto ´e, n˜ao

ˆ ´ ˜ APENDICE B. ANALISE DOS ERROS DE ESTIMAC ¸ AO

99

h´a falha em todas as comunica¸c˜oes e o atraso na comunica¸ca˜o n˜ao ´e infinito), temos que, ˆ 0 || tamb´em o ´e. Dessa forma, a partir da defini¸ca˜o do n´ como ||z20 || ´e limitado, ||λ umero 2 de agentes no grafo de comunica¸ca˜o, o valor real de λ02 fica limitado por uma nova compo0

ca de perturba¸c˜oes no sistema, deteriorando a conectividade nente λM 2 , que atua na presen¸ entre os agentes. Ou seja,

λ02

i h M0 M M0  −λ2 , λ2 − λ2

(B.2)

Temos ent˜ao que:

• λ02 ≤ 0 se o grafo ´e desconectado; 0

M • λ02 = λM se o grafo ´e completo, ou seja, se existe uma aresta entre cada par 2 − λ2

(i, j) de agentes e se a distˆancia d entre eles ´e tal que o peso das arestas aij assume o seu valor m´aximo (em outras palavras, se d = 0 e aij = 1, ∀(i, j)  {1, . . . , N | i 6= j}). 0

Assim, λM umero N qualquer de agentes interagindo. 2 fica bem definido para um n´ Seja δ 0  Rn o vetor contendo os erros de estima¸ca˜o de conectividade na presen¸ca de ˆ 0 k quanto kλ2 .1k s˜ao fun¸co˜es ˆ 0 − λ2 .1. Como tanto kλ perturba¸c˜oes, dado ent˜ao por δ 0 = λ 2 2 ˆ 0 −λ2 .1k ≤ Ξ. Assim, |λi0 −λ2 | ≤ limitadas, podemos concluir que ∃Ξ > 0 tal que kδ 0 k = kλ 2 2 Ξ, ∀i = 1, . . . , N .

ˆ ´ ˜ APENDICE B. ANALISE DOS ERROS DE ESTIMAC ¸ AO

B.2

100

˜ 2 na presen¸ Erro na Estima¸ c˜ ao de λ ca de perturba¸c˜ oes

Proposi¸c˜ ao B.2.1. Dado o sistema de estima¸c˜ao descrito pelas Equa¸c˜oes (2.4), (2.5) e 0

˜ 2 | ´e limitado, ∀i = 1, . . . , N (3.3), podemos afirmar que o erro de estima¸c˜ao |λi2 − λ ˆ 0 = [λ10 , . . . , λN 0 ]  Rn o vetor contendo as estimativas de λ2 feitas pelos Prova: Seja λ 2 2 2 ˜ 2 o segundo menor autovalor de L. agentes na presen¸ca de algum tipo de perturba¸ca˜o e λ De acordo com a Equa¸ca˜o (3.3) e a partir das estimativas de λ2 feitas por cada um dos 0 ˆ 0 fica definido da seguinte forma: agentes na presen¸ca de perturba¸c˜oes, dadas por λi2 , λ 2

ˆ 0 = k3 . (1 − z 0 ) λ 2 2 k2

(B.3)

Analogamente ao caso livre de perturba¸co˜es estudado em (SABATTINI et al., 2012), como ˆ 0 || tamb´em o ´e. Como demonstrado na Proposi¸ca˜o B.1.1, kλ ˆ 0 k ´e ||z20 || ´e limitado, ||λ 2 2 limitado. De (SABATTINI et al., 2012), temos que a norma do vetor de estados υ˜2 do sistema de estima¸ca˜o ´e limitada. Consequentemente, a m´edia das componentes de υ˜2 na   0 presen¸ca de perturba¸co˜es, dada por Ave {(˜ υ2i )} , tamb´em ´e limitada. Seja δ˜00  Rn o vetor contendo os erros de estima¸ca˜o de conectividade para um sistema ˆ 0 − λ0 .1. Como tanto kλ ˆ 0 k quanto na presen¸ca de perturba¸co˜es, dado ent˜ao por δ˜00 = λ 2 2 2 kλ02 .1k =

√

N .λ02 s˜ao limitados, ´e poss´ıvel concluir que ∃Ξ0 > 0 tal que kδ˜00 k ≤ Ξ0 . 0

˜ 2 | ≤ Ξ0 , ∀i = 1, . . . , N . Portanto, |λi2 − λ

Apˆ endice C - V´ıdeos Demonstrativos

C.1

Rela¸c˜ ao dos V´ıdeos das Simula¸ c˜ oes

V´ıdeos demonstrativos de casos t´ıpicos da influˆencia de perturba¸co˜es no AMC estudado neste trabalho podem ser encontrados nos links descritos na Tabela C.1, a seguir. URL

Descri¸c˜ ao

http://goo.gl/PWbwSM

pf alha = 0.2, δ = η = 0 em agentes ideais

http://goo.gl/lbTKoZ

pf alha = 0.2, δ = η = 0 em agentes tipicamente reais

http://goo.gl/hXySJA

pf alha = 0.4, δ = η = 0 em agentes ideais

http://goo.gl/Dh10Es

pf alha = 0.4, δ = η = 0 em agentes tipicamente reais

http://goo.gl/GpxhyN

δ = 5 ms, pf alha = η = 0 em agentes ideais

http://goo.gl/9DGB34

δ = 5 ms, pf alha = η = 0 em agentes tipicamente reais

http://goo.gl/m8MPWA

δ = 10 ms, pf alha = η = 0 em agentes ideais

http://goo.gl/jnawr4

δ = 10 ms, pf alha = η = 0 em agentes tipicamente reais

http://goo.gl/Wz0JKC

η = 0.5, pf alha = δ = 0 em agentes ideais

http://goo.gl/cjX72s

η = 0.5, pf alha = δ = 0 em agentes tipicamente reais

TABELA C.1 – Endere¸co eletrˆonico dos v´ıdeos dos principais casos estudados neste trabalho

Apˆ endice D - Materiais e M´ etodos

D.1

Ambiente de Simula¸ c˜ ao

Os resultados deste trabalho foram obtidos atrav´es da ferramenta Simulink r do ambiente num´erico de computa¸c˜ao e simula¸ca˜o M athworks M atlabr R2013a, em m´aquinas com processadores 2.8 GHz Intel Core i7 e 2.66 GHz Intel Core i7.

D.2

Dom´ınio do problema

Quanto `as vari´aveis do problema, fizemos a divis˜ao de dom´ınio com amostras suficientemente representativas do comportamento do sistema estudado. Na Tabela D.1 temos uma rela¸c˜ao dos dados de dom´ınio n˜ao processados durante as an´alises realizadas para a confec¸c˜ao deste trabalho.

Dado

Dom´ınio n˜ ao estudado

pf ail

0.7 < pf ail ≤ 1.0

δ

2.0 s < δ ≤ 5.0 s

η

η > 5.0

N

N > 10

Nobst

Nobst > 150

tsim

tsim > 10 s

TABELA D.1 – Valores de Dom´ınio do Problema N˜ao-Estudados

FOLHA DE REGISTRO DO DOCUMENTO 1.

˜ CLASSIFICAC ¸ AO/TIPO

TM 5.

2.

DATA

3.

15 de janeiro de 2015

REGISTRO No DCTA/ITA/DM-087/2014

4.

´ No DE PAGINAS

102

T´ITULO E SUBT´ITULO:

An´ alise dos Efeitos de Perturba¸c˜ oes na Manuten¸c˜ao da Conectividade Global de um Sistema de Robˆos 6.

AUTOR(ES):

Vin´ıcius Antonio Battagello 7.

˜ OES)/ ˜ ´ ˜ ˜ OES): ˜ INSTITUIC ¸ AO( ORG AO(S) INTERNO(S)/DIVISAO(

Instituto Tecnol´ ogico de Aeron´ autica. Ciˆencias da Computa¸c˜ao – ITA-PG/EEC-I 8.

PALAVRAS-CHAVE SUGERIDAS PELO AUTOR:

Sistemas Multi-agente; Manuten¸c˜ ao de Conectividade; Controle de Robˆos Multi-cooperativo; Robˆos em Rede; Ve´ıculos e Robˆ os M´ oveis; Perturba¸c˜ ao; Falha; Atraso; Ru´ıdo 9.

˜ PALAVRAS-CHAVE RESULTANTES DE INDEXAC ¸ AO:

Robˆ os; Dinˆ amica de Robˆ os; Controle Adaptativo; Sistemas de Computadores Embarcados; Redes de Comunica¸c˜ ao; Rob´ otica; Transmiss˜ ao de Dados; Engenharia de Computa¸c˜ao; Engenharia Eletrˆonica 10. ˜ APRESENTAC ¸ AO: (X) Nacional ( ) Internacional ITA, S˜ ao Jos´e dos Campos. Curso de Mestrado. Programa de P´os-Gradua¸c˜ao em Engenharia Eletrˆonica e ´ Computa¸c˜ ao. Area de Inform´ atica. Orientador: Prof. Dr. Carlos Henrique Costa Ribeiro.Defesa em 04 de Dezembro de 2014. Publicada em 2014. 11.

RESUMO:

Para desempenhar tarefas cooperativas de maneira descentralizada, exige-se que sistemas multi-robˆ o comuniquem-se entre si. Portanto, manter a conectividade do grafo de comunica¸c˜ao ´e uma quest˜ao fundamental. Neste trabalho, n´ os analisamos o efeito de diferentes tipos de perturba¸c˜ao na estrat´egia de controle para manuten¸ca˜o de conectividade descrita em (SABATTINI et al., 2012), avaliando o impacto de falha, atraso e ru´ıdo na comunica¸c˜ ao entre os agentes. Os resultados mostram que a estrat´egia para garantir a conectividade nem sempre ´e resiliente aos efeitos negativos de tais perturba¸c˜oes em configura¸c˜oes realistas que consideram um limite de banda para o esfor¸co de controle. Contudo, caracter´ısticas inerciais inerentes da maioria dos sistemas aqu´ aticos e terrestres abrem perspectiva de aplica¸c˜ao da estrat´egia de manuten¸c˜ao de conectividade a sistemas adaptativos que consideram, por exemplo, adapta¸c˜ao autˆonoma a restri¸c˜oes outras al´em da pr´ opria conectividade, como eficiˆencia na comunica¸ca˜o ou capta¸c˜ao de energia.

12.

GRAU DE SIGILO:

(X) OSTENSIVO

( ) RESERVADO

( ) CONFIDENCIAL

( ) SECRETO