borda - WordPress.com

Transcrição

Inteligência Artificial
Ronaldo F. Ramos, Dr.
[email protected]
Adaptado de : aima.cs.berkeley.edu
1
Visão Geral do Curso
1.  Conceito de IA, Histórico e Metas
2.  Agentes Inteligentes
3.  Solução de Problemas, Busca e Jogos
4.  Sistemas Lógicos, Conhecimento e Raciocínio
5.  Sistemas Baseados em Conhecimento.
6.  Planejamento
7.  Incerteza, Probabilidade e Teoria da Decisão
8.  Aprendizado
9.  Linguagem e Comunicação
10.  Percepção
11.  Robótica
12.  Questões Filosóficas
2
Bibliografia Básica
1.  Russel, Stuart J. & Norvig, Peter. Artificial Intelligence. 2a. Ed.
Elsevier,2003. Ou Inteligência Artificial. Tradução de publicare
consultoria, Ed CAMPUS, Rio de Janeiro, 2004.
2.  Rich, Elaine. Artificial Intelligence. McGraw-Hill, 1988 ou
Inteligencia Artificial. Tradução Newton Vasconcelos. McGrawHill, São Paulo, 1988 (Biblioteca do CEFET)
3.  Nolt, John. Lógica. Jonh Nolt & Denis Rohatyn: Tradução de
Mineko Yamashita. McGraw-Hill, São Paulo, 1991
4.  Schildt, Herbert. Artificial Intelligence Using C. McGraw-Hill,
Berkeley,CA. EUA, 1987. (Tem Tradução)
5.  Hegenberg, Leônidas Exercícios de Lógica. (Vários Vols)
Editora da USP. São Paulo, 1978
3
Bibliografia Básica – Cont.
6.  Ramos, Ronaldo. Sistemas Especialistas - Uma Abordagem
Baseada em Objetos. Dissertação de Mestrado da UFSC.
Florianópolis- SC, 1995. (Biblioteca do CEFET)
7.  Claudia, Marcus. Prolog Programming. Arity Corporation. 1986
8.  Waterman, Donald Arthur. A Guide to Expert Systems. Addison
Wesley, 1986.
9.  Barr, Avron & Feigenbaum. The Handbook of Artificial
Intelligence. (4 vols). Addison Wesley, 1986
10.  Fischler, Martin & Firschein, Oscar. Intelligence : The Eye, the
Brain and the Computer. Addison-Wesley, 1987
11.  Scott, A. Carlisle. A Pratical Guide to Knowledge Acquisition.
Addison Wesley, 1991
4
12.  Loesch, Claudio & Sari, Solange. Redes Neurais Artificiais
Fundamentos e Modelos. Editora da FURB. Blumenau-SC,
1996
13.  Hykin, Simon. Neural Networks: A Comprehensive
Foundation (2nd Edition). Prentice Hall. 1998. (Tradução em
português: Redes Neurais. Princípios e Práticas. Ed. Bookman)
14.  Freeman, James A. Neural networks : algorithms,
applications, and programming techniques. AddisonWesley, 1991
15.  Kovacs, Szolt. Redes Neurais Artificiais. Livraria da Física,
2002
16.  Frontino de Medeiros, Luciano. Redes Neurais em Delphi. Ed.
Visual Books, 2003.
5
17.  Mendes de Azevedo, Fernando. Redes Neurais com
Aplicações em Controle e Sistemas Especialistas. Ed. Visual
Books, 2001.
18.  Padua Braga, Antônio de. Redes Neurais Artificiais : Teoria e
Aplicações. Ed. LTC. 2000
19.  Barone, Dante. Sociedades Artificiais: A Nova Fronteira da
Inteligência nas Máquinas. Ed. Bookman. Porto Alegre - RS,
2003
20.  Ferber, Jacques. Les systèmes multi-agents vers une
intelligence collective. Intereditions. Paris. 1995
6
Bibliografia Recreativa.
21.  Greenfield, Susan A. Journey to the Centers of the Mind. W H.
Freedman and Company. N. Y. EUA, 1995
22.  Kovacs, Zsolt L. O Cérebro e Sua Mente. Uma introdução à
Neurociência Computacional. Edição Acadêmica. São Paulo
1997
23.  Lama, Dalai. A Arte da Felicidade. Ed. Martins Fontes. São
Paulo. 2000. (PRA DESOPILAR)
7
Pré-Requisitos
- 
- 
- 
- 
- 
- 
- 
Capacidade de Abstração
Raciocínio lógico
Conhecimentos Básicos em Matemática Incluindo Combinatória
(Arranjo, Combinação, Permutação, etc...)
Conhecimento básicos de ciência da computação incluindo
estruturas avançadas de dados (Pilhas, Filas, Árvores, Grafos)
Conhecimento Básico de Estatística e Probabilidade
Teoria da Complexidade (Análise Assintótica)
Introdução a Álgebra Linear (Manipulação de Matrizes)
8
1. Inteligência Artificial
! 
What Hell is That (Que diabo é isso)?
! 
Inteligência e racionalidade
! 
Histórico
! 
Escopo
! 
Paradigmas
9
1.1 Inteligência Artificial – What hell is that?(Diabéisso? )
Sistemas que pensam como seres humanos
O novo e interessante esforço para fazer os computadores pensarem ...
máquinas com mentes, mas no sentido total e literal .
(Haugeland)
Automatização de atividades que associamos ao pensamento humano,
atividades como a tomada de decisões, resolução de problemas,
aprendizado ...
(Bellman)
Sistemas que pensam racionalmente
O estudo das faculdades mentais pelo uso de modelos computacionais...
(Charniak)
O estudo das computações que tornam possível perceber, raciocinar e agir.
(Winston)
10
1.1 Inteligência Artificial – What hell is that?( Diabéisso? )
Sistemas que agem como seres humanos
A arte de criar máquinas que executam funções que exigem inteligência
quando executadas por pessoas...
(Kurzweil)
A arte de fazer com que os computadores realizem tarefas em que, no
momento, as pessoas são melhores
(Rich)
Sistemas que agem racionalmente
A inteligência computacional é o estudo do projeto de agentes inteligentes
(Poole)
11
1.2 Racionalidade?
Um sistema é racional se faz “tudo certo” com os dados que tem.
(Russel)
Nem sempre os seres humanos
são racionais!!!
Inteligente
Racional
Racionalidade = Inteligência Ideal.
12
1.3 Agindo de forma humana
Teste de Turing (1950) (Computer Machinery and Intelligence)
Máquinas podem pensar e agir de forma inteligente?
"  Previu que no ano 2000 máquinas teriam 30% de chance de enganar um
leigo por 5 minutos.
" Antecipou os argumentos da IA nos 50 anos seguintes.
" Sugeriu os principais componentes da IA: conhecimento, raciocínio,
linguagem, compreensão e aprendizagem.
Seis disciplinas da IA!!!!.
Probs. Não pode ser reproduzido ou analisado matematicamente.
13
1.3 Agindo de forma humana (cont.)
Seis disciplinas da IA!!!!.
# 
Processamento de linguagem natural
# 
Representação do conhecimento
# 
Raciocínio automatizado
# 
Aprendizado de máquina
# 
Visão de computador
# 
Robótica
14
1.4 Pensando de forma humana
- Revolução cognitiva (anos 60) – Psicologia do processamento da informação
(Em oposição ao comportamentalismo (behaviorism) ortodoxo)
- Necessidade do conhecimento científico sobre o funcionamento do cérebro.
-  Modelos (Abstração) ( Conhecimento ou Circuitos?)
-  Teste e previsão (compreensão) do comportamento humano
-  Identificação de informações neurológicas
-  Surgimento de duas novas áreas distintas da IA.
-  Ciências Cognitivas
-  Neurociências
- Ponto comun entre as duas novas áreas e IA. As Teorias disponíveis não
explicam, nem criam, algo semehante à inteligência humana geral.
15
1.5 Pensando Racionalmente (As leis do pensamento)
-  Aristóteles e as escolas gregas : Lógica. (A ciência do
raciocínio)
- A lógica é o ponto de ligação entre a matemática, a filosofia e a
I.A.
Problemas:
- Nem todo comportamento inteligente é mediado pela lógica.
-Suposição subjacente da IA-simbólica (Um sistema de símbolos
físicos pode representar a atividade inteligente geral)
-Quais os objetivos do pensar? Que pensamentos eu devo ter?
16
1.6 Agindo Racionalmente
Comportamento Racional
Fazer a Coisa Certa
(Otimização)
[Nem sempre envolve o ato de pensar]
(Ação reflexiva, por exemplo)
Toda arte e toda investigação, e da mesma forma, toda ação
e suas consequências são idealizadas visando algum bem.
Aristóteles (Ética a Nicômano)
17
1.7 Agentes Racionais
Um agente é uma entidade que percebe e age.
f : P* ! A
Onde: P* = Histórico de Percepções
A = Conjunto de Ações
IA (contemporânea) objetiva a construção de agentes racionais.
Objetiva-se que a ação de cada agente ou grupo de agentes seja a
melhor possível (ótima).
A racionalidade perfeita requer poder computacional indisponível no
momento.
18
1.9 Pré-História
Filosofia
Matemática
Lógica e raciocínio, a mente como um sistema físico,
fundamentos de linguagem, aprendizagem e racionalidade.
Representação formal e prova, algoritmos,
computabilidade, tratabilidade, probabilidade, etc.
Psicologia
Adaptação, percepção, controle motor
Economia
Teoria da decisão
Linguística
Gramática e representação do conhecimento
Neurociências
Atividade mental
Teoria do Controle
Estabilidade de sistemas e sistemas ótimos.
19
1.10 História
•  1943 – McCulloch & Pitts – Modelo matemático do neurônio
•  1950 – Alan Turing – Pai da ciência da computação – Teste de Turing
•  1956 – Darmouth Conference – John McCarthy cria o termo “Inteligência artificial”
•  1957 – GPS - General Problem Solver- Allen Newell e Herbert Simon
•  1958 – LISP – McCarthy
•  1966 – Eliza – Joseph Weizenbaum
•  1972 – Primeiros Sistemas Especialistas
•  1970s – Linguagem PROLOG – Franceses(Marseille) e Escoceses (Edinburgh)
•  1970s – MYCIN – PROSPECTOR - DENDRAL
•  1980s – Engenharia do conhecimento
•  1990s – Sistemas Híbridos – Inteligência Computacional - Agentes
•  2000s – Inteligência Ubíqua/Embarcada/Pervasiva
20
1.11 IA - Escopo
• Solução de problemas.
• Jogos
• Prova de Teoremas (lógica, incerteza e lógica nebulosa)
• Percepção (E reconhecimento de padrões)
• Visão
• Fala
• Compreensão de linguagem natural
• Resolução de problemas especializados (Incluindo sistemas especialistas)
• Matemática simbólica
• Diagnose (incluindo a diagnose médica)
• Análise química
• Projeto de engenharia
• Robótica e aprendizado de máquina
21
1.12. IA - Paradigmas
Paradigma Simbólico x Paradigma Conexionista
Suposições Subjacentes
1.  A atividade inteligente pode ser representada simbólicamente. O sistema de
símbolos físicos possui os meios necessários e suficientes para a ação
inteligente geral [Newell, 1976]
2.  A atividade inteligente é realizada pelo cérebro humano que é constituido
de uma rede de neurônios. Para se adquirir a verdadeira inteligência
artificial é necessário que se construam redes neurais (ou neuronais)
artificiais.
22
2. Agentes Inteligentes
! 
Agente e Ambiente
! 
Racionalidade
! 
Medida de desempenho, agente, ambiente, efetuador, sensor
! 
Tipos de ambientes
! 
Tipos de agentes
23
2.1 Agente e ambiente
Um agente pode ser: Ser humano, robô, termostato, sofbot, etc.
A função agente mapeia histórico de percepções em ações:
f : P* ! A
O programa agente “roda” sobre uma estrutura física para produzir f
24
2.1 Agente e ambiente (cont.)
Ex. O mundo do aspirador de pó.
Percepções: {(x,y) | x = A,B,C...(Local) e y = (LIMPO|SUJO)(Estado)}.
Ex. (A,SUJO)
Ações (Operadores): ESQUERDA, DIREITA, ASPIRAR, NULO
25
2.1 Agente aspirador de pó.
Sequência de Percepções
Ações
(A,LIMPO)
DIREITA
(A,SUJO)
ASPIRAR
(B,LIMPO)
ESQUERDA
(B,SUJO)
ASPIRAR
(A,LIMPO),(A,LIMPO)
DIREITA
(A,LIMPO),(A,SUJO)
ASPIRAR
(A,LIMPO), (A,LIMPO)
(A,LIMPO)
DIREITA
(A,LIMPO), (A,LIMPO)
(A,SUJO)
ASPIRAR
26
2.1 A função agente.
Ação f_agente_aspirador_de_po(local,status){
if (status == SUJO){
return ASPIRAR;
} elseif ( local == A){
return RIGHT;
} elseif (local == B){
return LEFT;
}
return NoOp;
}
27
2.2 Racionalidade
Medida de Desempenho (performance)
- Um ponto para cada quadrado limpo no tempo T
- Um ponto por cada quadrado em um Δt menos 1 por cada
movimento
- Penalização sempre que se tiver mais de K quadrados
sujos
Agente racional $ Maximizar a medida de desempenho
Racional
Onisciente
Racional
Clarividente
Racional
Bem sucedido
Racional $ Exploração, Aprendizado e Autonomia.
28
2.3 Método PEAS – Ambiente de tarefas
(P)  Performance
(Medida de desempenho)
(E) Ambiente
(A) Efetuadores(Atuadores)
(S) Sensores
29
2.3 Método PEAS – Ambiente de tarefas (cont.)
Tipo de Agente
Medida de
desempenho
Ambiente
Atuadores
Sensores
Sistema de
diagnóstico
Médico
Paciente
Saudável,
Minimizar
custos e
processos
judiciais
Paciente,
Hospital,
Equipe
Perguntas,
testes,
diagnósticos,
tratamentos,
indicações
Dispositivos de
Entrada
(teclado, etc)
para sintomas,
descobertas e
respostas dos
pacientes
Sistema de
Análise de
imagens de
satélites
Definição
correta da
categoria da
imagem
Link de
transmissão
Exibir a
categorização
da cena.
Matriz de pixels
coloridos.
Robôs de
seleção de
peças
Porcetagem de
peças em
bandejas
corretas
Correia
transportadora,
bandejas
Braços e mãos
articulados
Câmera,
sensores
angulados
articulados.
Controlador de
refinaria
Maximizar
pureza,
rendimento e
segurança
Refinaria,
Operadores
Válvulas,
bombas,
aquecedores
mostradores
Sensores de
temperatura,
pressão,
produtos
químicos.
30
2.3 (Programação multi agente - Método das vogais)
(E) Ambiente
(A) Agente
(I) Interações
(O) Organização
31
2.4 Tipos de ambientes
Observável = Completamente | Parcialmente
(O Agente conhece ou não o ambiente)
Determinístico versus Estocástico
(O próximo estado depende exclusivamente do estado anterior
e da ação do agente.)
Episódico ou sequencial
(As ações são independentes e afetam somente o próximo estado)
Estático x Dinâmico ou Semi-Dinâmico (Melhora do agente)
(O ambiente não muda enquanto o agente delibera sua ação)
Discreto ou contínuo.
(Relacionado com a passagem do tempo)
De agente simples ou multiagente.
Competitivo ou cooperativo.
32
2.4 Tipos de ambientes (cont)
Paciência
Compras via
Internet
Taxi
Automático
Observável
Sim
Não
Não
Determinístico
Sim
Parcialmente
Não
Episódico
Não
Não
Não
Estático
Sim
Semi
Não
Discreto
Sim
Sim
Não
Agente Único
Sim
Não
Não
O ambiente determina o projeto do agente.
Problemas do mundo real é parcialmente observável, estocástico,
Seqüencial, dinâmico, contínuo e multi-agente.
33
2.5 Tipos de agentes
• Agentes reativos simples
• Agentes reativos com estado
• Agentes baseados em modelos
• Agentes baseados em metas (objetivos)
• Agentes baseados em utilidade
• Agentes com aprendizagem(Todos Podem Ser)
• Outras classificações
• Agentes Inteligentes e Agentes Móveis
34
2.5.1 Agentes reativos simples
35
2.5.2 Agentes reativos com estado
36
2.5.3 Agentes baseados em objetivos
37
2.5.4 Agentes baseados em utilidade
38
2.5.5 Agentes com aprendizagem
39
2.5.6 Uma taxonomia global de agente inteligente
Ambiente
(Percepção)
+
Recursos
(Autonomia)
+
Comunicação
Com seus pares
+
Serviços
+
Reprodução
+
Inteligência
=
+
+
Mobilidade
Reatividade
=
=
Agente
Móvel
Agente
Reativo
Tendências
(Metas a realizar)
+
Agente
Inteligente
Inteligência coletiva
SMA – Sistemas Multi Agente
40
2.5.7 Agente inteligentes e Agentes Móveis
! 
! 
! 
! 
! 
! 
! 
Agente de rede
Agente comunicante
Agente autônomo
Agente inteligente
Agente adaptativo
Agente pró-ativo
Agente flexível
! 
Agente cognitivo
! 
Agente reativo
! 
Agente móvel
! 
Agente Intinerante
! 
Etc.
41
2.5.7 Agentes Inteligentes - Aplicações
%  Agentes locais
% 
% 
% 
% 
%  Agentes baseados em DAI
Assistentes pessoais
%  Conhecimento distribuído
Conselheiros pessoais
%  Agentes Móveis
Agendadores (Planejadores)
%  Telecomunicacões
Ferramentas de diagnóstico e
%  Comunicação pessoal
Solução de problemas
%  Gerenciamento de redes
%  Agentes em rede
%  Serviços sob demanda
%  Assistentes pessoais
%  Mercado eletrônico
%  Caixa de correio inteligente
%  Knowbot and Softbots
42
Exercício
Implementar em linguagem qualquer uma forma elementar
Desses agentes.
43
3. Solução de Problemas e Busca
! 
Agente para solução de problemas
! 
Tipos de problemas
! 
Formulação do problema
! 
Exemplos de problemas
! 
Algorítmos básicos de busca
! 
Recapitulando com o problema dos baldes
44
3.1 Agentes para solução de problemas
45
3.1 Exemplo : Romênia
De férias na Romênia. Atualmente “em Arad”
Formular Meta:
- Estar em Bucareste
Formular Problema:
- Estados: Diversas cidades
- Ações: Dirigir entre as cidades
Buscar a solução:
Seqüência de cidades, por exemplo:
Arad
Sibiu
Fagaras
Bucareste
46
3.1 Exemplo : Romênia
47
3.2 Tipos de problemas
Determinístico, completamente observável
Problema de estado único. O agente sabe exatamente em que estado o
mesmo estará; a solução é uma seqüência.
Não observável.
Problema sem sensores ou de conformidade. O agente não tem idéia de
sua localização. A solução (se existir) é uma seqüência.
Não determinístico e/ou parcialmente observável
Problema de contingência. As percepções fornecem informações novas
sobre o estado atual. A solução é uma árvore ou uma política. Freqüentemente
intercala-se busca com execução
Espaço de estados desconhecido
Problema de Exploração (“online”)
48
3.2 Exemplo do aspirador de pó.
49
3.3 Formulação do problema
Um problema é definido em 4 itens:
Estado Inicial, ex. Em(Arad)
Função Sucessor, conjunto de pares ordenados (Ação, Estado)
ex:
S(Arad) = {(Arad->Zerind, Zerind) ...}
Teste de Meta, pode ser:
Explícito: x = Bucareste
Implícito: não_sujo(x)
Custo do Caminho(Aditivo)
Soma das distâncias, número de ações executadas, etc.
C(x,a,y) = custo do passo. C>=0
Solução: Uma seqüência de ações que levam do estado inicial ao estado
meta.
50
3.3 Formulação do problema- Espaço de estados
Problemas do mundo real são excessivamente complexos:
& Espaço de estados é abstraído para a solução do problema.
(Abstrato) Estado = conjunto de estados reais
(Abstrato) Ação = combinação de ações (mais complexas)
do mundo real.
Ex. Arad->Zerind significa no mundo real um deslocamento
passando por vários postos, rodovias, etc.
Cada estado no mundo abstrato corresponde a um estado no
mundo real.
O problema abstraído deve ser mais fácil de solucionar que o
problema no mundo real.
51
3.3 Formulação do problema- Espaço de estados
52
3.3 Exemplo: Quebra cabeça de 8 peças
53
3.3 Exemplo: Montagem por braço robótico
54
3.3 Algoritmos de busca em árvore
55
3.3 Exemplo de busca em árvore
56
57
58
3.4 Implementação : Estados x Nós
59
3.5 Implementação : Busca em Árvore Geral
60
3.5 Estratégias de busca
61
3.5 Estratégias de busca sem Informação (CEGA)
62
3.5 Busca em Largura
63
64
3.5 Busca em Largura.
65
66
3.5 Propriedades da Busca em Largura
67
3.5 Busca com custo uniforme
Expande o nó de menor custo ainda não expandido
Implementação:
borda = fila ordenada pelo custo do caminho
Equivalente à busca em largura se todos os passos têm o mesmo custo.
Completa??:
Sim, se custo de cada passo é positivo > є
Tempo??:
O(b[C*/є]) onde C* é o custo da solução ótima
Espaço??:
O(b[C*/є])
Ótima??:
Sim
68
3.5 Busca em Profundidade
Expande sempre o nó mais profundo ainda não expandido.
Implementação:
borda = fila tipo LIFO (pilha), i. e., sucessores são colocados na frente da fila
(topo da pilha).
A
B
C
D
H
E
I
J
F
K
L
G
M
N
O
69
Implementação:
(topo da pilha).
A
B
C
D
H
E
I
J
F
K
L
G
M
N
O
70
Implementação:
(topo da pilha).
A
B
C
D
H
E
I
J
F
K
L
G
M
N
O
71
Implementação:
(topo da pilha).
A
B
C
D
H
E
I
J
F
K
L
G
M
N
O
72
Implementação:
(topo da pilha).
A
B
C
D
H
E
I
J
F
K
L
G
M
N
O
73
Implementação:
(topo da pilha).
A
B
C
D
H
E
I
J
F
K
L
G
M
N
O
74
Implementação:
(topo da pilha).
A
B
C
D
H
E
I
J
F
K
L
G
M
N
O
75
Implementação:
(topo da pilha).
A
B
C
D
H
E
I
J
F
K
L
G
M
N
O
76
Implementação:
(topo da pilha).
A
B
C
D
H
E
I
J
F
K
L
G
M
N
O
77
Implementação:
(topo da pilha).
A
B
C
D
H
E
I
J
F
K
L
G
M
N
O
78
Implementação:
(topo da pilha).
A
B
C
D
H
E
I
J
F
K
L
G
M
N
O
79
Implementação:
(topo da pilha).
A
B
C
D
H
E
I
J
F
K
L
G
M
N
O
80
3.5 Propriedades da Busca em Profundidade
Completa??:
Não. Falha em espaços com profundidade infinita, em laços.
- Deve ser modificada para evitar estados repetidos.
- É completa para espaços de estados finitos.
Tempo??:
O (bm) muito ruim no caso em que m > d
- Para soluções densas pode ser mais rápida que
busca em largura.
Espaço??: O (b * m), i.e., linear
Ótima??:
Não.
81
3.5 Busca com Profundidade Limitada.
= Busca em profundidade com limite l, i.e., nós com profundidade l
não possuem sucessores.
Implementação recursiva:
função BUSCA-EM-PROFUNDIDADE-LIMITADA(problema,limite) retorna
uma solução ou falha/
corte
retornar BPL-RECURSIVA(CRIAR-NÓ(ESTADO-INICIAL[problema]),problema,limite)
função BPL-RECURSIVA(nó,problema,limite) retorna uma solução ou falha/corte
corte_ocorreu? ' falso
se TESTAR-OBJETIVO[problema](ESTADO[nó]) então retornar SOLUÇÃO(nó)
senão se PROFUNDIDADE[nó] = limite então retornar corte
senão para cada sucessor em EXPANDIR(nó, problema) faça
resultado ' BPL-RECURSIVA(sucessor,problema,limite)
se resultado = corte então corte_ocorreu? ' verdadeiro
senão se resultado =/= falha então retornar resultado
se corte_ocorreu? então retornar corte senão retornar falha.
82
3.5 Busca por Aprofundamento Iterativo *
função BUSCA-POR-APROFUNDAMENTO-ITERATIVO(problema) retorna solução ou falha
entradas: problemas, um problema
para profundidade ' 0 até infinito faça
resultado ' BUSCA-EM-PROFUNDIDADE-LIMITADA(problema,profundidade)
se resultado =/= corte então retornar resultado
fim.
(iterativo =/= interativo)
83
3.5 Busca por Aprofundamento Iterativo l = 0
A
A
Limite = 0
84
Limite = 1
A
B
A
C
B
A
C
B
A
C
B
C
85
Limite = 2
A
A
B
C
D E
F
B
G
F
C
F
G
C
D E
F
D
C
E
B
G
D
C
E
F
A
B
G
A
B
A
B
E
C
D E
A
D
A
F
A
B
G
D
C
E
G
F
B
G
D
C
E
F
G
86
Limite = 3
A
C
B
E
D
H
I
J
F
K
L
G
M
N
O
87
3.5 Propriedades da BAI
Completa??:
Sim
Tempo??:
(d+1)*b0 + d*b1 + (d –1)*b2 + ... + bd = O (bd)
Espaço??:
O (b*d)
Ótima??:
Sim, se o custo do passo = 1
Pode ser adaptada para uma busca do custo
uniforme
Comparação com a busca em largura para b=10 e d = 5 a solução estando à direita
N(BAI) = 50+400+3.000+20.000+100.000 = 123.450
N(BL) = 10+100+1.000+10.000+100.000+999.990 = 1.111.100
88
3.5 Resumo dos Algoritmos de Busca Cega
Critério
Largura
Custo
Uniforme
Profundidade
Pronfundidade
Limitada
Aprofundamento
Iterativo
Completa
Sima
Sima,d
Não
Somente se
l >=d
Sima
Tempo
bd+1
b[C*/ є ]
bm
bl
bd
Espaço
bd+1
b[C*/ є ]
b*m
b*l
b*d
Ótima
Simc
Sim
Não
Não
Simc
a Completa
se b é finito; b custo do passo > algum valor positivo
є;
c
Ótima se os custos dos passos são iguais
89
3.5 Controle de estados repetidos
Repetição de estados pode levar um problema linear a uma
explosão combinatória (geração exponencial de nós).
A
A
B
B
A
C
...
...
....
A
B
B
90
3.5 Solução: Busca em Grafo
Função BUSCA-EM-GRAFO(problema,borda) retorna Solução/Falha
fechado ' um conjunto vazio
borda ' INSERIR(CRIAR-NÓ(ESTADO-INICIAL[problema]),borda)
repita
se borda == vazia então retornar Falha
nó ' REMOVE-FRENTE(borda)
se TESTE-DE-META[problema](ESTADO([nó]) então retornar nó
se ESTADO[nó] não em fechado
então
adicionar ESTADO[nó] a fechado
borda ' INSERIR-TODOS(EXPANDIR(nó,problema),borda)
fim-repita
fim.
91
3.5 Resumindo
• Formulação do problema requer abstração de detalhes do
mundo real para definir um espaço de estados que pode ser
explorado por um mecanismo de busca.
• Foram verificadas uma variedade de estratégias de busca sem
informação ou busca cega.
• A busca por aprofundamento iterativo utiliza apenas espaço
linear e não muito mais tempo que outras estratégias de busca
cega.
92
3.6 Recapitulando com o problema dos baldes.
Um exemplo de Técnica de IA em solução de problemas
Passo 1 – Compreensão do problema
Reservatório
4l
3l
Sejam dois baldes, um de 4l e outro de 3l , e uma bomba d´água. Os
baldes não possuem qualquer marcação. Como colocar exatamente 2l de
água no vasilhame de 4l?
93
Passo 2 – Abstração – Definição de um espaço de estados
Seja o conjunto de pares ordenados (x,y) tais que x representa o
conteúdo em l do balde de 4l e y o conteúdo do balde de 3. Logo Et
(Conjunto Espaço de Estados) sera :
Et = { (x,y) | x = 0,1,2,3,4 e y = 0,1,2,3}
Passo 3 – Definir o(s) estado(s) iniciai(s)
Ei = (0,0)
Passo 4 – Definir o(s) estado(s) meta(s)
Ei = (2,n) n Є { 0,1,2,3}
94
Passo 5 – Especificar um conjunto de regras descrevendo ações (operadores)
disponíveis.
1. 
2. 
3. 
4. 
5. 
6. 
7. 
(X,Y | X<4) ( (4,Y) = Encher o vasilhame de 4 litros
(X,Y | Y<3) ( (X,3) = Encher o vasilhame de 3 litros
(X,Y | X>0) ( (X-D,Y) = Despejar alguma água do vasilhame de 4 litros
(X,Y| Y>0) ( (X,Y-I) = Despejar alguma água do vasilhame de 3 litros
(X,Y| X>0) ( (0,Y) = Esvaziar o vasilhame de 4 litros
(X,Y| Y>0) ( (X,0)
= Esvaziar o vasilhame de 3 litros
(X,Y| X+Y>=4 ^ Y>0 ) ( (4,Y-(4-x)) = Despejar água do vasilhame de 3 l dentro do vasilhame de 4 l
até encher o vasilhame de 4 l
8.  (X,Y|X+Y >=3 ^ X> 0) ( (X-(3-Y),3) = Despejar água do vasilhame de 4l no de 3l até que o
vasilhame de 3l esteja cheio
9. 
(X,Y|X+Y <=4 ^ Y>0) ( (X+Y,0) = Despejar toda a água do vasilhame de 3l dentro do vasilhame de
4l
10.  (X,Y|X+Y >= 3 ^ X>0) ( (0,X+Y) = Despejar toda a água do vasilhame de 4 l dentro do vasilhame
de 3 l
95
Passo 6 – Usar as regras pra gerar uma árvore / grafo de busca e uma
estratégia de controle pra encontrar um caminho do estado inicial até o
estado meta.
3
Ei = (0,0)
Ei = (X,X)
2
Ea = (0,3)
X
Ei = (X,X)
9
X
Eb = (3,0)
1
Ei = (X,X)
2
En = (3,3)
...
7
Ey = (4,2)
Ei = (4,0)
...
5
Ek = (0,2)
9
Em = (2,0)
96
3.7 Exercício
Formalizar o problema dos missionários e dos canibais encontrando
uma solução.
Desc. do problema: 3 canibais e 3 missionários estão em uma
margem do rio e querem atravessá-lo em uma canoa que só cabe
duas pessoas por vez. Se em algum momento em alguma margem
existir mais canibais que missionários, os mesmos serão
devorados.
A meta é estabelecer a seqüência de viagens para que todos os
missionários cheguem com segurança à margem do outro lado.
97
3.8 Busca com Informação. (uso de heurísticas)
• Busca gulosa ou pela melhor escolha
• A*
• Heurísticas
• Subida da Encosta
• Têmpera Simulada
98
3.8 Revisão de Busca em Árvore
Função BUSCA-EM-ÁRVORE(problema,borda) retorna Solução/Falha
borda ' INSERIR(CRIAR-NÓ(ESTADO-INICIAL[problema]),borda)
repita
se borda == vazia então retornar Falha
nó ' REMOVE-FRENTE(borda)
se TESTE-DE-META[problema](ESTADO([nó]) então retornar nó
borda ' INSERIR-TODOS(EXPANDIR(nó,problema),borda)
fim-repita
fim.
$ Uma estratégia é definida pela ordem de expansão dos nós.
99
3.9 Busca Gulosa / Pela Melhor Escolha
Idéia básica: Utilizar uma função de avaliação para cada nó que
indique sua proximidade da meta. Trata-se de uma estimativa.
$ Expandir sempre o nó com melhor avaliação.
Implementação:
borda é uma fila ordenada em ordem decrescente pela função
de avaliação
Casos Especiais:
- Busca Gulosa
- A*
100
3.9 Busca Gulosa / Pela Melhor Escolha
101
3.9 Greedy Search (Busca Gulosa)
Função de avaliação h(n) (Heurística)
$ Estima o custo de n para a meta mais próxima
e.g. hDLR(n) = Distância em linha reta de n a Bucareste
$A busca gulosa, ou busca pela melhor escolha, expande o nó
que estaria mais próximo da meta.
102
3.9 Exemplo de Busca Gulosa
Passo 1
103
Passo 2
104
Passo 3
105
Passo 3
106
3.9 Propriedades da busca gulosa
Completa?? Não. Pode se perder nos laços. Será completa em
espaços de estados finitos com checagem de estados
repetidos.
Tempo?? O(bm), mas uma boa heurística pode diminuí-lo
sensivelmente.
Espaço?? O(bm) mantém todos os nós na memória
Ótima?? Não.
107
3.9 Busca A*
Idéia básica: Evitar expansão de caminho que são muito “custosos”
Função de avaliação f(n) = g(n) + h(n)
Onde:
g(n) = custo da origem até n
h(n) = estimativa do custo de n até a meta.
f(n) = estimativa do custo total do caminho da origem à
meta passando por n
A* usa uma heurística admissível, i. e., h(n) <= h*(n) é o
custo real de n. Também requer h(n) >= 0 e h(M) = 0
para toda meta M.
e.g., hdlr(n) nunca superestima a distância rodoviária
real.
Teorema: A busca A* é ótima.
108
3.9 Exemplo de Busca A*
109
110
111
112
113
114
3.10 Otimização de Busca A*
Suponha que alguma meta não-ótima (G2) foi gerada e está na
fila. Seja n un nó não expandido sobre o caminho mais curto para
a meta ótima (G1).
Início
n
G2
G1
f(G2) = g(G2) uma vez que h(G2)=0
>= g(G1) uma vez que G2 não é ótima.
>= f(n) uma vez que h é admissível
Observe que f(n)< f(n*)<f(G1)<f(G2)
f(n*) = custo real
Uma vez que f(G2) > f(n) , A* nunca expandirá G2
115
3.10 Otimização de Busca A*
Lema: A* expande nós em ordem crescente de f.
Gradualmente forma contornos em f. Um contorno i contém todos
os nós com f = fi onde fi < fi+1
116
3.10 Propriedades de Busca A*
Completa?? - Sim, a não ser que existam infinitos nós com f <= f(G)
Tempo?? - Exponencial em [erro relativo em h * comp. da solução]
Espaço?? - Matém todos os nós na memória
Ótima?? - Sim, não pode expandir fi+1 até que fi esteja terminada.
A* expande todos os nós com f(n) < C*
A* expande algum nó com f(n) = C*
A* não expande nós com
f(n) > C*
117
3.10 Prova de consistência
Uma heurística é consistente se
h(n) <= c(n,a,n’) + h(n’)
Se h é consistente teremos
f(n’) = g(n’) + h(n’)
= g(n) + c(n,a,n’) + h(n’)
>= g(n) + h(n) = f(n)
i.e., f(n) é não decrescente em qualquer
caminho
118
3.10 Exemplo de heurística Admissível
E.g., para o quebra cabeça de 8:
h1(n) = número de peças deslocadas
h2(n) = distância manhattan (número de posições que cada peça
está deslocada em relação à posição da meta)
119
3.10 Dominância
Se h2(n) >= h1(n) para todo n (ambas admissíveis) então h2
domina h1 e é melhor para a busca.
Custo de buscas típico:
d = 14 IDS = 3.473.941 nós
A*(h1) = 539 nós
A*(h2) = 113 nós
d = 24 IDS +/- 54.000.000.000 nós
A*(h1) = 39.135 nós
A*(h2) = 1.641 nós
120
3.10 Problemas Relaxados
Uma heurística admissível pode ser derivada do custo de uma
solução de uma versão relaxada do problema
Problemas relaxados são problemas com menos restrições
sobre as ações.
Se as regras do problema do quebra cabeça de 8 peças forem
relaxadas, poderíamos considerar que uma peça pode se
mover para qualquer quadrado adjacente e então a heurística
h2 nós dá a solução mais curta.
Ponto chave: O custo da solução ótima para um problema
relaxado não é maior que o de um problema real.
121
3.10 Algoritmos com Aperfeiçoamento Iterativo
•  Em muitos problemas de otimização o caminho é irrelevante.
•  O estado meta constitui a solução e não o caminho para se
chegar ao mesmo. (Ver problema das 8 rainhas)
•  Nestes casos, pode-se utilizar algoritmos de aperfeiçoamento
iterativo
•  Adequado tanto para busca “online” como “offline”
• BUSCA LOCAL.
-  Subida da encosta
-  Têmpera simulada
-  Busca em feixe (Algoritmos genéticos)
•  Princípio: Manter-se um único estado e tentar melhorá-lo
iterativamente.
122
3.10 Exemplo: Problema do caixeiro Viajante
• Iniciar com qualquer caminho fechado e ir trocando pares
123
3.10 Exemplo: Problema das n rainhas
• Colocar n rainhas em um tabuleiro n x n sendo que não poderão
ficar duas ou mais rainhas na mesma fila, coluna ou diagonal.
• Ação: mover a rainha para reduzir o número de conflitos
124
3.10 Heurística Subida da Encosta
Subir o Evereste em meio a um nevoeiro denso com crise de
amnésia.
Função SubidaDaEncosta(problema) retorna um máximo local
entradas: problema, um problema
variáveis locais:
corrente, um nó
vizinho, um nó
corrente ' CRIAR-NO(ESTADO-INICIAL[problema])
repita
vizinho ' mais valorado sucessor de corrente
se VALOR[vizinho] < VALOR[corrente]
retornar ESTADO[corrente]
corrente ' vizinho
fim do repita
Fim.
125
3.10 Heurística Subida da Encosta (cont)
Problemas:
-  Máximos locais (Cristas)
-  Planícies/Platôs
- Tamanho dos saltos em espaços contínuos/baixa convergência
Variantes: Subida da encosta estocástica
Subida da encosta pela melhor escolha
Subida da Encosta com reinício aleatório
Têmpera simulada
126
3.10 Heurística : Têmpera Simulada
Idéia: Sair dos máximos locais permitindo alguns movimentos ruins,
mas reduzir gradualmente sua ocorrência e tamanho
Função Tempera-Simulada(problema,escalonamento) retorna um estado solução
entradas: problema, um problema
escalonamento, um mapeamento de tempo para temperatura
variáveis locais:
corrente, um nó
proximo, um nó
T, uma “temperatura” que controla a probabilidade de passos descendentes
corrente ' CRIAR-NO(ESTADO-INICIAL[problema])
para t ' 1 até infinito faça
T ' escalonamento[t]
se T = 0 então retornar corrente
proximo ' um sucessor de corrente selecionado ao acaso
△E ' VALOR[proximo] – VALOR[corrente]
se △E > 0 entao corrente ' proximo
senão corrente ' proximo somente com probabilidade e△E/T
127
3.10 Heurística : Têmpera Simulada (propriedades)
% 
Pode-se provar que: se T decresce de forma
suficientemente lenta, a têmpera simulada encontrará
um ponto ótimo global com probabilidade próxima de 1
% 
Muito utilizada no projeto de layout de circuitos VLSI,
escalonamento de vôos, etc
128
3.10 Heurística : Busca em feixe local
% 
% 
% 
% 
Matém k estados em memória no lugar de apenas 1.
Inicia com k estados gerados aleatoriamente.
A cada iteração, todos os sucessores de todos os k
estados são gerados
Se algum deles é um estado meta, para; senão
selecionar os k melhores sucessores da lista
completa e recomeçar.
129
3.10 Algoritmos genéticos
% 
Os sucessores são gerados combinando dois estados “pais”.
% 
Começa com k estados gerados aleatoriamente (população).
% 
Um estado é representado como uma string sobre um alfabeto finito
(normalmente uma string de 0s e 1s)
% 
Função de avaliação (fitness). Valores mais altos para estados
melhores
% 
Produz uma nova geração por seleção, cruzamento (crossover) e
mutação.
130
%  Função
Fitness : número de pares que não se
atacam mutuamente(min = 0, max = 8 × 7/2 =
28)
%  24/(24+23+20+11) = 31%
%  23/(24+23+20+11) = 29% etc
131
132
3.10 Problemas de Satisfação de Restrições
Roteiro
% 
% 
% 
Problemas de Satisfação de restrições(PSR) (CSP)
Retrocesso (Backtracking) para PSRs
Busca Local para PSRs
133
Problemas de Satisfação de Restrições
% 
Problema de busca padrão:
% 
% 
PSR:
% 
% 
% 
Estado é uma caixa preta – qualquer estrutura de dados que
suporte função sucessores, função heurística e teste de meta.
Estado é definido por variáveis Xi com valores do domínio Di
Teste de meta é um conjunto de restrições especificando
combinações admissíveis de valores para subconjuntos de variáveis
Permite o uso de algoritmos de propósito geral com mais
eficiência que algoritmos de busca padrão
134
Problemas de Satisfação de Restrições.
Coloração de mapas
% 
% 
% 
% 
Variáveis WA, NT, Q, NSW, V, SA, T
Domínios Di = {vermelho,verde,azul}
Restrições: Regiões adjacentes devem ter cores diferentes
Ex., WA ≠ NT, ou (WA,NT) in {(vermelho,verde),(vermelho,azul),
(verde,vermelho), (verde,azul),(azul,vermelho),(azul,verde)}
135
%  Soluções
são conjuntos de atribuições completas
e consistentes, e.g., WA = vermelho, NT = verde,
Q = vermelho, NSW = verde,V = vermelho,SA =
azul, T = verde
136
% 
% 
PSR binário: cada restrição relaciona duas variáveis
Grafo de Restrições: Os nós representam as variáveis e os
arcos as restrições
137
% 
Variáveis discretas
% 
Domínios finitos:
% 
% 
% 
Domínios Infinitos:
% 
% 
% 
% 
n variáveis, tamanho de domíniod ! O(dn) atribuição completa
exs., PSR Booleano, incl. Satisfação não booleana(NP-completo)
Inteiros, strings, etc.
Exs., Escalas de trabalho, variáveis seriam dias de início/fim de cada
trabalho.
Necessita de uma linguagem de restrições, ex., InicioTrab1 + 5 ≤
InicioTrab3
Variáveis Contínuas
% 
% 
Ex., Horas de Início/Fim das observações do telescópio Hubble são
sincronizadas com variáveis astronômicas.
Restrições lineares solucionáveis em tempo polinomial usando
programação linear.
138
%  Restrições
Unárias envolvem somente uma
variável,
% 
Ex., SA ≠ verde
%  Restrições
% 
Binárias envolvem pares de variáveis,
Ex., SA ≠ WA
%  Restrições
de mais alta ordem envolvem 3 ou mais
variáveis,
% 
e.g., Restrições com colunas de criptoaritmética
139
% 
% 
% 
Variáveis: F T U W R O X1 X2 X3
Domínios: {0,1,2,3,4,5,6,7,8,9}
Restrições: TodosDiferentes (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, T ≠ 0, F ≠ 0
140
Problemas do Mundo Real
% 
Problemas de Atribuições
%  ex., quem ensina que classe.
% 
Problemas de escalas de horários
%  ex., Que classe é oferecida por quem e onde?
% 
Escalas de Transportes.
% 
Escalas de Fabricação.
% 
Problemas do mundo real envolvem variáveis
valoradas no mundo real.
141
Estados são definidos pelos valores atribuídos até aqui.
% 
% 
Estado Inicial: atribuição vazia { }
Função sucessor: Atribuir um valor a uma variável não atribuída
que não venha a gerar conflito com as atuais atribuições.
( Falha se não houver nenhuma atribuíção legal.
% 
Teste de meta: O conjunto de atribuíções é completo.
1. 
2. 
3. 
4. 
Sempre igual para todos os PSRs
As soluções aparecem na profundidade n com n variáveis
(Usar busca em profundidade
Caminho é irrelevante, então também pode-se utilizar a
formulação do estado completo.
5. 
b = (n - l )d na profundidade l, consequentemente a árvore
possui n! · dn folhas
142
% 
Atribuíção de Variáveis é comutativa, i.e.,
[WA = vermelho então NT = verde ] é o mesmo que [ NT =
verde então WA = vermelho ]
% 
A cada nó deve-se considerar apenas a atribuição de uma
única variável.
( b = d e existem d^n folhas (d = domínio máximo)
% 
Busca em profundidade para PSRs com atribuição à variável
única é chamada busca com retrocesso (backtracking search)
% 
A busca com retrocesso é a busca cega básica para PSRs
% 
Pode resolver o problema de n-rainhas com n ≈ 25
143
Busca com retrocesso
função PESQUISA-COM-RETROCESSO(psr) retorna uma solução ou falha
retornar RETROCESSO-RECURSIVO({},psr)
função RETROCESSO-RECURSIVO(atribuição, psr) retorna uma solução ou falha
se atribuição é completa então retornar atribuição
var ' SELECIONAR-VARIÁVEL-NÃO-ATRIBUIDA(VARIÁVEIS[psr],atribuição, psr)
para cada valor em VALORES-DE-ORDEM-NO-DOMINIO(var,atribuicao,psr) faça
se valor é consistente com atribuicao de acordo com RESTRIÇÕES[psr] então
adicionar { var = valor } a atribuição
resultado ' RETROCESSO-RECURSIVO(atribuição, psr)
se resultado <> falha então retornar resultado
remover { var = valor} de atribuição
retornar falha
144
145
146
147
148
Melhorando a eficiência do backtrack
% Métodos
de propósito geral podem dar
grandes ganhos em velocidade:
%  Qual
a próxima variável a ser atribuída?
%  Em qual ordem os valores devem ser tentados?
%  Podemos detectar falhas inevitáveis cedo?
149
% Varável
mais restrita:
escolher a variável com menos valores legais.
% Também
conhecida como heurística dos
valores restantes mínimos (VRM)(MRV)
150
Heurística de grau
% Desempate:
% Heurística
de grau ou da Variável com maior
número de restrições sobre variáveis não
atribuídas.
% Capaz
de chegar a uma solução sem
retrocesso.
151
Valor menos restritivo
% Escolher
o valor menos restritivo, ou seja,
escolher o valor que elimina o menor
número possível de escolhas para os
vizinhos.
% A combinação
dessas heurísticas torna
factível o problema das n rainhas com n =
1000
152
Checagem para a frente – Verificação Prévia
Idéia básica:
% 
% 
Manter lista de valores válidos remanescentes para variáveis não
atribuídas.
Terminar a busca quando não existir mais valores válidos.
153
Idéia básica:
% 
% 
atribuídas.
154
Idéia básica:
% 
% 
atribuídas.
155
% 
Idéia básica:
% 
% 
atribuídas.
156
Propagação de Restrições
% 
Verificação prévia propaga informações de variáveis
atribuídas para variáveis não atribuídas, mas não provê
detecção prévia para todas as falhas:
% 
NT e SA não podem ser azuis.
Propagation de restrições : reforça repetidamente restrições
locais
% 
157
Consistência de Arco
% 
% 
% 
A forma mais simples de propagação mantém os arcos
consistentes.
Um arco X (Y é consistente se e somente se
Para cada valor x de X existe um y permitido.
158
% 
% 
% 
consistentes.
159
% 
% 
% 
% 
consistentes.
Se X perde um valor, vizinhos de X precisam ser
rechecados.
160
% 
% 
% 
% 
% 
% 
consistentes.
Se X perde um valor , vizinhos precisam ser rechecados.
Consistência de arco detecta falhas mais cedo do que
verificação prévia.
Pode ser executada como um pré processador ou depois
161
de cada atribuição.
Algoritmo de consistência de arco
função CA-3(psr) retorna o PSR, possívelmente com domínios reduzidos
entradas: psr, um PSR binário com variáveis {x1,x2,...,xn}
variáveis locais : fila, uma fila de arcos, inicialmente todos arcos no psr
enquanto fila é não-vazia faça
(Xi,Xj) ' REMOVE-PRIMEIRO(fila)
se REMOVER-VALORES-INCONSISTENTES(Xi,Xj) então
para cada Xk em vizinhos[Xj] faça
adicionar (Xk,Xi) a fila
----------------------------------------------------------------------------------------------------------------------------função REMOVER-VALORES-INCONSISTENTES(Xi,Xj) retorna verdadeiro se removermos
um valor
removido ' falso
para cada x em DOMÍNIO[Xj] faça
se nenhum valor y em DOMÍNIO[Xj] permitir que (x,y) satisfaça à restrição entre Xi e Xj
então eliminar x de DOMÍNIO[Xi]; removido ' verdadeiro
retornar removido
% Complexidade
de tempo: O(n2d3)
162
% 
Busca Local
Subida da encosta e têmpera simulada normalmente
trabalham com estados completos, i.e., todas as variáveis
atribuídas.
% 
Para aplicar PSR:
%  Permitir estados com restrições não satisfeitas
%  Operadores reatribuem valores de variáveis
% 
Seleção de variáveis: selecionar aleatoriamente variáveis
com conflito
% 
Seleção de valor pela heurística dos conflitos mínimos:
% 
% 
Escolher valores que violam o menor número de restrições
i.e., Subida-Encosta com h(n) = Número total de restrições violadas
163
PSR (CSP) – Exemplo com 4 rainhas
% 
% 
% 
% 
% 
Estado: 4 rainhas em 4 colunas (44 = 256 estados)
Ações: mover as rainhas nas colunas
Teste de Meta: nenhum ataque.
Avaliação: h(n) = número de ataques
Dado estado inicial randômico pode-se solucionar n-rainhas
em tempo quase constante para um certo valor n com alta
probabilidade (e.g., n = 10,000,000)
164
Problemas de Satisfação de Restrições - Resumo
% 
PSRs são tipos especiais de problemas:
% 
% 
Estados são definidos por valores em um conjunto fixo de variáveis.
Teste de meta é definida por restrições nos valores das variáveis
% 
Retrocesso (Backtracking) = Busca em profundidade com uma
variável atribuída por nó.
% 
Ordenação de variáveis e heurísticas para seleção de valor ajuda
de forma significativa o processo.
% 
Verificação prévia previne atribuições que possam levar a uma
falha mais tarde.
% 
Propagação de restrições (ex. Consistência de arco ) ajuda a
restringir valores e detectar inconsistências.
% 
Heurística dos conflitos mínimos é normalmente efetiva na prática.
165
Busca Competitiva
Decisões ótimas
Poda α-β
Decisões imperfeitas em tempo real.
Jogos vs. Problemas de Busca
% 
Oponente Imprevisível ( Especificar um movimento para
cada resposta possível do oponente.
% 
Limites de Tempo ( Na impossibilidade de se encontrar a
meta, fazem-se aproximações.
167
Jogos vs. Problemas de Busca
Duas características novas:
% 
Oponente Imprevisível ( Especificar um movimento para
cada resposta possível do oponente.
% 
Limites de Tempo ( Na impossibilidade de se encontrar a
meta, fazem-se aproximações.
168
Árvore de jogos
169
Minimax
% 
% 
Perfeito para jogos determinísticos
Idéia : Escolher o movimento com o maior valor
minimax
170
Minimax algorithm
função DECISÃO-MINIMAX(estado) retorna uma ação
entrada: estado, estado corrente no jogo
v' VALOR-MAX(estado)
retornar a ação em SUCESSORES(estado) com valor v
---------------------------------------------------------------------------------------função VALOR-MAX(estado) retorna um valor de utilidade
se TESTE-TERMINAL(estado) então retornar UTILIDADE(estado)
v ' -∞
para a, s em SUCESSORES(estados) faça
v ' MAX(v, VALOR-MIN(s))
retornar v
---------------------------------------------------------------------------------------função VALOR-MIN(estado) retorna um valor de utilidade
v'∞
para a, s em SUCESSORES(estado) faça
v ' MIN(v,VALOR-MAX(s))
retornar v
171
Propriedades do minimax
% 
% 
% 
% 
% 
Completo? Sim para árvore finita
Ótimo Sim (contra um oponente ótimo)
Complexidade de Tempo? O(bm)
Complexidade de espaço? O(bm) (exploração em
profundidade)
Para Xadrez, b ≈ 35, m ≈100 ou outros jogos
“razoáveis”
( Solução exata inalcançável.
172
Poda α-β
173
Poda α-β (exemplo)
174
175
176
177
Propriedades da poda α-β
% 
A poda não afeta o resultado final
% 
Uma boa ordenação dos movimentos pode melhorar sua
eficácia.
% 
Com uma ordenação perfeita:
Complexidade de tempo = O(bm/2)
( duplica a capacidade de exame do minimax convencional
% 
% 
Trata-se de um exemplo do valor do raciocínio sobre que
computação é relevante(um tipo de meta-raciocínio)
178
Porque α-β?
% 
% 
% 
α é o valor do melhor
escolha (mais alto valor)
encontrado até o momento
ao longo do caminho de max
Se v é pior que α, max o
evitará
( podar essa ramificação
Define-se β de forma similar
(para o valor mais baixo)
para min.
179
O algoritmo α-β
função BUSCA-ALFA-BETA(ESTADO) retorna uma ação
entradas : estado, estado corrente do jogo
v' VALOR-MAX(estado, - ∞ ,+ ∞ )
retornar a ação em SUCESSORES(ESTADO) com valor v
----------------------------------------------------------------------------------------------------------------------função VALOR-MAX(estado,α, β) retorna um valor de utilidade
entradas: estado, estado corrente em jogo
α, o valor da melhor alternativa para max ao longo do caminho até estado
β, o valor da melhor alternativa para min ao longo do caminho até estado
v'-∞
v ' MAX(v,VALOR-MIN(s, α, β))
se v ≥ β então retornar v
α ' MAX(α,v)
retornar v
-------------------------------------------------------------------------------------------------------------------função VALOR-MIN(estado, α, β) retorna um valor de utilidade
entradas: estado, estado corrente em jogo
α, o valor da melhor alternativa para max ao longo do caminho até estado
β, o valor da melhor alternativa para min ao longo do caminho até estado
v'+∞
v ' MIN(v,VALOR-MAX(s, α, β))
se v ≤ α então retornar v
β ' MIN(β,v)
retornar v
180
Limite de recursos
Suponha que vc tem 100 segs e explore 104
nós/sec
( 106 nós por movimento
Abordagem padrão:
%  Teste de corte:
e.g., limite de profundidade(talvez busca quiescente)
(Impossibilidade de grandes mudanças próximas)
%  Função
de Avaliação
181
Função de Avaliação
% 
Para xadrez, normalmente, usa-se a soma de pesos
lineares das características observadas:
Eval(s) = w1 f1(s) + w2 f2(s) + … + wn fn(s)
% 
e.g., w1 = 9 com
f1(s) = (número de rainhas brancas) – (número de
rainhas pretas), etc.
182
Busca com corte
A busca com corte (MinimaxCutoff) é idêntica a minimax
(MinimaxValue) exceto por :
1. 
2. 
Terminal? Substituído por Corte?(Cutoff?)
Utilidade é substituído por Aval (Eval)
Funciona na prática?
bm = 106, b=35 ( m=4
Um jogador que faz busca em até 4 níveis é um jogador sem
esperança no xadrez.
% 
% 
% 
4 - níveis ≈ ser humano novato
8 - níveis ≈ um pc, um mestre
12 - níveis ≈ Deep Blue, Kasparov
183
Jogos Determinísticos na prática
% 
Damas: O software Chinook desbancou o reinado de 40 anos do
campeão mundial Marion Tinsley em 1994. Usou-se uma base de
dados de jogos perfeitos para todas as posições envolvendo menos de
8 peças.
% 
Xadrez: Deep blue derrota Kasparov em 1997 em seis partidas. O DB
é capaz de examinar 200 milhões de posições por segundo, usa uma
ulta sofisticada avaliação e métodos que permitem a busca chegar em
40 níveis.
% 
Othello: Campeões humanos se recusam a jogar contra computadores
pois os mesmos (computadores) são imbatíveis.
% 
Go: Campeões humanos se recusam a jogar contra computadores pois
os mesmos (computadores) são muito ruins. b > 300, então a maioria
dos programas usa bases de padrões para sugerir movimentos
plausíveis.
184
Sumário
% 
% 
% 
% 
Jogos são divertidos para se trabalhar com.
Eles ilustram importantes pontos de IA.
Pefeição é inatingível. Deve-se aproximar
É uma boa idéia pensar no que pensar.
185
Outras questões
% 
% 
% 
% 
Jogos não determinísticos com busca expectminimax.
Jogos de cartas
Jogos com múltiplos jogadores
Jogos com estratégias de cooperação para uma
meta razoavelmente comum.
186
Fim da parte I
187

borda - WordPress.com

Transcrição

Documentos relacionados

BRASILIDADE: O FILA BRASILEIRO por Luiz Henrique Costa e

PREFEITURA MUNICIPAL DE jABOTICABAL

orientações para o julgamento do original fila brasileiro – tópico 1.

ATA DE PROCESSO SELET Objeto: CONTRATRAÇÃO TEMPORÁ

O novo papel do FNMA

o handler e o fila brasileiro

Manual de Instruções REF.: 29834.01 Termômetro clínico digital de

A ORIGEM DA RAÇA FILA BRASILEIRO

c Cuidados que você deve ter com suas pilhas.

Flávio Borda d`Água, Universidade de Genebra