Controle de Missão de Voo de , Veículo Aéreo Não-Tripulado

Lucas Pluceno Behnck

Controle de Missão de Voo deVeículo Aéreo Não-Tripulado

Porto Alegre

2014



Projeto de diplomação realizado na Universi-dade Federal do Rio Grande do Sul, departa-mento de Engenharia Elétrica.

Universidade Federal do Rio Grande do Sul - UFRGS

Departamento de Engenharia Elétrica

Orientador: Prof. Dr. Carlos Eduardo Pereira

Porto Alegre2014

CIP - Catalogação na Publicação

Elaborada pelo Sistema de Geração Automática de Ficha Catalográfica da UFRGS com osdados fornecidos pelo(a) autor(a).

Pluceno Behnck, Lucas Controle de Missão de Voo de Veículo Aéreo Não-Tripulado / Lucas Pluceno Behnck. -- 2014. 58 f.

Orientador: Carlos Eduardo Pereira.

Trabalho de conclusão de curso (Graduação) --Universidade Federal do Rio Grande do Sul, Escola deEngenharia, Curso de Engenharia Elétrica, PortoAlegre, BR-RS, 2014.

1. Veículos Aéreos Não Tripulados. 2. SimulatedAnnealing. 3. Cálculo de Trajetória. I. EduardoPereira, Carlos, orient. II. Título.



Projeto de diplomação realizado na Universi-dade Federal do Rio Grande do Sul, departa-mento de Engenharia Elétrica.

Porto Alegre, 26 de março de 2014:

Prof. Dr. Carlos Eduardo PereiraOrientador

Ivan MüllerConvidado 1

Edison de Freitas PignatonConvidado 2

Porto Alegre2014

ResumoEste trabalho propõe um módulo embarcado capaz de realizar o cálculo de trajetóriasde pequenos veículos aéreos não tripulados. Primeiro, o modelo do VANT e do módulode Controle de Missão é descrito através de diagramas SysML. Em seguida apresenta-se a concepção de uma plataforma embarcada utilizando um Raspberry Pi capaz decomunicar-se com os VANTs estudados. Dois estudos de caso são apresentados. O primeiroestudo demonstra uma missão cujo objetivo é a visita de diversas localidades (pontosde interesse) em uma região, percorrendo a menor distância possível. A trajetória devisita destes pontos é calculada através do algoritmo Simulated Annealing clássico. Nosegundo caso, considera-se que os pontos de interesse estão classificados em duas categorias,que devem ser visitadas por dois VANTs especializados em cada uma destas categorias.Neste caso, o algoritmo Simulated Annealing é modificado para permitir a otimizaçãodas duas trajetórias. Ambos algoritmos são testados e têm seus desempenhos avaliados,monstrado-se adequados às aplicações. Finalmente, o módulo desenvolvido é testado comsucesso interagindo com múltiplos VANTs em um simulador de voo. Palavras-chaves:VANT. Simulated Anneling. Cálculo de Trajetória.

AbstractThis work proposes an embedded module capable of calculating paths for small UnmannedAircraft (UA). The UA is modeled through SysML diagrams, then the embedded platformis developed using a Raspberry Pi. Two study cases are presented. The first study casepresents an mission in which the UA must inspect a given list of locations (points ofinterest) in the best possible manner. In this mission, the flight path is calculated using theSimulated Annealing meta-heuristic. The following study case presents a situation whereeach one of the points of interest belongs to a different class, and should be inspectedby an UA with the appropriate specialization. To take this restriction into account; anmodified Simulated Annealing is proposed. The two algorithms are successfully tested forboth applications. The developed module is tested with the support of flight simulator,interacting simultaneously with multiple UAVs.

Key-words: Unmanned Aircraft. Simulated Annealing. Path Planning.

Lista de ilustrações

Figura 1 – Exemplo de VANT de Asa Fixa . . . . . . . . . . . . . . . . . . . . . . 13Figura 2 – Exemplo de VANT de Asa Rotativa . . . . . . . . . . . . . . . . . . . . 13Figura 3 – Classificações dos VANTs. . . . . . . . . . . . . . . . . . . . . . . . . . 14Figura 4 – Taxonomia dos diagramas SysML. . . . . . . . . . . . . . . . . . . . . 16Figura 5 – Um VANT com quatro rotores. . . . . . . . . . . . . . . . . . . . . . . 23Figura 6 – Diagrama de caso de uso simplificado do módulo de controle da missão. 24Figura 7 – Diagrama de caso de uso do controle de missão com modos de vôo. . . 25Figura 8 – Diagrama estrutural do veículo aéreo não tripulado. . . . . . . . . . . . 26Figura 9 – Diagrama estrutural do veículo aéreo não tripulado. . . . . . . . . . . . 27Figura 10 – Diagrama de definição dos blocos do Controle de Missão. . . . . . . . . 29Figura 11 – Raspberry Pi Model A. . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Figura 12 – Diagrama de sequência. . . . . . . . . . . . . . . . . . . . . . . . . . . 32Figura 13 – Diagrama de blocos do simulador de voo utilizado. . . . . . . . . . . . 33Figura 14 – Ilustração do estudo de caso 1. Os círculos vermelhos indicam pontos de

interesse detectados pelo primeiro VANT e que devem ser inspecionadosposteriormente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Figura 15 – Trajetórias dos VANTs em uma missão de varredura e inspeção. . . . . 35Figura 16 – Exemplo de trajetórias 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 37Figura 17 – Exemplo de trajetórias 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 37Figura 18 – Ilustração do segundo estudo de caso. . . . . . . . . . . . . . . . . . . . 41Figura 19 – Console de execução do Controle de Missão no Raspberry Pi. . . . . . 42Figura 20 – Visualização gráfica do vôo do VANT. . . . . . . . . . . . . . . . . . . 43Figura 21 – Console do simulador exibindo as informações do veículo aéreo. . . . . 43Figura 22 – Resolução de cinco problemas através do método de Simulated Annealing

original. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Figura 23 – Trajetória de visita a todos os POIs antes da otimização. . . . . . . . . 46Figura 24 – Trajetória otimizada de visita a todos os POIs. . . . . . . . . . . . . . 47Figura 25 – Simulated Annealing modificado com coeficiente de penalidade λ = 0, 15. 48Figura 26 – Simulated Annealing modificado com coeficiente de penalidade λ = 0. . 50Figura 27 – Trajetória planejada previamente para realização de varredura pelo

VANT Mestre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51Figura 28 – Voo do VANT 1 e detecção dos pontos de interesse. . . . . . . . . . . . 52Figura 29 – Rotas calculadas para os VANTs inspetores. . . . . . . . . . . . . . . . 53Figura 30 – Voo dos VANTs inspetores. . . . . . . . . . . . . . . . . . . . . . . . . 53

Lista de tabelas

Tabela 1 – Parâmetros utilizados na execução das otimizações por Simulated An-nealing Modificado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Tabela 2 – Comparação dos resultados demonstrados nas Figuras 22 e 25. . . . . . 48Tabela 3 – Energia das Soluções Ótimas nos três experimentos. . . . . . . . . . . . 50Tabela 4 – Parâmetros utilizados na execução da otimização por Simulated Annea-

ling Modificado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

Lista de abreviaturas e siglas

VANT Veículo Aéreo Não Tripulado

UAV Unmanned Aerial Vehicle

GPS Sistema de Posicionamento Global

POI Ponto de Interesse (Point of Interest)

GA Algoritmos Genéticos (Genetic Algorithms)

SA Simulated Annealing

Sumário

1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 REFERENCIAIS TEÓRICOS . . . . . . . . . . . . . . . . . . . . . . 122.1 Veículos Aéreos Não Tripulados . . . . . . . . . . . . . . . . . . . . . 122.2 Engenharia de Sistemas Baseada em Modelos . . . . . . . . . . . . . 142.2.1 SysML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2.1.1 Diagrama de Definição de Blocos . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.1.2 Diagrama de Caso de Uso . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 Cálculo de trajetória . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3.1 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3.1.1 Simulated Annealing no problema do Vendedor Viajante . . . . . . . . . . . . . . . 18

2.4 Cálculo da Distância entre Pontos Geográficos . . . . . . . . . . . . 192.4.1 Norma WGS84 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.4.2 Cálculo de distâncias através do método de Haversine . . . . . . . . . . . . 19

3 PROJETO DE UM MÓDULO DE CONTROLE DE MISSÃO EM-BARCADO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.1 Apresentação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.1.1 Especificação da Aeronave . . . . . . . . . . . . . . . . . . . . . . . . . . 223.2 Modelagem do Sistema em SysML . . . . . . . . . . . . . . . . . . . 233.2.1 Caso de Uso do Controle de Missão . . . . . . . . . . . . . . . . . . . . . 243.2.2 Modelos do VANT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.2.3 Diagrama de definição dos Blocos do Controle de Missão . . . . . . . . . . 283.3 Plataforma Embarcada . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.3.1 Comunicação entre Controle de Missão e VANT . . . . . . . . . . . . . . . 303.3.2 Troca de mensagens entre o módulo de Controle de Missão e o VANT . . . 313.4 Simulador de Voo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.5 Estudos de caso do controle de missão embarcado. . . . . . . . . . . 333.5.1 Pontos de interesse homogêneos. . . . . . . . . . . . . . . . . . . . . . . . 343.5.1.1 Cálculo da trajetória de inspeção de POI. . . . . . . . . . . . . . . . . . . . . . 35

3.5.2 Missão com pontos de interesse heterogêneos. . . . . . . . . . . . . . . . . 363.5.2.1 Cálculo das trajetórias de inspeção de POI por dois VANTs com especialidades diferentes. 37

3.5.2.2 Implementação da Missão utilizando três aeronaves não tripuladas. . . . . . . . . . . 40

4 RESULTADOS E DISCUSSÕES . . . . . . . . . . . . . . . . . . . . 42

4.1 Comunicação entre Controle de Missão e Simulador . . . . . . . . . 424.2 Teste do algoritmo Simulated Annealing embarcado no caso de

pontos de interesse homogêneos. . . . . . . . . . . . . . . . . . . . . 444.2.1 Teste no simulador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454.3 Simulação com VANTs e Pontos de Interesse Heterogêneos . . . . . 474.3.1 Simulated Annealing Modificado . . . . . . . . . . . . . . . . . . . . . . . 474.3.2 Execução de uma Missão de Varredura e Inspeção com Três VANTs . . . . 51

5 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

ANEXOS 57

ANEXO A – LOCALIZAÇÃO DA REGIÃO DE GERAÇÃO DE PON-TOS DE INTERESSE ALEATÓRIOS. . . . . . . . . . 58

11

1 Introdução

Espera-se que o uso civil de veículos aéreos não tripulados (VANTs) torne-seimportante, sobretudo na agricultura de precisão e segurança pública (JENKINS, 2014).Esta constatação motiva a pesquisa de novas soluções no uso de VANTs a fim de obternovas funcionalidades e maior autonomia.

