Fechar
Metadados

@PhDThesis{Véras:2019:EsPrAm,
               author = "V{\'e}ras, Luiz Gustavo Diniz de Oliveira",
                title = "Estudo de processos de amostragem n{\~a}o uniforme/informada em 
                         {\'a}rvores aleat{\'o}rias de explora{\c{c}}{\~a}o r{\'a}pida 
                         visando o planejamento autom{\'a}tico de rotas para 
                         ve{\'{\i}}culos a{\'e}reos n{\~a}o tripulados",
               school = "Instituto Nacional de Pesquisas Espaciais (INPE)",
                 year = "2019",
              address = "S{\~a}o Jos{\'e} dos Campos",
                month = "2019-08-09",
             keywords = "planejamento de rota, RRT, grades de Sukharev, v{\'e}rtices 
                         convexos, amostragem n{\~a}o uniforme/informada, path planning, 
                         RRT, Sukharev grids, convex vertices, non uniform/informed 
                         sampling.",
             abstract = "A etapa de planejamento de rota na navega{\c{c}}{\~a}o de um 
                         Ve{\'{\i}}culo A{\'e}reo N{\~a}o Tripulado (VANT) garante que 
                         uma rota cinematicamente e dinamicamente vi{\'a}vel e sem 
                         colis{\~a}o seja planejada entre um ponto inicial e um ponto 
                         final em um ambiente de navega{\c{c}}{\~a}o. Um dos algoritmos 
                         mais utilizados nessa etapa {\'e} o {\'A}rvore Aleat{\'o}ria de 
                         Explora{\c{c}}{\~a}o R{\'a}pida (RRT, do ingl{\^e}s 
                         Rapidly-exploring Random Tree), o qual constr{\'o}i 
                         iterativamente uma estrutura de dados em {\'a}rvore onde cada um 
                         de seus n{\'o}s {\'e} coletado aleatoriamente como uma amostra 
                         do ambiente de navega{\c{c}}{\~a}o at{\'e} que os pontos de 
                         navega{\c{c}}{\~a}o inicial e final sejam conectados 
                         atrav{\'e}s deles. O algoritmo RRT* (l{\^e}-se RRT estrela) 
                         {\'e} uma varia{\c{c}}{\~a}o do algoritmo RRT que garante o 
                         planejamento da rota com o menor comprimento para o VANT baseado 
                         em realoca{\c{c}}{\~a}o de arestas de n{\'o}s vizinhos, 
                         por{\'e}m, devido a essa nova opera{\c{c}}{\~a}o, exige um alto 
                         custo computacional. Alguns autores afirmam que ao direcionar a 
                         coleta de novas amostras para regi{\~o}es espec{\'{\i}}ficas no 
                         ambiente de navega{\c{c}}{\~a}o, seria poss{\'{\i}}vel 
                         melhorar o tempo de planejamento desse algoritmo. Processos que 
                         utilizam esse tipo de abordagem s{\~a}o conhecidos como 
                         amostragem n{\~a}o uniforme/informada. Nesta tese, {\'e} 
                         apresentado um estudo do uso de dois processos de amostragem 
                         n{\~a}o uniforme/informada no algoritmo RRT*, um baseado em grade 
                         de Sukharev (um tipo de grade que gera amostras com dispers{\~a}o 
                         {\'o}tima) e outro nos v{\'e}rtices convexos das 
                         envolt{\'o}rias de seguran{\c{c}}a dos obst{\'a}culos. A 
                         influ{\^e}ncia de cada um dos processos considerados no tempo de 
                         planejamento e comprimento das rotas planejadas pelo algoritmo 
                         RRT* {\'e} estudada. Com base nessas verifica{\c{c}}{\~o}es, 
                         {\'e} apresentado um novo algoritmo baseado no RRT*, denominado 
                         RRT* Sukharev V{\'e}rtices (RRT*-SV), no qual s{\~a}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{\^e}s Batch 
                         Informed Trees Star), que tamb{\'e}m utilizam processos de 
                         amostragem n{\~a}o uniforme/informada. Os testes computacionais 
                         foram realizados considerando diversos ambientes de 
                         navega{\c{c}}{\~a}o com representa{\c{c}}{\~a}o 
                         cont{\'{\i}}nua e bidimensional e com diferentes quantidades e 
                         distribui{\c{c}}{\~o}es espaciais de obst{\'a}culos 
                         est{\'a}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{\'a}rios tipos de ambientes de navega{\c{c}}{\~a}o quando 
                         comparado aos outros algoritmos considerados. Pelo desempenho 
                         demonstrado, o algoritmo RRT*-SV se mostra adequado para uso em 
                         aplica{\c{c}}{\~o}es de navega{\c{c}}{\~a}o em tempo real de 
                         VANTs que tenham como restri{\c{c}}{\~a}o o planejamento da rota 
                         de menor comprimento. ABSTRACT: 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.",
            committee = "K{\"o}rting, Thales Sehn (presidente) and Guimar{\~a}es, 
                         Lamartine Nogueira Frutuoso (orientador) and Medeiros, Felipe 
                         Leonardo L{\^o}bo (orientador) and Carvalho, Solon Ven{\^a}ncio 
                         de and Pinto, Maria Jos{\'e} and Pillat, Valdir Gil",
         englishtitle = "Study of non-uniform/informed sampling processes in 
                         rapidly-exploring random trees for the automatic path planning for 
                         unmanned aerial vehicles",
             language = "pt",
                pages = "237",
                  ibi = "8JMKD3MGP3W34R/3TQ87S5",
                  url = "http://urlib.net/rep/8JMKD3MGP3W34R/3TQ87S5",
           targetfile = "publicacao.pdf",
        urlaccessdate = "11 abr. 2021"
}


Fechar