Inteligencia Artificial 2.3 Problemas de Satisfacción de Restricciones

Inteligencia ArtificialInteligencia Artificial

2.3 Problemas de Satisfacción 2.3 Problemas de Satisfacción de Restriccionesde Restricciones

IntroducciónIntroducción

Anteriormente se vio que los problemas pueden Anteriormente se vio que los problemas pueden resolverse buscando en un espacio de resolverse buscando en un espacio de estadosestados..Estos estados pueden evaluarse por heurísticas Estos estados pueden evaluarse por heurísticas específicas para el dominio y probados para específicas para el dominio y probados para verificar si son estados meta.verificar si son estados meta.Desde el punto de vista del algoritmo de Desde el punto de vista del algoritmo de búsqueda, cada estado es una búsqueda, cada estado es una caja negracaja negra sin sin estructura interna discernible.estructura interna discernible.Solo es accesada por las Solo es accesada por las rutinasrutinas específicas específicas del del problema (la función de sucesor, la función problema (la función de sucesor, la función heurística y la prueba de meta).heurística y la prueba de meta).


En los En los problemas de satisfacción de problemas de satisfacción de restricciones (PSR)restricciones (PSR), los estados y la prueba de , los estados y la prueba de meta siguen a una meta siguen a una representaciónrepresentación estándar, estándar, estructurada y muy simple.estructurada y muy simple.

Los algoritmos de búsqueda pueden ser Los algoritmos de búsqueda pueden ser definidos de tal manera que tomen ventaja de la definidos de tal manera que tomen ventaja de la estructura de los estados y usen heurísticas de estructura de los estados y usen heurísticas de propósito generalpropósito general en vez de en vez de específicas del específicas del problemaproblema, para permitir la solución de , para permitir la solución de problemas grandes.problemas grandes.


Tal vez lo más importante es que la Tal vez lo más importante es que la representación estándar de la prueba de representación estándar de la prueba de meta revela la estructura del problema meta revela la estructura del problema mismo.mismo.Esto lleva a los métodos para Esto lleva a los métodos para descomposición de problemas y a un descomposición de problemas y a un entendimiento de la conexión íntima entre entendimiento de la conexión íntima entre la estructura del problema y la dificultad la estructura del problema y la dificultad para resolverlo.para resolverlo.

Problemas de Satisfacción de Problemas de Satisfacción de RestriccionesRestricciones

Un Un problema de satisfacción de restriccionesproblema de satisfacción de restricciones (o PSR) se define por un conjunto de (o PSR) se define por un conjunto de variablesvariables, , XX11, , XX22, …, , …, XXnn, y un conjunto de , y un conjunto de restriccionesrestricciones, ,

CC11, , CC22, …, , …, CCmm..

Cada variable Cada variable XXii tiene un tiene un dominiodominio no vacío no vacío DDii

de posibles de posibles valoresvalores..

Cada restricción Cada restricción CCii involucra algún subconjunto involucra algún subconjunto

de las variables y especifica las combinaciones de las variables y especifica las combinaciones permisibles de valores de ese subconjunto.permisibles de valores de ese subconjunto.


Un estado del problema se define por una Un estado del problema se define por una asignaciónasignación de valores a alguna o todas las de valores a alguna o todas las variables, {variables, {XXii = = vvii, , XXjj = = vvjj, …}., …}.

Una asignación que no viola ninguna restricción Una asignación que no viola ninguna restricción es llamada es llamada consistenteconsistente o legal. o legal.

Una asignación completa es una en la cual cada Una asignación completa es una en la cual cada variable es mencionada.variable es mencionada.

Una Una soluciónsolución a un PSR es una asignación a un PSR es una asignación completa que satisface todas las restricciones.completa que satisface todas las restricciones.


Problema: Colorear el Problema: Colorear el mapa de Australia, mapa de Australia, usando los colores usando los colores rojo, verde o azul, de rojo, verde o azul, de tal forma que dos tal forma que dos regiones vecinas no regiones vecinas no tengan el mismo tengan el mismo color.color.

Australiadel

Oeste

Territoriodel

Norte

Australiadel Sur

Queensland

Nueva Galesdel Sur

Victoria

Tasmania


Formulación como PSR:Formulación como PSR:– Variables: las regiones de AustraliaVariables: las regiones de Australia

AOAO (Australia del Oeste) (Australia del Oeste)

TNTN (Territorio del Norte) (Territorio del Norte)

QQ (Queensland) (Queensland)

NGSNGS (Nueva Gales del Sur) (Nueva Gales del Sur)

VV (Victoria) (Victoria)

ASAS (Australia del Sur) (Australia del Sur)

TT (Tasmania) (Tasmania)


Formulación como PSR:Formulación como PSR:– Dominios: El dominio de cada variable es el conjunto Dominios: El dominio de cada variable es el conjunto

{{rojo, verde, azulrojo, verde, azul}.}.– Restricciones: Las restricciones requieren que Restricciones: Las restricciones requieren que

regiones vecinas tengan distintos colores. Por regiones vecinas tengan distintos colores. Por ejemplo, las combinaciones permisibles para ejemplo, las combinaciones permisibles para AO AO yy TN TN son los pares:son los pares:

{({(rojo, verderojo, verde), (), (rojorojo, , azulazul), (), (verdeverde, , rojorojo), (), (verdeverde, , azulazul), ), ((azulazul, , rojorojo), (azul, ), (azul, verdeverde)})}

– Esta restricción puede representarse como Esta restricción puede representarse como AO AO TN. TN.


Formulación como PSR:Formulación como PSR:– Solución: Hay muchas soluciones posibles, Solución: Hay muchas soluciones posibles,

comocomo

{{AO = rojo, TN = verde, Q = rojo, NGS = verde, AO = rojo, TN = verde, Q = rojo, NGS = verde, V = rojo, AS = azul, T = rojoV = rojo, AS = azul, T = rojo}}


Es útil visualizar un Es útil visualizar un PSR como un PSR como un grafo grafo de restriccionesde restricciones. .

Los nodos del grafo Los nodos del grafo corresponden a las corresponden a las variables del variables del problema, y los arcos problema, y los arcos corresponden a las corresponden a las restricciones.restricciones.