Os projetos nos quais este trabalho estão inseridos estudam o uso de veículos aéreosem missões de diferentes naturezas, como, por exemplo, na localização de animais napecuária, na busca de vítimas de tragédias naturais ou ainda na localização de fraturasem grandes estruturas civis, como pontes ou edifícios. Estuda-se também a comunicação einteração entre os diferentes agentes atuando no ambiente, como VANTs e sensores.

Este trabalho de conclusão de curso propõe um Módulo de Controle de Missão. Oobjetivo deste projeto é obter um módulo a ser adicionado no veículo aéreo não tripulado,permitindo que o VANT calcule autonomamente missões (trajetórias) baseando-se emobjetivos pré-definidos e nas informações do ambiente disponíveis. Este trabalho concentra-se na elaboração dos modelos do Controle de Missão, no projeto da plataforma embarcadae no estudo e implementação dos algoritmos de cálculo de trajetória.

O Módulo de Controle de Missão é capaz de coordenar a execução de missões devarredura e inspeção realizadas por múltiplos VANTs. Nestas missões, um primeiro VANTsobrevoa uma área identificando pontos de interesse, e em seguida ordena a inspeção destespontos de interesse por outros VANTs através de trajetórias calculadas visando minimizara distância percorrida pelas aeronaves. Para que este cálculo seja realizado, o trabalhoapresenta o uso da meta-heurística Simulated Annealig modificada, permitindo o cálculode múltiplas trajetórias simultaneamente.

Este trabalho está estruturado como segue: na Seção 2 revisam-se conceitos sobreos quais este trabalho utilizados neste trabalho; na Seção 3 a proposta do Módulo deControle de Missão é apresentada; na Seção 4 os resultados obtidos são demonstrados ediscutidos; a Seção 5 apresenta as conclusões sobre o trabalho realizado.

12

2 Referenciais Teóricos

Esta seção revisa alguns conceitos que são utilizados ao longo do desenvolvimentodeste trabalho. A seção 2.1 descreve o que são os veículos aéreos não tripulados e algumasde suas características principais. Em seguida, tendo em vista que a modelagem do VANTe do Controle de Missão é o primeiro objetivo deste trabalho, conceitos sobre EngenhariaBaseada em Modelos e a linguagem SysML são explicados na seção 2.2. A seção 2.3revisa alguns algoritmos de otimização heurísticos e detalha o método chamado SimulatedAnnealing, utilizado para o cálculo de trajetória. Finalmente, a necessidade de calculara distância total de uma trajetória na resolução dos algoritmos de otimização implica oestudo da norma WGS84 e no método mais adequado de calcular de distâncias, tópicosabordados na seção 2.4.

2.1 Veículos Aéreos Não TripuladosEsta seção revisa os conceitos sobre os veículos aéreos não tripulados, baseados no

livro Unmanned Aircraft Systems (AUSTIN, 2011).

Os veículos aéreos não tripulados são definidos como aeronaves que não carregamum operador, podendo ser controladas remotamente ou voar de maneira autônoma . Otermo "sistema aéreo não tripulado" pode também ser utilizado, denotando o conjunto detodos os outros elementos necessários ao funcionamento de um veículo aéreo não tripulado,incluindo por exemplo uma estação base ou o operador remoto.

Existem diversas situações onde o uso de VANTs traz vantagens em relação autilização de veículos aéreos tripulados. Em operações militares, os VANTs podem desem-penhar missões de alto risco sem colocar em perigo uma tripulação humana. Podem aindadesempenhar longas missões de vigilância, extremamente cansativas para a tripulação.As possibilidades de uso civil de VANTs também são numerosas. Os VANTs podem serutilizados em situações com potencial de contaminação de humanos, como aplicação deagrotóxicos ou monitoramento de vazamentos químicos ou radioativos. Pesquisas científicaspodem utilizar VANTs para testar novos métodos de voo ou de missões aéreas, comcustos e riscos reduzidos. Além disso, a disponibilidade de veículos aéreos não tripuladoscomerciais, de baixo custo e de fácil utilização, tornam viáveis o uso de VANTs em áreascomo agricultura de precisão ou filmagens aéreas.

As características dos VANTs variam conforme a aplicação, mas alguns elementosfundamentais estão presentes em praticamente todas as aeronaves. O Sistema de Navegação,por exemplo, é responsável pelas informações de posicionamento da aeronave. Estas

Capítulo 2. Referenciais Teóricos 13

informações podem ser enviadas para a estação base e utilizadas pelos operadores remotosno rastreio da aeronave ou modificação das missões de voo, ou ainda utilizadas pelossistemas de controle de voo da aeronave em uma situação de navegação autônoma. Umcanal de comunicação entre a estação base e a aeronave é outro elemento quase semprepresente. Dependendo da aplicação, este canal pode usado pelos operadores com o objetivode monitorar ou controlar a aeronave remotamente. Além disso, a aeronave pode utilizareste meio de comunicação para enviar fotografias, filmagens ou outros tipos de dadoscoletados durante a execução de uma missão.

Outras características são extremamente dependentes da aplicação da aeronave. Asdimensões das aeronaves podem variar desde VANTs militares com envergadura de dezenasde metros até pequenos VANTs capazes de serem lançados manualmente e utilizados emmissões locais. A capacidade de carga destes veículos é outro elemento dependente daaplicação. Aeronaves militares, por exemplo, podem transportar armamentos ou radarescujo peso pode chegar a centenas de quilogramas. Já em uma aplicação civil, a carga podeser composta por sensores ou câmeras pesando algumas centenas de gramas.

Figura 1 – Exemplo de VANT de AsaFixa

Figura 2 – Exemplo de VANT de AsaRotativa

Fonte: Wikimedia Commons.

Convém também ressaltar a classificação dos VANTs conforme seu modo de voo.As aeronaves de asa fixa (Figura 1) geram sustentação através da passagem do ar emvelocidade ao longo de suas asas que permanecem fixas à fuselagem. Um ou mais motoressão responsáveis por manter a velocidade da aeronave, permitindo assim seu voo (excetono caso de planadores). Estes VANTs precisam de pistas para efetuar pousos ou decolagens,ou ainda podem ser arremessados em voo manualmente ou com o auxílio de lançadoresespeciais. Já em um VANT de asa rotativa (Figura 2), a sustentação é gerada diretamentepelas pás dos rotores, o que permite a aeronave pousar e decolar verticalmente e pairarno ar. As principais diferenças de desempenho entre estes dois tipos de aeronaves sãosuas velocidades, autonomias, capacidades de carga e mobilidade. Os VANTs de asa fixademonstram-se superiores nos três primeiros aspectos, enquanto os VANTs de asa rotativapossuem mobilidade superior, capazes de operar em regiões com grandes restrições depouso e decolagem. Isto significa que a escolha na utilização de um ou outro dependerásempre das necessidades da aplicação.


Esta seção apresentou conceitos gerais sobre os veículos aéreos não tripulados quesão apresentados de maneira resumida através da Figura 3. A modelo do sistema utilizadoneste projeto será apresentado com mais detalhes posteriormente na Seção 3.2.

Figura 3 – Classificações dos VANTs.

Classificação dos VANTs

Aplicação

Militar Civil

Voo

Controlado Remotamente

Autônomo

Sustentação

Asa Fixa Asa

Rotativas

2.2 Engenharia de Sistemas Baseada em ModelosO uso de modelos na engenharia tem como objetivo reduzir a complexidade dos

sistemas estudados através de abstrações (BEYDEDA et al., 2005). Estas abstraçõesrepresentam os aspectos essenciais de um projeto, correspondentes às suas funcionalidades.Os aspectos não essenciais correspondem, por exemplo, a plataforma em que as funcionali-dades serão implementadas. Este tipo de estudo, embora importante, não precisa ser feitonas etapas iniciais de desenvolvimento.

As abstrações são feitas por meio de modelos, que nada mais são do que representa-ções de um aspecto funcional de um ponto de um projeto. O uso de modelos pode reduzir acomplexidade de um sistema durante a análise, o que permite a previsão de característicasdo sistema, a análise de propriedades específicas e também facilita a comunicação entreengenheiros ou cientistas atuando no projeto.

No contexto de engenharia de sistemas, é necessário que o produto desenvolvidoseja representado sob diferentes visões: modelos estruturais, modelos de comportamento,modelos de custo, etc.. A engenharia baseada em modelos vai ao encontro desta necessidade,proporcionando uma metodologia capaz de facilitar a análise e o projeto deste sistema. Omodelo permite verificar se os produtos satisfazem especificações, assim como proporcionauma base de informações para a análise e o projeto da solução. Tudo isto pode ser feito emdiferentes níveis de abstração, permitindo assim que apenas as características essenciaissejam consideradas inicialmente.

2.2.1 SysML

O SysML (Systems Modelling Language ou Linguagem de Modelagem de Sistemas)(FRIEDENTHAL; MOORE; STEINER, 2009) é uma linguagem gráfica de modelagem


baseada em um perfil UML com extensões. Esta linguagem suporta a especificação, análise,projeto, verificação e validação de sistemas que incluem hardware, software, informação,pessoal, procedimentos e instalações.

Os pilares desta linguagem são os diagramas que representam elementos do modelo.Estes diagramas estão divididos em diferentes categorias: diagramas de comportamento,diagramas de estrutura, e diagramas de requerimentos. A Figura 4 demonstra a classificaçãodos diferentes tipos de diagramas da linguagem SysML.

A primeira categoria, os chamados de diagramas de requerimentos, representam asnecessidades da solução de maneira gráfica. Estes requerimentos podem definir propriedadese categorias como, por exemplo, métodos de verificação, interfaces e desempenho.

Os diagramas estruturais representam os diferentes componentes do sistema emdiversos níveis de abstrações, também demonstrando como os elementos estão relacionadosentre si. O elemento básico destes diagramas é o bloco, que propõe a descrição de umelemento ou sistema. Um bloco pode representar hardware, software, informação, pessoa,procedimento, etc..

Já os diagramas de comportamento têm como objetivo descrever o funcionamentodo modelo. Eles demonstram a transformação das entradas do sistema em saídas, asatividades desempenhadas, máquinas de estado, entre outros.

A modelagem de um sistema utilizando estes diferentes tipos de diagramas tornapossível representa-lo em diferentes níveis de abstração, desde sua composição total até ofuncionamento individual de seus elementos. Isto permite que o modelo seja analisado demaneira hierárquica a partir de diferentes pontos de vista, contribuindo para a compreensãoglobal do sistema.

2.2.1.1 Diagrama de Definição de Blocos

O diagrama de definição de blocos é um diagrama cujo o objetivo é comunicar ainformação estrutural do sistema. Este diagrama apresenta as diferentes relações entre oselementos do sistema, estabelecendo sua hierarquia.

Os elementos do sistema são representados por retângulos, e conectados entre sipor linhas dotadas de ícones em suas extremidades, indicando o tipo de relação entre oselementos conectados.

Uma conexão cujo ícone na extremidade seja um diamante negro representa umarelação de composição entre os blocos, ou seja, um dos blocos é parte fundamental do outro.Já o diamante branco representa uma relação de agregação: esta ligação, embora forte,indica que um dos blocos não é absolutamente necessário ao outro. Uma linha simplesligando dois blocos representa uma relação de associação entre eles.


