Tesis de graduación sobre programación basada en restricciones

Resumen

A medida que aumentan los posibles eventos, el simulador examina repetidamente muchas condiciones. Entonces, si a partir del progreso se puede juzgar que “esta condición nunca volverá a cumplirse”, ¿no sería posible detener esa verificación de manera segura? Se diseñó e implementó un método para el lenguaje de modelado de sistemas híbridos HydLa que, utilizando la dirección del cambio de los valores como pista, excluye de la búsqueda en curso las condiciones que ya no son necesarias.

En el modelo de evaluación, se redujo el tiempo de ejecución aproximadamente a la mitad del convencional sin cambiar los resultados de la simulación. Lo importante no es que todos los cálculos se hayan acelerado uniformemente. Es que, utilizando la estructura del problema, se redujo el propio número de posibilidades que deben considerarse.

El enfoque de programación basada en restricciones que aprendí en esta investigación se ha convertido en la base del actual Mi filosofía de diseño. No se trata de especificar directamente cada resultado uno por uno, sino de definir reglas, prioridades y límites, y a partir de ello derivar una solución que se cumpla desde el interior.

Problema — cuanto más aumentan las posibilidades, más lento se vuelve el cálculo

HydLa es un lenguaje para describir sistemas híbridos, en los que se combinan cambios continuos y eventos discretos, como restricciones matemáticas y lógicas. Sin necesidad de escribir todas las secuencias de procedimientos, es posible simular comportamientos que satisfagan las condiciones simplemente declarando lo que debe cumplirse.

Por otro lado, en los modelos que tienen muchas reglas que se activan según las condiciones, el simulador examina repetidamente una gran cantidad de candidatos. Como los candidatos permanecen incluso para condiciones que ya no se cumplen y que tampoco se cumplirán en el futuro, a medida que el modelo crece, se acumulan cálculos innecesarios.

Tema: sistemas que mezclan lo continuo y lo discreto

Una pelota que rebota es un ejemplo claro de un sistema híbrido. En el aire, la posición y la velocidad cambian de manera continua, y en el momento en que toca el suelo, ocurre un evento discreto de rebote. Los termostatos, los automóviles y los robots también poseen estos dos tipos de cambios internamente, aunque a diferente escala.

Para la evaluación, se utilizó un modelo en el que una bola que se mueve horizontalmente rebota en una superficie dividida en múltiples secciones. Para cada sección de la superficie, hay una regla condicional que establece 'si la bola llega a este rango, rebotará'. Al aumentar el número de secciones, se incrementa la cantidad de objetos que se pueden representar, pero también aumentan las condiciones que el simulador debe verificar.

Cuello de botella: el número de condiciones eleva la complejidad computacional

Las reglas que solo se vuelven efectivas cuando se cumplen ciertas condiciones se llaman 'restricciones con guarda'. En el modelo de evaluación, la regla de rebote de un área específica solo se vuelve efectiva cuando la pelota alcanza el suelo y su posición horizontal está dentro de esa área.

Al aumentar el número de parcelas de 10 a 200, el simulador convencional se volvió aproximadamente más lento en proporción al cuadrado del número de parcelas. En modelos de gran escala, el mismo problema se amplía porque aumentan los objetos, las áreas de contacto y los eventos posibles.

Investigación: ¿Dónde estaba el 96% del tiempo de procesamiento?

Al medir el tiempo de procesamiento, en un modelo con 100 secciones, el 96% del total se utilizaba en FindMinTime. Este es el proceso de buscar "el próximo evento más temprano" entre los candidatos. Por lo tanto, todas las condiciones de guardia se evaluaban repetidamente.

Se ha aclarado el lugar que debe mejorarse. No es necesario rehacer todo el método de cálculo; basta con reducir de manera segura los candidatos que se pasan a FindMinTime. El objetivo fue no cambiar los resultados de la simulación y eliminar solo las posibilidades que no necesitan ser investigadas.

Enfoque — Eliminar de manera segura condiciones que nunca se cumplirán

Quiero que imagines una pelota bajando las escaleras rebotando. Si la pelota pasa de un escalón y continúa avanzando, ese escalón ya no puede afectar a la pelota. Cualquiera que vea el diagrama ignora inmediatamente los escalones detrás de la pelota. El algoritmo original seguía examinando cada uno de ellos.

La parte difícil es el lado que demuestra que las guardas eliminadas no serán necesarias más adelante. Si se eliminan solo porque ahora son falsas, podrían devolver silenciosamente un resultado incorrecto cuando vuelvan a ser verdaderas. Por eso, el método propuesto usa la monotonía: se trata de si se puede garantizar que una variable seguirá aumentando o disminuyendo durante un cierto intervalo de tiempo.

Cuando la dirección del cambio no cambia

La primera medida corresponde a los casos en los que una variable se mueve en una sola dirección a lo largo de toda la simulación. En un modelo con superficies divididas, la posición horizontal de la bola siempre aumenta. Una vez que atraviesa un sector, las condiciones de ese sector ya no se cumplen nunca más. Esta propiedad puede verificarse antes de la simulación mediante técnicas de verificación de modelos, por lo que los controles que se vuelven innecesarios a medida que avanza la ejecución pueden eliminarse de manera segura.

Cuando la dirección del cambio cambia a mitad de camino

Muchos sistemas en la realidad no se mueven en una sola dirección para siempre. Las variables pueden aumentar, cambiar de dirección y luego disminuir. Por lo tanto, el artículo presentó una segunda correspondencia. Primero se supone una dirección, se supervisa esa suposición mediante una afirmación, y cuando la dirección cambia, se reanuda el proceso de reducción a partir de ese punto. Los guardias eliminados para un intervalo monótono se restauran cuando comienza el siguiente intervalo.

Resultado: reducir el tiempo de ejecución del modelo de evaluación a la mitad aproximadamente

Se implementó la correspondencia con la monotonía uniforme y se evaluó en un modelo con superficies divididas. Tanto el algoritmo original como el método propuesto requieren más tiempo a medida que aumenta el número de secciones. Sin embargo, el método propuesto tuvo consistentemente menos carga de trabajo. Al comparar las curvas ajustadas, el coeficiente de mayor grado disminuyó de 1.1463 a 0.6083, y en este punto de referencia, el tiempo total de simulación se redujo aproximadamente a la mitad.

Esto no es una afirmación de que todos los modelos de HydLa se vuelvan el doble de rápidos. Lo que se muestra es dónde funciona este método: en modelos con muchos objetos que tienen guardias, donde se puede demostrar la dirección del cambio y donde los guardias se vuelven permanentemente irrelevantes durante la ejecución.

Perspectiva obtenida de este estudio

Lo que se hizo en esta investigación no fue acelerar un poco cada cálculo individual. Se trató de usar lo que se sabe sobre el comportamiento del sistema para reducir el conjunto de posibilidades que se deben considerar. La idea de restringir el espacio de búsqueda sin cambiar el resultado es la fortaleza de la programación basada en restricciones.

Lo que se implementó y evaluó es el caso en que las variables continúan moviéndose en una sola dirección. En los casos en que la dirección del cambio cambia a mitad de camino, se limitó al diseño, y la evaluación quedó como un tema pendiente para el futuro. Aún existe la posibilidad de encontrar restricciones innecesarias utilizando propiedades distintas de la monotonía.

El hecho de que yo, en la actualidad, intente diseñar las condiciones y los límites que la IA puede explorar, en lugar de diseñar directamente la salida de la IA, también se conecta con esta experiencia. Al tratar con resultados complejos, es tan importante definir lo que no es necesario considerar como lo que se va a calcular.