Problemas de Satisfação de Restrições ( Constraint Satisfaction Problems )

19/04/23 IA - Prof. Paulemir Campos 1

Problemas de Satisfação de Restrições

(Constraint Satisfaction Problems)

UPE – Caruaru – Sistemas de InformaçãoDisciplina: Inteligência ArtificialProf.: Paulemir G. Campos


Roteiro da Aula

CSP e Exemplos Busca por Backtracking para CSP Busca Local para CSP Estrutura do Problema e Decomposição

do Problema Quadro Comparativo Bibliografia


CSP e Exemplos


Problema de Busca Padrão

Estado é uma “black box” Representado por qualquer estrutura de

dados com:– Sucessor– Heurística– e, Teste de Meta


Constraint Satisfaction Problems Estado é definido por variáveis Xi com

valores num domínio Di

Teste de Meta é um conjunto de restrições sobre os valores das variáveis

Exemplo simples de uma Linguagem de Representação Formal

Uso de algoritmos e heurísticas de propósito geral


Problema de Colorir um Mapa

Variáveis: WA, NT, Q, NSW, V, SA, T

Domínio: Di = { vermelho, verde, azul }

Restrições: Regiões vizinhas devem ter cores diferentes



Soluções: São atribuições que satisfazem todas as restrições

Ex.: { WA=vermelho, NT=verde, Q=vermelho, NSW=verde, Victoria=vermelho, SA=azul, T=verde }


Grafo de Restrições

Aumenta a velocidade de busca (Algoritmos CSP de propósito geral)

Ex.: Tasmânia é um subproblema independente

Variável

Restrição


Variedade de CSPs

Variáveis Discretas– Domínios Finitos: d O(dn)

• Ex.: CSP Booleanos, inclusive Satisfabilidade

Booleana (NP-Completo)

– Domínios Infinitos (Inteiros, strings, etc.)• Ex.: Agendamento de Trabalhos

Variáveis : dias de start / end de cada job

Linguagem de Restrições: StartJob1 + 5 StartJob3

Permite resolver restrições lineares frente a

indecidibilidade não-linear


Variedade de CSPs

Variáveis Contínuas– Ex.: Tempo de start / end para as

observações do Telescópio Hubble– Resolve restrições lineares em tempo

polinomial por métodos de Programação Linear (PL)


Tipos de Restrições

Unária (Ex.: SA verde ) Binária (Ex.: SA WA ) Ordem Maior (Três ou mais variáveis)

• Ex.: Restrições entre colunas cryptarithmetic

Preferenciais

(Problemas de Otimização)• Ex.: Vermelho é melhor do que verde, isto é,

há uma função de custo nas atribuições.


Cryptarithmetic

Problema – Associar a cada letra, um dígito diferente tal que

substituindo as letras pelos seus dígitos associados a adição esteja aritmeticamente correta

Formulação em CSP:– Variáveis: F, T, U, W, R, O, X1, X2, X3

– Domínio: { 0,1,2,3,4,5,6,7,8,9 }– Restrições: alldiff (F,T,U,W,R,O)

O + O = R + 10 . X1 X1 + W + W = U + 10 . X2

X2 + T + T = O + 10 . X3 X3 = F


CSPs do Mundo Real

Problemas de Alocação• Ex.: Que professores com qual turma?

Problemas de Oferta de Disciplinas• Ex.: Que matéria será oferecida,quando e onde?

Configuração de Hardware Agendamento de Transportadora

(Geralmente usam variáveis de valores reais)


Formulação Busca Padrão

Estados são definidos pelos valores atribuídos Estado Inicial: Atribuição vazia, { } Função Sucessor: Atribui um valor a uma

variável vazia, sem violar as restrições Teste de Meta: Atingiu a atribuição completa Caminho de Custo: Um valor constante para

todo passo.


Formulação Busca Padrão

1) Idêntico para todos os CSPs2) Toda solução aparece em profundidade n com n

variáveis (Uso de depth-first search)3) Caminho é irrelevante, assim, pode ser usada

Formulação de Estado Completo4) Fator de ramificação b decresce com profundidade

no nó da árvore de busca5) Se cardinalidade maior dos domínios = d

Então fator de ramificação a profundidade l, é b = (n - l)d

Conseqüentemente há n!dn folhas na árvore


Busca por Backtrackingpara CSP


Características