AO

TN

AS

Q

NGS

V

T


Es útil visualizar un Es útil visualizar un PSR como un PSR como un grafo grafo de restriccionesde restricciones. .

Los nodos del grafo Los nodos del grafo corresponden a las corresponden a las variables del variables del problema, y los arcos problema, y los arcos corresponden a las corresponden a las restricciones.restricciones.

AO

TN

AS

Q

NGS

V

T


Tratar un problema como un PSR tiene Tratar un problema como un PSR tiene importantes beneficios:importantes beneficios:– La representación de estados en un PSR sigue un La representación de estados en un PSR sigue un

patrón estándar (un conjunto de variables con valores patrón estándar (un conjunto de variables con valores asignados), por lo que la función de sucesor y la asignados), por lo que la función de sucesor y la prueba de meta pueden ser escritos de una manera prueba de meta pueden ser escritos de una manera genérica que se aplica a todos los PSR.genérica que se aplica a todos los PSR.

– Se pueden desarrollar heurísticas efectivas que no Se pueden desarrollar heurísticas efectivas que no requieren experiencia adicional específica del requieren experiencia adicional específica del dominio.dominio.

– La estructura del grafo de restricciones puede usarse La estructura del grafo de restricciones puede usarse para simplificar el proceso de solución en algunos para simplificar el proceso de solución en algunos casos, dando una reducción exponencial en casos, dando una reducción exponencial en complejidad.complejidad.


A un PSR se le puede hacer una A un PSR se le puede hacer una formulación formulación incrementalincremental como un problema de búsqueda como un problema de búsqueda estándar de la siguiente manera:estándar de la siguiente manera:– Estado inicialEstado inicial: La asignación vacía { }, en la cual : La asignación vacía { }, en la cual

todas las variables están sin asignar.todas las variables están sin asignar.– Función de sucesorFunción de sucesor: Un valor puede ser asignado a : Un valor puede ser asignado a

una variable sin asignar, siempre y cuando no entre una variable sin asignar, siempre y cuando no entre en conflicto con variables previamente asignadas.en conflicto con variables previamente asignadas.

– Prueba de meta: Prueba de meta: La asignación actual está completa.La asignación actual está completa.– Costo de rutaCosto de ruta: Un costo constante (por ejemplo, 1) : Un costo constante (por ejemplo, 1)

para cada paso.para cada paso.


Cada solución debe ser una asignación completa y Cada solución debe ser una asignación completa y por lo tanto tiene una profundidad por lo tanto tiene una profundidad nn si hay si hay nn variables.variables.Por esta razón, los algoritmos de búsqueda primero Por esta razón, los algoritmos de búsqueda primero en profundidad son populares para los PSR.en profundidad son populares para los PSR.También ocurre que También ocurre que la ruta por la cual se alcanza la ruta por la cual se alcanza una solución es irrelevanteuna solución es irrelevante. Por lo tanto, también se . Por lo tanto, también se puede usar una puede usar una formulación de estado completoformulación de estado completo, , en la cual cada estado es una asignación completa en la cual cada estado es una asignación completa que puede satisfacer o no las restricciones. Los que puede satisfacer o no las restricciones. Los métodos de búsqueda local trabajan bien con esta métodos de búsqueda local trabajan bien con esta formulación.formulación.


El tipo más simple de PSR involucra variables que El tipo más simple de PSR involucra variables que son son discretasdiscretas y tienen y tienen dominios finitosdominios finitos..Los problemas de coloreo de mapas son de este Los problemas de coloreo de mapas son de este tipo. Incluso el problema de las 8 reinas puede tipo. Incluso el problema de las 8 reinas puede plantearse como PSR:plantearse como PSR:– Variables: Variables: QQ11, …, Q, …, Q88 (Posiciones de cada reina en las (Posiciones de cada reina en las

columnas 1, …, 8).columnas 1, …, 8).– Dominios: Cada variable tiene el dominio {1, 2, 3, 4, 5, 6, Dominios: Cada variable tiene el dominio {1, 2, 3, 4, 5, 6,

7, 8}.7, 8}.

Los PSR de dominios finitos incluyen a los Los PSR de dominios finitos incluyen a los PSR PSR booleanosbooleanos, cuyas variables son , cuyas variables son verdadero verdadero o o falso.falso.


Las variables discretas pueden también tener Las variables discretas pueden también tener dominios infinitosdominios infinitos, por ejemplo, el conjunto de los , por ejemplo, el conjunto de los números enteros, o el conjunto de todas las números enteros, o el conjunto de todas las cadenas de caracteres.cadenas de caracteres.Por ejemplo, cuando se requieren programar Por ejemplo, cuando se requieren programar trabajos de construcción en el calendario, la fecha trabajos de construcción en el calendario, la fecha de inicio de cada trabajo es una variable, y sus de inicio de cada trabajo es una variable, y sus valores posibles es el número de días enteros a valores posibles es el número de días enteros a partir de la fecha actual.partir de la fecha actual.Con dominios infinitos, ya no es posible describir las Con dominios infinitos, ya no es posible describir las restricciones enumerando todas las combinaciones restricciones enumerando todas las combinaciones de valores permisibles.de valores permisibles.


Con dominios infinitos, se debe usar entonces un Con dominios infinitos, se debe usar entonces un lenguaje de restriccioneslenguaje de restricciones..

Por ejemplo, si Por ejemplo, si TrabajoTrabajo11 toma 5 días, y debe preceder toma 5 días, y debe preceder a a TrabajoTrabajo33, entonces necesitaríamos un lenguaje de , entonces necesitaríamos un lenguaje de restricciones de desigualdades algebraicas tal como restricciones de desigualdades algebraicas tal como

InicioTrabajoInicioTrabajo11 + 5 + 5 InicioTrabajoInicioTrabajo33

Existen algoritmos de solución especiales para las Existen algoritmos de solución especiales para las restricciones linealesrestricciones lineales de variables enteras de variables enteras (restricciones como la anterior, en la que cada (restricciones como la anterior, en la que cada variable aparece sólo en forma lineal).variable aparece sólo en forma lineal).


