Tesis de licenciatura sobre programación con restricciones

Resumen general

Siendo estudiante de grado en informática, mi investigación partió de una pregunta práctica: cuando un simulador acumula muchas condiciones posibles, ¿cómo se consigue que deje de reconsiderar las que ya no pueden ocurrir? Desarrollé y evalué un método para HydLa que se apoya en la dirección en la que un valor está cambiando para retirar de la búsqueda las condiciones que han quedado obsoletas. En el modelo de referencia, el tiempo total de simulación se redujo aproximadamente a la mitad.

Este trabajo es uno de los primeros cimientos de mi filosofía de diseño. La programación con restricciones me enseñó que los resultados complejos no siempre hay que especificarlos directamente: pueden surgir de un espacio de reglas, prioridades y límites definido con cuidado. Esa manera de pensar sostiene hoy mi forma de diseñar a partir de restricciones en la era de la IA: diseñar las condiciones dentro de las cuales un sistema generativo queda libre para actuar.

Resumen

HydLa es un lenguaje de modelado para sistemas híbridos: sistemas en los que el cambio continuo y los eventos discretos interactúan. Su diseño basado en restricciones permite describir esos sistemas de forma concisa y simularlos con gran precisión. El coste es que, en un modelo grande, el simulador puede quedarse comprobando un enorme número de reglas condicionales incluso después de que algunas hayan dejado de ser pertinentes.

Esta investigación propuso reducir esas restricciones con guarda de forma dinámica. Al reconocer un comportamiento monótono —un valor que sigue moviéndose en una sola dirección—, el simulador puede determinar que ciertas guardas nunca llegarán a cumplirse en el futuro y dejar de comprobarlas sin riesgo. El enfoque resultó especialmente eficaz en un modelo con muchos objetos guardados de la misma forma, donde el tiempo de ejecución medido bajó a alrededor de la mitad del original.

1. Introducción

Un sistema híbrido combina comportamiento continuo con eventos discretos. Una pelota que rebota es un ejemplo sencillo: su posición y su velocidad cambian de manera continua mientras está en el aire, pero el instante en que toca una superficie crea un evento discreto que cambia su dirección. Termostatos, vehículos y robots contienen versiones más consecuentes de esa misma mezcla.

HydLa permite describir estos sistemas con restricciones matemáticas y lógicas, en lugar de detallar una única secuencia procedimental. Su simulador, HyLaGI, puede hacer cálculo simbólico sin error de redondeo y trabajar con parámetros inciertos. Este enfoque expresivo, sin embargo, crea un problema de escala: cuando un modelo contiene muchas reglas que se activan solo bajo condiciones concretas, el simulador tiene que preguntarse una y otra vez si cada condición podría ser la siguiente en ocurrir.

2. Restricciones con guarda en la simulación

Una restricción con guarda es una regla que solo se activa cuando su condición de guarda se cumple. En el modelo de referencia anterior, cada tramo de la superficie tiene su propia regla: si la pelota llega a altura cero mientras su posición horizontal está dentro de ese tramo, se aplica la regla del rebote. Dividir la superficie en más piezas da por tanto al simulador más guardas que inspeccionar.

El experimento varió el número de tramos entre 10 y 200. El simulador original se volvía más lento aproximadamente con el cuadrado de ese número. Esto importa más allá del ejemplo de juguete: un modelo mayor puede representar muchos objetos físicos, regiones de contacto o eventos posibles exactamente en esta forma guardada.

3. Localización del cuello de botella

El perfilado mostró que la ralentización no estaba repartida de manera uniforme por el simulador. Con 100 tramos de superficie, el 96 % del tiempo de ejecución medido se consumía en FindMinTime, la operación que busca el primer evento posible siguiente. Estaba evaluando repetidamente las guardas de todas las restricciones candidatas.

Ese resultado concretó el objetivo de la optimización: reducir el número de guardas que FindMinTime tiene que considerar, preservando exactamente el mismo comportamiento simulado.

4. Reducción de las restricciones con guarda

Imagina una pelota que baja rebotando por una escalera. Una vez que la pelota ha pasado un escalón y sigue avanzando, ese escalón ya no puede afectarla. Quien mira el diagrama descarta de inmediato los escalones que quedan detrás; el algoritmo original seguía comprobando todos y cada uno.

Lo difícil es demostrar que una guarda descartada no volverá a hacer falta más adelante. Eliminarla solo porque ahora es falsa podría producir en silencio un resultado incorrecto si vuelve a cumplirse. Por eso la propuesta se apoya en la monotonía: si se garantiza que una variable sigue creciendo, o sigue decreciendo, a lo largo de un intervalo de tiempo.

4.1 Enfoque para la monotonía uniforme

El primer enfoque se aplica cuando una variable se mueve en una sola dirección durante toda la simulación. En el modelo de la superficie dividida, la posición horizontal de la pelota siempre crece. Una vez que ha pasado un tramo, la condición de ese tramo no puede volver a cumplirse. Las técnicas de verificación de modelos permiten establecer esta propiedad antes de simular, de modo que las guardas obsoletas se pueden retirar sin riesgo a medida que avanza la ejecución.

4.2 Enfoque para la monotonía alternante

Muchos sistemas reales no se mueven en una sola dirección para siempre. Una variable puede crecer, girar y luego decrecer. El artículo esbozó por eso un segundo enfoque: partir de una dirección supuesta, vigilar esa suposición con aserciones y reiniciar la lógica de reducción desde el punto en que la dirección cambia. Las guardas retiradas para un intervalo monótono se restablecen cuando empieza el siguiente.

5. Resultados experimentales

Implementé el enfoque de monotonía uniforme y lo evalué con el modelo de la superficie dividida. Tanto el algoritmo original como el propuesto seguían tardando más a medida que crecía el número de tramos, pero la versión propuesta hacía sistemáticamente menos trabajo. Comparando las curvas ajustadas, el coeficiente principal bajó de 1,1463 a 0,6083; para este caso de referencia, el tiempo total de simulación se redujo aproximadamente a la mitad.

El resultado no afirma que todo modelo HydLa se vuelva dos veces más rápido. Muestra dónde ayuda el método: en modelos con muchos objetos guardados y una dirección de cambio demostrable, donde las guardas quedan permanentemente irrelevantes durante la ejecución.

6. Conclusión y trabajo futuro

La investigación demostró que el conocimiento sobre un modelo —y no solo un cálculo de bajo nivel más rápido— puede hacer más eficiente una simulación. Al usar la monotonía para reconocer qué posibilidades se han vuelto imposibles, HyLaGI puede reducir su conjunto de restricciones activas sin cambiar el resultado.

El experimento implementado cubrió la monotonía uniforme. El artículo dejó dos direcciones para más adelante: evaluar el método basado en aserciones para el comportamiento alternante, y usar invariantes distintos de la monotonía para identificar más restricciones que puedan eliminarse sin riesgo.