Este diagrama é utilizado neste trabalho para representar a hierarquia dos elementospresentes nos VANTs e no módulo de controle de missão.

2.2.1.2 Diagrama de Caso de Uso

Os diagramas de Caso de Uso representam as funcionalidades de um sistema,representadas por elipses, e os atores que interagem com ele, representados por um desenhoestilizado de um homem. Estes atores representam todos os elementos externos queinteragem com o sistema sendo modelado.

Figura 4 – Taxonomia dos diagramas SysML.

Fonte: http://www.omgsysml.org/INCOSE-OMGSysML-Tutorial-Final-090901.pdf

2.3 Cálculo de trajetóriaO problema de cálculo de trajetória pertinente a este trabalho corresponde ao

cálculo da melhor trajetória capaz de visitar todas as n localidades (também chamadascidades) dispostas em uma dada região geográfica. Este é um problema de otimizaçãoconhecido como vendedor viajante (traveling salesman), com diferentes métodos de soluçõesdisponíveis na literatura científica. Alguns métodos exatos de resolução deste problemasão conhecidos há bastante tempo: busca por força bruta, programação linear inteira,programação dinâmica, branch and bound, etc.. Como este problema é classificado comoNP-Completo, um método exato implica em grande peso computacional (CORMEN et al.,2001), o que pode representar um obstáculo à implementação embarcada.

Outra possibilidade é a utilização de algoritmos heurísticos ou meta-heurísticos,capazes de se aproximar de soluções ótimas em um uma quantidade muito menor deiterações. Os algoritmos heurísticos podem ser interpretados como algoritmos que buscamsoluções melhores na vizinhança de uma solução inicial a um custo computacional reduzido,


aproximando-se de soluções ótimas. Já os algoritmos de meta-heurística preveem a eventualaceitação de soluções piores (de acordo com um determinado critério) como um meio deevitar a permanência em mínimos locais. Como exemplos destes algoritmos (VOSS, 2001),destacam-se:

• Algoritmos Genéticos, baseados na dinâmica de genética populacionais. Nestesalgoritmos, um conjunto de soluções (população) interagem entre si trocando partede suas informações, de maneira a gerar novas soluções. Estas trocas são realizadaspor meio de diferentes operações inspiradas na genética biológica, como por exemploreprodução, mutação e crossover. Uma função de fitness é responsável por avaliar assoluções e executar estes operadores, de acordo com a função objetiva do problema.

• A Busca Tabu usa procura soluções melhores em uma vizinhança, sem todaviaretornar a um ótimo local previamente visitado. Isto é feito a partir de uma “memória”que armazena um certo número de vizinhos já visitados.

• Otimização por Colônias de Formigas, baseado em uma população de soluções einspirada na dinâmica das formigas em busca de comida. Neste algoritmo, cada umdos indivíduos da população é um agente que trabalha estocasticamente em umasolução. Cada um destes agentes atualiza um modelo probabilístico cujo objetivo éguiar as escolhas dos agentes, de maneira a tornar maior a probabilidade de que osfuturos agentes encontrarão soluções melhores (DORIGO; BIRATTARI, 2010).

• Simulated Annealing é uma meta-heurística baseada em uma analogia com o processode recozimento em metalurgia. Neste processo, buscam-se novas soluções na vizi-nhança de uma certa solução e a probabilidade de aceitação de uma solução inferioré relacionada a uma variável de controle chamada temperatura. Este algoritmo édescrito em mais detalhes na seção a seguir.

Neste trabalho discute-se a implementação de uma de solução meta-heurísticaatravés do método Simulated Annealing. O algoritmo clássico é utilizado otimizandoapenas um objetivo, conforme exposto em Kirkpatrick, Gelatt e Vecchi (1983). Em seguidadiscute-se algoritmos de otimização de vários objetivos, incluindo a possibilidade deadaptação do algoritmo Simulated Annealing para mais de um objetivo.

2.3.1 Simulated Annealing

Em metalurgia, o recozimento de metais (annealing) refere-se a um processo ondeo metal é aquecido até altas temperaturas e em seguida é resfriado lentamente. Esta lentadiminuição da temperatura tem como objetivo fazer com que a configuração atômica domaterial atinja um estado de energia interna mínima. Isto corresponde a um materialcristalino e de ótima qualidade.


De maneira análoga, esta busca pelo estado de menor energia interna pode serinterpretado como um problema de otimização combinatória, desde que seja possívelcalcular sua energia interna a partir de uma dada configuração (função custo). Neste caso,cada configuração do sistema é análoga ao estado de energia interna do sistema físico.

Este método de otimização combinatória é considerado meta-heurístico pois com-binações piores podem ser aceitas durante o transcorrer da otimização a fim de evitar aestagnação em mínimos locais. A cada iteração, a diferença entre a energia da combinaçãogerada e a combinação anterior (∆E) é calculada: caso esta energia seja menor ou igual azero (∆E ≤ 0), a nova combinação é aceita; caso contrário, se ∆E > 0, a aceitação destacombinação é tratada de maneira probabilística: a probabilidade de aceitação é dada pelofator de probabilidade de Boltzmann:

P (∆E) = e∆EkbT , (2.1)

onde kb é a constante de Boltzmann e T é a temperatura. Em seguida um número aleatóriop é gerado no intervalo uniforme [0, 1]. Caso p < P (∆E) a nova configuração é aceita,caso contrário mantém-se a configuração anterior. No início da resolução do problema, atemperatura T possui um valor alto e a probabilidade de se aceitar combinação piores émaior; conforme a resolução prossegue, T diminui, até que próximo ao término da execuçãoda otimização a probabilidade de aceitar-se uma solução pior seja diminuta.

Para que a otimização seja bem-sucedida, é necessário que se determine a faixade temperaturas e outros parâmetros empiricamente de acordo com o problema a serresolvido.

2.3.1.1 Simulated Annealing no problema do Vendedor Viajante

No problema do vendedor viajante, busca-se a melhor ordem de visita de cidades demaneira a minimizar a distância percorrida. Para que se realize a otimização da trajetóriaé necessário definir a função de cálculo da energia correspondente a cada combinação ecomo gerar novas soluções a cada iteração.

Sendo N o número de cidades a serem visitadas e

x = [x1, x2, x3, xi, ..., xN ] (2.2)

a ordem de visita das cidades, busca minimizar a distância total percorrida

disttotal(x) =N−1∑i=1

dist(xi, xi+1). (2.3)

Pode-se considerar que a energia de solução é proporcional a distância total dotrajeto, deste modo obtém se uma definição para a função E(x) a ser utilizada no problemade otimização.


Uma maneira de gerar novas soluções em uma vizinhança é demonstrada porKirkpatrick, Gelatt e Vecchi (1983), através da permutação de dois elementos de umasolução, conforme o exemplo a seguir:

xoriginal =[0 1 2 3 4

]=⇒ xnova =

[0 1 3 2 4

]

2.4 Cálculo da Distância entre Pontos GeográficosA busca de trajetórias ótimas depende do cálculo da distância entre os pontos

geográficos de interesse. Observa-se que localização destes pontos é descrita através de suasLatitudes e Longitudes através da norma WGS84, utilizada na maioria dos sistemas deGPS comerciais. Torna-se necessário então o estudo desta norma e uma maneira compatívelde calcular a distância entre dois pontos de interesse.

2.4.1 Norma WGS84

A norma WGS84 (World Geodetic System 1984 ) define um sistema de coordenadastridimensional terrestre. De acordo com relatório publicado pelo Departamento de Defesados Estados Unidos (2000), as características deste modelo são:

• é um modelo geocêntrico, definindo o centro de massa da Terra,

• a escala é baseada no sistema referencial local da terra,

• sua orientação foi definida inicialmente pelo Bureau International de l’Heure,

• sua evolução temporal não cria rotação residual em relação à crosta terrestre.

Finalmente, convém ressaltar que neste sistema de coordenadas a superfície daterra é definida através de uma elipsóide.

2.4.2 Cálculo de distâncias através do método de Haversine

Embora a norma WGS84 defina um sistema referencial baseado em um modeloelipsoidal da Terra, é possível adotar um cálculo simplificado (e possivelmente mais leveem termos computacionais) utilizando um modelo esférico terrestre. A adoção de ummodelo esférico permite a utilização da fórmula de Haversine no cálculo de distâncias entrepontos geográficos de maneira satisfatória para pequenas distâncias (SINNOTT, 1984). Adistância entre dois pontos localizados em uma esfera através deste método é descrita por:

d = 2Rsen−1

√sen2 ∆lat

2 + cos(lat1)cos(lat2)sen2 ∆lon

2 (2.4)


onde lat é a latitude de cada ponto, lon é a longitude, R é o raio médio da Terra,∆lat = lat1 − lat2 e ∆lon = lon1 − lon2. O raio médio da terra foi considerado sendo

R = 6372797m. (2.5)

21

3 Projeto de um Módulo de Controle de Mis-são Embarcado

3.1 ApresentaçãoEste trabalho propõe a concepção de um módulo de controle de missão de voo

embarcado em um veículo aéreo não tripulado. A missão de voo de um VANT deve sercompreendida como um conjunto de instruções que determinam o voo realizado peloveículo: decolagem, acessar certas localidades de interesse, retornar à estação base, entreoutras.

O módulo de controle de missão deve ser capaz de calcular sozinho estas missõesde maneira a satisfazer um ou mais objetivos principais. Por exemplo, suponha-se queum agricultor necessite fotografar diferentes partes de sua lavoura utilizando um veículoaéreo: a visita de todas estas localidades corresponderia ao objetivo principal. A partirdesta missão global, o módulo de controle de missão definiria a missão de voo do VANTcomposta por diferentes etapas: decolagem, voo pelas localidades de interesse de maneiraa minimizar a distância percorrida, pouso, etc..

A concepção deste módulo de controle de missão consiste em diversas etapas quesão enunciadas a seguir e desenvolvidas ao longo do trabalho:

1. Elaboração de modelos descrevendo o veículo aéreo não tripulado e o módulo decontrole de missão.

2. Implementações de funções de comunicação entre o módulo de controle e o VANT.

3. Elaboração de estudos de caso de e implementação de algoritmos de cálculo detrajetória adequados.

4. Simulação de estudo de caso a fim de testar a solução desenvolvida.

5. Avaliação dos resultados obtidos.

É também necessário destacar algumas definições e suposições deste trabalho:

• Define-se ponto de interesse como uma localidade útil ou interessante de acordo comuma missão global. Como exemplo, suponha-se uma aplicação de rastreamento napecuária: estes pontos de interesse seriam localizações de possíveis cabeças de gado.

• Os VANTs são dotados de sistemas capazes de identificar e até mesmo classificar ospontos de interesse, sendo que não faz parte do interesse deste trabalho como esta

Capítulo 3. Projeto de um Módulo de Controle de Missão Embarcado 22

identificação ou classificação é realizada. A capacidade de detecção e identificaçãodos pontos de interesse é fruto da previsão de um módulo de visão embarcado.