Puede demostrarse que no existe un algoritmo para Puede demostrarse que no existe un algoritmo para resolver resolver restricciones no linealesrestricciones no lineales generales sobre generales sobre variables enteras.variables enteras.En algunos casos, se puede reducir los problemas de En algunos casos, se puede reducir los problemas de restricciones enteras a problemas de dominio finito restricciones enteras a problemas de dominio finito simplemente acotando los valores de todas las simplemente acotando los valores de todas las variables. Ejemplo: poniendo una cota superior igual a variables. Ejemplo: poniendo una cota superior igual a la de duración total de todos los trabajos a ser la de duración total de todos los trabajos a ser programados.programados.


Los PSR con Los PSR con dominios continuos dominios continuos son muy comunes en son muy comunes en el mundo real y son ampliamente estudiados en el campo el mundo real y son ampliamente estudiados en el campo de la investigación de operaciones. Por ejemplo, la de la investigación de operaciones. Por ejemplo, la programación de experimentos en el Telescopio Espacial programación de experimentos en el Telescopio Espacial Hubble, que requiere una medición muy precisa del tiempo Hubble, que requiere una medición muy precisa del tiempo para las observaciones, para el inicio y fin de cada para las observaciones, para el inicio y fin de cada observación, y el manejo de variables continuas que deben observación, y el manejo de variables continuas que deben obedecer una variedad de restricciones astronómicas, de obedecer una variedad de restricciones astronómicas, de precedencia y de energía.precedencia y de energía.La categoría mejor conocida de PSR de dominio continuo La categoría mejor conocida de PSR de dominio continuo es la de los problemas de es la de los problemas de programación linealprogramación lineal, donde las , donde las restricciones deben ser desigualdades lineales formando restricciones deben ser desigualdades lineales formando una región una región convexaconvexa..


Los problemas de programación lineal pueden ser Los problemas de programación lineal pueden ser resueltos en tiempo polinomial en el número de variables. resueltos en tiempo polinomial en el número de variables. También se han estudiado otros problemas con diferentes También se han estudiado otros problemas con diferentes tipos de restricciones y funciones objetivo (programación tipos de restricciones y funciones objetivo (programación cuadrática, programación cónica de segundo orden, etc.)cuadrática, programación cónica de segundo orden, etc.)


Los tipos de restricciones que se pueden tener son:Los tipos de restricciones que se pueden tener son:– Restricciones unarias: restringen el valor de una sola Restricciones unarias: restringen el valor de una sola

variable.variable.Ejemplo: A la gente de Australia del Sur no le gusta el color Ejemplo: A la gente de Australia del Sur no le gusta el color verdeverde. . AS AS verdeverdeCada restricción unaria puede eliminarse simplemente Cada restricción unaria puede eliminarse simplemente preprocesando el dominio de la variable correspondiente para preprocesando el dominio de la variable correspondiente para eliminar cualquier valor que viole la restricción.eliminar cualquier valor que viole la restricción.

– Restricciones binarias: relacionan dos variables.Restricciones binarias: relacionan dos variables.Ejemplo: Australia del Sur y Nueva Gales del Sur no pueden Ejemplo: Australia del Sur y Nueva Gales del Sur no pueden tener el mismo color. tener el mismo color. ASAS NGSNGS

Un PSR binario es uno que tiene sólo restricciones Un PSR binario es uno que tiene sólo restricciones binarias, y se puede representar con un grafo de binarias, y se puede representar con un grafo de restricciones.restricciones.


Las restricciones de alto orden involucran tres o más Las restricciones de alto orden involucran tres o más variables. Un ejemplo familiar de esto lo representan variables. Un ejemplo familiar de esto lo representan los problemas de los problemas de criptoaritméticacriptoaritmética..

T W O+ T W OF O U R


El hecho de que cada letra representa un dígito diferente se El hecho de que cada letra representa un dígito diferente se puede representar mediante una restricción de seis variables: puede representar mediante una restricción de seis variables: TodasDif TodasDif ((F, T, U, W, R, OF, T, U, W, R, O), o puede ser representado por la ), o puede ser representado por la colección de restricciones binarias {colección de restricciones binarias {FF T, FT, F UU, …, , …, RR OO}.}.Las restricciones de adición de las cuatro columnas también Las restricciones de adición de las cuatro columnas también involucran varias variables:involucran varias variables:

O + O = R + O + O = R + 1010 X X11

XX11 + W + W = U + + W + W = U + 1010 X X22

XX22 + T + T = O + + T + T = O + 1010 X X33

XX33 = = FF

XX11,, XX22 y y XX33 son son variables auxiliaresvariables auxiliares que representan el dígito que representan el dígito (0 o 1) acarreado a la siguiente columna.(0 o 1) acarreado a la siguiente columna.


Las restricciones de alto orden se pueden representar en Las restricciones de alto orden se pueden representar en un un hipergrafo de restriccioneshipergrafo de restricciones::

F T U W R O

X3 X2 X1


Cada restricción de alto orden, con dominio finito, puede Cada restricción de alto orden, con dominio finito, puede reducirse a un conjunto de restricciones binarias, si se reducirse a un conjunto de restricciones binarias, si se introducen las variables auxiliares suficientes. Es por eso introducen las variables auxiliares suficientes. Es por eso que se estudian preferentemente problemas sólo con que se estudian preferentemente problemas sólo con restriccines binarias.restriccines binarias.Hasta ahora se han descrito sólo restricciones Hasta ahora se han descrito sólo restricciones absolutasabsolutas (cualquier asignación completa que viole alguna de ellas, (cualquier asignación completa que viole alguna de ellas, se descarta como solución).se descarta como solución).Muchos PSR del mundo real incluyen restricciones de Muchos PSR del mundo real incluyen restricciones de preferenciapreferencia, indicando cuales soluciones son preferibles. , indicando cuales soluciones son preferibles. Estas restricciones pueden ser codificadas como costos Estas restricciones pueden ser codificadas como costos sobre las asignaciones de variables individuales.sobre las asignaciones de variables individuales.

Búsqueda Búsqueda backtracking backtracking para los para los PSRPSR

