Planejamento de trajetórias para veículos aéreos não tripulados usando modelagem computacional de ambientes de navegação através de grafos de visibilidade e modelos digitais de elevação

• Ano de defesa: 2012
• Autor(a) principal: Felipe Leonardo Lôbo Medeiros
• Orientador(a): Horacio Hideki Yanasse
• Banca de defesa: João Batista Camargo Júnior, Karl Heinz Kienitz
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Instituto Nacional de Pesquisas Espaciais
• Programa de Pós-Graduação: Programa de Pós-Graduação do INPE em Computação Aplicada
• País: BR
• Resumo em Inglês: This work focuses on the problem of automatic planning of two-dimensional trajectories for Unmanned Aerial Vehicles (UAVs) using computational modeling of navigation environments through visibility graphs, digital elevation models and spatial distributions of analysis of the effects caused by the fall of these vehicles. Visibility graphs constructed through digital elevation models can present a high number of nodes and edges. The first objective of this work was the study of the simplification of such graphs. Initially, a simplification was considered by decreasing the number of convex intermediate vertices of the polygonal obstacles that define the nodes of a visibility graph. Two problems were identified with the application of conventional methods for the simplification of polygonal obstacles: the occultation of obstacles; and the creation of invisibility areas, causing loss of navigable area. Aiming at the solution of such problems, an algorithm was proposed for the simplification of polygons based on the invisibility area among convex intermediate vertices. Analyzing the results obtained, it was verified that the proposed algorithm allows a significant reduction of the number of vertices, limiting the creation of invisibility areas and avoiding the occultation of obstacles. Another objective was to evaluate the possibility of simplifying the visibility graphs directly by eliminating nodes or edges. In this work, the Dijkstra Algorithm based on terrain Elevation (DAE) was proposed for the planning of free-collision trajectories for UAVs through the representations of navigation environments defined by visibility graphs and by digital elevation models. ADE uses kinematic constraints of UAVs for the planning. A navigation trajectory must be dynamically feasible and collision-free, but it is also important to plan the trajectory to reduce the risk to the population in accidents with falls of UAVs. This way, a method was proposed to model navigation environments defined by the evaluation of the effects of UAVs falls and through digital models of elevation. With the results obtained, it could be observed that the visibility graphs constructed by the environments modeled of the proposed method allow the planning of paths and trajectories for UAVs based on an estimation of the expected number of fatalities in possible accidents with falls of these vehicles.
• Link de acesso: http://urlib.net/sid.inpe.br/mtc-m19/2012/03.16.13.15

Este trabalho aborda o problema de planejamento automático de trajetórias bidimensionais para Veículos Aéreos Não Tripulados (VANTs) usando modelagem computacional de ambientes de navegação através de grafos de visibilidade, modelos digitais de elevação e distribuições espaciais de análises de efeitos causados pela queda destes veículos. Grafos de visibilidade construídos através de modelos digitais de elevação podem apresentar um elevado número de nós e de arestas. O primeiro objetivo deste trabalho foi o estudo da simplificação de tais grafos. Inicialmente, foi abordada a simplificação pela redução do número de vértices intermediários convexos dos obstáculos poligonais que definem os nós dos grafos de visibilidade. Foram identificados dois problemas com a aplicação de métodos convencionais para a simplificação de obstáculos poligonais: a ocultação de obstáculos; e a criação de áreas de invisibilidade, causando perda de área navegável. Visando à solução de tais problemas, foi proposto um algoritmo para simplificação de polígonos baseado na área de invisibilidade entre vértices intermediários convexos. Através de análises dos resultados obtidos, verificou-se que o algoritmo proposto permite uma redução significativa do número de vértices intermediários convexos, limitando a criação de áreas de invisibilidade e evitando a ocultação de obstáculos. Outro objetivo foi avaliar a possibilidade de simplificação direta dos grafos de visibilidade, através da eliminação de nós ou de arestas. Neste trabalho foi proposto o Algoritmo Dijkstra baseado em Elevações de terreno (ADE) para o planejamento de trajetórias livres de colisão para VANTs através de representações de ambientes de navegação definidos por grafos de visibilidade e modelos digitais de elevação. O ADE utiliza restrições cinemáticas de VANTs para o planejamento. Uma trajetória de navegação deve ser livre de colisão e dinamicamente viável, mas também é importante que a trajetória seja planejada para reduzir o risco à população em acidentes com queda de VANTs. Deste modo, um método foi proposto para modelar ambientes de navegação definidos através da avaliação dos efeitos da queda de VANTs e através de modelos digitais de elevação. Através dos resultados obtidos, pôde-se observar que os grafos de visibilidade construídos através dos ambientes modelados pelo método proposto permitem o planejamento de rotas e trajetórias para VANTs baseado em uma estimação do número esperado de fatalidades em possíveis acidentes com queda destes veículos.