• Presume-se que a comunicação entre o controle de missão e os VANTs é perfeita: umamensagem enviada pelo controle de missão sempre atingirá o VANT de destino. Estasuposição não corresponde claramente a uma situação real, mas este assunto deveráser abordado em trabalhos futuros que deverão discutir as melhores estratégias decomunicação entre VANTs e Controle de Missão.

• Presume-se que o receptor GPS esteja sempre ao alcance de uma quantidade sufici-entes de satélites de maneira que sua posição geográfica seja sempre conhecida.

Tendo estabelecido o que é o módulo de controle de missão, apresenta-se a seguir acategoria de veículos aéreos não tripulados de interesse neste trabalho.

3.1.1 Especificação da Aeronave

Este projeto baseia-se na utilização aeronaves de asas fixas ou asas rotativasde pequeno porte desempenhando o papel de veículo aéreo não tripulado. A primeiracategoria é especialmente adequada a missões de varredura, devido a sua maior autonomiae velocidade. Já a segunda categoria possui características de voo diferenciadas, como porexemplo a capacidade de pouso e decolagem verticais e a habilidade de flutuação no ar.Isto as torna mais adequadas para realizar tarefas de inspeção, onde a aproximação deum ponto de interesse pode ser necessária. O veículo sobre o qual baseia-se o modelo ésemelhante ao exposto na Figura 5


Figura 5 – Um VANT com quatro rotores.

Fonte: mikrokopter.de

O veículo em questão é formado por diversos sistemas, entre os quais estão osistema de controle de voo, responsável pela estabilização da aeronave no ar; e o sistemade navegação, capaz de percorrer rotas pré programadas utilizando o Sistema de Posi-cionamento Global (GPS). Também dispõe dos sistemas de rádio, controle de motores,entre outros. Estes sistemas são compostos por sensores, processadores e eventualmenteatuadores próprios, o que resulta em um sistema de certa complexidade. A obtenção deum bom modelo torna-se crucial para facilitar a compreensão de seu funcionamento epermitir o estudo de como a funcionalidade de controle de missão pode ser adicionado aesta plataforma.

Os modelos de veículos aéreos analisados neste trabalho são baseados na plataformaArducopter (SITIO ARDUCOPTER, 2014), e utilizam o protocolo de comunicação Mavlink(2014). Este protocolo é descrito com mais detalhes na seção 3.3.1.

3.2 Modelagem do Sistema em SysMLA primeira etapa deste projeto consiste na elaboração do modelo do controle de

missão (e de outros sistemas relacionados, quando necessário) em linguagem SysML, capazde descrever os componentes e funcionalidades do sistema sob diferentes perspectivas.


3.2.1 Caso de Uso do Controle de Missão

O diagrama de caso de uso básico do sistema de controle de missão proposto éapresentado na Figura 6.

Neste diagrama, um administrador de missão interage com o caso Define Missionespecificando a missão que deve ser realizada pelo VANT: busca de cabeças de gado, porexemplo.

O caso de uso Read Input Data representa a leitura e interpretação de dadosprovenientes de atores externos ao controle de missão: o Sistema de Visão (Vision System)e o VANT (UAV ), sendo que estes estão associados aos atores Alvo (Target) e Ambiente(Environment).

A tarefa a ser realizada é decidida pelo bloco Decide Current Task. Esta funcio-nalidade depende da definição da missão e das informações disponíveis pelo controle demissão, e representa a capacidade do controle de missão de decidir de maneira autônomaa tarefa a ser executada. Como exemplo, pode-se imaginar que ao detectar um alvo, ocontrole de missão decida abandonar sua rota e perseguir o alvo.

A funcionalidade denominada por Execute Specified Task tem como objetivo exe-cutar a tarefa escolhida, através de sua relação com o Sistema de Visão ou o VANT.Continuando o exemplo do parágrafo anterior, esta funcionalidade corresponde a execuçãodos algoritmos de perseguição ao alvo pela aeronave.

Figura 6 – Diagrama de caso de uso simplificado do módulo de controle da missão.

É possível elaborar um segundo diagrama de caso de uso explicitando as tarefasespecíficas citadas no diagrama anterior, constituindo assim diferentes casos de uso. Estediagrama é apresentado na Figura 7 (as relações entre alguns casos de uso e os atoresexternos foram omitidas para facilitar a visualização).


O primeiro caso de uso é chamado Preflight, que representa o caso de funcionamentoanterior ao voo do veículo. Esta funcionalidade tem como objetivo realizar as configuraçõesiniciais da plataforma e verificar o bom funcionamento do veículo. O caso Takeoff representaa função decolagem no controle de missão. Em seguida, é apresentado a situação de voo doVANT, através do caso de uso Follow Path. Esta funcionalidade traduz o funcionamentodo VANT quando este voa ao longo de uma rota, ou seja, quando este está executandouma missão de voo. Este caso de uso inclui o cálculo de trajetórias (Calculate Waypoints),que corresponde ao caso de uso onde o controle de missão calcula a trajetória a ser enviadaa um ou mais VANTs participantes da missão global. Finalmente, o caso de uso EndMission representa o funcionamento do VANT em modo de finalização da sua missão,onde comandos de retorno à base ou pouso podem ser adotados.

Figura 7 – Diagrama de caso de uso do controle de missão com modos de vôo.

3.2.2 Modelos do VANT

O primeiro diagrama apresentado corresponde ao modelo das partes físicas re-lacionadas ao VANT. O objetivo deste diagrama é proporcionar uma visão geral doscomponentes da aeronave e a suas relações.


Figura 8 – Diagrama estrutural do veículo aéreo não tripulado.

O diagrama é apresentado na Figura 8. A descrição dos blocos é apresentada aseguir:

• UAV : este bloco representa o veículo aéreo não tripulado (Unmanned Aerial Vehicle).

• Frame: corresponde à estrutura mecânica que suporta todos os componentes presentesno veículo. A relação de composição indica que este elemento é indispensável aoveículo aéreo estudado.

• Motors: os motores são indispensáveis para o voo do veículo, o que implica em umarelação de composição. O diagrama também indica que um único VANT pode possuirvários motores.

• Motor Control: os controladores dos motores são indispensáveis para o funcionamentodo veículo, portanto uma relação de composição é estabelecida. Como cada motordeve ser controlado diretamente por ao menos um controlador, uma relação deassociação entre estes blocos é necessária.


• Autopilot: o piloto automático é a unidade capaz de realizar de maneira autônomao voo e a navegação da aeronave através da leitura dos sensores disponíveis (ace-lerômetros, giroscópio, GPS, etc.) e controle dos atuadores (motores, lemes, ailerons,etc.).

• Radio Tx, Radio Rx : veículos aéreos não tripulados contém geralmente uma unidadereceptora de rádio (Rx) associada a uma unidade transmissora (TX) situada emterra. Todavia esta unidade não é indispensável, pois os VANTs são capazes derealizar voo autônomo sem necessidade de receber comandos da base. Uma relaçãode agregação é então utilizada.

• Mission e Vision Module: este módulo corresponde a uma nova unidade de hardwareonde serão implementadas funções relativas ao controle de missão e processamentode imagens do veículo. Nota-se que esta unidade é composta por uma unidade deprocessamento e uma câmera. Este bloco não é indispensável à existência do veículo,por consequência nota-se a relação de agregação.

A partir deste diagrama torna-se possível visualizar-se todas as partes que compõemum veículo aéreo não tripulado.

Os blocos representados neste diagrama correspondem a funcionalidades existentesem um veículo aéreo não tripulado. Neste nível de abstração o interesse é demonstrar comocada funcionalidade se relaciona ao VANT e não como ou onde ela é implementada.

Figura 9 – Diagrama estrutural do veículo aéreo não tripulado.

A funcionalidade representada pelo bloco Flight Control representa o Controle deVoo do VANT. Esta funcionalidade é responsável pela estabilização do veículo aéreo no ar,realizada através de diversos controladores embarcados. Esta é a unidade responsável pelaleitura dos sensores inerciais, como acelerômetros e giroscópios, assim como a interfacecom os controladores dos motores. Nota-se que este bloco foi relacionado ao bloco UAVatravés de uma relação de composição. Isto se deve sobretudo ao fato dos VANTs de asas


rotativas, como quadricópteros, necessitarem controladores para sua estabilização no ar,sendo que raramente uma destas aeronaves é utilizada sem eles.

O Controle de Navegação (Nav Control) permite ao VANT de estimar sua posiçãoatravés de diferentes sistemas (sensores inerciais, sensores de pressão, magnetômetros,receptor GPS), assim como coordenar o voo do VANT ao longo de rotas previamentecalculadas. Estas rotas são definidas através de uma lista ordenada de localidades a seremvisitadas (waypoints).

O sistema de visão (Vision System), a ser ainda implementado em trabalhos futuros,corresponde ao sistema de captura e processamento de imagens embarcado, que permitemao VANT identificar e classificar pontos de interesse.

Finalmente, o módulo destacado (Mission Control) representa o objeto de estudodeste trabalho, que resultará em uma nova funcionalidade capaz de interpretar as informa-ções disponíveis nos outros módulos a fim de elaborar uma missão de voo a ser executadapelo Controle de Navegação do VANT.

3.2.3 Diagrama de definição dos Blocos do Controle de Missão

Tendo em vista ao caso de uso do controle de missão apresentado anteriormente eo modelo do veículo aéreo não tripulado e seus componentes, é possível estabelecer umdiagrama de definição de blocos demonstrando a composição módulo de controle de missão.Este diagrama deve ser interpretado como o conjunto das funções que integram o módulo,e é apresentado na Figura 10.

O bloco Mission Control pode ser expandido em três outros blocos: UAV Commu-nication, Path Planning, e Vision System Interface.

O primeiro bloco representa um conjunto de funções que realizam a comunicaçãoentre o Controle de Missão e um ou mais VANTs. Ele é composto por funções de comuni-cação de finalidades diversas cujo uso dependerá da aplicação, com exceção da mensagemSend Heartbeat que será sempre utilizada para que o controle de missão seja identificadopelo VANT de interesse.


Figura 10 – Diagrama de definição dos blocos do Controle de Missão.

Logo abaixo, o bloco Path Planning representa o conjunto de funções utilizadasno cálculo autônomo de trajetórias. Os principais elementos deste bloco correspondemàs funções necessárias na resolução de problemas de otimização, além de funções deplanejamento de decolagem e conversão de pontos de interesse em waypoints.

O bloco Vision System Interface representa as funções previstas para a interfacecom o sistema de visão que deverão ser implementadas em outros trabalhos.

As funções de comunicação e cálculo de trajetórias previstas neste diagrama serãotratadas nas seções 3.3 e 3.5 a seguir.

3.3 Plataforma EmbarcadaEste trabalho propõe a utilização de um Raspberry Pi como módulo de controle de

missão e visão, conforme apresentado na Figura 8. O Raspberry Pi é um computador de


tamanho reduzido com um processador ARM11 com uma frequência de clock de 700MHz e512MB de memória RAM. Além de ser um produto de baixo custo e facilmente encontradocomercialmente, sua utilização traz outras vantagens:

• sistema operacional baseado na distribuição Debian do Linux, agilizando a imple-mentação de código através das bibliotecas disponíveis para esta plataforma;

• possibilidade de realizar processamento de imagens na CPU ou GPU (processamentográfico);

• tamanho e peso reduzidos (85,6 x 56 mm, 45g), facilitando sua fixação a um VANT;

Figura 11 – Raspberry Pi Model A.

Fonte: Wikimedia Commons

Para permitir que esta plataforma fosse utilizada em conjunto com os veículosaéreos no desenvolvimento do controle de missão, foi necessário implementar o protocolode comunicação utilizado pelos VANTs incluindo as funcionalidades descritas na Figura 10.O detalhamento desta tarefa encontra-se no item 3.3.1. Em seguida, propõe-se a utilizaçãode um simulador de voo para validar a capacidade deste módulo comandar um VANT etestar os algoritmos de controle de missão (seção 3.4).

3.3.1 Comunicação entre Controle de Missão e VANT

O protocolo de comunicação utilizado na plataforma ArduCopter baseia-se noprotocolo Mavlink (2014), uma solução utilizada em diversas plataformas de pequenas


aeronaves não tripuladas. Este solução baseia-se em uma biblioteca de mensagens quepode ser utilizada na comunicação entre aeronaves e estações base, implementadas emlinguagem C e Python. Todavia, a maioria das ferramentas já disponíveis utilizadas nocontrole de VANTs por meio do protocolo Mavlink são programadas em linguagem demais alto nível programadas em Python (Pymavlink, Mavproxy), que se situam em uma"camada" acima da biblioteca Mavlink.

Devido a possibilidade dos métodos matemáticos utilizados serem pesados computa-cionalmente, optou-se a linguagem de baixo nível C ao invés de Python na implementaçãodo sistema de controle de missão. Isto implica na utilização da biblioteca programada emlinguagem C na plataforma utilizada (Raspberry Pi).

A biblioteca Mavlink é composta por diversas mensagens padrões cuja utilizaçaodepende do modelo de VANT. Nesta proposta estuda-se o uso da plataforma ArduCopter,sendo que é necessário identificar as mensagens necessárias a este modelo a fim de comandaro seu voo. Um exemplo da utilização de algumas destas mensagens é apresentada na seção3.3.2.

3.3.2 Troca de mensagens entre o módulo de Controle de Missão e o VANT

O objetivo deste diagrama de sequência é demonstrar a troca básica de mensagensentre o Controle de Missão e o VANT com o objetivo de enviar uma missão a um VANT eordenar execução. As finalidades de cada mensagem presente na Figura 12 são descritas aseguir:

• as mensagens 1 e 2 são os Heartbeats, usados para que um dos atores (VANT, Controlede Missao) seja capaz de perceber a existência do outro e o identificar,

• a mensagem 3 é a requisição dos dados dos diferentes sistemas do VANT para oControle de Missão,

• a sequência das mensagens 4 a 7 representam o envio de uma trajetória do Controlede Missão ao VANT,

• as mensagens 8 a 11 representam as mensagens necessárias para o início do voo doVANT. Na sequência, o acelerador é armado (8), o controle do rádio é tomado peloControle de Missão (10) e o modo automático é ativado (11).


Figura 12 – Diagrama de sequência.

Ao final desta troca de mensagens, o VANT terá seus motores armados, seu pilotoautomático estará ativado, e então ele percorrerá a trajetória enviada pelo controle demissão.

3.4 Simulador de VooA utilização de um simulador de vôo é motivada por dois fatores principais: validar

a capacidade do módulo de controle de missão de comunicar-se efetivamente com o VANTe atribuir-lhe missões, assim como testar os algoritmos elaborados para o controle demissão.

O simulador de voo é capaz de executar o software de controle de voo e navegaçãoda plataforma Arducopter, o que significa que o funcionamento interno do veículo obtidoem simulação deve ser próximo ao real. Outra Vantagem se deve ao fato de que a trocade mensagens entre o controle de missão e o simulador permanecerá a mesma quando ocontrole de missão for utilizado em um VANT Arducopter.

O diagrama de blocos do simulador é representado na Figura 13. O bloco vermelhorepresenta o arquivo executável que emula o funcionamento do ArduCopter. Este executávelestá associado a um simulador do ambiente, que interpreta os dados dos atuadores do


VANT e fornece as medidas dos sensores embarcados e do GPS da aeronave.

Os blocos verdes correspondem a ferramentas de controle de missão que podem seracopladas a simulação através de conexões TCP/IP e troca de mensagens Mavlink. Estasferramentas usualmente são programas baseados em uma estação base em terra onde serealiza o planejamento manual de rotas para os VANTs. Neste trabalho, esta ferramentaserá substituída pelo módulo de controle de missão.

No caso da simulação, a comunicação entre o controle de missão e a aeronave érealizada através de uma conexão TCP/IP utilizando mensagens do padrão Mavlink. Aoembarcar o módulo em um VANT real ArduCoper, será suficiente substituir esta conexãoTCP/IP por uma conexão serial mantendo-se o padrão de mensagens e todo o softwaredesenvolvido anteriormente.

Figura 13 – Diagrama de blocos do simulador de voo utilizado.

Fonte: https://code.google.com/p/ardupilot-mega/wiki/SITL

3.5 Estudos de caso do controle de missão embarcado.Nesta seção propõe-se duas missões de diferentes naturezas a fim de se demonstrar

o uso do módulo de controle de missão.


O primeiro caso demonstra como um VANT pode utilizar o sistema de controle demissão para inspecionar pontos de interesse levantados por um outro VANT através damenor trajetória possível (trajetória ótima).

A segunda missão possui complexidade mais elevada: neste caso, existem doisVANTs de inspeção especializados cada um em uma certa categoria de pontos de interesse.Ao início desta missão, estes VANTs permanecem na estação base e aguardam ordens doVANT mestre. Este VANT mestre, dotado do módulo de controle de missão, deve identificaros pontos de interesse e calcular as trajetórias ótimas dos VANTs inspetores, minimizandoa distância percorrida levando em conta a classificação dos pontos de interesse.

3.5.1 Pontos de interesse homogêneos.

O objetivo global da missão proposta é buscar e identificar alvos em uma dada regiãogeográfica, por meio de cooperação entre dois VANTs dotados de câmeras fotográficas ecapazes de realizar o processamento das imagens obtidas de modo a detectar possíveisalvos. Estes dois veículos possuem naturezas distintas e cumprem diferentes papéis nodesempenho da missão, ilustrada na Figura 14.

Figura 14 – Ilustração do estudo de caso 1. Os círculos vermelhos indicam pontos deinteresse detectados pelo primeiro VANT e que devem ser inspecionadosposteriormente.

Fonte: http://store.3drobotics.com/

O primeiro veículo aéreo realiza uma varredura de uma certa região e buscaidentificar possíveis pontos de interesse (POI). Neste caso, o VANT deve poder cobrirgrandes distâncias no menor tempo possível, características típicas dos veículos de asafixa (aviões). Através da obtenção de imagens e seu processamento, busca-se identificarpossíveis pontos de interesse localizados em terra. Caso um possível ponto de interesseseja identificado, este VANT guarda sua posição e prossegue seu voo, acumulando assimuma lista de pontos de interesse.


O segundo veículo aéreo tem como objetivo inspecionar estes pontos de interesselevantados pelo primeiro VANT. A tarefa de inspeção implica em aproximar-se do pontode interesse e realizar alguma tarefa de modo a adquirir informações mais detalhadas noponto de interesse (fotografá-lo de uma menor distância, sob diferentes ângulos, etc.). UmVANT de maior mobilidade (asas rotativas, por exemplo) pode ser útil neste papel devidoa sua maior mobilidade.

Figura 15 – Trajetórias dos VANTs em uma missão de varredura e inspeção.

A varredura realizada pelo primeiro VANT pode ser desempenhada através doplanejamento prévio de uma trajetória capaz de cobrir idealmente toda a área de interesse.Esta trajetória assemelha-se a um "zigue-zague", conforme visualizado na Figura 15. Aespecificação desta trajetória depende das características do sensor embarcado (neste caso,uma câmera), da altitude de voo da aeronave e sua autonomia.

A segunda aeronave deverá percorrer os pontos de interesse através de uma trajetóriaótima segundo alguns critérios pré estabelecidos (distância, prioridade dos POI, etc.).Neste estudo de caso, busca-se calcular a trajetória de menor distância capaz de atendera todos os pontos de interesse informados, o que corresponde ao conhecido problema do"vendedor viajante"(travelling salesman). Alguns métodos de solucionar este problemasão explicados em 2.3.1.1. As seções que seguem explicam como o módulo de controle demissão calculará a rota a ser seguida.

3.5.1.1 Cálculo da trajetória de inspeção de POI.

O algoritmo Simulated Annealing foi adotado na otimização da trajetória de visitados pontos de interesse. Esta escolha se deve ao fato de já haver significativa literaturacientífica relativa ao problema do vendedor viajante, assim como pela disponibilidadede uma ferramenta de SA através da biblioteca de cálculo científico em linguagem C(GNU Scientific Library, GSL) capaz de ser compilada e executada no hardware disponível(Raspberry Pi).


As funções responsáveis por gerar novas soluções e calcular a energia de uma soluçãoforam implementadas conforme descrito em 2.3.1, de maneira que uma nova solução éobtida trocando-se dois elementos de uma solução anterior e a energia interna equivale àdistância total percorrida segundo uma dada solução. Estas funções baseiam-se no artigode Kirkpatrick, Gelatt e Vecchi (1983) e no exemplo disponível em na biblioteca de cálculocientífico GNU GSL (GSL. . . , 2014).

3.5.2 Missão com pontos de interesse heterogêneos.

Neste estudo de caso, os pontos de interesse estão divididos em duas categoriasdiferentes, poi1 e poi2. Embora não faça parte do objetivo deste trabalho classificar ospontos de interesse, é possível imaginar a situações onde esta classificação é interessante:

• a classificação de rebanhos conforme espécie ou tamanho no caso de uma aplicaçãode monitoramento na pecuária;

• patologias de diferentes características em construções civis;

Devido às divergências das características dos pontos de interesse de uma certasituação, é possível imaginar que estes podem ser melhor inspecionados se houver umacerta variedade de recursos de análise disponíveis, e que este cada um destes recursos sejamais adequado a uma certa categoria de ponto de interesse. Em outras palavras, cadaponto de interesse de uma certa categoria será melhor analisado se a inspeção for realizadaexatamente pelo instrumento mais adequado àquela categoria.

Considerando esta aplicação onde cada VANT é dotado de um diferente instrumentoe cada ponto de interesse será visitado uma única vez, deseja-se idealmente que os pontosde interesse do tipo poi1 sejam visitados pelos VANTs de tipo V ANT1 e os pontos deinteresse de classificação poi2 visitados pelos VANTs de categoria V ANT2.