Usando la formulación antes mencionada para Usando la formulación antes mencionada para PSR, cualquier algoritmo de búsqueda visto PSR, cualquier algoritmo de búsqueda visto anteriormente puede ser usado para resolverlos.anteriormente puede ser usado para resolverlos.

Suponiendo que se usa búsqueda primero por Suponiendo que se usa búsqueda primero por amplitud, el factor de ramificación en el nivel amplitud, el factor de ramificación en el nivel superior es superior es ndnd, en el siguiente nivel es (, en el siguiente nivel es (nn – 1) – 1)dd, , y así sucesivamente para los y así sucesivamente para los nn niveles. Se niveles. Se genera un árbol de genera un árbol de nn!!ddnn hojas. hojas.


Sin embargo, todos los PSR tienen la propiedad Sin embargo, todos los PSR tienen la propiedad de la de la conmutatividadconmutatividad. .

Un problema es conmutativo si el orden de Un problema es conmutativo si el orden de aplicación de cualquier conjunto dado de aplicación de cualquier conjunto dado de acciones no tiene efecto en la salida.acciones no tiene efecto en la salida.

Por lo tanto, Por lo tanto, todos los algoritmos de búsqueda todos los algoritmos de búsqueda en PSR generan sucesores considerando las en PSR generan sucesores considerando las posibles asignaciones para sólo una variable en posibles asignaciones para sólo una variable en cada nodo del árbol de búsqueda.cada nodo del árbol de búsqueda.


La La búsqueda backtrackingbúsqueda backtracking es una es una búsqueda primero en profundidad que búsqueda primero en profundidad que elige valores para una variable a la vez y elige valores para una variable a la vez y “regresa” (““regresa” (“backtraksbacktraks”) cuando a una ”) cuando a una variable no le quedan valores legales para variable no le quedan valores legales para asignarle.asignarle.


AO = rojo AO = verde AO = azul

AO = rojoTN = verde

AO = rojoTN = azul

AO = rojoTN = verde

Q = rojo

AO = rojoTN = verde

Q = rojo


La La búsqueda backtrackingbúsqueda backtracking simple es un simple es un algoritmo no informado, asi que no se algoritmo no informado, asi que no se espera que sea efectivo para problemas espera que sea efectivo para problemas grandes.grandes.

Búsqueda Búsqueda backtracking backtracking para los para los PSRPSRProblemaProblema Back-Back-

TrackingTracking

BT+MVRBT+MVR Forward Forward CheckingChecking

FC+FC+

MVRMVR

Conflictos Conflictos Min.Min.

USAUSA (>1,000K)(>1,000K) (>1,000K)(>1,000K) 2K2K 6060 6464

n-Reinasn-Reinas (>40,000K)(>40,000K) 13,500K13,500K (>40,000K(>40,000K))

817K817K 4K4K

CebraCebra 3,859K3,859K 1K1K 35K35K 0.5K0.5K 2K2K

Aleatorio Aleatorio 11

415K415K 3K3K 26K26K 2K2K

Aleatorio Aleatorio 22

942K942K 27K27K 77K77K 15K15K

K = miles de chequeos de consistencia, ( ) = no halló solución


Los métodos de propósito general se hacen las Los métodos de propósito general se hacen las siguientes preguntas:siguientes preguntas:– ¿Qué variable debe asignarse en seguida, y en que ¿Qué variable debe asignarse en seguida, y en que

orden deben intentarse los valores?orden deben intentarse los valores?– ¿Cuáles son las implicaciones de las asignaciones ¿Cuáles son las implicaciones de las asignaciones

actuales de variables para las otras variables sin actuales de variables para las otras variables sin asignar?asignar?

– Cuando una ruta falla (es decir, un estado es Cuando una ruta falla (es decir, un estado es alcanzado en el cual una variable no tiene valores alcanzado en el cual una variable no tiene valores legales) ¿Puede la búsqueda evitar repetir esta falla legales) ¿Puede la búsqueda evitar repetir esta falla en rutas subsecuentes?en rutas subsecuentes?


Orden de las variables y de los valoresOrden de las variables y de los valores– Por default, la siguiente variable a asignar se Por default, la siguiente variable a asignar se

selecciona de una lista estática de variables que rara selecciona de una lista estática de variables que rara vez produce una búsqueda eficiente.vez produce una búsqueda eficiente.

– La idea intuitiva de elegir la variable que tenga el La idea intuitiva de elegir la variable que tenga el mínimo de valores legales es llamada la heurística mínimo de valores legales es llamada la heurística del del mínimo de valores remanentesmínimo de valores remanentes (MVR). (MVR). También se le llama la de la “variable más También se le llama la de la “variable más restringida” o de “falla-primero”, porque selecciona la restringida” o de “falla-primero”, porque selecciona la variable que probablemente pronto causará una falla, variable que probablemente pronto causará una falla, podando el árbol de búsqueda.podando el árbol de búsqueda.


Orden de las variables y de los valoresOrden de las variables y de los valores– La heurística MVR no ayuda en absoluto para elegir La heurística MVR no ayuda en absoluto para elegir

la primera region a colorear del mapa de Australia, la primera region a colorear del mapa de Australia, porque inicialmente cada región tiene tres colores porque inicialmente cada región tiene tres colores legales.legales.

– En este caso, la En este caso, la heurística de gradoheurística de grado es utilizada. es utilizada. Intenta reducir el factor de ramificación para Intenta reducir el factor de ramificación para elecciones futuras seleccionando la variable que está elecciones futuras seleccionando la variable que está involucrada en el mayor número de restricciones. involucrada en el mayor número de restricciones. ASAS tiene grado 5, las otras tiene 2 o 3, y tiene grado 5, las otras tiene 2 o 3, y TT tiene 0. tiene 0.

– La heurística de MVR es una guía más poderosa, La heurística de MVR es una guía más poderosa, pero la heurística de grado puede ser muy útil para pero la heurística de grado puede ser muy útil para romper empates.romper empates.


Orden de las variables y de los valoresOrden de las variables y de los valores– Una vez que una variable ha sido seleccionada, el algoritmo Una vez que una variable ha sido seleccionada, el algoritmo

debe decidir en qué orden examinar sus valoresdebe decidir en qué orden examinar sus valores..– Para esto, la heurística del Para esto, la heurística del valor menos restrictivovalor menos restrictivo puede ser puede ser

