🔢 mathematics

Square Root Gauss-Newton iLQR

Este artículo presenta una formulación de iLQR de Gauss-Newton de Raíz Cuadrada numéricamente robusta y algorítmicamente simple que aprovecha la estructura de mínimos cuadrados ponderados de la función de costo para permitir un paso hacia atrás basado en descomposiciones QR únicas, mejorando así el condicionamiento y la estabilidad, particularmente dentro de marcos de Lagrangiano aumentado para la optimización de trayectorias con restricciones.

Autores originales: Maximilian Haas-Heger, Jur van den Berg

Publicado 2026-09-21

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Maximilian Haas-Heger, Jur van den Berg

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Los robots, los coches autónomos y las naves espaciales comparten un desafío fundamental: deben moverse de un lugar a otro respetando las leyes de la física y evitando obstáculos. Para lograrlo, dependen de un proceso matemático llamado optimización de trayectorias, que actúa como un navegante superpotente. Este navegante calcula constantemente la mejor ruta posible probando innumerables variaciones de velocidad y dirección, buscando la ruta que utilice la menor cantidad de energía o tiempo. Cuando el mundo es simple y predecible, las herramientas matemáticas estándar pueden resolver este rompecabezas perfectamente. Pero el mundo real es caótico. Los robots tienen articulaciones complejas, los coches se deslizan en carreteras mojadas y las naves espaciales deben esquivar escombros. En estas situaciones, las matemáticas se vuelven no lineales y difíciles, lo que requiere que la computadora realice una serie de conjeturas educadas, las refine y repita el proceso hasta encontrar una solución que funcione. Este proceso iterativo es la columna vertebral de la planificación de movimiento moderna, permitiendo que las máquinas realicen tareas delicadas como el ensamblaje de piezas o el aterrizaje en otros planetas.

Sin embargo, a medida que estas máquinas se vuelven más capaces, se les pide que operen bajo reglas más estrictas. Un brazo robótico podría necesitar evitar golpear una mano humana, o un dron podría necesitar permanecer dentro de un pasillo estrecho. Para imponer estas reglas, las computadoras añaden penalizaciones pesadas a sus cálculos cada vez que una trayectoria se acerca a romper una restricción. Si bien esto obliga al robot a obedecer, también crea un peligro oculto: los números que la computadora utiliza para encontrar la ruta pueden volverse tan salvajemente diferentes en tamaño que la máquina pierde su capacidad de distinguirlos. Es como intentar medir el ancho de un solo cabello mientras se está de pie junto a una montaña; el pequeño detalle se pierde en el ruido de la escala masiva. Cuando esto sucede, los cálculos de la computadora se vuelven inestables y el robot puede fallar al encontrar una ruta, o peor aún, calcular una ruta que parece perfecta en el papel pero que es físicamente imposible.

En un estudio reciente, los investigadores Maximilian Haas-Heger y Jur van den Berg, de Waabi Innovation Inc., abordaron este problema de inestabilidad numérica. Se centraron en un algoritmo específico conocido como Regulador Cuadrático Lineal iterativo, o iLQR, que se utiliza ampliamente para planificar estas rutas complejas. El equipo descubrió que, al cambiar la forma en que el algoritmo maneja su matemática interna, podían hacerlo significativamente más robusto sin ralentizarlo. Su trabajo se centra en una técnica llamada formulación de "raíz cuadrada". En la computación estándar, el algoritmo realiza un seguimiento de una gran tabla de números que representan el costo de cada movimiento posible. Cuando las restricciones son estrictas, esta tabla se vuelve difícil de leer. Los investigadores se dieron cuenta de que, en lugar de rastrear la tabla completa, el algoritmo podía rastrear una versión triangular más simple, muy parecido a mantener solo los ingredientes esenciales de una receta en lugar de toda la despensa.

