La Tecnología de Resolución de Restricciones1 Rodolfo Fernández González

Ante el boom de la demanda de aplicaciones de planificación y asignación de recursos, la tecnología de resolución de restricciones ofrece soluciones eficientes y fiables, sobre la base de técnicas y productos consolidados.

Planificación y Diseño: actualidad de los problemas de configuración Una importante categoría de los problemas estudiados en Inteligencia Artificial es la configuración. La solución de este tipo de problemas se construye o sintetiza a partir de componentes de distinta naturaleza, de acuerdo con unas reglas o condiciones determinadas, que es lo que llamamos restricciones. El resultado de esa «construcción» es un diseño o un plan de acción. Los problemas de este tipo se sitúan en dominios de aplicación que en los últimos años han adquirido una enorme importancia, dada la criticidad del posicionamiento competitivo en el mercado, la demanda de servicios de calidad creciente, el esfuerzo continuado por la disminución de costes, etc. En especial, prácticamente todas las actividades logísticas (véase BIT n° 5, diciembre de 1994) incluyen componentes de esta naturaleza. Podemos identificar los siguientes ámbitos de aplicación: • Planificación de turnos de personal (enfermería, seguridad, cajas en grandes superficies, conductores,...); • Planificación de rutas de transporte y distribución, estiba y desestiba; • Planificación del trabajo en planta; • Planificación de obra civil; • Configuración de corte; • Maquetado de páginas; • Diseño de instalaciones industriales, máquinas, dispositivos, ... Básicamente, la planificación consiste en la asignación de actividades a recursos en el tiempo, para llevar a cabo un conjunto determinado de tareas. En la planificación a capacidad finita (scheduling) se define la utilización de cada recurso en un intervalo de tiempo dado, y el problema consiste en situar en el tiempo un conjunto de actividades teniendo en cuenta la disponibilidad de recursos y su consumo. Si lo que tenemos es un problema de asignación de recursos, conocemos de antemano la necesidad o demanda de recursos, y el problema que hay que resolver consiste en asignar recursos en el tiempo de forma que dichos recursos siempre cubran la demanda. En ambas categorías de problemas, hay que decidir qué actividades son las que podemos llevar a cabo, y de qué recursos disponemos para ellas. Y, en casi todos los casos, se requiere revisar la planificación producida para hacerse cargo de nuevas incidencias (actividades no previstas; recursos que han dejado de estar disponibles; ...). Se trata, por tanto, en general, de un proceso de toma de decisiones. Las restricciones que afectan a esta toma de decisiones pueden ser de dos tipos: 1

Este artículo se publicó por primera vez en el Boletín Interno Tecnológico (Bit) nº 6 de Marzo de 1995 de la empresa Eritel, actualmente Indra. 1

•

Las restricciones de obligado cumplimiento, no relajables, son las que definen el espacio de las soluciones admisibles. Ejemplos de estas restricciones son: cumplimiento de la normativa de convenios laborales; máquinas disponibles; tiempo mínimo de operaciones; intervalo de seguridad entre operaciones; tiempos de parada para mantenimiento preventivo; disponibilidad de materia prima; orden de operaciones; etc.

•

Las restricciones aconsejables o preferencias, relajables, son las que caracterizan la calidad de las decisiones de planificación que adoptemos. Estas restricciones, como por ejemplo: cumplimiento de las fechas de entrega, frecuencia de cambio de herramientas, etc., inducen a la adopción de prioridades entre servicios u órdenes de fabricación, definición de rutas de transporte o de producción alternativas, uso de recursos de distinto coste, etc.