Atribuição de Variáveis são Comutativas– Ex.: WA=vermelho Então NT=verde NT=verde Então WA=vermelho

Só atribuição a uma variável simples por vez:– b = d– dn folhas na árvore de busca


Definição

Busca primeiro por profundidade (depth-first search) para CSPs com atribuição de variáveis simples.

É um algoritmo uniformizado básico para CSPs

Pode resolver n-queens para n 25




Melhorando a Eficiência do Backtracking Métodos de propósito geral podem obter

imensos ganhos em velocidade– Que variável poderá ser atribuída a seguir?– Em que ordem seus valores serão

tentados?– Pode-se detectar falhas inevitáveis cedo?– Podemos tirar vantagens da estrutura do

problema?


Que variável será atribuída a seguir?

A variável mais restringida (unária)– Escolha a variável com o menor número de

valores legais (Minimum Remaining Values)


A variável com mais restrições (binária)– Escolha a variável com o maior número de

restrições das variáveis restantes

Que variável será atribuída a seguir?


O valor com menos restrições– Escolha o valor que provoque o menor

número de restrições possíveis nas variáveis restantes

SA = azul

SA = { }Obs.: Combinando essas heurísticas possivelmente

resolveremos o problema n-queens com n=1000

Em que ordem seus valores serão tentados?


Em que ordem seus valores serão tentados? Checagem para Frente

(Forward Checking)– Idéia: Manter a trilha de valores legais

restantes para as variáveis não atribuídas. – Busca termina quando qualquer variável

tem nenhum valor legal.


Checagem para Frente

WA

V

Q


Propagando Restrições Checagem para frente propaga informações

de atribuições para variáveis vazias. Porém, não provê detecção antecipada de

todas as falhas.Restrição:NT SA


Pode-se detectar falhas inevitáveis cedo?

Consistência de Arco• Forma mais simples de propagação faz cada

arco consistente

X Y é consistente se somente se

para cada valor x de X há algum y válido.


Consistência do Arco

WAQ

SA NSW

Caminho mais simples

Se SA = azul Então NSW = vermelho

Logo o arco de SA para NSW é consistente!



WAQ

SA NSW

Caminho menos simples

Se NSW = azul Então SA = { }Logo o arco

de NSW para SA é INconsistente!

Restrição:SA NSW


Se X perde um valor, vizinhança de X precisa ser checada novamente


WAQ

SA

V

NSW

Se vermelho V={vermelho, verde,azul} Então V={verde,azul}

Se SA = azul Então NSW = {vermelho}

Com a checagem da vizinhança de NSW, o arco de V para NSW tornou-se consistente!


Pode ser usado como pré-processamento ou depois de cada atribuição. O(n2d3) podem ser reduzido para O(n2d2), porém não detecta todas as falhas em

tempo polinomial.

WAQ

SA

NT

Se Q = verde Então NT = {azul}


Se azul SA={azul} Então SA={}

Com a checagem da vizinhança de NT, consegue-se detectar mais cedo(que checagem para frente) um futuro arco INconsistente!

Restrição:SA NT


Busca Local para CSP


Algoritmos Iterativos para CSPs

Hill-climbing e simulated annealing trabalham com estados “completos”

Aplicando-os aos CSPs• Permite estados com restrições insatisfeitas• Operadores reatribui valores às variáveis

Seleção de Variável• Qualquer com conflito aleatoriamente


Algoritmos Iterativos para CSPs

Seleção pela Heurística do Mínimo Conflito (Min-Conflicts Heuristic)– Escolha do valor que viole o menor

número de restrições possívelEx.: Hill-climb com h(n) = nº total de violações


Problema das 4-Queens

Estados: 4 rainhas em 4 colunas (44 = 256) Operador: Move rainha em coluna Teste de Meta: Nenhum ataque Avaliação: h(n) = nº de ataques


Performance do Mínimo Conflito

Estado Inicial Aleatório• Pode resolver o problema das n-queens em

tempo quase sempre constante para um n arbitrário com alta probabilidade (n=10.000.000)

Qualquer CSP gerado aleatoriamente• O mesmo aparenta ser verdade, exceto na faixa

estreita de razão R, conforme abaixo. nº de restrições R = nº de variáveis


Gráfico com Performance do Mínimo Conflito

Performance do Mínimo Conflito


Estrutura do Problema e Decomposição do Problema


