IF67B C71 aula12

Prévia do material em texto

IF71B-C71 - Inteligeˆncia Artificial
Aula 12 - Problemas de Satisfac¸a˜o de Restric¸o˜es
Profa. Dra. Priscila T iemi çaeda Saito
k psaito@utfpr.edu.br
2o Semestre 2016
21/09/16
Roteiro
1 Problemas de Satisfac¸a˜o de Restric¸o˜es
2 Busca com Backtracking para PSR
3 Busca Local para PSR
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 2 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Problemas de Satisfac¸a˜o de Restric¸o˜es (PSR) ou Constraint
Satisfaction Problems (CSP)
Problema da busca padra˜o
I estado e´ uma caixa preta “black box”
I qualquer estrutura que suporte a func¸a˜o sucessor, heur´ısticas, e teste
de objetivo
PSR ou CSP
I estado e´ definido por varia´veis Xi com valores de um dom´ınio Di
I teste de objetivo e´ um conjunto de restric¸o˜es especificando
combinac¸o˜es permitidas de valores para as varia´veis
Representa uma linguagem formal de representac¸a˜o
Permite algoritmos u´teis de propo´sito geral com mais poder que
algoritmos de busca padra˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 3 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Formulac¸a˜o
I estados: definidos pelos valores poss´ıveis das varia´veis
I estado inicial: nenhuma varia´vel instanciada ainda
I operadores: atribuem valores (instanciac¸a˜o) a`s varia´veis
F uma varia´vel por vez
I teste de te´rmino: verificar se todas as varia´veis esta˜o instanciadas
obedecendo a`s restric¸o˜es do problema
I soluc¸a˜o: conjunto dos valores das varia´veis instanciadas
I custo de caminho: nu´mero de passos de atribuic¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 4 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
O conjunto de valores que a varia´vel i pode assumir e´ chamado
dom´ınio Di
I o dom´ınio pode ser discreto ou cont´ınuo
F fabricantes de uma pec¸a do carro, peso das pec¸as do carro
Quanto a` aridade, as restric¸o˜es podem ser
I una´rias (sobre uma u´nica varia´vel)
I bina´rias (sobre duas varia´veis)
I n-a´rias
Quanto a` natureza, as restric¸o˜es podem ser
I absolutas (na˜o podem ser violadas)
I preferenciais (devem ser satisfeitas quando poss´ıvel)
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 5 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Toda soluc¸a˜o deve ser uma atribuic¸a˜o completa e, portanto, aparece
na profundidade n
A a´rvore de busca se estende ate´ a profundidade
Por essas razo˜es, os algoritmos de busca em profundidade sa˜o
populares para CSP
O caminho pelo qual uma soluc¸a˜o e´ alcanc¸ada e´ irrelevante
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 6 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Problema das 8-rainhas
varia´veis: localizac¸a˜o das rainhas (coluna, linha)
valores: poss´ıveis posic¸o˜es do tabuleiro
restric¸a˜o bina´ria: duas rainhas na˜o podem estar na mesma coluna,
linha ou diagonal
soluc¸a˜o: valores para os quais a restric¸a˜o e´ satisfeita
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 7 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Busca cega com backtracking para CSP
Funcionamento
I estado inicial: varia´veis sem atribuic¸a˜o
I aplica operador: instancia uma varia´vel
I teste de parada: todas varia´veis instanciadas sem violac¸o˜es
Backtracking (Retrocesso)
I depois de realizar uma atribuic¸a˜o, verifica se restric¸o˜es na˜o sa˜o violadas
I caso haja violac¸a˜o, retrocede
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 8 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Busca cega com backtracking para CSP
Ana´lise
I pode ser busca em profundidade limitada
F l = nu´mero de varia´veis
I e´ completa
I fator de expansa˜o:
∑
i |Di |
I teste de parada e´ decomposto em um conjunto de restric¸o˜es sobre as
varia´veis
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 9 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Colorac¸a˜o de mapas
Colorir cada bloco de vermelho, verde ou azul, de tal modo que
nenhum bloco vizinho tenha a mesma cor
Formular o problema como um PSR
I varia´veis: ?
I dom´ınio: ?
I restric¸o˜es: ?
Soluc¸a˜o: ? (atribuic¸o˜es completas e consistentes)
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 10 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Colorac¸a˜o de mapas
varia´veis: A, B, C, D, E, F
dom´ınio: Da = Db... = Df = {green, red, blue}
restric¸o˜es:
A 6= B;A 6= C ;A 6= E ;B 6= E ;B 6= F ;C 6= E ;C 6= F ;D 6= F ;E 6= F
Soluc¸a˜o: ? (atribuic¸o˜es completas e consistentes)
Solucionar usando busca em profundidade limitada com l = 6
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 11 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Soluc¸a˜o usando busca em profundidade limitada com l = 6
Verificac¸a˜o pre´via combinada com propagac¸a˜o de restric¸o˜es
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 12 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Colorac¸a˜o de mapas
varia´veis: A, B, C, D, E, F
dom´ınio: Da = Db... = Df = {green, red, blue}
restric¸o˜es: A 6= B; A 6= C ; A 6= E ; B 6= E ; B 6= F ; C 6= E ; C 6=
F ; D 6= F ; E 6= F
Soluc¸a˜o
A = green, B = red, C = red, D red, E = blue, F = green
Simulac¸a˜o passo a passo
A = green
B = green (falha com A)
B = red
C = green (falha com A)
C = red
D = green
E = green (falha com A)
E = red (falha com B e C)
E = blue
F = green (falha com D)
F = red (falha com C)
F = blue (falha com E)
F backtracking
E backtracking
D = red
E = green (falha com A)
E = red (falha com B)
E = blue
F = green
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 13 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Poderia comec¸ar por red e fazer outra forma de selec¸a˜o de valores no
dom´ınio
Colorac¸a˜o de mapas
varia´veis: A, B, C, D, E, F
dom´ınio: Da = Db... = Df = {red, green, blue}
restric¸o˜es: A 6= B; A 6= C ; A 6= E ; B 6= E ; B 6= F ; C 6= E ; C 6=
F ; D 6= F ; E 6= F
Simulac¸a˜o passo a passo
A = red
B = green
C = blue
D = red
E = ? Backtracking
D = green
E = ? Backtracking
D = blue
E = ? backtracking
D = ? backtracking
C = green
D = green
E = blue
F = red
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 14 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Backtracking na˜o basta
Problema do backtracking
I na˜o adianta mexer na se´tima rainha para poder posicionar a u´ltima
I o problema e´ mais em cima
I o backtrack normalmente tem que ser de mais de um passo
Soluc¸o˜es
I verificac¸a˜o pre´via (forward checking)
I propagac¸a˜o de restric¸o˜es
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 15 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Verificac¸a˜o pre´via (forward checking)
I ideia: olhar para frente para detectar situac¸o˜es insolu´veis
Algoritmo
I apo´s cada atribuic¸a˜o, elimina do dom´ınio das varia´veis na˜o
instanciadas os valores incompat´ıveis com as atribuic¸o˜es realizadas ate´
agora
I se um dom´ınio torna-se vazio, retrocede imediatamente
E´ bem mais eficiente
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 16 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Verificac¸a˜o pre´via (forward checking)
Colorac¸a˜o de mapas
varia´veis: A, B, C, D, E, F
dom´ınio: Da = Db... = Df = {red, green, blue}
restric¸o˜es: A 6= B; A 6= C ; A 6= E ; B 6= E ; B 6=
F ; C 6= E ; C 6= F ; D 6= F ; E 6= F
Simulac¸a˜o passo a passo
A = red
I B, C, E = {green, blue}
(varia´veis com restric¸o˜es com A)
I D, F = {red, green, blue}
B = green
I E = {blue}, F = {red, blue}
(varia´veis com restric¸o˜es com B)
I C = {green, blue}, D = {red, green, blue}
C = green
I E ={blue}, F = {red, blue}
(restric¸o˜es com C)
I D = {red, green, blue}
D = red, E = blue, F = ?
Backtracking F e D
D = green, E = blue, F = red
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 17 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Propagac¸a˜o de restric¸o˜es (constraint propagation)
Uma consequeˆncia da verificac¸a˜o pre´via
Quando um valor e´ eliminado, isto e´ propagado para outros valores
que dele dependem, podendo torna´-los inconsistentes e eliminados
tambe´m
E´ como uma onda que se propaga: as escolhas ficam cada vez mais
restritas
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 18 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Colorac¸a˜o de mapas
varia´veis: A, B, C, D, E, F
dom´ınio: Da = Db... = Df = {green, red, blue}
restric¸o˜es: A 6= B; A 6= C ; A 6= E ; B 6= E ; B 6= F ; C 6= E ; C 6=
F ; D 6= F ; E 6= F
Simulac¸a˜o passo a passo
A = green
B,C,E = {r, b}, D, F = {g, r, b}
B = red
C = {r, b}, D = {g, r, b}, E =
{b}, F = {g, b} → C = {r}, F =
{g} → D = {r, b}
C = red
D = {r, b}, E = {b}, F = {g}
D = red
E = {b}, F = {g}
E = blue
F = green
Sem retrocesso
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 19 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Heur´ıstica para CSP
Tenta reduzir o fator de expansa˜o do espac¸o de estados
Onde pode entrar uma heur´ıstica?
I ordenando a escolha da varia´vel a instanciar
I ordenando a escolha do valor a ser associado a uma varia´vel
Existem 3 heur´ısticas para isto
I valores remanescentes m´ınimos (MRV): varia´vel com menor
nu´mero de valores legais
I de grau: varia´vel com mais restric¸o˜es
I valor menos restritivo: valor que descarta menos valores para as
varia´veis restantes
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 20 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Heur´ıstica de valores remanescentes m´ınimos (mrv)
Varia´vel que pode assumir menos valores
Colorac¸a˜o de mapas
varia´veis: A, B, C, D, E, F
dom´ınio: Da = Db... = Df = {green, red, blue}
restric¸o˜es: A 6= B; A 6= C ; A 6= E ; B 6= E ; B 6= F ; C 6= E ; C 6=
F ; D 6= F ; E 6= F
Simulac¸a˜o passo a passo
Candidatas: todas
A = green
Candidatas: B, C, E, ...
B = red
Candidatos: E, F, ...
E = blue
Candidatos: C, F, D
C = red
Candidatos: F, D
F = green
D = blue ou red
Sem Backtrack
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 21 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Heur´ıstica de Grau
Varia´vel envolvida no maior nu´mero de restric¸o˜es
Colorac¸a˜o de mapas
varia´veis: A, B, C, D, E, F
dom´ınio: Da = Db... = Df = {green, red, blue}
restric¸o˜es: A 6= B; A 6= C ; A 6= E ; B 6= E ; B 6= F ; C 6= E ; C 6=
F ; D 6= F ; E 6= F
Simulac¸a˜o passo a passo
Candidatas: E, F, ..., resto
(em ordem de prioridade)
E = green
Candidatas: F, ..., resto
F = red
Candidatos: A, B, C, D
A = red
Candidatos: B, C, D
B = blue
Candidatos: C, D
C = blue
D = green
Sem Backtrack
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 22 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Heur´ıstica de valor menos restritivo
Valor que descarta menos valores para as varia´veis restantes
Colorac¸a˜o de mapas
varia´veis: A, B, C, D, E, F
dom´ınio: Da = Db... = Df = {green, red, blue}
restric¸o˜es: A 6= B; A 6= C ; A 6= E ; B 6= E ; B 6= F ; C 6= E ; C 6=
F ; D 6= F ; E 6= F
Simulac¸a˜o passo a passo
Comec¸ando com
A = green
B = red
C = ? red e´ melhor do que blue
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 23 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Busca Local para PSRs
Algoritmos de busca local mostram-se muito eficazes na resoluc¸a˜o de
va´rios PSRs
PSR Iterativo
I pode ser resolvido iterativamente
I utilizam formulac¸a˜o de estados completos
I estado inicial atribui um valor a cada varia´vel
I busca altera o valor de uma varia´vel de cada vez para diminuir o
nu´mero de restric¸o˜es na˜o satisfeitas
F heur´ıstica de conflitos m´ınimos (min-conflicts)
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 24 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 25 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Min-conflict
I aplicado com sucesso ao problema das n rainhas
F valores de n extremamente grandes
I problema das 1000000 rainhas solucionado em me´dia com cerca de 50
passos
F soluc¸a˜o por meio de buscas tradicionais imposs´ıvel → busca em a´rvore
com fator de ramificac¸a˜o de 1012
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 26 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Problemas reais de PSRs → grande importaˆncia pra´tica
I muitos envolvem varia´veis com valores reais
I va´rias soluc¸o˜es existem e e´ mais fa´cil dizer o que na˜o se quer
I exemplos
F criac¸a˜o, projeto (design)
F agendamento (scheduling)
F log´ıstica de transporte
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 27 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Problema-exemplo: agendamento de tarefas
montagem de um carro → trabalho composto de tarefas
modelagem de cada tarefa como uma varia´vel
valor de cada varia´vel e´ o tempo em que comec¸a a tarefa
restric¸o˜es podem afirmar que uma tarefa deve ocorrer antes da outra
I uma roda deve ser instalada antes que a calota seja colocada, e que
apenas tais tarefas podem ser simultaˆneas
restric¸o˜es podem especificar que uma tarefa leva certo tempo para ser
conclu´ıda
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 28 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Problema-exemplo: agendamento de tarefas
varia´veis
{Eixof , Eixot , Rodadf , Rodaef , Rodadt , Rodaet , Porcadf , Porcaef , Porcadt ,
Porcaet , Calotadf , Calotaef , Calotadt , Calotaet , inspecionar}
dom´ınio
{hora em que a tarefa comec¸a}
restric¸o˜es de precedeˆncia
T1 + d1 ≤ T2
em que T1 e T2 → tarefas e d1 → durac¸a˜o da tarefa T1
restric¸o˜es de precedeˆncia
Eixof + 10 ≤ Rodadf
Eixof + 10 ≤ Rodaef
Eixot + 10 ≤ Rodadt
Eixot + 10 ≤ Rodaet
em que 10 → tempo para instalar um eixo
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 29 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Resumo
PSR e´ um tipo especial de problema
I estados sa˜o definidos por valores de varia´veis
I teste de objetivo e´ definido por restric¸o˜es nos valores das varia´veis
Backtracking = busca em profundidade com uma varia´vel atribu´ıda
por vez
Verificac¸a˜o pre´via previne atribuic¸o˜es que levam a falha futura
Propagac¸a˜o de restric¸o˜es ajuda a restringir valores e detectar
insconsisteˆncias
Heur´ıstica min-conflicts e´ bastante efetiva na pra´tica
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 30 / 31
Problemas de Satisfac¸a˜o de Restric¸o˜es
Exerc´ıcio
O mapa apresenta os principais estados e territo´rios da Austra´lia
Atribuir cores a cada regia˜o de modo que na˜o haja regio˜es vizinhas
com a mesma cor
Considere
WA (Western Australia), NT (Northern Territory), Q (Queensland), NSW
(New South Wales), V (Victoria), SA (South Australia), T (Tasmania)
R (vermelho), G (verde), B (azul)
Formule o problema como PSR e solucione utilizando:
I retrocesso (backtracking)
I verificac¸a˜o pre´via (forward checking)
I heur´ısticas: minimum remaining values, degree heuristic, least
constraining value
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 12 - PSR/CSP 31 / 31
	Problemas de Satisfação de Restrições
	Busca com Backtracking para PSR
	Busca Local para PSR