efectiva en algunos casos.efectiva en algunos casos.– Esta heurística prefiere el valor que elimine la menor cantidad Esta heurística prefiere el valor que elimine la menor cantidad

de valores posibles de las variables vecinas en el grafo de de valores posibles de las variables vecinas en el grafo de restricciones.restricciones.

– Por ejemplo, si se ha asignado Por ejemplo, si se ha asignado AO=rojo, TN=verde, AO=rojo, TN=verde, y se tiene y se tiene que elegir que elegir QQ. Si se elige azul, esto elimina el último valor legal . Si se elige azul, esto elimina el último valor legal que podíamos asignarle a que podíamos asignarle a ASAS. Por lo tanto, según la heurística . Por lo tanto, según la heurística del valor menos restrictivo, se debe asignar del valor menos restrictivo, se debe asignar QQ==rojorojo. .

– La idea es contar siempre con la mayor flexibilidad posible para La idea es contar siempre con la mayor flexibilidad posible para las asignaciones de variables subsecuentes.las asignaciones de variables subsecuentes.


Propagando información a través de las Propagando información a través de las restriccionesrestricciones– Hasta ahora solo se han considerado las Hasta ahora solo se han considerado las

restricciones sobre una variable solo cuando restricciones sobre una variable solo cuando la variable se elige para asignarle valor. la variable se elige para asignarle valor.

– Observando algunas restricciones un poco Observando algunas restricciones un poco antes durante la búsqueda, o incluso antes de antes durante la búsqueda, o incluso antes de que la búsqueda comience, se puede reducir que la búsqueda comience, se puede reducir drásticamente el espacio de búsqueda.drásticamente el espacio de búsqueda.


Propagando información a través de las Propagando información a través de las restriccionesrestricciones– Forward checkingForward checking

Cuando una variable Cuando una variable XX es asignada, el proceso FC es asignada, el proceso FC observa a cada variable sin asignar observa a cada variable sin asignar YY que esté que esté conectada a conectada a XX por una restricción y borra del por una restricción y borra del dominio de dominio de YY cualquier valor que sea inconsistente cualquier valor que sea inconsistente con el valor elegido para con el valor elegido para XX..


Propagando información a través de las Propagando información a través de las restriccionesrestricciones– Forward checkingForward checking

AOAO TNTN QQ NGSNGS VV ASAS TTDominios Dominios InicialesIniciales RVARVA RVARVA RVARVA RVARVA RVARVA RVARVA RVARVA

Después Después que que

AO=rojoAO=rojo

R R

VAVA RVARVA RVARVA RVARVA VAVA RVARVA


Q=verdeQ=verdeRR AA VV R AR A RVARVA AA RVARVA


V=azulV=azulRR AA VV R R AA ------ RVARVA


Propagando información a través de las Propagando información a través de las restriccionesrestricciones– Propagación de restriccionesPropagación de restricciones

Aunque FC detecta muchas inconsistencias, no las detecta Aunque FC detecta muchas inconsistencias, no las detecta todas.todas.En la tabla anterior, puede verse que cuando En la tabla anterior, puede verse que cuando AO AO es es rojorojo y y Q Q es verde, tanto es verde, tanto TNTN como como ASAS son forzados a ser azules. Sin son forzados a ser azules. Sin embargo, estos dos últimos son adyacentes y por lo tanto, embargo, estos dos últimos son adyacentes y por lo tanto, no pueden tener el mismo color. FC no detecta esto como no pueden tener el mismo color. FC no detecta esto como una inconsistencia, porque no mira más allá.una inconsistencia, porque no mira más allá.La La propagación de restriccionespropagación de restricciones es el término general es el término general para propagar las implicaciones de una restricción sobre una para propagar las implicaciones de una restricción sobre una variable en otras variables.variable en otras variables.



La idea de La idea de consistencia de arco consistencia de arco proporciona un método proporciona un método rápido de propagación de restricciones que es rápido de propagación de restricciones que es sustancialmente más fuerte que FC.sustancialmente más fuerte que FC.““Arco” se refiere al arco Arco” se refiere al arco dirigidodirigido en el grafo de restricciones, en el grafo de restricciones, por ejemplo, el arco que va de por ejemplo, el arco que va de ASAS a a NGSNGS..Dados los dominios actuales de Dados los dominios actuales de ASAS y y NGSNGS, el arco es , el arco es consistente si, para consistente si, para cada cada valor valor xx de de ASAS, hay , hay algúnalgún valor valor yy de de NGSNGS que sea consistente con que sea consistente con xx..En el renglón 3 de la tabla, se puede ver que el arco de En el renglón 3 de la tabla, se puede ver que el arco de ASAS a a NGSNGS es consistente, pero el arco inverso de es consistente, pero el arco inverso de NGSNGS a a ASAS no lo no lo es. Este arco puede hacerse consistente borrando el valor es. Este arco puede hacerse consistente borrando el valor azulazul del dominio de del dominio de NGSNGS..



La verificación de consistencia de arco puede ser aplicada La verificación de consistencia de arco puede ser aplicada tanto como un paso de preprocesamiento antes de empezar tanto como un paso de preprocesamiento antes de empezar la búsqueda, o como un paso de propagación (como FC) la búsqueda, o como un paso de propagación (como FC) después de cada asignación durante la búsqueda.después de cada asignación durante la búsqueda.En cualquiera de los dos casos, el proceso debe ser En cualquiera de los dos casos, el proceso debe ser aplicado aplicado repetidamenterepetidamente hasta que no quede ninguna hasta que no quede ninguna inconsistencia, ya que la eliminacion de una de ellas puede inconsistencia, ya que la eliminacion de una de ellas puede crear otras nuevas.crear otras nuevas.El algoritmo completo para consistencia de arco es llamado El algoritmo completo para consistencia de arco es llamado AC-3.AC-3.