La clave de su éxito reside en la forma en que simplificaron el problema. Trataron el objetivo del robot como una suma ponderada de errores, similar a cómo un fotógrafo podría enfocarse en minimizar el desenfoque en una foto ajustando configuraciones específicas. Al utilizar un método conocido como Gauss-Newton, que aproxima curvas complejas con líneas rectas, aseguraron que la estructura matemática del problema permaneciera estable. Esto permitió reemplazar los cálculos pesados e inestables por una operación más ligera y precisa llamada descomposición QR. Piense en esta operación como una forma de organizar una pila desordenada de datos en una pila ordenada y pulcra donde cada pieza encaja perfectamente sin huecos ni solapamientos. Este nuevo enfoque permite que la computadora mantenga su precisión incluso cuando la penalización por romper una regla es enorme.

Los investigadores probaron su nuevo método en un escenario desafiante que involucraba a dos brazos robóticos trabajando juntos para transportar un objeto rígido. Los brazos debían mover el objeto desde un punto de partida hasta un objetivo manteniendo sus agarres a una distancia fija entre sí, una restricción que requería que la computadora equilibrara múltiples demandas contrapuestas. Ejecutaron simulaciones donde la penalización por violar esta regla de distancia se aumentó a niveles extremos, mucho más allá de lo que una computadora estándar normalmente manejaría. En estas pruebas, el método tradicional comenzó a fallar, perdiendo precisión y eventualmente produciendo resultados sin sentido a medida que la penalización crecía. El nuevo método de raíz cuadrada, sin embargo, se mantuvo firme. Continuó produciendo rutas precisas incluso cuando la penalización era tan grande que el método estándar se había roto por completo. De hecho, el nuevo enfoque mantuvo de seis a siete dígitos significativos de precisión en la aritmética computacional estándar donde el método antiguo había perdido casi todos ellos.

Esta mejora no es solo una victoria teórica; se traduce directamente en fiabilidad para las máquinas del mundo real. El estudio demostró que el nuevo método podía impulsar el proceso de optimización mucho más lejos, permitiendo que los robots satisfagan las restricciones con un nivel de rigurosidad que antes era imposible. Mientras que el método estándar podría rendirse cuando se le pide ser preciso a una parte en un millón, el nuevo método podría llevar esa precisión a una parte en cien mil millones. Los investigadores señalaron que esta ganancia en precisión viene con casi ningún costo adicional en tiempo de computación, añadiendo menos del tres por ciento al tiempo total requerido para resolver un problema. Esto significa que los ingenieros pueden usar el nuevo método como un reemplazo directo del anterior, haciendo que sus robots sean instantáneamente más capaces de manejar tareas difíciles y de alto riesgo.

El artículo también aborda por qué esta mejora específica no se ha adoptado ampliamente hasta ahora. Aunque técnicas similares de "raíz cuadrada" se han utilizado durante décadas en sistemas de navegación como el filtro de Kalman, han sido más difíciles de aplicar a la optimización de trayectorias porque la matemática es más compleja. Los intentos previos de crear una versión de raíz cuadrada de iLQR eran o demasiado complicados de usar o numéricamente inferiores. Los autores argumentan que su enfoque es diferente porque aprovecha la estructura específica del problema para simplificar la matemática, reduciendo cada paso a una operación única y elegante. Sugieren que, para cualquier robot que planee una ruta bajo restricciones estrictas, no hay razón para no usar este método más estable, tal como los ingenieros no elegirían un sistema de navegación inestable para una nave espacial.

En última instancia, el trabajo demuestra que los límites del movimiento de los robots suelen estar definidos no por las leyes de la física, sino por los límites de la capacidad de la computadora para calcularlas. Al refinar la forma en que se realizan estos cálculos, los investigadores han eliminado una barrera significativa, permitiendo que las máquinas naveguen por entornos más complejos y peligrosos con mayor confianza. El estudio confirma que, con las herramientas matemáticas adecuadas, podemos expandir los límites de lo que los sistemas autónos pueden lograr, asegurando que permanezcan precisos y fiables incluso cuando las apuestas son más altas.