De esta forma, mientras que las restricciones no relajables definían el espacio de las soluciones admisibles, las preferencias definen el espacio de la optimización de la solución. Es decir, una vez asegurado el cumplimiento de las restricciones obligatorias, y si se dispone de más de una solución, tendremos que elegir cuáles de las soluciones disponibles se ajusta más a los objetivos del sistema. Puesto que estas restricciones normalmente entran en competencia unas con otras, siendo imposible satisfacerlas todas al mismo tiempo, el problema de la planificación también consiste en decidir qué preferencias hay que cumplir y cuáles no. La realización de las funciones de planificación (y diseño) está reservada en las organizaciones a personal con una amplia experiencia, dedicado habitualmente casi por entero a estas tareas, dada su complejidad e importancia. Se trata habitualmente de jefes de operaciones, responsables de logística, o jefes de servicio o de planta. Su medio de trabajo habitual -no mecanizado- es una gran planilla en la que van situando los distintos servicios, recursos -materiales y humanos-, distribuyéndolos en el tiempo y optimizando su uso. La complejidad de la tarea obliga a que se apoyen habitualmente en planes anteriores y que sólo se lleven a cabo pequeñas modificaciones para adecuarlos a las necesidades diarias. Los sistemas clásicos de programación matemática resultaban, en general, demasiado pesados e ineficientes para estas tareas, sobre todo para hacer frente a las incidencias del día a día, y sólo ahora se dispone de técnicas eficaces. Análisis orientado a restricciones Aunque resulta fácil identificar un problema como susceptible de ser tratado desde el punto de vista de resolución de restricciones, no es posible disponer de una solución generalmente aplicable a todos ellos. Incluso dentro de cada categoría de problemas de planificación podemos encontrar grandes diferencias. Por ejemplo, en un caso la planificación de una planta de fabricación puede requerir que sólo las máquinas sean consideradas como recursos, mientras que en otro podemos encontrarnos con que debemos tener en cuenta, además, la mano de obra. El número de actividades a planificar puede oscilar de unas decenas a cientos. En algunos casos, el tiempo de espera a la respuesta no es relevante, mientras que en otros, se deberán tener en cuenta nuevas incidencias que puedan forzar una replanificación y en tiempo casi real. Esta variabilidad pone de relieve el papel central de una estrategia de análisis, sólo a partir de la cual cabe pensar en herramientas especializadas de implementación. Todas las tareas de configuración pueden ser analizadas provechosamente en términos de problemas de resolución de restricciones (Constraint Solving Problems -CSP-). Típicamente, el resultado de dicho análisis conduce a la identificación de tres conjuntos de elementos: variables, valores y restricciones. El objetivo consiste en encontrar todas las asignaciones de valores a las variables que satisfacen todas las restricciones. Genéricamente, para analizar un problema en términos de restricciones tenemos que identificar: 2

