El clásico problema matemático se manifiesta en el mundo real.

Hace cien años, el gran matemático David Hilbert hizo una pregunta de investigación desde el campo de las matemáticas puras. Los desarrollos recientes en la teoría de la optimización llevan el trabajo de Hilbert al mundo de los robomóviles

Mucho antes de que los robots pudieran correr y los autos pudieran conducir, los matemáticos consideraron una simple pregunta matemática. Finalmente, lo resolvieron y lo dejaron a un lado, sin poder saber que el objeto de su curiosidad matemática se manifestaría en máquinas del futuro lejano.

El futuro ha llegado. Como resultado del nuevo trabajo de Amir Ali Ahmadi y Aniruda Majumara de la Universidad de Princeton, el problema clásico de las matemáticas puras está listo para proporcionar una prueba de hierro de que los drones automáticos y los robomobiles no se estrellarán contra los árboles ni rodarán en el carril que viene.

"Existe una garantía completa y 100% demostrable de que su sistema" puede evitar colisiones, dijo Georgina Hall , una estudiante graduada de Princeton que colaboró ​​con Ahmadi en este trabajo.

Amir Ali Ahmadi, profesor de Princeton

La garantía se otorga en un lugar inesperado, en un problema matemático conocido como " suma de cuadrados ". Fue puesto en 1900 por el gran matemático David Hilbert. Preguntó si ciertas ecuaciones siempre pueden expresarse como la suma de dos términos separados, cada uno de los cuales es cuadrado.

Los matemáticos respondieron la pregunta de Hilbert unas décadas más tarde. Luego, casi 90 años después, los científicos e ingenieros informáticos descubrieron que esta propiedad matemática, la expresibilidad de una ecuación en términos de la suma de cuadrados, ayuda a resolver muchos problemas reales que les gustaría resolver.

"Muchas de las matemáticas clásicas del siglo XIX se usan en lo que hago, junto con las matemáticas computacionales muy modernas", dijo Ahmadi.

Sin embargo, tan pronto como los investigadores se dieron cuenta de que la suma de los cuadrados podría ayudar a responder muchos tipos de preguntas, tuvieron problemas para aplicar este enfoque. El nuevo trabajo elimina uno de los mayores problemas, obligando a la vieja pregunta matemática a resolver algunos de los problemas tecnológicos más importantes de nuestro tiempo.

Positivo garantizado

¿Qué significa que cierta cantidad es la suma de cuadrados? Tome el número 13. Esta es la suma de dos cuadrados: 2 ² y 3 ² . El número 34 es la suma de 3 ² y 5 ² .

En lugar de números, la pregunta de Hilbert, el 17 de los 23 problemas que propuso en los albores del siglo XX, trata con polinomios como 5x ² + 16x + 13. A veces, estos polinomios también pueden representarse como sumas de cuadrados. Por ejemplo, 5x ² + 16x + 13 se pueden reescribir como (x + 2) ² + (2x + 3) ² .

Cuando una expresión es la suma de cuadrados, sabes que siempre es positiva (todos los números [reales] al cuadrado dan un número positivo o cero, y la suma de números positivos es positiva). Hilbert quería saber si esto funciona de otra manera: ¿se pueden expresar todos los polinomios no negativos como la suma de cuadrados de funciones racionales? En 1927, el matemático Emil Artin demostró que la hipótesis de Hilbert era cierta.

Esta relación es bastante útil. Si se le da un polinomio complejo, con docenas de variables elevadas al más alto grado, es bastante difícil determinar de inmediato si siempre es no negativo. “Algunos polinomios son obviamente no negativos, otros no. Es difícil evaluar su no negatividad ", dijo Ahmadi.

Pero tan pronto como demuestres que este polinomio puede expresarse en términos de la suma de cuadrados, entonces la no negatividad será simplemente una consecuencia de esto. "La suma de los cuadrados le da un hermoso certificado de positividad", dijo Pablo Parrilo , un científico e ingeniero informático del Instituto de Tecnología de Massachusetts que participó en llevar el tema de la suma de cuadrados al mundo de las aplicaciones.