Resumen Técnico: iLQR de Gauss-Newton de Raíz Cuadrada

Formulación del Problema

El artículo aborda el problema de la optimización de trayectorias no lineales para sistemas dinámicos de tiempo discreto. El objetivo es encontrar una secuencia de entradas de control $u_0, \dots, u_{\ell-1}$ que dirija un sistema $x_{t+1} = f_t(x_t, u_t)$ desde un estado inicial hacia un estado final mientras se minimiza una función de costo total. Los autores se centran específicamente en funciones de costo expresables como sumas ponderadas de residuos al cuadrado (estructura de Gauss-Newton):
$c_t(x_t, u_t) = \frac{1}{2} r_t(x_t, u_t)^T W_t r_t(x_t, u_t)$
donde $r_t$ es un vector de residuos y $W_t$ es una matriz de pesos definida positiva. Esta formulación es común en robótica y conducción autónoma, particularmente al manejar restricciones mediante un marco de Lagrangiano aumentado. En tales marcos, se utilizan grandes parámetros de penalización $\mu$ para imponer restricciones, lo que degrada significativamente el condicionamiento del problema de optimización, provocando inestabilidad numérica en los solvers estándar.

Metodología

iLQR de Gauss-Newton Estándar

El Regulador Cuadrático Iterativo (iLQR) resuelve este problema mediante la linealización iterativa de la dinámica y la cuadratización del costo alrededor de una trayectoria nominal. En la variante Gauss-Newton estándar, el costo se aproxima linealizando el vector de residuos $r_t$ en lugar de realizar una expansión de segundo orden completa de la función de costo. Esto produce una matriz Hessiana aumentada $C_t = R_t^T W_t R_t$ , la cual es semidefinida positiva (PSD) por construcción. El algoritmo procede mediante un paso hacia atrás (cálculo de las ganancias de retroalimentación óptimas y matrices de costo de ida) y un paso hacia adelante (simulación del sistema con la nueva política).

La Formulación de Raíz Cuadrada

La contribución central de este artículo es un algoritmo iLQR de Gauss-Newton de Raíz Cuadrada. En lugar de propagar la matriz Hessiana completa del costo de ida $S_t$ , el algoritmo propaga su factor de Cholesky superior $\sqrt{S_t}$ (donde $S_t = \sqrt{S_t}^T \sqrt{S_t}$ ).

La derivación se basa en dos ideas clave:

Propiedad PSD Global: Debido a la estructura de Gauss-Newton, no solo la matriz Hessiana del bloque del costo de ida es PSD, sino que toda la matriz de costo de ida aumentada $Q_t$ es PSD.
Eficiencia de la Descomposición QR: La matriz $Q_t$ puede expresarse como $M_t^T M_t$ , donde $M_t$ se construye a partir de las raíces cuadradas de los pesos, los Jacobianos de los residuos y la raíz cuadrada del factor de costo de ida del siguiente paso de tiempo.

El paso hacia atrás se simplifica a una única descomposición QR de la matriz $M_t$ :
$M_t = \begin{bmatrix} \sqrt{W_t} R_t \\ \sqrt{S_{t+1}} F_t \end{bmatrix}$
Realizar una descomposición QR ( $M_t = QU$ ) produce el factor triangular superior $U$ , el cual codifica directamente el factor de Cholesky de $Q_t$ . La ganancia de retroalimentación $L_t$ y el siguiente factor de costo de ida $\sqrt{S_t}$ se extraen directamente de los bloques de $U$ . Este enfoque evita la formación explícita de las matrices cuadradas (como $Q_t$ o $S_t$ ), previniendo así la amplificación de errores de redondeo.

Para problemas con restricciones utilizando el método de Lagrangiano aumentado, los Jacobianos de las restricciones y los términos de penalización simplemente se anexan como un bloque de filas adicional a $M_t$ , manteniendo la misma estructura computacional.

Principales Contribuciones