Formas más fuertes de propagación se pueden definir Formas más fuertes de propagación se pueden definir usando la notación llamada usando la notación llamada k-k-consistenciaconsistencia..Un PSR es Un PSR es k-k-consistente si, para cualquier conjunto de consistente si, para cualquier conjunto de kk-1 -1 variables y para cualquier asignación consistente a esas variables y para cualquier asignación consistente a esas variables, un valor consistente puede siempre ser asignado variables, un valor consistente puede siempre ser asignado a cualquier a cualquier kk-ésima variable.-ésima variable.Por lo tanto, 1-consistencia significa que cada variable Por lo tanto, 1-consistencia significa que cada variable individual es consistente por sí misma; esto es también individual es consistente por sí misma; esto es también llamado llamado consistencia de nodoconsistencia de nodo. 2-consistencia es lo mismo . 2-consistencia es lo mismo que consistencia de arco. 3-consistencia significa que que consistencia de arco. 3-consistencia significa que cualquier par de variables adyacentes puede siempre ser cualquier par de variables adyacentes puede siempre ser extendida a una tercera variable vecina, lo que se llama extendida a una tercera variable vecina, lo que se llama consistencia de rutaconsistencia de ruta..



Un grafo es Un grafo es fuertemente fuertemente k-k-consistenteconsistente si es si es k-k-consistente consistente y además es también (y además es también (k-k-1)-consistente, (1)-consistente, (kk-2)-consistente, … -2)-consistente, … y así hasta llegar a 1-consistente.y así hasta llegar a 1-consistente.

Si se tiene un problema con Si se tiene un problema con nn nodos, y se hace fuertemente nodos, y se hace fuertemente nn-consistente, entonces el problema se puede resolver sin -consistente, entonces el problema se puede resolver sin backtracking.backtracking.

Sin embargo, cualquier algoritmo para establecer la Sin embargo, cualquier algoritmo para establecer la nn--consistencia debe tomar tiempo exponencial en consistencia debe tomar tiempo exponencial en n n en el peor en el peor caso.caso.


Propagando información a través de las Propagando información a través de las restriccionesrestricciones– Manejo de restricciones especialesManejo de restricciones especiales

Ejemplo, la restricción Ejemplo, la restricción TodasDiferentesTodasDiferentes dice que dice que todas las variables involucradas deben tener todas las variables involucradas deben tener valores diferentes.valores diferentes.Una forma simple de detectar la inconsistencia de Una forma simple de detectar la inconsistencia de esta restricción es: si hay esta restricción es: si hay mm variables involucradas variables involucradas en la restricción, y si ellas tienen en la restricción, y si ellas tienen nn posibles posibles valores distintos cada una, y valores distintos cada una, y mm > > nn, entonces la , entonces la restricción no puede ser satisfecha.restricción no puede ser satisfecha.



Tal vez la restricción de alto orden más importante es la Tal vez la restricción de alto orden más importante es la restricción de recursos, restricción de recursos, algunas veces llamada restricción algunas veces llamada restricción cuandomuchocuandomucho..

Por ejemplo, sean Por ejemplo, sean PAPA11, …, , …, PAPA44 las cantidades de personal las cantidades de personal asignado a cada una de 4 tareas. La restricción de que no asignado a cada una de 4 tareas. La restricción de que no se asignen más de 10 personas en total se escribe como se asignen más de 10 personas en total se escribe como cuandomuchocuandomucho(10, (10, PAPA11, , PAPA22 PAPA33, , PAPA44).).

Una inconsistencia puede detectarse simplemente checando Una inconsistencia puede detectarse simplemente checando la suma de los valores mínimos de los dominios actuales. la suma de los valores mínimos de los dominios actuales. Por ejemplo, si cada variable tiene el dominio {3,4,5,6}, la Por ejemplo, si cada variable tiene el dominio {3,4,5,6}, la restricción restricción cuandomuchocuandomucho no puede ser satisfecha. no puede ser satisfecha.



Para problemas grandes limitados en recursos, como Para problemas grandes limitados en recursos, como problemas de logística involucrando miles de personas o problemas de logística involucrando miles de personas o cientos de vehículos, usualmente no es posible representar cientos de vehículos, usualmente no es posible representar el dominio de cada variable como un conjunto de enteros y el dominio de cada variable como un conjunto de enteros y reducirlo gradualmente con los métodos de verificación de reducirlo gradualmente con los métodos de verificación de consistencia.consistencia.

Lo que se hace en estos casos es representar los dominios Lo que se hace en estos casos es representar los dominios por medio de límites superiores e inferiores, y manejarlos por por medio de límites superiores e inferiores, y manejarlos por propagación de límitespropagación de límites..


Backtracking Backtracking inteligente: mirando hacia atrás.inteligente: mirando hacia atrás.– Cuando una rama de la búsqueda falla, el algoritmo Cuando una rama de la búsqueda falla, el algoritmo

de BT regresa a la variable precedente e intenta un de BT regresa a la variable precedente e intenta un nuevo valor para ella.nuevo valor para ella.

– Esto es llamado Esto es llamado Backtracking cronológicoBacktracking cronológico..– ¿Qué pasaría si en el problema de Australia se ¿Qué pasaría si en el problema de Australia se

hubiera elegido un orden de instanciación fijo hubiera elegido un orden de instanciación fijo Q, Q, NGS, V, T, AS, AO, TNNGS, V, T, AS, AO, TN? Supón que ya se ha ? Supón que ya se ha generado la asignación {generado la asignación {Q=rojo, NGS=verde, V=azul, Q=rojo, NGS=verde, V=azul, T=rojoT=rojo}. Cuando se intenta asignar la siguiente }. Cuando se intenta asignar la siguiente variable, variable, ASAS, todo falla. Regresar y cambiar el valor a , todo falla. Regresar y cambiar el valor a TT no soluciona el problema. no soluciona el problema.


Backtracking Backtracking inteligente: mirando hacia inteligente: mirando hacia atrás.atrás.– Un enfoque más inteligente que el BT es Un enfoque más inteligente que el BT es

regresar hasta una de las variables del regresar hasta una de las variables del conjunto que conjunto que causaron la fallacausaron la falla. Este conjunto . Este conjunto es llamado el es llamado el conjunto conflictoconjunto conflicto..

– El conjunto conflicto para la variable El conjunto conflicto para la variable XX es el es el conjunto de variables previamente asignadas conjunto de variables previamente asignadas que están conectadas a que están conectadas a XX por restricciones. por restricciones.