Saber que un polinomio particular es siempre no negativo puede parecer una trivialidad matemática. Pero cien años después de que Hilbert hiciera su pregunta, la no negatividad de los polinomios resultó ser la respuesta a los problemas aplicados que nos afectan a todos.

Mejor manera

Suma de cuadrados se encuentra con el mundo real en el campo de la optimización. La teoría de la optimización está preocupada por encontrar la mejor manera de hacer algo dentro de las limitaciones, por ejemplo, encontrar la mejor ruta para llegar al trabajo, dado el estado del camino y la parada necesaria que debe hacer en el camino. Tales escenarios a menudo se pueden reducir a polinomios. En tales casos, es posible resolver u "optimizar" el escenario al encontrar el valor mínimo que toma el polinomio.

Encontrar el mínimo de un polinomio con muchas variables es una tarea difícil. No existe un algoritmo simple del libro de texto para calcular el valor mínimo de polinomios complejos; además, son difíciles de construir en un gráfico.

Georgina Hall

Dado que el valor mínimo de un polinomio es difícil de calcular directamente, los investigadores hacen suposiciones sobre este valor por otros métodos. Aquí es donde entra en juego la no negatividad, y la cuestión de si un polinomio es la suma de cuadrados. "Asegurar la no negatividad es la esencia de todos los problemas de optimización", dijo Reha Thomas, matemática de la Universidad de Washington.

Una forma de encontrar el valor mínimo es hacer la pregunta: ¿qué valor máximo se puede restar de un polinomio no negativo para que no se vuelva negativo en algún momento? Para responder a la pregunta, es necesario verificar varios valores: ¿es posible restar 3 para que no se vuelva negativo? Y 4? Y 5? Repitiendo el procedimiento, en cada paso debe saber si el polinomio permanece no negativo. Esto se verifica a través de la posibilidad de su expresión como la suma de cuadrados.

"La pregunta que debe hacerse es" ¿el polinomio no es negativo? ". El problema es que con una gran cantidad de variables, esta pregunta es difícil de responder", dijo Ahmadi. "Por lo tanto, usamos la suma de los cuadrados como un reemplazo para la no negatividad".

Tan pronto como los investigadores se den cuenta del mínimo, el valor óptimo del polinomio, pueden usar otros métodos para determinar los parámetros de entrada que conducen a este valor. Sin embargo, para que la no negatividad ayude a resolver problemas de optimización, debe encontrar una forma de calcular rápidamente si un polinomio se expresa en términos de la suma de cuadrados. Y para que los investigadores pudieran hacer esto, les tomó 100 años desde el momento en que Hilbert planteó la pregunta.

Rompiendo el problema

El decimoséptimo problema de Hilbert pasó del mundo de las matemáticas puras al plano aplicado alrededor del año 2000. Fue entonces cuando varios investigadores idearon un algoritmo para verificar si un polinomio puede representarse en términos de la suma de cuadrados. Llegaron a este punto resolviendo el problema cuadrado a través de una "programación semi-definida ", gracias a la cual las computadoras pueden hacer frente a tal tarea. Esto permitió a los investigadores de campos como la informática y la ingeniería utilizar las posibilidades de la no negatividad para dirigir sus búsquedas hacia formas óptimas de resolver problemas.

Aniruda Majumdar

Pero la programación semi-definida tiene una gran limitación: funciona lentamente en tareas grandes y no puede procesar algunos de los polinomios más complejos en los que los investigadores están particularmente interesados. La programación semi-definida se puede usar para descomponer en la suma de cuadrados tales polinomios que consisten en no más de una docena de variables elevadas a una potencia de no más de 6. Los polinomios que describen problemas de ingeniería complejos, por ejemplo, garantizando que el robot se mantendrá en pie, pueden ingrese 50 variables, o incluso más que eso. Un programa puede masticar un polinomio de este tipo hasta el final de los tiempos, y aún así no dar la suma de los cuadrados.

