• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.18.2014.tde-05092014-163621
Documento
Autor
Nome completo
Hiparco Lins Vieira
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Carlos, 2014
Orientador
Banca examinadora
Grassi Júnior, Valdir (Presidente)
Chaimowicz, Luiz
Wolf, Denis Fernando
Título em português
Redução do custo computacional do algoritmo RRT através de otimização por eliminação
Palavras-chave em português
Ambientes dinâmicos
Custo computacional
Otimização
Planejamento de trajetórias
Primitivas de movimento
Replanejamento de trajetórias
RRT
Resumo em português
A aplicação de técnicas baseadas em amostragem em algoritmos que envolvem o planejamento de trajetórias de robôs tem se tornado cada vez mais difundida. Deste grupo, um dos algoritmos mais utilizados é chamado Rapidly-exploring Random Tree (RRT), que se baseia na amostragem incremental para calcular de forma eficiente os planos de trajetória do robô evitando colisões com obstáculos. Vários esforços tem sido realizados a fim de reduzir o custo computacional do algoritmo RRT, visando aplicações que necessitem de respostas mais rápidas do algoritmo, como, por exemplo, em ambientes dinâmicos. Um dos dilemas relacionados ao RRT está na etapa de geração de primitivas de movimento. Se várias primitivas são geradas, permitindo o robô executar vários movimentos básicos diferentes, um grande custo computacional é gasto. Por outro lado, quando poucas primitivas são geradas e, consequentemente, poucos movimentos básicos são permitidos, o robô pode não ser capaz de encontrar uma solução para o problema, mesmo que esta exista. Motivados por este problema, um método de geração de primitivas de movimento foi proposto. Tal método é comparado com os métodos tradicional e aleatório de geração de primitivas, considerando não apenas o custo computacional de cada um, mas também a qualidade da solução obtida. O método proposto é aplicado ao algoritmo RRT, que depois é aplicado em um caso de estudo em um ambiente dinâmico. No estudo de caso, o algoritmo RRT otimizado é avaliado em termos de seus custos computacionais durante planejamentos e replanejamento de trajetória. As simulações são realizadas em dois simuladores: um desenvolvido em linguagem Python e outro em Matlab.
Título em inglês
Reduction in the computational cost of the RRT algorithm through optimization by elimination
Palavras-chave em inglês
Computational cost
Dynamic environments
Motion primitives
Optimization
Path planning
Path replanning
RRT
Resumo em inglês
The application of sample-based techniques in path-planning algorithms has become year-by-year more widespread. In this group, one of the most widely used algorithms is the Rapidly-exploring Random Tree (RRT), which is based on an incremental sampling of configurations to efficiently compute the robot's path while avoiding obstacles. Many efforts have been made to reduce RRT computational costs, targeting, in particular, applications in which quick responses are required, e.g., in dynamic environments. One of the dilemmas posed by the RRT arises from its motion primitives generation. If many primitives are generated to enable the robot to perform a broad range of basic movements, a signicant computational cost is required. On the other hand, when only a few primitives are generated, thus, enabling a limited number of basic movements, the robot may be unable to find a solution to the problem, even if one exists. To address this quandary, an optimized method for primitive generation is proposed. This method is compared with the traditional and random primitive generation methods, considering not only computational cost, but also the quality of local and global solutions that may be attained. The optimized method is applied to the RRT algorithm, which is then used in a case study in dynamic environments. In the study, the modied RRT is evaluated in terms of the computational costs of its planning and replanning. The simulations were developed to access the effectiveness and efficiency of the proposed algorithm.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Hiparco.pdf (1.81 Mbytes)
Data de Publicação
2014-09-15
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2020. Todos os direitos reservados.