View
273
Download
0
Category
Preview:
Citation preview
IA: MEE - F.Giorno
Método do Espaço de Estados
(MEE)
Sistemas Baseados em Conhecimento / IA
Fernando Giorno
IA: MEE - F.Giorno
Introdução ao Curso
Inteligência Artificial (cap 4) Introdução, Visualizações Alternativas, Fundamentos e Sub-áreas
Método do Espaço de Estados (MEE) e Classificação Heurística
Representação de Conhecimento (cap 5) Fatos, Objetos e Regras de Produção
Sistemas Especialistas (cap 6) Fundamentos
Utilização
Introdução nas Empresas
Desenvolvimento
Complementos
Exercícios, Atividades e Labs
Inteligência Artificial (IA) com ênfase em SBCs
Fernando Giorno
IA: MEE - F.Giorno
Xadrez
Jarro de Água
Lavrador, Lobo, Cabra e Maço de Couve
Missionários e Canibais
Jogo dos 15 (quebra cabeça do patrão)
Torre de Hanói
. . .
O que estes problemas têm em comum?
Alguns Problemas Brinquedo
IA: MEE - F.Giorno
Tem-se 2 jarros de água, um com capacidade para 4 galões e outro com capacidade para 3 galões, e um esguicho que pode ser usado para preencher os jarros.
Não há marcação de medida em nenhum dos jarros.
Usando somente esses elementos, obter exatamente 2 galões de água no jarro de 4 galões.
Jarro de Água (JA)
4 galões 3 galões
IA: MEE - F.Giorno
Lavrador, Lobo, Cabra e Maço de Couve
Um lavrador, tendo chegado a margem norte de um rio, necessita atingir a margem sul transportando um lobo, uma cabra e um maço de couve.
Para efetuar a travessia o lavrador dispõe de um pequeno barco que só permite o transporte próprio e de um de seus pertences. Se, em qualquer margem, a cabra for deixada sózinha com o lobo, este devora a cabra e, se o maço de couve for deixado sózinho com a cabra, esta devora a couve.
Planejar a travessia de modo que o lavrador mantenha todos os seus pertences.
IA: MEE - F.Giorno
Três missionários, acompanhados de três canibais, necessitam atravessar um rio usando um barco disponível na margem.
O barco pode conduzir no máximo 2 pessoas de cada vez. Em qualquer margem do rio o número de canibais não pode ser superior ao número de missionários pois, se isto ocorrer, os missionários serão devorados pelos canibais.
Planejar a travessia de modo que os missionários não sejam devorados pelos canibais.
Missionários e Canibais (MC)
IA: MEE - F.Giorno
1 3
4
6
15 13
2
11
9
12
8
5
10
7
14
1 2
6
10
14 13
5
4
8
12
3
7
11
15
9
Jogo dos 15 (quebra cabeça do patrão)
IA: MEE - F.Giorno
Clássico problema em computação envolvendo
mover um conjunto de discos, de diferentes
tamanhos, colocados em um de três pinos de
uma placa, em ordem decrescente a partir da
placa, para um dos outros dois pinos, sob
restrições nas ações que podem ser efetuadas.
Torre de Hanói (TH)
IA: MEE - F.Giorno
Torre de Hanói (TH) No Templo de Benares, na Índia, sob a cúpula que marca o centro do
mundo, há uma placa de latão na qual estão fixadas verticalmente 3 pinos de diamante. Em um destes pinos, Brama, ao criar o mundo, colocou 64 discos de ouro, de diferentes tamanhos, em ordem decrescente a partir da placa.
Dia e noite, sem cessar, em revezamento, os sacerdotes do templo mudam os discos de um pino para outro, de acordo com leis imutáveis que exigem:
apenas um disco pode ser movido por vez
nenhum disco pode ser colocado sobre um disco de raio menor
a cada instante, todos discos devem estar em um dos 3 pinos
Quando os 64 discos tiverem sido transferidos do pino inicial para outro pino, o mundo desaparecerá com um estrondo ensurdecedor.
Obs: O 3o pino deve ser usado como local temporário para os discos
TH com 3 discos
IA: MEE - F.Giorno
O número mínimo de movimentações (transferências) de discos que
deverão ser realizadas para se atingir o objetivo do jogo é 2n - 1 onde
n é o número de discos.
Considerando então o jogo TH com 64 discos e
atendimento das regras do jogo
uma transferência / segundo
nenhum erro
a tarefa passada por Brama será completada em
264 - 1 = 58.454.204.609 séculos
+
6 anos
Torre de Hanói (TH)
IA: MEE - F.Giorno
Elementos Comuns
Estados representando a situação corrente
– estados iniciais
– estados intermediários
– estados objetivos
definindo um espaço de estados (cjto de todos estados possíveis)
Transformações do estado corrente para um novo estado (efetuada por operadores)
Restrições que devem ser obedecidas
Pesquisa em um espaço de estados em busca de um estado objetivo
IA: MEE - F.Giorno
Estado (qtde água no jarro 4g, qtde água no jarro 3g)
Estado Inicial (nil, nil)
Estado Objetivo (2, *)
Operadores {
op1: (X, Y) | X < 4 => (4, Y), op2: (X, Y) | Y < 3 => (X, 3), op3: (X, Y) | X > 0 => (X - D, Y),
. . .
}
Solução caminho através do Espaço de Estados conectando Estado Inicial à Estado Objetivo.
Jarro de Água (JA)
op: (X, Y) => (X', Y')
IA: MEE - F.Giorno
Estado (Nmissionários, Ncanibais, posição do barco)
Estado Inicial (3, 3, esquerda)
Estado Objetivo (3, 3, direita)
Operadores {
op1: move 1M da ME p/ MD,
op2: move 1C da ME p/ MD,
op3: move 1M e 1C da ME p/ MD,
. . . }
Restrição capacidade de transporte do barco: som/ 2 pessoas
Solução caminho através do Espaço de Estados conectando Estado Inicial à Estado Objetivo
Missionários e Canibais (MC)
IA: MEE - F.Giorno
Estado ( (elementos ME) (elementos MD) )
Estado Inicial ( (M, M, M, C, C, C, B) ( ) )
Estado Objetivo ( ( ) (M, M, M, C, C, C, B) )
Operadores {
op1: move 1M da ME p/ MD,
op2: move 1C da ME p/ MD,
op3: move 1M e 1C da ME p/ MD,
. . . }
Restrição capacidade de transporte do barco: som/ 2 pessoas
Solução caminho através do Espaço de Estados conectando Estado Inicial à Estado Objetivo
Missionários e Canibais - outra representação para estado
IA: MEE - F.Giorno
Estado ((discos pino A) (discos pino B) (discos pino C))
Estado Inicial ((1, 2, . . . , 64) ( ) ( ))
Estado Objetivo (( ) ( ) (1, 2, . . . , 64))
Operadores {
move1AB,
move2AC,
. . . }
Restrição disco não pode ser colocado sobre disco menor
Solução Caminho através do Espaço de Estados conectando Estado Inicial à Estado Objetivo
Torre de Hanói (TH)
IA: MEE - F.Giorno
A B C A B C
2
3
1
2
3
1
Torre de Hanói (TH) - Estados Inicial e Objetivo
Estado Inicial
( (1 2 3) ( ) ( ) ) Estado Objetivo
( ( ) ( ) (1 2 3) )
IA: MEE - F.Giorno
A B C A B C
Estado Inicial
( (1 2 3) ( ) ( ) ) move1AB
2
3
1
2
3 1
Torre de Hanói (TH) Operador move1AB aplicado ao Estado Inicial
Estado Intermediário
( (2 3) (1) ( ) )
IA: MEE - F.Giorno
Alguns Problemas Brinquedo
Xadrez
Jarro de Água
Lavrador, Lobo, Cabra e Maço de Couve
Missionários e Canibais
Jogo dos 15 (quebra cabeça do patrão)
Torre de Hanói
. . .
MEE
IA: MEE - F.Giorno
Representação do problema por Espaço de Estados
Análise do problema visando identificar necessidades especiais
Escolha e aplicação de técnicas de solução
Método do Espaço de Estados (MEE)
IA: MEE - F.Giorno
Representação do problema por Espaço de Estados – estados iniciais
– estados objetivos
– operadores
– restrições
Análise do problema visando identificar necessidades especiais
Escolha e aplicação de técnicas de solução
Método do Espaço de Estados (MEE)
IA: MEE - F.Giorno
Uma Solução no Espaço de Estados Conjunto de todos estados possíveis
Exemplo / Visualização: TH com 2 discos
• no de estados possíveis: 32 = 9
IA: MEE - F.Giorno
Espaço de Estados
• no de estados possíveis: 32 = 9 • no min de movimentações de discos: 22 - 1 = 3
Conjunto de todos estados possíveis
Exemplo / Visualização: TH com 2 discos - uma solução Estado1
Estado2 Estado3
Estado4: Solução
IA: MEE - F.Giorno
Representação do problema por Espaço de Estados – estados iniciais
– estados objetivos
– operadores
– restrições
Análise do problema visando identificar necessidades especiais – decomposição?
– retrocesso?
– incerteza?
– otimização?
– conhecimento?
– interação? . . .
Escolha e aplicação de técnicas de solução
Método do Espaço de Estados (MEE)
IA: MEE - F.Giorno
Característica Análise Decomposição Particionamento do EE em sub-espaços
correspondentes a sub-problemas
independentes ("dividir para conquistar")?
Recuperação de Recuperação de passos de iteração durante o
Passos de Solução processo de solução (uso de algoritmo de retrocesso)?
Incerteza Tratamento de incertezas associadas ao domínio
(abordagem de incertezas)?
Otimização Solução ótima ou uma solução viável é suficiente
(uso de técnicas de otimização)?
Conhecimento Papel desempenhado pelo conhecimento na solução
do problema? Corretude, completude e copnsistência
da Base de Conhecimento (BC)?
Interação Interação sistema - usuário em busca cooperativa de
solução?
Análise do Problema - Características Especiais
IA: MEE - F.Giorno
Problema do Caixeiro-Viajante
Tendo a sua cidade como base, um vendedor deve visitar uma única vez cada cidade de seu território de vendas antes de retornar à base. A distância entre todas as cidades são conhecidas.
Encontrar um itinerário que minimize a distância total a ser percorrida.
IA: MEE - F.Giorno
CV com 1 cidade: 1
CV com 2 cidades: 1-2-1
CV com 3 cidades: 1-2-3-1
1-3-2-1
CV com 4 cidades: 1-2-3-4-1
1-2-4-3-1
1-3-2-4-1
1-3-4-2-1
1-4-2-3-1
1-4-3-2-1
CV com 10 cidades: 362880 candidatos
CV com 30 cidades: 8.8E30 candidatos 1h CPU (mainframe)
CV com 31 cidades: 30h CPU (mainframe)
CV com 32 cidades: 330h CPU (mainframe)
CV com n cidades: (n-1)! candidatos
Problema do Caixeiro-Viajante - Candidatos à Solução
IA: MEE - F.Giorno
A representação do problema por meio de estados e
operadores conduz a uma árvore ou grafo no qual:
os estados são os nós da árvore ou grafo
os operadores são os arcos
a solução é algum caminho conectando o nó inicial ao nó objetivo
a solução do problema dado
passa a ser a
solução de um problema de busca em árvore ou grafo
IA: MEE - F.Giorno
Representação do problema por Espaço de Estados – estados iniciais
– estados objetivos
– operadores
– restrições
Análise do problema visando identificar necessidades especiais – decomposição?
– retrocesso?
– incerteza?
– otimização?
– conhecimento?
– interação? . . .
Escolha e aplicação de técnicas de solução – Gere e Teste (GT)
– Busca em Profundidade (BP)
– Busca em Amplitude (BA)
– Branch and Bound (BB)
– A* . . .
Método do Espaço de Estados (MEE)
IA: MEE - F.Giorno
Problema do Níquel e do Dime
Resolver o problema do Níquel e do Dime aplicando o MEE.
Dados:
Tabuleiro com 5 posições horizontais.
Configuração inicial: Níquel Níquel nil Dime Dime
Configuração final: Dime Dime nil Níquel Níquel
Movimentos possíveis:
Níquel só pode ser movido para a direita.
Dime só pode ser movido para a esquerda.
Níquel e Dime podem saltar 1 moeda adjacente se houver espaço vazio em seguida à moeda.
IA: MEE - F.Giorno
MEE - Extensão para EE Amplo
A extensão do MEE para a solução de problemas associados com EE de grande porte - problemas altamente combinatórios - envolve:
usar, de modo cooperativo, outras técnicas de solução de problemas:
– decomposição (“dividir para conquistar”)
– . . .
encontrar atalhos no EE para, a partir de um estado inicial, atingir um estado objetivo
Heurísticas
IA: MEE - F.Giorno
Heurística Técnica, sem base matemática firme, que permite
melhorar a eficiência de um processo de busca
métodos algoritmicos garantem produzir, em tempo finito, a solução correta ou ótima de um problema
métodos heurísticos aumentam a possibilidade de se encontrar uma solução aceitável de um problema
Vantagens
evitar explosão combinatorial
aumentar a chance de encontrar uma solução
Uso
nos operadores
nas técnicas de solução
IA: MEE - F.Giorno
Função de Avaliação
Determina a que ponto se está próximo da intenção perseguida. Em um jogo, representa “a vontade de ganhar”.
No caso da máquina, é possível construir um software que utilize uma função de avaliação determinada por uma intencionalidade bem definida.
No caso do cérebro, a intencionalidade muda conforme os problemas se apresentam.
– Devido a isso, o próprio cérebro cria a função de avaliação adequada a uma dada intencionalidade.
– De modo mais preciso, o cérebro deve poder apreciar se essa função de avaliação se adapta a intencionalidade dada.
– Por conseguinte, o cérebro deve ter possuir uma função de avaliação de funções de avaliação!?
Ref: Changeux,J-P e A.Connes, Matéria e Pensamento, Ed. da Unesp
IA: MEE - F.Giorno
Jogo das 8 Damas
No xadrez, a Dama (Rainha) é conhecida pela mobilidade: ela pode ser deslocada horizontal, vertical e diagonalmente.
Como dispor 8 Damas no tabuleiro de forma que elas não ameacem umas às outras?
IA: MEE - F.Giorno
Jogo das 8 Damas
Q
Q
Q
A B C
1 2
3 4
5 6 7 8
f(A) = 8
f(B) = 9
f(C) = 10 jogar em C
Seja f(X) = número total de células não-atacadas
IA: MEE - F.Giorno
Jogo do Patrão (solução com menor número de passos)
2 3
1 8 4
7 6 5
1 2 3
8 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
A B C
Estado Inicial Estado Objetivo
ou ou
IA: MEE - F.Giorno
2 3
1 8 4
7 6 5
1 2 3
8 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
A B C
Estado Inicial Estado Objetivo
ou ou Seja
h(X): no quadradinhos
fora de lugar
h(A) = 2
h(B) = 3
h(C) = 4
Jogo do Patrão (solução com menor número de passos)
IA: MEE - F.Giorno
Problema Bem Definido (PBD)
estados iniciais e objetivos são conhecidos
operadores são conhecidos
restrições são conhecidas
Problemas Mal Definidos (PMD) - problemas reais
alguns destes elementos não são conhecidos
associados a EE de grande porte (em geral)
MEE - Extensão para Problemas Reais
IA: MEE - F.Giorno
MEE - Extensão para Problemas Reais
Problema Bem Definido
MEE
Problema Bem Definido com EE de Grande Porte
MEE + heurísticas + outras técnicas
Problema Mal Definido (problema real)
MEE + heurísticas + outras técnicas
+ conhecimento (relativo ao domínio de problemas)
IA: MEE - F.Giorno
Sistema de Produção - componentes
BC MT
MI
Motor
ou
Mecanismo de Inferência
Base de Regras
(Base de Conhecimento)
Memória de Trabalho
IA: MEE - F.Giorno
Base de Regras (BC - Base de Conhecimento)
contém regras de produção ou de inferência com sintaxe:
SE < premissa > ENTÃO < ações ou conclusões >
Memória de Trabalho (MT)
área de trabalho contendo os dados que definem o estado corrente do problema
Motor ou Mecanismo de Inferência (MI)
interpreta as regras por meio de ciclos - em cada ciclo tem-se:
- reconhecimento: escolha das regras aplicáveis
- resolução de conflitos: seleciona uma regra entre as regras simultaneamente aplicáveis
- ação: executa (dispara) a regra selecionada, alterando o estado corrente do sistema
Sistema de Produção - componentes
IA: MEE - F.Giorno
Exercício Conforme visto, o MEE para a solução de
determinadas categorias de problemas:
pode ser estendido para resolver problemas reais por meio de: – apoio de outras técnicas de solução de problemas
– incorporação de heurísticas
– representação e processamento de conhecimento relativo ao domínio
pode ser implementado por meio de Sistemas de Produção
Mostre (por meio de texto, figura, esquema ...) como os elementos básicos do MEE estendido são acomodados em um Sistema de Produção.
IA: MEE - F.Giorno
Represente o problema
em termos de
estados e operadores.
Gere um
Espaço de Busca
e o examine.
Identifique
conhecimento
que possa ser
aplicado p/ reduzir
o Espaço de Busca.
Desenvolva uma
estrutura de
conhecimento
como uma mistura
de inferência e
representação.
Implemente como
um sistema, usando
lings / ferramentas
apropriadas.
Teste e revise.
O problema é passível
de solução algorítmica?
Problema
Sistemas Convencionais Sistemas OO puros . . .
SBCs
SBCOOs
Desenvolvendo Sistemas
sim não
Caminho
da EC
IA: MEE - F.Giorno
Classificação Heurística [Clancey, 1983]
Dados
Abstratos
Soluções
Genéricas
Dados Soluções
abstração
associação heurística
refinamento
IA: MEE - F.Giorno
Mapa Conceitual (MC) com foco em IA
Atividades:
Rever o MC coletivo efetuado em classe;
Efetuar o levantamento da lista (não-ordenada) de relações;
Rever a lista de relações e, conseqüentemente, o MC;
Elaborar um texto a partir da ordenação adequada dos elementos da lista de relações (obtendo então um resumo do assunto IA);
Rever o resumo obtido e, conseqüentemente, o MC;
Criar um ícone para o MC elaborado (se julgar necessário ara lembrança futura).
Recommended