A Figura 16 demonstra esta situação onde dois VANTs visitam apenas os pontosde interesse mais adequados a suas especialidades. Neste exemplo, os pontos do gráficocorrespondem a pontos de interesse cujo classificação é demonstrada através de sua cor(azul ou vermelho). Cada um destes pontos de interesse são visitados por um entre doisVANTs especializados, onde trajetórias são representada por linhas de cores iguais às corespontos de interesse, indicando correspondência entre especialidade do VANT e tipo depontos de interesse. Neste caso, os pontos de interesse azuis são visitados exclusivamentepelo VANT de trajetória azul, enquanto os pontos de interesse vermelhos são visitadosexclusivamente pelo VANT de trajetória vermelha. O ponto preto indica a estação base,ou ponto de partida de ambos os VANTs.


Figura 16 – Exemplo de trajetórias 1 Figura 17 – Exemplo de trajetórias 2

Outra possibilidade seria a de permitir eventualmente que um VANT possa inspe-cionar pontos de interesse em discordância com a sua especialidade, reduzindo assim adistância total percorrida. Presume-se neste caso que, se o ponto de interesse for visitadopor um VANT de especialidade não correspondente, a interação entre eles é deteriorada,mas ainda assim contribui para o progresso da missão. Um exemplo correspondente aesta hipótese é apresentada na Figura 17. Nota-se que neste caso a trajetória azul visitaum ponto de interesse vermelho em adição a vários outros pontos azuis, e a trajetóriavermelha também visita um ponto azul além de vários outros vermelhos. Considerandoque as distância percorridas pelo VANTs são os perímetros dos polígonos definidos porestas trajetórias, nota-se que a distância percorrida total neste caso será menor do queapresentado na Figura 16.

Adotando a estratégia de permitir eventuais discordâncias entre especialidades dosVANTs e espécies de pontos de interesse, a seção seguinte propõe uma maneira de realizaro cálculo de trajetória buscando um compromisso entre a distância total percorrida e avisita dos pontos de interesse pelo melhor inspetor possível.

3.5.2.1 Cálculo das trajetórias de inspeção de POI por dois VANTs com especialidadesdiferentes.

Considerando a disponibilidade prévia do solver de Simulated Annealing, optou-sepor modificar o algortimo existente a fim de obter uma solução para o problema expostona seção anterior. Dentro desta proposta, o processo de otimização visa encontrar duastrajetórias X e Y capazes de visitar todos os pontos de interesse, percorrendo a menordistância total possível. A visita de um ponto de interesse por um VANT de especialidadecorrespondente é interpretada como uma restrição “flexível”, e sua violação resulta empenalidades na função custo.

Os pontos de interesse são denotados por pci , onde o índice c indica a classificação

do ponto de interesse e i indica a ordem da detecção pelo VANT mestre. Ao final davarredura, uma lista qualquer de pontos de interesse detectados é descrita por um vetor


semelhante apoi =

[p1

1 p12 p2

3 p14 p2

5 p26 ...

](3.1)

O primeiro passo é elaborar uma solução inicial composta por dois vetores X e Y ,que correspondem a ordem de visita dos pontos de interesse por cada um dos VANTs.Esta solução inicial é gerada dispondo os pontos de interesse de uma dada categoria natrajetória do VANT mais adequado. Supondo que o VANT que percorrerá a trajetória Xé especializado em pontos de interesse de categoria 1, e que o VANT de trajetória Y éespecializado em pontos de interesse de categoria 2, obtêm-se:

X =[x1 x2 x3 x4 ... xN1

]=

[p0 p1

1 p12 p1

4 ... p0

](3.2)

eY =

[y1 y2 y3 y4 ... yN2

]=

[p0 p2

3 p25 p2

6 ... p0

](3.3)

onde p0 é ponto de interesse zero, que indica a posição da estação base. Nota-se que esteponto corresponde ao primeiro e último elemento de cada trajetória, indicando que oVANT parte da estação base e retorna a ela no fim do voo.

A energia da configuração é dada por

E(X, Y,m1,m2) = (m1λ+ 1)N1−1∑i=1

dist(xi, xi+1) + (m2λ+ 1)N2−1∑i=1

dist(yi, yi+1) (3.4)

onde dist(p1, p2) é a função que calcula a distância entre dois pontos, λ é o coeficiente depenalidade e m1 e m2 são o número de pontos de interesse discordantes em cada trajetória.

O objetivo desta penalidade é direcionar o processo de otimização para regiõesonde a incidência de discordâncias seja mínima (ou aceitável), forçando a visita de cadaponto de interesse por um VANT de especialidade adequada. O valor do coeficiente depenalidade deverá ser ajustado conforme a aplicação: em situações onde a especialidadede cada VANT possui um papel fundamental o coeficiente de penalidade será elevado,fazendo a otimização convergir a um mínimo local onde as restrições sejam respeitadas; jáem situações onde os VANTs ou pontos de interesse sejam homogêneos este coeficiente serázero, permitindo assim ao programa de otimização de se aproximar de um mínimo global.

A geração de novas soluções na vizinhança atual pode ocorrer de quatro formasdiferentes, sendo que a cada iteração uma destas é escolhida aleatoriamente. A escolha dospontos a ser substituídos também é feita de maneira aleatória, mas de modo a sempremanter os pontos de interesse p0 nas extremidades indicando a partida e o retorno à base:

1. permutação de dois pontos quaisquer na trajetória do primeiro VANT (para que estaoperação possa ocorrer, é necessário que X contenha ao menos cinco elementos):

X =[x1 x2 x3 x4 ... xN1

]=⇒ X =

[x1 x3 x2 x4 ... xN1

]


2. permutação de dois pontos quaisquer na trajetória do segundo VANT (para que estaoperação possa ocorrer, é necessário que Y contenha ao menos cinco elementos):

Y =[y1 y2 y3 y4 ... yN2

]=⇒ Y =

[y1 y3 y2 y4 ... yN2

]3. colocação de um ponto da trajetória do VANT 1 na trajetória do VANT 2 (para que

esta operação possa ocorrer, é necessário que X contenha ao menos três elementos) :

X =[x1 x2 x3 x4 ... xN1

]=⇒ X =

[x1 x2 x4 ... xN1

]Y =

[y1 y2 y3 y4 ... yN2

]=⇒ Y =

[y1 y2 y3 x3 y4 ... yN2

]4. colocação de um ponto da trajetória do VANT 1 na trajetória do VANT 2 (para que

esta operação possa ocorrer, é necessário que Y contenha ao menos três elementos):

X =[x1 x2 x3 x4 ... xN1

]=⇒ X =

[x1 x2 x3 y2 x4 ... xN1

]Y =

[y1 y2 y3 y4 ... yN2

]=⇒ Y =

[y1 y3 y4 ... yN2

]

A cada iteração do processo de otimização, uma destas operações é selecionadaaleatoriamente gerando uma nova solução na vizinhança da solução anterior. Isto é feito demodo que a probabilidade de seleção de cada uma destas operações dependa da quantidadede pontos de interesse em cada trajetória: assim, uma trajetória que possua mais pontosde interesse do que a outra possuirá uma probabilidade maior de ser modificada a cadaiteração. Além disso, cada uma das operações anteriores só pode ser realizada se a soluçãoconter um número mínimo de pontos de interesse, o que implica em condições que devemser testadas a cada iteração.

A maneira que estas operações foram descritas permitem que em dado momento,uma das duas soluções não contenha nada além dos dois pontos p0 marcando o início e ofim da missão. Isto significa que, naquela solução, um dos VANTs não visitará nenhumponto de interesse.

O algoritmo proposto pode-ser resumido como a sequência à seguir:

1. Inicializa-se a variável Temperatura.

2. Gera-se uma solução inicial em que os POI são visitados pelos VANTs correspondentes.Adota-se esta solução como a solução atual. Calcula-se a Energia da solução atual.

3. Gera-se uma nova solução através de uma entre as 4 operações possíveis (escolhidaestocasticamente).

4. Obtém-se a Energia desta solução através do cálculo das distâncias das trajetórias eaplicação das penalidades.


5. Adota-se esta solução

• se a Energia da nova solução for menor que a Energia da Solução atual,

• ou se a Energia da nova solução for maior que a Energia da Solução atual, desdeque um número aleatório gerado no intervalo [0, 1] seja menor que P (∆E) =e

−∆EkbT .

6. Calcula-se o novo valor da variável Temperatura Tk+1 = Tk/MUT .

7. Retorna para o passo 3 a menos que a temperatura mínima seja atingida.

3.5.2.2 Implementação da Missão utilizando três aeronaves não tripuladas.

Define-se como missão global o conjunto das missões individuais de cada veículoaéreo. Neste estudo de caso, a missão global é identificar e inspecionar de maneira ótimapontos de interesse de duas categorias diferentes em posições desconhecidas em uma região.

As missões individuais correspondem às missões de cada um dos VANTs atuandonesta região: a missão de varredura e identificação de pontos de interesse pelo VANTmestre e as missões de inspeção dos VANTs inspetores.

A fim de simular esta missão global, o seguinte roteiro foi estipulado:

1. Uma localidade é definida como a estação base da simulação. Nesta base, os trêsVANTs aguardam, decolam para executar uma missão e retornam após concluí-la.

2. O administrador da missão define a rota de varredura no VANT Mestre, que é oVANT dotado do módulo de controle de missão responsável por identificar os pontosde interesse e comandar os VANTs inspetores.

3. Após a definição da rota de varredura, o controle de missão é acionado e inicia o voodo mestre, através do commando dos módulos de voo e navegação.

4. Durante o voo do mestre, pontos de interesse são gerados em intervalos de tempoaleatórios. A posição destes pontos de interesse é dada pela posição do VANT nomomento da geração, e sua classificação é definida aleatoriamente em duas categoriaspossíveis, poi1 e poi2, sendo que P (poi1) = P (poi2) = 0, 5.

5. Ao final da trajetória de varredura estipulada inicialmente, o VANT mestre calcula astrajetórias a serem percorridas pelos dois VANTs de inspeção que aguardam na base.Ao concluir o cálculo, o mestre envia as missões individuais aos VANTs inspetores ecommanda suas decolagens.

6. O VANT inspetor retorna a base enquanto os inspetores executam suas missões.


7. Ao término da missão de suas missões de inspeção, os VANTs retornam à estaçãobase.

A Figura 18 ilustra a configuração das aeronaves neste estudo de caso. O VANTmestre (asa fixa) realiza a varredura de uma certa região geográfica (demarcada peloquadrilátero). Os pontos de interesse detectados por este VANT são representados porcírculos preenchidos em azul ou amarelo, correspondentes as categorias dos POI. Nalateral esquerda são representados dois VANTs cujas cores coincidem com a dos pontos deinteresse, de maneira a indicar a especialidade da inspeção de cada um.

Figura 18 – Ilustração do segundo estudo de caso.

Fonte: http://store.3drobotics.com/

42

4 Resultados e Discussões

4.1 Comunicação entre Controle de Missão e SimuladorEsta seção demonstra a validação das propostas expressas em 3.3 e 3.4 relativas ao

módulo de controle de missão e simulador. Neste experimento, observou-se a capacidade docontrolador em comunicar-se com o VANT simulado através da troca de pacotes Mavlinkpor meio de uma conexão TCP/IP. Nesta simulação, o Controle de Missão envia umarota qualquer ao VANT e aplica os comandos necessários para sua decolagem (conforme afigura 12).