– El conjunto conflicto para El conjunto conflicto para AS AS es {es {Q,NGS,VQ,NGS,V}. }.


Backtracking Backtracking inteligente: mirando hacia atrás.inteligente: mirando hacia atrás.– El método El método backjumpingbackjumping regresa a la variable regresa a la variable mmás ás

recientereciente en el conjunto conflicto. En este caso, BJ en el conjunto conflicto. En este caso, BJ brincaría sobre Tasmania y buscaría un nuevo valor brincaría sobre Tasmania y buscaría un nuevo valor para para VV..

– El algoritmo FC puede crear el conjunto conflicto El algoritmo FC puede crear el conjunto conflicto mientras realiza su búsqueda (simplemente almacena mientras realiza su búsqueda (simplemente almacena lo que elimina).lo que elimina).

– BJ ocurre cuando cada valor en el dominio está en BJ ocurre cuando cada valor en el dominio está en conflicto con la asignación actual; FC detecta esto conflicto con la asignación actual; FC detecta esto antes y previene que la búsqueda llegue a un nodo antes y previene que la búsqueda llegue a un nodo así. Por lo tanto, casí. Por lo tanto, cada rama podada por BJ es ada rama podada por BJ es también podada por FC, así que son redundantes.también podada por FC, así que son redundantes.


Backtracking Backtracking inteligente: mirando hacia atrás.inteligente: mirando hacia atrás.– BJ nota la falla cuando el dominio de una cariable queda vacío, BJ nota la falla cuando el dominio de una cariable queda vacío,

pero en muchos casos una rama está perdida mucho antes de pero en muchos casos una rama está perdida mucho antes de que esto ocurra.que esto ocurra.

– Ejemplo, cuando se hace la asignación parcial {Ejemplo, cuando se hace la asignación parcial {AO=rojo, AO=rojo, NGS=rojoNGS=rojo}. Si se intenta }. Si se intenta T=rojoT=rojo, y luego se asignan , y luego se asignan TN, Q, V, TN, Q, V, ASAS, ninguna asignación funciona para estas últimas., ninguna asignación funciona para estas últimas.

– ¿A dónde hacer backtrack? BJ no puede funcionar, porque ¿A dónde hacer backtrack? BJ no puede funcionar, porque TNTN SÍ tiene valores consistentes con las variables asignadas SÍ tiene valores consistentes con las variables asignadas precedentes. precedentes. TNTN no tiene un conjunto conflicto completo. no tiene un conjunto conflicto completo.

– Esto lleva a una noción más profunda del conjunto conflicto: si el Esto lleva a una noción más profunda del conjunto conflicto: si el conjunto de variables precedentes que causaron conjunto de variables precedentes que causaron TNTN, , junto con junto con cualquier variable subsecuente, cualquier variable subsecuente, no tienen solución consistente.no tienen solución consistente.

– A este algoritmo se le llama A este algoritmo se le llama backjumping dirigido por backjumping dirigido por conflictosconflictos..

Búsqueda local para PSRBúsqueda local para PSR

Los algoritmos de búsqueda local son efectivos para Los algoritmos de búsqueda local son efectivos para resolver muchos PSR.resolver muchos PSR.Usan una formulación de estado completo: el estado Usan una formulación de estado completo: el estado inicial asigna un valor a cada variable, y la función inicial asigna un valor a cada variable, y la función sucesor usualmente trabaja cambiando el valor de una sucesor usualmente trabaja cambiando el valor de una variable a la vez.variable a la vez.El problema de las 8 reinas puede plantearse de dos El problema de las 8 reinas puede plantearse de dos formas:formas:– Poner las 8 reinas en las 8 columnas al azar, y mover luego Poner las 8 reinas en las 8 columnas al azar, y mover luego

cada reina a lo largo de su columna.cada reina a lo largo de su columna.– Poner las 8 reinas, una por columna en una permutación de las Poner las 8 reinas, una por columna en una permutación de las

8 columnas, y luego generar sucesores intercambiando dos 8 columnas, y luego generar sucesores intercambiando dos reinas de columna.reinas de columna.

Búsqueda local para PSRBúsqueda local para PSR

Para elegir un nuevo valor para una Para elegir un nuevo valor para una variable, la heurística más obvia es variable, la heurística más obvia es seleccionar el valor que resulte en el seleccionar el valor que resulte en el número mínimo de conflictos con otras número mínimo de conflictos con otras variables – la heurística de variables – la heurística de conflictos conflictos mínimosmínimos..

La estructura de los problemasLa estructura de los problemas

La única manera en la que podemos esperar tratar con La única manera en la que podemos esperar tratar con el mundo real es, posiblemente, descomponiéndolo en el mundo real es, posiblemente, descomponiéndolo en muchos subproblemas.muchos subproblemas.Por ejemplo, analizando el problema de colorear Por ejemplo, analizando el problema de colorear Australia para identificar su estructura, un hecho Australia para identificar su estructura, un hecho sobresale: Tasmania no está conectado al continente.sobresale: Tasmania no está conectado al continente.Intuitivamente, es obvio que colorear Tasmania y Intuitivamente, es obvio que colorear Tasmania y colorear el continente son colorear el continente son subproblemas subproblemas independientes.independientes.Cualquier solución para el continente, combinada con Cualquier solución para el continente, combinada con cualquier solución para Tasmania, proporciona una cualquier solución para Tasmania, proporciona una solución para el mapa entero.solución para el mapa entero.


La independencia puede ser confirmada La independencia puede ser confirmada simplemente observando los simplemente observando los componentes componentes conectadosconectados del grafo de restricciones. del grafo de restricciones.Los subproblemas completamente Los subproblemas completamente independientes son muy deseables, pero raros. independientes son muy deseables, pero raros. En la mayoría de los casos, los subproblemas En la mayoría de los casos, los subproblemas de un CSP están conectados. El caso más de un CSP están conectados. El caso más simple es cuando el grafo de restricciones forma simple es cuando el grafo de restricciones forma un un árbolárbol: cualquier par de variables está : cualquier par de variables está conectado a lo mucho por una ruta.conectado a lo mucho por una ruta.


A

B

C

E

D

