Tesis de grado sobre programación por restricciones
junio de 2019
Visión general
Cuantos más eventos posibles incluye una simulación, más condiciones debe evaluar repetidamente. Pero si su evolución permite demostrar que una condición nunca volverá a cumplirse, ¿se puede omitir esa comprobación de forma segura? Diseñé e implementé un método para HydLa, un lenguaje de modelado de sistemas híbridos, que utiliza la dirección del cambio de las variables para eliminar las condiciones que ya no necesitan comprobarse.
En el modelo de evaluación, el método redujo el tiempo de ejecución a aproximadamente la mitad del empleado por el algoritmo original, sin alterar los resultados de la simulación. La mejora se logró aprovechando la estructura del problema para reducir las posibilidades que debían considerarse.
La perspectiva de la programación por restricciones que desarrollé en esta investigación sustenta hoy mi enfoque de los proyectos de mi portafolio: en lugar de especificar directamente cada resultado, definir reglas, prioridades y límites, y después obtener soluciones que los satisfagan.
Problema: más posibilidades implican más tiempo de ejecución
HydLa describe sistemas híbridos, que combinan cambios continuos y eventos discretos, mediante restricciones matemáticas y lógicas. En lugar de especificar cada paso del procedimiento, el modelo declara las condiciones que deben cumplirse y el simulador encuentra comportamientos que las satisfacen.
En los modelos con muchas reglas condicionales, el simulador comprueba repetidamente un gran conjunto de candidatos. Incluso las condiciones que ya no pueden volver a cumplirse permanecen en ese conjunto. A medida que crece el modelo, esas comprobaciones innecesarias aumentan el trabajo de cálculo.
Modelo: combinar cambios continuos y discretos
Una pelota que rebota es un ejemplo sencillo de sistema híbrido. Su posición y velocidad cambian de forma continua mientras está en el aire, y el contacto con el suelo desencadena un evento discreto de rebote. Los termostatos, los automóviles y los robots también combinan estos dos tipos de cambio, a distintas escalas.
La evaluación utilizó un modelo de una pelota que se desplaza horizontalmente y rebota sobre una superficie dividida en segmentos. Cada segmento tiene una regla condicional que hace rebotar la pelota cuando llega a esa zona. Añadir segmentos permite representar más objetos, pero también aumenta el número de condiciones que el simulador debe comprobar.
Cuello de botella: más condiciones aumentan el tiempo de ejecución
Una regla que solo se activa cuando se cumple una condición se denomina restricción con guarda. En el modelo de evaluación, la regla de rebote de un segmento solo se activa cuando la pelota llega al suelo y su posición horizontal se encuentra dentro de ese segmento.
Al aumentar el número de segmentos de 10 a 200, el tiempo de ejecución del simulador original creció aproximadamente en proporción al cuadrado de ese número. Los modelos mayores pueden agravar este problema al incluir más objetos, zonas de contacto y eventos posibles.
Investigación: ¿a qué se destinaba el 96 % del tiempo de ejecución?
El análisis del rendimiento del modelo con 100 segmentos mostró que FindMinTime consumía el 96 % del tiempo total de ejecución. Esta rutina determina el instante más temprano en que puede producirse el siguiente evento, evaluando repetidamente todas las condiciones de guarda candidatas.
Esto permitió identificar una mejora concreta: reducir de forma segura los candidatos enviados a FindMinTime. El objetivo era omitir únicamente las posibilidades que ya no necesitaban evaluarse, conservando los resultados de la simulación.
Enfoque: eliminar las condiciones que ya no pueden volver a cumplirse
Imagina una pelota que baja rebotando por una escalera. Una vez que ha superado un escalón y sigue avanzando, ese escalón ya no puede afectarla. Una persona que observa el diagrama descarta de inmediato los escalones que quedan atrás; el algoritmo original seguía examinándolos todos.
La dificultad consiste en demostrar que una guarda eliminada no volverá a necesitarse. Eliminarla solo porque ahora es falsa podría producir un resultado incorrecto sin advertencia si vuelve a ser verdadera. Por ello, el método propuesto utiliza la monotonía: la garantía de que una variable seguirá aumentando o disminuyendo durante un intervalo determinado.
Cuando la dirección del cambio se mantiene
El primer enfoque se aplica cuando una variable cambia en una sola dirección durante toda la simulación. En el modelo de superficie segmentada, la posición horizontal de la pelota siempre aumenta. Una vez que supera un segmento, la guarda de ese segmento nunca puede volver a ser verdadera. Las técnicas de verificación de modelos permiten comprobar esta propiedad antes de la simulación, de modo que las guardas pueden eliminarse con seguridad cuando dejan de ser pertinentes durante la ejecución.
Cuando la dirección del cambio se invierte
Muchos sistemas no cambian en una sola dirección indefinidamente: una variable puede aumentar, invertir su dirección y después disminuir. Por ello, la tesis propuso un segundo enfoque. Este supone una dirección de cambio y supervisa esa suposición mediante aserciones. Cuando la dirección cambia, el proceso de reducción se reinicia y restaura las guardas eliminadas durante el intervalo monótono anterior. Este enfoque se diseñó, pero no se implementó ni se evaluó en el proyecto.
Resultado: aproximadamente la mitad del tiempo de ejecución en el modelo de evaluación
Implementé el enfoque de monotonía uniforme y lo evalué con el modelo de superficie segmentada. El tiempo de ejecución aumentó con el número de segmentos en ambos algoritmos, pero el método propuesto fue sistemáticamente más rápido. En las curvas ajustadas, el coeficiente del término de mayor grado pasó de 1.1463 a 0.6083. En esta prueba, el tiempo total de simulación se redujo aproximadamente a la mitad.
El resultado corresponde específicamente a esta prueba. El método resulta útil cuando el modelo contiene muchos objetos con guardas, se puede demostrar la dirección del cambio y las guardas dejan de ser pertinentes de forma permanente durante la ejecución. No implica que todos los modelos de HydLa se ejecuten al doble de velocidad.
Lo que aprendí
Esta investigación utilizó propiedades conocidas del comportamiento de un sistema para reducir el conjunto de posibilidades que el simulador debía considerar. Acotar el espacio de búsqueda conservando los resultados es una de las fortalezas de la programación por restricciones.
La implementación y la evaluación abarcaron variables que seguían cambiando en una sola dirección. El tratamiento de las inversiones de dirección quedó en la fase de diseño y aún requería evaluación. Otras propiedades, además de la monotonía, también podrían ayudar a identificar restricciones innecesarias.
Esta experiencia alimenta mi interés actual por diseñar las condiciones y los límites dentro de los cuales la IA puede buscar soluciones. Al trabajar con resultados complejos, definir qué puede ignorarse con seguridad importa tanto como definir qué debe calcularse.
Takafumi Horiuchi y Kazunori Ueda. «Dynamic Reduction of Guarded Constraints for the Hybrid Systems Modeling Language HydLa». Proceedings of the 33rd Annual Conference of the Japanese Society for Artificial Intelligence, 2019. DOI: 10.11517/pjsai.JSAI2019.0_1E3OS3b02