A Figura 19 demonstra o console de saída da rotina executada no Raspberry Pi. Oconsole indica o envio de três pontos definindo a rota waypoints 0, 1 e 2, a inicializaçãodos motores e a seleção do modo de vôo (Set Mode). As mensagens subsequentes indicamque o VANT atingiu o ponto 1.

Figura 19 – Console de execução do Controle de Missão no Raspberry Pi.

O resultado dos comandos enviados pode ser visualizado na Figura 20. Esta é umarepresentação geográfica do VANT e sua rota (indicada pelas linhas brancas). A linha corde rosa conecta o VANT ao próximo ponto de destino.

Capítulo 4. Resultados e Discussões 43

Figura 20 – Visualização gráfica do vôo do VANT.

O console do VANT é mostrado na Figura 21. Ele exibe os dados de seus diferentessistemas (velocidade, altitude, bateria, etc.) e as mensagens Mavlink mais relevantes.

Figura 21 – Console do simulador exibindo as informações do veículo aéreo.

Através da realização deste, a capacidade de comunicação entre o módulo decontrole de missão e VANT foi validada.


4.2 Teste do algoritmo Simulated Annealing embarcado no casode pontos de interesse homogêneos.Nesta seção são demonstrados os resultados obtidos durante a execução exclusiva

do algoritmo Simulated Annealing. Neste caso, a "Energia" de uma solução correspondea distância total de uma trajetória. A fim de testar o desempenho do algoritmo, foramgerados cinco problemas contendo 25 pontos de interesse aleatórios em uma região (AnexoA). A cada 10 resoluções de um problema o coeficienteMU_T foi incrementado, acelerandoa diminuição da variável de controle Temperatura (ver equação 4.1) consequentementediminuindo o número de iterações realizadas em cada resolução.

Tk+1 = Tk

MU_T (4.1)

A primeira resolução partiu de um coeficiente de resfriamento de 1, 001, sendo quea cada 10 resoluções este coeficiente era incrementado em 0, 0004. Para cada problema, 200coeficientes de resfriamento foram testados, obtendo-se 2000 soluções para cada problema.Os outros parâmetros foram mantidos conforme a Tabela 1.

Tabela 1 – Parâmetros utilizados na execução das otimizações por Simulated AnnealingModificado.

Parâmetro Valor DescriçãoN_TRIES 200 Número tentativas para gerar uma nova soluçãoITERS_FIXED_T 350 Número de iterações para cada TK 1 Constante de BoltzmannT_INITIAL 5000 Temperatura InicialT_MIN 0,5 Temperatura Final

Os valores finais da Energia obtidos foram normalizados de acordo com a melhorsolução obtida em cada problema, e calculou-se a média destes valores normalizados paracada coeficiente de resfriamento. Os dados obtidos são apresentados na Figura 22.

A escala representada no eixo vertical da direita corresponde às médias dos valoresfinais da Energia normalizados para cada problema em função do coeficiente de temperatura(eixo das abscissas). A curva rosa demonstra o tempo de execução médio do algoritmo deotimização também em função do coeficiente de temperatura.


Figura 22 – Resolução de cinco problemas através do método de Simulated Annealingoriginal.

1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08

1

2

3

4

5

6

7

8

9

10

Tem

po d

e R

esol

ução

(s)

Coeficiente de Resfriamento MUT

1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.081

1.02

1.04

1.06

1.08

1.1

1.12

1.14

1.16

1.18

1.2

Méd

ias

de E

(x)

norm

aliz

adas

Problema 1Problema 2Problema 3Problema 4Problema 5

Tempo

Nota-se que, para coeficientes de resfriamento menores que 1, 01, a maior parte dasmédias das soluções normalizadas encontra-se entre 1, 02 e 1, 07, ou seja, entre 2% e 7%acima do valor ótimo. Já para valores maiores do coeficiente de resfriamento, os valoresdas médias são superiores. Para um coeficiente de resfriamento de 1, 08, as médias estãolocalizadas em um intervalo entre 1, 08 e 1, 16, indicando uma faixa entre 8% e 16% acimada solução ótima.

Este comportamento é esperado: um resfriamento rápido faz que o algoritmo deotimização fique preso em mínimos locais: a variável Temperatura do algoritmo rapidamenteatingirá valores baixos, resultando que a probabilidade de escapar destes mínimos locais(ou seja, aceitar soluções "piores") seja reduzida. Logo, torna-se mais improvável que oalgoritmo atinja mínimos globais.

4.2.1 Teste no simulador

A otimização da trajetória foi efetuada no Raspberry Pi utilizando 20 pontosde interesse gerados de maneira aleatória, com os coeficientes dados pela Tabela 1 eMUt = 1.002. A Figura 23 demonstra uma rota gerada a partir da lista aleatória depontos de interesse. Neste caso, nenhuma otimização é realizada: a ordem de recebimento


dos pontos de interesse é a mesma ordem de visita. Pode-se concluir visualmente que atrajetória obtida é de baixa qualidade, conforme o esperado.

Figura 23 – Trajetória de visita a todos os POIs antes da otimização.

Em seguida, o processo de otimização é realizado no módulo de controle de missão.Os pontos de interesse são reordenados e uma nova trajetória é fornecida ao controle denavegação. O resultado pode ser visualizado na Figura 24. Neste caso, é possível constatarvisualmente que a trajetória é muito mais curta se comparada com a da Figura 23. Esteresultado valida a aplicação do algoritmo Simulated Annealing no módulo de controle demissão em conjunto com o simulador de voo.


Figura 24 – Trajetória otimizada de visita a todos os POIs.

4.3 Simulação com VANTs e Pontos de Interesse HeterogêneosEsta seção visa apresentar os resultados da implementação das propostas apresenta-

das na Seção 3.5.2. Inicialmente, resultados do algoritmo Simulated Annealing modificadosão apresentados e discutidos. Em seguida, a simulação de uma missão completa é demons-trada, onde um VANT Mestre varre uma região buscando pontos de interesse, que sãoposteriormente visitados por dois VANTs inspetores.

4.3.1 Simulated Annealing Modificado

Esta seção demonstra os testes do algoritmo Simulated Annealing Modificado, demaneira semelhante a seção 4.2. Todavia, nesta seção a Energia da solução não correspondenecessariamente a distância total das trajetórias, devido a inclusão das penalidades. Nestecaso a primeira resolução partiu de um coeficiente de resfriamento de 1, 004, sendo que acada 10 resoluções este coeficiente era incrementado em 0, 0002, diminuindo gradualmenteo tempo de resolução dos problemas. No final obtiveram-se 2000 soluções para cadaproblema, totalizando 10000 soluções. Os outros parâmetros foram mantidos conforme aTabela 1. O coeficiente de penalidade utilizado foi λ = 0, 15.

Os resultados (Energia Final de cada Solução) foram normalizados de acordo com amelhor solução obtida em cada problema, e calculou-se a média destes valores normalizadospara cada coeficiente de resfriamento. Os dados obtidos são apresentados na Figura 25


Figura 25 – Simulated Annealing modificado com coeficiente de penalidade λ = 0, 15.

1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08

1

2

3

4

5

6

7

8

9

10T

empo

de

Res

oluç

ão (

s)


1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.081

1.007

1.014

1.021

1.028

1.035

1.042

1.049

1.056

1.063

1.07

Méd

ias

de E

(x)

norm

aliz

adas


Tempo

Analisando-se a Figura 25, nota-se que a média das Energias finais normalizadascresce conforme o coeficiente de resfriamento aumenta. Todavia, se esta figura for comparadaà Figura 22, algumas diferenças podem ser observadas. As características de alguns pontosdestas curvas são demonstrados na Tabela 2.

Nota-se que o tempo de resolução é maior do que no caso anterior. No exemploanterior, o tempo de resolução para MU_T = 1.01 era de 2s. No caso do SimulatedAnnealing modificado, este tempo foi de 3s. Isto é explicado pelo fato de que as novasfunções de cálculo de energia e geração de nova solução são computacionalmente maiscomplexas do que no caso original. Conforme exposto na seção 3.5.2.1, a função de cálculode energia deve agora verificar a existência e pontos de interesse inadequados em cadatrajetória e aplicar a penalidade correspondente, enquanto que a geração de novas soluçõesdeve levar em conta as restrições de cada possível operação. Outro ponto interessante é

Tabela 2 – Comparação dos resultados demonstrados nas Figuras 22 e 25.

Problema MUT Qualidade da Solução Tempo de Execução

SA Original 1.01 Enorm(x) < 1.085 2, 0s1.08 Enorm(x) < 1.17 0, 2s

SA Modificado 1.01 Enorm(x) < 1.02 3, 0s1.08 Enorm(x) < 1.056 0, 4s


o fato de que as médias normalizadas desta solução estão mais próximas a 1 do que nocaso anterior. Se observamos a Tabela 2, considerando o coeficiente de resfriamento iguala 1.01, nota-se que Enorm(x) < 1.085 no algoritmo original enquanto Enorm(x) < 1.02no algoritmo modificado. Para um coeficiente de resfriamento igual a 1.08 o resultadoé análogo, Enorm(x) < 1.17 no caso original e Enorm(x) < 1.056 no novo algoritmo. Istomostra que as soluções encontradas pelo algoritmo modificado tendem a ser mais próximasa solução ótima de cada problema.

Para se entender este comportamento, deve-se relembrar a consequência da inserçãodo fator de penalidade no cálculo das distâncias. Com este fator, regiões com soluções emque hajam várias discordâncias entre POI e especialidades dos VANT resultarão em valoresda função Energia mais elevados. O processo de busca da solução tenderá a se concentrarnas regiões de baixas penalidades, onde o mínimo provavelmente estará localizado.

Para confirmar esta hipótese o experimento foi realizado novamente, utilizando omesmo algoritmo mas desta vez adotando um coeficiente de penalidade λ = 0. Espera-seque os dados obtidos sejam semelhantes aos representados na Figura 22, pois neste caso aotimização não estará mais restrita a uma única região. Logo, a qualidade da solução comtaxas de resfriamento rápidas deverá ser pior do que no caso com penalidades.

De fato, ao analisar os dados obtidos nesta nova simulação apresentados na Figura26, observa-se que, para coeficientes de resfriamento inferiores a 1, 01, as médias da energianormalizada da soluçao encontram-se entre 1, 02 e 1, 08. Para coeficientes de resfriamentopróximos a 1, 08, as médias das energias normalizadas encontram-se entre 1, 08 e 1, 16,resultado semelhante ao obtido na seção 4.2. Este resultado confirma a hipótese levantadaanteriormente.


Figura 26 – Simulated Annealing modificado com coeficiente de penalidade λ = 0.

1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08

1

2

3

4

5

6

7

8

9

10T

empo

de

Res

oluç

ão (

s)


1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.081

1.02

1.04

1.06

1.08

1.1

1.12

1.14

1.16

1.18

1.2

Méd

ias

de E

(x)

norm

aliz

adas


