Problemas de Satisfação de Restrições
Constraint Satisfaction Problems (CSP)
Disciplina:
Inteligência Artificial
Prof. Frederico Brito Fernandes
[email protected]
CONTEÚDO
(1) CSP (Coloração de Mapas)
(2) Exercício
(3) Problema Real: Alocação de
Disciplinas
Roteiro da aula de CSP
(1) Mini-problema: Coloração do Mapa com CSP
A
C
– Objetivo:
•
•
B
E
Colorir o mapa com o mínimo de cores;
Dois blocos adjacentes não podem ter cores iguais
F
D
(2) Exercício de compreensão: passagem de moto-taxi
– Objetivo:
•
•
Fazer o pagamento da corrida de moto-taxi usando 5 moedas;
Uma moeda de 50 centavos ou duas de 25c são obrigatórias;
(3) Problema real: alocação de disciplinas
– Objetivo:
•
•
Disciplina: Inteligência Artificial
Fazer a alocação das disciplinas de um curso;
Variáveis possíveis: professores, disciplinas, períodos, laboratórios,
salas com data show, professores com restrições de horários, etc
Professor: Frederico Brito Fernandes
2/21
(1) Satisfação de Restrições (CSP)
• Um Problema de Satisfação de Restrições
– Constraint Satisfaction Problems (CSP)
– tipo de problema que impõe propriedades estruturais adicionais à
solução a ser encontrada
– há uma demanda mais refinada do que na busca clássica
• ex. ir de Recife à Cajazeiras com no máximo 3 tanques de gasolina e
7 horas de viagem
• Um CSP consistem em:
– um conjunto de variáveis que podem assumir valores dentro de um
dado domínio
– um conjunto de restrições que especificam propriedades da
solução - valores que essas variáveis podem assumir.
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
3/21
(1) CSP: Formulação
• Estados:
– definidos pelos valores possíveis das variáveis
• Estado inicial:
– nenhuma variável instanciada ainda
• Operadores:
– atribuem valores (instanciação) às variáveis (uma variável por vez)
• Teste de término:
– verificar se todas as variáveis estão instanciadas obedecendo as
restrições do problema
• Solução:
– conjunto dos valores das variáveis instanciadas
• Custo de caminho:
– número de passos de atribuição
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
4/21
(1) CSP: características das restrições
• O conjunto de valores que a variável i pode assumir é chamado
domínio Di
– O domínio pode ser discreto (fabricantes de uma peça do carro) ou
contínuo (peso das peças do carro)
• Quanto à aridade, as restrições podem ser
–
–
–
–
unárias (sobre uma única variável) - ex. B ≠ azul
binárias (sobre duas variáveis) - ex. B ≠ C
n-árias - ex. palavras cruzadas
a restrição unária é um sub-conjunto do domínio, enquanto que a nária é um produto cartesiano dos domínios
• Quanto à natureza, as restrições podem ser
– absolutas (não podem ser violadas)
– preferenciais (devem ser satisfeitas quando possível)
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
5/21
(1) CSP - Busca cega
• Funcionamento
– estado inicial: variáveis sem atribuição
– aplica operador: instancia uma variável
– teste de parada: todas variáveis instanciadas sem violações
• Análise
– pode ser implementada com busca em profundidade limitada
( l = número de variáveis)
– é completa
– fator de expansão: i |Di|
– o teste de parada é decomposto em um conjunto de restrições
sobre as variáveis
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
6/21
(1) CSP-Exemplo: coloração de mapas
Simulação passo a passo...
A= verde
B = verde
C= verde
D=verde
E=verde
F=verde (falha c/ C, E, D)
F=vermelho
E (falha c/ C,A,B)
E=vermelho (falha c/ F)
E=azul
C (falha c/ A)
...
Muito dispendioso
Disciplina: Inteligência Artificial
variáveis: A,B,C,D,E,F
domínio: {verde,vermelho,azul}
restrições: A  B; A  C; A  E; B
 E; B  F; C  E; C 
