Planejamento Quinodinâmico Randomizado

Este artigo apresenta a primeira abordagem randomizada para o planejamento quinodinâmico (também conhecido como planejamento de trajetórias ou design de trajetórias). A tarefa é determinar entradas de controle para conduzir um robô de uma configuração e velocidade iniciais para uma configuração e velocidade de objetivo, obedecendo a modelos dinâmicos baseados em física e evitando obstáculos no ambiente do robô. Os autores consideram sistemas genéricos que expressam a dinâmica não linear de um robô em termos do espaço de configuração de alta dimensão do robô. O planejamento quinodinâmico é tratado como um problema de planejamento de movimento em um espaço de estado de dimensão superior que possui tanto restrições diferenciais de primeira ordem quanto restrições globais baseadas em obstáculos. O espaço de estado desempenha o mesmo papel que o espaço de configuração para o planejamento básico de caminhos; no entanto, técnicas padrão de planejamento de caminhos randomizados não se aplicam diretamente ao planejamento de trajetórias no espaço de estado. Os autores desenvolveram uma abordagem de planejamento randomizada que é especialmente adaptada para problemas de planejamento de trajetórias em espaços de estado de alta dimensão. A base para esta abordagem é a construção de árvores aleatórias de exploração rápida, que oferecem benefícios semelhantes aos obtidos por métodos de planejamento holonômicos randomizados bem-sucedidos, mas se aplicam a uma classe de problemas muito mais ampla. Uma análise teórica do algoritmo é apresentada. Resultados experimentais são apresentados para uma implementação que calcula trajetórias para hovercrafts e satélites em ambientes congestionados, resultando em espaços de estado de até 12 dimensões.