Open Source Robotics

Uma coleção selecionada de projetos, ferramentas e software de robótica de código aberto de alta qualidade.

Hybrid A*

  • Também chamado: Hybrid A-star, hybrid-state A*
  • Categoria: Planning & manipulation › Motion planning
  • Tags: path-planning, graph-search, autonomous-driving, nonholonomic, parking

Uma variante da busca A* para robôs do tipo carro que expande nós simulando movimentos de esterçamento viáveis em estado contínuo, enquanto poda com uma grade grosseira de (x, y, orientação).

Definição

Hybrid A é um planejador de caminhos baseado em busca para veículos com restrições não holonômicas, apresentado por Dolgov, Thrun, Montemerlo e Diebel para a participação de Stanford no DARPA Urban Challenge de 2007, onde cuidava de estacionamentos e outras áreas não estruturadas. Como o A padrão, ele mantém uma lista aberta ordenada por custo mais heurística. A diferença está em como os estados são representados. O espaço de busca é dividido em células de posição e orientação, mas cada nó guarda uma pose contínua exata. Um nó é expandido simulando o veículo, geralmente com um modelo de bicicleta** cinemático, ao longo de um arco curto com alguns ângulos de esterçamento, como todo à esquerda, reto e todo à direita, andando para a frente e, se permitido, de ré. Uma nova pose só é mantida se sua célula ainda não tiver sido alcançada com custo menor.

Como cada aresta é um movimento simulado, o caminho resultante é dirigível por construção, algo que um A simples em grade sobre os centros das células não consegue oferecer. O preço é que a poda por células descarta estados que poderiam ter levado a uma solução, de modo que o planejador não é nem completo nem ótimo em sentido estrito; células grosseiras o tornam rápido, mas podem fazê-lo perder manobras apertadas. O método original usava duas heurísticas admissíveis e tomava a maior: o comprimento do caminho mais curto para um carro sem obstáculos, como um caminho de Reeds–Shepp ou de carro de Dubins**, e o caminho mais curto que leva em conta os obstáculos para um robô que consegue girar no lugar, vindo de uma busca 2D na grade. Ele também tentava periodicamente conectar o nó atual diretamente ao objetivo com uma curva de Reeds–Shepp, chamada expansão analítica, o que ajuda a busca a alcançar uma pose-objetivo exata.

O caminho bruto segue as escolhas discretas de esterçamento, então ziguezagueia levemente. O sistema original o suavizava com um otimizador baseado em gradiente que equilibrava folga, curvatura e suavidade, e depois o interpolava para o controlador de rastreamento. O Hybrid A difere do planejamento por reticulado de estados, que liga pontos fixos de um reticulado com primitivas de movimento** pré-calculadas, e dos planejadores no referencial de Frenet, que pressupõem uma faixa de referência.

Por que importa

O Hybrid A* é um dos planejadores mais usados para robôs do tipo carro em estacionamentos, pátios e outros espaços sem faixas. Ele mostra uma forma prática de combinar a velocidade da busca em grade com caminhos que respeitam os limites de esterçamento de um veículo, e sua estrutura aparece em muitas pilhas de condução de código aberto.

Principais aplicações

  • Estacionamento automatizado e manobras de manobrista
  • Manobras de caminhões, rebocadores e reboques em pátios e depósitos
  • Robôs do tipo carro em armazéns, fazendas e canteiros de obras
  • Planejamento em áreas não estruturadas dentro de pilhas de condução autônoma
  • Planejamento de caminhos para veículos off-road e de mineração

Na prática

Um rebocador autônomo precisa entrar de ré em uma doca de carga. O planejador discretiza o pátio em células de posição e faixas de orientação, expande nós com alguns ângulos de esterçamento para a frente e para trás usando o modelo de bicicleta e verifica colisões do contorno completo do veículo em cada pose simulada. A cada poucas expansões, ele tenta uma conexão direta de Reeds–Shepp até a pose da doca. Quando um caminho é encontrado, ele é suavizado quanto a curvatura e folga, verificado de novo quanto a colisões e recebe um perfil de velocidade antes que um controlador de rastreamento de caminho o execute. Quando o planejador falha em pontos apertados, a equipe primeiro reduz o tamanho das células ou acrescenta mais ângulos de esterçamento antes de mudar qualquer outra coisa.

Equívocos comuns

  • Hybrid A é um A comum em uma grade — os nós guardam poses contínuas alcançadas por movimentos de esterçamento simulados, e a grade só poda duplicatas
  • Seus caminhos podem ser cinematicamente inviáveis por causa da grade — as arestas são movimentos simulados do veículo, então a viabilidade é garantida; o que a grade custa é completude e otimalidade
  • Hybrid A* dá o caminho mais curto — a poda por células e as poucas opções de esterçamento fazem o resultado ser aproximado, geralmente seguido de suavização
  • Ele planeja a trajetória completa com velocidades — ele planeja um caminho geométrico; perfis de velocidade e dinâmica são tratados depois

Quem deve saber

  • Engenheiros de condução autônoma que trabalham com estacionamento e áreas não estruturadas
  • Desenvolvedores de robôs móveis com plataformas do tipo carro ou Ackermann
  • Estudantes de planejamento de movimento que estudam planejamento baseado em busca
  • Engenheiros de robótica de campo em agricultura, mineração e logística

Tecnologias relacionadas

  • Busca A (A search)
  • Curvas de Reeds–Shepp
  • Planejador por reticulado de estados (state lattice planner)
  • Campo de Voronoi (Voronoi field)
  • Suavização de caminhos (path smoothing)
  • Controladores Pure Pursuit e Stanley

Termos relacionados

  • Nonholonomic Constraint
  • Dubins Car
  • Bicycle model
  • Motion Primitive
  • Configuration Space
  • Frenet Frame Planning

Projetos relacionados

  • Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
  • ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
  • OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
  • Mesh Navigation: Robot navigation on 3D triangle meshes for rough outdoor terrain, from Nature Robots
  • Fields2Cover: Coverage path planning library for autonomous agricultural vehicles
  • Vision Pilot: Autoware Foundation's open-source L2 ADAS stack from a single camera

Este site requer JavaScript. Por favor, habilite o JavaScript para explorar nossos projetos de robótica.