Estabilidad Numérica: Al propagar factores de Cholesky en lugar de matrices completas, el algoritmo efectivamente duplica el número de dígitos significativos fiables. El número de condición del factor de Cholesky escala con $\sqrt{\mu}$ en lugar de $\mu$ , mitigando directamente la degradación numérica causada por grandes parámetros de penalización en la optimización con restricciones.
Simplicidad Algorítmica: A diferencia de otras formulaciones de raíz cuadrada para iLQR o Programación Dinámica Diferencial (DDP), que eran algorítmicamente complejas o requerían múltiples descomposiciones y actualizaciones de rango uno, este método reduce cada paso del pase hacia atrás a una única descomposición QR.
Eficiencia Computacional: La sobrecarga de la formulación de raíz cuadrada es mínima. La complejidad computacional aumenta, como máximo, un factor de 2 (el costo clásico de QR sobre las ecuaciones normales) para el término principal dependiente de la dimensión del residuo. En escenarios prácticos (por ejemplo, manipulación bimanual), el tiempo total de computación aumenta en menos del 3%.
Robustez ante la Singularidad: El método garantiza la semidefinición positiva numérica por construcción. Mientras que los solvers estándar pueden fallar completamente cuando la Hessiana se vuelve indefinida debido a errores de redondeo, la variante de raíz cuadrada se degrada de forma gradual, permitiendo realizar controles de salud basados en las entradas diagonales del factor triangular.

Resultados Experimentales

Los autores validaron el método en un problema de optimización de trayectoria con restricciones que involucra dos brazos robóticos de 3 eslabones transportando cooperativamente un objeto.

Comparación de Precisión: Al compararse contra una referencia de alta precisión (50 dígitos decimales), el iLQR estándar (usando precisión doble, f64) perdió aproximadamente un dígito significativo por cada década de aumento en el parámetro de penalización $\mu$ . Con $\mu = 10^{16}$ , el método estándar falló por completo. En contraste, la variante de raíz cuadrada en f64 mantuvo de seis a siete dígitos significativos incluso con $\mu = 10^{20}$ .
Precisión Simple (f32): La ventaja fue aún más pronunciada en precisión simple. El solver f32 estándar falló en $\mu = 10^7$ , mientras que el solver de raíz cuadrada f32 se mantuvo funcional hasta $\mu = 10^{15}$ , proporcionando cinco a seis décadas adicionales de estabilidad.
Convergencia: En un bucle completo de Lagrangiano aumentado, el solver de raíz cuadrada convergió exitosamente desde 24 trayectorias iniciales aleatorizadas a una tolerancia de restricción de $10^{-8}$ , mientras que el solver estándar falló en $10^{-7}$ . El método de raíz cuadrada no encontró un óptimo "mejor", pero permitió que el bucle externo redujera las restricciones de forma más estricta antes de que el ruido numérico causara el fallo del pase hacia atrás.

Significado y Reivindicaciones

El artículo sostiene que para problemas de optimización de trayectoria que pueden formularse con costos de suma de cuadrados ponderados (una clase amplia que incluye muchas aplicaciones de robótica), el iLQR de Raíz Cuadrada de Gauss-Newton debería ser la opción por defecto sobre el iLQR estándar. Los autores trazan un paralelo con la adopción generalizada de los filtros de Kalman de raíz cuadrada en la estimación, señalando que la naturaleza dual de la estimación y el control sugiere beneficios similares.

La importancia radica en la combinación de elegancia y robustez. El método elimina la necesidad de técnicas de regularización ad-hoc (como el amortiguamiento de Levenberg-Marquardt) que a menudo se requieren para mantener la definición positiva en el iLQR estándar. Los autores afirman que "no hay desventajas" al usar esta formulación en sistemas de producción donde se aplica la estructura de Gauss-Newton, ya que ofrece un mejor condicionamiento numérico con una sobrecarga computacional insignificante. El artículo concluye que el éxito de los métodos de raíz cuadrada en la estimación debe extenderse a la optimización de trayectorias, siempre que la estructura del problema permita la aproximación de Gauss-Newton.