Repositório Institucional da UFPB

Tipo:	Dissertação
Título:	Uma heurística simplificada para funções custo de planejadores da família A*
Autor(es):	Silva, Jefferson Barbosa Belo da
Primeiro Orientador:	Siebra, Clauirton de Albuquerque
Resumo:	Uma das principais questões relacionados ao tema da robótica móvel é descobrir a maneira mais eficiente para realizar a navegação, de um ponto a outro no ambiente, com máxima segurança e despendendo a menor quantidade de tempo e de recursos computacionais possível. À vista disso, o presente trabalho se motiva a desenvolver uma melhoria heurística que possa ser aplicável às funções custo dos principais algoritmos baseados na família A* e que propõe utilizar, de forma mais eficiente, os recursos computacionais disponíveis, aperfeiçoando assim, os resultados obtidos através dos principais algoritmos de buscas aplicados à robótica móvel. A mesma tem o objetivo de minimizar a quantidade de colisões, a duração do trajeto, bem como o tempo de processamento através da minimização da importância da variável g(n) - responsável em armazenar informações subutilizadas do passado dos algoritmos. Para visualizar os efeitos dessa modificação, um levantamento das melhores estratégias de busca em ambiente estático e dinâmico foi realizado e, através deste, foram analisados os quatro melhores e mais atuais algoritmos destacados pela literatura técnica especializada. Algumas comparações foram efetuadas considerando ambientes estáticos e altamente dinâmico com diferentes direções de busca e parâmetros que visavam mensurar a qualidade das trajetórias geradas. Em seguida, esses foram novamente analisados com suas respectivas funções custo modificada. Os resultados da comparação demonstraram que o algoritmo R*, com direção de busca direta, é o mais eficiente para diferentes espaços e pesquisas. No entanto, a modificação em suas respectivas funções custo proporcionou uma melhora significativa nos resultados conquistados pelos algoritmos originais. Em ambientes estáticos, esta modificação se mostrou mais eficaz para problemas grandes e complexos, os que são efetivamente utilizados por robôs reais. Em ambientes altamente dinâmicos, a mesma apresentou uma redução considerável no tempo de planejamento e no número de iterações para localizar o objetivo, bem como reduziu a utilização de memória o que, consequentemente, tornou os robôs mais ágeis e habilidosos.
Abstract:	One of the main issues related to the mobile robotics area is to find the most efficient way to perform the navigation from one point to another over environments, considering maximum safety and spending as less as possible time and computer resources. From this perspective, the aim of this work was to specify improved heuristics that could be applicable to cost functions of key A* based algorithms and use, more efficiently, the available computational resources. In this way, our approach aimed at minimizing the amount of collisions, the length of paths, and the processing time by minimizing the importance of g(n) term, which accounts for storing information from past steps of A* family algorithms. To show the effects of this modification, a survey of the best search strategies in dynamic and static environments was carried out and, after that, we analyzed the four best and latest algorithms, according to the specialized literature. Some comparisons have been made considering static and highly dynamic environments with different directions and search parameters to measure the quality of generated paths. Then, these algorithms were again analyzed with their cost functions modified according to our approach. The results of the comparison show that the R* algorithm, with forward search, is the most efficient for different spaces and searches. However, the change in their respective cost functions provided a significant improvement in the already excellent results achieved by the algorithms. In static environments, this modification showed up to be more effective for large and complex problems, which are commonly used for real robots. In highly dynamic environments, the cost function modification provided a considerable reduction in the time of planning and number of iterations to find the goal, as well as reductions in the memory utilization.
Palavras-chave:	Função custo; Planejamento de caminho; Geração de trajetória. Cost function; Path planning; Trajectory generation.
CNPq:	CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma:	por
País:	Brasil
Editor:	Universidade Federal da Paraíba
Sigla da Instituição:	UFPB
Departamento:	Informática
Programa:	Programa de Pós-Graduação em Informática
Citação:	SILVA, Jefferson Barbosa Belo da. Uma heurística simplificada para funções custo de planejadores da família A*. 2015. 81 f. Dissertação (Mestrado em Informática) - Universidade Federal da Paraíba, João Pessoa, 2015.
Tipo de Acesso:	Acesso aberto
URI:	https://repositorio.ufpb.br/jspui/handle/tede/7846
Data do documento:	21-Ago-2015
Aparece nas coleções:	Centro de Informática (CI) - Programa de Pós-Graduação em Informática

Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.