Tempo

A Tabela 3 mostra o valor da Função Energia final nos três experimentos. Nota-seque tanto o algoritmo original quanto o modificado (com coeficiente de penalidade iguala zero) atingiram o mesmo valor mínimo nos cinco problemas. Nestes casos, a energiafinal corresponde a distância total da(s) trajetória(s). Já o algoritmo modificado compenalidades apresenta energia final superior se comparada aos outros experimentos, pois ofator de penalidade restringe a região de busca a uma vizinhança e obtém uma soluçãoótima que é na verdade um mínimo local. Além disso, o valor da Função Energia nestecaso inclui o valor das possíveis penalidades.

Estes resultados demonstram que a modificação realizada no algoritmo atingiu oobjetivo de direcionar a otimização para regiões onde a ocorrência de discordâncias entreclasse dos pontos de interesse e especialidades dos VANTs seja pequena.

Tabela 3 – Energia das Soluções Ótimas nos três experimentos.

Algoritmo Penalidade E1(x) E2(x) E3(x) E4(x) E5(x)SA - 3447, 8 3535, 8 3575, 8 3351, 5 3240, 8SA mod 0 3447, 8 3535, 8 3575, 8 3351, 5 3240, 8SA mod 0,15 5153, 8 5345, 6 5665, 2 5350, 3 4754, 5


Estes resultados demonstram o funcionamento das diferentes implementações daotimização utilizando Simulated Annealing, e as curvas obtidas podem auxiliar na definiçãodo fator de resfriamento a ser utilizado de acordo com qualidade da solução necessária.Além disso, estes resultados deixam evidente que a elevação dos coeficientes de penalidadetornam a resolução do problema mais rápida ao restringir a região de atuação do algoritmode otimização.

4.3.2 Execução de uma Missão de Varredura e Inspeção com Três VANTs

Esta seção demonstra uma simulação realizada conforme descrito em 3.5.2.2. Osparâmetros de otimização por Simulated Annealing são apresentados na Tabela 4

Tabela 4 – Parâmetros utilizados na execução da otimização por Simulated AnnealingModificado.

Parâmetro Valor DescriçãoMU_T 1.0015 Fator de diminuição da temperaturaLambda 0,15 Coeficiente de Penalidade

Uma rota é planejada inicialmente de modo a cobrir uma região de interesse,conforme demonstrado na Figura 27. A trajetória desejada (linha vermelha) é definidaatravés de um certo número de waypoints, correspondentes a pontos que devem seralcançados pelo VANT na ordem exposta pela numeração na Figura.

Figura 27 – Trajetória planejada previamente para realização de varredura pelo VANTMestre.

A Figura 28 demonstra o voo do VANT Mestre e os pontos de interesse detectadosdurante o voo. A classe de cada ponto é ilustrada através da cor do ícone correspondente,


sendo este azul ou amarelo. A trilha verde representa o trajeto percorrido pelo VANTMestre.

Figura 28 – Voo do VANT 1 e detecção dos pontos de interesse.

Ao término da varredura, o VANT Mestre calcula as rotas dos VANTs inspetores1 e 2, conforme observado na Figura 29. As trajetórias são marcadas evidenciando aespecialidade de cada VANT, de modo que a trajetória azul indica um inspetor especializadonos pontos de interesses marcados em azul, e a trajetória amarela indica um VANT inspetorespecializado nos pontos de interesse marcados em amarelo.

Nota-se que a trajetória azul visita 8 pontos de interesse no total, sendo 6 azuis e 2amarelos, ao passo que a rota amarela visita 11 pontos de interesse, sendo 8 amarelos e 3azuis. Este resultado demonstra a tendência do processo de otimização de corresponder ascategorias de pontos de interesse às especialidades dos VANTs.


Figura 29 – Rotas calculadas para os VANTs inspetores.

Figura 30 – Voo dos VANTs inspetores.

A Figura 30 ilustra a etapa final da simulação. No momento em que a imagem foicapturada, os VANTs Inspetores já receberam as missões do VANT Mestre, assim comoas instruções para decolagem e início da missão. Em seguida, os VANTs voam visitando ospontos de interesse de acordo com a trajetória calculada e retornam a base. A execuçãocompleta da missão leva aproximadamente 22 minutos.

54

5 Conclusão

Este trabalho apresentou a concepção de um módulo de Controle de Missão embar-cado, capaz de atribuir, de maneira autônoma, missões a veículos aéreos não tripulados. Omódulo desenvolvido foi testado com sucesso em simulações, atingindo o objetivo proposto.

O desenvolvimento da plataforma embarcada consistiu inicialmente na modelagemdo VANT e do Controle de Missão. Os modelos obtidos foram utilizados como base naconcepção da plataforma, guiando a produção de código durante o desenvolvimento doprojeto. A etapa seguinte consistiu na implementação, no Raspberry Pi, das funçõesnecessárias à comunicação entre o Controle de Missão e VANTs. Esta etapa foi testada evalidada, e o trabalho foi concentrado no estudo e implementação dos algoritmos cálculo detrajetória através de otimização por Simulated Annealing. Ao final destas etapas, o sistemadesenvolvido foi testado com o uso simuladores de voo. Os testes demonstraram que, apósuma missão inicial de varredura ter sido planejada, o módulo de Controle de Missão foicapaz de comandar a decolagem e o voo do primeiro VANT, calcular as trajetórias dosVANTs inspetores e comandar o início de suas missões.

Futuramente, a atuação conjunta do Controle de Missão e o sistema de visãopermitirá aos VANTS realizar missões "reais" em campo, identificando alvos através doprocessamento de imagens e definindo trajetórias para outros VANTs inspetores. Aplicaçõespoderão ser desenvolvidas, testando este sistema em situações de rastreamento de gado,inspeção de lavouras, entre outras possibilidades. O código desenvolvido para o controledos Vants da plataforma ArduPilot poderá também ser reutilizado em outros projetos,facilitando o uso dos VANTs por outros pesquisadores.

É importante também notar que alguns pontos do projeto necessitam ser futura-mente desenvolvidos. A modelagem dos sistemas VANT e Controle de missão foi útil paraguiar o desenvolvimento do projeto, porém é pertinente observar que os modelos geradosainda são superficiais. Os modelos atuais não descrevem o funcionamento completo dossistemas envolvidos, de modo que eventualmente estes modelos precisem ser aprofundados.O desenvolvimento da plataforma embarcada foi feito visando a compatibilidade entre ofirmware dos VANTs baseados na plataforma ArduPilot e o Controle de Missão, permi-tindo a utilização de VANTs em estudos de campo no futuro. Devido ao uso exclusivode simuladores neste projeto, toda a comunicação entre Controle de Missão e veículosaéreos foi realizada através de uma conexão de rede por cabos, utilizando o protocoloTCP/IP. Esta solução não é compatível com uma situação de voo real, o que significaque a utilização plena deste módulo está condicionada a implementação de uma soluçãode comunicação sem fio. Os algoritmos de cálculo de trajetória foram implementados e

Capítulo 5. Conclusão 55

testados atendendo aos objetivos de cada estudo de caso. Outros trabalhos futuros poderãoser realizados sobre esta funcionalidade, como a implementação de outros métodos deotimização e a posterior comparação entre seus desempenhos.

Finalmente, este trabalho pode representar um primeiro passo em direção a estabe-lecer certa autonomia em VANTs comerciais de baixo custo, abrindo caminho para que asfuncionalidades do Módulo sejam expandidas e testadas em situações reais.

56

Referências

ARDUCOPTER Website. 2014. Disponível em: <http://copter.ardupilot.com/>. Acessoem: 24 abr. 2011. Citado na página 23.

AUSTIN, R. Unmanned aircraft systems: UAVS design, development and deployment.[S.l.]: John Wiley & Sons, 2011. Citado na página 12.

BEYDEDA, S. et al. Model-driven software development. [S.l.]: Springer, 2005. Citado napágina 14.

CORMEN, T. H. et al. Introduction to algorithms. [S.l.]: MIT press Cambridge, 2001.Citado na página 16.

DEPARTAMENTO DE DEFESA DOS ESTADOS UNIDOS. World Geodetic System1984. EUA, 2000. Citado na página 19.

DORIGO, M.; BIRATTARI, M. Ant colony optimization. In: Encyclopedia of MachineLearning. [S.l.]: Springer, 2010. p. 36–39. Citado na página 17.

FRIEDENTHAL, S.; MOORE, A.; STEINER, R. OMG Systems ModelingLanguage Tutorial. [S.l.], 2009. Disponível em: <http://www.omgsysml.org/INCOSE-OMGSysML-Tutorial-Final-090901.pdf>. Acesso em: 26 mar. 2014. Citado napágina 14.

GSL TSP Example. 2014. Disponível em: <http://www.gnu.org/software/gsl/manual/html_node/Traveling-Salesman-Problem.html>. Acesso em: 15 maio 2011. Citado napágina 36.

JENKINS, B. V. D. The Economic Impact of Unmanned Aircraft Systems Integrationin the United States. [S.l.], 2014. Disponível em: <http://www.auvsi.org/resources/economicreport>. Acesso em: 24 abr. 2011. Citado na página 11.

KIRKPATRICK, S.; GELATT, C. D.; VECCHI, M. P. Optimization by simulatedannealing. Science, American Association for the Advancement of Science, v. 220, n. 4598,p. 671–680, 1983. ISSN 00368075. Disponível em: <http://www.jstor.org/stable/1690046>.Citado 3 vezes nas páginas 17, 19 e 36.

MAVLINK. 2014. Disponível em: <http://qgroundcontrol.org/mavlink/>. Acesso em: 24abr. 2011. Citado 2 vezes nas páginas 23 e 30.

SINNOTT, R. W. Virtues of the Haversine. skytel, v. 68, p. 158, dez. 1984. Citado napágina 19.

VOSS, S. Meta-heuristics: The state of the art. In: Local Search for Planning andScheduling. [S.l.]: Springer, 2001. p. 1–23. Citado na página 17.

http://copter.ardupilot.com/

http://www.omgsysml.org/INCOSE-OMGSysML-Tutorial-Final-090901.pdf

http://www.omgsysml.org/INCOSE-OMGSysML-Tutorial-Final-090901.pdf

http://www.gnu.org/software/gsl/manual/html_node/Traveling-Salesman-Problem.html

http://www.gnu.org/software/gsl/manual/html_node/Traveling-Salesman-Problem.html

http://www.auvsi.org/resources/economicreport

http://www.auvsi.org/resources/economicreport

http://www.jstor.org/stable/1690046

http://qgroundcontrol.org/mavlink/

Anexos

58

ANEXO A – Localização da região degeração de pontos de interesse aleatórios.

Os quatro vértices da região de geração de pontos de interesse aleatórios é dada natabela a seguir.

Coordenada dos vértices (graus).

Vértice Latitude Longitude1 29, 9888700 S 51, 167394 O2 29, 9888700 S 51, 172394 O3 29, 9938700 S 51, 167394 O4 29, 9938700 S 51, 172394 O

Documents

Controle de Missão de Voo de , Veículo Aéreo Não-Tripulado