Hybrid A*
- También llamado: Hybrid A-star, hybrid-state A*
- Categoría: Planning & manipulation › Motion planning
- Etiquetas: path-planning, graph-search, autonomous-driving, nonholonomic, parking
Una variante de la búsqueda A* para robots tipo coche que expande nodos simulando movimientos de giro factibles en estado continuo, mientras poda con una cuadrícula gruesa de (x, y, orientación).
Definición
Hybrid A es un planificador de caminos basado en búsqueda para vehículos con restricciones no holonómicas, presentado por Dolgov, Thrun, Montemerlo y Diebel para la participación de Stanford en el DARPA Urban Challenge de 2007, donde se encargaba de los aparcamientos y otras zonas no estructuradas. Como el A estándar, mantiene una lista abierta ordenada por coste más heurística. La diferencia está en cómo se representan los estados. El espacio de búsqueda se divide en celdas de posición y orientación, pero cada nodo conserva una pose continua exacta. Un nodo se expande simulando el vehículo, normalmente con un modelo de bicicleta** cinemático, a lo largo de un arco corto con unos pocos ángulos de giro, como todo a la izquierda, recto y todo a la derecha, avanzando y, si está permitido, marcha atrás. Una pose nueva solo se conserva si su celda no se ha alcanzado ya con un coste menor.
Como cada arista es un movimiento simulado, el camino resultante es conducible por construcción, algo que un A simple en cuadrícula sobre los centros de las celdas no puede ofrecer. El precio es que la poda por celdas descarta estados que podrían haber llevado a una solución, de modo que el planificador no es ni completo ni óptimo en sentido estricto; las celdas gruesas lo hacen rápido pero pueden hacer que se le escapen maniobras ajustadas. El método original usaba dos heurísticas admisibles y tomaba la mayor: la longitud del camino más corto para un coche sin obstáculos, como un camino de Reeds–Shepp o de coche de Dubins**, y el camino más corto que tiene en cuenta los obstáculos para un robot que puede girar sobre sí mismo, obtenido de una búsqueda 2D en la cuadrícula. También intentaba periódicamente conectar el nodo actual directamente con el objetivo mediante una curva de Reeds–Shepp, lo que se llama expansión analítica y ayuda a la búsqueda a alcanzar una pose objetivo exacta.
El camino en bruto sigue las elecciones discretas de giro, así que zigzaguea ligeramente. El sistema original lo suavizaba con un optimizador basado en gradiente que equilibraba holgura, curvatura y suavidad, y después lo interpolaba para el controlador de seguimiento. Hybrid A se diferencia de la planificación con retícula de estados, que une puntos fijos de una retícula con primitivas de movimiento** precalculadas, y de los planificadores en el sistema de referencia de Frenet, que suponen un carril de referencia.
Por qué importa
Hybrid A* es uno de los planificadores más usados para robots tipo coche en aparcamientos, patios y otros espacios sin carriles. Muestra una forma práctica de combinar la velocidad de la búsqueda en cuadrícula con caminos que respetan los límites de giro de un vehículo, y su estructura aparece en muchas pilas de conducción de código abierto.
Aplicaciones clave
- Aparcamiento automatizado y maniobras de aparcacoches
- Maniobras de camiones, tractores de arrastre y remolques en patios y depósitos
- Robots tipo coche en almacenes, explotaciones agrícolas y obras
- Planificación en zonas no estructuradas dentro de pilas de conducción autónoma
- Planificación de rutas para vehículos todoterreno y de minería
En la práctica
Un tractor de arrastre autónomo debe entrar marcha atrás en un muelle de carga. El planificador discretiza el patio en celdas de posición e intervalos de orientación, expande nodos con unos pocos ángulos de giro hacia delante y hacia atrás usando el modelo de bicicleta y comprueba en cada pose simulada si el contorno completo del vehículo colisiona. Cada pocas expansiones intenta una conexión directa de Reeds–Shepp con la pose del muelle. Una vez encontrado un camino, se suaviza en curvatura y holgura, se vuelve a comprobar frente a colisiones y recibe un perfil de velocidad antes de que un controlador de seguimiento de caminos lo ejecute. Cuando el planificador falla en sitios estrechos, el equipo primero reduce el tamaño de celda o añade más ángulos de giro antes de cambiar cualquier otra cosa.
Ideas erróneas comunes
- Hybrid A es un A corriente en una cuadrícula — los nodos guardan poses continuas alcanzadas mediante movimientos de giro simulados, y la cuadrícula solo poda duplicados
- Sus caminos pueden ser cinemáticamente infactibles por culpa de la cuadrícula — las aristas son movimientos simulados del vehículo, así que la factibilidad se cumple; lo que cuesta la cuadrícula es la completitud y la optimalidad
- Hybrid A* da el camino más corto — la poda por celdas y las pocas opciones de giro hacen que el resultado sea aproximado, normalmente seguido de un suavizado
- Planifica la trayectoria completa con velocidades — planifica un camino geométrico; los perfiles de velocidad y la dinámica se tratan después
Quién debería saberlo
- Ingenieros de conducción autónoma que trabajan en aparcamiento y zonas no estructuradas
- Desarrolladores de robots móviles con plataformas tipo coche o Ackermann
- Estudiantes de planificación de movimiento que estudian la planificación basada en búsqueda
- Ingenieros de robótica de campo en agricultura, minería y logística
Tecnologías relacionadas
- Búsqueda A (A search)
- Curvas de Reeds–Shepp
- Planificador de retícula de estados (state lattice planner)
- Campo de Voronoi (Voronoi field)
- Suavizado de caminos (path smoothing)
- Controladores Pure Pursuit y Stanley
Términos relacionados
- Nonholonomic Constraint
- Dubins Car
- Bicycle model
- Motion Primitive
- Configuration Space
- Frenet Frame Planning
Proyectos 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