PROPOSTA DE MODELO DE VEÍCULOS AÉREOS NÃO … · Operações de Busca e Salvamento. Algoritmos de navegação. ABSTRACT There are an increasing number of researches into UAV (Unmanned

ÁQUILA NEVES CHAVES

PROPOSTA DE MODELO DE VEÍCULOS AÉREOS NÃO TRIPULADOS (VANTS) COOPERATIVOS APLICADOS A

OPERAÇÕES DE BUSCA

São Paulo 2013



OPERAÇÕES DE BUSCA Dissertação de mestrado apresentada à Escola Politécnica da Universidade de São Paulo para obtenção do título de Mestre em Ciências

São Paulo 2013



OPERAÇÕES DE BUSCA Dissertação de mestrado apresentada à Escola Politécnica da Universidade de São Paulo para obtenção do título de Mestre em Ciências Área de Concentração: Sistemas Digitais Orientador: Prof. Dr. Paulo Sérgio Cugnasca

São Paulo 2013

Este exemplar foi revisado e alterado em relação à versão original, sob

responsabilidade única do autor e com a anuência de seu orientador.

São Paulo, de janeiro de 2013.

Assinatura do autor ____________________________

Assinatura do orientador _______________________

FICHA CATALOGRÁFICA

Chaves, Áquila Neves

Proposta de modelo de veículos aéreos não tripulados

(VANTs) cooperativos aplicados a operações de busca / A.N.

Chaves. – ed.rev. -- São Paulo, 2013.

147 p.

Dissertação (Mestrado) - Escola Politécnica da Universidade

de São Paulo. Departamento de Engenharia de Computação e

Sistemas Digitais.

1. Aeronaves não tripuladas 2. Sistemas multiagentes

3. Busca e resgate 4. Salvamento marítimo 5. Algoritmos 6. Na-

vegação aérea I. Universidade de São Paulo. Escola Politécnica.

Departamento de Engenharia de Computação e Sistemas Digi-

tais II. t.

AGRADECIMENTOS

Primeiramente agradeço aos meus pais, João e Célia, que foram os grandes

incentivadores do estudo na minha vida. Sem eles, este trabalho não seria sequer

iniciado. Serei eternamente grato pelo esforço empreendido por eles na educação

de seus filhos (minhas irmãs e eu).

Agradeço também, em especial, ao Prof. Dr. Paulo Sérgio Cugnasca, que

dedicou parte de seu tempo e atenção ao longo deste trabalho, e que além de

orientador, foi um grande amigo nessa jornada. Não só em questões acadêmicas,

mas muitos foram os assuntos discutidos nos finais de tarde durante os últimos

dezenove meses. Espero ter correspondido às expectativas.

Também não poderia deixar de agradecer aos colegas (engenheiros,

pesquisadores, mestrandos e doutorandos) do Grupo de Análise de Segurança

(GAS), ao qual fui muito bem recebido em fevereiro de 2011, pelas inúmeras

conversas e trocas de informações sobre os mais variados assuntos ao longo desta

pesquisa. Meu sentimento é de agradecimento e de admiração por todos.

Durante este período, alguns professores também foram muito importantes à

pesquisa desenvolvida. Agradeço imensamente a todos eles: ao Prof. Dr. João

Batista Camargo Jr., chefe do GAS, pelo acolhimento e suporte prestado; ao Prof.

Dr. João Rady, também professor do GAS, pela valiosa contribuição como membro

da banca do exame de qualificação; à Profa. Dra. Anarosa Brandão, pelas

orientações durante a pesquisa e também pela valiosa contribuição como membro

da banca do exame de qualificação; ao Prof. Dr. João José Neto, pelas conversas,

sugestões e pela participação conjunta em um dos artigos submetidos; à Profa. Dra.

Linda Lee Ho, pela atenção e orientação sobre as questões estatísticas da

simulação.

Tenho que registrar também meus agradecimentos e admiração ao Prof. Dr.

José Sidnei Martini, ao Prof. Dr. Marcos Rodrigues e ao Jorge Lopes, com os quais

pude contar com grande auxílio e orientação no início da minha carreira profissional,

me incentivando a iniciar esta jornada acadêmica, e que, indiretamente, também

contribuíram com esse trabalho de mestrado.

Por fim, agradeço os apoios financeiros recebidos. Ao Conselho Nacional de

Desenvolvimento Científico e Tecnológico (CNPq), pelo auxílio recebido na forma de

concessão de bolsa de mestrado. À Fundação para o Desenvolvimento Tecnológico

da Engenharia (FDTE), pelo auxílio recebido na forma de bolsa de mestrado antes

da vigência da bolsa CNPq e pelo auxílio financeiro na participação de eventos

acadêmicos. E ao Programa de Pós-Graduação em Engenharia Elétrica da Escola

Politécnica da Universidade de São Paulo (PPGEE/EPUSP), que além do apoio

institucional, pude contar com auxílio financeiro em participações em eventos

acadêmicos.

RESUMO

Os Veículos Aéreos Não Tripulados (VANTs) são ideais para operações de risco e

estressante para o ser humano – são as chamadas dull, dirty and dangerous

missions. Portanto, uma importante aplicação desse tipo de robô aéreo diz respeito

a operações de busca envolvendo múltiplos VANTs cooperativos, em que há risco

de colisões entre aeronaves e o tempo de um voo é limitado, entre outros fatores,

pela capacidade de um piloto trabalhar sem descanso. Entretanto, apesar de

atualmente verificar-se um crescente número de pesquisas envolvendo VANTs e do

grande potencial existente na utilização de VANTs, operações de busca

cooperativas ainda não estão ocorrendo. Esse assunto é uma área de estudo

multidisciplinar e nascente, que possui diversas linhas de pesquisa. Diferentes

algoritmos de navegação e padrões de busca foram estudados visando selecionar

o(s) mais adequado(s). Além disso, apresenta-se, neste trabalho, uma visão geral

sobre os mecanismos de coordenação multiagente e avalia a adequação de cada

uma delas à coordenação distribuída de agentes (VANTs), visando cooperação.

Assim, com o objetivo de melhorar o desempenho de uma operação de busca, esta

pesquisa de mestrado propõe um modelo de VANTs cooperativos que combina

mecanismos de coordenação multiagente, algoritmos de navegação e padrões de

busca estabelecidos pelos principais órgãos responsáveis pelas operações de busca

e salvamento. Visando avaliar a sensibilidade do percentual médio de detecção de

objetos, bem como o tempo médio de busca, foi desenvolvido um simulador e

milhares de simulações foram realizadas. Observou-se que, utilizando o modelo,

VANTs cooperativos podem reduzir, em média, 57% do tempo de busca

(comparando com uma busca de dois VANTs não cooperativos no mesmo cenário),

mantendo a probabilidade média de detecção dos objetos próxima de 100% e

sobrevoando apenas 30% do espaço de busca.

Palavras-chave: Veículos Aéreos Não Tripulados. VANTs cooperativos. Sistemas

multiagentes. Operações de Busca e Salvamento. Algoritmos de navegação.

ABSTRACT

There are an increasing number of researches into UAV (Unmanned Aerial Vehicle)

in the literature. These robots are quite suitable to dull, dirty and dangerous missions.

Thus, an important application of these vehicles is the search operations involving

multiple UAVs – in which there is risk of collisions among aircrafts and the flight time

is limited by the maximum time of pilot working hours. However, despite the huge

potential use of the UAVs, cooperative search operations with this kind of flying

robots are not yet occurring. This research topic is a new and multidisciplinary area of

study in its beginning and there are several issues that can be studied, such as

centralized versus decentralized control, path planning for cooperative flights, agent

reasoning for UAV tactical planning, safety assessments, reliability in automatic

target reconnaissance by cameras, agent coordination mechanisms applied to UAV

cooperation and the application itself. Different path planning algorithms were studied

aiming to attain the most suitable to these kinds of operations, and the conclusions

are presented. In addition, official documents of Search and Rescue operations are

also studied in order to know the best practices already established for this kind of

operations, and, finally, an overview of the coordination multi-agent theory is

presented and evaluated to achieve the UAV coordination. This work proposes a

model that combines path planning algorithms, search patterns and multi-agent

coordination techniques to obtain a cooperative UAV model. The great goal for

cooperative UAV is to achieve such performance that the performance of the group

overcomes the sum of the individual performances isolatedly. Then, aiming to

analyze the average percentage of objects detection, and the average search time, a

simulator was developed and thousands of simulations were run. It was observed

that, using the proposed model, two cooperative UAVs can perform a search

operation 57% faster than two non cooperative UAVs, keeping the average

probability of objects detection approaching at 100% and flying only 30% of the

search space.

Keywords: Unmanned Aerial Vehicle. Cooperative UAV. Multi-agent Systems.

Search and Rescue. SAR operations. Path planning algorithms.

LISTA DE ILUSTRAÇÕES

Figura 1 – Área de responsabilidade da Aeronáutica Brasileira referente a operações

de busca e salvamento. Fonte: (DECEA, 2010a) ...................................................... 19

Figura 2 – Comunicação do Global Hawk com a estação base [adaptado de

Billingsley (2006)] ...................................................................................................... 27

Figura 3 – Níveis de autonomia em VANTs. Adaptado de (DOD, 2005) ................... 33

Figura 4 – Recomendações da OACI para operações de busca tripulada ................ 40

Figura 5 – Divisões de áreas marítimas para operações SAR [Adaptado de

(ROBITAILLE, 1999)]. ............................................................................................... 42

Figura 6 – Distribuição normal de três dimensões .................................................... 46

Figura 7 – Arquitetura geral de um VANT. Fonte: (CHAVES e CUGNASCA, 2011) . 51

Figura 8 – Pseudocódigo do algoritmo A* [Adaptado de (LESTER, 2005)] ............... 61

Figura 9 – Busca local inspirada no padrão “Pente” [adaptado de (RUBIO,

VAGNERS e RYSDYK, 2004)]. ................................................................................. 63

Figura 10 – Ilustração do processo de busca local utilizando a metáfora do

aquecimento global para procurar máximos locais. .................................................. 67

Figura 11 – Convergência de conceitos para a construção do modelo de VANTs

cooperativos .............................................................................................................. 69

Figura 12 – Espaço de busca discretizado e atualização do conhecimento do VANT

(CHAVES e CUGNASCA, 2012a) ............................................................................. 71

Figura 13 – Cálculo do tamanho da célula do espaço discretizado ( é a amplitude

da visão da câmera; ; é a altitude de voo; e é o raio do círculo de

observação da câmera). ............................................................................................ 75

Figura 14 – Modelo de navegação ............................................................................ 76

Figura 15 – Focalização da câmera na célula durante a navegação ........................ 77

Figura 16 – Exemplo do cenário de busca. Fonte: (CHAVES, CUGNASCA e NETO,

2012) ......................................................................................................................... 79

Figura 17 – Arquitetura de implementação do modelo .............................................. 81

Figura 18 – Planejamento inicial da busca cooperativa. Os pontos vermelhos

representam os objetos perdidos, alvos da operação de busca................................ 83

Figura 19 – Primeira detecção .................................................................................. 84

Figura 20 – Planejamento Multiagente no cálculo da trajetória utilizando o algoritmo

A*. As linhas tracejadas representam a trajetória planejada dos VANTs. ................. 86

Figura 21 – Início do planejamento da busca local ................................................... 87

Figura 22 – Pseudocódigo da implementação da busca local................................... 88

Figura 23 – Emprego do mecanismo de coordenação Planejamento Multiagente na

busca local. ............................................................................................................... 89

Figura 24 – Variação do espaçamento no padrão de busca “Rotas Paralelas”

(CHAVES e CUGNASCA, 2012b) ............................................................................. 95

Figura 25 – Análise gráfica para obtenção do número de simulações necessárias

com a evolução da média do número de células navegadas até a detecção de todos

os objetos. ................................................................................................................. 96

Figura 26 – Ilustração dos espaçamentos S=1 e S=2 ............................................. 100

Figura 27 – Porcentagem média de objetos detectados pela variação do

espaçamento do padrão de busca Rotas Paralelas, utilizando uma aeronave não

cooperativa .............................................................................................................. 101

Figura 28 – Porcentagem média de objetos detectados pela variação do

espaçamento do padrão de busca Rotas Paralelas, utilizando duas aeronaves não

cooperativas. ........................................................................................................... 102

Figura 29 – Porcentagem média de objetos encontrados pela variação do

espaçamento (S) ..................................................................................................... 103

Figura 30 – Porcentagem de células navegadas do cenário pela variação do

espaçamento (S) ..................................................................................................... 104

Figura 31 – Porcentagem de células navegadas pela variação do espaçamento (S)

com distinção de fases. Barras azuis: fase de varredura inicial; barras vermelhas:

fase de deslocamento ponto-a-ponto; barras verdes: fase de busca local. ............. 105

Figura 32 – Instante final da operação de busca. (a) Utilizando espaçamento S=1; (b)

Utilizando espaçamento S=3. .................................................................................. 106

Figura 33 – Melhor parametrização do espaçamento. ............................................ 107

Figura 34 – Ilustração do cenário 1 (figura a) e do cenário 2 (figura b) ................... 108

Figura 35 – Variação no tempo de busca (linha azul) e variação na porcentagem

média do número de objetos detectados (linha vermelha), ambos pela variação do

espaçamento (S) ..................................................................................................... 110

Figura 36 – Influência do raio de atualização do conhecimento (a) e ilustração de

uma busca com uma única detecção (b). [Adaptado de Chaves e Cugnasca (2012b)]

................................................................................................................................ 111

Figura 37 – Análise da variação do raio de atualização do conhecimento (R) ........ 112

Figura 38 – Análise de sensibilidade para o número de objetos (eixos horizontais das

figuras). Nos eixos verticais: as barras azuis apresentam a média de células

percorridas; as linhas vermelhas, a média de objetos detectados .......................... 114

Figura 39 – Variação do espalhamento dos objetos. (a) Utilizando desvio-padrão de

; (b) de ; e (c) de . ..................... 116

Figura 40 – Análise de sensibilidade do espalhamento dos objetos. Os eixos

horizontais representam a variação do desvio padrão utilizado na distribuição

gaussiana; as barras azuis, a média de células percorridas; as linhas vermelhas, a

média de objetos detectados. .................................................................................. 117

Figura 41 – População versus Amostra .................................................................. 139

Figura 42 – Histograma. O eixo x apresenta as medidas observadas do tempo de

busca e o eixo y apresenta as frequências observadas nos intervalos ilustrados no

gráfico. .................................................................................................................... 142

Figura 43 – Mesmo histograma da Figura 42, mas com a função de densidade

traçada com maior granularidade (também utilizando o software estatístico R). .... 143

LISTA DE TABELAS

Tabela 1 – Padrões de busca obtidos nos manuais de referência (IMO/ICAO, 2003;

DECEA, 2009). [Figuras adaptadas de (DECEA, 2009)]. .......................................... 43

Tabela 2 – Análises pretendidas ............................................................................... 94

Tabela 3 – Tempos de busca dos cenário 1 e 2 ...................................................... 109

Tabela 4 – Comparação do tempo de busca de uma busca cooperativa com uma

não cooperativa ....................................................................................................... 109

Tabela 5 – Síntese de observações sobre a sensibilidade dos parâmetros ............ 121

Tabela 6 – Distribuição Normal. Valores de . .................................... 146

Tabela 7 – Distribuições t de Student. Valores de onde . .... 147

LISTA DE ABREVIATURAS E SIGLAS

AGL Above Ground Level

AMSL Above Mean Sea Level

AOP Agent-Oriented Programming

API Application Program Interface

ARCC Aeronautical Rescue Coordination Centre

CACI Convenção de Aviação Civil Internacional

CAMPOUT Control Architecture for Multi-robot Planetary OUTpost

CAS Collision Avoidance Systems

CDPS Cooperative Distributed Problem Solving

CINDACTA Centro Integrado de Defesa Aérea e Controle de Tráfego Aéreo

CNP Contract Net Protocol

CxBR Context Based Reasoning

DAI Distributed Artificial Intelligence

DECEA DEpartamento de Controle do Espaço Aéreo

DoD Department of Defense

D-SAR Divisão de Busca e Salvamento

FAB Força Aérea Brasileira

FINEP Financiadora de Estudos e Projetos

FIPA The Foundation of Intelligent Physical Agents

FIPA ACL FIPA Agent Communication Language

FVF Fuzzy Virtual Force

IAMSAR International Aeronautical and Maritime Search and Rescue manual

ICAO International Civil Aviation Organization

IMO International Maritime Organization

J-UCAS Joint Unmanned Combat Air Systems

LGPL Lesser General Public License

LHC Local Hill Climbing

LKP Last Known Position

MAS Multi-Agent System

MCT Ministério da Ciência e Tecnologia

MISUS Multi-rover Integrated Science Understanding System

OACI Organização de Aviação Civil Internacional

OASIS Optimal Aircraft Sequencing using Intelligent Scheduling

OGM Occupancy Grid Map

OMI Organização Marítima Internacional

P&D Pesquisa e Desenvolvimento

P,D&I Pesquisa, Desenvolvimento e Inovação

PDA Personal Digital Assistant

POC Probabilidade de Contenção

POD Probabilidade de Detecção

POS Probabilidade de Sucesso

RCC Rescue Coordination Center

SAR Search and Rescue

SISSAR Sistema de Busca e Salvamento Aeronáutico

SMC Search and Rescue (SAR) Mission Co-ordinator

SRR Região de Busca e Salvamento (Search and Rescue Region)

SRU Search and Rescue Unit

STOL Short Take-Off and Landing

UAS Unmanned Aircraft System

UAV Unmanned Aerial Vehicle

UCAR Unmanned Combat Armed Rotorcraft

UGV Unmanned Ground Vehicles

USV Unmanned Surface Vehicle

UUV Unmanned Underwater Vehicles

VANT Veículo Aéreo Não Tripulado

VSNT Veículos Submersíveis Não Tripulados

VTNT Veículos Terrestres Não Tripulados

VTOL Vertical Take-Off and Landing

WiSAR Wilderness Search And Rescue

SUMÁRIO

1 INTRODUÇÃO ................................................................................................... 16

1.1 Objetivo ........................................................................................................ 17

1.2 Motivação ..................................................................................................... 18

1.3 Justificativa ................................................................................................... 21

1.4 Organização ................................................................................................. 23

2 VEÍCULOS AÉREOS NÃO TRIPULADOS ......................................................... 25

2.1 Histórico ....................................................................................................... 27

2.2 Tendências ................................................................................................... 29

2.3 VANTs Cooperativos .................................................................................... 31

2.4 Considerações finais do capítulo ................................................................. 37

3 OPERAÇÃO DE BUSCA E SALVAMENTO ....................................................... 38

3.1 SAR no Brasil ............................................................................................... 40

3.2 SAR no mundo ............................................................................................. 41

3.3 Padrões de Busca ........................................................................................ 43

3.4 Modelo matemático de acidentes em alto mar ............................................. 45


4 TEORIA MULTIAGENTE PARA VANTs COOPERATIVOS ............................... 48

4.1 Agente .......................................................................................................... 49

4.2 Cooperação versus Coordenação ................................................................ 51

4.2.1 Organização estrutural .......................................................................... 53

4.2.2 Acordos bilaterais (contracting) ............................................................. 53

4.2.3 Compartilhamento de informações ........................................................ 55

4.2.4 Planejamento multiagente ..................................................................... 55

4.2.5 Negociação ............................................................................................ 56


5 ALGORITMOS DE NAVEGAÇÃO ...................................................................... 58

5.1 Algoritmos de navegação ponto-a-ponto ...................................................... 59

5.2 Algoritmos de busca local ............................................................................ 63


6 PROPOSTA ....................................................................................................... 69

6.1 Discretização da região de busca ................................................................ 70

6.2 Modelagem da navegação ........................................................................... 75

6.3 Definição do cenário..................................................................................... 78

6.4 Busca cooperativa ........................................................................................ 80

6.4.1 Varredura inicial ..................................................................................... 82

6.4.2 Primeira pista encontrada ...................................................................... 83

6.4.3 Busca local ............................................................................................ 87


7 SIMULAÇÕES .................................................................................................... 91

7.1 Cenários simulados ...................................................................................... 93

7.2 Análise estatística ........................................................................................ 95


8 ANÁLISE DOS RESULTADOS .......................................................................... 99

8.1 Cenário 1 – um VANT não cooperativo ........................................................ 99

8.2 Cenário 2 – dois VANTs não cooperativos ................................................. 101

8.3 Cenário 3 – variação do espaçamento (S) ................................................. 102

8.3.1 Comparação dos cenários 1, 2 e 3 ...................................................... 108

8.4 Cenário 4 – variação do raio de atualização do conhecimento (R) ............ 110

8.5 Cenário 5 – variação do número de objetos (n) ......................................... 113

8.6 Cenário 6 – variação do espalhamento dos objetos ( ) ............................. 115

9 CONCLUSÕES E CONSIDERAÇÕES FINAIS ................................................ 119

9.1 Conclusão .................................................................................................. 120

9.2 Trabalhos futuros ....................................................................................... 122

9.3 Considerações finais .................................................................................. 124

REFERÊNCIAS ....................................................................................................... 125

GLOSSÁRIO ........................................................................................................... 137

APÊNDICE A – Estimação de parâmetros .............................................................. 139

16

1 INTRODUÇÃO

Com o progresso tecnológico observado na aviação, a utilização dos Veículos

Aéreos Não Tripulados (VANTs) em diversas aplicações já é uma realidade. Apesar

de, historicamente, os VANTs terem sido empregados principalmente em operações

de guerra (CORRÊA, 2008) – como, por exemplo, missões de reconhecimento –,

existe uma grande demanda para o emprego de VANTs também em aplicações

civis. No primeiro semestre de 2011, uma empresa brasileira anunciou operações de

monitoramento de gasodutos utilizando um dirigível não tripulado (PETROBRÁS,

2011); e, também no Brasil, VANTs já estão sendo utilizados em operações de

vigilância de fronteiras e monitoramento em geral, tais como em usinas hidrelétrica e

em grandes eventos (MORAES, 2011; GALANTE, 2011).

Esses robôs são ideais em operações de longa duração (que expõem a

tripulação à fadiga extrema) ou quando há risco para o piloto (tanto para a saúde

quanto risco de morte) – são as chamadas dull1, dirty2 and dangerous3 missions.

Como exemplo de uma operação de risco para a saúde do piloto, pode-se citar

sobrevoos em áreas radioativas. Já sobrevoos em baixa altitude, principalmente

durante a noite, é um exemplo de operações em que há risco maior de acidente e,

consequentemente, expõem a vida do piloto a uma situação de risco.

Logo, uma importante aplicação desses veículos diz respeito às operações de

busca envolvendo múltiplos VANTs (WAHARTE e TRIGONI, 2010; GAN e

SUKKARIEH, 2011; DOHERTY e RUDOL, 2007; HOME LAND SECURITY

NEWSWIRE, 2010). Em operações dessa natureza, os VANTs podem sobrevoar

ininterruptamente uma determinada área por muito mais tempo do que uma

aeronave tripulada, pois não há a necessidade de descanso e, por ser mais leve, há

menor consumo de combustível, aumentando, por conseguinte, a autonomia de voo.

Além disso, o barateamento das tecnologias de controle e de comunicação torna a

utilização de VANTs viável e bastante atrativa, fazendo com que o voo tripulado não

seja a única escolha.

1 Operações que requerem mais que 30 ou 40 horas. Além de desgastar a tripulação ao extremo, a

fadiga da tripulação pode comprometer o sucesso da missão. 2 Envolve risco para a saúde do piloto. Por exemplo, sobrevoar áreas radioativas.

3 Envolve risco de morte para o piloto. Por exemplo, reconhecimento de território inimigo.

17

De acordo com Cox et al. (2004), as aplicações civis dos VANTs se dividem

em quatro categorias: gestão do uso da terra, uso comercial, estudos científicos e

segurança do território. A gestão do uso da terra engloba mapeamento, agricultura,

controle de queimadas, etc. A utilização comercial corresponde à utilização de

VANTs para, por exemplo, transporte de cargas. A utilização de VANT em estudos

científicos pode ser realizada, a título ilustrativo, para sensoriamento remoto,

estudos climáticos ou em situações em que agilidade e discrição na observação de

grupos de animais são necessárias (PAZMANY, 2011). Por fim, a segurança do

território nacional envolve tanto o patrulhamento quanto operações de emergência –

nas quais se situam as operações de busca e salvamento, contexto em que esta

pesquisa de mestrado está presente. Cabe ressaltar que no Brasil as operações de

busca e salvamento estão sob a alçada militar, mais especificamente sob a Divisão

de Busca e Salvamento (D-SAR) do Departamento de Controle do Espaço Aéreo

(DECEA).

No entanto, além de apresentarem muita relevância para as missões de

busca e salvamento, as operações de busca (fase principal nas operações de busca

e salvamento) podem ser generalizadas para outras situações, tais como: vigilância

ambiental (extração ilegal de madeira e busca por focos de incêndio, por exemplo),

combate ao narcotráfico (como buscas de pistas de pousos ilegais), entre outras.

As subseções a seguir apresentam, nesta ordem, o objetivo da pesquisa, a

motivação, a justificativa e a organização do trabalho.

1.1 Objetivo

O objetivo deste trabalho é propor um modelo de VANTs cooperativos para

uma missão de busca. Espera-se que o desempenho do grupo cooperativo seja

melhor do que o desempenho de um grupo não cooperativo com o mesmo número

de indivíduos. Para isso, visando aumentar a eficiência do grupo de VANTs, buscar-

se-á dotar cada um dos VANTs de capacidade de coordenação e planejamento.

18

Assim, atuando de forma autônoma e descentralizada, cada VANT é

responsável por tomar suas próprias decisões levando em conta o objetivo global da

missão e as ações dos outros VANTs.

Para atingir esse objetivo precípuo, propõe-se um levantamento de algoritmos

de navegação para VANTs, bem como as melhores práticas de busca estabelecidas

pelo DECEA, e de técnicas de coordenação multiagentes, que serão combinados,

de forma a construir um modelo de VANTs cooperativos.

1.2 Motivação

O Brasil – Estado contratante da Organização de Aviação Civil Internacional

(OACI) 4 – é signatário da Convenção de Aviação Civil Internacional (CACI)

(MINISTÉRIO DAS RELAÇÕES EXTERIORES, 1944; MINISTÉRIO DA RELAÇÕES

EXTERIORES, 2011). Desde a assinatura desse tratado, em 1944, o país passou a

adotar as diretrizes emanadas por essa entidade, incluindo a organização de um

serviço de Busca e Salvamento no país.

A Região de Busca e Salvamento (SRR5) no Brasil compreende uma área de

22 milhões de quilômetros quadrados (km2) subdividida em cinco Centros de

Coordenação de Salvamento Aeronáuticos (ARCC6) – Figura 1. Observa-se que,

aproximadamente metade dessa área corresponde a áreas marítimas – cenário em

que a utilização de aeronaves, para a realização de buscas na superfície, é mais

adequada que a utilização de veículos aquáticos. Logo, a responsabilidade

assumida pelo país de prestação de serviço de Busca e Salvamento é uma tarefa

que demanda enorme quantidade de recursos e capacidade de gerenciamento

(DECEA, 2010b).

4 Também conhecida pela sigla em inglês: International Civil Aviation Organization (ICAO)

5 Sigla do termo em inglês Search and Rescue Region

6 Em inglês, Aeronautical Rescue Coordination Centre. O sufixo faz referência à região e ao Centro

Integrado de Defesa Aérea e Controle de Tráfego Aéreo (CINDACTA) responsável.

19

Figura 1 – Área de responsabilidade da Aeronáutica Brasileira referente a operações de busca e

salvamento. Fonte: (DECEA, 2010a)

Para exemplificar a dimensão do tamanho de uma operação de busca e

salvamento, pode-se citar o caso da operação de busca de passageiros e tripulantes

do voo 447 da Air France que caiu no oceano Atlântico em 2009 – a maior e mais

complexa operação de Busca e Salvamento realizada na história brasileira

(CENTRO DE COMUNICAÇÃO SOCIAL DA MARINHA, 2009). No dia 31 de maio

desse ano, uma aeronave desapareceu quando voava na rota Rio de Janeiro –

Paris. Após seu desaparecimento, foram realizadas buscas que perduraram até o

dia 26 de junho de 2009. As buscas se encerraram pelo motivo de que não era mais

possível encontrar sobreviventes (objetivo primordial da operação), dado o tempo

decorrido desde o acidente.

Nesses 26 dias, foram resgatados 51 corpos, mais de 600 partes e

componentes estruturais da aeronave, bem como bagagens e outros objetos. A

Força Aérea Brasileira (FAB) utilizou doze aeronaves e contou com o apoio de

aviões da França, dos EUA e da Espanha. Cerca de 1500 horas de voo foram

empregadas em buscas visuais numa área correspondente a 350 mil quilômetros

20

quadrados7 . Um avião R-99, por sua vez, realizou busca eletrônica numa área

correspondente a dois milhões de quilômetros quadrados8 . A Marinha do Brasil

utilizou onze navios em revezamento, totalizando 35 mil milhas navegadas9. Ao todo,

a operação envolveu mais de 1.600 profissionais nas tarefas de busca, resgate e

suporte a essas atividades, sendo 1.344 militares da Marinha do Brasil (CENTRO

DE COMUNICAÇÃO SOCIAL DA MARINHA, 2009).

Cabe registrar que, após o encerramento das buscas, os meios navais

dedicados a captar emissões das caixas de dados e voz da aeronave acidentada

permaneceram na área de buscas sob a coordenação da França. Apenas quase

dois anos depois, no dia 1º de maio de 2011, a unidade de memória do gravador de

dados de voo (caixa preta) foi encontrada (BEA E CECOMSAER, 2011). A

localização da caixa preta ocorreu graças às buscas realizadas pelo robô Remora

6000 (PHOENIX INTERNATIONAL HOLDINGS, INC., 2011), que já no seu primeiro

mergulho encontrou o chassi da caixa preta. Verifica-se, portanto, a relevância dos

veículos não tripulados (não só os aéreos) em operações dessa natureza.

Nesse contexto, a utilização de VANTs cooperativos pode contribuir com,

além do aumento da eficiência das buscas (reduzindo o tempo de busca), o

barateamento do custo de uma operação de busca. Segundo o Ministério da Justiça,

o custo de uma hora de voo de um VANT equivale a aproximadamente 8% do custo

de uma aeronave tripulada10 (PORTAL DA COPA, 2011). Esse número pode chegar

a até 5% para aeronaves não tripuladas de asas rotativas (SILVEIRA, 2010). Uma

das principais razões para essa redução do custo é a redução do peso, pois um

VANT dispensa, por exemplo, mecanismos de segurança e ergonomia para o

piloto 11 . Consequentemente, com um peso total menor, a aeronave reduz

drasticamente o consumo de combustível. Além disso, com peso menor, é possível

carregar mais combustível do que uma aeronave tripulada. O engenheiro Roberto

7 Equivalente a três vezes a área do estado de Pernambuco.

8 Equivalente a oito vezes a dimensão do estado de São Paulo.

9 Equivalente a oito vezes a extensão da costa brasileira.

10 Comparação realizada entre um VANT de grande porte e uma aeronave tripulada também de

grande porte. 11

Por exemplo, rádio para comunicação por voz, cadeira ejetável, cabine do piloto, sistema de pressurização, etc.

21

Ferraz12 aponta que o consumo de combustível de um VANT chega a ser sessenta

vezes menor do que o consumo de uma aeronave tripulada de mesmo porte.

Ademais, a chance de sobrevivência das vítimas não fatais de um acidente

aéreo, ou mesmo de pessoas perdidas em regiões de montanha (muitas vezes

inóspitas), reduz-se com o passar do tempo. Sendo assim, qualquer esforço para

reduzir o tempo de busca estará contribuindo para aumentar a chance de

sobrevivência dessas vítimas e, indiretamente, para aumentar a segurança do

sistema de transporte aéreo do país, bem como de seus usuários.

Por fim, um fato que atesta a relevância para o país da pesquisa sobre

VANTs colaborativos foi o lançamento de uma chamada pública, em 2009, pela

Financiadora de Estudos e Projetos (FINEP) – empresa pública vinculada ao

Ministério da Ciência e Tecnologia (MCT) –, que disponibilizou nove milhões de reais

não reembolsáveis para fomento de tecnologia de VANTs na forma de apoio

financeiro. Essa chamada objetivou selecionar propostas de projetos de P,D&I

(Pesquisa, Desenvolvimento e Inovação) em veículos aéreos não tripulados e em

tecnologias acessórias. As empresas interessadas deveriam ter aplicações em áreas

tais como: segurança pública, defesa, controle de fronteiras, meteorologia,

agricultura, bem como monitoramento de queimadas, poluição e degradação

ambiental. Um dos tipos de projetos objeto de apoio foi: “sistemas que permitam o

voo colaborativo de múltiplos veículos [...] possibilitando maior autonomia em

missões conjuntas” (FINEP, 2009, grifo nosso). Logo, além do aspecto humanitário

envolvido, a utilização de VANTs cooperativos é de grande relevância nacional e se

insere nesse cenário de modo estratégico.

1.3 Justificativa

Em favor da utilização de VANTs em operações de busca, o Manual

Internacional de Busca e Salvamento (IMO/ICAO, 2003) aponta que mais de uma

aeronave tripulada não deve fazer buscas na mesma subárea, pois essa situação

12

Engenheiro de uma das mais promissoras empresas fabricantes de VANTs do país, localizada no Centro de Inovação, Empreendedorismo e Tecnologia (CIETEC).

22

gera um estado de alerta prejudicial ao sucesso da operação, fazendo com que a

tripulação tenha a sua atenção desviada das buscas visuais para a navegação e

coordenação com outras aeronaves. Portanto, nesse contexto, a utilização de

VANTs em operações de busca envolvendo múltiplas aeronaves é oportuna.

Sobre as operações de buscas, estas representam a fase mais importante

das operações de busca e salvamento (DECEA, 2009), mais conhecidas na

literatura pela sigla SAR (em inglês, search and rescue). Nesse contexto, a pesquisa

da teoria multiagente e de algoritmos de navegação provê, além de otimização da

operação de busca, coordenação e autonomia ao grupo de VANTs. Ademais, a

abordagem multiagente possui grande atratividade quando se busca estudar

maneiras de agregar e coordenar um grupo de agentes, representados pelos

VANTs, para atingir um objetivo em comum (REN e CAO, 2011).

Vale ressaltar, também, que adaptatividade, escalabilidade, flexibilidade e

robustez são características desejáveis em operações envolvendo VANTs

cooperativos, já que é conveniente que falhas individuais não devem afetar o

cumprimento da missão. Para atender essas demandas, deve-se fazer uso de

algoritmos distribuídos que se apoiem em interações locais para obter determinado

comportamento global (REN e CAO, 2011; PECHOUCEK e SISLAK, 2009). Sendo

assim, o estudo da teoria multiagente, visando dotar os VANTs de autonomia e

capacidade de coordenação e cooperação, também colabora nesse sentido. Mais

detalhes e esse respeito são apresentados no capítulo 4.

Outro aspecto importante do trabalho é o levantamento de algoritmos de

navegação e padrões de busca, que serão responsáveis por planejar a ação a ser

tomada na forma de uma sequência de pontos a sobrevoar.

Conforme assinala o Manual de Busca e Salvamento do Comando da

Aeronáutica (DECEA, 2009), cada cenário exige uma estratégia de busca

diferenciada, que seja mais adequada a cada situação. Portanto, uma proposta que

vise à otimização da busca de qualquer (ou quaisquer) alvo(s), por um grupo de

VANTs, deve considerar também, pelo menos no cenário brasileiro, a utilização de

padrões de buscas já estabelecidos pelo DECEA nesse manual, pois já foi feito esse

esforço de avaliação do grau de adequação de cada padrão de busca a

determinadas situações. Neste trabalho, o cenário estudado é o espalhamento de

23

vários objetos a partir de um ponto central, simulando um acidente de uma aeronave

em alto mar.

1.4 Organização

O trabalho está estruturado de forma a, primeiramente, ambientar o leitor aos

assuntos pesquisados e, posteriormente, apresentar a proposta, resultados e

considerações finais.

Mesmo não sendo o foco principal do trabalho, uma apresentação breve

sobre VANTs, contextualização sobre busca e salvamento e breve apresentação da

teoria multiagente são relevantes para o entendimento desta pesquisa de mestrado.

O capítulo 2 apresenta alguns conceitos sobre VANTs, descrevendo a

evolução dessa tecnologia, desde o seu surgimento, passando pelo atual estado da

arte até a visão de futuro desses robôs: os VANTs cooperativos.

O capítulo 3 traz informações sobre operações de busca e salvamento no

Brasil e no mundo. Esse capítulo traz informações sobre a organização desse

serviço, estatísticas a respeito e os padrões de busca estabelecidos pela entidade

responsável no Brasil.

O capítulo 4 aborda a teoria multiagente e discute algumas estratégias de

coordenação, discorrendo sobre a adequação de cada uma à cooperação de

VANTs.

O capítulo 5 apresenta os principais algoritmos de navegação de VANTs

utilizados na literatura, subdivididos em duas classes: navegação ponto-a-ponto e

busca local, bem como suas principais vantagens e desvantagens.

O capítulo 6 apresenta a proposta da pesquisa de mestrado, bem como as

premissas e simplificações adotadas. Nesse capítulo, discorre-se sobre como os

algoritmos de navegação, os padrões de busca e os mecanismos de coordenação

são combinados numa estratégia de cooperação para se alcançar o modelo de

VANTs cooperativos, utilizando, também, a discretização do espaço de busca em

células.

24

O capítulo 7 apresenta a metodologia de simulação bem como o

planejamento e as justificativas para os cenários simulados. Esse capítulo também

faz referência ao APÊNDICE A – Estimação de parâmetros –, que completa a

explicação, visando dar ao leitor todas das informações necessárias para

compreender e prosseguir na pesquisa do tema a partir deste trabalho.

O capítulo 8 apresenta os resultados obtidos pelas simulações, bem como as

análises desses resultados. Aqui, o objetivo é avaliar a sensibilidade dos parâmetros

envolvidos no modelo de VANTs cooperativos.

Por fim, o capítulo 9 apresenta as conclusões e considerações finais desta

pesquisa de mestrado, incluindo conclusões referentes ao modelo, sugestões e

visões para trabalhos futuros, bem como comentários finais sobre o tema.

25

2 VEÍCULOS AÉREOS NÃO TRIPULADOS

De acordo com o Departamento de Defesa Americano (Department of

Defense – DoD), VANT é “uma aeronave ou um balão que não transporta um

operador humano e é capaz de voar sob controle remoto ou autônomo” (JP, 2011).

Porém, em 2005 (CORRÊA, 2008), o mesmo órgão definia VANT como

[...] um veículo aéreo motorizado que não transporta um operador

humano, usa forças aerodinâmicas para a sustentação aérea, pode

voar de maneira autônoma ou ser pilotado por controle remoto, pode

ser descartável ou recuperável e pode transportar uma carga útil letal

ou não-letal. Veículos balísticos ou semibalísticos, mísseis de

cruzeiro e projeteis de artilharia não são considerados veículos

aéreos não-tripulados.

Apesar de a definição atual estar mais abrangente, destaca-se a ausência de

piloto e a existência de dois tipos de VANTs (remotamente controlado ou autônomo)

como sendo as suas principais características. Esta pesquisa de mestrado possui

interesse maior no segundo tipo.

Embora a maioria das aplicações desse tipo de aeronave ainda se concentre

no campo militar – vigilância, reconhecimento, combate e utilização para testes de

novas armas –, as aplicações no domínio civil estão ganhando força, por exemplo:

vigilância urbana e de fronteiras, rodovias, costa, infraestrutura crítica, etc. (JAKOB

et al., 2010; BOSSONARO et al., 2011); escolta aérea; monitoramento de obras,

queimadas, dutos (PETROBRÁS, 2011), linhas de transmissão (CEMIG, 2011), etc.;

mapeamento de território; busca e salvamento; e quaisquer outras aplicações em

que seja conveniente poupar o piloto de riscos e de trabalhos desgastantes – ou

seja, nas operações “dull, dirty and dangerous”.

Além da diversidade de aplicações e dos tipos de controle já mencionados, é

possível encontrar na literatura algumas classificações de VANTs. De acordo com

26

Valavanis (2007), os VANTs podem ser: de asas fixas (fixed-wing13) ou de asas

rotativas (rotary-wing14); mais leves ou mais pesados do que o ar; com decolagem

vertical (VTOL – vertical take-off and landing) ou em curto espaço (STOL – short

take-off and landing); com controle on-board (autônomo) ou off-board (controlado

remotamente). Novamente, tem-se a ideia de robôs ou balões, autônomos ou

controlados remotamente – alguns autores também se referem a esse último

utilizando o termo semiautônomos (BILLINGSLEY, 2006).

A maior parte dos VANTs ainda é controlada remotamente (LONG et al.,

2007), dependendo de intervenção humana e de uma infraestrutura de comunicação

com uma estação de controle, cujo diagrama esquemático está ilustrado na Figura 2.

Esse tipo de VANT é controlado por dois sistemas em solo: o controle da missão –

que atua na subida, descida e controle da operação – e o sistema de lançamento e

recuperação – que automatiza a decolagem e o pouso do VANT. Este último

também pode se comunicar diretamente com o controle de tráfego aéreo para obter

informações mais precisas sobre a aeronave. Ambos se comunicam com o VANT

por meio de link direto e, quando não há possibilidade de comunicação direta, o

controle da missão também pode utilizar a comunicação indireta via satélite. O

controle de tráfego aéreo também pode se comunicar com o VANT, que repassa as

informações recebidas ao controle da missão ou ao controle de pouso e decolagem,

dependendo do caso.

Um dos maiores e mais conhecidos VANTs do mundo é o Global Hawk, que

utiliza esse esquema de controle remoto (BILLINGSLEY, 2006). Essa aeronave

possui 35 metros de envergadura, 36 horas de autonomia de voo e é capaz de voar

em uma altitude de até 65 mil pés15 (PARSCH, 2008). Sua envergadura é maior que

a do Boeing 737-600, que possui 34 metros (BOEING, 2011).

13

Aviões não tripulados que requerem uma pista para decolar e pousar ou uma catapulta de lançamento. 14

Um exemplo de aeronave com asas rotativas é o helicóptero. 15

Equivalente a 19.800 metros.

27

Figura 2 – Comunicação do Global Hawk com a estação base [adaptado de Billingsley (2006)]

2.1 Histórico

Quando se refere a VANTs, há também outros termos utilizados na literatura

como sinônimos de VANTs: Unmanned Aerial Vehicles (UAV), Uninhabited Aerial

Vehicles (COX et al., 2004), Unmanned Aircraft Systems (UAS)16 ou simplesmente

drones17 (VALAVANIS, 2007). Esse último é bastante empregado na literatura militar

e em reportagens veiculadas na imprensa. Outros nomes menos comuns são:

Remotely Piloted Vehicle (RPV) ( ART NE -VAL e HERNÁNDEZ, 1999) –

16

Bastante utilizado entre pesquisadores estadunidenses. 17

Não se sabe ao certo a origem do termo drone, que em inglês significa zangão. Mas, segundo a enciclopédia colaborativa Wikipedia, o nome vem da evolução de projetos de aeronaves controladas por rádio frequência, que eram utilizadas como alvos aéreos. Em 1935, os ingleses produziram um modelo de alvo aéreo chamado DH.82B Queen Bee (cuja tradução para o português seria abelha rainha). Então, em 1936, o chefe do grupo de pesquisa da marinha americana passou a utilizar o termo drone para se referir aos alvos aéreos. Outra hipótese também levantada durante a pesquisa é a de que o nome se deve ao formato dos primeiros protótipos, que se assemelha a zangões por apresentarem uma espécie de ferrão na parte frontal da aeronave (Figura 2).

Controle de

Tráfego AéreoElemento de Controle

da Missão

Satélite(s) de

comunicação

VANT remotamente

controlado

Sistema de Lançamento

e Recuperação

28

defendido por alguns autores por ser mais descritivo –, Remotely Piloted Aircraft

(RPA) e Remotely Operated Aircraft (ROA).

O histórico dos VANTs está bastante associado a operações militares.

Enquanto o conceito de voo não tripulado foi introduzido formalmente por Nicola

Tesla em 1915 (U.S. ARMY, 2010), os primeiros testes sem tripulação datam de

1916 – quando Lawrence e Elmer Sperry construíram uma aeronave com

navegação automática, batizada de “torpedo aéreo” (COX et al., 2004). No entanto,

somente em 1917, durante a Primeira Guerra Mundial, é que o primeiro VANT foi

desenvolvido. Até aquele momento, os VANTs não eram confiáveis e sua utilidade

não era reconhecida pela maioria dos militares e líderes políticos (VALAVANIS,

2007, p. 3).

Cabe ressaltar que, muito antes disso, o ser humano já se aventurava a

construir “engenhocas” que, pela definição atual, já poderiam ser classificadas como

VANTs. Em 1849, austríacos utilizaram balões interligados a cabos elétricos para

lançar bombas sobre o inimigo (SCIENTIFIC AMERICAN, 1849).

Após esses primeiros testes na Primeira Guerra Mundial, os alemães

empregaram, na Segunda Guerra Mundial, as chamadas Bombas Voadoras do tipo

V-1 e V-2, concebidas para missões perigosas demais para serem executadas por

seres humanos (CORRÊA, 2008).

Passado esse período, a década de 70 inicia a era moderna dos VANTs –

com os Estados Unidos e Israel desenvolvendo projetos de VANTs de pequeno

porte, menos velozes e mais baratos do que os seus precursores. Posteriormente, o

sucesso das operações israelenses utilizando essas aeronaves, na guerra do Líbano

em 1982, deu origem a um novo sistema que foi utilizado com sucesso nas

operações no Iraque, em 1991 e em 2003 (COX et al., 2004).

Portanto, pode-se dizer que foi após as operações em 1991, quando o VANT

Pioneer foi utilizado em 300 missões durante a operação Desert Storm, que a

utilização de VANTs passou a ser vista com um interesse maior (VALAVANIS, 2007;

U.S. ARMY, 2010). Dez anos depois houve o atentado ocorrido em 11 de setembro

de 2001 – esse acontecimento pode ser considerado o “divisor de águas” na história

dos VANTs. Após esse ataque, não só a popularidade dos VANTs (que passaram a

aparecer constantemente em capas de jornais e revistas), mas também os

29

investimentos em pesquisas e aquisições de VANTs aumentaram bruscamente

(VALAVANIS, 2007). Em abril desse mesmo ano, cinco meses antes do ataque, a

previsão de investimentos em VANTs (pelo DoD) para os anos de 2000 e 2001 era

de, respectivamente, 284 e 363 milhões de dólares – com aumento anual em torno

de 5% até 2005 (DOD, 2001). Pouco mais de um ano depois, em dezembro de

2002, o mesmo relatório do DoD (UAV Roadmap) apontava um investimento anual

chegando a 2,1 bilhões de dólares em 2005 (multiplicando por cinco) e 3,2 bilhões

de dólares em 2009 (DOD, 2002). Nesse relatório, verifica-se um aumento médio da

previsão de investimento de 60% ao ano (de 2001 a 2005), com 110% somente de

2001 para 2002 – imediatamente após o ataque de 11 de setembro de 2011.

2.2 Tendências

De acordo com Frost&Sullivan (1998) apud Valavanis (2007), em 1997 o lucro

total do mercado mundial de VANTs foi de 2,27 bilhões de dólares. Em 2005,

somente o DoD investiu 2,1 bilhões de dólares (DOD, 2005). Nos anos seguintes, o

investimento anual do mercado global de VANTs passou para 3,4 bilhões de dólares

em 2008 (TEAL GROUP, 2008) e 4,9 bilhões de dólares em 2010 (TEAL GROUP,

2010). A expectativa é que, no período de 2011 até 2020, sejam investidos, tanto em

pesquisa quanto em aquisições, mais de 94 bilhões de dólares, chegando a 11,9

bilhões de dólares anuais em 2018 (TEAL GROUP, 2011).

Além do crescimento observado nos investimentos, cresce também as

projeções, ou seja, as estimativas de crescimento do mercado de VANTs estão

sendo refeitas e reestimadas para valores maiores. Em 2008, a projeção era de que

o mercado mundial de VANTs chegaria a investir 7,4 bilhões de dólares anuais na

década de 2011 a 2020. Em 2010, essa projeção passou a 11,5 bilhões de dólares.

Isso mostra que o tamanho do mercado de VANTs pode vir a ser ainda maior do que

o previsto.

Portanto, esses números indicam um grande interesse mundial em VANTs e

indicam uma tendência de crescimento de investimentos no setor até 2020, que,

30

dada a velocidade da evolução e do barateamento tecnológico, pode ser até maior

do que o indicado pelas projeções.

No entanto, em 2007, dois terços ( ) do mercado global era dominado por

empresas americanas (VALAVANIS, 2007). Já em 2011, “apenas” 34% dos

investimentos em VANTs, englobando pesquisas e aquisições, foram de origem

estadunidense (TEAL GROUP, 2011). Logo, apesar de ainda haver grande

predomínio dos Estados Unidos nesse setor, há tendência de crescimento da

participação dos outros países.

Em relação à aplicabilidade dos VANTs, apesar de já serem utilizados em

aplicações civis, em 2008 as pesquisas na área militar ainda correspondiam à maior

parte (CORRÊA, 2008). No entanto, de acordo com o relatório da Teal Group (2011),

as aplicações civis utilizando VANTs foi o setor da indústria aeroespacial que mais

cresceu na última década (período de 2000 a 2010) e a previsão é que este dobre

nesta década (período de 2011 a 2020). Segundo o mesmo estudo, o mercado de

VANTs civil ainda se encontra em fase inicial e deve emergir lentamente, tendo

como principal obstáculo a falta de acesso ao espaço aéreo até que normas e

padrões sejam criados pelas agências reguladoras competentes. Essa demanda por

regulamentação pôde ser constatada pelas discussões que aconteceram na

conferência UAS Latin American, que ocorreu em São José dos Campos entre os

dias 25 e 27 de outubro de 2011, onde estiveram presentes alguns representantes

governamentais, da indústria e da academia.

Apesar da dificuldade regulatória, já existem iniciativas de investimentos em

aplicações civis. Em abril de 2011, uma grande empresa brasileira revelou que já

estava utilizando um dirigível não tripulado para monitorar obras de construção de

gasodutos (SANTOS, 2011). A necessidade veio do grande volume de obras em

andamento que precisavam ser monitoradas. Outro fato posterior a esse, que

reforça essa tendência, foi a cessão de três VANTs à Polícia Militar Ambiental do

Estado de São Paulo (OLIVEIRA, 2011) por uma empresa fabricante de VANTs. De

acordo com a informação veiculada pela imprensa, os VANTs cedidos são dotados

de câmeras fotográficas e seriam utilizados para monitoramento, em áreas de

preservação permanente, desmatadas, de pesca ilegal, avaliação de mata ciliar,

queimadas e, utilizando um sensor termal, para localização de pessoas perdidas nas

matas. Observa-se que o modelo de VANTs cooperativos proposto nesta pesquisa

31

de mestrado possui similaridade com esse último possível emprego dos VANTs

cedidos à Polícia Militar, o que é um indicativo que já existe demanda para o modelo

proposto.

2.3 VANTs Cooperativos

Após décadas de avanço, os principais desafios referentes aos veículos

aéreos não tripulados estão relacionados ao voo colaborativo. Apesar de os VANTs

atuais apresentarem baixa autonomia18, a expectativa é que, no futuro, múltiplos

robôs aéreos sejam capazes de atuar autonomamente e de modo colaborativo

(VALAVANIS, 2007). Já Vachtsevanos, Tang e Reimann (2004) afirmam que no

futuro os VANTs funcionarão como uma rede de sensores, devendo ser

coordenados para cumprir missões complexas sem a intervenção humana. Ademais,

de acordo com o relatório (U.S. ARMY, 2010), a previsão é que até 2035 operadores

sejam capazes de controlar múltiplos VANTs a partir de um único sistema de

controle e nano-VANTs sejam capazes de colaborar uns com os outros – formando,

assim, enxames de nano-VANTs com autonomia suficiente para monitorar aéreas

externas e internas.

Isso demandará novas tecnologias de controle, de comunicação e

computacionais (VALAVANIS, 2007), e é nessa direção que este trabalho visa,

majoritariamente, contribuir.

Além disso, o avanço no sentido de dotar os VANTs de mais autonomia

também se faz necessário. Sobre esse aspecto, o Departamento de Defesa

americano (DOD, 2005) apresenta o significado de autonomia de VANTs apontando

dez níveis de autonomia. A Figura 3 ilustra esses níveis e, indicada pela curva no

gráfico, a evolução observada e esperada dos VANTs no que diz respeito à

18

A autonomia referida é a autonomia de decisão, que se refere à capacidade do VANT tomar suas próprias decisões sem intervenção humana. VANTs que possuem essa capacidade são comumente chamados de VANTs autônomos. A autonomia aqui tratada não deve ser confundida com a autonomia de voo, termo que também é bastante comum na pesquisa e desenvolvimento de aeronaves tripuladas e não tripuladas. Essa última, diferentemente da autonomia de decisão, se refere à capacidade de voo ininterrupto de uma aeronave sem reabastecimento, ou seja, quanto maior o número de horas que uma aeronave é capaz de voar sem retornar ao solo, maior é sua autonomia de voo.

32

autonomia. Os níveis de autonomia variam desde a operação totalmente

teleoperada (controle remoto) até enxames de VANTs totalmente autônomos. No

primeiro nível, é como se o VANT tivesse um piloto que realiza todos os comandos

que um piloto realizaria numa aeronave tripulada, só de forma remota. Assim, a

partir do primeiro nível, os VANTS vão ganhando mecanismos de autonomia

incrementais até o último nível, no qual grupos de VANTs são guiados por objetivos

e operam sem interferência de um operador.

Quatro exemplos de VANTs são destacados e classificados ao longo da

curva, são eles: Pioneer, Predator, Global Hawk, J-UCAS Goal e UCAR Goal. Os

três primeiros representam, basicamente, a evoluções de um mesmo projeto e,

como se pode observar, o Global Hawk, já citado anteriormente como um dos

VANTs mais conhecidos do mundo, é controlado remotamente e possui alguns

mecanismos de adaptações automáticas a falhas e condições de voo. O Joint

Unmanned Combat Air Systems (J-UCAS) é um projeto de desenvolvimento de

VANT de combate que foi interrompido em 2006 (SHERMAN, 2006) e retomado em

2010 (DEFENSE INDUSTRY DAILY, 2012). Por fim, o projeto mais moderno é o

Unmanned Combat Armed Rotorcraft (UCAR). Segundo descrições encontradas em

sítio eletrônicos especializados no assunto, o UCAR possuirá elevado grau de

autonomia, será capaz de colaborar com múltiplos VANTs do mesmo tipo, não

necessitará de uma estação de base dedicada (diferente dos seus precursores) e,

sendo capaz de planejar missões autonomamente, necessitará de um operador

humano apenas para autorização de tarefas relacionadas a armamento e ataque. De

acordo com as últimas notícias a respeito do projeto UCAR, o sistema deveria ser

lançado a campo por volta no ano de 2012 (GLOBALSECURITY.ORG, 2011).

Observa-se, também, que o enxame de VANTs totalmente autônomos está

num horizonte de tempo ainda muito distante, que não tinha sido projetado na época

do relatório (2005). Porém, conforme dito anteriormente, espera-se que até 2035

haverá enxames de nano-VANTs com autonomia suficiente para monitorar aéreas

externas e internas.

33

Figura 3 – Níveis de autonomia em VANTs. Adaptado de (DOD, 2005)

Para obter controle de múltiplos veículos interconectados, Ren e Cao (2011)

apontam que duas abordagens podem ser adotadas: a abordagem centralizada e a

abordagem distribuída. Pelos motivos expostos a seguir, esta pesquisa de mestrado

concentra seus esforços na segunda.

A abordagem centralizada assume a existência de um sistema central com

capacidade grande o suficiente para atender e coordenar todos os sistemas sob seu

controle. Portanto, o sistema central, necessário a essa abordagem de controle,

exige a existência de uma grande quantidade de recursos computacionais, o que

pode aumentar consideravelmente o custo de um sistema de controle de muitos

VANTs.

Já a abordagem descentralizada não necessita de um sistema central. Porém,

essa abordagem pode ser muito mais complexa que a primeira (REN e CAO, 2011).

Mesmo sendo mais complexo, o controle descentralizado é mais promissor, na

medida em que não se faz necessário um sistema central de elevadas capacidades

computacionais. Além disso, haja vista que falhas individuais não comprometem a

efetividade do sistema, os requisitos de robustez, adaptatividade, flexibilidade e

escalabilidade são atendidos pela abordagem descentralizada.

4

3

2

1

Replanejamento autônomo de rota

Adaptação a falhas e a condições de voo

Diagnóstico de problemas em tempo real

Controlado remotamente

5

Enxames totalmente autônomos

Grupo com objetivos estratégicos comuns

Controle distribuído

Grupo com objetivos táticos comuns

Grupo com replanajemanto tático

Coordenação conjunta

10

9

8

7

6

1955 1965 1975 1985 1995 2005 2015

Pioneer

Predator

Global Hawk

UCAR Goal

2025

J-UCAS Goal

34

Para atingir esses objetivos, arquiteturas de hardware e software devem ser

utilizadas em conjunto com tecnologias de coordenação e planejamento. Como, por

exemplo, inteligência artificial distribuída19, teoria de sistemas multiagentes20, teoria

dos jogos e otimização dinâmica (VALAVANIS, 2007).

Já Ryan et al. (2004) apontam que, apesar do barateamento dos sistemas

computacionais e do crescente interesse pela utilização de VANTs colaborativos,

alguns desafios ainda persistem, tais como: (i) detecção do alvo por câmeras ou

sensores; (ii) mecanismos para evitar colisão com outros VANTs ou com obstáculos

fixos; (iii) reconfiguração de formação, quando os VANTs voam em formação; (iv)

controle transparente do grupo de VANTs, que visa o controle de múltiplos VANTs

por um único operador humano sem a necessidade de operar individualmente cada

VANT; e (v) limitações de hardware e de comunicação.

Nesse trabalho, Ryan et al. (2004) abordam, principalmente, o controle

transparente, sugerindo que uma aplicação de VANTs colaborativos deve fornecer

uma interface gráfica simplificada para que um operador insira os objetivos da

missão. Nesse estudo, os VANTs cooperam dividindo as tarefas, que foram

alocadas pelo operador, de modo autônomo. Será visto, no capítulo 6, que a

proposta do modelo de VANTs cooperativos também atende ao desafio (iv)

apontado por esses autores.

A detecção de pessoas por meio do processamento de imagens, aspecto

bastante relevante na aplicação de VANTs em operações de busca e já apontado

por Ryan et al. (2004) – desafio (i) – foi abordada por Doherty e Rudol (2007). Nesse

trabalho, os autores trataram o problema refinando algoritmos de identificação de

corpos humanos. Além disso, desenvolveram um framework para cooperação

baseado em delegação de metas e sequência de ações, no qual a operação é

composta por duas fases: na primeira fase os VANTs apenas localizam as vítimas e,

na segunda fase, VANTs especializados levam medicamentos e objetos de

primeiros socorros.

Além disso, em determinados cenários de busca, também pode ser

necessário considerar regiões de sombra enquanto a operação de busca é

realizada. Por exemplo, em aéreas urbanas, a presença de prédios e construções

19

Distributed Artificial Intelligence (DAI) 20

Multi-Agent System (MAS)

35

exige que os VANTs sejam dotados de uma inteligência tal que determinados pontos

no solo (como, por exemplo, a base de um prédio) sejam observados de vários

ângulos diferentes para evitar essas regiões de sombra. Abordando esse problema,

Waharte e Trigoni (2010), e Jakob et al. (2010), compararam a eficiência de alguns

algoritmos de busca, considerando regiões de sombra.

Há também os trabalhos que utilizam protótipos reais para estudar a

colaboração de VANTs. Ryan et al. (2007), por exemplo, implementaram um sistema

que realiza missões cooperativas supervisionadas por um único operador. Nesse

trabalho, VANTs de pequeno porte foram utilizados e a cooperação se dá pela

distribuição de tarefas, de patrulha ou de procura de invasor.

Portanto, pode-se dizer que a pesquisa em VANTs cooperativos é uma área

multidisciplinar que ainda se encontra no seu nascedouro. Dentre os aspectos

envolvidos na pesquisa desse tema, destacam-se os seguintes:

Controle centralizado versus controle distribuído;

Estratégia de navegação dos VANTs (path planning);

Estratégia de deliberação individual de cada VANT;

Confiabilidade e segurança na resolução de conflitos. Por exemplo,

mecanismo anticolisão (Collision Avoidance System – CAS);

Confiabilidade no reconhecimento do alvo (processamento de imagens

e visão computacional); e

Aplicação em si. Neste trabalho, por exemplo, a aplicação investigada

é operação busca.

Em relação ao controle distribuído, visionado pelo modelo de VANTs

cooperativos proposto, Ren e Cao (2011) apontam seis tipos de controle distribuído

em veículos não tripulados (não só os aéreos):

Coordenação por consenso: em que os agentes buscam consenso

para tomar as decisões;

36

Controle por formação distribuída: baseia-se na formação de um

padrão geométrico. Como, por exemplo, o padrão em “V” adotado

pelas aves migratórias;

Otimização distribuída: baseia-se em encontrar a estratégia ótima de

acordo com determinada função de custo (function cost);

Divisão de tarefas: baseia-se em quebrar o objetivo global em tarefas e

distribuí-las entres os agentes;

Controle por estimação distribuída: diferentes sensores espalhados

entre os agentes são utilizados para estimativas globais. Aqui há um

foco maior na coleta de informações e na tomada de decisões; e

Coordenação inteligente: cada agente é dotado de certa “inteligência”

e, portanto, escolhe a melhor alternativa levando em conta seu próprio

objetivo e conhecimento. Essa abordagem também é utilizada em

estudos econômicos, ciências sociais, entre outros.

As três primeiras (consenso, controle por formação distribuída e otimização

distribuída) não são atrativas para o objetivo desta pesquisa de mestrado pelos

motivos expostos a seguir. A busca por uma solução consensual degradará a

robustez do sistema, de modo que as decisões serão possíveis apenas se houver

consenso no grupo de VANTs. A formação de padrão geométrico também não é

interessante porque haveria perda na autonomia dos VANTs, deixando-os presos a

determinada formação e perdendo capacidade de responder a modificações no

ambiente. Por último, a otimização distribuída demandaria muito processamento e,

além disso, não é necessário que a solução seja ótima.

Será visto, no capítulo 6, que o modelo proposto nesta pesquisa de mestrado

utiliza conceitos das três últimas estratégias: divisão de tarefas, controle por

estimação distribuída e coordenação inteligente.

Por fim, cabe ressaltar que a adequação de cada tipo de controle distribuído

está diretamente relacionada à característica do problema que se deseja tratar. Os

controles utilizados no modelo proposto foram escolhidos porque foram

considerados os mais apropriados ao cenário de busca definido no capítulo 6. O

37

controle por formação distribuída, por exemplo, poderia ser mais adequado a uma

operação de vigilância,

2.4 Considerações finais do capítulo

Esse capítulo apresentou o estado da arte dos VANTs, passando

sucintamente por seu surgimento, pelas tecnologias atuais e o que se espera da

nova geração de veículos aéreos não tripulados: os VANTs cooperativos.

Além disso, foram apresentados alguns números que indicam que ainda

existe uma forte presença de investimentos militares na pesquisa de VANTs, mas

com uma tendência de crescimento percentual dos investimentos civis. No geral, o

mercado apresenta uma previsão de grande crescimento para a década atual.

Por fim, conceitos gerais sobre a multidisciplinaridade presente na pesquisa

de VANTs cooperativos foram apresentados, bem como os caminhos possíveis e os

que mais se adéquam ao objetivo da pesquisa.

38

3 OPERAÇÃO DE BUSCA E SALVAMENTO

Operações de busca e salvamento, mais conhecidas pela sigla em inglês

SAR (Search And Rescue), são operações cujo objetivo é localizar e resgatar

pessoas em difíceis condições. A busca pode ser feita a olho nu ou por algum

equipamento eletrônico – nesse último caso, a pessoa, embarcação ou aeronave

perdida deve possuir equipamento emissor de sinais.

De acordo com o Departamento de Defesa 21 americano (JP, 2011), a

definição formal de busca e salvamento é “o uso de aeronaves, veículos de

superfície, submarinos e de equipes de resgates e equipamentos especializados

para buscar e resgatar pessoas em perigo, em terra ou em mar, que estejam num

ambiente de difícil sobrevivência” (traduzido).

Antes de apresentar a parte computacional do modelo de VANTs

cooperativos para operações de busca, objeto desta pesquisa de mestrado, este

capítulo apresenta as operações SAR do ponto de vista dos órgãos responsáveis.

De acordo com o Manual de Busca e Salvamento do DECEA (DECEA, 2009),

a mera ação de sobrevoar encostas de montanhas, ou regiões de alto mar, a baixa

altitude, já constitui, por si só, uma atividade de risco, que exige de toda a tripulação

uma atenção redobrada. Além disso, é importante ressaltar que o Coordenador de

Missão SAR (SMC22) deverá obter, do Controle de Tráfego Aéreo responsável pela

área onde as buscas serão realizadas, a reserva de espaço aéreo, a fim de facilitar a

coordenação do tráfego na área de busca (DECEA, 2009, p. 147). Portanto, esses

dois aspectos configuram uma situação bastante atraente para a utilização de

VANTs em operações de busca e salvamento. Esses veículos podem se sujeitar a

uma exposição maior ao risco e, por haver segregação do espaço aéreo, é possível

utilizar os modelos de VANTs já existentes, não sendo necessários mecanismos

complexos de coordenação com aeronaves tripuladas para navegação em espaço

aéreo compartilhado, assunto de pesquisa bastante relevante em outros contextos.

21

DoD (Department of Defense). 22

Do inglês Search and Rescue Mission Co-ordinator.

39

Corroborando com a utilização de VANTs em operações SAR, o Manual

Internacional de Busca e Salvamento (IMO/ICAO, 2003) aponta que o uso dos

recursos disponíveis para a operação de busca deve ser otimizado, pois, além de

contribuir para o aumento da probabilidade de salvar vidas com a redução do tempo

de resgate, as operações de buscas são financeiramente dispendiosas e muitas

vezes colocam a equipe de busca numa situação de alto risco. Sendo assim, o

manual recomenda que, para maximizar a efetividade de busca, os seguintes

passos devem ser seguidos:

Dividir a região de busca em subáreas;

Estimar a probabilidade de contenção23 (POC) para cada subárea;

Desenvolver um plano que maximiza a probabilidade de sucesso 24

(POS), selecionando padrões de busca;

Conduzir o plano de busca;

Atualizar todas as probabilidades de contenção que refletem os

resultados parciais da busca;

Utilizar os valores das probabilidades de contenção atualizados num

novo planejamento de busca, maximizando a probabilidade de sucesso

na próxima busca subsequente.

Além disso, cabe ressaltar que o planejamento deve ser constantemente

atualizado e revisto, de acordo com as informações que forem surgindo sobre a

posição dos objetos de busca encontrados. Todas essas recomendações remetem à

construção da Figura 4. Observa-se, também, que essa figura é bastante

semelhante ao conhecido ciclo PDCA (Plan, Do, Check, Act), elaborado por

Shewhart em 1939 (SHEWHART, 1986).

23

Ver glossário 24

Ver glossário

40

Figura 4 – Recomendações da OACI para operações de busca tripulada

3.1 SAR no Brasil

O documento que guia as operações SAR no Brasil é o Manual de Busca e

Salvamento. Esse documento está de acordo com doutrina SAR mundial, com as

diretrizes da OACI e com as diretrizes da Organização Marítima Internacional

(OMI)25 (DECEA, 2009). Esse manual se originou do Anexo 12 da CACI e do Manual

Internacional Aeronáutico e Marítimo de Busca e Salvamento (IMO/ICAO, 2003), o

IAMSAR, e foi complementado com informações obtidas pela experiência brasileira

adquirida em operações SAR.

Por meio da Divisão de Busca e Salvamento, o DECEA é o órgão responsável

pelas operações de busca e salvamento. Conforme apresentado na Figura 1 (página

19), o território pelo qual o Brasil é responsável pela busca e salvamento é dividido

em cinco áreas. As ações de busca e salvamento em cada uma dessas áreas estão

sob responsabilidade do respectivo Centro de Coordenação de Salvamento (RCC26),

também chamados de Salvaero. Esses órgãos são dotados de uma adequada rede

de comunicação e de pessoal altamente especializado, em permanente estado de

alerta, sete dias por semana, 365 dias por ano (DECEA, 2011).

25

Em inglês: International Maritime Organization (IMO) 26

Do inglês Rescue Coordination Center

41

Estatísticas obtidas no sítio eletrônico do DECEA apontam que, apenas de

janeiro a outubro de 2011, houve 2.277 operações de busca de salvamento nas

cinco regiões apresentadas na Figura 1. Dessas, estima-se que 45% foram na

região amazônica (área ARCC-AZ da Figura 1), 20% na região nordeste (área

ARCC-RF da Figura 1), 10% na região marítima (área ARCC-AO da Figura 1) e

aproximadamente 12,5% em cada uma das áreas central (ARCC-BS) e sul (ARCC-

CW) da Figura 1 (DECEA, 2011).

A atividade SAR no Brasil também colabora para a segurança do tráfego

aéreo. De acordo com o código brasileiro de aeronáutica (BRASIL, 1986; DECEA,

2009, p. 14), as atividades de busca e salvamento integram o sistema de proteção

ao voo, que visa à regularidade, segurança e eficiência do fluxo de tráfego no

espaço aéreo. As outras atividades que também o integram são: controle de tráfego

aéreo, telecomunicações aeronáuticas e auxílios à navegação aérea, meteorologia

aeronáutica; atividades de cartografia e informações aeronáuticas; atividades de

inspeção em voo; atividades de coordenação e fiscalização do ensino técnico

específico; e atividades de supervisão de fabricação, reparo, manutenção e

distribuição de equipamentos terrestres de auxílio à navegação aérea. Logo, pode-

se afirmar que melhorias no sistema de busca e salvamento brasileiro – o SISSAR27

– ajudam a aprimorar do sistema de proteção ao voo, que por sua vez contribuem

para o aumento de segurança no transporte aéreo.

Portanto, verifica-se o tamanho da importância de melhorar o sistema de

busca e salvamento, que, além de crítico, possui grande complexidade de operação

devido às dimensões continentais sob sua responsabilidade.

3.2 SAR no mundo

No âmbito global, ou seja, no âmbito dos países membros da OACI, o

documento que rege as atividades SAR é o ANEXO 12 da Convenção de Aviação

27

Acrônimo de Sistema de Busca e Salvamento Aeronáutico. Foi criado pela portaria nº 99/GM3, de 20 de fevereiro de 1997, induzido pela evolução da prestação do serviço SAR e pela necessidade de se adequar as operações SAR à realidade do País. Desde então, o SISSAR passa por um processo de evolução permanente.

42

Civil Internacional (CACI) de 1944, complementado pelo Manual Internacional

Aeronáutico e Marítimo de Busca e Salvamento (DECEA, 2010a). Desde a

convenção, em 1944, os países signatários, como o Brasil, passaram a adotar as

diretrizes emanadas pela OACI, incluindo as relacionadas à organização de um

serviço de Busca e Salvamento no país.

A Figura 5 apresenta a divisão marítima das áreas SAR realizada pela OACI e

os signatários da CACI, indicando os países responsáveis por cada uma delas.

Verifica-se que o Brasil é um dos países que possui uma das maiores áreas

marítimas sob sua responsabilidade, reforçando o tamanho da responsabilidade

brasileira. Os retângulos vermelhos, assinalados com as letras A, B, C, D, E e F,

apresentam grande fragmentação, por isso a divisão das áreas SAR dessas regiões

não foram explicitadas na figura – para consultar a divisão marítimas dessas regiões

pode-se consultar a referência da figura.

Figura 5 – Divisões de áreas marítimas para operações SAR [Adaptado de (ROBITAILLE, 1999)].

Além das diretrizes formais emanadas pela OACI, existem diversos outros

projetos, competições e instituições que visam agregar esforços para gerar e manter

conhecimento sobre operações de busca e salvamento, principalmente, as

operações chamadas WiSAR, Wilderness Search and Rescue (WISAR TEAM, 2011;

43

CLOSE-SEARCH, 2011; UAV CHALLENGE, 2011; BRIGHAM YOUNG

UNIVERSITY, 2011; WISAR LAB, 2011). Todos têm em comum o apelo humanitário

e a maioria procura utilizar mini-VANTs para dar suporte às equipes de busca.

3.3 Padrões de Busca

Para cada cenário28, há sempre uma estratégia de busca mais adequada

(DECEA, 2009). Portanto, a identificação do cenário é essencial para o sucesso de

uma operação de busca, que, por sua vez, é essencial para o sucesso de uma

operação SAR. Por isso, foi feito um levantamento das estratégias de busca

descritas nos manuais de referência (IMO/ICAO, 2003; DECEA, 2009). Assim,

levando em consideração que já são práticas de busca consolidadas e adequadas a

determinadas situações, esses padrões serão utilizados nos planos de busca dos

agentes (VANTs) sempre que possível. As informações levantadas estão

compiladas na Tabela 1, que apresenta os Padrões de Busca e suas principais

características.

Tabela 1 – Padrões de busca obtidos nos manuais de referência (IMO/ICAO, 2003; DECEA, 2009). [Figuras adaptadas de (DECEA, 2009)].

Padrão de busca Trajeto ilustrativo

Padrão de busca “Longitudinal”

(Track Line Search – TS).

Empregado quando se conhece a

rota em que a aeronave perdida

estava cumprindo e acredita-se

que a mesma esteja próxima ao

traçado original de sua rota.

Normalmente, esse padrão é

empregado como esforço inicial de

busca.

28

Ver definição do DECEA no glossário.

44


Padrão de busca “Rotas

Paralelas” (Parallel Sweep Search

- PS). Empregado quando não se

dispõe de informações quanto à

posição provável do objeto de

busca29 e deseja-se uma cobertura

rápida e uniforme. Nesse padrão,

o espaçamento (S) pode ser

ampliado visando uma cobertura

menos densa e com progressão

mais rápida.

Padrão de busca “Pente”

(Creeping Line Search – CS). É

menos eficiente, porém similar,

que o padrão “Rotas Paralelas”,

mas, muitas vezes, é a única

solução para minimizar efeitos

adversos. Como, por exemplo, o

reflexo do sol.

Padrão de busca “Quadrado

Crescente” (Expanding Square

Search – SS). Utilizado quando se

acredita que a localização do

objeto de busca está dentro de

determinados limites específicos.

Nesse padrão, o uso de marcador

flutuante é obrigatório e se exige

que a SRU30 detenha recursos de

navegação precisos.

29

Ver definição do DECEA no glossário. 30

Em inglês, Unidade de Busca e Salvamento (ver glossário).

45


Padrão de busca “Setor” (Sector

Search – VS). Utilizado quando se

dispõe de informações precisas

sobre o objeto da busca.

Normalmente, essa situação

ocorre quando o sinal proveniente

de uma baliza de emergência foi

captado. Esse padrão proporciona

uma cobertura intensa nas regiões

próximas ao centro e demanda

uso obrigatório de marcador

flutuante.

3.4 Modelo matemático de acidentes em alto mar

Uma operação de busca sobre o mar possui características bastante

peculiares, que a diferem substancialmente das operações de busca terrestres. As

principais diferenças dizem respeito à dificuldade de se conseguir informações sobre

os objetos de busca e ao deslocamento dos mesmos em decorrência da deriva. Esta

última, devido à complexidade de simulações do ambiente oceânico, não está sendo

tratada no modelo proposto desta pesquisa de mestrado. No entanto, cabe ressaltar

que a deriva marítima é influenciada pelos seguintes fatores: corrente marítima total

(composta por corrente oceânica, correntes de marés e correntes de vento local) e

força do vento sobre a superfície dos objetos – chamado de caimento31 (DECEA,

2009).

Em relação ao posicionamento dos objetos, o Manual Internacional de Busca

e Salvamento (IMO/ICAO, 2003) estabelece que o primeiro passo num planejamento

de uma operação de busca marítima é a determinação dos limites da área que

31

É a principal força que movimenta um barco à vela.

46

contém todos os possíveis sobreviventes. Essa área é que determinará o escopo da

operação de busca.

Tendo os limites da busca bem definidos, o mesmo manual aponta que outra

importante consideração a ser feita numa operação de busca é distribuição de

probabilidades da posição dos objetos de busca, pois essa consideração influenciará

a forma com que os recursos serão empregados na operação de busca.

Essa distribuição de probabilidades, quando não há evidências que fornecem

uma indicação clara sobre a provável posição dos objetos, pode ser estimada por

padrões de distribuições. As mais utilizadas são a distribuição normal (pontos e

linhas datum32) e a distribuição uniforme (para áreas datum). Tendo a posição

estimada do acidente, tem-se uma distribuição normal em três dimensões ao redor

dessa posição (IMO/ICAO, 2003) indicando que a probabilidade de haver objetos é

menor quando se afasta dessa posição estimada – conforme ilustrado na Figura 6.

Numa distribuição uniforme, todos os pontos da figura apresentariam o mesmo valor,

sendo assim, forma geométrica seria um planalto.

Figura 6 – Distribuição normal de três dimensões

O desvio padrão dessa distribuição normal deve ser fixado num valor tal que

50% dos objetos estejam dentro do erro da estimativa (IMO/ICAO, 2003). Esse erro

pode ser calculado, por exemplo, pela imprecisão do equipamento pelo qual se

estimou a posição provável do acidente, pelo tempo decorrido (juntamente com a

deriva do local), entre outros.

32

Ver glossário.

47


Este capítulo apresentou a organização das operações de busca e

salvamento no Brasil e no mundo. A doutrina brasileira está alinhada com a doutrina

SAR mundial, sendo que esta última se originou do Anexo 12 da CACI e do Manual

Internacional Aeronáutico e Marítimo de Busca e Salvamento.

As estatísticas e números apresentados, juntamente com a Figura 1 (página

19) e a Figura 5 (página 42), mostram o tamanho da responsabilidade do Brasil no

diz respeito às operações de busca e salvamento em seu território e na parte

marítima sob sua responsabilidade, bem como a relevância de prover a máxima

eficiência possível ao sistema de busca e salvamento.

Recomendações a serem seguidas nas operações de busca, bem como

padrões de busca, foram apresentados e, por fim, o modelo matemático de

acidentes em alto mar, que será considerado nas simulações.

48

4 TEORIA MULTIAGENTE PARA VANTs COOPERATIVOS

Este capítulo apresenta alguns conceitos sobre a teoria multiagente e, com

foco maior na coordenação de agentes, apresenta a inserção dessa teoria nesta

pesquisa de mestrado.

A abordagem multiagente possui grande aderência à aplicação de VANTs

cooperativos para busca e salvamento, pois ela fornece um conjunto de mecanismos

e protocolos de negociação, de coordenação e de tomada de decisão

descentralizada em grupos de agentes parcialmente cooperativos (PECHOUCEK e

SISLAK, 2009). Pechoucek e Sislak utilizam a expressão “parcialmente

cooperativos” para indicar que a cooperação não é incondicional, ou seja, o VANT

deve cooperar com os demais, mas não deve colocar em risco sua própria

segurança ou a segurança dos demais.

Corroborando com Pechoucek e Sislak (2009), Wooldridge (2009) aponta que

um agente é um sistema capaz de agir independentemente. Já um sistema

multiagente consiste em um grupo de agentes que, para atingir um objetivo comum,

interagem entre si por meio de cooperação, coordenação e negociação. Isso é o que

se deseja obter com uma equipe de VANTs cooperativos.

De acordo com Bellifemine, Caire e Greenwood (2007), a programação

orientada a agentes – ou Agent-Oriented Programming (AOP) – é um paradigma de

software relativamente novo que utiliza conceitos da inteligência artificial dentro dos

sistemas distribuídos. Segundo eles, esse paradigma modela um conjunto de

agentes que são caracterizados pela autonomia, pró-atividade e habilidade de

comunicação. Novamente, trata-se de características intrinsecamente relacionadas

aos VANTs cooperativos.

Além disso, Jennings e Wooldridge (1998) apontam que agentes inteligentes

vêm sendo utilizados em aplicações desde as mais simples e menos críticas (por

exemplo, sistema de filtro de e-mails) até em sistemas complexos e críticos. Como

exemplo de sistemas complexos e críticos que utilizam agentes pode-se citar o

49

sistema de controle de tráfego aéreo OASIS33 (LJUNGBERG e LUCAS, 1992), que,

segundo os seus criadores, apresenta grande robustez no que diz respeito a

tolerância a falhas. Esse sistema, que visa diminuir o congestionamento do tráfego

aéreo maximizando a utilização da pista, foi testado com sucesso utilizando dados

reais de tráfego aéreo no horário de pico do aeroporto de Sidnei (Austrália) – com

demanda de 65 pedidos de pouso em 3 horas e meia. Outros exemplos de aplicação

de sistemas multiagentes mais similares ao estudo desta pesquisa de mestrado são

os sistemas CAMPOUT – Control Architecture for Multi-robot Planetary OUTpost

(HUNTSBERGER et al., 2003) –, desenvolvido pela NASA –, e o MISUS – Multi-

rover Integrated Science Understanding System (ESTLIN et al., 2005). Ambos são

propostas de arquiteturas de controle multiagente para exploração planetária.

Já Luck et al. (2005) afirmam que, com o avanço significativo de hardware e

software observado nas últimas seis décadas, os sistemas terão que ser capazes de

se adaptar a ambientes dinâmicos, de se autoconfigurar e de efetuar manutenção

neles mesmos, e tudo isso irá requerer o uso da tecnologia de agentes. Mais uma

vez, essas características mencionadas também são bastante desejáveis num

modelo de VANTs cooperativos.

Portanto, dada a necessidade de novas tecnologias para se alcançar a

colaboração de VANTs apontada por Valavanis (2007) – citado na subseção 2.3 –,

considera-se promissor o uso da teoria multiagente como forma de abordar os

desafios existentes na cooperação de VANTs, principalmente no que diz respeito ao

controle distribuído.

4.1 Agente

Embora não haja consenso na definição de agente, as principais definições

encontradas na literatura (JENNINGS e WOOLDRIDGE, 1998; RUSSELL e NOWIG,

2003) convergem numa característica principal: a autonomia. Sendo autônomo, o

33

Optimal Aircraft Sequencing using Intelligent Scheduling

50

agente é capaz de realizar tarefas sem intervenção de um operador humano –

característica desejável em times de VANTs cooperativos.

Além da autonomia, de acordo com Sichman (2011) apud Demazeau (1994),

os agentes podem ser classificados em reativos e cognitivos. Enquanto os primeiros

são baseados em, principalmente, autômatos e na lógica estímulo-resposta, os

últimos são baseados no controle deliberativo, em que as ações são planejadas

utilizando mecanismos mais complexos. Também, nos agentes reativos surge o

conceito de emergência (LENAT, 1975; MINSKY, 1988), em que a cooperação

emerge a partir de regras simples de interação. Já na concepção de agentes

cognitivos, a modelagem é mais sofisticada, demandando, normalmente,

coordenação entre os agentes, comunicação, construção de planos e modelos de

raciocínio.

Embora não seja objeto de análise desta pesquisa de mestrado, além do

controle deliberativo necessário para a exploração dos VANTs, o controle reativo

também é um aspecto a se considerar numa operação real de um VANT (SISLAK,

VOLF e PECHOUCEK, 2010). Nesse estudo, os autores deram mais enfoque no

controle reativo, responsável pela resposta a emergências – como o desvio de um

obstáculo, por exemplo. Corroborando com Sislak, Volf e Pechoucek (2010), Long et

al. (2007) apontam que a operação de veículos autônomos em ambientes reais, com

ruídos e incertezas, exige diversos sensores e mecanismos de controle tanto

reativos quanto deliberativos.

A Figura 7 ilustra a arquitetura geral de um VANT envolvendo esses dois

controles. Enquanto no controle reativo observa-se o uso, principalmente, de

sensores e atuadores para executar funções de piloto automático e para mecanismo

anticolisão (CAS), no controle deliberativo observam-se as funções de planejamento

de trajetória e de coordenação com outros VANTs, que fazem uso da comunicação

com outros VANTs e do processamento embarcado.

51

Figura 7 – Arquitetura geral de um VANT. Fonte: (CHAVES e CUGNASCA, 2011)

A utilização da teoria multiagente não é inédita. Além disso, outras

arquiteturas são possíveis, até mesmo utilizando vários agentes para modelar um

único VANT – como proposto por Corrêa (2008) e por Sislak, Volf e Pechoucek

(2010).

4.2 Cooperação versus Coordenação

Antes de entrar no assunto, julga-se relevante fazer uma breve distinção entre

os termos cooperação e colaboração, pois na literatura esses termos são muitas

vezes utilizados de maneira indiscriminada e equivocada. De acordo com Shima e

Rasmussen (2008), um conjunto disperso de VANTs com alguns objetivos em

comum é um time colaborativo. Se os VANTs trabalham em conjunto para atingir um

objetivo comum, levando em consideração as ações dos demais para contribuir para

o grupo, e não apenas cumprir seu objetivo individual, diz-se que os VANTs são

cooperativos. Portanto, é na cooperação de VANTs que esta pesquisa de mestrado

possui maior interesse. Esta última apresenta mais sinergia do que a colaboração,

de modo que há a expectativa de que o desempenho do grupo cooperativo supere o

desempenho de um grupo com o mesmo número de indivíduos não cooperativos.

52

Sendo baseado num sistema multiagente, uma característica importante para

a investigação da equipe de VANTs cooperativos é a capacidade de coordenação.

Por conseguinte, dar-se-á atenção especial a esse assunto, separando-o nesta

subseção.

De acordo com Nwana, Lee e Jennings (1996), coordenação é o processo em

que os agentes se empenham para garantir que uma comunidade de agentes aja de

maneira coerente. Já Wooldridge (2009) afirma que o maior problema na

cooperação de agentes é a coordenação, essa última, por sua vez, é definida como

o gerenciamento de interdependências das atividades.

Luck et al. (2005) apontam que cooperar é coordenar com um objetivo

comum. Já a coordenação pode ser definida de várias formas, mas a definição mais

simples é a de que coordenar é garantir que ações ou decisões de agentes

independentes sejam coerentes. Além disso, os autores apontam que existem

diversas formas de coordenação e cooperação: cooperação emergente; protocolos

de coordenação; armazenamento distribuído de dados para habilitar comunicação

assíncrona de objetivos e outras informações úteis; e planejamento distribuído.

Bellifemine, Caire e Greenwood (2007) apontam que há quatro situações em

que a coordenação é necessária:

Os objetivos dos agentes conflitam com suas ações;

Os objetivos dos agentes são interdependentes;

Existência de agentes com diferentes capacidades e conhecimentos;

Ou quando há o desejo de que os objetivos possam ser alcançados

mais rapidamente, com cada um dos agentes se empenhando em um

objetivo paralelamente.

Verifica-se, portanto, que existe convergência na definição de coordenação,

principalmente no que diz respeito à coesão e interdependência de ações e de

objetivos individuais. A coordenação de agentes é um assunto bastante extenso na

inteligência artificial e não cabe aqui qualquer tentativa de inovar nessa área. As

subseções a seguir apresentam os principais mecanismos (ou abordagens) de

coordenação encontrados na literatura.

53

4.2.1 Organização estrutural

O mecanismo de coordenação baseado na organização estrutural se baseia

num framework que define atividades e interações entre os agentes por meio da

definição de regras, canais de comunicação e relações de autoridade (DURFEE,

1999).

A organização estrutural se utiliza da metáfora social, em que cada indivíduo

possui habilidades, papéis e responsabilidades diferentes. Dessa forma, o

comportamento do grupo de indivíduos é resultado dessas regras e relações.

Embora seja uma abordagem bastante interessante, com forte viés sociológico, essa

abordagem possui custo computacional relativamente alto.

Um dos exemplos mais simples de coordenação que utiliza essa abordagem

é a arquitetura mestre-escravo, na qual o agente mestre adquire conhecimento por

meio dos escravos, elabora planos e aloca tarefas aos escravos.

Existem diversas modelagens que se utilizam de organizações estruturais e

que podem ser empregados na construção de sistemas multiagentes, tais como:

TAEMS (LESSER et al., 2004), AGR (FERBER e GÜTKNECHT, 1998), STEAM

(TAMBE e ZHANG, 1998), MOISE+ (HÜBNER, SICHMAN e BOISSIER, 2002). Há,

também, metodologias de desenvolvimento indicadas para construção desses

sistemas, por exemplo: GAIA (WOOLDRIDGE, JENNINGS e KINNY, 2000).

4.2.2 Acordos bilaterais (contracting)

Outra importante técnica de coordenação multiagente é o Contract Net

Protocol, definido por (SMITH, 1980), que posteriormente virou uma especificação

da FIPA34 (FIPA, 2002). Essa abordagem é inspirada num mercado descentralizado,

em que os agentes podem desempenhar apenas dois papéis: contratante e

contratado. Basicamente, a ideia é que, para alcançar um objetivo, um agente

34

FIPA (Foundation for Intelligent Physical Agents) é um conjunto de padrões do IEEE Computer Society que promove tecnologias baseadas em agentes e sistemas multiagentes, visando a interoperabilidade entre agentes e com outras tecnologias.

54

encontre outros agentes capazes e com disposição de colaborar. Para fazer isso,

usa-se um mecanismo inspirado em leilões com as seguintes etapas de

comunicação:

O agente faz o anúncio aos outros agentes (solicita ajuda) – fase 1:

announcement;

Os agentes que recebem o pedido de ajuda respondem informando o

custo da ajuda (ou qualquer outra informação que permita a

comparação das respostas) – fase 2: bidding;

O agente compara as respostas e escolhe aquela que seja mais

vantajosa, alocando a tarefa ao agente autor da melhor resposta

(oferta) – fase 3: awarding.

Wooldridge (2009) aponta que há duas variações desse mecanismo:

“resolução de inconsistências” (handling inconsistency) e “divisão de tarefas” (task

sharing).

Na resolução de inconsistências, cada agente planeja suas atividades

individualmente e apenas os planos conflitantes são resolvidos. Essa resolução se

dá por um agente moderador (também conhecido como sincronizador) ou pelo

protocolo Contract Net (FIPA, 2002).

Já na divisão de tarefas, que se enquadra na categoria conhecida por

Cooperative Distributed Problem Solving (CDPS), o processo divide-se em três

fases: (i) decomposição do problema, (ii) resolução do subproblema e (iii) síntese da

solução (SMITH e DAVIS, 1981). Ou seja, o problema é decomposto em problemas

menores que são alocados individualmente aos agentes e, quando cada

subproblema é solucionado, os agentes trabalham na composição da solução global.

Nesse mecanismo, o maior desafio é descobrir como dividir e alocar as tarefas. A

simplicidade desse mecanismo faz que ele seja bastante empregado em estudos e

aplicações envolvendo múltiplos VANTs (DOHERTY e RUDOL, 2007; RYAN et al.,

2007; TISDALE et al., 2006; MAZA et al., 2011). O protocolo Contract Net é um dos

mais utilizados na implementação desse mecanismo (SMITH, 1980; SMITH e

DAVIS, 1981; WOOLDRIDGE, 2009).

55

4.2.3 Compartilhamento de informações

Esse mecanismo, que também se enquadra na categoria Cooperative

Distributed Problem Solving (CDPS), envolve o compartilhamento de informações

relevantes para a solução do problema. A troca de informações pode ser feita pró-

ativamente – um agente envia a informação porque acredita que esta será útil ao(s)

outro(s) agente(s) – ou reativamente – o agente envia informações somente quando

for solicitado (WOOLDRIDGE, 2009).

Durfee (1999) afirma que o compartilhamento de informações melhora o

desempenho do grupo, no que diz respeito à solução do problema, em

confiabilidade, completeza, precisão e tempo de resposta. A confiabilidade é

garantida na medida em que as informações de diversos agentes podem ser

conferidas umas com as outras. A completeza é obtida porque os agentes ampliam

a visão da operação, pois eles passam a “enxergar” além da sua região geográfica.

Consequentemente, a solução será mais precisa e mais rápida.

4.2.4 Planejamento multiagente

Essa abordagem entende o problema de coordenação de agentes como um

problema de planejamento. Nesse mecanismo, que pode ser centralizado ou

distribuído, a estratégia é planejar previamente as ações dos agentes de modo a

evitar inconsistências e conflitos com os planos dos outros agentes (BELLIFEMINE,

CAIRE e GREENWOOD, 2007).

A resolução de conflitos pode, inclusive, objetivar a segurança (safety) dos

agentes (que modelam os VANTs). Sislak, Volf e Pechoucek (2010), por exemplo,

fizeram uso desse mecanismo para evitar colisões de VANTs por meio do

planejamento dinâmico de rotas, alterando dinamicamente os planos de voos de

VANTs em vias de colisão. Assim, enxergando a trajetória como um plano, ao

planejar essa trajetória, o agente verifica as trajetórias (planos) de outros agentes

com o intuito prever a possibilidade de colisão. Se houver possibilidade de colisão

com outros agentes, o agente replaneja sua trajetória visando evitar essas colisões.

56

O planejamento centralizado se baseia na existência de um agente central,

que recebe os planos parciais ou locais de cada agente, analisa-os objetivando a

identificação de conflitos e os devolve aos agentes com ajustes que os livrem de

conflitos (GEORGEFF, 1983). Wooldridge (2009) também chama esse mecanismo

de sincronização.

Quando o planejamento é distribuído, os agentes devem ter conhecimento

dos planos dos outros agentes e comunicar uns com os outros para eliminar os

conflitos existentes entre os planos (GEORGEFF, 1984). Cabe ressaltar que a

eliminação de conflitos não necessariamente precisa chegar numa solução ótima e

pode, muitas vezes, ser um processo iterativo.

4.2.5 Negociação

O mecanismo de negociação é o processo de comunicação em que um grupo

de agentes busca um acordo a respeito de alguma situação (BUSSMANN e

MÜLLER, 1993). Por isso, Bellifemine, Caire e Greenwood (2007) sugerem que a

negociação é provavelmente a técnica de coordenação de agente mais confiável,

pois exige que as partes tomem decisões apenas se houver concordância com as

outras partes, podendo haver concessões de algumas partes. Assim, isso evita que

uma decisão de um agente prejudique outro agente ou o grupo.

De acordo com esses mesmos autores, a negociação cooperativa tem sido

empregada, principalmente, de modo centralizado. De certa forma, é similar ao

processo de sincronismo tratado na subseção 4.2.4, com a diferença de que as

partes possuem mais poder individual, pois se não houver concordância a decisão

não é tomada.

Mas, por outro lado, perde-se em robustez, pois uma falha de comunicação

pode, erroneamente, levar o sistema a não tomar uma decisão. Além disso, o tempo

de processamento pode ser consideravelmente comprometido, uma vez que o

57

número de canais de comunicação cresce exponencialmente35 à medida que cresce

o número de agentes no grupo participante da negociação.


Este capítulo discorreu sobre a aderência da teoria multiagentes à pesquisa

de mestrado. As vantagens de utilização dessa teoria foram apresentadas e diversos

casos de sucesso da literatura, relacionados com a pesquisa, foram citados.

A subseção 4.2 justificou a utilização de mecanismos de coordenação e

apresentou os principais mecanismos encontrados na literatura, indicando suas

vantagens e desvantagens, bem como os que mais se adéquam ao modelo de

VANTs cooperativos proposto nesta pesquisa de mestrado. Além disso, essa seção

apresentou a diferença de colaboração e cooperação, termos que muitas vezes são

utilizados indistintamente e equivocadamente na literatura.

35

O número de comunicações bilaterais num grupo de agentes pode ser calculado por ,

em que é o número de participantes.

58

5 ALGORITMOS DE NAVEGAÇÃO

O controle dos VANTs pode ser feito diretamente por teleoperação, ou seja, o

piloto controla o VANT diretamente por controles remotos (por exemplo, joystick), ou

via programação da rota. Pela programação da rota, o operador atribui pontos

(waypoints) por onde o VANT deve passar. Esse último é bastante utilizado em mini-

VANTs.

Os algoritmos de navegação se utilizam desse segundo modo. Assim, o

objetivo desses algoritmos é gerar uma sequência de waypoints, de forma a otimizar

a navegação de acordo com algum critério – que pode ser reduzir a distância

percorrida, reduzir o risco, etc. Durante toda a busca, mais de um algoritmo pode ser

utilizado na exploração do cenário. O desafio é conceber a melhor combinação para

cada cenário.

Além dos padrões de busca descritos no capítulo 3, que também podem gerar

algoritmos de navegação36, esta pesquisa de mestrado identificou, na literatura, a

existência de duas “famílias” de algoritmos de navegação, cada uma com suas

características particulares. São elas:

Algoritmos de navegação ponto-a-ponto;

Algoritmos de busca local.

Os algoritmos de navegação ponto-a-ponto têm o objetivo de, como o próprio

nome sugere, gerar uma trajetória de navegação de um ponto de origem até um

ponto de destino. Já os de busca local tem o objetivo de, dada uma região, varrer

exaustivamente essa região da melhor maneira possível.

36

Ou seja, pode-se implementar um algoritmo de navegação que realiza determinado padrão de busca.

59

5.1 Algoritmos de navegação ponto-a-ponto

Para obter uma trajetória ponto-a-ponto, diversos algoritmos podem ser

utilizados. O mais utilizado na literatura é o algoritmo A* (pronuncia-se “A-estrela”),

que possui muitas variantes. O objetivo desse algoritmo é gerar uma rota sobre

qualquer grafo considerando os pesos das arestas, que representam alguma métrica

relacionada ao custo do deslocamento – por exemplo: distância, risco, consumo de

combustível, etc.

Iniciando pelo nó de origem, o algoritmo calcula a função F (soma das

funções G37 e H38) de cada um dos nós vizinhos. Aquele que tiver o menor valor de

F é adicionado numa lista chamada closedlist (mais de um nó pode ser adicionado

nessa lista em caso de empate). Então, o processo de avaliação de todos os

vizinhos é repetido para cada nó da closedlist até que se alcance o nó de destino.

Assim, o algoritmo consegue restringir o espaço de busca verificando apenas os nós

mais “promissores”. Quando o nó de destino é encontrado, a melhor trajetória é

gerada percorrendo a árvore mais curta (de menor peso) do nó de destino até o nó

de origem. A Figura 8 apresenta o pseudocódigo do algoritmo A* e informações

detalhadas sobre a implementação podem ser consultadas em (LESTER, 2005).

Entre as variantes do algoritmo A* está o algoritmo Accelerated A*, AA*

(SISLAK, VOLF e PECHOUCEK, 2009), também chamado de Sparse A* Search por

outros autores (YANG et al., 2009; MENG e GAO, 2010). O princípio básico desse

algoritmo é, ao invés de avaliar os nós imediatamente vizinhos ao nó de origem, o

algoritmo avalia nós ao redor do ponto de origem, mas que não são imediatamente

vizinhos (ou seja, que estão numa distância maior do que apenas uma aresta) –

desde que não haja obstáculos entre essa vinzinhaça e o nó de origem. Assim, o

algoritmo AA* poupa o processamento em muitos nós.

37

Distância calculada entre o nó de origem e o nó avaliado. Como todos os nós entre esses dois nós já foram visitados pelo algoritmo A*, essa distância pode ser facilmente computada percorrendo a árvore formada entre os nós (que, na verdade, já está armazenada em cada um dos nós e é constantemente atualizada a cada descoberta de um caminho mais curto). 38

Distância estimada do nó avaliado até o nó de destino. Normalmente, essa estimativa é feita utilizando uma função heurística. As heurísticas mais comumente utilizadas nesse caso são a distância Euclidiana e a distância Manhatthan.

60

Também na busca por melhor performance, Kopriva et al. (2010) propuseram

o algoritmo chamado Iterative Accelerated A*, IAA*, para evitar colisões em

ambientes complexos com um grande número de aeronaves dividindo o espaço

aéreo. A diferença em relação ao AA* é que, ao contrário do algoritmo AA*, a

distância entre o nó de origem e a vizinhança escolhida para ser avaliada varia

decrescentemente, o que reduz consideravelmente o número de nós visitados

durante o processamento do algoritmo. Inicialmente, o algoritmo verifica nós de uma

vizinhança bastante distante. Se houver alguma colisão na trajetória gerada, o

cálculo de trajetória é refeito reduzindo a distância da vizinhança, e assim

sucessivamente até que se encontre uma trajetória livre de colisões.

Quigley et al. (2005) utilizaram o algoritmo A*, originalmente proposto para

ambientes bidimensionais, para gerar trajetórias de menor custo, considerando

também a altitude. Nesse trabalho, as trajetórias geradas eram posteriormente

carregadas nos VANTs, que de posse delas cumpriam o trajeto previamente

planejado. Os autores também propuseram um procedimento adicional que suaviza

a trajetória, eliminando pontos intermediários que pudessem ser aproximados por

apenas dois pontos, formando uma trajetória retilínea.

Em outros trabalhos (SISLAK, VOLF e PECHOUCEK, 2010; PECHOUCEK e

SISLAK, 2009; KOPRIVA et al., 2010), o algoritmo A* foi adaptado para considerar

também a dimensão temporal. Ou seja, foi adicionado um atributo de tempo a cada

waypoint gerado. Uma segunda fase de processamento foi concebida para atribuir, a

cada waypoint, velocidades diferentes às aeronaves em rota de colisão, de modo

que uma aeronave atinja o ponto de cruzamento antes da outra – evitando,

consequentemente, a colisão. Apesar de não estar explicitamente dito no trabalho,

verifica-se que esse mecanismo é um exemplo do mecanismo de coordenação

“planejamento multiagente” (apresentado na subseção 4.2.4).

61

Figura 8 – Pseudocódigo do algoritmo A* [Adaptado de (LESTER, 2005)]

Assim, por ser razoavelmente eficiente, possuir diversos casos de sucesso na

literatura, ser flexível a variações e gerar trajetórias baseadas em waypoints (que

podem ser facilmente utilizados para guiar VANTs), o algoritmo A* é considerado um

dos mais adequados algoritmos de planejamento de caminhos para VANTs.

Apesar disso, o algoritmo de Dijkstra também possui seu lugar de destaque

entre os algoritmos de planejamento de trajetória. Essencialmente, o algoritmo de

Dijkstra é uma simplificação do algoritmo A*. Enquanto o algoritmo A* calcula o

custo do deslocamento, somando a distância real do nó de origem aos nós

intermediários (que vão sendo avaliados recursivamente), com a estimativa da

62

distância dos nós intermediários até o nó de destino (utilizando uma heurística), o

algoritmo de Dijkstra utiliza apenas o cálculo da distância real do ponto de origem

até os pontos intermediários. Por esse motivo, o algoritmo de Dijkstra vai

“expandindo”39 igualmente em todas as direções, fazendo com que o cálculo da

trajetória explore uma área muito maior até encontrar o ponto de destino, tornando-

o, assim, mais lento que o algoritmo A*. No entanto, cabe ressaltar que o algoritmo

de Dijkstra é mais indicado quando se deseja obter o caminho mínimo para visitar

vários pontos, sem um destino certo (LESTER, 2005).

Outro algoritmo utilizado para a navegação ponto-a-ponto é algoritmo

baseado em forças virtuais, proposto por Zhuoning et al. (2010). Batizado de fuzzy

virtual force (FVF) method, os autores propuseram um método de planejamento de

rota utilizando forças virtuais e lógica nebulosa (fuzzy). A ideia básica do algoritmo é

criar caminhos viáveis com base nas informações disponíveis sobre a região de

sobrevoo, de modo que as áreas que apresentam riscos40 sejam evitadas. Assim,

essas áreas são representadas como forças virtuais de repulsão ao VANT e regras

fuzzy atuam no controle do VANT – por exemplo, utilizando regras do tipo “SE a

força é intensa ENTÃO vire muito à direita (ou esquerda)”.

Embora Zhuoning et al. (2010) tenham obtido resultados que indicam que o

método FVF é superior ao algoritmo A*, no que diz respeito ao planejamento de

trajetória em tempo real em ambientes com muitos obstáculos, há uma característica

que o torna menos aplicável aos VANTs atuais. Esse modelo produz trajetórias

contínuas, ou seja, a trajetória não está representada por uma sequência de

waypoints, o que define a trajetória são comandos fuzzy do tipo “vire pouco para a

esquerda”, “vire muito para a direita”, etc. Isso torna esse algoritmo menos

adequado a modelos discretizados.

39

Ou seja, a avaliação dos pontos vizinhos ocorre igualmente em todas as direções, sem direção certa. 40

Pode ser obstáculos ou áreas hostis de regiões de conflitos.

63

5.2 Algoritmos de busca local

Similarmente aos padrões de busca estabelecidos pelo DECEA,

apresentados no capítulo 3 (subseção 3.3), os algoritmos de busca local visam a

varredura completa de determinada região da melhor forma possível, só que de

forma concentrada.

Rubio, Vagners e Rysdyk (2004), por exemplo, utilizaram conceitos de

adaptatividade para adequar a trajetória de busca aos reflexos do sol e trabalharam

com um objeto de busca por vez. No referido trabalho, os autores utilizam o padrão

de busca “Pente” (embora não tenha sido explicitamente mencionado) para realizar

a busca local numa região onde há incerteza em relação à localização provável do

objeto de busca. Porém, nesse trabalho, o objetivo não era a redução do tempo da

busca, e sim aumentar a qualidade da busca local, de modo a evitar que reflexos do

sol prejudicassem a detecção do objeto por câmera. A Figura 9 ilustra esse tipo de

busca local, na qual o ponto dentro da área circular representa o objeto de busca, o

círculo cinza representa a região de incerteza a respeito da localização do objeto de

e a linha tracejada a rota do VANT. A busca local se refere apenas à trajetória

pontilhada sobre o círculo cinza.

Figura 9 – Busca local inspirada no padrão “Pente” [adaptado de (RUBIO, VAGNERS e RYSDYK,

2004)].

64

Nesse estudo, os autores se referem ao algoritmo como “manobra tática de

busca” (traduzido). Já Lin e Goodrich (2009), em outro trabalho, se refere ao mesmo

procedimento de busca como Complete-Coverage Algorithm.

Outro tipo de algoritmo bastante utilizado em aplicações de robótica é a

navegação por gradiente. Nesse algoritmo, o robô se movimenta sempre na direção

em que determinado atributo é maior. Esse atributo pode ser, por exemplo, a

probabilidade de não colisão, luminosidade do ambiente, entre outros. Havendo um

conhecimento probabilístico do cenário de navegação, o robô pode se orientar até

mesmo no sentido que maximiza essa probabilidade. No caso ilustrado na Figura 6

(página 46), por exemplo, o sentido de crescimento do gradiente, e, portanto,

também o sentido de navegação, seria o ponto central da distribuição de

probabilidade.

Steels (1990) apresentou um estudo de caso sobre cooperação emergente

(conceito introduzido na subseção 4.2), em que robôs autônomos são despejados

por uma nave num planeta desconhecido com o objetivo de exploração (procurando

e coletando amostras de pedras). Aqui, a cooperação e o comportamento dos

agentes distribuídos são tratados pela auto-organização e no estabelecimento de

funcionalidades emergentes, que nada mais são do que regras simples de interação

que produzem um efeito emergente no sistema. Uma das regras utilizadas, que

resulta em comportamento emergente, é o uso do gradiente para direcionar a

locomoção dos robôs.

Basicamente, a ideia é estabelecer uma métrica de distância da nave (de

onde o desembarque no planeta é feito) até os robôs – o que pode ser obtido pela

medição da intensidade de um sinal omnidirecional instalado na nave. Assim, quanto

mais perto do veículo, maior será a intensidade do sinal. Portanto, estando em modo

exploração, os robôs se locomovem visando se afastar da aeronave, ou seja,

buscando detectar um gradiente negativo. Após a coleta de amostras, o robô precisa

retornar à aeronave para depositar a amostra coletada. Por isso, se desloca visando

detectar um gradiente positivo.

Em outra oportunidade41, fora do contexto desta pesquisa de mestrado, esse

estudo de caso foi implementado com base nas informações do artigo e as

41

Num trabalho de disciplina realizada durante a pesquisa de mestrado.

65

simulações apontaram que a inserção do mecanismo de gradiente reduziu o tempo

médio de exploração do planeta em aproximadamente 75%, comparando com um

conjunto de robôs que se deslocam aleatoriamente (sem utilizar o gradiente). Pôde-

se observar também que emergiu um comportamento “mais inteligente”, em que os

robôs se afastam do veículo para explorar o planeta e retornam rapidamente quando

encontram alguma amostra.

Em outro trabalho, Chung e Burdick (2008) avaliaram o desempenho de um

algoritmo muito similar, o algoritmo “drosophila inspired”, cujo nome faz alusão ao

comportamento de uma mosca à procura de comida, que se movimenta sempre no

sentido que aguça mais os seus sentidos. Nesse trabalho, os autores avaliaram

buscas probabilísticas utilizando agentes e testando diferentes algoritmos. Em

comparação ao outro algoritmo testado nesse trabalho (saccadic – não aplicável à

navegação de VANTs), o “drosophila inspired” obteve pior desempenho. Porém,

cabe ressaltar que o estudo de caso não era específico a operações utilizando

VANTs, portanto, a conclusão não se aplica ao objeto de estudo desta pesquisa de

mestrado.

Existe uma pequena e sutil diferença entre o algoritmo baseado em gradiente

e o “drosophila inspired”, enquanto o algoritmo baseado em gradiente segue sempre

a célula vizinha com o maior parâmtero42, o segundo vai em direção a célula, vizinha

ou não, com maior parâmetro – ou seja, o algoritmo “drosophila inspired” busca

máximos locais.

Já Lin e Goodrich (2009), se referiram a esse tipo de algoritmo por “Local Hill

Climbing” (LHC). No referido trabalho, os autores implementaram o algoritmo

utilizando a metáfora do aquecimento global. Essa técnica se baseia na restrição da

região onde será realizada a busca local, considerando apenas as células cuja

probabilidade de conter um objeto de busca é maior que determinado valor , que é

estabelecido de acordo com a necessidade. Assim, verifica-se o aparecimento de

“ilhas” cujas células estão acima desse valor. Então, na geração de uma trajetória

para realizar a busca local, pode-se “elevar o nível do oceano” para restringir a custo

computacional da geração de trajetórias e concentrar a busca numa área mais

próxima do ponto central de maior probabilidade.

42

No caso desta pesqusa de mestrado, o parâmetro é a probabilidade de haver um objeto de busca.

66

No trabalho de Lin e Goodrich (2009), a metáfora do aquecimento global foi

utilizada para explorar regiões de máximos locais. No caso de uma busca local

inspirada nessa mesma metáfora, pode-se utilizar esse conceito para priorizar as

regiões de maior probabilidade. No referido estudo, os autores trabalharam com um

distribuição de probabilidades simetricamente distribuída a partir de um ponto de

máximo – como se fosse uma distribuição normal em três dimensões. Como isso

não corresponde a realidade (talvez corresponda apenas num momento inicial da

busca), durante um processo de reflexão, ao longo de um período desta pesquisa de

mestrado, pensou-se no algoritmo de busca local ilustrado na Figura 10.

Essa figura ilustra quatro detecções sucessivas, em que cada detecção

mapeia uma área circular onde será realizada a busca local. Como os pontos estão

próximos uns dos outros, há sobreposições desses mapeamentos (Figura 10.a),

sugerindo que subáreas mais escuras apresentam prioridade na busca local. Dessa

forma, o VANT responsável pela busca local utilizaria o algoritmo de cobertura

completa (ou algum outro) priorizando as áreas mais escuras em cada instante. No

exemplo da Figura 10, as áreas priorizadas seriam as ilustradas pela cor amarela,

nessa ordem, nas Figura 10.b, Figura 10.c, Figura 10.d e Figura 10.e. Como podem

existir mais de uma região com mesma prioridade em cada instante (que é o caso

das Figura 10.c, Figura 10.d e Figura 10.e), também seria necessária uma heurística

para ordenar a busca local nessas regiões.

Apesar de interessante, esse algoritmo apresenta a desvantagem de que,

para se deslocar entre os máximos locais, o VANT perde tempo sobrevoando

células já sobrevoadas. Ou seja, há um desperdício de tempo na busca local.

67

(a)

(b)

(c)

(d)

(e)

Figura 10 – Ilustração do processo de busca local utilizando a metáfora do aquecimento global para

procurar máximos locais.

68


Este capítulo apresentou os principais algoritmos de navegação utilizados na

literatura para a navegação de VANTs. Esses algoritmos foram classificados em

duas “famílias”: algoritmos de navegação ponto-a-ponto e algoritmos de busca local.

Para cada um deles, as principais vantagens e desvantagens foram apresentadas.

Também foi apresentada, na Figura 10, uma proposta de algoritmo de busca

local (para o cenário de busca utilizado nesta pesquisa de mestrado) inspirado no

algoritmo LHC e na metáfora do aquecimento global.

69

6 PROPOSTA

Para propor um modelo de cooperação de VANTs para uma missão de busca,

esta pesquisa se baseou nas recomendações de buscas estabelecidas pelo DECEA,

na teoria multiagentes para obter a coordenação dos VANTs e na avaliação de

algoritmos de navegação. Essa convergência de conceitos está ilustrada na Figura

11.

Assim, cada VANT, modelado como um agente autônomo, utilizará padrões

de busca e algoritmos de navegação para planejar sua trajetória e empregará

mecanismos de coordenação visando a cooperação com os outros VANTs

(agentes).

Figura 11 – Convergência de conceitos para a construção do modelo de VANTs cooperativos

Cabe ressaltar que o modelo de VANTs cooperativos proposto é aderente às

recomendações do Manual Internacional de Busca de Salvamento (sintetizadas na

Figura 4, página 40), que refletem uma busca guiada pela maximização da

70

probabilidade de detecção. A vantagem do modelo proposto é que a atualização das

medidas de probabilidade ocorre de maneira mais dinâmica do que numa operação

de busca que utiliza aeronaves tripuladas.

Além disso, propõe-se a discretização do espaço de busca (subseção 6.1),

que deverá suportar todo o processo de busca, e um modelo de navegação

(subseção 6.2) adequado a essa discretização do espaço de busca. Após todos

esses aspectos terem sido abordados nos capítulos 3, 4 e 5, respectivamente, este

capítulo discorre sobre a combinação desses fatores visando à concepção do

modelo de VANTs cooperativos aplicados a operações de busca.

Por fim, a subseção 6.4 apresenta o modelo em si, detalhando a estratégia de

cooperação dos VANTs, bem como as justificativas para cada escolha realizada.

Porém, antes de apresentar a estratégia de cooperação, foi necessário definir o

cenário de busca para o qual o modelo de VANTs cooperativos foi concebido

(subseção 6.3). Mais adiante, nos capítulos 7 e 8, são apresentados o planejamento

das simulações que visam mostrar o benefício do modelo, bem como os resultados

obtidos, respectivamente.

6.1 Discretização da região de busca

Um dos mecanismos de coordenação propostos nesta pesquisa de mestrado

para a busca cooperativa é o compartilhamento de informações. As informações

mantidas e trocadas representam o conhecimento sobre o ambiente, possibilitando,

portanto, acompanhar a evolução da operação de busca. Sem essa troca de

informações, o conhecimento de cada VANT estaria restrito às informações obtidas

pelos seus próprios sensores.

Portanto, primeiramente foi definida a estrutura das informações que serão

mantidas e trocadas pelos VANTs, ilustrada na Figura 12 – que ilustra, também, o

processo de atualização do conhecimento. A região de busca foi discretizada em

células, e cada célula possui uma medida da probabilidade de conter um objeto de

busca. Assim, a cada troca de informações, os VANTs recebem as informações

71

obtidas por outros VANTs e passam a considerar essas novas informações no seu

planejamento individual de busca. Quando um VANT detecta 43 um objeto, ele

atualiza o seu conhecimento sobre o espaço de busca incrementando o atributo

indicativo de probabilidade44 das células ao redor da célula em que o objeto foi

encontrado. Todas as células já sobrevoadas, como é o caso da célula em o objeto

foi detectado (Figura 12), recebem valor “0” para evitar que sejam sobrevoadas

novamente. Cabe ressaltar, também, que a figura à direita apresenta apenas uma

pequena parte exemplificativa do espaço de busca, que pode conter milhares de

células.

A ideia é que as células com valor maior que zero sejam priorizadas na busca

local, podendo inclusive, haver níveis de prioridade dentro da própria busca local.

Figura 12 – Espaço de busca discretizado e atualização do conhecimento do VANT (CHAVES e

CUGNASCA, 2012a)

43

No simulador desenvolvido nesta pesquisa de mestrado, sempre que um VANT sobrevoar um waypoint (célula do espaço a de busca discretizado) que contém um objeto, esse objeto é considerado detectado. No entanto, outros modelos mais sofisticados poderiam ser empregados para conferir mais realismo à simulação. Por exemplo, levando em conta a taxa de falhas de uma câmera de detecção automática. 44

A medida não representa uma probabilidade em si (de 0 a 1), apenas um indicativo de probabilidade. Ou seja, quanto maior o valor da célula, que é um número inteiro, maior é a chance de essa célula conter um objeto de busca.

72

Aqui, cabe ressaltar que este modelo de VANTs cooperativos trabalha com a

premissa de que quando um VANT sobrevoa uma célula que contém um objeto

perdido ele sempre detecta esse objeto. Ou seja, desconsidera-se a probabilidade

de falha da detecção.

Outra simplificação adotada, também referente à discretização do espaço de

busca e relacionada com a anterior, é que o tamanho, o formato e o tipo do objeto

não são importantes para a detecção. Ou seja, reforçando a simplificação anterior,

basta o VANT sobrevoar a célula contendo objeto que este é detectado.

A discretização em células facilita o planejamento da navegação (gerando um

grafo em que cada célula é um nó), facilita a troca de conhecimento entre os VANTs

(ampliando o conhecimento de cada um) e direciona a busca (possibilitando a

priorização de busca).

De acordo com Chung e Burdick (2008), os métodos probabilísticos são os

mais apropriados para avaliar a evolução da maioria das tarefas de coleta de

informações, pois eles são capazes de representar as imprecisões de informações

do espaço de busca. Nesse trabalho, os autores avaliaram diferentes estratégias de

busca cooperativa considerando a tarefa de procurar um objeto utilizando múltiplos

agentes buscadores e discretizando a área de busca. Nesse estudo, porém, os

agentes não são robôs se movimentando fisicamente no espaço, eles são apenas

sensores capazes de analisar uma célula por unidade de tempo.

A discretização em células foi inspirada no conceito de grade de ocupação

(Occupancy Grid Map - OGM), paradigma muito utilizado na modelagem de robôs

móveis (THRUN et al., 1998). A grade de ocupação é um quadriculado 2D utilizado

para mapeamento de obstáculos no ambiente de operação do robô, em que cada

célula armazena uma informação quantitativa, que está relacionada à probabilidade

da célula estar ocupada (MORAVEC e ELFES, 1985; ELFES, 1989). A utilização

dessa estrutura é bastante útil para aplicações de robôs porque facilita a modelagem

da navegação, planejamento de trajetória, localização e mecanismos anticolisão

(COLLINS, COLLINS e RYAN, 2007).

Luotsinen, Gonzalez e Boeloeni (2004), por exemplo, propuseram um modelo

em que a colaboração de VANTs ocorre pela troca de informações sobre os riscos

existentes na exploração de um ambiente hostil. Para isso, eles também utilizaram o

73

conceito de grade de ocupação, que, sendo compartilhada entres os VANTs, é

utilizada para a identificação de regiões hostis. Assim, essa informação é utilizada

na navegação de cada VANT, de modo a evitar essas regiões. Segundo os autores,

além da grade de ocupação, o principal conceito utilizado na colaboração entre os

VANTs foi o Context Based Reasoning framework (CxBR) (GONZALEZ e AHLERS,

1998), cuja função é modelar o comportamento dos agentes (que exercem papel de

VANT) baseando-se no conhecimento prévio dos agentes e nas suas experiências

adquiridas ao longo da operação. Assim, a cada percepção, o agente define um

conjunto finito de consequências das observações realizadas e atualiza seu

conhecimento. Verifica-se, portanto, que apesar de os autores não mencionarem

explicitamente, a utilização de duas técnicas de coordenação mapeadas no capítulo

4: o compartilhamento de informações e o planejamento multiagente.

Porém, no trabalho de Luotsinen, Gonzalez e Boeloeni (2004), as células não

representam nós no grafo de navegação e os autores não informaram os detalhes

da navegação dos VANTs. Na subseção 6.2, esta pesquisa de mestrado apresenta

o modelo de navegação proposto no modelo de VANTs cooperativos.

Por fim, cabe ressaltar que, apesar de irrelevante para as simulações (pois na

simulação o VANT “enxerga” o ambiente como um simples grafo), foi feita uma

análise quanto ao tamanho da célula. O valor foi obtido levando em conta a altitude

de voo recomendada pelo DECEA para operações de busca e experimentos de

operações de busca utilizando VANTs e o raciocínio está detalhado a seguir.

No experimento realizado por Goodrich et al. (2008), os autores realizaram os

sobrevoos a uma altutide45 de 70 metros e utilizaram uma câmera com amplitude de

40º por 30º. Essa amplitude de visão corresponde a valores encontrados outros

trabalhos (AL-HELAL e SPRINKLE, 2010) e descrições de VANTs comerciais (AIR-

ATTACK.COM). Assim, como o modelo de VANTs cooperativos proposto neste

pesquisa de mestrado utiliza células quadradas, utilizando a menor amplitude de

visão, obter-se-ia um círculo de observação cujo raio é aproximadamente 20 metros,

conforme o cálculo ilustrado na ilustrado na Figura 13 (onde

45

A altitude a ser considerada é a chamada altitude AGL (Above Ground Level), bastante utilizada na aviação e nas ciências da atmosférica. Diferente da altitude medida com relação ao nível médio do mar (a altitude AMSL – above mean sea level), a altitude AGL é medida com relação à superfície abaixo da aeronave. Em determinadas regiões do planeta, a diferença entre as altitudes AGL e AMSL pode ser maior que 500 metros.

74

). No entanto, cabe ressaltar que, no experimento de Goodrich et al.

(2008), utilizou-se uma câmera de baixa resolução (640 x 480). Outros trabalhos

utilizam sistemas óticos com até 90º de amplitude de visão (WEIXIONG, 2009).

Já o Manual de Busca e Salvamento (DECEA, 2009) aponta que a altitude de

voo ideal para buscas de homem ao mar é de 150 metros. Nessa altitude, segundo

os cálculos do DECEA, a largura de varredura46 capaz para detectar pessoas em

buscas visuais seria de aproximadamente 200 metros (aqui observa-se uma

amplitude de visão de aproximadamente 60º). Entretanto, diversos fatores podem

influenciar (isoladamente ou de forma combinada) no cálculo da largura de

varredura, entre outros, é possível destacar os seguintes: tipo do objeto da busca,

visibilidade metereológica; tipo de terreno ou estado do mar; altura do voo; posição

do sol; eficácia dos observadores ou do equipamento de detecção empregado; e

fatores diurnos e noturnos47.

Portanto, utilizando a altitude recomendada pelo DECEA (h = 150 metros) e

considerando a possibilidade de utilizar melhores equipamentos de detecção (com

amplitude ( ) de 50º – valor definido por critério de razoabilidade48), chega-se numa

célula de aproximadamente 100 metros de lado (considerando que a célula deve

estar circunscrita num círculo de observação). Basta, na Figura 13, substituir h (a

altitude de voo) por 150 e fazer , em que é a amplitude de visão da

camera embarcada no VANT. Contudo, vale lembrar que pode haver uma enorme

variedade de combinção de parâmetros, levando a diferentes tamanhos de célula.

46

Ver glossário. 47

Buscas visuais diurnas são mais fáceis de realizar do que buscas visuais noturnas, mesmo em noites claras. 48

Mais do que a amplitude de câmeras simples utilizadas em experimentos acadêmicos (30º) e um pouco menos do que a amplitude utilizada pelo DECEA (60º).

75

Figura 13 – Cálculo do tamanho da célula do espaço discretizado ( é a amplitude da visão da

câmera; ; é a altitude de voo; e é o raio do círculo de observação da câmera).

6.2 Modelagem da navegação

No modelo proposto, a navegação do VANT entre as células se restringe às

direções norte, sul, leste e oeste. Ou seja, no jargão da aviação, os VANTs podem

possuir heading angle de 0º, 90º, 180º ou 270º. Na literatura de computação, diz-se

que esse modelo é um grafo com conectividade-quatro 49 . Esse modelo de

navegação já se mostrou viável para mini-VANTs em alguns trabalhos encontrados

na literatura (LIN e GOODRICH, 2009; SUJIT e BEARD, 2008).

Apesar de ser conhecido o fato de que um VANT de asa fixa não é capaz de

executar uma manobra de rotação de 90 graus em torno do seu eixo, Lin e Goodrich

(2009) apontam que esse modelo é bem próximo das capacidades reais de um

VANT de pequeno porte (mini e micro-VANTs), pois, em voos reais, um VANT faz

uma curva de 90 graus (cobrindo três células) no mesmo tempo de dois

49

Uma navegação em oito direções, com heading angle de 0º, 45º, 90º, 135º, 180º, 225º, 270º ou 315º, seria um grafo com conectividade 8.

76

deslocamentos perpendiculares (também cobrindo três células), conforme ilustrado

na Figura 14. Por exemplo, numa curva de 90 graus à esquerda o VANT deveria

sobrevoar, nessa ordem, as células 1, 2 e 3(e), que corresponderia a dois

deslocamentos perpendiculares (caso isso fosse fisicamente possível). Ademais,

não é demais ressaltar que esse modelo de navegação também é bastante

adequado a VANTs de asas rotativas.

Figura 14 – Modelo de navegação

A ideia é que, sobrevoando o centro de célula, o VANT possa focalizá-la com

uma câmera. Mesmo não sendo possível sobrevoar exatamente o centro da célula,

como acontece numa curva de 90 graus (célula 2 da Figura 14), é possível corrigir

essa limitação física, utilizando uma câmera com rotação em três eixos (mais

conhecida como gimbal camera), mantendo o foco da câmera no centro da célula

onde a curvatura é realizada (GOODRICH et al., 2008). Essa focalização da célula é

ilustrada na Figura 15: a Figura 15.(a) apresenta a célula vista de cima, como se o

observador estivesse dentro do VANT; Figura 15.(b) apresenta uma visão lateral do

VANT focalizando a célula; e a Figura 15.(c) ilustra um exemplo de focalização da

célula utilizando uma gimbal camera, quando o VANT não consegue sobrevoar

exatamente o centro da célula.

77

(a)

(b)

(c)

Figura 15 – Focalização da câmera na célula durante a navegação

Para confirmar a viabilidade do modelo, também foram levantadas

informações da capacidade de curvatura de VANTs com duas empresas fabricantes

de mini-VANTs, uma nacional e outra estadunidense. O levantamento constatou que

esses veículos são capazes de realizar uma curva de 90º empregando um raio de

curvatura de 80 metros, que é suficiente para cobrir três células de 100 metros de

lado cada uma (conforme a Figura 14). Essa dimensão de célula é apropriada à

altitude de voo adequada à detecção de objetos por câmera.

A Figura 14 ilustra o modelo de navegação em que os pontos indicam o

centro das células de destino e as linhas pontilhadas a trajetória ilustrativa do VANT.

A vantagem do modelo de navegação com conectividade 4, em contraposição

ao modelo de conectividade 8 é que ele limita o número de caminhos possíveis,

aumentando, consequentemente, a eficiência do cálculo das rotas. Além disso, ele

facilita a simulação na medida em que todos os deslocamentos entre células possui,

teoricamente, a mesma duração. Por fim, se fosse utilizado a navegação de

conectividade 8, haveria desperdício de recursos quando o VANT empregasse um

deslocamento diagonal entre células, pois apenas duas células seriam cobertas num

tempo maior do que um deslocamento horizontal ou vertical (cuja cobertura também

é de duas células).

78

6.3 Definição do cenário

De acordo com o Manual de Busca e Salvamento do DECEA, no contexto de

operações de busca e salvamento, cenário é o “conjunto consistente de fatos e

previsões que descrevem o que pode ter acontecido aos sobreviventes, desde o

momento do eventual sinistro até o momento presente” (DECEA, 2009).

Além disso, o Manual Internacional de Busca e Salvamento aponta que a

definição do cenário é a base para o planejamento da operação de busca, que deve

ser realizado para cada cenário em particular. Ademais, a definição do cenário é o

primeiro passo depois do estabelecimento dos limites50 (IMO/ICAO, 2003). Portanto,

a definição do cenário é crucial para a construção do modelo de VANTs

cooperativos (aplicados a operações de busca) e, consequentemente, para o

sucesso da operação de busca.

Assim, o cenário em que se baseou o modelo foi o de acidente em alto mar

com o desconhecimento total de qualquer informação sobre sua posição – um dos

cenários de busca mais complexos em operações SAR reais (CENTRO DE

COMUNICAÇÃO SOCIAL DA MARINHA, 2009). No entanto, cabe uma ressalva

sobre uma simplificação adotada em relação aos acidentes reais: aqui, os objetos

são considerados estáticos. Numa situação real, em alto mar, os objetos estão em

constante movimento devido a correntes marítimas e correntes de ar. Essa

movimentação é difícil de simular devido à complexidade do ambiente oceânico, e é

influenciada pela corrente marítima total (composta por corrente oceânica, correntes

de marés e correntes de vento local) e força do vento sobre a superfície dos objetos

(DECEA, 2009), que podem variar de local para local.

Nesse cenário, pressupõe-se conhecido apenas a região onde é possível que

estejam as partes que se espalharam (os limites extremos da busca), representada

pela região retangular na Figura 16. Além disso, utilizou-se uma distribuição

gaussiana para o espalhamento dos objetos a partir de um ponto central

(representado pelos pontos espalhados na Figura 16), conforme o modelo

50

Área que contém todos os possíveis sobreviventes.

79

matemático apresentado na subseção 3.4, que está de acordo com o Manual

Internacional de Busca e Salvamento (IMO/ICAO, 2003).

Figura 16 – Exemplo do cenário de busca. Fonte: (CHAVES, CUGNASCA e NETO, 2012)

Nas simulações, esse modelo de espalhamento foi parametrizado. Assim,

variando o desvio padrão da distribuição normal, é possível obter cenários com

diferentes espalhamentos (com maior, ou menor, densidade). Na definição das

dimensões dos espalhamentos, foram utilizadas informações obtidas de acidentes

reais em alto mar, tais como o acidente do voo 447 da Air France, que, em 2009,

fazia o trajeto Rio-Paris e caiu no Atlântico, matando 228 pessoas. Algumas horas

depois do acidente, o Ministro da Defesa naquela época, Nelson Jobim, deu a

seguinte declaração (FOLHA ONLINE, 2009):

“A FAB [Força Aérea Brasileira] definiu que foram localizados

materiais metálicos e não metálicos (...) pelo [avião] Hércules no

meio do oceano, em um raio de 5 km, a 400 milhas de Fernando de

Noronha, em 9.785 km quadrados de área de busca, o que

confirmam que avião acabou caindo nessa região" (grifo nosso).

80

6.4 Busca cooperativa

Ratificando, então, para obter um modelo de VANTs cooperativos, a proposta

é, discretizando o espaço de busca em células contendo medidas de probabilidades,

combinar padrões de busca estabelecidos pelo DECEA, algoritmos de navegação e

mecanismos de coordenação da teoria multiagentes (Figura 11).

Assim, é possível sintetizar a estratégia de cooperação nos seguintes passos:

1. Escolha de um padrão para iniciar a operação de busca baseado nas

informações disponíveis;

2. Compartilhamento de informações quando há atualizações relevantes;

3. Utilização de algoritmo de navegação para obter deslocamento ponto-a-

ponto;

4. Utilização do algoritmo Cobertura Completa para planejar busca local em

área cuja probabilidade de contar objetos seja maior;

5. Atualização constante do conhecimento e replanejamento da busca local.

Esses passos não precisam, necessariamente, serem realizados nessa

ordem e por todos os VANTs, pois representam apenas os principais eventos que

ocorrem no grupo de VANTs cooperativos. Durante uma operação de busca, cada

VANT escolhe, em determinado momento, o algoritmo de navegação mais

adequado ao seu objetivo individual. Além disso, observa-se que esses passos

possuem inspiração no processo de busca tripulada recomendado pelo Manual

Internacional de Busca e Salvamento, sintetizado na Figura 4 (página 40).

O modelo proposto, que será detalhado de maneira descritiva nas subseções

6.4.1, 6.4.2 e 6.4.3, pode ser sintetizado na Figura 17, que, tomando emprestado

alguns conceitos de modelagem UML (BOOCH, RUMBAUGH e JACOBSON, 2005),

apresenta o modelo destacando três núcleos principais: a verificação do sensor

81

(utilizado em cada célula), a obtenção do próximo waypoint a navegar (também

utilizado em todas as células51) e o planejamento de rota.

Verifica sensor

VANT

Atualiza

conhecimentobrodcast

«extends»

{se encontrou

algum objeto}

«uses»

«uses»

Obtém próximo

waypoint

Planeja rota

... ...

Fila de waypoints

Busca Local

Rotas Paralelas

A*

Gerador de trajetória

«uses»

«uses»

«extends»

«extends»

«extends»

Figura 17 – Arquitetura de implementação do modelo

Este último se subdivide em busca local, utilização do algoritmo A* ou do

padrão de busca Rotas Paralelas, que compõem o gerador de trajetória e que, por

sua vez, alimenta a fila de waypoints. Dessa forma, para obter o próximo waypoint,

basta ler a fila de waypoints. Os geradores de trajetória são acionados com

periodicidade tal, que a fila de waypoints nunca fica vazia. Mesmo que isso ocorra,

os VANTs atuais possuem o mecanismo de orbitar em volta do último waypoint

informado, preservando a segurança da operação.

A verificação do sensor também é feita de modo independente. O VANT

verifica se há objetos em cada célula sobrevoada e atualiza o seu conhecimento. Se

houver detecção de objetos, ele compartilha esse conhecimento enviando-o para os

outros VANTs via broadcast.

51

Numa implementação real, seria interessante identificar os próximos pontos com antecedência suficiente para que o VANT não fique sem próximo waypoint.

82

Observa-se, também, que existe um grande potencial de paralelização. Numa

implementação real, os três ramos da Figura 17 (verificação do sensor, obtenção do

próximo waypoint e planejamento de rota) podem executar em processadores

diferentes, o que é bastante interessante em softwares embarcados.

6.4.1 Varredura inicial

Assim, adotado cenário exposto na subseção 6.3, o padrão de busca

escolhido para iniciar a busca é o Rotas Paralelas. Esse padrão é ideal quando não

se tem informações sobre a localização provável dos objetos, ou seja, quando a

incerteza sobre a localização dos objetos segue uma distribuição uniforme. Nesse

caso, deseja-se uma varredura uniforme. Nessa situação, não cabe utilizar nenhum

algoritmo de navegação, pois não há um ponto de destino e não há informações

suficientes para fazer qualquer busca local, e a varredura uniforme (provida pelo

padrão Rotas Paralelas) maximiza é probabilidade de detecção.

Nesse momento, o objetivo dos VANTs é procurar pistas sobre a localização

do foco do espalhamento. Dessa forma, o espaço de busca é dividido igualmente

entre os VANTs e cada um inicia a varredura pelo padrão Rotas Paralelas pela

célula mais à esquerda e mais inferior da sua respectiva subárea.

Além disso, visando aumentar a velocidade de progressão no cenário em

detrimento da densidade dessa varredura inicial, variações desse padrão de busca

podem ser empregadas. Essas variações foram implementadas e simuladas, cujos

detalhes são descritos nos capítulos 7 e 8 a seguir.

Para realizar a varredura de acordo com esse padrão foi desenvolvida uma

função que, recebendo como parâmetro a posição do VANT no mapa e o

espaçamento ( ), acrescenta ao plano de voo do VANT as 100 próximas células

(waypoints) que este deve sobrevoar – cumprindo o padrão determinado. Assim,

enquanto o VANT se encontra empregando este padrão de busca, ele aciona essa

função periodicamente, de modo a não sobrecarregar muito o processamento no

cálculo dos próximos pontos.

83

Durante essa varredura inicial, não há necessidade de se trocar informações

sobre o mapa discretizado, pois ainda não há nenhuma informação relevante a ser

compartilhada. Os VANTs sabem apenas onde os objetos de busca não estão e,

portanto, devem continuar nesse padrão de busca até, em último caso, completar a

varredura na subárea de sua responsabilidade.

Nessa fase, há predomínio da utilização do padrão de busca Rotas Paralelas,

não sendo utilizados mecanismos de coordenação multiagente e nem algoritmos de

navegação. A Figura 18 ilustra esse planejamento inicial da busca.

Figura 18 – Planejamento inicial da busca cooperativa. Os pontos vermelhos representam os objetos

perdidos, alvos da operação de busca.

6.4.2 Primeira pista encontrada

Quando um dos VANTs detecta o primeiro objeto de busca (Figura 19.a), ele

atualiza o seu conhecimento sobre a área de busca (Figura 19.b), aumentando a

probabilidade das células não visitadas ao redor desse ponto (conforme ilustrado na

84

Figura 12). Nesse momento, há uma nova informação relevante a ser compartilhada.

Então, o mapa discretizado é enviado aos demais VANTs via broadcast52.

(a)

(b)

Figura 19 – Primeira detecção

Nesse momento, não há mais motivo para todos os VANTs continuarem suas

varreduras pelo padrão Rotas Paralelas (que objetiva cobertura uniforme), pois, de

acordo com as características do cenário (definido na subseção 6.3), existem fortes

indícios de que há outros objetos próximos à primeira detecção. Ou seja, sabe-se

que esse objeto está dentro da área de espalhamento do acidente, que obedece

uma distribuição normal (Figura 6, página 46).

Sendo assim, o VANT que detectou o primeiro objeto pode continuar sua

varredura pelo padrão Rotas Paralelas, a fim de encontrar outros objetos que podem

estar por perto. No entanto, não faz sentido que outros VANTs em subáreas

distantes daquela primeira detecção continuem sobrevoando pelo padrão Rotas

Paralelas visando cobertura uniforme nessas subáreas distantes. Então, numa

busca cooperativa de dois VANTs 53 , o VANT que recebeu a atualização do

52

Aqui cabe a ressalva de que não se considerou o tratamento de falhas e atrasos na comunicação entre os VANTs. Assim, quando um dos VANTs atualiza o seu conhecimento, os outros VANTs recebe essa informação instantaneamente. 53

Quando houver mais do que dois VANTs, a escolha de qual VANT deve se deslocar até a célula da primeira detecção poderá ser feita utilizando o mecanismo de coordenação “bidding”, apresentado na

85

conhecimento (a partir de agora chamado de “VANT Ajudante”) se desloca até a

localização da primeira detecção utilizando o algoritmo A*, que, conforme descrito no

capítulo 5 (subseção 5.1), é o mais adequado para a navegação ponto-a-ponto de

VANTs54. Além de ser mais eficiente55 de que o seu predecessor (o algoritmo de

Dijkstra), é bastante flexível – permitindo a personalização para seja implementado

visando economia de combustível, desvio de obstáculos, etc. – e, diferentemente do

algoritmo FVF, gera uma sequência de waypoints (que pode ser facilmente

carregada num VANT).

Durante o deslocamento do “VANT Ajudante”, ele pode sobrevoar subáreas

onde outros VANTs estão realizando varreduras com o padrão “Rotas Paralelas”,

incorrendo em risco de colisão. Para isso, nesse momento é utilizado o mecanismo

de coordenação planejamento multiagente (subseção 4.2.4, página 55), que busca

exatamente a resolução de conflitos entre os agentes.

Sabendo a posição do VANT que encontrou o objeto perdido, seu respectivo

plano de voo (o padrão de busca Rotas Paralelas) e a distância estimada até a

região de maior probabilidade56, o “VANT Ajudante” infere onde o primeiro VANT vai

estar quando o ajudante chegar à região de maior probabilidade. Então, tendo essa

posição inferida (representada pela estrela na Figura 20), o “VANT Ajudante”

classifica essa célula, e por segurança as vizinhas, como células não navegáveis no

grafo utilizado pelo algoritmo A* para calcular a rota ponto-a-ponto mais curta. Dessa

forma, o algoritmo A* gera uma trajetória que evita essas células não navegáveis

(representadas pelas células vermelhas na Figura 20). No exemplo da Figura 20,

essas células não navegáveis não estão entre o “VANT Ajudante” e a região

amarela, por isso a trajetória gerada pelo algoritmo A* é a mais direta possível.

subseção 4.2.2. Em que o VANT que detectou o objeto arbitra um leilão entre os outros VANTs visando escolher aquele que está mais perto e, consequentemente, chegará mais rápido até o local. 54

Conforme descrito no capítulo 5, esse algoritmo é implementado com a utilização de uma heurística que estima a distância do ponto (nó do grafo) em análise até o ponto de destino. Foram testadas duas heurísticas: distância Euclidiana e distância Manhatthan. Observou-se que, o grafo utilizado possui conectividade-4, ambas resultam na mesma distância. Porém, o uso da distância Euclidiana fornece um deslocamento mais linear até o ponto de destino, o que pode favorecer o sobrevoo acidental de algum outro objeto. 55

Em qualquer sistema computacional crítico, como é o caso dos VANTs, a eficiência é crucial para o bom funcionamento e para a segurança (safety). 56

Mais precisamente até a célula onde ocorreu a primeira detecção.

86

Figura 20 – Planejamento Multiagente no cálculo da trajetória utilizando o algoritmo A*. As linhas

tracejadas representam a trajetória planejada dos VANTs.

Ademais, cabe ressaltar que a geração da trajetória pelo A*, desconsiderando

as células estabelecidas como não navegáveis, é realizada antes do início do

deslocamento. Ou seja, foi desenvolvida uma função que, implementando o

algoritmo A* (Figura 8), recebe como parâmetro os pontos de origem e destino, bem

como o grafo navegável que representa o espaço de busca, gera a sequência de

waypoints, que são acrescentados ao plano de voo do VANT e que este deve

cumprir para chegar ao seu ponto de destino.

Portanto, nessa fase percebe-se a utilização do padrão de busca Rotas

Paralelas, do algoritmo de navegação A* e dos mecanismos de coordenação

multiagente Compartilhamento de Informações (subseção 4.2.3) e Planejamento

Multiagente (subseção 4.2.4). Em caso de mais de dois VANTs sendo empregados

na busca cooperativa, poderia ser utilizado um terceiro mecanismo de coordenação

multiagente: o leilão57 (subseção 4.2.2).

57

Bidding.

87

6.4.3 Busca local

Assim, os VANTs seguem seus planos de voo. Um prossegue na varredura

utilizando o padrão de busca Rotas Paralelas e o outro (o “VANT Ajudante”) segue o

plano de voo gerado pelo algoritmo A*.

Quando o “VANT Ajudante” chega à célula de destino (último waypoint da

trajetória fornecida pelo algoritmo A*), ele conclui o plano de voo gerado pelo

algoritmo A* e inicia a busca local pelo algoritmo Cobertura Completa (subseção

5.2). Conforme explicitado nessa subseção, esse algoritmo é mais vantajoso em

relação aos outros porque, diferentemente dos algoritmos de navegação por

gradiente ou o LHC, ele apresenta uma menor tendência de sobrevoar células já

inspecionadas – aumentando, assim, a eficiência de toda a busca local.

O planejamento da busca local se dá pela geração de uma trajetória que varre

exaustivamente a região de maior probabilidade (área amarela da Figura 21) do

espaço de busca (cobrindo todas as células) de baixo para cima e da esquerda para

a direita. É similar à navegação pelo padrão Rotas Paralelas aplicada localmente e

com espaçamento ( ) mínimo.

Figura 21 – Início do planejamento da busca local

88

Para isso, foi desenvolvida uma função que, recebendo como parâmetro a

posição do VANT no mapa e o conhecimento do espaço de busca com a região de

maior probabilidade, acrescenta ao plano de voo do VANT 50 waypoints que este

deve sobrevoar para realizar a busca local – visando sempre sobrevoar as células

da região amarela de baixo para cima e da esquerda para a direita. Assim, enquanto

o “VANT Ajudante” se encontra responsável pela busca local, ele aciona essa

função periodicamente, de modo a não sobrecarregar muito o processamento no

cálculo dos próximos pontos. Além disso, o acionamento periódico permite que o

“VANT Ajudante” replaneje a busca local caso tenha ocorrido alguma atualização do

conhecimento após o último planejamento da busca local.

A Figura 22 apresenta o pseudocódigo do algoritmo da busca local.

Inicialmente, o algoritmo obtém o último waypoint ( , linha 1 da

figura), que nesse momento é a célula onde o VANT se encontra. A partir dessa

célula, utilizando a função (linha 4 da figura), o algoritmo

procura a célula que esteja mais abaixo e mais a esquerda da área de busca local.

Assim, a busca local tende a formar um “zig-zag” de baixo para cima e iniciando da

esquerda para a direita (conforme é ilustrado na Figura 23), minimizando o número

de células sobrevoadas mais de uma vez na busca local. Se essa próxima célula for

vizinha da última célula da fila de waypoints, ela é simplesmente adicionada na fila.

Se não for vizinha, o algoritmo A* ( , linha 9 da figura) é utilizado para gerar

a rota até essa célula.

Figura 22 – Pseudocódigo da implementação da busca local

89

Ademais, no planejamento da busca local, o “VANT Ajudante” se utiliza

novamente do mecanismo de coordenação multiagente Planejamento Multiagente

(subseção 4.2.4). No planejamento da busca local, o “VANT Ajudante” calcula sua

trajetória desconsiderando a linha de células (representada pelas células vermelhas

na Figura 23) que o primeiro VANT está e vai estar em seguida. Dessa forma, o

“VANT Ajudante” busca evitar, pró-ativamente, uma eventual colisão com o VANT

“dono” daquela subárea. Para isso, é necessário que o “VANT Ajudante” receba a

posição do outro VANT. Por fim, além de desconsiderar a linha do VANT “dono” da

subárea, como o algoritmo de busca local (Figura 22) utiliza o algoritmo A*,

eventuais deslocamentos maiores também evitarão colisões.

Figura 23 – Emprego do mecanismo de coordenação Planejamento Multiagente na busca local.

Observa-se, também, que, naturalmente, o VANT que prossegue no padrão

Rotas Paralelas vai detectando outros objetos antes e durante a busca local pelo

“VANT Ajudante”. Na Figura 23, a linha tracejada na cor verde representa a trajetória

planejada do VANT que emprega o padrão Rotas Paralelas e a linha tracejada na

cor preta, a trajetória planejada do “VANT Ajudante” que realiza a busca local.

Portanto, nessa terceira fase da operação de busca (a busca local), observa-

se o emprego do padrão de busca Rotas Paralelas, do algoritmo de navegação de

90

busca local Cobertura Completa (subseção 5.2), do mecanismo de coordenação

Planejamento Multiagente (subseção 4.2.4) para evitar colisões e do mecanismo de

coordenação Compartilhamento de Informações (subseção 4.2.3), que acontece

sempre que há detecções de objetos.


Partindo de discussões e considerações preliminares (discretização do

espaço de busca, modelagem da navegação e definição do cenário), este capítulo

apresentou o modelo de VANTs cooperativos, sintetizado na Figura 17 e detalhado

na subseção 6.4.

No início das buscas, no intuito de maximizar a probabilidade de detecão

(pois, devido à ausência de informação, considera-se que a probabilidade de haver

objetos no cenário se distribui uniformemente) ambos os VANTs adotam o padrão

de busca “Rotas Paralelas”.

Quando um VANT detecta um objeto, ele atualiza e compartilha o seu

conhecimento. Aqui, é o mecanismo de coordenação “compartilhamento de

informações” que é acionado (subseção 4.2.3).

Ao receber essa informação, o outro VANT a recebe como se fosse um

pedido de ajuda e altera o seu planejamento de rota acionando o algoritmo A* para

navegar até a região onde o primeiro objeto foi encontrado (mecanismo simplificado

de coordenação “acordos bilaterais” – subseção 4.2.2).

Então, no acionamento do algoritmo A*, o “VANT Ajudante”, conhecendo o

padrão de navegação do primeiro VANT (que continua no padrão de busca “Rotas

Paralelas” até o final da busca), estima a posição onde este vai estar (região de

possível colisão) e atribui a este nó (célula), e aos vizinhos, a condição de nós não

navegáveis. Assim, o algoritmo A* gerará uma trajetória desviando dessa região.

Aqui, há a implementação do mecanismo de coordenação “planejamento

multiagente” (subseção 4.2.4). Este mecanismo também é implementado da mesma

forma durante a busca local.

91

7 SIMULAÇÕES

Para simular a operação de busca, foi desenvolvido um programa utilizando a

linguagem de programação Java (ORACLE, 2012), utilizando plataforma de

desenvolvimento NetBeans 7.0 (NETBEANS.ORG, 2012). O código desenvolvido

permite que as principais variáveis do cenário sejam parametrizadas por meio de um

arquivo de configuração:

Número de objetos espalhados;

Desvio padrão do espalhamento gaussiano58 dos objetos a partir de um

ponto sorteado aleatoriamente;

Espaçamento da busca local utilizando o padrão Rotas Paralelas

(distância S da Figura 24);

Raio de atualização do conhecimento;

E informações sobre arquivos de saída.

Essa característica, aliada a construção de arquivos batch (que executam

automaticamente vários cenários de simulação, N vezes cada um) e a geração

automática de uma planilha contendo as informações relevantes de cada uma das

simulações, acelerou o processo de geração e compilação dos resultados. Por meio

da edição dos arquivos de configuração de cada bateria de simulação e de arquivos

batch, vários cenários puderam ser executados com apenas um comando.

O programa simulador também permite que, ao final de cada simulação, seja

gerada uma imagem da respectiva operação de busca em seu instante final (com os

objetos, a área de maior probabilidade extraída do conhecimento dos VANTs e as

trajetórias dos VANTs). Há duas possibilidades da geração da foto: por geração de

comandos 59 para plotagem no MatLab (MATHWORKS®, 2012); ou a geração

automática de imagens com extensão .png. Esta última foi desenvolvida

posteriormente para aumentar a qualidade das imagens, que estava deixando a

58

A implementação também permite a utilização de outros tipos espalhamentos. O espalhamento uniforme já está implementado. 59

Basicamente, os comandos utilizados são os seguintes: contour, scatter e plot.

92

desejar na primeira opção. Portanto, apesar de a geração de comandos para

plotagem no MatLab não ter sido muito utilizada nas simulações para coleta de

resultados, ainda é possível e pode ser explorada caso se necessite personalizar os

comandos de modo a atender eventuais necessidades pontuais.

Além disso, por meio da serialização de objetos (DEITEL, 2004, p. 697-706) –

que nada mais é do que a persistência de objetos em arquivos de texto –, o

programa permite salvar os cenários utilizados em arquivos de texto. Assim, esses

cenários salvos podem, posteriormente, ser carregados pelo programa para repetir

determinadas simulações, pois como os objetos são espalhados de maneira

aleatória, a repetição de cenários só é possível por meio da persistência dos

cenários. Essa característica do programa foi muito útil durante o processo de

desenvolvimento e depuração do simulador, na medida em que os erros observados

puderam ser reproduzidos quantas vezes foram necessárias.

As características da máquina onde foram realizadas as simulações são as

seguintes:

Sistema Operacional: Windows Vista (32 bits);

Processador: Intel Core 2 Duo (2,10 GHz);

Memória RAM: 3 GB de memória RAM.

Por fim, cabe ressaltar que, com o intuito avaliar a robustez da simulação, foi

implementado no programa simulador, a utilização de um algoritmo gerador de

números pseudoaleatórios mais robusto que o algoritmo nativo fornecido pela

linguagem Java: o algoritmo Mersenne Twister, desenvolvido por Matsumoto e

Nishimura (1998) – um dos algoritmos geradores de números pseudoaleatórios mais

robustos e utilizados na literatura. Apenas para ilustrar o poder desse algoritmo, os

autores afirmam que seu período de repetição é 219937, enquanto a função

random() da linguagem Java possui período de 248. Esse período de 248 é

considerado bastante curto (COFFEY, 2009), principalmente para aplicações

científicas que utilizam combinações de valores – por exemplo, coordenadas –

(COFFEY, 2010), que é o caso do simulador concebido e desenvolvido nesta

pesquisa de mestrado.

93

Em outra oportunidade60, observou-se que algoritmos muito dependentes da

geração de números pseudoaleatórios tiveram um grande ganho em qualidade com

a adoção do Mersenne Twister. Como o modelo de VANTs cooperativos utiliza

números pseudoaleatórios para o sorteio de cada objeto, N objetos são espalhados

em cada simulação, 600 simulações são realizadas para cada parametrização em

cada cenário e cada cenário pode ter até dez parametrizações (totalizando até 6.000

simulações por cenário de simulação), achou-se conveniente utilizar o Mersenne

Twister como algoritmo gerador de números pseudoaleatórios. De fato, observou-se

mais robustez nos resultados. No simulador, foi utilizada a implementação do

algoritmo desenvolvido por Luke (1999) para a linguagem Java.

Por fim, cabe ressaltar que outros simuladores, bem como plataformas de

simulação (GIL et al., 2010; UNMANNED DYNAMICS, 2009; GARCIA e BARNES,

2010), foram avaliados e decidiu-se pelo desenvolvimento de um simulador próprio

devido à maior flexibilidade que se alcançaria nas simulações. Mais detalhes sobre

simuladores podem ser encontrados em Gil (2011), faz um levantamento sobre os

principais simuladores de voo.

Nas subseções a seguir, os cenários de simulação definidos são

apresentados (subseção 7.1) e a análise estatística para identificar o número de

simulações necessário, de forma que a medida obtida seja um resultado

estatisticamente válido, é apresentada (subseção 7.2).

7.1 Cenários simulados

Primeiramente, cabe ressalvar que o cenário de busca utilizado (definido da

subseção 6.3 do capítulo 6), bem como as simplificações adotadas, foi o mesmo

para todos os cenários de simulação: um acidente em alto mar com espalhamento

gaussiano de objetos. Esta subseção trata apenas dos cenários de simulação.

Esses cenários foram selecionados com o intuito de examinar o benefício do

modelo proposto de VANTs cooperativos e realizar a análise de sensibilidade dos

60

No desenvolvimento de uma meta-heurística sem conexão com esta pesquisa de mestrado.

94

parâmetros envolvidos. Assim, baterias de simulações foram planejadas para cada

um desses cenários. A Tabela 2 lista esses cenários de simulação, cada um com os

respectivos objetivos na coluna da direita. Na apresentação dos resultados, no

capítulo 8, esses cenários são discutidos em mais detalhes.

Tabela 2 – Análises pretendidas

Cenários Objetivos da análise

1 Simulação com um

VANT não cooperativo Ter uma medida de referência para comparar com as buscas cooperativas.

2 Simulação com dois

VANTs não cooperativos

Comparar o cenário simples com a simulação com dois VANTs não cooperativos e ter uma medida de referência para comparar com as buscas cooperativas.

3

Sim

ula

çõe

s c

om

dois

VA

NT

s c

oo

pera

tivo

s

Variação do espaçamento (S) do padrão “Rotas

Paralelas”

Apresentado na subseção 3.3, o padrão de busca “Rotas Paralelas” provê uma varredura com determinada densidade, que pode ser variada de acordo com a situação. Apesar de se correr o risco de não cobrir um espaço que contenha objetos de busca, uma cobertura menos densa apresenta progressão mais rápida. Assim, pode-se chegar mais rápido na região onde se encontram os objetos espalhados. A ideia desse cenário de

simulação é variar a distância ilustrada na Figura 24 e observar o efeito na redução do tempo de busca.

4

Variação do raio de atualização (R) do conhecimento do

VANT na detecção de objetos

Avaliar a sensibilidade do raio de atualização do conhecimento do VANT. Representado pelo símbolo R, essa distância é o raio do círculo que em que as células pertencentes são atualizadas quando ocorre uma detecção do objeto – processo ilustrado na Figura 12.

5 Variação do

número de objetos de busca

Analisar, no que diz respeito ao número dos objetos de busca, em que tipo de cenário o modelo de VANTs cooperativos agrega mais benefício à operação de busca. Ou seja, variar o número de objetos de busca e observar o efeito.

6 Variação do

espalhamento dos objetos de busca

Analisar, no que diz respeito ao espalhamento dos objetos de busca, em que tipo de cenário o modelo de VANTs cooperativos agrega mais benefício à operação de busca. Ou seja, variar o raio de espalhamento dos objetos de busca e observar o efeito.

95

Figura 24 – Variação do espaçamento61

no padrão de busca “Rotas Paralelas” (CHAVES e

CUGNASCA, 2012b)

7.2 Análise estatística

Antes de iniciar as simulações, visando obter um resultado estatisticamente

confiável, é preciso realizar uma análise estatística para calcular o número suficiente

de simulações para que a média do tempo de busca seja calculada. Assim, a análise

estatística se concentrou na principal variável envolvida: a média do tempo de busca

medido em simulações. Essa medida é calculada por:

(1)

em que é o tempo da busca obtido na i-ésima simulação (medido em número de

células navegadas) e é o número de simulações realizado. Cabe ressaltar que,

estatisticamente falando, a média calculada é a média amostral, que visa ser uma

estimativa da média populacional (ver Figura 41, página 139).

Então, primeiramente, foi feita uma análise gráfica visando observar a partir

de qual simulação essa média se mantém estável. Isso indica quantas simulações

são necessárias para estimar a média populacional com razoável grau de confiança.

61

Ver definição do DECEA no glossário.

96

Nessa análise, observa-se quando a média acumulada não se altera mais ou se

altera pouco.

O número de simulações necessárias para obter uma medida robusta pode

ser obtido por meio da análise do gráfico de evolução da média (Figura 25), que

indica, no eixo horizontal, as simulações e no eixo vertical a média acumulada do

número de células navegadas em cada simulação por cada um dos VANTs. A média

acumulada foi calculada da primeira simulação até a k-ésima – obtida pela equação

(1), página 95. Observa-se que aproximadamente a partir da 250ª simulação o

número médio de células navegadas começa a se estabilizar em aproximadamente

2.000 células navegadas por cada VANT, o que equivale a 40% do espaço de

busca.

Figura 25 – Análise gráfica para obtenção do número de simulações necessárias com a evolução da

média do número de células navegadas até a detecção de todos os objetos.

As 1.000 simulações da Figura 25 foram realizadas utilizando as

configurações do caso mais simples do cenário de simulação 3 da Tabela 2 (S=1,

R=1.000 metros, 20 objetos e = 500 metros). Essa configuração foi selecionada

porque se observou que nesta configuração há grande desvio padrão (calculado,

para as 1.000 simulações, em 1.030 – equivalente a 52% da média), maior do que

os observados empiricamente em outros cenários de simulação. Dessa forma,

1.000

1.200

1.400

1.600

1.800

2.000

2.200

2.400

2.600

2.800

Número da simulação

Média do número de células navegadas

97

conforme detalhado no APÊNDICE A – Estimação de parâmetros –, mais

especificamente na equação (8), página 141, esse pode ser considerado um dos

piores casos no que diz respeito ao número de simulações necessárias para se

obter uma média estatisticamente confiável. Sendo assim, o número de simulações

necessárias foi calculado para esse cenário e considerou-se que esse número seria

suficiente também para os outros casos.

Porém, essa análise tem a desvantagem de que não é possível quantificar

quão confiável é a medida obtida e necessita de muitas simulações para afastar a

possibilidade de haver falsa percepção de estabilidade. Portanto, é preciso ter

cuidado para obter graficamente o número de simulações necessárias.

Nessa situação, uma abordagem poderosa que pode ser utilizada é a teoria

da estimação de parâmetros da estatística, que, levando em conta a média amostral

obtida (representada pelo símbolo na estatística), busca-se estimar a média

populacional (representada pelo símbolo na estatística). Essa estimativa permite a

o cálculo do número de simulações (tamanho da amostra) que fornece determinado

grau de confiança à medida. Assim, sabe-se qual é o grau de certeza da estimativa

da média populacional ( ).

Utilizando a teoria de estimação de parâmetros da estatística (APÊNDICE A –

Estimação de parâmetros), obtêm-se, com grau de confiança de 95% e permitindo

um erro de 10062, que são necessárias 455 simulações para estimar a média de

células navegadas. Esse número é compatível com a análise gráfica apresentada na

Figura 25. Por segurança, e por não representar aumento excessivo no tempo de

simulação, cada configuração de cada cenário de simulação foi simulada 600 vezes.


Neste capítulo, apresentou-se o simulador desenvolvido durante a pesquisa

de mestrado para testar o modelo proposto, os cenários de simulação planejados

para avaliar a sensibilidade dos parâmetros do modelo e, por fim, a análise

62

100 células navegadas – equivalente a 2% do cenário, para cada VANT.

98

estatística realizada para obter o número de simulações necessário para que a

média obtida seja um resultado válido.

Mais detalhes sobre a análise estatística podem ser obtidos no APÊNDICE A

– Estimação de parâmetros. A seguir, no capítulo 8, os resultados obtidos são

apresentados de discutidos.

99

8 ANÁLISE DOS RESULTADOS

Este capítulo está dividido em subseções, em que cada uma apresenta e

analisa os resultados de cada cenário. Em cada cenário, variou-se um dos

parâmetros, fixando os outros. O balanço geral sobre as conclusões das simulações

de cada cenário e a conclusão da pesquisa são apresentadas no capítulo 9.

Em cada simulação, tanto o número de células navegadas (indicativo do

tempo de busca) quanto o número de objetos detectados foram registrados. Assim,

a análise de sensibilidade foi realizada sob o enfoque dessas duas medias.

Além disso, nas simulações, considerou-se a busca encerrada quando todos

os objetos eram detectados ou quando o “VANT Ajudante” varria toda a área da

busca local. Neste último caso, mesmo havendo objetos ainda não detectados, por

não haver mais células para efetuar a busca local, também se deu por encerrada a

operação de busca.

Assim, para cada variação de parâmetro, calculou-se a média do número de

objetos detectados (considerando todas as 600 simulações) e a média do número de

células percorridas. Neste último caso, consideraram-se apenas as simulações em

que todos os objetos foram detectados, pois não faria sentido comparar simulações

bem sucedidas com simulações mal sucedidas ou parcialmente bem sucedidas.

8.1 Cenário 1 – um VANT não cooperativo

Nesta análise, tentou-se simular uma operação de busca de um único VANT,

que, não sabendo da provável posição do acidente, empregaria apenas o padrão de

busca Rotas Paralelas. Como apenas esse padrão é utilizado, variou-se o

espaçamento e observou-se o efeito. O espaçamento é medido em número de

células, conforme ilustrado na Figura 26.

100

Figura 26 – Ilustração dos espaçamentos S=1 e S=2

Aqui, não faz sentido construir o gráfico de evolução do tempo de busca, pois

somente para S=1 é que todos os objetos são encontrados. Assim, como a

simulação é interrompida quando todos os objetos são encontrados, somente para

S=1 é que se pode calcular a média do tempo de busca – cujo valor obtido foi 5.392

células navegadas, com desvio padrão de 2.622. Para os demais valores de S, o

VANT não encontra todos os objetos e, por isso, a busca é encerrada apenas

quando toda a área é varrida, resultando sempre o mesmo número de células

navegadas.

A Figura 27 apresenta a porcentagem média de objetos detectadas (no eixo

vertical) pela variação do espaçamento do padrão de busca Rotas Paralelas (eixo

horizontal). Observa-se que os valores obtidos são bem próximos dos valores

teóricos. Ou seja, para S=2, tem-se uma cobertura de 50% das células no padrão

RT 63 , logo, detecta-se 50% dos objetos; para S=3, tem-se uma cobertura de

aproximadamente das células no padrão RT, logo, detecta-se aproximadamente

dos objetos; e assim sucessivamente.

63

Para cada duas linhas de células, uma é sobrevoada (Figura 26).

101

Figura 27 – Porcentagem média de objetos detectados pela variação do espaçamento do padrão de

busca Rotas Paralelas, utilizando uma aeronave não cooperativa

8.2 Cenário 2 – dois VANTs não cooperativos

Analogamente ao cenário 1 (subseção 8.1), aqui também foi variado o

espaçamento do padrão de busca RT e também não faz sentido construir o gráfico

de evolução do tempo de busca, pois somente para S=1 é que todos os objetos são

encontrados – cuja média obtida do número de células percorridas foi de 3.527, com

desvio padrão de 1.221.

A Figura 28 apresenta a porcentagem média de objetos detectados pela

variação do espaçamento. Assim como no cenário 1, os valores obtidos foram bem

próximos dos valores teóricos.

0%

10%

20%

30%

40%

50%

60%

70%

80%

90%

100%

Po

rcen

tag

em

méd

ia d

e o

bje

tos

dete

cta

do

s

102

Figura 28 – Porcentagem média de objetos detectados pela variação do espaçamento do padrão de

busca Rotas Paralelas, utilizando duas aeronaves não cooperativas.

Todos os próximos cenários envolveram simulações de VANTs cooperativos

utilizando o modelo apresentado no capítulo 6.

8.3 Cenário 3 – variação do espaçamento (S)

Nas simulações variando o espaçamento (S) do padrão de busca Rotas

Paralelas, fixou-se raio de atualização do conhecimento64 em 1.000 metros65, duas

vezes o desvio padrão utilizado do espalhamento gaussiano dos objetos (500

metros), e variou-se o espaçamento de 1 a 10. No entanto, com o intuito de encurtar

o tempo de simulação, a partir da sexta medida de espaçamento (S=6) foram

utilizadas medidas mais esparsas, ou seja, pularam-se as parametrizações S=7 e

S=9. Para cada valor de espaçamento observado, foram realizadas 600 simulações.

64

Distância máxima do objeto detectado às células atualizadas, conforme ilustrado na Figura 12 e detalhado na subseção 8.4. 65

Medida que se mostrou mais vantajosa, conforme descrito na subseção 8.4. O cenário 4 foi simulado antes do cenário 3, mas este foi apresentado antes daquele para facilitar a leitura e a comparação com os cenários 1 e 2.

0%

10%

20%

30%

40%

50%

60%

70%

80%

90%

100%

Po

rcen

tag

em

méd

ia d

e o

bje

tos

dete

cta

do

s

103

Cabe ressaltar, também, que o espaçamento está sendo apresentado em

número de células, ou seja, utilizando uma célula de 100 metros de lado (subseção

6.2), S=1 indica que o espaçamento é de 100 metros, S=2, 200 metros, e assim por

diante.

Observando as medidas obtidas e compiladas, verifica-se que, aumentando o

espaçamento, a probabilidade de detecção dos objetos de busca (Figura 29)

aumenta levemente de S=1 para S=2, se mantém estável (bem próxima dos 100%)

até o espaçamento S=4 e tende a cair a partir daí.

Figura 29 – Porcentagem média de objetos encontrados pela variação do espaçamento (S)

O pequeno aumento de S=1 a S=3 (principalmente de S=1 para S=2) pode

ser explicado observando o que acontece quando há somente uma detecção

(ilustrada na Figura 36.b – subseção 8.4, página 110). Como a busca é encerrada

quando o “VANT Ajudante” “consome” toda a região de busca local, ou quando

todos os objetos são encontrados, esse tipo de situação, em que há um objeto muito

distante e abaixo66 do foco de espalhamento, pode fracassar67 a busca porque o raio

de atualização do conhecimento (R) não será suficiente para levar o “VANT

Ajudante” até os outros objetos. Assim, se o raio de atualização do conhecimento for

66

Como nas simulações o padrão de busca Rotas Paralelas varre sempre de baixo para cima, se o objeto afastado estivesse acima do foco de espalhamento não teria problemas, ou pelo menos seria menos prejudicial à busca. 67

No sentido de reduzir drasticamente o número de objetos detectados naquela operação de busca.

50%

55%

60%

65%

70%

75%

80%

85%

90%

95%

100%

104

menor que a distância desse primeiro objeto encontrado até algum outro objeto, e o

VANT que prossegue na varredura pelo padrão Rotas Paralelas não detectar

nenhum outro objeto antes da conclusão da busca local pelo “VANT Ajudante”, este

último não será capaz de encontrar nenhum outro objeto e a busca se dará por

finalizada com apenas um objeto detectado, conforme ilustrada na Figura 36.b.

Pela análise da Figura 30, que no eixo vertical indica a porcentagem média de

células navegadas dentro do cenário (medida indicativa de tempo) pela variação do

espaçamento, no eixo horizontal, observa-se que também há uma tendência de

redução do número médio de células sobrevoadas e, consequentemente, no tempo

de busca. No entanto, a partir do espaçamento S=3, verifica-se uma tendência de

estabilização nesse tempo em aproximadamente 30% de células do cenário

sobrevoadas.

Figura 30 – Porcentagem de células navegadas do cenário pela variação do espaçamento (S)

Inicialmente, no decorrer desta pesquisa de mestrado, a observação dessa

estabilização causou estranheza. No entanto, suspeitando de que uma das fases de

busca pudesse estar sendo o gargalo da busca, o simulador foi alterado para

registrar, também, o número de células sobrevoadas em cada fase da busca:

varredura inicial (subseção 6.4.1), deslocamento ponto-a-ponto (subseção 6.4.2) e

busca local (subseção 6.4.3).

0%

5%

10%

15%

20%

25%

30%

35%

40%

45%

50%

105

Então, as simulações foram realizadas novamente e, conforme apresentado

na Figura 31, a suspeita foi confirmada. O tempo da fase de varredura inicial (barras

azuis) tende a reduzir rapidamente. Já o tempo da fase de deslocamento utilizando o

algoritmo A* (barras vermelhas), como era de se esperar, se mantém estável. Em

relação ao tempo dedicado à busca local (barras verdes), observa-se que a partir do

segundo espaçamento (S=2) essa fase passa a ser a mais fase da operação de

busca.

Figura 31 – Porcentagem de células navegadas pela variação do espaçamento (S) com distinção de

fases. Barras azuis: fase de varredura inicial; barras vermelhas: fase de deslocamento ponto-a-ponto;

barras verdes: fase de busca local.

A considerável redução observada no tempo dedicado à varredura inicial se

deve ao fato de que, considerando um ponto no cenário, para chegar a esse ponto

utilizando o padrão Rotas Paralelas com S=2, um VANT precisa de metade do

tempo do que precisaria utilizando o mesmo padrão de busca com S=1. Também

comparando com S=1, esse tempo seria reduzido à terça parte utilizando S=3. Vale

lembrar que, conforme já tratado (Figura 29), um espaçamento maior possui o efeito

colateral de contribuir para reduzir a probabilidade de detecção.

O crescimento no tempo dedicado à busca local é explicado pela necessidade

de que o “VANT Ajudante” tem de se deslocar para diferentes partes da área de

0%

5%

10%

15%

20%

25%

30%

35%

40%

45%

50%

106

busca local, sobrevoando, assim, mais de uma vez uma mesma célula pertencente a

essa área. Ou seja, para S=1, o “VANT Ajudante” fará a busca local sobrevoando a

área correspondente em “zig-zags” sempre em direção ao norte, pois, para S=1, o

primeiro objeto detectado será sempre o objeto mais abaixo e não haverá células

não sobrevoadas abaixo da posição da primeira detecção. Assim, para S=1, a

operação de busca sempre encontra todos os objetos e, por isso, é finalizada

quando o último objeto é detectado (Figura 32.a).

Já para espaçamentos maiores, há situações em que o primeiro objeto

detectado está no meio do foco de espalhamento. Então, a busca local, que se inicia

de baixo para cima a partir do ponto da primeira detecção, não é tão organizada

quanto a que ocorre para S=1. À medida que mais objetos são detectados, a área da

busca local vai aumentando de tamanho e, muitas vezes, o “VANT Ajudante” precisa

sobrevoar algumas células mais de uma vez para se deslocar até uma célula que foi

“deixada para trás” pela varredura inicial dos VANTs, pois aqui essa varredura é

menos densa e não varre todas as células. Isso tende a ocorrer menos para

espaçamentos menores – não acontecendo para S=1.

(b) (a)

Figura 32 – Instante final da operação de busca. (a) Utilizando espaçamento S=1; (b) Utilizando

espaçamento S=3.

107

A Figura 32 ilustra o instante final de duas simulações de buscas deste

cenário. Conforme pode ser observado, há maior ocorrência de sobrevoos em

células já visitados na Figura 32.b.

Além disso, por haver maior ocorrência de células afastadas (e mais abaixo

do foco de espalhamento) não serem detectadas na varredura inicial, a operação de

busca só termina quando a área da busca local é inteiramente consumida – situação

também ilustrada na Figura 32.b.

Portanto, diante do que foi exposto nesta subseção conclui-se que, em

relação ao tempo de busca, o “gargalo” de uma operação de busca é a fase de

busca local. Ademais, para cada configuração de cenário, existe uma configuração

do parâmetro de espaçamento (S) que traz mais benefícios à operação de busca.

No cenário simulado 68 , os valores de espaçamento que fornecem a melhor

configuração (provendo probabilidade máxima de detecção de objetos e menor

tempo de busca) são S=3 e S=4.

Vale lembrar que esses valores se referem à distância ilustrada na Figura 33

contada em número de células. Utilizando esses valores de espaçamento, a

varredura inicial pelo padrão Rotas Paralelas provê uma cobertura de 33,3%69 e

25%, respectivamente. Mesmo assim, a porcentagem média de objetos detectados

atinge quase 100% com apenas 30%, aproximadamente, das células do cenário

sobrevoadas.

Figura 33 – Melhor parametrização do espaçamento.

68

Espalhamento de 20 objetos, com desvio padrão de 500 metros e raio de atualização (R) de 1.000 metros. 69

Ou seja, para cada três linhas de células, apenas uma é sobrevoada.

108

8.3.1 Comparação dos cenários 1, 2 e 3

Primeiramente, comparou-se o benefício de se empregar duas aeronaves não

cooperativas ao invés de apenas uma utilizando a estratégia de busca simples –

que, como não se sabe onde estão os destroços e não há cooperação, emprega-se

apenas o padrão Rotas Paralelas (Figura 34).

(a)

(b)

Figura 34 – Ilustração do cenário 1 (figura a) e do cenário 2 (figura b)

É claro que, a depender da localização do foco de espalhamento dos objetos,

uma busca com duas aeronaves não cooperativas pode levar tanto tempo quanto

uma busca que emprega apenas uma aeronave, ou até mais. Mas, na média,

quando se utiliza duas aeronaves, tem-se um ganho de 35% em relação ao tempo

de busca – que é medido em unidades (uma unidade é o tempo necessário para

sobrevoar 100 metros: de uma célula a outra). Além disso, há uma redução de 53%

no desvio padrão do tempo de busca, o que também é bastante benéfico à operação

de busca, na medida em que o tempo de busca torna-se mais previsível e, portanto,

pode-se planejar melhor o plano de salvamento. A Tabela 3 apresenta as medidas

obtidas.

109 Tabela 3 – Tempos de busca dos cenário 1 e 2

Tipo da busca Média do tempo

de busca Porcentagem média de

células sobrevoadas Desvio padrão

Uma aeronave 5392 54% 2622

Duas aeronaves não cooperativas

3527 71%70

1221

Num segundo momento, comparou-se apenas o cenário 2 com os valores

obtidos no cenário 3 (utilizando a cooperação) – pois não seria razoável comparar

valores obtidos utilizando duas aeronaves com valores obtidos utilizando apenas

uma e, além disso, tanto no cenário 2 quanto no cenário 3, houve variação do

espaçamento (S). Assim, obtém-se a Tabela 4. Observa-se que, com o mesmo

número de aeronaves e utilizando o modelo VANTs cooperativos, pode-se obter

uma redução de até 57% no tempo de busca, apenas variando o espaçamento (S).

Tabela 4 – Comparação do tempo de busca de uma busca cooperativa com uma não cooperativa

Tipo da busca Média do tempo

de busca Redução em relação à busca não cooperativa

Duas aeronaves não cooperativas 3527 -

VANTs cooperativos (cen. 3 - S=1) 2011 43%






A Figura 35 contrapõe a variação no tempo de busca (linha azul – eixo vertical

da esquerda) com a variação na porcentagem média do número de objetos

detectados (linha vermelha – eixo vertical da direita), ambos pela variação do

espaçamento do padrão Rotas Paralelas. Verifica-se que realmente há grande

70

Mesmo sobrevoando mais células, o tempo é menor porque as células sobrevoadas são divididas em dois VANTs.

110

redução no tempo de busca sem perda significativa na probabilidade de detecção

(até S=6).

Figura 35 – Variação no tempo de busca (linha azul) e variação na porcentagem média do número de

objetos detectados (linha vermelha), ambos pela variação do espaçamento (S)

8.4 Cenário 4 – variação do raio de atualização do conhecimento (R)

Aqui, as simulações realizadas tiveram como objetivo a avaliação do

parâmetro R (raio de atualização do conhecimento quando se detecta um objeto).

Por exemplo, considerando uma célula de 100 metros, o raio de atualização do

conhecimento ilustrado na Figura 12 (subseção 6.1, página 70) é de 200 metros.

Esse parâmetro, se pequeno demais, pode fazer com que a atualização do

conhecimento não seja suficiente para que a região de maior probabilidade conduza

o “VANT Ajudante” a outros objetos perdidos. Por outro lado, se grande demais,

esse parâmetro pode aumentar demasiadamente a área de busca local,

aumentando, assim, o tempo da busca. A Figura 36.a ilustra uma situação hipotética

em que se o raio de atualização fosse um pouco menor que R a atualização (D1) do

conhecimento não seria suficiente para encontrar os outros objetos. A Figura 36.b

0%

10%

20%

30%

40%

50%

60%

70%

80%

90%

100%

0

1.000

2.000

3.000

4.000

5.000

6.000

Po

rcen

tag

em

méd

ia d

e o

bje

tos

dete

cta

do

s

Tem

po

de b

usca

111

ilustra uma situação observada em uma das simulações em que um raio de

atualização reduzido levou a busca a detectar apenas um objeto.

(b) (a)

Figura 36 – Influência do raio de atualização do conhecimento (a) e ilustração de uma busca com

uma única detecção (b). [Adaptado de Chaves e Cugnasca (2012b)]

A Figura 37 mostra a análise obtida por simulações do modelo variando o raio

de atualização do conhecimento (R). Aqui também, para cada simulação, foi

sorteado um ponto e espalhou-se 20 objetos ao redor desse ponto com uma

distribuição gaussiana de desvio padrão de 500 metros. Em relação ao

espaçamento do padrão de busca Rotas Paralelas, foi utilizado S=1.

Pela análise dos gráficos, pode-se concluir que a probabilidade de detecção

dos objetos é mais sensível à variação do parâmetro R do que o tempo médio

(número de células navegadas) empregado na busca. A Figura 37.a mostra que,

aumentando o raio de atualização, existe uma tendência de crescimento linear no

tempo de busca. Apesar dessa observação não ter sido imaginada de início,

revisitando essa figura (Figura 37.a) depois de todas as simulações realizadas, essa

constatação parece intuitiva. Isso porque o aumento do R aumenta marginalmente a

área da busca local e, consequentemente, o número de células navegadas.

D1

D2

D3

D4

R

112

Em relação à probabilidade de detecção dos objetos (média de objetos

detectados), observou-se uma grande sensibilidade nessa medida entre R=300 e

700 metros, e uma menor sensibilidade para R maior que 700 metros, chegando a

quase 100% de detecção para R maior ou igual a 1.000 metros Figura 37.b.

(a) Média do número de células percorridas.

(b) Média do número de objetos detectados.

Figura 37 – Análise da variação do raio de atualização do conhecimento (R)

0%

5%

10%

15%

20%

25%

30%

35%

40%

45%

50%

Méd

ia d

e c

élu

las p

erc

orr

idas

0%

10%

20%

30%

40%

50%

60%

70%

80%

90%

100%

Po

rcen

tag

em

méd

ia d

e d

ete

cção

113

8.5 Cenário 5 – variação do número de objetos (n)

Para avaliar a sensibilidade do modelo em relação ao número de objetos,

foram realizadas simulações utilizando cenários pequenos (espalhando 20 objetos),

cenários médios (com 50 objetos) e cenários grandes (com 100 objetos).

Essa classificação (pequeno, médio, grande) foi baseada em dados de

acidentes reais – mais especificamente do acidente ocorrido com o voo 447 da Air

France (CENTRO DE COMUNICAÇÃO SOCIAL DA MARINHA, 2009). Nesse

acidente, foram encontrados 600 objetos em 26 dias. Como esse número

corresponde a várias operações de busca realizadas durante os 26 dias, considerou-

se razoável que uma única busca de 100 objetos seria um cenário grande, 50

objetos seria um cenário médio e com 20 seria um cenário reduzido.

Para avaliar a sensibilidade do modelo em relação ao número de objetos

espalhadas, foram realizadas 600 simulações 71 para cada configuração de

parâmetros com as seguintes configurações:

Desvio padrão do espalhamento igual a 500 metros; raio de atualização

(R) igual a 700 metros; espaçamento (S) igual a 1; e variação do número

de objetos em 20, 50 e 100.


(R) igual a 1.000 metros; espaçamento (S) igual a 1; e variação do número



(R) igual a 1.200 metros; espaçamento (S) igual a 1; e variação do número


Optou-se por simular três subcenários para poder melhor observar as

interdependências dos parâmetros. Pela Figura 38, conclui-se que o número de

objetos não influencia muito o número de células percorridas. Na verdade, a

influência do número de objetos no número de células percorridas é quase nula.

Observa-se apenas um pequeno aumento no número de células navegadas. Esse

71

Conforme a explanação apresentada no capítulo 7.2.

114

resultado apresenta coerência, pois, conforme visto nas seções anteriores, a busca

local corresponde a grande parte do tempo de busca. Logo, como o tempo dedicado

à busca local depende do tamanho da área da busca local, o tempo da busca

dependerá mais do tamanho da área onde será realizada a busca local.

(a) Utilizando raio de atualização R = 700 metros

(b) Utilizando raio de atualização R = 1.000 metros

(c) Utilizando raio de atualização R = 1.200 metros

Figura 38 – Análise de sensibilidade para o número de objetos (eixos horizontais das figuras). Nos

eixos verticais: as barras azuis apresentam a média de células percorridas; as linhas vermelhas, a

média de objetos detectados

94%

95%

96%

97%

98%

99%

100%

0%

10%

20%

30%

40%

50%

% m

éd

ia d

e o

bje

tos

de

tect

ado

s

Cé

lula

s p

erc

orr

idas

94%

95%

96%

97%

98%

99%

100%

0% 5%

10% 15% 20% 25% 30% 35% 40% 45% 50%

% m

éd

ia d

e o

bje

tos

dete

cta

do

s

Célu

las p

erc

orr

idas

94%

95%

96%

97%

98%

99%

100%

0%

10%

20%

30%

40%

50%

% m

éd

ia d

e o

bje

tos

dete

cta

do

s

Célu

las p

erc

orr

idas

115

Assim, verifica-se que o número de objetos possui pequena influência no

tamanho da área de busca local, pois há uma leve tendência de aumento no tempo

de busca quando se aumenta o número de objetos. No entanto, esse aumento é

marginal. Além disso, também se observa uma tendência de crescimento no tempo

da busca quando se aumenta o raio de atualização do conhecimento, conforme já

concluído nas simulações do Cenário 4 – variação do raio de atualização do

conhecimento (R).

Em relação à porcentagem média de objetos detectados, a observação da

Figura 38 também corrobora a conclusão obtida na subseção 8.4: a de que

aumentando o raio de atualização (R), aumenta-se a probabilidade de detecção dos

objetos. Mas é possível concluir algo mais: também há uma relação entre a

probabilidade de detecção e a densidade de objetos espalhados, pois o desvio

padrão do espalhamento se mantém o mesmo. Nos três gráficos da Figura 38,

verifica-se que o aumento do número de objetos tende a aumentar a porcentagem

média de objetos detectados.

Portanto, os resultados obtidos até agora vão convergindo para o seguinte: o

tempo médio de busca depende, principalmente, do tamanho da área da busca

local; e, a probabilidade de detecção, depende, principalmente, da densidade de

objetos espalhados.

8.6 Cenário 6 – variação do espalhamento dos objetos ( )

Este cenário buscou avaliar a influência do tamanho da área de espalhamento

dos objetos na busca. O parâmetro que representa o tamanho dessa área é o desvio

padrão da distribuição gaussiana utilizada no sorteio da localização dos objetos ao

redor de um ponto central, também sorteado. Neste cenário, também foram

utilizados 20 objetos em espalhamentos pequenos ( ), médios

( ) e grandes ( ) – conforme ilustrado na Figura

39.a, na Figura 39.b e na Figura 39.c, respectivamente.

116

(a)

(b)

(c)

Figura 39 – Variação do espalhamento dos objetos. (a) Utilizando desvio-padrão de ;

(b) de ; e (c) de .

Assim como no Cenário 5 – variação do número de objetos (n) – essas

dimensões foram definidas comparando com um cenário real (CENTRO DE

COMUNICAÇÃO SOCIAL DA MARINHA, 2009). Considerado a maior e mais

complexa operação SAR da história brasileira, no acidente em questão foram

encontrados objetos espalhados num raio de cinco quilômetros (FOLHA ONLINE,

2009). Portanto, como numa distribuição gaussiana as medidas se distribuem 68%

delas entre e , 95% delas entre e , e 99,7%

entre e 72 , para um desvio padrão de 500 metros, por

exemplo, os pontos estarão num raio de 1.500 metros, e maioria deles estará num

raio de 500 metros.

Então, de mesma forma que no cenário 5 (subseção 8.5), foram feitas

simulações em três subcenários (para espaçamento igual a 1, 4 e 10). Dessa forma,

fixando o raio de atualização em 1.000 metros, variou-se, em cada subcenário, o

espalhamento dos objetos (desvio padrão). A Figura 40 apresenta os resultados das

simulações.

72

Regra empírica conhecida como “regra 68-95-99.7”

117

(a) Utilizando espaçamento S = 1

(b) Utilizando espaçamento S = 4

(c) Utilizando espaçamento S = 10

Figura 40 – Análise de sensibilidade do espalhamento dos objetos. Os eixos horizontais representam

a variação do desvio padrão utilizado na distribuição gaussiana; as barras azuis, a média de células

percorridas; as linhas vermelhas, a média de objetos detectados.

0%

10%

20%

30%

40%

50%

60%

70%

80%

90%

100%

0%

10%

20%

30%

40%

50%

60%

% m

éd

ia d

e o

bje

tos

dete

cta

do

s

Célu

las p

erc

orr

idas

0%

10%

20%

30%

40%

50%

60%

70%

80%

90%

100%

0%

10%

20%

30%

40%

50%

60%

% m

éd

ia d

e o

bje

tos

dete

cta

do

s

Célu

las p

erc

orr

idas

0%

10%

20%

30%

40%

50%

60%

70%

80%

90%

100%

0%

10%

20%

30%

40%

50%

60%

% m

éd

ia d

e o

bje

tos

dete

cta

do

s

Célu

las p

erc

orr

idas

118

A conclusão que se pode tirar é que o aumento do espalhamento influencia

positivamente o tempo da busca (que tende a aumentar) e negativamente a

probabilidade de detecção dos objetos (que tende a reduzir). Numa situação real de

busca e salvamente, esse parâmetro pode representar o tempo decorrido entre o

acidente e a operação de busca, pois quanto mais tempo os objetos ficam a deriva

(sob a influência de correntes marinhas e de ventos) mais eles se espalham.

A influência no tempo de busca (barras azuis na Figura 40) é razoável, cuja

diferença entre o menor ( ) e o maior ( )

espalhamento pode chegar a aproximadamente 20% de células navegadas a mais.

Esse resultado é esperado, pois já foi observado em simulações anteriores que o

tamanho da área da busca local é um dos fatores que mais influenciam o tempo da

busca, e, como é de se esperar, quanto maior o espalhamento dos objetos, maior é

a área da busca local.

Em relação à probabilidade de detecção dos objetos, também se observou

grande sensibilidade desta em relação ao espalhamento dos objetos. Conforme se

aumenta o espalhamento dos objetos, a porcentagem média de objetos detectados

reduz consideravelmente (chegando até a 56% 73 ). Essa observação também

corrobora com outra conclusão obtida anteriormente: a de que a probabilidade de

detecção depende, principalmente, da densidade de objetos na área de busca local.

73

Para S = 10 e

119

9 CONCLUSÕES E CONSIDERAÇÕES FINAIS

Iniciando por uma breve introdução e pela motivação, bem como por uma

apresentação sobre VANTs, esta dissertação de mestrado discorreu sobre as três

principais vertentes da pesquisa (busca e salvamento; coordenação de sistemas

multiagentes; e algoritmos de navegação), apresentou o modelo de VANTs

cooperativos que foi concebido ao longo de toda a pesquisa, apresentou a

metodologia de simulação empregada e, por fim, os resultados obtidos. Portanto,

consideram-se contribuições da pesquisa, não só o modelo proposto de VANTs

cooperativos, como também a organização do conhecimento dos temas

relacionados – que será de grande importância para a continuação da pesquisa.

Após situar o leitor sobre o estado da arte dos veículos aéreos não tripulados

e apresentar o que a literatura visiona para o futuro desses robôs (VANTs

cooperativos e autônomos), cada vertente da pesquisa foi detalhada de modo a

facilitar ao leitor o entendimento do curso da pesquisa e das decisões que

conduziram a pesquisa ao modelo proposto de VANTs cooperativos.

Basicamente, por haver com algum conhecimento acumulado sobre esse tipo

de operação, a ideia foi inspira-se nas buscas tripuladas já realizadas, de modo que

o modelo de VANTs cooperativos, mesmo visando ser autônomo, pudesse ter um

ponto de partida. Então, com o intuito de prover autonomia e cooperação aos

VANTs, selecionaram-se mecanismos de coordenação da teoria multiagente, que é

bastante aderente ao problema que se pretendeu resolver. E, com o intuito de

escolher prover capacidade de planejamento individual para os VANTs, foi feita uma

pesquisa em algoritmos de navegação.

Por fim, procurando ser o mais detalhado e claro possível, o modelo de

VANTs cooperativos foi apresentado – explicitando como os mecanismos de

coordenação são implementados e como conceitos de buscas tripuladas,

mecanismos de coordenação e algoritmos de navegação são combinados com o fim

de obter o modelo. Então, estabeleceu-se um planejamento e metodologia de

simulação, e os resultados obtidos em cada cenário de simulação foram

interpretados, apresentados e analisados.

120

9.1 Conclusão

Duas medidas foram avaliadas pelas simulações do modelo: número médio

de células navegadas e porcentagem média de objetos detectados. Observou-se

que, utilizando o modelo, dois VANTs cooperativos são capazes de buscar todos os

objetos (com probabilidade próxima de 100%) sobrevoando apenas 30% das células

existentes no cenário, o que representa uma redução de 57% em relação a uma

busca simples de dois VANTs não cooperativos.

Isso quer dizer que, considerando o pior cenário de busca (desconhecimento

total da provável localização do acidente), com a implementação do modelo de

VANTs cooperativos, haveria uma redução do tempo de busca bastante significativa:

de 57%.

Foi observado também, que a redução máxima do tempo de busca

(representado no número de células navegadas) tende a saturar nesse valor. Ou

seja, a porcentagem mínima de células percorridas girou em torno de 30% – que

representa uma redução de 57% em relação a uma busca simples de dois VANTs

não cooperativos.

Verificou-se também, que a busca local tende a se tornar o gargalo da busca.

Portanto, novas pesquisas que visem aumentar a eficiência da busca local trariam

benefícios relevantes ao modelo.

Em relação à sensibilidade dos parâmetros, a Tabela 5 sintetiza as

conclusões obtidas. Conclui-se que: aumentando o espaçamento (S) do padrão de

busca Rotas Paralelas, o tempo de busca é reduzido, porém a probabilidade de

detecção de objetos também é reduzida; aumentando o raio de atualização do

conhecimento (R), há um pequeno aumento linear na porcentagem de células

navegadas e um aumento considerável na probabilidade de detecção dos objetos

até R=1.000 metros (com estabilização perto de 100% a partir daí); já o aumento do

número de objetos (n) apresentou pouca influência positiva tanto no número de

células navegadas quanto na probabilidade de detecção dos objetos; quanto ao

espalhamento dos objetos (σ), observou-se grande influência positiva na

121

porcentagem média de células navegadas e grande influência negativa na

probabilidade de detecção dos objetos de busca.

Tabela 5 – Síntese de observações sobre a sensibilidade dos parâmetros

Parâmetro Efeito no tempo da busca

(células navegadas) Efeito na probabilidade de

detecção

Espaçamento (S) do padrão de busca Rotas Paralelas

Redução considerável até S=3 e estabilização em 30%

a partir de S=3

Próximo de 100% até S=4 e redução considerável a partir de

S=5

Raio de atualização do conhecimento (R)

Aumento pequeno linear

Aumento considerável até R=1.000 metros e estabilização

em aproximadamente 100% a de R=1.000 metros

Número de objetos espalhamento (n)

Aumento muito pequeno (pouca influência)

Aumento pequeno (influência menor para R maiores

e maior para R menores)

Espalhamento dos objetos ( ) Aumento considerável

(muita influência) Redução considerável

(muita influência)

A análise mais profunda da Tabela 5, em conjunto com a Figura 31 (página

105), permite concluir que o tempo de busca é majoritariamente influenciado pelo

tamanho da área da busca local, que por sua vez é influenciada levemente pelo

número de objetos de busca, medianamente pelo raio de atualização do

conhecimento (R) e fortemente pelo espalhamento destes.

Já a probabilidade de detecção dos objetos é majoritariamente é diretamente

proporcional à densidade de objetos espalhados (objetos / área) e ao raio de

atualização do conhecimento do VANT.

A redução no número de células navegadas é uma das principais motivações

desta pesquisa de mestrado, pois repercute diretamente no tempo da busca –

principal fase de uma operação de busca e salvamento. Consequentemente,

aumenta-se a probabilidade de sucesso do salvamento (fase posterior à busca).

Portanto, considera-se que o objetivo da pesquisa foi concretizado.

122

9.2 Trabalhos futuros

Em trabalhos futuros, outros detalhes podem ser explorados, tais como:

melhoria do modelo proposto no capítulo 6; implementação de cooperação

envolvendo tantos VANTs quanto se queira; e utilização da cooperação entre VANTs

para outros propósitos.

Em relação à melhoria do modelo, sugere-se modificar a busca local de modo

a aumentar a eficiência dessa fase da busca. Os resultados compilados e

apresentados no capítulo 8 mostram que a busca local é, muitas vezes, o “gargalo”

da operação de busca.

Além disso, algumas simplificações adotadas podem ser trabalhadas com o

intuito de prover mais realidade ao modelo de VANTs cooperativos, tais como:

considerar correntes marinhas no deslocamento dos objetos durante a busca e

considerar falhas74 na detecção automática por câmera dos objetos. Neste último,

também pode ser considerado a probabilidade de detecção levando em conta

características do objeto como, por exemplo, tamanho e cor.

Quanto à implementação de cooperação entre mais de dois VANTs, o

mecanismo de coordenação Contract Net (subseção 4.2.2) poderia ser empregado

na seleção do “VANT Ajudante”. Nesse caso, poderia ser utilizado o “bidding”, sob a

coordenação do VANT que detecta o primeiro objeto, para que seja acionado (para a

busca local) o VANT que está mais perto do ponto onde ocorreu a primeira

detecção.

Saindo um pouco do tema operações de busca e do modelo de VANTs

cooperativos em si, a cooperação de VANTs também pode ser explorada em outras

áreas. Os conceitos de cooperação multiagente apresentados nesta pesquisa de

mestrado, por exemplo, poderiam ser explorados na investigação de técnicas que

consideram o conceito de voo livre – free-flight concept (FOREMAN, 1998) –, que,

por sua vez, poderia ser exploradas na aviação comercial. Aeronaves poderiam ser

dotadas de uma inteligência tal que permitisse a coordenação dos voos de forma

74

Numa operação real, quando o VANT sobrevoa um objeto, não necessariamente este objeto é detectado. Isso ocorre por limitações da câmera, por reflexos do sol, etc.

123

descentralizada, diminuindo a necessidade da grande centralização que existe hoje

na figura do controlador de tráfego aéreo.

Ainda sobre este último tópico, de acordo com um relatório publicado em

2010 sobre o setor de tráfego aéreo (MCKINSEY&COMPANY, 2010), ao mesmo

tempo em que a expansão da infraestrutura aeroportuária surge como a

necessidade mais importante e imediata, existem outras oportunidades de atuação

no setor. Por exemplo, a combinação de investimentos em pátio com

aperfeiçoamentos no controle de tráfego aéreo (e aqui poderia entrar a coordenação

descentralizada das aeronaves), poderia diminuir o tempo necessário de viagem,

permitindo rotas com traçado mais direto, progressão de subida e descida mais

eficiente e menores circuitos de espera para aproximação para pouso. Também

poderia haver outros ganhos indiretos dessa coordenação descentralizada, tais

como: menor consumo de combustível, menor custo operacional e menor impacto

ambiental. Dessa forma, os diversos mecanismos de cooperação estudados nesta

pesquisa poderiam ser utilizados com intuito de aumentar a eficiência do sistema de

tráfego aéreo.

Apesar de ser mais aplicável a operações em espaços aéreos segregados,

este conceito já está sendo estudado para o tráfego aéreo comercial (SISLAK, VOLF

e PECHOUCEK, 2010). Desse modo, espera-se que a descentralização do

planejamento e do controle do tráfego acarrete na utilização mais eficiente do

espaço aéreo, na melhoria do replanejamento de voos e em melhores mecanismos

anticolisão 75 (PECHOUCEK e SISLAK, 2009; SISLAK, VOLF e PECHOUCEK,

2010).

Enfim, trabalhos futuros podem não só continuar esta pesquisa de mestrado,

aperfeiçoando o modelo de VANTs cooperativos proposto, como também utilizar o

embasamento teórico utilizado (mecanismos de coordenação, algoritmos de

navegação, etc.) em pesquisas de outras áreas.

75

Collision Avoidance Systems (CAS)

124

9.3 Considerações finais

De tudo o que foi exposto, conclui-se que o objetivo desta pesquisa de

mestrado foi atendido. O modelo de VANTs cooperativos proposto é capaz de

realizar buscas com desempenho melhor do que buscas realizadas por VANTs não

cooperativos. Assim, espera-se que esse modelo possa servir de inspiração a outras

pesquisas bem como a projetos que aspiram construir VANTs cooperativos

aplicados a nobre causa que da busca e salvamento.

As condições para a construção de VANTs com este propósito já existem:

viabilidade técnica, alguns incentivos governamentais e uma motivação nobre.

Assim, espera-se que este trabalho possa ser continuado e que outros possam

surgir, até que VANTs cooperativos aplicados a operações de busca possam existir

e operar.

E que iniciativas como essa ajudem a consagrar o Lema Internacional de

Busca e Salvamento, “... para que outros possam viver!”, e a levar o espírito SAR

aos usuários da Navegação Aérea e Marítima, no Brasil ou em qualquer parte do

planeta, trazendo-lhes a certeza de dizerem ao final, quando vítimas de um

incidente: “... Eu sabia que vocês viriam!”76.

76

Frases citadas no Curso Básico de Busca e Salvamento publicado pelo Comando da Aeronáutica, (2011).

125

REFERÊNCIAS

AIR-ATTACK.COM. MQ-1 Predator. Air-Attack.com. Disponivel em: <http://air-attack.com/page/53/MQ-1-Predator.html>. Acesso em: 28 Maio 2012.

AL-HELAL, H.; SPRINKLE, J. UAV Search: Maximizing Target Acquisition. 17th IEEE International Conference and Workshops on Engineering of Computer Based Systems (ECBS). Oxford, UK: [s.n.]. 2010. p. 9-18.

ARSHAM, P. H. Systems Simulation: The shortest route to applications. Modeling and Simulation, 2012. Disponivel em: <http://home.ubalt.edu/ntsbarsh/simulation/sim.htm>. Acesso em: 01 Fevereiro 2012.

BEA E CECOMSAER. BEA resgata unidade de memória de caixa preta do AF-447. Força Aérea Brasileira, 2011. Disponivel em: <http://www.fab.mil.br/portal/capa/index.php?mostra=7067>. Acesso em: 21 Julho 2011.

BELLIFEMINE, F.; CAIRE, G.; GREENWOOD, D. Developing multi-agent system with JADE. 1. ed. [S.l.]: Wiley, 2007.

BILLINGSLEY, T. B. Safety Analysis of TCAS on Global Hawk using Airspace Encounter Models. Massachussetts Institute of Technology. [S.l.]. 2006.

BOEING. 737 Family. Boeing, 2011. Disponivel em: <http://www.boeing.com/commercial/737family/>. Acesso em: 2011 Junho 29.

BOOCH, G.; RUMBAUGH, J.; JACOBSON, I. UML: Guia do Usuário. [S.l.]: Campus, 2005.

BOSSONARO, A. A. et al. An Integrated System to Support Critical Infrastructure Securit. In: 1st Brazilian Conference on Critical Embedded Systems (CBSEC 2011). São Carlos, Brazil: [s.n.]. 2011.

BRASIL. Lei nº 7.565, de 19 de dezembro de 1986. Dispõe sobre o código brasileiro de aeronáutica. Diário Oficial da União, Brasília, 1986. Disponível em: <http://www.planalto.gov.br/ccivil_03/leis/L7565.htm>. Acesso em: 10 jan. 2012.

BRIGHAM YOUNG UNIVERSITY. WiSAR Wiki. WiSAR Project, 2011. Disponivel em: <https://facwiki.cs.byu.edu/WiSAR/index.php/Main_Page>. Acesso em: 19 Dezembro 2011.

BUSSMANN, S.; MÜLLER, J. A Negotiation Framework for Cooperating Agents. In: 1992 Proceedings of the Special Interest Group on Cooperating Knowledge Based Systems. Keele, UK: DDeen, S.M. 1993. p. 1-17.

http://air-attack.com/page/53/MQ-1-Predator.html

http://air-attack.com/page/53/MQ-1-Predator.html

http://home.ubalt.edu/ntsbarsh/simulation/sim.htm

http://www.fab.mil.br/portal/capa/index.php?mostra=7067

http://www.boeing.com/commercial/737family/

https://facwiki.cs.byu.edu/WiSAR/index.php/Main_Page

126

CEMIG. Monitoramento nas alturas: Aeronave autônoma será utilizada nas inspeções das linhas de transmissão da Cemig. Revista P&D - Informativo do programa de gestão estratégica em tecnologiada CEMIG, n. 7, p. 32-43, 2011.

CENTRO DE COMUNICAÇÃO SOCIAL DA MARINHA. Término das buscas do voo 447 da Air France. Força Aérea Brasileira, 2009. Disponivel em: <http://www.fab.mil.br/portal/capa/index.php?mostra=3311>. Acesso em: 2011 Julho 12.

CHAVES, A. N.; CUGNASCA, P. S. Veículos Aéreos não tripulados autônomos e colaborativos aplicados a operações de busca e salvamento. In: Anais do X Simpósio de Pesquisa em Transporte Aéreo (X SITRAER). Ouro Preto, MG, Brasil: [s.n.]. 2011. p. 13-25.

CHAVES, A. N.; CUGNASCA, P. S. Cooperative UAVs using multi-agent coordination techniques for search operations. In: Anais do VI Workshop-Escola de Sistemas de Agentes, seus Ambientes e apliCações (WESAAC 2012). Florianópolis, SC, Brasil: UFSC. 2012a. p. 217-228.

CHAVES, A. N.; CUGNASCA, P. S. Autonomous Cooperative Unmanned Aerial Vehicle. In: Proceedings of 10th World Congress On Computational Mechanics (WCCM 2012). São Paulo, SP, Brazil: P.M. Pimenta; E.M.B. Campello. 2012b. CD.

CHAVES, A. N.; CUGNASCA, P. S.; NETO, J. J. Adaptive Search with multiple Unmanned Aerial Vehicles (UAVs). Revista de Sistemas e Computação, Salvador, Brasil, v. 2, n. 1, p. 53-59, Junho 2012.

CHUNG, T. H.; BURDICK, J. W. Multi-agent probabilistic search in a sequential decision-theoretic framework. In: IEEE International Conference on Robotics and Automation, 2008. ICRA 2008. Pasadena, California, USA: [s.n.]. 2008. p. 146-151.

CLOSE-SEARCH. Close-Search Project. Close-search, 2011. Disponivel em: <http://www.close-search-project.eu>. Acesso em: 19 Dezembro 2011.

COFFEY, N. How good is java.util.Random? Stack Overflow, 2009. Disponivel em: <http://stackoverflow.com/questions/453479/how-good-is-java-util-random>. Acesso em: 10 Julho 2012.

COFFEY, N. How does java.util.Random work and how good is it? Javamex, 2010. Disponivel em: <http://www.javamex.com/tutorials/random_numbers/>. Acesso em: 05 Novembro 2012.

COLLINS, T.; COLLINS, J. J.; RYAN, C. Occupancy grid mapping: An empirical evaluation. In: 15th IEEE Mediterranean Conference on Control Automation (MED '07). Athens, Greece: [s.n.]. 2007. p. 1-6.

COMANDO DA AERONÁUTICA. SAR 005 Curso Básico de Busca e Salvamento. DECEA - Departamento de Controle do Espaço Aéreo. [S.l.]. 2011.

CORRÊA, Mario. Modelo de Veículos Aéreos não Tripulados Baseado em Sistemas Multi-agentes. 2008. 89 p. Tese (Doutorado em Engenharia Elétrica) - Escola Politécnica, Universidade de São Paulo. São Paulo.

http://www.fab.mil.br/portal/capa/index.php?mostra=3311

http://www.close-search-project.eu/

http://stackoverflow.com/questions/453479/how-good-is-java-util-random

http://www.javamex.com/tutorials/random_numbers/

127

COSTA NETO, P. L. D. O. Estatística. 2. ed. São Paulo: Edgar Blücher, 2002.

COX, T. H. et al. Civil UAV Capability Assessment. NASA; CSM, Inc. [S.l.]. 2004.

DECEA. Manual de Busca e Salvamento (SAR). Ministério da Defesa - Comando da Aeronáutica. [S.l.]. 2009.

DECEA. NSCA 64-1 Sistema de Busca e Salvamento Aeronáutico. Ministério da Defesa - Comando da Aeronáutica. [S.l.]. 2010a.

DECEA. PCA 64-1 Plano de Busca e Salvamento Aeronáutico Brasileiro. Ministério da Defesa - Comando da Aeronáutica. [S.l.]. 2010b.

DECEA. DECEA >> Busca e Salvamento. DECEA, 2011. Disponivel em: <http://www.decea.gov.br/espaco-aereo/busca-e-salvamento/>. Acesso em: 2011 Julho 12.

DEFENSE INDUSTRY DAILY. Naval Air, Unmanned: US Navy Flying Toward N-UCAS. Defense Industry Daily, 2012. Disponivel em: <http://www.defenseindustrydaily.com/cv-ucavs-the-return-of-ucas-03557/>. Acesso em: 24 Maio 2012.

DEITEL, H. E. P. Java How to Program. 6th. ed. [S.l.]: Prentice Hall, 2004.

DEMAZEAU. Disributed AI and Multi-Agent Systems. 1994. Notas de Aula.

University of Odense, Denmark.

DICKERSON, L. UAVs on the Rise. Aviation Week & Space Technology, v. 166, n. 3, Janeiro 2007.

DOD. Unmanned Aerial Vehicles Roadmap 2000-2025. Department of Defense - DoD. [S.l.]. 2001.

DOD. Unmanned Aerial Vehicles Roadmap 2002 - 2027. Department of Defense - DoD. [S.l.]. 2002.

DOD. Unmanned Aircraft Systems Roadmap 2005-2030. Department of Defense - DoD. [S.l.]. 2005.

DOHERTY, P.; RUDOL, P. A UAV Search and Rescue Scenario with Human Body Detection and Geolocalization. In: ORGUN, M.; THORNTON, J. AI 2007: Advances in Artificial Intelligence. [S.l.]: Springer Berlin / Heidelberg, v. 4830, 2007. p. 1-13.

DURFEE, E. H. Distributed Problem Solving and Planning. In: WEISS, G. Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence. Cambridge, MA, USA: MIT Press, 1999. p. 121-164.

EASTON, V. J.; MCCOLL, J. H. Nonparametric methods. Statistics Glossary, 2012. Disponivel em: <http://www.stats.gla.ac.uk/steps/glossary/nonparametric.html>. Acesso em: 11 Junho 2012.

http://www.decea.gov.br/espaco-aereo/busca-e-salvamento/

http://www.defenseindustrydaily.com/cv-ucavs-the-return-of-ucas-03557/

http://www.stats.gla.ac.uk/steps/glossary/nonparametric.html

128

ELFES, A. Occupancy grids: a probabilistic framework for robot perception and navigation. 1989. Tese de Doutorado (Department of Electrical and Computer Engineering) - Carnegie Mellon University. Pittsburgh, PA, USA.

ESTLIN, T. et al. Coordinating multiple rovers with interdependent science objectives. In: Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems. New York, NY, USA: ACM. 2005. p. 879-886.

FERBER, J.; GÜTKNECHT, O. A meta-model for the analysis and design of organizations in multi-agent systems. In: Proceedings of 3rd International Conference on Multi Agent Systems. Paris, France: IEEE Computer Society. 1998. p. 128-135.

FERREIRA, A. M. Métodos estatísticos e delineamento experimental: testes não paramétricos. Escola Superior Agrária Castelo Branco. [S.l.], p. 41. 2006.

FINEP. CHAMADA PÚBLICA/ MCT/FINEP - CT-AERO - VANT 01/200. FINEP, 04 Dezembro 2009. Disponivel em: <http://www.finep.gov.br//fundos_setoriais/ct_aero/editais/Chamada%20VANT2009%20vers%C3%A3o%20final1.pdf>. Acesso em: 2011 Maio 15.

FIPA. FIPA Contract Net Interaction Protocol Specification. Foundation for Intelligent Physical Agents. Geneva, Switzerlan. 2002.

FOLHA ONLINE. Ministro afirma que avião da Air France caiu a cerca de 700 km de Fernando de Noronha. Folha.com, 2009. Disponivel em: <http://www1.folha.uol.com.br/folha/cotidiano/ult95u575492.shtml>. Acesso em: 1º Junho 2012.

FORE AN, P. Proposed “free flight” environment raises a number of pressing issues for the world’s pilots. ICAO Journal, v. 53, n. 5, p. 9-12, 27, 1998.

FROST & SULLIVAN. World Markets for Military; Civil and Commercial Unmanned Aerial Vehicles: Reconnaissance UAVs and Aerial Targets. Frost & Sullivan. [S.l.]. 1998.

GALANTE, A. VANT inovador feito na USP monitora desmatamento em Jirau. Poder Aéreo, 2011. Disponivel em: <http://www.aereo.jor.br/2011/07/15/vant-inovador-feito-na-usp-monitora-desmatamento-em-jirau/>. Acesso em: 19 Dezembro 2011.

GAN, S. K.; SUKKARIEH, S. Multi-UAV target search using explicit decentralized gradient-based negotiation. In: IEEE International Conference on Robotics and Automation (ICRA). Shangai, China: [s.n.]. 2011. p. 751-756.

GARCIA, R.; BARNES, L. Multi-UAV Simulator Utilizing X-Plane. Journal of Intelligent & Robotic Systems, v. 57, p. 393-406, 2010.

GEORGEFF, M. Communication and Interaction in Multi-Agent Planning. In: Proceedings of the 3rd National Conference on Artificial Intelligence (AAAI-83). Menlo Park, CA: AAAI Press. 1983. p. 125-129.

http://www.finep.gov.br/fundos_setoriais/ct_aero/editais/Chamada%20VANT2009%20vers%C3%A3o%20final1.pdf

http://www.finep.gov.br/fundos_setoriais/ct_aero/editais/Chamada%20VANT2009%20vers%C3%A3o%20final1.pdf

http://www1.folha.uol.com.br/folha/cotidiano/ult95u575492.shtml

http://www.aereo.jor.br/2011/07/15/vant-inovador-feito-na-usp-monitora-desmatamento-em-jirau/

http://www.aereo.jor.br/2011/07/15/vant-inovador-feito-na-usp-monitora-desmatamento-em-jirau/

129

GEORGEFF, M. A theory of action for multi-agent planning. In: Proceedings of the 4th National Conference on Artificial Intelligence (AAAI '84). Austin, TX: [s.n.]. 1984. p. 121-125.

GIBBONS, J. D.; CHAKRABORTI, S. Nonparametric Statistical Inference. 5th. ed. [S.l.]: Chapman and Hall/CRC, 2010.

GIL, F. D. O. Metodologia de avaliação de segurança das comunicações entre controlador e piloto via enlace de dados (CPDLC) aplicada em áreas terminais. 2011. 150 p. Dissertação de Mestrado (Sistemas Digitais) - Escola Politécnica, Universidade de São Paulo. São Paulo.

GIL, F. O. et al. PIPE-SEC: Platform for Testing and Validation of the Operation of Unmanned Aerial Vehicles (UAVs) in Controlled Airspace. Journal of the Brazilian Air Transportation Research Society - JBATS, v. 6, p. 507-521, 2010.

GLOBALSECURITY.ORG. Unmanned Combat Armed Rotorcraft [UCAR]. GlobalSecurity.org, 2011. Disponivel em: <http://www.globalsecurity.org/military/systems/aircraft/ucar.htm>. Acesso em: 24 Maio 2012.

GONZALEZ, A. J.; AHLERS, R. Context-based representation of intelligent behavior in training simulations. Transactions of the Society for Computer Simulation International, v. 15, n. 4, p. 153-166, 1998.

GOODRICH, M. A. et al. Supporting wilderness search and rescue using a camera-equipped mini UAV. Journal of Field Robotics, v. 25, n. 1-2, p. 89-110, 2008.

HOLLANDER, M.; WOLFE, D. A. Nonparametric Statistical Methods. 2nd. ed. [S.l.]: Wiley-Interscience, 1999.

HOME LAND SECURITY NEWSWIRE. UAVs perform autonomous search-and-rescue operations. Home Land Security NewsWire, Julho 2010. Disponivel em: <http://www.homelandsecuritynewswire.com/uavs-perform-autonomous-search-and-rescue-operations>.

HÜBNER, J. F.; SICHMAN, J. S.; BOISSIER, O. MOISE+: towards a structural, functional, and deontic model for MAS organization. In: Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1. New York, NY, USA: ACM. 2002. p. 501-502.

HUNTSBERGER, T. et al. CAMPOUT: A Control Architecture for Tightly Coupled Coordination of Multi-Robot Systems for Planetary Surface Exploration. IEEE Trans. Systems, Man & Cybernetics, Part A: Systems and Humans, v. 33, p. 550-559, 2003.

IMO/ICAO. IAMSAR Manual - International Aeronautical and Maritime Search and Rescue Manual. IMO/ICAO. London/Montreal. 2003.

ISARABHAKDEE, P.; GAO, Y. Cooperative Control of a multi-tier Robotic System for Planetary Exploration. In: IJCAI-09 Workshop on Artificial Intelligent in Space. Pasadena, California, US: [s.n.]. 2009.

http://www.globalsecurity.org/military/systems/aircraft/ucar.htm

http://www.homelandsecuritynewswire.com/uavs-perform-autonomous-search-and-rescue-operations

http://www.homelandsecuritynewswire.com/uavs-perform-autonomous-search-and-rescue-operations

130

JAKOB, M. et al. Occlusion-aware Multi-UAV Surveillance of Multiple Urban Areas. In: 6th Workshop on Agents in Traffic and Transportation (ATT 2010). Toronto, Canada: [s.n.]. 2010.

JENNINGS, N. R.; WOOLDRIDGE, M. Agent technology. Secaucus, NJ, USA: Springer-Verlag New York, Inc., 1998. Cap. Applications of intelligent agents, p. 3-28.

JP. Department of Defense Dictionary of Military and Associated Terms. [S.l.]: Joint Education and Doctrine Division, J-7, Joint Staff, 2011.

KOPRIVA, S. et al. Iterative accelerated A* path planning. In: 49th IEEE Conference on Decision and Control (CDC). Atlanta, Georgia, USA: [s.n.]. 2010. p. 1201-1206.

LEHMANN, E. L. Nonparametrics: Statistical Methods Based on Ranks. Facsimile edition. ed. [S.l.]: Pearson Education, 1998.

LENAT, D. B. Beings: knowledge as interacting experts. In: Proceedings of the 4th international joint conference on Artificial intelligence. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. 1975. p. 126-133.

LESSER, V. et al. Evolution of the GPGP/TAEMS Domain-Independent Coordination Framework. Autonomous Agents and Multi-Agent Systems, v. 9, n. 1, p. 87-143, 2004.

LESTER, P. A* path finding for beginners. PolicyAlmanac.org, 2005. Disponivel em: <http://www.policyalmanac.org/games/aStarTutorial.htm>. Acesso em: 2011 Dezembro 14.

LIN, L.; GOODRICH, M. A. UAV intelligent path planning for Wilderness Search and Rescue. In: The 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems. St. Louis, USA: [s.n.]. 2009. p. 709-714.

LIN, L.; GOODRICH, M. A. A Bayesian approach to modeling lost person behaviors based on terrain features in Wilderness Search and Rescue. Computational and Mathematical Organization Theory, v. 16, p. 300-323, 2010.

LJUNGBERG, M.; LUCAS, A. The OASIS Air Traffic Management System. In: 2nd Pacific Rim International Conference on Artificial Intelligence. Seoul Korea: [s.n.]. 1992.

LONG, L. N. et al. A Review of Intelligent Systems Software for Autonomous Vehicles. In: IEEE Symposium on Computational Intelligence in Security and Defense Applications, 2007 (CISDA 2007). Honolulu, HI, USA: [s.n.]. 2007. p. 69-76.

LUCK, M. et al. Agent Technology: Computing as Interaction (A Roadmap for Agent Based Computing). [S.l.]: AgentLink, 2005.

LUKE, S. Sean Luke: Code. George Mason University, 1999. Disponivel em: <http://cs.gmu.edu/~sean/research/>. Acesso em: 8 Agosto 2012.

http://www.policyalmanac.org/games/aStarTutorial.htm

http://cs.gmu.edu/~sean/research/

131

LUOTSINEN, L. J.; GONZALEZ, A. J.; BÖLÖNI, L. Collaborative UAV exploration in hostile environments. In: Proceedings of the 24th Army Science Conference. Orlando, Florida: [s.n.]. 2004.

MARTINEZ, S. UAV Cooperative Decision and Control: Challenges and Practical Approaches (Shima, T. and Rasmussen, S.; 2008) [Bookshelf]. Control Systems Magazine, IEEE, v. 30, n. 2, p. 104-107, 2010.

MATHWORKS®. MATLAB - The Language Of Technical Computing. MathWorks, 2012. Disponivel em: <http://www.mathworks.com/products/matlab/index.html>. Acesso em: 05 Janeiro 2012.

MATSUMOTO, M.; NISHIMURA, T. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation (TOMACS), v. 8 issue 1, p. 3-30, 1998.

MAZA, I. et al. Experimental Results in Multi-UAV Coordination for Disaster Management and Civil Security Applications. Journal of Intelligent & Robotic Systems, v. 61, p. 563-585, 2011.

MCKINSEY&COMPANY. Estudo do Setor de Transporte Aéreo do Brasil: Relatório Consolidado. McKinsey&Company. Rio de Janeiro. 2010.

MENG, B.-B.; GAO, X. UAV Path Planning Based on Bidirectional Sparse A* Search Algorithm. 2010 International Conference on Intelligent Computation Technology and Automation (ICICTA). Changsha, China: IEEE Computer Society. 2010. p. 1106-1109.

MINISTÉRIO DA RELAÇÕES EXTERIORES. Atos Multilaterais Assinados pelo Brasil no Campo da Aviação Civil. Portal do Ministério da Relações Exteriores, 2011. Disponivel em: <http://www2.mre.gov.br/dai/aviaciv.htm>. Acesso em: 2011 Julho 14.

MINISTÉRIO DAS RELAÇÕES EXTERIORES. Convenção de Aviação Civil Internacional. Ministério das Relações Exteriores, 1944. Disponivel em: <http://www2.mre.gov.br/dai/m_21713_1946.htm>. Acesso em: 2011 Julho 14.

MINSKY, M. The Society of Mind. Pages Bent. ed. New York. London. Toronto. Sydney. Tokyo. Singapore.: Simon & Schuster, 1988.

MORAES, M. Aviões-robôs ajudam a vigiar os céus. INFO online, 2011. Disponivel em: <http://info.abril.com.br/noticias/tecnologia-pessoal/avioes-robos-visam-os-ceus-22082011-6.shl>. Acesso em: 26 Agosto 2011.

MORAVEC, H.; ELFES, A. High resolution maps from wide angle sonar. In: Robotics and Automation. Proceedings. 1985 IEEE International Conference on. St. Louis, Missouri, USA: IEEE Computer Society Press. 1985. p. 116-121.

MORETTIN, P. A.; BUSSAB, W. D. O. Estatística Básica. 6. ed. São Paulo: Saraiva, 2010.

http://www2.mre.gov.br/dai/aviaciv.htm

http://www2.mre.gov.br/dai/m_21713_1946.htm

http://info.abril.com.br/noticias/tecnologia-pessoal/avioes-robos-visam-os-ceus-22082011-6.shl

http://info.abril.com.br/noticias/tecnologia-pessoal/avioes-robos-visam-os-ceus-22082011-6.shl

132

NCSS STATISTICAL SOFTWARE. PASS: Power Analysis and Sample Size. NCSS & PASS, 2012. Disponivel em: <http://www.ncss.com/pass.html>. Acesso em: 12 Junho 2012.

NETBEANS.ORG. Welcome to NetBeans. NetBeans.org, 2012. Disponivel em: <http://netbeans.org/>. Acesso em: 11 Junho 2012.

NWANA, H.; LEE, L.; JENNINGS, N. Coordination in Software Agent Systems. British Telecom Technical Journal, v. 14, n. 4, p. 79-88, 1996.

OLIVEIRA, M. D. Controle remoto - Pequenas aeronaves sem tripulação ganham espaço no Brasil. Pesquisa FAPEAP Online, 2011. Disponivel em: <http://revistapesquisa.fapesp.br/?art=4472&bd=1&pg=1&lg=>. Acesso em: 2011 Julho 27.

ORACLE. Java SE downloads. Oracle Technology Network for Java Developers, 2012. Disponivel em: <http://www.oracle.com/technetwork/java/javase/downloads/index.html>. Acesso em: 11 Junho 2012.

PARSCH, A. Directory of U.S. Military Rockets and Missiles - Appendix 2: Modern UAVs; Northrop Grumman (Teledyne Ryan) RQ-4 Global Hawk. Designation-Systems, 2008. Disponivel em: <http://www.designation-systems.net/dusrm/app2/q-4.html>. Acesso em: 2011 Julho 14.

PAZMANY, M. M. Aeromab Project.: small UAS for wildlife monitoring. In: 1st International Conference & Exhibition for the Latin American UAS Community (UAS Latin American). São José dos Campos, SP, Brasil: [s.n.]. 2011.

PECHOUCEK, M.; SISLAK, D. Agent-Based Approach to Free-Flight Planning, Control, and Simulation. IEEE Intelligent Systems, v. 24, n. 1, p. 14-17, 2009.

PETROBRÁS. Inovação: dirigível registra obras de gasodutos. Petrobrás: Fatos e Dados, 2011. Disponivel em: <http://fatosedados.blogspetrobras.com.br/2011/04/23/inovacao-dirigivel-registra-obras-de-gasodutos/>. Acesso em: 15 Outubro 2011.

PHOENIX INTERNATIONAL HOLDINGS, INC. Remora 6000 ROV Specifications. BEA, 2011. Disponivel em: <http://www.bea.aero/fr/enquetes/vol.af.447/remora6000.pdf>. Acesso em: 09 Dezembro 2011.

PORTAL DA COPA. PF apresenta o Vant, “reforço” para operações de fronteira: Equipamento de monitoramento será uma das ferramentas de segurança utilizada nos megaeventos esportivos. Portal da Copa, 2011. Disponivel em: <http://www.copa2014.gov.br/noticia/pf-apresenta-o-vant-reforco-para-operacoes-de-fronteira>. Acesso em: 08 Dezembro 2011.

QUIGLEY, M. et al. Towards real-world searching with fixed-wing mini-UAVs. In: Intelligent Robots and Systems, 2005. (IROS 2005). 2005 IEEE/RSJ International Conference on. Edmonton, Canadá: [s.n.]. 2005. p. 3028-3033.

http://www.ncss.com/pass.html

http://netbeans.org/

http://revistapesquisa.fapesp.br/?art=4472&bd=1&pg=1&lg=

http://www.oracle.com/technetwork/java/javase/downloads/index.html

http://www.designation-systems.net/dusrm/app2/q-4.html

http://www.designation-systems.net/dusrm/app2/q-4.html

http://fatosedados.blogspetrobras.com.br/2011/04/23/inovacao-dirigivel-registra-obras-de-gasodutos/

http://fatosedados.blogspetrobras.com.br/2011/04/23/inovacao-dirigivel-registra-obras-de-gasodutos/

http://www.bea.aero/fr/enquetes/vol.af.447/remora6000.pdf

http://www.copa2014.gov.br/noticia/pf-apresenta-o-vant-reforco-para-operacoes-de-fronteira

http://www.copa2014.gov.br/noticia/pf-apresenta-o-vant-reforco-para-operacoes-de-fronteira

133

REN, W.; CAO, Y. Distributed Coordination of Multi-agent Networks. [S.l.]: Springer, 2011.

ROBITAILLE, M. Global maritime Search and Rescue Areas. Neptune: the world of silence, 1999. Disponivel em: <http://www.neptune-scuba.info/sarmap-en.html>. Acesso em: 16 Janeiro 2012.

R-PROJECT. The R Project for Statistical Computing. R-project, 2012. Disponivel em: <http://www.r-project.org/>. Acesso em: 06 Junho 2012.

RUBIO, J. C.; VAGNERS, J.; RYSDYK, R. Adaptive path planning for autonomous uav oceanic search missions. In: AIAA 1st Intelligent Systems Technical Conference. Chigado, Illinois: [s.n.]. 2004.

RUSSELL, S.; NOWIG, P. Artificial Intelligence: A Modern Approach. Second Edition. ed. [S.l.]: Prentice Hall, 2003.

RYAN, A. et al. An overview of emerging results in cooperative UAV control. In: 43rd IEEE Conference on Decision and Control (CDC). Atlantis, Paradise Island, Bahamas: [s.n.]. 2004. p. 602 -607 Vol.1.

RYAN, A. et al. Decentralized Control of Unmanned Aerial Vehicle Collaborative Sensing Missions. In: American Control Conference (ACC '07). New York City, USA: [s.n.]. 2007. p. 4672-4677.

SANTOS, C. Petrobras traz técnicas inéditas para o Brasil. Valor Econômico, v. 08/06/2011, 2011.

SCIENTIFIC AMERICAN. More about Ballons. Scientific American, v. Vol. 4, n. No. 26, p. 205, Março 1849.

SHERMAN, J. Pentagon Sets Plan For New Bomber, Terminates J-UCAS Program. GlobalSecurity.org, 2006. Disponivel em: <http://www.globalsecurity.org/org/news/2006/060113-j-ucas-terminated.htm>. Acesso em: 24 Maio 2012.

SHEWHART, W. A. Statistical Method from the Viewpoint of Quality Control. [S.l.]: Dover Publications, 1986.

SHIMA, T.; RASMUSSEN, S. UAV Cooperative Decision and Control: Challenges and Practical Approaches. 1. ed. [S.l.]: Society for Industrial and Applied Mathematics, 2008.

SICHMAN, Jaime. Sistemas multi-agentes: SMAs Reativos. Abril de 2011. Notas de Aula. Universidade de São Paulo, Brasil.

SILVEIRA, V. Mini-helicóptero tem versão nacional. Valor Econômico, São Paulo, 23 Março 2010.

SISLAK, D.; VOLF, P.; PECHOUCEK, M. Accelerated A* Path Planning. Proceedings of 8th International Conference on Autonomous Agents and Multiagent

http://www.neptune-scuba.info/sarmap-en.html

http://www.r-project.org/

http://www.globalsecurity.org/org/news/2006/060113-j-ucas-terminated.htm

134

Systems (AAMAS 2009). Hungary: Decker; Sichman; Sierra; Castelfranchi. 2009. p. 1133-1134.

SISLAK, D.; VOLF, P.; PECHOUCEK, M. Large-scale Agent-based Simulation of Air-traffic. In: Proceedings of the 20th European Meeting on Cybernetics and Systems Research. Vienna, Austria: [s.n.]. 2010.

SMITH, R. G. The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver. Computers, IEEE Transactions on, v. C-29, n. 12, p. 1104-1113, 1980.

SMITH, R. G.; DAVIS, R. Frameworks for Cooperation in Distributed Problem Solving. Systems, Man and Cybernetics, IEEE Transactions on, v. 11, n. 1, p. 61-70, 1981.

STEELS, L. Cooperation between distributed agents through self-organisation. In: Intelligent Robots and Systems '90. 'Towards a New Frontier of Applications', Proceedings. IROS '90. IEEE International Workshop on. Bruxelas, Bélgica: [s.n.]. 1990. p. 8-14.

SUJIT, P.; BEARD, R. Multiple UAV exploration of an unknown region. Annals of Mathematics and Artificial Intelligence, v. 52, p. 335-366, Abril 2008.

TAMBE, M.; ZHANG, W. Towards flexible teamwork in persistent teams. In: Proceedings of 3rd International Conference on Multi Agent Systems, 1998. Paris, France: IEEE Computer Society. 1998. p. 277-284.

TEAL GROUP. Teal Group Predicts Worldwide UAV Market Will Reach Nearly $55 Billion. Teal Group Corporation, 2008. Disponivel em: <http://tealgroup.com/index.php?option=com_content&view=article&id=31:teal-group-predicts-worldwide-uav-market-will-reach-nearly-55-billion&catid=3&Itemid=16>. Acesso em: 16 Janeiro 2012.

TEAL GROUP. Teal Group Predicts Worldwide UAV Market Will Total Over $80 Billion In Its Just Released 2010 UAV Market Profile and Forecast. Teal Group Corporation, 2010. Disponivel em: <http://tealgroup.com/index.php?option=com_content&view=article&id=62:uav-study-release&catid=3&Itemid=16>. Acesso em: 16 Janeiro 2012.

TEAL GROUP. World Unmanned Aerial Vehicle Systems - 2011 Market Profile and Forecast. Teal Group Corporations. [S.l.]. 2011.

THRUN, S. et al. Map Learning and High-Speed Navigation in RHINO. In: KORTENKAMP, D.; BONASSO, R. P.; MURPHY, R. AI-based Mobile Robots: Case Studies of Successful Robot Systems. [S.l.]: MIT Press, 1998.

TISDALE, J. et al. The software architecture of the Berkeley UAV Platform. In: Computer Aided Control System Design, 2006 IEEE International Conference on Control Applications, 2006 IEEE International Symposium on Intelligent Control, 2006 IEEE. Munich, Germany: [s.n.]. 2006. p. 1420-1425.

http://tealgroup.com/index.php?option=com_content&view=article&id=31:teal-group-predicts-worldwide-uav-market-will-reach-nearly-55-billion&catid=3&Itemid=16



http://tealgroup.com/index.php?option=com_content&view=article&id=62:uav-study-release&catid=3&Itemid=16

http://tealgroup.com/index.php?option=com_content&view=article&id=62:uav-study-release&catid=3&Itemid=16

135

U.S. ARMY. Unmanned Aircraft System - Roadmap 2010-2035. U.S. Army. Fort Rucker, Alabama. 2010.

UAV CHALLENGE. Search and Rescue Challenge. UAV Challenge, 2011. Disponivel em: <http://www.uavoutbackchallenge.com.au/2011/index.cfm?contentID=5>. Acesso em: 19 Dezembro 2011.

UNMANNED DYNAMICS. AeroSim Blockset. Unmanned Dynamics, LLC, 2009. Disponivel em: <http://web.archive.org/web/20090512224330/http://www.u-dynamics.com/aerosim/default.htm>. Acesso em: 06 Junho 2011.

VACHTSEVANOS, G.; TANG, L.; REIMANN, J. An Intelligent Approach to Coordinated Control of Multiple Unmanned Aerial Vehicles. In: American Helicopter Society 60th Annual Forum. Baltimore, MD: American Helicopter Society International, Inc. 2004.

VALAVANIS, K. P. Advances in Unmanned Aerial Vehicles: State of the Art and the Road to Autonomy. Tampa, Florida, USA: Springer, 2007.

WAHARTE, S.; TRIGONI, N. Supporting Search and Rescue Operations with UAVs. In: International Conference on Emerging Security Technologies (EST). Canterbury, UK: [s.n.]. 2010. p. 142-147.

WEIXIONG, Huang. AM20: coastal surveillance UAV. 2009. 86 p.Monografia (Graduação em Bachelor of Engineering) - National University of Singapore . Kent Ridge, Singapore.

WISAR LAB. WiSAR Lab. WiSAR Lab, 2011. Disponivel em: <http://www.wisar.org/>. Acesso em: 19 Dezembro 2011.

WISAR TEAM. Wilderness Search and Rescue Team. Wilderness Search and Rescue Team, 2011. Disponivel em: <http://www.wsar.org/>. Acesso em: 19 Dezembro 2011.

WONG, E.-M.; BOURGAULT, F.; FURUKAWA, T. Multi-vehicle Bayesian Search for Multiple Lost Targets. In: Robotics and Automation, 2005. ICRA 2005. Proceedings of the 2005 IEEE International Conference on. Barcelona, Spain: IEEE. 2005. p. 3169-3174.

WOOLDRIDGE, M. An Introduction to MultiAgent Systems. 2. ed. [S.l.]: John Wiley & Sons, 2009.

WOOLDRIDGE, M.; JENNINGS, N. R.; KINNY, D. The Gaia Methodology for Agent-Oriented Analysis and Design. Journal of Autonomous Agents and Multi-Agent Systems, v. 3, n. 3, p. 285-312, 2000.

YANG, X. et al. Fast on-ship route planning using improved sparse A-star algorithm for UAVs. MIPPR 2009: Medical Imaging, Parallel Processing of Images, and Optimization Techniques. [S.l.]: SPIE Proceedings. 2009.

http://www.uavoutbackchallenge.com.au/2011/index.cfm?contentID=5

http://web.archive.org/web/20090512224330/http:/www.u-dynamics.com/aerosim/default.htm

http://web.archive.org/web/20090512224330/http:/www.u-dynamics.com/aerosim/default.htm

http://www.wisar.org/

136

ZHUONING, D. et al. Study on UAV Path Planning Approach Based on Fuzzy Virtual Force. Chinese Journal of Aeronautics, v. 23, n. 3, p. 341-350, 2010.

137

GLOSSÁRIO

Área de possibilidade – é a menor área que contém todas as localizações

possíveis do objeto da busca ou sobreviventes.

Busca e Salvamento (SAR) – the use of aircraft, surface craft, submarines, and

specialized rescue teams and equipment to search for and rescue distressed

persons on land or at sea in a permissive environment. Also called SAR [...].

Cenário – conjunto consistente de fatos e previsões que descrevem o que pode ter

acontecido aos sobreviventes, desde o momento do eventual sinistro até o momento

presente.

Datum – é um ponto, uma linha ou uma área utilizado(a) como referência no

planejamento de uma operação de busca. Normalmente é o ponto de início da busca

quando se tem essa informação, que nem sempre está disponível. Num caso de

acidente marítimo, pode ser a última posição conhecida (em inglês, Last Known

Position – LKP) ou a LKP corrigida da estimativa de deriva. Um datum do tipo ponto

é a posição mais provável do objeto de busca. Há também datum do tipo linha e do

tipo área. Exemplos comuns de área datum incluem aeronaves que decolam para

executarem treinamento em uma área específica e determinada e embarcações que

suspendem para realizar atividade de pesca e áreas pré-determinadas.

Espaçamento – representado pela letra (S) no Manual de Busca e Salvamento do

DECEA, o espaçamento é a distância entre trajetórias paralelas e adjacentes de um

padrão de busca.

Incidente SAR – qualquer situação anormal relacionada com a segurança de

aeronave ou embarcação e que requeira alerta ou ação imediata dos recursos SAR.

Largura de varredura – medida da eficácia com que um determinado sensor pode

detectar certo objeto nas condições ambientais reinantes. Ou seja, é a largura de

faixa que a busca aérea é capaz de detectar um objeto perdido sobrevoando a linha

central dessa faixa.

Mini-UAV – arremessados com as mãos, com peso inferior a 5 kg, dimensão linear

máxima de 3,0 m, alcance mínimo de 20 km, autonomia de vôo mínima de 60

minutos e capaz de ser transportado, montado e operado por uma equipe de apenas

2 (duas) pessoas.

Micro-UAV – arremessados com as mãos, com peso máximo de 200g, dimensão

linear máxima de 200 mm, alcance mínimo de 10km, autonomia de vôo mínima de

60 minutos, propulsão por motor elétrico e alimentação elétrica a bateria ou célula de

combustível.

138

Objeto de busca – uma embarcação ou aeronave desaparecida ou em perigo,

sobreviventes, ou outro objeto ou evidência correlatos em função do qual é

conduzida uma busca.

Operações de Busca e Salvamento (ou, operações SAR) – utilização de

aeronaves, veículos de superfície, submarinos, equipes especializadas de resgate e

equipamentos para buscar e resgatar pessoas em situações de risco, na terra ou no

mar.

Probabilidade de Contenção (POC) – probabilidade de que o objeto da busca

esteja contido dentro dos limites de uma área, subárea ou célula de grade.

Probabilidade de Detecção (POD) – probabilidade do objeto da busca ser

detectado, supondo-se que o mesmo se encontra na área onde as buscas estejam

sendo efetuadas. A POD é uma função do fator de cobertura, do sensor utilizado,

das condições da busca e da precisão com a qual os meios de busca estão

navegando para seguir a configuração dos padrões de busca designados. A POD

mede a efetividade do sensor sob a as condições de busca reinantes.

Probabilidade de Sucesso (POS) – probabilidade de se encontrar o objeto da

busca em uma busca determinada. Para cada subárea coberta, POS = POC x POD.

A POS mede a efetividade da busca.

Unidade de Busca e Salvamento (SRU) – recurso móvel composto por pessoal

habilitado e dotado de equipamento apropriado para executar com rapidez as

operações de Busca e Salvamento.

Veículos aéreos não tripulados (VANT) – uma aeronave ou um balão que não

transporta um operador humano e é capaz de voar por controle remoto ou

autônomo.

139

APÊNDICE A – Estimação de parâmetros

Na estatística, a estimação de parâmetro se divide em estimação por ponto e

em estimação por intervalo. Na primeira, deseja-se apenas fornecer a melhor

estimativa possível para um parâmetro a partir de determinada amostra de uma

população. Na segunda, trabalha-se com intervalos de confiança, ou seja, analisam-

se medidas de posição77 e de dispersão78 para estimar a média com determinado

grau de confiança. Por se tratar de um breve resumo, serão abordados apenas os

conceitos utilizados nesta pesquisa de mestrado, porém, cabe ressaltar que esse

assunto é bastante amplo.

Quando a análise de um fenômeno é conduzida por simulações, cada

simulação é um elemento de uma amostra. Então, quando se calculou a média do

tempo de busca na Figura 25 (página 96), foi obtida, na verdade, a média amostral.

Assim, é preciso saber quanto a média amostral corresponde, de fato, ao fenômeno

– ou seja, à média populacional. A Figura 41 ilustra a ideia da amostragem.

Figura 41 – População versus Amostra

77

As medidas de posição servem para localizar a distribuição de frequências sobre o eixo de variação em questão. As principais medidas de posição são: média aritmética, mediana e moda. Em geral, as medidas de posição precisam ser complementadas pelas medidas de dispersão. 78

As medias de dispersão indicam quanto os dados se encontram dispersos em torno da região central. As principais medidas de dispersão são: amplitude, variância, desvio-padrão e o coeficiente de variação.

140

Sabe-se que, segundo o Teorema Central do Limite, sendo o número de

simulações, fazendo , a média amostral calculada se iguala à média

populacional. Ou seja:

(2)

Dessa forma, como não é possível realizar infinitas simulações, deseja-se

estimar a média populacional ( ) pela média amostral:

(3)

em que é o tamanho da amostra e é medida obtida na i-ésima simulação.

Assim, quanto maior o tamanho da amostra, melhor será a precisão de , ou seja,

mais se aproximará da média populacional ( ).

Já a variância amostral ( ), importante medida de dispersão utilizada na

estimação de parâmetros, pode ser calculada por:

(4)

Logo, o desvio-padrão amostral é:

(5)

Tendo a média amostral e o desvio-padrão amostral, pode-se estimar a média

populacional utilizando a estimação por intervalo. Assim, deseja-se construir o

intervalo de confiança, que, com probabilidade conhecida, deverá conter o valor real

do parâmetro (nesse caso, o parâmetro é a média).

Então, o intervalo a ser construído será do tipo , sendo necessário

apenas determinar de modo que o intervalo possua nível de confiança .

Matematicamente tem-se o seguinte:

141

(6)

De acordo com Costa Neto (2002), supondo que a distribição amostral do

estimador seja normal79, a semi-amplitude do intervalor de confiança é dada por:

(7)

em que é o desvio-padrão da população, o tamanho da amostra, é o

grau de confiança da estimativa e é obtido pela Tabela 6.

Porém, o fenômeno observado na simulação desta pesquisa de mestrado

(redução do tempo de busca utilizando VANTs cooperativos) possui desvio-padrão

desconhecido. Nesse caso, trabalhando com as informações disponíveis, estima-se

a desvio-padrão populacional pelo desvio-padrão amostral apresentado na equação

(5). No entanto, a simples substitução de por na expressão (7) reduziria o grau

de certeza na construção do intervalo de confiança. Portanto, deve-se corrigir o

intervalo para compensar o efeito dessa maior incerteza. Para isso, utiliza-se a

distribuição t de Student com graus de liberdade, obtendo a seguinte semi-

amplitude para o intervalo de confiança:

(8)

em que é otibdo pela Tabela 7, é o grau de confiança da estimativa e

é o tamanho da amostra. Assim, a interpretação do intervalo obtido é:

(9)

Logo, para determinar o número de simulações que deve ser feita ( ) para

que seja uma boa estimativa de , garantindo um grau de confiança de ,

basta estabelecer o erro tolerável ( ) e isolar na expressão (8):

79

Isso ocorrerá se a população for normalmente distribuída ou, caso contrário, com boa aproximação, se a amostra for suficientemente grande (COSTA NETO, 2002, p. 68).

142

(10)

em que ’ é o tamanho de uma amostra-piloto extraída apenas para calcular a

estimativa . Se , conclui-se que a amostra-piloto já teria sido suficiente para

a estimação. Caso contrário, deve-se continuar amostrando (COSTA NETO, 2002).

Porém, no caso em questão, a distribuição amostral não segue uma

distribuição normal. Nesse caso, apesar de Costa Neto (2002) afirmar que uma

amostra suficientemente grande contornaria esse “problema”, a análise não

paramétrica é a mais indicada (HOLLANDER e WOLFE, 1999). A Figura 42,

construída com auxílio do software estatístico R (R-PROJECT, 2012), apresenta o

histograma das 1000 simulações utilizadas na construção do gráfico da Figura 25.

Conforme pode ser observado, a distribuição amostral não segue uma distribuição

normal.

Figura 42 – Histograma80

. O eixo x apresenta as medidas observadas do tempo de busca e o eixo y

apresenta as frequências observadas nos intervalos ilustrados no gráfico.

80

Os comandos utilizados foram, nessa ordem, os seguintes: > xn <- scan("filename.txt", what=numeric(0), n=1e6) # importa as medidas

> hist(xn) # desenha histograma

> hist(xn, seq(0, 5000, 500), prob=TRUE) # desenha histograma

> lines(density(xn, bw=250)) # cria linha contínua

> lines(density(xn, bw=500)) # cria linha contínua

143

Figura 43 – Mesmo histograma da Figura 42, mas com a função de densidade traçada com maior

granularidade (também utilizando o software estatístico R).

A análise visual, por si só, já é suficiente para afirmar que o histograma não

segue a distribuição normal. No entanto, para verificar a aderência a uma

distribuição normal, também foi realizado o teste de aderência qui-quadrado

(COSTA NETO, 2002, p. 132). O resultado do teste confirmou a não aderência da

amostra a uma distribuição normal.

Nesse caso, deve-se realizar um teste não paramétrico. Um teste não

paramétrico é indicado quando a premissa de que a distribuição populacional segue

uma distribuição normal é questionável. Além da vantagem de não precisar assumir

distribuição normal, os testes não paramétricos possuam as seguintes vantagens

(HOLLANDER e WOLFE, 1999; SIEGEL e CASTELLAN, 1988):

Os métodos não paramétricos também são indicados para situações

em que não é viável obter amostras grandes, ou seja, há restrições

quanto ao tamanho da amostra;

Normalmente (não sempre) apresentam fácil aplicação;

144

São relativamente insensíveis a outliers81;

Por último, os métodos não paramétricos são aplicáveis a inúmeras

situações onde os métodos paramétricos são intratáveis. Como, por

exemplo, a dados não numéricos.

Por outro lado, as desvantagens dos métodos não paramétricos são que eles

são menos poderosos do que os paramétricos, pois trabalham com menos

informação, e são menos flexíveis, permitindo trabalhar com um intervalo menor de

hipóteses do que os testes paramétricos (SIEGEL e CASTELLAN, 1988).

Os principais (mais conhecidos e mais utilizados na literatura) métodos não

paramétricos para análise de uma amostral são o Teste do Sinal 82 e Teste de

Wilcoxon 83 (EASTON e MCCOLL, 2012; FERREIRA, 2006; GIBBONS e

CHAKRABORTI, 2010; HOLLANDER e WOLFE, 1999). Ambos trabalham com a

mediana ao invés da média, que é utilizada pelos métodos paramétricos mais

tradicionais. No entanto, apesar de os testes não paramétricos requisitarem menos

premissas do que os testes paramétricos, eles ainda fazem algumas suposições.

O Teste de Wilcoxon faz assume que as medidas amostrais são mutuamente

independentes e que a população é contínua e, além disso, simétrica em relação à

mediana (HOLLANDER e WOLFE, 1999).

Já o Teste do Sinal, também assume que as medidas amostrais são

independentes umas das outras. Porém, assume apenas que a população é

contínua (HOLLANDER e WOLFE, 1999), ou seja, não supõe que a população é

simetricamente distribuída ao redor da mediana. Essa flexibilização faz com que o

Teste do Sinal seja menos poderoso do que o Teste de Wilcoxon (EASTON e

MCCOLL, 2012). Portanto, para as simulações desta pesquisa de mestrado, o Teste

do Sinal seria o mais indicado.

Cabe ressaltar, também, que não existe consenso na doutrina sobre a

estimação do tamanho da amostra para distribuições não paramétricas. Além disso,

observou-se que os testes não paramétricos não mais utilizados para a comparação

de amostras pareadas (por exemplo, para saber se duas amostras pertencem à

81

Medidas discrepantes que prejudicam a análise. Em análises paramétricas, normalmente, os outliers são eliminados. 82

Sign Test 83

Wilcoxon Signed Ranks Test

145

mesma população). Para maiores detalhes sobre os métodos não paramétricos,

sugere-se consultar as referências citadas.

Além disso, esta pesquisa não poderia deixar de mencionar a existência do

software estatístico PASS (NCSS STATISTICAL SOFTWARE, 2012), que facilita

bastante a realização de cálculos estatísticos, tanto para testes paramétricos quanto

para testes não paramétricos. Porém, o cálculo do tamanho de amostras utilizando o

Teste do Sinal não é disponibilizado e o software é proprietário84.

Por fim, cabe destacar, também, que, para a estimação do tamanho da

amostra, dependendo da natureza da distribuição85, também é possível utilizar a

seguinte regra prática: estimar o tamanho da amostra utilizando a equação (10) e

adicionar mais 15% (LEHMANN, 1998) – equação (11), onde é o tamanho da

amostra que atende a equação (10):

(11)

Conforme se observa na Figura 42 e na Figura 43, a distribuição (que foi

construída com um número razoável de medidas: 1000) não possui caudas que

tendem ao infinito e não apresenta uma forma incomum.

Portanto, decidiu-se pela utilização dessa regra prática para estimar o

tamanho da amostra. Assim, aplicando a regra ao tamanho da amostra obtido pela a

equação (10), , obtém-se .

Utilizando a amostra de 1000 simulações (Figura 25), calculou-se a variância

amostral ( ). O grau de confiança foi definido em 95%, logo:

. O erro tolerável ( ), estabelecido por critério de razoabilidade, foi definido em

100 86 . Por fim, obteve-se

da Tabela 7 e calculou-se . Então,

aplicando a regra prática de Lehmann, obtém-se que o tamanho da amostra

.

84

O preço da licença é US$ 1095 para uso comercial e US$ 795 para uso acadêmico ou para uso governamental. 85

A distribuição deve ser construída a partir de um número razoável de medidas amostrais (algumas dezenas) e não deve ser muito incomum (não possui caudas infinitas que aumentam consideravelmente o desvio padrão) 86

Menos de 5% de média amostral e 2% no número máximo de células navegadas por cada VANT.

146 Tabela 6 – Distribuição Normal. Valores de .

Z0 0 1 2 3 4 5 6 7 8 9

0,0 0,0000 0,0040 0,0080 0,0120 0,0160 0,0199 0,0239 0,0279 0,0319 0,0359

0,1 0,0398 0,0438 0,0478 0,0517 0,0557 0,0596 0,0636 0,0675 0,0714 0,0753

0,2 0,0793 0,0832 0,0871 0,0910 0,0948 0,0987 0,1026 0,1064 0,1103 0,1141

0,3 0,1179 0,1217 0,1255 0,1293 0,1331 0,1368 0,1406 0,1443 0,1480 0,1517

0,4 0,1554 0,1591 0,1628 0,1664 0,1700 0,1736 0,1772 0,1808 0,1844 0,1879

0,5 0,1915 0,1950 0,1985 0,2019 0,2054 0,2088 0,2123 0,2157 0,2190 0,2224

0,6 0,2257 0,2291 0,2324 0,2357 0,2389 0,2422 0,2454 0,2486 0,2517 0,2549

0,7 0,2580 0,2611 0,2642 0,2673 0,2704 0,2734 0,2764 0,2794 0,2823 0,2852

0,8 0,2881 0,2910 0,2939 0,2967 0,2995 0,3023 0,3051 0,3078 0,3106 0,3133

0,9 0,3159 0,3186 0,3212 0,3238 0,3264 0,3289 0,3315 0,3340 0,3365 0,3389

1,0 0,3413 0,3438 0,3461 0,3485 0,3508 0,3531 0,3554 0,3577 0,3599 0,3621

1,1 0,3643 0,3665 0,3686 0,3708 0,3729 0,3749 0,3770 0,3790 0,3810 0,3830

1,2 0,3849 0,3869 0,3888 0,3907 0,3925 0,3944 0,3962 0,3980 0,3997 0,4015

1,3 0,4032 0,4049 0,4066 0,4082 0,4099 0,4115 0,4131 0,4147 0,4162 0,4177

1,4 0,4192 0,4207 0,4222 0,4236 0,4251 0,4265 0,4279 0,4292 0,4306 0,4319

1,5 0,4332 0,4345 0,4357 0,4370 0,4382 0,4394 0,4406 0,4418 0,4429 0,4441

1,6 0,4452 0,4463 0,4474 0,4484 0,4495 0,4505 0,4515 0,4525 0,4535 0,4545

1,7 0,4554 0,4564 0,4573 0,4582 0,4591 0,4599 0,4608 0,4616 0,4625 0,4633

1,8 0,4641 0,4649 0,4656 0,4664 0,4671 0,4678 0,4686 0,4693 0,4699 0,4706

1,9 0,4713 0,4719 0,4726 0,4732 0,4738 0,4744 0,4750 0,4756 0,4761 0,4767

2,0 0,4772 0,4778 0,4783 0,4788 0,4793 0,4798 0,4803 0,4808 0,4812 0,4817

2,1 0,4821 0,4826 0,4830 0,4834 0,4838 0,4842 0,4846 0,4850 0,4854 0,4857

2,2 0,4861 0,4864 0,4868 0,4871 0,4875 0,4878 0,4881 0,4884 0,4887 0,4890

2,3 0,4893 0,4896 0,4898 0,4901 0,4904 0,4906 0,4909 0,4911 0,4913 0,4916

2,4 0,4918 0,4920 0,4922 0,4925 0,4927 0,4929 0,4931 0,4932 0,4934 0,4936

2,5 0,4938 0,4940 0,4941 0,4943 0,4945 0,4946 0,4948 0,4949 0,4951 0,4952

2,6 0,4953 0,4955 0,4956 0,4957 0,4959 0,4960 0,4961 0,4962 0,4963 0,4964

2,7 0,4965 0,4966 0,4967 0,4968 0,4969 0,4970 0,4971 0,4972 0,4973 0,4974

2,8 0,4974 0,4975 0,4976 0,4977 0,4977 0,4978 0,4979 0,4979 0,4980 0,4981

2,9 0,4981 0,4982 0,4982 0,4983 0,4984 0,4984 0,4985 0,4985 0,4986 0,4986

3,0 0,4987 0,4987 0,4987 0,4988 0,4988 0,4989 0,4989 0,4989 0,4990 0,4990

3,1 0,4990 0,4991 0,4991 0,4991 0,4992 0,4992 0,4992 0,4992 0,4993 0,4993

3,2 0,4993 0,4993 0,4994 0,4994 0,4994 0,4994 0,4994 0,4995 0,4995 0,4995

3,3 0,4995 0,4995 0,4995 0,4996 0,4996 0,4996 0,4996 0,4996 0,4996 0,4997

3,4 0,4997 0,4997 0,4997 0,4997 0,4997 0,4997 0,4997 0,4997 0,4997 0,4998

3,5 0,4998 0,4998 0,4998 0,4998 0,4998 0,4998 0,4998 0,4998 0,4998 0,4998

3,6 0,4998 0,4998 0,4999 0,4999 0,4999 0,4999 0,4999 0,4999 0,4999 0,4999

3,7 0,4999 0,4999 0,4999 0,4999 0,4999 0,4999 0,4999 0,4999 0,4999 0,4999

3,8 0,4999 0,4999 0,4999 0,4999 0,4999 0,4999 0,4999 0,4999 0,4999 0,4999

3,9 0,5000 0,5000 0,5000 0,5000 0,5000 0,5000 0,5000 0,5000 0,5000 0,5000

147 Tabela 7 – Distribuições t de Student. Valores de onde .

Graus de liberdade ( )

P

0,20 0,10 0,05 0,025 0,01 0,005

1 1,376 3,078 6,314 12,706 31,821 63,657

2 1,061 1,886 2,920 4,303 6,965 9,925

3 0,978 1,638 2,353 3,182 4,541 5,841

4 0,941 1,533 2,132 2,776 3,747 4,604

5 0,920 1,476 2,015 2,571 3,365 4,032

6 0,906 1,440 1,943 2,447 3,143 3,707

7 0,896 1,415 1,895 2,365 2,998 3,499

8 0,889 1,397 1,860 2,306 2,896 3,355

9 0,883 1,383 1,833 2,262 2,821 3,250

10 0,879 1,372 1,812 2,228 2,764 3,169

11 0,876 1,363 1,796 2,201 2,718 3,106

12 0,873 1,356 1,782 2,179 2,681 3,055

13 0,870 1,350 1,771 2,160 2,650 3,012

14 0,868 1,345 1,761 2,145 2,624 2,977

15 0,866 1,341 1,753 2,131 2,602 2,947

16 0,865 1,337 1,746 2,120 2,583 2,921

17 0,863 1,333 1,740 2,110 2,567 2,898

18 0,862 1,330 1,734 2,101 2,552 2,878

19 0,861 1,328 1,729 2,093 2,539 2,861

20 0,860 1,325 1,725 2,086 2,528 2,845

21 0,859 1,323 1,721 2,080 2,518 2,831

22 0,858 1,321 1,717 2,074 2,508 2,819

23 0,858 1,319 1,714 2,069 2,500 2,807

24 0,857 1,318 1,711 2,064 2,492 2,797

25 0,856 1,316 1,708 2,060 2,485 2,787

26 0,856 1,315 1,706 2,056 2,479 2,779

27 0,855 1,314 1,703 2,052 2,473 2,771

28 0,855 1,313 1,701 2,048 2,467 2,763

29 0,854 1,311 1,699 2,045 2,462 2,756

30 0,854 1,310 1,697 2,042 2,457 2,750

40 0,851 1,303 1,684 2,021 2,423 2,704

50 0,849 1,299 1,676 2,009 2,403 2,678

100 0,845 1,290 1,660 1,984 2,364 2,626

200 0,843 1,286 1,653 1,972 2,345 2,601

0,842 1,282 1,645 1,960 2,326 2,576

Documents

PROPOSTA DE MODELO DE VEÍCULOS AÉREOS NÃO … · Operações de Busca e Salvamento. Algoritmos de navegação. ABSTRACT There are an increasing number of researches into UAV (Unmanned