F; D  F; E  F
A
B
C
E
F
Professor: Frederico Brito Fernandes
D
7/21
(1) CSP - Backtracking na busca cega
• Problema da busca em profundidade
– perda de tempo pois continua mesmo que uma restrição já tenha
sido violada (não se pode mais redimir o erro)
• Solução: Backtracking
– depois de realizar uma atribuição, verifica se restrições não são
violadas
– caso haja violação  backtrack
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
8/21
(1) CSP-Exemplo: coloração de mapas
Simulação passo a passo...
A= verde
B = verde (falha c/ A)
B=vermelho
C=verde (falha c/ A)
C= vermelho
D=verde
E= verde (falha c/ A)
E= vermelho (falha c/ B e C)
E= azul
F=verde (falha c/ D)
F=vermelho (falha c/ C)
F = azul (falha c/ E)
F backtracking
E backtracking
D=vermelho
E=verde (falha c/ A)
E= vermelho (falha c/ B)
E= azul
F=verde
Disciplina: Inteligência Artificial
variáveis: A,B,C,D,E,F
domínio: Da=Db...=Df={verde,vermelho,azul}
restrições:
A  B; A  C; A  E; B  E; B 
F; C  E; C  F; D  F; E  F
A
B
C
E
F
Professor: Frederico Brito Fernandes
D
9/21
(1) CSP-Exemplo: coloração de mapas
Mas poderia ser mais complicado
começando por vermelho...
A=vermelho
B=verde
variáveis: A,B,C,D,E,F
C=azul
domínio: Da=Db...=Df={verde,vermelho,azul}
restrições:
A  B; A  C; A  E; B  E; B  F;
D=vermelho
C  E; C  F; D  F; E  F
E= ?? Backtracking
D=verde
E=?? Backtracking
B
A
D=azul
E=?? Backtracking
C
D= ?? Backtracking
C = verde
D = verde
E
E = azul
F=vermelho
D
F
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
10/21
(1) CSP - Backtracking não basta...
• Problema do backtracking:
– Após atribuir um valor a uma variável -> solução impossível
• Ex.: A=vermelho, B=verde e C=azul.
• Soluções
– Verificação de arco-consistência (forward checking)
– Propagação de restrições
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
11/21
(1) CSP - Refinamentos
• Verificação prévia (forward checking)
– idéia: olhar para frente para detectar situações insolúveis
• Algoritmo:
– Após cada atribuição, elimina do domínio das variáveis não
instanciadas os valores incompatíveis com as atribuições feitas até
agora.
– Se um domínio torna-se vazio, backtrack imediatamente.
• É bem mais eficiente!
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
12/21
(1) CSP - Propagação de restrições
• Forward checking é um caso particular de verificação de
arco-consistência
– um estado é arco-consistente se o valor de cada variável é
consistente com as restrições sobre esta variável
– arco-consistência é obtida por sucessivas eliminações de valores
inconsistentes
• Propagação de restrições (constraint propagation)
– uma conseqüência da verificação de arco-consistência
– quando um valor é eliminado, outros podem se tornar
inconsistentes e terem que ser eliminados também
– é como uma onda que se propaga: as escolhas ficam cada vez mais
restritas
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
13/21
(1) CSP - Propagação de restrições
variáveis: A,B,C,D,E,F
domínio: Da=Db...=Df={verde,vermelho,azul}
restrições:
A  B; A  C; A  E; B  E; B  F;
C  E; C  F; D  F; E  F
Passo a passo...
A=vermelho
=> B, C, E ={verde,azul} (variáveis c/ restrições c/ A)
=> D, F ={vermelho,verde,azul}
B=verde
=> E = {azul}, F = {vermelho, azul} (variáveis c/ restrições c/ B)
=> C ={verde,azul}, D ={vermelho,verde,azul}
C = verde
=> E ={azul}, F = {vermelho, azul} (restrições c/ C)
B
A
=> D = {vermelho,verde,azul}
D=vermelho, E=azul, F=??
C
Backtracking F e D!!
D=verde, E=azul, F=vermelho
E
F
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
D
14/21
(1) CSP - Heurísticas para CSP
• Tenta reduzir o fator de expansão do espaço de estados
• Onde pode entrar uma heurística?
– Ordenando a escolha da variável a instanciar
– Ordenando a escolha do valor a ser associado a uma variável
• Existem 3 heurísticas para isto...
– Variável mais restritiva: variável envolvida no maior número de
restrições é preferida
– Variável mais restringida: variável que pode assumir menos valores é
preferida
– Valor menos restritivo: valor que deixa mais liberdade para futuras
escolhas
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
15/21
(1) CSP - Variável mais restritiva
(variável envolvida no maior número de restrições)
variáveis: A,B,C,D,E,F
domínio: Da=Db...=Df={verde,vermelho,azul}
restrições:
A  B; A  C; A  E; B  E; B  F;
C  E; C  F; D  F; E  F
Candidatas1: E(4), F(4), ...resto(3)
E = verde
Candidatas2: F, ...resto
F = vermelho
Candidatos3: A, B, C, D
A= vermelho
Candidato4: B, C, D
B= azul
Candidatos5: C, D
C= azul
D = verde
A
BB
C
E
F
D
SEM BACKTRACK!!
1
em ordem de prioridade
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
16/21
(1) CSP - Variável mais restringida
(variável que pode assumir menos valores)
variáveis: A,B,C,D,E,F
domínio: Da=Db...=Df={verde,vermelho,azul}
restrições:
A  B; A  C; A  E; B  E; B  F;
C  E; C  F; D  F; E  F
Candidatas1: todas
A={v,v,a},B={v,v,a},C={v,v,a},...
A = verde
Candidatas2: B={v,a}, C={v,a}, E={v,a}, D={v,v,a}, F={v,v,a}
B = vermelho
Candidatos3: E={a}, C={v,a}, F={v,a}, D={v,v,a}
E=azul
Candidatos4: C={v}, F={v}, D={v,v,a}
BB
A
C=vermelho
Candidatos5: F={v}, D={v,v,a}
C
F=verde
Candidatos6: D={v,a}
D = azul ou vermelho
E
SEM BACKTRACK!!
Disciplina: Inteligência Artificial
F
Professor: Frederico Brito Fernandes
D
17/21
(1) CSP - Valor menos restritivo?
(valor que deixa mais liberdade)
variáveis: A,B,C,D,E,F
domínio: Da=Db...=Df={verde,vermelho,azul}
restrições:
A  B; A  C; A  E; B  E; B  F;
C  E; C  F; D  F; E  F
A
Começando com
A = verde
B = vermelho
C=??? vermelho é melhor do
que azul
Disciplina: Inteligência Artificial
B
C
E
F
Professor: Frederico Brito Fernandes
D
18/21
(1) CSP - Conclusão
• Grande importância prática, sobretudo em tarefas de
– criação (design)
– agendamento (scheduling)
– onde várias soluções existem e é mais fácil dizer o que não se
quer...
• Estado atual
– Grandes aplicações industriais $$$$
– Número crescente de artigos nas principais conferências
• Observação:
– a sigla CSP também é usada para falar de Constraint Satisfaction
Programming, que é um paradigma de programação
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
19/21
(2) Exercício
• Eu preciso pagar a minha passagem de moto-taxi, que custa 91
centavos. Para pagá-la, eu devo utilizar 5 moedas. O cobrador quer
que eu lhe dê uma moeda de 25 centavos ou duas de 10 centavos.
Represente isso como um problema de satisfação de restrições e
mostre como as heurísticas de propagação de restrições (forwardchecking), variável mais restrita eu variável mais restringente
agilizam a resolução. Admita que você possui um número infinito de
cada moeda.
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
20/21
(3) Problema real: Alocação de Disc.
•
Objetivo:
–
•
Formule uma solução para esse problema:
–
–
•
Todo coordenador tem a cansativa tarefa de montar os horários das
disciplinas a cada semestre.
usando CSP, lembrando que você deve estabelecer: (1)Variáveis; (2)
Domínio e (3) Regras.
a lógica de programação usada (independente de linguagem).
Admita que a faculdade têm apenas:
–
–
–
–
–
–
–
dois períodos (P1 e P2);
dois professores (Fechine e Nilton);
duas disciplinas por período (d1_a, d1_b, d2_a, d2_b);
Fechine leciona d1_a e d2_a, e Nilton leciona d1_b, d2_b;
duas noites de aula por semana, com duas aulas por noite;
Fechine não pode ensinar no primeiro horário da segunda;
não é permitido que uma mesma disciplina tenha duas aulas por noite.
Disciplina: Inteligência Artificial
Professor: Frederico Brito Fernandes
21/21