Podemos tirar vantagens da estrutura do problema?

– Tasmânia e o território principal da Austrália são Sub-problemas Independentes

– Identificados pelo Grafo de Restrições: Componentes Conectados


Suponha que cada sub-problema tenha c variáveis fora as n totais. O custo da solução de pior caso é n / c.dc, linear em n.

Ex.: n=80, d=2, c=20

Problema Completo: 280 = 4 bilhões de anos**

Sub-Problemas: 4. 220 = 0.4 segundos**

** Com taxa de 10 milhões de nós/segundo

Podemos tirar vantagens da estrutura do problema?


CSP Estruturado em Árvore

Teorema: “Se o grafo de restrições não tem laços, o CSP pode ser resolvido em O(nd2)”

Os CSPs gerais no pior caso é de O(d2) Aplicável a raciocínio lógico e

probabilístico Idéia: De um grafo de restrições construir

uma árvore que represente o CSP.


Algoritmo para Construção da Árvore1) Escolha qualquer variável para a raiz da

árvore e ordene-as da raiz até as folhas2) Para j de n decrescendo até 2, aplique a

Consistência do Arco em (Xi,Xj)*, removendo valores do Domínio[Xi] caso necessário

3) Para j de 1 até n, atribua qualquer valor a Xj consistente com o valor atribuído a Xi

* Onde Xi é o pai de Xj



A B C D E F

Domínio = { vermelho, verde, azul }Restrição = Os nós folhas e os nós pai com cores distintas1) Raiz: A; Variáveis Ordenadas = { A, B, C, D, E, F}2) Aplicar a Consistência de Arco das folhas para a raiz,

removendo inconsistência do nó pai3) Atribuir a partir da raiz valores consistentes às folhas


A B C D E F


CSP Quase Estruturado em Árvore Passos para a sua obtenção:

1) Escolha uma ou mais variáveis de modo que o grafo de restrições torne-se uma árvore com a poda dessa(s) variável(is)*

2) Para cada atribuição possível ao conjunto de corte S que satisfaz todas as suas restrições faça: 2.1 Remova do domínio das variáveis restantes qualquer

valor que seja inconsistente com a atribuição para S, e 2.2 Se o CSP resultante tem uma solução, então retorne-a

junto com a atribuição para S

* As variáveis removidas do grafo constituem o conjunto de corte S


CSP Quase Estruturado em Árvore

Conjunto de corte de tamanho c: Tempo de execução é de O(dc.(n-c) d2) (Grafo muito parecido com uma árvore muito rápido para c pequeno)

WA

T

SA

QNT

NSW

V

S = {SA = azul}


Decomposição do Problema Metodologia de Decomposição da Árvore

1) Cada variável do problema original deve aparecer em pelo menos um sub-problema

2) Se duas variáveis são conectadas por uma restrição no problema original, deverão estar juntas num ou mais sub-problema

3)Se uma variável aparece em mais de um sub-problema na árvore, ela deverá estar em cada sub-problema ao longo do caminho que os interliga


WA

NT

NT

SA

SA

SA

SA

Q

Q

NSW

NSW

V

T

Sub-Problema 1Sub-Problema 2

Sub-Problema 3

Sub-Problema 4

Sub-Problema 5


Quadro Comparativo

Obs.: Valores são números médios de checagem de consistência (> 5 execuções)

Problema Backtracking BT+MRV Forward

Checking

FC+MRV Minimum

Conflicts

USA

(4-colors)

(>1.000K) (>1.000K) 2K 60 64

n-Queens

(3 < n < 50)

(>40.000K) 13.500K (>40000K) 817K 4K

Zebra

(ex. 5.13)

3.859K 1K 35K 0.5K 2K

Random 1 415K 3K 26K 2K Not run

Random 2 942K 27K 77K 15K Not run


Bibliografia

Artificial Intelligence a Modern Approach (2nd Edition), S. Russell & P. Norvig, 2002, Prentice-Hall, 137-159pp

Russel, S. e Norvig, P. Inteligência Artificial. Tradução de: “Artificial Intelligence: A Modern Approach”, 2 ed. Editora Campus, 2004. (Capítulo 5)

http://aima.eecs.berkeley.edu/slides-pdf/chapter05.pdf

Documents

Problemas de Satisfação de Restrições ( Constraint Satisfaction Problems )