F

Grafo de restricciones de un PSR estructurado como árbol


Cualquier PSR estructurado como árbol Cualquier PSR estructurado como árbol puede ser resuelto en un tiempo lineal en puede ser resuelto en un tiempo lineal en el número de variables.el número de variables.


El algoritmo es el siguiente:El algoritmo es el siguiente:– PASO 1: Elija cualquier variable como la raíz PASO 1: Elija cualquier variable como la raíz

del árbol, y ordene las variables desde la raíz del árbol, y ordene las variables desde la raíz hasta las hojas de tal forma que el padre de hasta las hojas de tal forma que el padre de cada nodo en el árbol lo preceda en el cada nodo en el árbol lo preceda en el ordenamiento. Etiquete las variables ordenamiento. Etiquete las variables XX11, …, , …,

XXnn en orden. Ahora, cada variable, excepto la en orden. Ahora, cada variable, excepto la

raíz, tiene exactamente una variable padre.raíz, tiene exactamente una variable padre.


A B C ED F

Un ordenamiento lineal de las variables consistente con el árbol con A como raíz


– PASO 2: Variando los valores de PASO 2: Variando los valores de jj desde desde nn hasta 2 (disminuyendo de 1 en 1), aplique hasta 2 (disminuyendo de 1 en 1), aplique verificación de consistencia de arco al arco verificación de consistencia de arco al arco ((XXii, , XXjj), donde ), donde XXii es el padre de es el padre de XXjj, , removiendo valores del DOMINIO[removiendo valores del DOMINIO[XXii] ] conforme sea necesario.conforme sea necesario.

– PASO 3: Variando los valores de PASO 3: Variando los valores de jj desde 1 desde 1 hasta hasta nn (aumentando de 1 en 1), asigne (aumentando de 1 en 1), asigne cualquier valor para cualquier valor para XXjj consistente con el consistente con el valor asignado para valor asignado para XXii, donde , donde XXii es el padre es el padre de de XXjj..


Ahora que se tiene un algoritmo eficiente Ahora que se tiene un algoritmo eficiente para árboles, se puede considerar si para árboles, se puede considerar si grafos de restricciones más generales grafos de restricciones más generales pueden pueden reducirsereducirse a árboles de alguna a árboles de alguna manera.manera.Hay dos maneras principales de hacer Hay dos maneras principales de hacer esto, una basada en remover nodos y otra esto, una basada en remover nodos y otra basada en colapsar varios nodos juntos basada en colapsar varios nodos juntos en uno.en uno.


El primer enfoque involucra asignar El primer enfoque involucra asignar valores a algunas variables de tal manera valores a algunas variables de tal manera que las variables restantes formen un que las variables restantes formen un árbol.árbol.

Considera el grafo de restricciones para Considera el grafo de restricciones para Australia. Si se pudiera eliminar Australia Australia. Si se pudiera eliminar Australia del Sur, el grafo se convertiría en un árbol.del Sur, el grafo se convertiría en un árbol.


AO

TN

AS

Q

NGS

V

T

AO

TN

Q

NGS

V

T

Grafo de Restricciones Original

Grafo de Restricciones después de quitar AS


Afortunadamente, esto se puede hacer fijando Afortunadamente, esto se puede hacer fijando un valor para un valor para ASAS y borrando de los dominios de y borrando de los dominios de las otras variables cualquier valor que sea las otras variables cualquier valor que sea inconsistente con el valor elegido para inconsistente con el valor elegido para ASAS..

Ahora, cualquier solución para el PSR después Ahora, cualquier solución para el PSR después de que de que ASAS y sus restricciones fueron removidas y sus restricciones fueron removidas será consistente con el valor elegido para será consistente con el valor elegido para ASAS..

El árbol restante puede se resuelto con el El árbol restante puede se resuelto con el algoritmo para árboles ya mencionado.algoritmo para árboles ya mencionado.


El segundo enfoque está basado en la El segundo enfoque está basado en la construcción de una construcción de una descomposición en árboldescomposición en árbol del grafo de restricciones en un conjunto de del grafo de restricciones en un conjunto de subproblemas conectados.subproblemas conectados.Cada subproblema se resuelve Cada subproblema se resuelve independientemente, y las soluciones independientemente, y las soluciones resultantes son combinada.resultantes son combinada.Como cualquier algoritmo del tipo Como cualquier algoritmo del tipo divide-y-divide-y-vencerásvencerás, éste trabaja bien si ningún , éste trabaja bien si ningún subproblema es demasiado grande.subproblema es demasiado grande.


AO

TN

AS

T

Una descomposición en árbol del grafo del

restricciones del problema del coloreo

de Australia

TN

AS

Q

AS

Q

NGS

AS NGS

V


Una descomposición en árbol debe satisfacer Una descomposición en árbol debe satisfacer los siguientes tres requerimientos:los siguientes tres requerimientos:– Cada variable en el problema original aparece en por Cada variable en el problema original aparece en por

lo menos uno de los subproblemas.lo menos uno de los subproblemas.– Si dos variables están conectadas por una restricción Si dos variables están conectadas por una restricción

en el problema original, deben aparecer juntas (con en el problema original, deben aparecer juntas (con su restricción) en por lo menos uno de los su restricción) en por lo menos uno de los subproblemas.subproblemas.

– Si una variable aparece en dos subproblemas en el Si una variable aparece en dos subproblemas en el árbol que se está creando, debe aparecer en cada árbol que se está creando, debe aparecer en cada subproblema que forme parte de la ruta que conecta subproblema que forme parte de la ruta que conecta a los dos primeros subproblemas.a los dos primeros subproblemas.


Los problemas se resuelven Los problemas se resuelven independientemente. Si cualquiera de los independientemente. Si cualquiera de los subproblemas no tiene solución, entonces subproblemas no tiene solución, entonces sabemos que el problema completo sabemos que el problema completo tampoco tiene solución.tampoco tiene solución.

Si todos los subproblemas se pueden Si todos los subproblemas se pueden resolver, se intenta construir entonces una resolver, se intenta construir entonces una solución global al problema.solución global al problema.

Documents

Inteligencia Artificial 2.3 Problemas de Satisfacción de Restricciones