a) Los parámetros o variables que forman la solución del problema. Por ejemplo: • Vehículos • Conductores • ... b) El tipo y rango de valores que cada variable puede tomar. Por ejemplo: • días_laborable={lunes,..., viernes} • horario_recepción = (13h, 16h) • x,y,z enteros • x < 10 c) Las condiciones adicionales que una variable debe cumplir respecto a otra. Por ejemplo: • color_país1 color_país2 • y10, modificaremos la etiqueta del nodo x de forma que el extremo inferior de su rango de valores sea 11. • Inconsistencia de arco. Las restricciones que etiquetan cada arco entre dos nodos (diádicas) especifican las relaciones que han de darse entre los valores de ambas variables. Tendremos inconsistencias de arco en una red si hay valores en alguno de los nodos del arco que son incompatibles con valores en el otro nodo. Supongamos que tenemos un problema según el cual las dos variables x e y tienen un rango de valores de 1 a 10, Y la etiqueta del arco especifica la siguiente restricción: • y>x+2 De acuerdo con ella, la etiqueta de x se reduciría a (1,7) y la de y a (4,10). Si tenemos otra variable (y otro nodo) z cuya etiqueta fuera (1,2), Y una restricción adicional • z =< x la etiqueta de x se reduciría aún más, para hacerse igual a la de z. Resolver las inconsistencias de arco de una red, consiste en encontrar valores que satisfagan todas las restricciones simultáneamente. Esto se hace comparando la etiqueta de cada nodo con la de su vecino. Esta operación se itera hasta que ya no se producen nuevos cambios en los conjuntos de valores. Este es el estado de equilibrio de la red. El algoritmo de Waltz , aplicado inicialmente al análisis de escenas visuales, es el ejemplo paradigmático de tal procedimiento de propagación. La idea central de este algoritmo es que la información deducida de un grupo de restricciones se almacena como un cambio en la red, y este cambio se utiliza en las derivaciones posteriores. De esta forma, los efectos de las restricciones se van expandiendo por la red, de modo que las restricciones locales se propagan globalmente. Al final del proceso podemos encontrarnos con uno de estos tres casos: a) En cada nodo sólo hay un valor. Se trata de la solución que satisface todas las restricciones, y que es única. b) Hay al menos un nodo que tiene más de un valor. Tendremos entonces más de una solución. Pero en este espacio de búsqueda reducido podemos aplicar más fácilmente estrategias de optimización mediante técnicas de programación matemática, heurísticos o cualquier otro procedimiento. c) Hay nodos cuya etiqueta ha quedado vacía. Esto sucede porque hay restricciones que no se pueden cumplir. Lo que procede es pasar a relajar las restricciones no obligatorias (las preferencias) de acuerdo con un orden de prioridades o con algún modelo más complejo que incorpore heurísticos. A continuación se reitera el proceso hasta obtener alguna solución. Los algoritmos que facilitan la resolución de restricciones, construidos todos ellos sobre algoritmos básicos de movimiento en grafos, son numerosos y siguen perfeccionándose continuamente. Lo más importante es ser consciente de que esta tecnología, que aquí sólo se ha presentado en sus

5

fundamentos más básicos, nos permite abordar con garantías la resolución de problemas complejos, modelizados de una forma sencilla y difícilmente tratables por otros medios. Herramientas La tecnología de resolución de restricciones está siendo utilizada ya desde hace algunos años para el tratamiento de problemas de complejidad media/alta. Los primeros dominios de aplicación fueron los sistemas gráficos y las actividades de simulación (Sketchpad en 1965 y ThingLab en 1979). Desde entonces se han desarrollado un gran número de sistemas, y hoy en día se cuenta ya con herramientas comerciales que facilitan el uso de esta tecnología, sin tener que implementar algoritmos específicos. Podemos identificar dos grupos de herramientas de estas características: •

Programación lógica por restricciones (sistemas CLP): Se trata de sistemas Prolog que aumentan la eficiencia de sus algoritmos tradicionales de unificación y resolución mediante algoritmos de tratamiento de restricciones. Su ventaja específica es que facilitan la adopción de un enfoque declarativo puro -y más adecuado para la implementación del resultado de un análisis orientado a la resolución de restricciones- sin incurrir en las ineficiencias tradicionales de la programación lógica. Se pueden mencionar dos herramientas: Prolog 11I (Prologia) y CHIP (Cosytec).

•

Bibliotecas de resolución de restricciones: Con el fin de facilitar la integración en los entornos clásicos -lo que no siempre resulta fácil con las herramientas de programación lógica- algunos desarrolladores han introducido en el mercado bibliotecas que ponen a disposición de programadores clásicos los recursos algorítmicos de la metodología de resolución de restricciones. Productos de este tipo son Charme (Bull) y bibliotecas C++ Solver y Schedule (Ilog). La primera es una biblioteca de optimización de recursos y la segunda una biblioteca orientada específicamente al desarrollo de aplicaciones de planificación a capacidad finita, y que trabaja sobre las clases y procedimientos definidos en Solver.

En tanto que Prolog III maneja restricciones lineales en dominios continuos, Solver, Charme y CHIP se especializan en el tratamiento de dominios finitos, y disponen de los mecanismos de control de la consistencia de arco. Bibliografía «Constraínt Programmíng Languages». Leler,W., Addison-Wesley. 1988. «Constraint Satisfaction in Logic Programming». van Henteryck, P. MIT Press, 1989

6