Satisfacción de restricciones

En inteligencia artificial e investigación de operaciones , la satisfacción de restricciones es el proceso de encontrar una solución a través de un conjunto de restricciones que imponen condiciones que las variables deben satisfacer . ^[1] Por lo tanto, una solución es una asignación de valores a las variables que satisface todas las restricciones, es decir, un punto en la región factible .

Las técnicas utilizadas en la satisfacción de restricciones dependen del tipo de restricciones que se consideren. A menudo se utilizan restricciones sobre un dominio finito , hasta el punto de que los problemas de satisfacción de restricciones se identifican típicamente con problemas basados ​​en restricciones sobre un dominio finito. Tales problemas se resuelven generalmente mediante búsqueda , en particular una forma de retroceso o búsqueda local . La propagación de restricciones es otra familia de métodos utilizados en tales problemas; la mayoría de ellos son incompletos en general, es decir, pueden resolver el problema o demostrar que no se puede satisfacer, pero no siempre. Los métodos de propagación de restricciones también se utilizan junto con la búsqueda para hacer que un problema dado sea más simple de resolver. Otros tipos de restricciones considerados son sobre números reales o racionales ; la resolución de problemas sobre estas restricciones se realiza mediante la eliminación de variables o el algoritmo simplex .

La satisfacción de restricciones como un problema general se originó en el campo de la inteligencia artificial en la década de 1970 (ver por ejemplo (Laurière 1978)). Sin embargo, cuando las restricciones se expresan como ecuaciones lineales multivariadas que definen (in)igualdades, el campo se remonta a Joseph Fourier en el siglo XIX: la invención de George Dantzig del algoritmo simplex para programación lineal (un caso especial de optimización matemática) en 1946 ha permitido determinar soluciones factibles a problemas que contienen cientos de variables.

Durante los años 1980 y 1990, se desarrolló la incorporación de restricciones en un lenguaje de programación . El primer lenguaje ideado expresamente con soporte intrínseco para la programación con restricciones fue Prolog . Desde entonces, se han puesto a disposición bibliotecas de programación con restricciones en otros lenguajes, como C++ o Java (por ejemplo, Choco para Java ^[2] ).

Tal como se definieron originalmente en la inteligencia artificial, las restricciones enumeran los posibles valores que un conjunto de variables puede tomar en un mundo dado. Un mundo posible es una asignación total de valores a las variables que representan una forma en que el mundo (real o imaginario) podría ser. ^[3] De manera informal, un dominio finito es un conjunto finito de elementos arbitrarios. Un problema de satisfacción de restricciones en dicho dominio contiene un conjunto de variables cuyos valores solo pueden tomarse del dominio y un conjunto de restricciones, cada restricción especificando los valores permitidos para un grupo de variables. Una solución a este problema es una evaluación de las variables que satisface todas las restricciones. En otras palabras, una solución es una forma de asignar un valor a cada variable de tal manera que todas las restricciones sean satisfechas por estos valores.

En algunas circunstancias, pueden existir requisitos adicionales: uno puede estar interesado no solo en la solución (y en la forma más rápida o computacionalmente más eficiente de llegar a ella) sino también en cómo se llegó a ella; por ejemplo, uno puede querer la solución "más simple" ("más simple" en un sentido lógico, no computacional, que tiene que definirse con precisión). Este suele ser el caso en juegos de lógica como el Sudoku .

En la práctica, las restricciones suelen expresarse de forma compacta, en lugar de enumerar todos los valores de las variables que las satisfacen. Una de las restricciones más utilizadas es la (obvia) que establece que los valores de las variables afectadas deben ser todos diferentes.

Los problemas que pueden expresarse como problemas de satisfacción de restricciones son el rompecabezas de las ocho reinas , el problema de resolución de sudoku y muchos otros problemas lógicos, el problema de satisfacibilidad booleana , los problemas de programación , los problemas de estimación de error acotado y varios problemas en gráficos como el problema de coloración de gráficos .

Aunque no suelen incluirse en la definición anterior de un problema de satisfacción de restricciones, las ecuaciones aritméticas y las desigualdades limitan los valores de las variables que contienen y, por lo tanto, pueden considerarse una forma de restricción. Su dominio es el conjunto de números (ya sea entero, racional o real), que es infinito: por lo tanto, las relaciones de estas restricciones también pueden ser infinitas; por ejemplo, tiene un número infinito de pares de valores satisfactorios. Las ecuaciones aritméticas y las desigualdades a menudo no se consideran dentro de la definición de un "problema de satisfacción de restricciones", que se limita a dominios finitos. Sin embargo, se utilizan a menudo en la programación de restricciones .${\displaystyle X=Y+1}$

Se puede demostrar que las desigualdades o ecuaciones aritméticas presentes en algunos tipos de acertijos de lógica finita como Futoshiki o Kakuro (también conocidos como sumas cruzadas) se pueden tratar como restricciones no aritméticas (ver Satisfacción de restricciones basada en patrones y acertijos lógicos ^[4] ).

Los problemas de satisfacción de restricciones en dominios finitos se resuelven normalmente utilizando una forma de búsqueda . Las técnicas más utilizadas son variantes de retroceso , propagación de restricciones y búsqueda local . Estas técnicas se utilizan en problemas con restricciones no lineales .

La eliminación de variables y el algoritmo símplex se utilizan para resolver ecuaciones e inecuaciones lineales y polinómicas , y problemas que contienen variables con dominio infinito. Estos suelen resolverse como problemas de optimización en los que la función optimizada es el número de restricciones violadas.

