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