Detalhes bibliográficos
| Ano de defesa: |
2019 |
| Autor(a) principal: |
Luiz Gustavo Diniz de Oliveira Véras |
| Orientador(a): |
Lamartine Nogueira Frutuoso Guimarães,
Felipe Leonardo Lôbo Medeiros |
| Banca de defesa: |
Solon Venâncio de Carvalho,
Maria José Pinto,
Valdir Gil Pillat |
| Tipo de documento: |
Tese
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Instituto Nacional de Pesquisas Espaciais (INPE)
|
| Programa de Pós-Graduação: |
Programa de Pós-Graduação do INPE em Computação Aplicada
|
| Departamento: |
Não Informado pela instituição
|
| País: |
BR
|
| Resumo em Inglês: |
The path planning step in the navigation of an Unmanned Aerial Vehicle (UAV) ensures that a kinodynamically viable, collision-free path between a start point and an end point in a navigation environment can be planned. One of the most commonly used algorithms for path planning is the Rapidly-exploring Random Tree (RRT), which iteratively constructs a tree data structure where each of its nodes is randomly collected as a sample of the navigation environment until the start and end navigation points are connected through them. The RRT* algorithm (read RRT star) is a variation of the RRT algorithm that ensures the planning of the path with the shortest length for the UAV based on edge relocation of neighboring node edges. However, due to this new operation requires, it require a high computational cost. Some authors affirm that by biasing the collection of new samples to specific regions in the navigation environment, it would be possible to improve the planning time of this algorithm. Processes using this type of approach are known as non-uniform/informed sampling. In this thesis, a study of the use of two non-uniform/informed sampling processes in the RRT* algorithm, one based on Sukharev grid (one type of grid that generates optimally dispersed samples) and the other on the convex vertices of safety envelopes of the obstacles, is carried out together with the RRT* algorithm. The influence of each of the considered processes on the planning time and length of the path planned by the RRT* algorithm is studied. Based on these verifications, a new RRT* based algorithm called RRT* Sukharev Vertices (RRT*-SV) is presented, in which both processes studied in this work are used. Computational tests were performed to verify if the RRT*-SV algorithm has shorter planning time than the RRT* algorithm and other literature algorithms such as RRT*-Smart, Informed-RRT* and BIT* (Batch Informed Trees Star) algorithms, which also uses non-uniform/informed sampling processes. The computational tests were performed considering several navigation environments with continuous and two-dimensional representation and with different quantities and spatial distributions of polygonal static obstacles. The results indicate that the proposed sampling process accelerates the RRT* planning time and shows that the RRT*-SV algorithm has better performance in various types of navigation environments when compared to the other algorithms considered. Due to its performance, the RRT*-SV algorithm is suitable for use in real-time UAV navigation applications that have as constraint the planning of the path with the shortest length. |
| Link de acesso: |
http://urlib.net/sid.inpe.br/mtc-m21c/2019/08.07.15.41
|
Resumo: |
A etapa de planejamento de rota na navegação de um Veículo Aéreo Não Tripulado (VANT) garante que uma rota cinematicamente e dinamicamente viável e sem colisão seja planejada entre um ponto inicial e um ponto final em um ambiente de navegação. Um dos algoritmos mais utilizados nessa etapa é o Árvore Aleatória de Exploração Rápida (RRT, do inglês Rapidly-exploring Random Tree), o qual constrói iterativamente uma estrutura de dados em árvore onde cada um de seus nós é coletado aleatoriamente como uma amostra do ambiente de navegação até que os pontos de navegação inicial e final sejam conectados através deles. O algoritmo RRT* (lê-se RRT estrela) é uma variação do algoritmo RRT que garante o planejamento da rota com o menor comprimento para o VANT baseado em realocação de arestas de nós vizinhos, porém, devido a essa nova operação, exige um alto custo computacional. Alguns autores afirmam que ao direcionar a coleta de novas amostras para regiões específicas no ambiente de navegação, seria possível melhorar o tempo de planejamento desse algoritmo. Processos que utilizam esse tipo de abordagem são conhecidos como amostragem não uniforme/informada. Nesta tese, é apresentado um estudo do uso de dois processos de amostragem não uniforme/informada no algoritmo RRT*, um baseado em grade de Sukharev (um tipo de grade que gera amostras com dispersão ótima) e outro nos vértices convexos das envoltórias de segurança dos obstáculos. A influência de cada um dos processos considerados no tempo de planejamento e comprimento das rotas planejadas pelo algoritmo RRT* é estudada. Com base nessas verificações, é apresentado um novo algoritmo baseado no RRT*, denominado RRT* Sukharev Vértices (RRT*-SV), no qual são utilizados ambos os processos estudados neste trabalho. Testes computacionais foram realizados para verificar se o algoritmo RRT*-SV apresenta menor tempo de planejamento do que o algoritmo RRT* e outros algoritmos da literatura como, por exemplo, os algoritmos RRT*-Smart, o Informed-RRT* e o BIT* (do inglês Batch Informed Trees Star), que também utilizam processos de amostragem não uniforme/informada. Os testes computacionais foram realizados considerando diversos ambientes de navegação com representação contínua e bidimensional e com diferentes quantidades e distribuições espaciais de obstáculos estáticos poligonais. Os resultados indicam que o processo de amostragem proposto acelera o tempo de planejamento do RRT* e demonstram que o algoritmo RRT*-SV possui melhor desempenho em vários tipos de ambientes de navegação quando comparado aos outros algoritmos considerados. Pelo desempenho demonstrado, o algoritmo RRT*-SV se mostra adequado para uso em aplicações de navegação em tempo real de VANTs que tenham como restrição o planejamento da rota de menor comprimento. |