La solución de un problema de satisfacción de restricciones en un dominio finito es un problema NP-completo con respecto al tamaño del dominio. Las investigaciones han mostrado una serie de subcasos manejables , algunos de los cuales limitan las relaciones de restricción permitidas, otros requieren que los alcances de las restricciones formen un árbol, posiblemente en una versión reformulada del problema. Las investigaciones también han establecido relaciones del problema de satisfacción de restricciones con problemas en otras áreas, como la teoría de modelos finitos .

La programación con restricciones es el uso de restricciones como lenguaje de programación para codificar y resolver problemas. Esto se hace a menudo incorporando restricciones en un lenguaje de programación , que se denomina lenguaje anfitrión. La programación con restricciones se originó a partir de una formalización de igualdades de términos en Prolog II , lo que dio lugar a un marco general para incorporar restricciones en un lenguaje de programación lógica . Los lenguajes anfitriones más comunes son Prolog , C++ y Java , pero también se han utilizado otros lenguajes.

Un programa de lógica de restricciones es un programa lógico que contiene restricciones en los cuerpos de las cláusulas. Como ejemplo, la cláusula A(X):-X>0,B(X)es una cláusula que contiene la restricción X>0en el cuerpo. Las restricciones también pueden estar presentes en el objetivo. Las restricciones en el objetivo y en las cláusulas utilizadas para probar el objetivo se acumulan en un conjunto llamado almacén de restricciones . Este conjunto contiene las restricciones que el intérprete ha asumido como satisfacibles para continuar en la evaluación. Como resultado, si se detecta que este conjunto no es satisfacible, el intérprete retrocede. Las ecuaciones de términos, tal como se utilizan en la programación lógica, se consideran una forma particular de restricciones, que se pueden simplificar utilizando la unificación . Como resultado, el almacén de restricciones puede considerarse una extensión del concepto de sustitución que se utiliza en la programación lógica regular. Los tipos de restricciones más comunes utilizados en la programación lógica de restricciones son las restricciones sobre números enteros/racionales/reales y las restricciones sobre dominios finitos.

También se han desarrollado lenguajes de programación de lógica de restricciones concurrentes . Se diferencian significativamente de la programación de lógica de restricciones no concurrente en que están destinados a programar procesos concurrentes que pueden no terminar. Las reglas de manejo de restricciones pueden considerarse una forma de programación de lógica de restricciones concurrente, pero también se utilizan a veces dentro de un lenguaje de programación de lógica de restricciones no concurrente. Permiten reescribir restricciones o inferir otras nuevas en función de la veracidad de las condiciones.

Los kits de herramientas de satisfacción de restricciones son bibliotecas de software para lenguajes de programación imperativos que se utilizan para codificar y resolver un problema de satisfacción de restricciones.

• Solucionador de restricciones Cassowary , un proyecto de código abierto para la satisfacción de restricciones (accesible desde C, Java, Python y otros lenguajes).
• Comet, un lenguaje de programación y un conjunto de herramientas comerciales
• Gecode , un kit de herramientas portátil de código abierto escrito en C++, desarrollado como una implementación de calidad de producción y altamente eficiente de un conjunto teórico completo.
• Gelisp, un contenedor portátil de código abierto de Gecode a Lisp . ^[5] http://gelisp.sourceforge.net/
• IBM ILOG CP Optimizer: bibliotecas C++, Python, Java, .NET (propietarias, gratuitas para uso académico). ^[6] Sucesor de ILOG Solver/Scheduler, considerado líder del mercado en software de programación de restricciones comerciales en 2006 ^[7]
• JaCoP , un solucionador de restricciones de Java de código abierto.
• Koalog, un solucionador de restricciones comercial basado en Java.
• logilab-constraint, un solucionador de restricciones de código abierto escrito en Python puro con algoritmos de propagación de restricciones.
• Minion , un solucionador de restricciones de código abierto escrito en C++, con un lenguaje pequeño con el propósito de especificar modelos/problemas.
• ZDC, un programa de código abierto desarrollado en el Proyecto de Satisfacción de Restricciones Asistida por Computadora para modelar y resolver problemas de satisfacción de restricciones.

Los conjuntos de herramientas de restricciones son una forma de incorporar restricciones en un lenguaje de programación imperativo . Sin embargo, solo se utilizan como bibliotecas externas para codificar y resolver problemas. En el lenguaje de programación Kaleidoscope se adopta un enfoque en el que las restricciones se integran en un lenguaje de programación imperativo .

También se han incorporado restricciones a los lenguajes de programación funcional .

• Problema de satisfacción de restricciones
• Restricción (matemáticas)
• Solución candidata
• Problema de satisfacibilidad booleana
• Teoría de la decisión
• Teorías de satisfacibilidad módulo
• Configuración basada en conocimiento

• Tutorial de CSP

• Conferencia sobre satisfacción de las restricciones a cargo del Dr. Madhu Sharma (3:47)
• Introducción a los problemas de satisfacción de restricciones por Edward Tsang (7:34)
• Problemas de satisfacción de restricciones por Wheeler Ruml (9:18)
• Conferencia sobre problemas de satisfacción de restricciones a cargo del Instituto Indio de Tecnología de Madrás (51:59)
• Conferencia sobre los CSP (1:16:39)
• Conferencia sobre problemas de satisfacción de restricciones a cargo de Berkeley AI (1:17:38)
• Curso de posgrado en IA 5: Satisfacción de restricciones por el profesor Mausam (1:34:29)