En un artículo publicado en línea en junio pasado, Ahmadi y Majumdar explican cómo sortear el lento trabajo de la programación semi-definida. En lugar de tratar de encontrar la descomposición en la suma de cuadrados con un único programa lento, muestran cómo puede hacer esto con una solución
secuencias de tareas más simples, que serán mucho más rápidas de calcular.

Las tareas de este tipo se denominan "lineales" y se desarrollaron en la década de 1940 para resolver problemas de optimización relacionados con problemas militares. Los programas de línea ahora se comprenden bien y se resuelven rápidamente. En un nuevo artículo, Ahmadi y Majumdar muestran que es posible resolver muchos programas lineales conectados (o, en algunos casos, un tipo diferente de problema, un programa de cono de segundo orden), y combinan los resultados para obtener algo casi tan bueno como la respuesta. , que podría dar un programa para programación semi-definida. Como resultado, los ingenieros tienen una herramienta nueva y práctica que pueden usar para verificar la no negatividad y encontrar rápidamente la descomposición en la suma de cuadrados.

"Estudiamos varios problemas de robótica y teoría de control, y demostramos que la calidad de las soluciones obtenidas es útil para el uso práctico, y que son mucho más rápidas de calcular", dijo Majumdar.

Prueba de seguridad

La velocidad de decisión lo es todo si estás en un robot robótico. En tal situación, el polinomio puede actuar como una barrera matemática establecida alrededor de obstáculos en los que no desea chocar, si se puede calcular lo suficientemente rápido.

Imagine un ejemplo simple: un automóvil robótico en un estacionamiento gigante. No hay nada en el estacionamiento, excepto una cabina de seguridad en el otro extremo. Su tarea es programar la máquina para que nunca se bloquee en esta cabina.

En este caso, puede tirar de la cuadrícula al estacionamiento. Luego, haga un polinomio que tome puntos en la cuadrícula como entrada. Asegúrese de que los valores del polinomio en la ubicación de la máquina sean negativos y que el valor en la ubicación de la cabina de la guardia sea positivo.

En algunos conjuntos de puntos entre su automóvil y la cabina, el polinomio pasará de menos a más. Dado que su automóvil solo puede ubicarse donde el polinomio es negativo, estos puntos desempeñarán el papel de una pared.

“Si comienzas desde cierto lugar, el robot no cruzará la línea detrás de la cual se encuentra el obstáculo. Esto le proporciona evidencia formal de evitar colisiones ”, dijo Ahmadi.

Por supuesto, será inconveniente si esta pared está en el medio del camino entre la máquina y la cabina. Es necesario construir un polinomio para que la pared rodee el obstáculo lo más apretado posible. Esta opción protegerá la cabina y le dará al automóvil mucho espacio para moverse.

En la práctica, debe minimizar el valor, la distancia entre la pared y la cabina, por lo que debe cambiar la gráfica del polinomio y ver qué tan lejos se puede mover hasta que pase de menos a más. Esto se logra al verificar si el polinomio sigue siendo la suma de cuadrados.

El estacionamiento casi vacío es una cosa. Pero en escenarios realistas de control de una máquina, sus sensores detectan constantemente nuevos obstáculos en movimiento: automóviles, bicicletas, niños. Cada vez que aparece un nuevo obstáculo o uno conocido se mueve, la máquina necesita construir nuevos polinomios complejos que encierren estos obstáculos. Esta es una gran cantidad de controles sobre la cantidad de cuadrados que se deben realizar sobre la marcha.

Hace siete años, otro par de investigadores ya imaginaban que tales técnicas para trabajar con polinomios podrían usarse para separar los robomobiles y aquellos lugares donde no deberían caerse. Pero en ese momento, el poder de las computadoras hizo de esta idea un sueño.

El nuevo enfoque de Ahmadi y Majumdar abre una nueva forma de llevar a cabo dicha computación instantánea. Entonces, si los robomobiles pueden moverse con seguridad alrededor del mundo, podemos agradecer a Google y Tesla, así como a Hilbert por esto.