@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/ibi/8JMKD3MGP3W34R/3TQ87S5",
targetfile = "publicacao.pdf",
urlaccessdate = "25 abr. 2024"
}