slaides de IA

Prévia do material em texto

INTELIGÊNCIA ARTIFICIAL 
 
Introdução à Inteligência Artificial 
Visão Geral da Área 
MOTIVAÇÃO (Quebra-cabeça) 
MOTIVAÇÃO (2 x 2) 
24 
24 
combinações 
possíveis 
MOTIVAÇÃO (3 x 3) 
24 
362.880 
combinações 
possíveis 
MOTIVAÇÃO (8 x 8) 
24 
1.2688 x 1089 
combinações 
possíveis 
MOTIVAÇÃO (8 x 8) 
 1.2688 x 1089 de combinações 
 
Testando um bilhão de combinações 
por segundo, cerca de 4 x 1069 
milênios... 
MOTIVAÇÃO 
Então, por que é que nós humanos, 
podemos resolvê-lo muito mais rápido? 
 
Porque utilizamos conhecimento do 
problema de forma inteligente. 
 
MOTIVAÇÃO 
Podemos programar um computador 
para utilizar conhecimento de um 
problema de forma inteligente? 
O QUE É IA? 
1. Pensar como humanos 
2. Pensar de forma racional 
3. Agir como humanos 
4. Agir de forma racional 
O QUE É IA? 
“IA Forte” versus “IA Fraca” 
 
Turing (1950): ao invés de perguntar se 
podem “pensar”, perguntar se podem 
“passar teste de comportamento”. 
 
TESTE DE TURING 
O examinador e o examinado 
“conversam” através de um teclado. 
 
Um sistema passa no teste se o 
interrogador não consegue dizer se é um 
humano ou um computador. 
 
HABILIDADES 
● Processamento de Linguagem Natural. 
● Representação do Conhecimento. 
● Raciocıńio Automático. 
● Aprendizado de Máquina. 
 
 
HABILIDADES 
● Processamento de Linguagem Natural. 
● Representação do Conhecimento. 
● Raciocıńio Automático. 
● Aprendizado de Máquina. 
 
 
ABORDAGENS EM IA 
1. Pensar como humanos - cognitiva 
2. Pensar de forma racional - lógica 
3. Agir como humanos - teste de Turing 
4. Agir de forma racional 
 
 
PRÉ-HISTÓRIA 
● Filosofia 
● Lógica 
● Matemática 
● Economia 
 
 
 
● Psicologia 
● Neurociência 
● Linguística 
● ... 
O INÍCIO (Neurônios Artificiais) 
Warren McCulloch e Walter Pitts (1943) 
 
● Cada neurônio poderia estar “ligado” 
ou “desligado”. 
● Baseado em conhecimento sobre 
fisiologia e as funções dos neurônios. 
 
O INÍCIO (Dartmouth) 
John McCarthy propõe encontro em 
1956 e usa o termo Inteligência Artificial. 
 
Participantes: Claude Shannon, Marvin 
Minsky, Herbert Simon, ... 
 
O INÍCIO (McCarthy) 
“Programs with Common Sense” - 1959 
 
Uso de lógica para resolver problemas. 
 
O INÍCIO 
Primeiros sistemas especialistas: uso de 
conhecimento para resolver problemas. 
 
Dendral (~1965), MYCYN (~1975) 
O INÍCIO 
Primeiro algoritmo de aprendizado de 
máquina: Tom Mitchell (~1978) 
 
APLICAÇÕES 
Veículos Autônomos 
Sistemas de Recomendação (Netflix, 
YouTube, Spotify, …) 
Jogos (DeepBlue, AlphaGo) 
... 
 
VISÃO GERAL DO CURSO 
Resolução de Problemas 
 
 Como representar um problema? 
 
 Como buscar soluções? 
VISÃO GERAL DO CURSO 
Busca por soluções 
 
 Sem informação sobre o domínio 
 
 Informada (heurísticas) 
VISÃO GERAL DO CURSO 
Resolução de Problemas 
 
 Usando lógica 
 
 Planejando ações 
PROBLEMAS 
Quebra-cabeças 
 
Xadrez 
 
Encontrar um caminho 
PROBLEMAS 
Estado Inicial 
Ações 
Teste de Objetivo 
Custo 
 
PROBLEMAS 
Solução: sequência de ações que levam 
de um estado inicial a um objetivo. 
 
Solução ótima: solução de custo mínimo 
EXEMPLO 
Chegar da minha casa ao trabalho. 
 
Ações possíveis: andar, pegar ônibus, 
dirigir, pegar bicicleta… 
 
Custo: financeiro, tempo, distância 
 
INTELIGÊNCIA ARTIFICIAL 
 
Introdução à Inteligência Artificial 
Visão Geral da Área 
• 1) Desenhe a porção do espaço de estados correspondente 
aos estados 1 a 15.Resposta 









• 2) Suponha que o estado objetivo seja 11. Liste a ordem em 
que os nós serão visitados no caso: a) da busca em largura 
b) da busca em profundidade limitada com limite 3; e c) da 
busca por aprofundamento iterativo.
• busca em largura 1,2,3,4,5,6,7,8,9,10,11
• Busca em profundidade limitada com limite 
3: 1,2,4,8,9,5,10,11
• Busca por aprofundamento iterativo: 1; 1,2,3; 
1,2,4,5,3,6,7; 1,2,4,8,9,5,10,11
• 

(Adaptado do livro de Russell e Norvig, exercício 3.9) Problema dos 
missionários e canibais: três missionários e três canibais estão em 
um lado de um rio, juntamente com um barco que pode conter 
uma ou duas pessoas. Descubra um meio de fazer todos 
atravessarem o rio, sem deixar que um grupo de missionários de 
um lado fique em número menor que o número de canibais.
• 1) Formule o problema precisamente (estados, ações, estado 
inicial, estado final). Trace um diagrama do espaço de estados 
completo.Uma representação possível: um estado é um vetor 
com três inteiros listando o número de missionários, canibais e 
barcos na margem inicial do rio. Sendo assim, o estado inicial é 
(3,3,1) e o estado objetivo é (0,0,0). O teste de objetivo verifica se 
o estado objetivo (0,0,0) foi alcançado. A função de custo tem 
valor 1 para cada ação. Os sucessores de um estado são todos 
os estados que movem uma ou duas pessoas e um barco de um 
lado para o outro, sem que o número de missionários de um lado 
fique menor do que o número de canibais. 

Espaço de estados:









• 2) Resolva o problema de forma ótima, utilizando um algoritmo de 
busca apropriado. Explique sua solução (basta dizer qual o 
algoritmo escolhido e mostrar a árvore de busca).Vamos usar 
busca em largura para encontrar a solução ótima. A árvore de 
busca desconsidera estados repetidos (rotulados com um *) e 
estados inválidos (com maior número de canibais do que 
missionários do mesmo lado).









• 3) É uma boa ideia verificar a existência de estados repetidos? 
Como ficaria a busca sem a verificação?Sim. Se não verificarmos 
os estados repetidos, cada nó marcado com * na árvore gerada 
na questão 4 seria expandido e geraria vários laços. 



•
 
INTELIGÊNCIA ARTIFICIAL 
 
Resolução de Problemas 
através de Busca 
 PROBLEMA 
Estado Inicial 
Ações 
Teste de Objetivo 
Custo 
 
PROBLEMAS 
Solução: sequência de ações que levam 
de um estado inicial a um objetivo. 
 
Solução ótima: solução de custo mínimo 
 ESPAÇO DE ESTADOS 
O conjunto de todos os estados 
acessíveis a partir de um estado 
inicial é chamado de espaço de 
estados. 
 
 ESPAÇO DE ESTADOS 
O espaço de estados pode ser 
interpretado como um grafo em que 
os nós são estados e os arcos são 
ações. 
 ESPAÇO DE ESTADOS 
Abstração do mundo real. 
 
Exemplo: Caminho de casa até o 
trabalho. Estados dados pela posição 
exata ou discretizados? 
 EXEMPLO (Aspirador de Pó) 
 EXEMPLO (Aspirador de Pó) 
• Estados: Posição do robô e sujeira (8) 
• Estado inicial: Qualquer um 
• Ações: esquerda (L), direita (R), 
aspirar(S) 
• Teste de objetivo: todas as posições 
estão limpas? 
• Custo do caminho: 1 cada passo 
 EXEMPLO (8 rainhas) 
 EXEMPLO (8 rainhas) 
• Estados: Qualquer disposição de 0 a 8 
rainhas 
• Estado inicial: Nenhuma rainha 
• Ações: colocar mais uma rainha 
• Teste de objetivo: 8 rainhas, 0 ataques 
 
64x63x...57 = 3x1014 possibilidades! 
 EXEMPLO (8 rainhas) 
• Estados: n rainhas nas n primeiras 
colunas, sem ataque 
• Ações: colocar uma rainha na próxima 
coluna, sem ataque. 
 
2.057 estados possíveis 
 
 BUSCA EM ÁRVORE 
Fronteira: nós a serem expandidos 
(começa com o estado inicial) 
 
A função Expande cria novos nós, 
usando as ações aplicáveis para gerar 
os estados correspondentes. 
 
 
 
 
 
 BUSCA EM ÁRVORE 
1. Retira o primeiro nó da fronteira (falha 
se vazia) 
2. Testa se é um estado final (solução): 
se for, devolve nó, sucesso 
3. Expande nó; 
4. Insere os nós gerados na fronteira e 
volta para o passo 1 
 
 ESTRATÉGIAS DE BUSCA 
A estratégia usada define a ordem 
em que os nós são expandidos, ou 
seja, retirados da fronteira. 
BUSCA CEGA (não informada) 
● Em Largura 
● Em Profundidade 
● Profundidade Limitada 
● Aprofundamento Iterativo 
 BUSCA EM LARGURA 
Nós são expandidos na ordem em 
que foram criados.BUSCA EM LARGURA 
 
 
 BUSCA EM LARGURA 
 
 
 BUSCA EM LARGURA 
 
 
 BUSCA EM LARGURA 
• Completa Se número de ações é finito 
• Ótima Se ações tem custo 1 
 
• Espaço mantém todos os nós na 
memória... 
 
 BUSCA EM PROFUNDIDADE 
O último nó criado é o primeiro a 
ser expandido. 
 BUSCA EM PROFUNDIDADE 
 BUSCA EM PROFUNDIDADE 
 BUSCA EM PROFUNDIDADE 
 BUSCA EM PROFUNDIDADE 
 BUSCA EM PROFUNDIDADE 
 BUSCA EM PROFUNDIDADE 
 BUSCA EM PROFUNDIDADE 
• Não é Completa (ramo pode ser 
infinito) 
• Não é ótima (encontra a primeira 
solução e não a de menor custo) 
 
Mas: só guarda nós do caminho atual! 
 
 PROFUNDIDADE LIMITADA 
Coloca um limite l na busca em 
profundidade. Nós de profundidade 
l são considerados como terminais. 
 PROFUNDIDADE ITERATIVA 
Repete a busca com profundidade 
limitada para valores de l cada vez 
maiores. 
Combina vantagens da busca em 
profundidade com a busca em 
largura! 
 PROFUNDIDADE ITERATIVA 
 PROFUNDIDADE ITERATIVA 
 PROFUNDIDADE ITERATIVA 
 PROFUNDIDADE ITERATIVA 
 PROFUNDIDADE ITERATIVA 
• Completa Se número de ações é finito 
• Ótima Se ações tem custo 1 
 
• Espaço mantém apenas o caminho 
atual na memória! 
 
 
 PROFUNDIDADE ITERATIVA 
Repete a busca com profundidade 
limitada para valores de l cada vez 
maiores. 
Combina vantagens da busca em 
profundidade com a busca em 
largura! 
 
INTELIGÊNCIA ARTIFICIAL 
 
Resolução de Problemas 
através de Busca 
 
 
INTELIGÊNCIA ARTIFICIAL 
 
Busca Informada 
Heurísticas 
 PROBLEMA 
Estado Inicial 
Ações 
Teste de Objetivo 
Custo 
 
 ESTADOS ⨯ NÓS 
PROBLEMAS 
Solução: sequência de ações que levam de um 
estado inicial a um objetivo. 
 
Solução ótima: solução de custo 
mínimo 
BUSCA INFORMADA 
Utiliza conhecimento específico sobre o 
problema para encontrar soluções de forma 
mais eficiente do que a busca cega. 
 
BUSCA INFORMADA 
Abordagem geral: busca pela melhor 
escolha. 
 
● Utiliza função de avaliação para nós. 
● Expande o nó com melhor avaliação. 
● Estratégia de busca depende 
da função. 
 
MELHOR ESCOLHA 
Ideia: função de avaliação f(n) dá 
uma estimativa do valor do nó n 
 
→Expandir nó mais desejável que 
ainda não foi expandido 
 
 
MELHOR ESCOLHA 
Implementação: 
 Ordenar nós na fronteira de acordo com f 
 
• Casos especiais: 
– Busca gulosa pela melhor escolha 
– Busca A* 
 
 
 
ROMÊNIA (Distância em KM) 
BUSCA GULOSA 
• Função de avaliação f(n) = h(n) (heurística) 
 = estimativa do custo de n até o objetivo 
 ex., hDLR(n) = distância em linha reta de n até 
Bucareste. 
 
• Busca gulosa pela melhor escolha 
expande o nó que parece mais 
próximo ao objetivo de acordo com 
a função heurística. 
ROMÊNIA (Distância Linha Reta) 
BUSCA GULOSA (Exemplo) 
BUSCA GULOSA (Exemplo) 
BUSCA GULOSA (Exemplo) 
BUSCA GULOSA (Exemplo) 
BUSCA GULOSA 
 
Segue o melhor passo considerando somente 
o estado atual. 
 
→Pode haver um caminho melhor 
seguindo algumas opções piores 
em alguns pontos da árvore de 
busca. 
 
BUSCA GULOSA 
 
Minimizar h(n) é suscetível a falsos inícios. 
 
– Ex. Ir de Iasi a Fagaras 
• Heurística sugerirá ir a Neamt, que 
é um beco sem saída. 
• Se repetições não forem detectadas 
a busca entrará em loop. 
BUSCA GULOSA 
 
• Não é Completa (pode ficar presa em laços, 
como, Iasi → Neamt → Iasi → Neamt) 
• Não é ótima 
 
• Espaço Mantém todos os nós na memória. 
 
BUSCA A* 
Ideia: evitar expandir caminhos caros 
 
Função de avaliação f(n) = g(n) + h(n) 
 
– g(n) = custo para alcançar n 
– h(n) = custo estimado de n até o 
objetivo 
– f(n) = custo total estimado do 
caminho através de n até o objetivo. 
BUSCA A* (Exemplo) 
BUSCA A* (Exemplo) 
BUSCA A* (Exemplo) 
BUSCA A* (Exemplo) 
BUSCA A* (Exemplo) 
BUSCA A* (Exemplo) 
HEURÍSTICA ADMISSÍVEL 
Uma heurística admissível nunca 
superestima o custo de alcançar o objetivo - 
ela é otimista. 
 
→ Exemplo: distância em linha reta 
nunca é maior que distância pela 
estrada. 
 
BUSCA A* 
• Completa 
• Ótima Se a heurística for admissível. 
 
• Espaço Mantém todos os nós na 
memória. 
 
 
BUSCA A* 
Nenhum outro algoritmo de busca ótimo tem 
garantia de expandir um número de nós menor 
que A*. 
 
Isso porque qualquer algoritmo que não 
expande todos os nós com f(n) menor 
que o custo ótimo corre o risco de 
omitir uma solução ótima. 
 
EXEMPLO (Heurísticas) 
EXEMPLO (Heurísticas) 
 
– h1(n) = número de peças fora da posição 
 
– h2(n) = distância “Manhattan” total (soma 
das distâncias de cada peça até a sua 
posição) 
EXEMPLO (Heurísticas) 
h1(S) = 6 
h2(S) = 4+0+3+3+1+0+2+2 = 15 
DOMINÂNCIA 
h2 sempre melhor que h1 pois ∀n h2(n) ≥h1(n) 
 
h2 domina h1 
 
Menos nós expandidos pela heurística 
dominante. 
(Escolhe nós mais próximos da 
solução.) 
DOMINÂNCIA 
 
Para profundidade 14: 
 
IDS = 3.473.941 nós 
A∗(h1) = 539 nós 
A∗(h2) = 113 nós 
 
 
DOMINÂNCIA 
 
Para profundidade 24: 
 
IDS = 54 bilhões de nós 
A∗(h1) = 39.135 nós 
A∗(h2) = 1.641 nós 
 
 
COMO CRIAR HEURÍSTICAS 
A solução de uma simplificação de um 
problema (problema relaxado) é uma heurística 
para o problema original. 
 
– Admissível: a solução do problema 
relaxado não vai superestimar a do 
problema original. 
EXEMPLO 
• h1 daria a solução para um problema em que 
as peças pudessem se deslocar para qualquer 
lugar. 
 
• h2 daria a solução para um problema 
em que as peças pudessem se mover 
um quadrado por vez em qualquer 
direção. 
 
COMO CRIAR HEURÍSTICAS 
Usar o custo da solução de um 
subproblema do problema original. 
 
 
INTELIGÊNCIA ARTIFICIAL 
 
Busca Informada 
Heurísticas 
• 	 (Adaptado de Russell e Norvig, ex. 5.8) Considere o seguinte 
jogo de dois jogadores, partindo do estado inicial ilustrado 
abaixo:
• 	 

O jogador A joga primeiro e os dois jogadores se revezam. Cada 
jogador deve mover sua ficha para um espaço adjacente aberto 
em qualquer sentido. Se o oponente ocupar um espaço 
adjacente, o outro jogador pode saltar sobre seu oponente até o 
próximo espaço aberto, se houver (por exemplo, se A estiver em 3 
e B estiver em 2, A poderá voltar a 1). O jogo termina quando um 
jogador chegar à extremidade oposta do tabuleiro. Se o jogador A 
alcançar o espaço 4 primeiro, o valor do jogo para A será +1; se o 
jogador B alcançar o espaço 1 primeiro, o valor do jogo para A 
será −1.

 
• 	 Desenhe a árvore de jogo completa, usando as 
convenções a seguir:
• 	 Escreva cada estado com (sA, sB), em que sA e 
sB denotam as posições das fichas.
• 	 Coloque cada estado terminal em um quadrado e 
escreva o seu valor em um círculo.
• 	 Insira os estados repetidos em quadrados duplos. 
Tendo em vista que não está clara a maneira de atribuir 
valores a esses estados, identifique cada estado com 
um “?”.
• 	 Resposta:







• 	 
•
•
• Agora marque cada nó com seu valor minimax propagado. 
Explique como você tratou os valores “?” e por que fez 
desse jeito.Os valores “?” são tratados supondo que um 
agente que possa escolher entre ganhar o jogo e entrar num 
estado “?” sempre escolherá ganhar. Isso quer dizer que 
min(-1,?) = -1 e max(+1,?) = +1. Se todos os sucessores são 
“?”, o valor propagado é “?”.



• 	 
• 	 
• 	 Explique por que o algoritmo minimax padrão falharia 
nessa árvore.O minimax padrão é uma busca em 
profundidade e entraria em loop infinito.



• 	 



• 	 (Adaptado de Russell e Norvig, ex. 5.16) A figura a seguir 
mostra a árvore de jogo completa para um jogo trivial:

 

Suponha que os nós folha sejam avaliados na ordem da esquerda 
para a direita e que, antes de um nó folha ser avaliado, nãosabemos nada sobre o seu valor, sendo que a faixa de valores 
possíveis é  − 
∞ 


 até  ∞ 




• 	 Copie a figura, marque o valor de todos os nós internos 
e indique a melhor jogada na raiz com uma seta.Resposta:





• 	 
• 	 
• 	 Dados os valores das primeiras seis folhas, será 
preciso avaliar a sétima e a oitava folhas?Sim, pois os 
valores da sétima e oitava folhas poderiam ser grandes o 
suficiente para dar mais do que 1,5 no nó de acaso da 
direita.



• 	 
• 	 
• 	 Dados os valores das sete primeiras folhas, será 
preciso avaliar a oitava folha?Não, pois após avaliar a sétima 
folha, já sabemos que min vai escolher no máximo -1, e, 
portanto, o nó de acaso da direita terá valor no máximo -0,5. 



• 	 
• 	 
• 	 Suponha que os valores dos nós folha estejam entre −2 
e 2, inclusive. Após as duas primeiras folhas serem 
avaliadas, qual é o intervalo de valor para o nó de acaso da 
esquerda?O intervalo é [0,2]. 



• 	 
• 	 
• 	 Quais as folhas que não precisam ser avaliadas se 
todos os valores estiverem em [-2,2]?A sexta, a sétima e a 
oitava folhas, pois, ao saber que o nó de acaso da esquerda 
vale 1,5 e que a quinta folha vale 0, já não há como fazer o 
nó de acaso da direita ser maior que 1,5.



•
 
INTELIGÊNCIA ARTIFICIAL 
 
 
Jogos Adversariais 
 
ATÉ AGORA... 
 
• Problemas sem interação com outro agente. 
• O agente possui total controle sobre suas ações e 
sobre o efeito de suas ações. 
• Muitas vezes encontrar a solução ótima é factível. 
2 
JOGOS VS. BUSCA 
 
O oponente é “imprevisível” 
 
– O agente precisa considerar todos 
os movimentos possíveis do 
oponente. 
3 
DECISÕES ÓTIMAS 
Consideraremos jogos com dois 
jogadores: 
– MAX e MIN 
– MAX faz o primeiro movimento e depois 
eles se revezam até o jogo terminar. 
 
4 
JOGOS COMO BUSCA 
– estado inicial 
– função sucessor (-> movimento, 
estado) 
– teste de objetivo 
– função utilidade: valor numérico 
para os estados terminais 
5 
EXEMPLO (Jogo da Velha) 
6 
ESTRATÉGIAS ÓTIMAS 
A solução ótima para MAX 
depende dos movimentos de MIN. 
 
– MAX busca estratégia de 
contingência especificando seu 
movimento no estado inicial e 
depois nos estados resultantes 
de cada movimento de MIN. 
7 
ESTRATÉGIAS ÓTIMAS 
A estratégia ótima pode ser 
determinada a partir do valor 
minimax de cada nó. 
 
 O valor minimax (para MAX) é a 
utilidade de MAX para cada estado, 
assumindo que MIN escolhe os 
estados mais vantajosos para ele 
mesmo. 
8 
MINIMAX 
Melhor estratégia para jogos 
determinísticos 
 
Ideia: escolher a jogada com o melhor 
retorno possível supondo que o 
oponente também vai fazer a melhor 
jogada possível. 
 
 
9 
MINIMAX 
 
VALOR-MINIMAX(n) = 
• UTILIDADE(n) se n é terminal 
• maxx∈Succ(n)Valor Minimax(x) se n é 
um nó MAX 
• minx∈Succ(n)Valor Minimax(x) se n é 
um nó MIN 
10 
EXEMPLO 
12 8 5 2 3 2 14 4 6 
max 
min 
ALGORITMO MINIMAX 
Busca completa em profundidade na árvore 
do jogo. 
 
• Completo? Sim (Se a árvore é finita) 
• Ótimo? Sim (contra um oponente ótimo) 
 
 
 
12 
ALGORITMO MINIMAX 
Busca completa em profundidade na árvore do jogo. 
 
Para xadrez: ações possíveis ≈ 35 
 profundidade da árvore ≈100 
 
 → solução exata não é possível 
13 
PODA α-β 
• Algoritmo minimax: no de estados do jogo é 
exponencial em relação ao no de movimentos 
• Poda α-β: 
– calcular a decisão correta 
sem examinar todos os nós 
da árvore. 
– retorna o mesmo que minimax. 
14 
PODA α-β 
15 
PODA α-β 
16 
PODA α-β 
17 
PODA α-β 
18 
PODA α-β 
19 
PODA α-β 
• Depende da ordem em que os 
sucessores são examinados. 
• Com a melhor ordem possível, 
dobra a profundidade da busca que 
conseguimos fazer. 
 
20 
DECISÕES IMPERFEITAS 
• Minimax gera o espaço de busca todo. 
• Poda α-β ainda tem que chegar até os 
estados terminais. 
 Ineficientes para jogos com 
muitos passos até os estados 
terminais (quase todos os jogos 
interessantes!). 
21 
DECISÕES IMPERFEITAS 
Ideia (Shannon, 1950): 
– Substituir utilidade por heurística e teste de 
objetivo por teste de corte. 
– Função de avaliação retorna uma 
estimativa da utilidade esperada. 
– Nós não terminais se transformam 
em nós terminais para minimax 
ou poda α-β. 
 
22 
DECISÕES IMPERFEITAS 
– Heurística deve ordenar nós-terminais 
da mesma forma que a função utilidade; 
– A computação deve ser rápida; 
– Em estados não terminais, avaliação 
deve estar relacionada com as chances 
reais de vitória. 
 
23 
DECISÕES IMPERFEITAS 
 
• Exemplo de características de estado 
para xadrez: peão=1, cavalo ou 
bispo=3, torre=5, rainha=9 
• Função de avaliação: função linear 
ponderada das características 
Aval(s) = w1 f1(s) + w2 f2(s) + … + wn fn(s) 
 
24 
DECISÕES IMPERFEITAS 
Ignora o fato de um bispo ser mais 
valioso no fim do jogo. 
 
• É possível usar combinações 
não lineares. 
– Par de bispos pode valer mais 
que o dobro do valor de dois 
bispos. 25 
DECISÕES IMPERFEITAS 
 
Características e pesos não fazem parte das 
regras do jogo. 
– Foram aprendidos ao longo dos anos. 
– Pesos podem ser estimados usando 
técnicas de aprendizado automático. 
26 
JOGOS DE AZAR 
 
• Elemento aleatório proveniente de 
jogo de dados, sorteio de cartas, etc. 
• O estudo de algoritmos para jogos 
com elemento aleatório é um passo 
em direção a algoritmos que podem 
ser aplicados no mundo real. 
27 
JOGOS DE AZAR 
• Árvore de jogo não determinístico 
deve incluir nós de acaso além de 
nós minimax. 
• Ramificações que saem dos nós de 
acaso denotam “resultados de dados 
possíveis” (anotadas com a 
probabilidade de cada mudança de 
estado). 
 
28 
EXEMPLO: GAMÃO 
Jogadas (5→10,5→11), (5→11,19→24), 
(5→10,10→16) e (5→11,11→16). 
29 
EXEMPLO: GAMÃO 
• [1,1],...,[6,6] tem probabilidade 1/36, todas 
as outras combinações têm probabilidade 
1/18. 
• Não é possível calcular o valor minimax 
exato, só o valor minimax esperado. 
30 
EXEMPLO: GAMÃO 
31 
EXPECTIMINIMAX 
32 
Resultado médio para jogadas ótimas: 
● Nós de acaso são como os min, mas o 
resultado é incerto. 
● Calcular utilidades esperadas (média 
ponderada dos filhos). 
 
EXPECTIMINIMAX 
33 
 
INTELIGÊNCIA ARTIFICIAL 
 
 
Jogos Adversariais 
 
Hunt the Wumpus
Arrows remaining: 5
About Hunt the Wumpus
The original version of Hunt the Wumpus was created by Gregory Yob in 1972. The original version was quite a bit different than this version: it was text based, and was based on
the vertices of a collapsed dodecahedron (rather than a grid). Each room (vertex) connected to 3 others (rather than four). You can read more about it in the author's Hunt the
Wumpus.
Rules (for this version)
1. There are 3 hazards:
1. A bottomless pit (you will feel a breeze nearby).
2. A colony of bats that will pick you up and drop you in a random space--including potentially deadly spaces (you will hear flapping nearby).
3. A fearsome, hungry, and unbathed wumpus (you will smell it nearby).
2. The wumpus is heavy; bats cannot lift him.
3. The wumpus is covered in suckers; he won't fall down the bottomless pit.
4. Firing an arrow that misses the wumpus may cause it to move.
5. You have 5 wumpus-piercing arrows.
6. You may find an arrow dropped by a previous hunter.
Keyboard Shortcuts
Use CTRL+arrow keys to move
Use ALT+arrow keys to fire arrows
Move (ctrl+arrow) Shoot (alt+arrow)
You are at 3,3 
You hear flapping 
http://www.atariarchives.org/bcc1/showpage.php?page=247
Javascript Keyboard Shortcuts from OpenJS
Play Hunt the Wumpus on twitter! Follow @wumpus_bot on twitter, and once it follows you back send a DM with the message "new game" to start playing. This is in beta, so let me
know if you notice any bugs: chris @ osric . com.
Find more games on osric.com.
http://www.openjs.com/scripts/events/keyboard_shortcuts/
http://www.openjs.com/https://twitter.com/wumpus_bot
https://osric.com/games/
INTELIGÊNCIA ARTIFICIAL 
 
Lógica em 
Inteligência Artificial 
 
ATÉ AGORA 
 
• Semana 3: conhecimento melhorando a busca. 
• Que tipo de conhecimento? 
2 
 
• Semana 3: conhecimento melhorando a busca. 
• Que tipo de conhecimento? Heurísticas. 
 
3 
ATÉ AGORA 
 
• Semana 3: conhecimento melhorando a busca. 
• Que tipo de conhecimento? Heurísticas. 
• Às vezes precisamos de mais 
flexibilidade... 
4 
ATÉ AGORA 
AGENTES LÓGICOS 
• Queremos representar o 
conhecimento formalmente. 
• Queremos poder deduzir 
conhecimento adicional ao 
acrescentar novas informações. 
• Sistemas Baseados em 
Conhecimento. 
5 
BASE DE CONHECIMENTO 
 
Conjunto de sentenças em uma linguagem 
formal (por exemplo, lógica proposicional) 
 
Sentenças podem ser adicionadas 
por uma operação TELL. 
6 
CONSULTAS À BASE 
 
A operação ASK pode ser usada para 
consultar a base de conhecimento. 
 
A resposta deve seguir do que está 
armazenado na base, eventualmente 
envolvendo inferências. 
7 
O MUNDO WUMPUS 
8 
Ambiente: 
– próximos ao wumpus: cheiro 
– próximos ao poço: brisa 
– quadrado do ouro: brilho 
– uma flecha somente 
– atirar mata wumpus, se em frente 
– pegar ou soltar ouro no 
mesmo quadrado 
 
9 
O MUNDO WUMPUS 
Desempenho: 
– ouro +1000, morte-1000 
– passo -1 , flecha -10 
Sensores: cheiro, brisa, brilho, 
impacto, grito 
Ações: esquerda, direita, pegar, 
soltar, atirar 
10 
O MUNDO WUMPUS 
EXPLORANDO O MUNDO 
11 
12 
EXPLORANDO O MUNDO 
13 
EXPLORANDO O MUNDO 
14 
EXPLORANDO O MUNDO 
15 
EXPLORANDO O MUNDO 
16 
EXPLORANDO O MUNDO 
17 
EXPLORANDO O MUNDO 
18 
EXPLORANDO O MUNDO 
WUMPUS EM LÓGICA 
Pij: existe um poço em [i, j] 
Bij: há brisa em [i, j] 
 
 ¬P11 
 ¬B11 
 B21 
 
 
19 
B 
WUMPUS EM LÓGICA 
Poços causam brisa em quadrados adjacentes 
 
 B11 ⇔ (P12∨ P21) 
 B21⇔ (P11∨ P22∨ P31) 
 
20 
WUMPUS EM LÓGICA 
Poços causam brisa em quadrados adjacentes 
 
 B11 ⇔ (P12∨ P21) 
 B21⇔ (P11∨ P22∨ P31) 
 
“Brisa se e somente se 
tem poço adjacente” 
21 
SEMÂNTICA 
Suponha que o agente 
verificou brisa em [1,2]. 
 
Antes de se mover 
novamente, ele quer saber 
se há poços em [2,1], [2,2] e 
[1,3]. 
22 
SEMÂNTICA 
Suponha que o agente 
verificou brisa em [1,2]. 
 
Antes de se mover 
novamente, ele quer saber 
se há poços em [2,1], [2,2] e 
[1,3]. 
 Há 8 possibilidades. 
23 
MODELOS 
24 
25 
¬P11 
¬B11 
 B21 
MODELOS 
26 
¬P11 
¬B11 
 B21 
 
B21⇔ 
P22∨ P31 
MODELOS 
MODELOS 
27 
¬P11 
¬B11 
 B21 
 
α1: ¬P21 
 
KB ⊨ α1 
MODELOS 
28 
¬P11 
¬B11 
 B21 
 
α2: ¬P22 
 
KB ⊭ α2 
PROPOSICIONAL? 
Poços causam brisa em quadrados adjacentes 
 B11 ⇔ (P12∨ P21) 
 B21⇔ (P11∨ P22∨ P31) 
 B31⇔ (P21∨ P32∨ P41) 
 B41⇔ (P31∨ P42) 
 B12⇔ (P11∨ P22∨ P13) 
 ... 
 
29 
PRIMEIRA ORDEM 
Poços causam brisa em quadrados adjacentes 
 
∀y(B(y) ⇔ ∃x(P(x) ∧ Adj(x,y))) 
30 
PRIMEIRA ORDEM 
Poços causam brisa em quadrados adjacentes 
 
∀y(B(y) ⇔ ∃x(P(x) ∧ Adj(x,y))) 
 
“Brisa se e somente se 
tem poço adjacente” 
31 
INTELIGÊNCIA ARTIFICIAL 
 
Lógica em 
Inteligência Artificial 
 
 
INTELIGÊNCIA ARTIFICIAL 
 
Representação de 
Conhecimento 
 
AGENTES LÓGICOS 
 
• Queremos representar o 
conhecimento formalmente. 
• Queremos poder deduzir 
conhecimento adicional ao 
acrescentar novas informações. 
• Sistemas Baseados em 
Conhecimento. 
O MUNDO WUMPUS 
PROPOSICIONAL? 
Poços causam brisa em quadrados adjacentes 
 B11 ⇔ (P12∨ P21) 
 B21⇔ (P11∨ P22∨ P31) 
 B31⇔ (P21∨ P32∨ P41) 
 B41⇔ (P31∨ P42) 
 B12⇔ (P11∨ P22∨ P13) 
 ... 
 
PRIMEIRA ORDEM 
 
∀y(B(y) ⇔ ∃x(P(x) ∧ Adj(x,y))) 
 
 
 
∀y(B(y) ⇔ ∃x(P(x) ∧ Adj(x,y))) 
 
∀x,y,x’,y’ (Adj([x,y],[x’,y’]) ⇔ 
 [x’,y’] ∈ {[x+1,y], [x-1,y],[x,y+1],[x,y-1]}) 
 
PRIMEIRA ORDEM 
 
Wumpus causa cheiro em quadrado adjacente: 
 
∀y(C(y) ⇔ ∃x(W(x) ∧ Adj(x,y))) 
 
 
 
PRIMEIRA ORDEM 
 
Wumpus pode estar em um único quadrado: 
 
 ∀x,y(W(x) ∧ W(y) ⇒ x=y) 
 
 
PRIMEIRA ORDEM 
 
Wumpus não pode estar em um poço: 
 
 ∀x(W(x) ⇒ ¬P(x)) 
 
 
PRIMEIRA ORDEM 
REPRESENTAÇÃO 
Lógica proposicional: somente fatos 
(verdadeiros ou falsos) 
 
Lógica de primeira ordem: objetos, 
propriedades, relações, funções... 
 
 
REPRESENTAÇÃO 
Objetos: agente, ouro, quadrado, Wumpus, … 
 
Propriedades: tem cheiro, tem brisa, … 
 
Relações: adjacente, localizado em, … 
 
Funções: coordenada x, coordenada y, … 
REPRESENTAÇÃO 
Lógica proposicional: somente fatos 
(verdadeiros ou falsos) 
 
Lógica de primeira ordem: objetos, 
propriedades, relações, funções... 
 
 
REPRESENTAÇÃO 
Lógica proposicional: somente fatos 
(verdadeiros ou falsos) 
 
Lógica de primeira ordem: objetos, 
propriedades, relações, funções... 
 
 (verdadeiro ou falso) 
REPRESENTAÇÃO 
Lógica proposicional: somente fatos 
(verdadeiros ou falsos) 
 
Lógica de primeira ordem: objetos, 
propriedades, relações, funções… 
 
 
 (objetos) 
 
 
ESCOLHAS 
W(x) ou LocalizadoEm(w,x) 
 
 Adj(x,y) ou Adj(x,y,x’,y’) 
 
 B(x) ou Percebe(a,x,b) 
 
 
ESCOLHAS 
W(x) ou LocalizadoEm(w,x) 
 
 Adj(x,y) ou Adj(x,y,x’,y’) 
 
 B(x) ou Percebe(a,x,b) 
 
 Decisões ontológicas! 
 
ENGENHARIA 
1. Definir uma tarefa; 
2. Agregar conhecimento relevante; 
3. Definir um vocabulário de predicados, 
funções e constantes; 
4. Codificar conhecimento geral 
sobre o domínio; 
 
ENGENHARIA 
 
5. Codificar uma descrição da instância 
específica do problema; 
6. Formular consultas ao procedimento 
de inferência e obter respostas; 
7. Depurar a base de conhecimento. 
EXEMPLO: somador 
EXEMPLO: somador 
1. Identificar a tarefa: 
– O circuito adiciona de maneira correta? 
– Se todas as entradas são 1, qual a saída 
de A2? 
– ... 
Não queremos saber: custo de 
produção, consumo de energia, ... 
 
EXEMPLO: somador 
2. Agregar conhecimento relevante: 
– Composto de cabos e portas 
– Tipos de portas (AND, OR, XOR, NOT) 
– Cada porta recebe sinais de 
entrada e produz um sinal de saída 
– ... 
Irrelevante: tamanho, forma, cor, ... 
 
EXEMPLO: somador 
3. Decidir um vocabulário: 
– Constantes: A1, A2, X1, X2, O1, C 
– Terminais: X1In1 vs. In(1, X1) 
– Connected(Out(1, X1 ), In(1, X2 )) 
– Sinal: constantes 1 e 0 e 
função Signal 
 
 
EXEMPLO: somador 
– Type(X1) = XOR (função e constante XOR) 
– Type(X1,XOR) (predicado e constante XOR) 
– XOR(X1) (predicado XOR) 
 
 
 
EXEMPLO: somador 
– Type(X1) = XOR (função e constante XOR) 
– Type(X1,XOR) (predicado e constante XOR) 
– XOR(X1) (predicado XOR) 
 
Função assegura um único tipo 
para cada porta! 
 
 
EXEMPLO: somador 
4.Codificar o conhecimento geral: 
– ∀t1,t2 Connected(t1,t2) ⇒ Signal(t1) = Signal(t2) 
– ∀t Signal(t) = 1 ∨ Signal(t) = 0 
– ∀t1,t2 Connected(t1, t2) ⇒ 
Connected(t2, t1) 
– ∀g Type(g) = OR ⇒ Signal(Out(1,g)) 
= 1 ⇔ ∃n Signal(In(n,g)) = 1 
 
EXEMPLO: somador 
5.Codificar a instância específica: 
Type(X1) = XOR Type(X2) = XOR 
Type(A1) = AND Type(A2)= AND 
 
Connected(Out(1,X1),In(1,X2)) 
Connected(Out(1,X1),In(2,A2)) 
Connected(Out(1,A2),In(1,O1)) 
EXEMPLO: somador 
6.Formular consultas e obter respostas: 
 
– Que combinações de entradas fariam a 
primeira saída de C (o bit de soma) 
ser 0 e a segunda saída de C 
(o bit de transporte) ser 1? 
 
EXEMPLO: somador 
6.Formular consultas e obter respostas: 
 
∃i1,i2,i3 Signal(In(1,C1))=i1 ∧ Signal(In(2,C1))=i2 
∧ Signal(In(3,C1))=i3 ∧ Signal(Out(1,C1))=0 
∧ Signal(Out(2,C1)) = 1 
 
Resposta: valores para i1, i2 e i3 
(ex. i1/1, i2/1, i3/0) 
 
EXEMPLO: somador 
7. Depurar a base de conhecimento: 
 
Pode ter havido omissões como 1 ≠ 0 
 
Testar perguntas com 
respostas conhecidas. 
 
INTELIGÊNCIA ARTIFICIAL 
 
Representação de 
Conhecimento 
 
 Linha de discussão: Fórum de dúvidas - Semana 6Inteligência Arti�cial - EEI101 - Turma 002 Fórum de discussão Fórum: Fórum de dúvidas - Semana 6
Linha de discussão: Fórum de dúvidas - Semana 6 
5 Postagem(ns) nesta linha de discussão 0 Não Lida 0 Respostas não lidas para mim
Selecionar: 
 
Todos Nenhum
Ações de mensagem  Expandir tudo Fechar tudo
Anônimo
 
Fórum de dúvidas - Semana 6
há 1 ano
Responder 
Discussões sobre o conteúdo da semana.
 
RE: Fórum de dúvidas - Semana 6
5 dias atrásGustavo Delgado Sacilotto 
Olá a todos!
Estamos iniciando a nossa penúltima semana de estudos.
O conteúdo referente a Semana 6 já está disponível. O tema dessa semana é Representação de conhecimento
E não se esqueçam da atividade avaliativa desta semana, para não perderam o prazo.
Quaisquer dúvidas que tiverem podem ser tiradas durante as Lives ou aqui no Fórum.
?
Atualizarr PesquisarF
https://ava.univesp.br/webapps/blackboard/execute/courseMain?course_id=_5968_1
https://ava.univesp.br/webapps/discussionboard/do/conference?action=list_forums&course_id=_5968_1&nav=discussion_board
https://ava.univesp.br/webapps/discussionboard/do/forum?action=list_threads&forum_id=_99743_1&conf_id=_29142_1&course_id=_5968_1&nav=discussion_board
javascript:expandAllMessagesInTheTree();
javascript:collapseAllMessagesInTheTree();
javascript:toggleReadByIcon('_315232_1')
javascript:toggleFlagByIcon('_315232_1')
Lembrando que vocês podem participar da live de todas as turmas (1 e 2). E devido ao feriado nesta semana, a nossa Live de quinta-
feira foi reagendada para terça-feira no mesmo horário. 
E em relação aos textos de apoio, eles servem como um complemento para o conteúdo, não sendo obrigatório a sua leitura.
Obrigado a todos e bons estudos!
Gustavo D. Sacilotto.
 
RE: Fórum de dúvidas - Semana 6
5 dias atrásRafael Fernandes Novais 
Prezado Gustavo, 
Boa noite!
No meu entendimento, a sentença III da questão anexa não pode estar correta. Pois ela afirma que existe um bloco "x", para todo
bloco "y" e "z", onde o bloco "x" está sobre o bloco "y" e o bloco "y" está sobre o bloco "z". Para que isso fosse verdade precisaríamos
ter tres blocos empilhados, afinal de contas, um bloco não pode estar empilhado sobre ele mesmo. Assim sendo, conforme a figura
mostra, se A está sobre B e B está sobre a mesa, e não sobre outro bloco, a sentença é falsa. Por gentileza, me ajude a entender a
materia se eu estiver enganado. Mas se voce concorda comigo, por favor, solicite a revisão do gabarito.
Muito obrigado Professor!
▲ Ocultar 2 respostas
 
RE: Fórum de dúvidas - Semana 6 
5 dias atrásRafael Fernandes Novais 
FECHAR
  inteligenciaArti�cialSemana6.jpg (90,507 KB)  
javascript:toggleReadByIcon('_315622_1')
javascript:toggleFlagByIcon('_315622_1')
javascript:toggleReadByIcon('_315623_1')
javascript:toggleFlagByIcon('_315623_1')
https://ava.univesp.br/courses/1/EEI101-2022S1B2-T002/db/_315623_1/inteligenciaArtificialSemana6.jpg
Selecionar: 
 
Responder Citar Autor do e-mail
 
RE: Fórum de dúvidas - Semana 6
4 dias atrásGustavo Delgado Sacilotto 
Boa tarde Rafael,
Vou estar repassando, ao supervisor, o seu questionamento sobre a questao desta semana.
Agradeço o empenho e bons estudos. 
Att
Gustavo D. Sacilotto
Todos Nenhum
Ações de mensagem  Expandir tudo Fechar tudo
← OK
javascript:toggleReadByIcon('_316030_1')
javascript:toggleFlagByIcon('_316030_1')
javascript:expandAllMessagesInTheTree();
javascript:collapseAllMessagesInTheTree();
 
INTELIGÊNCIA ARTIFICIAL 
 
Planejamento 
 
O QUE É UM PLANO? 
 
Objetivo: comprar leite, bananas e um martelo. 
 
Plano: ir ao supermercado, ir à seção de 
frutas, pegar as bananas, ir à seção de 
leite, pegar o leite, ir ao caixa, pagar tudo, 
ir a uma loja de ferramentas, ..., 
voltar para casa. 
 
2 
PLANO COMO BUSCA 
● Estado inicial: Em casa, sem objetos 
● Estado final: Em casa, com objetos 
● Operadores: Tudo o que o agente 
pode fazer 
● Heurística: Número de objetos 
ainda não obtidos. 
3 
LIMITAÇÕES 
 
● Considera as ações em sequência 
● Ramificação muito grande 
(muitas ações) 
● Não há uma abstração de 
estados parciais 
 
 4 
IDEIAS PRINCIPAIS 
Representação dos estados, objetivos e 
ações usando lógica (descrições parciais 
dos estados). 
 
Exemplo: 
Estado: Have (Milk) 
Ação: Buy (Milk) => Have (Milk) 
 
IDEIAS PRINCIPAIS 
Conectar diretamente estados (sentenças) e 
ações (pré condições + efeitos) 
 
 
Have(Money) Buy(Milk) Have(Milk) 
 
IDEIAS PRINCIPAIS 
Conectar diretamente estados (sentenças) e 
ações (pré condições + efeitos) 
 
 Have(Money) 
Have(Money) Buy(Milk) Have(Milk) 
 Have(Milk) 
IDEIAS PRINCIPAIS 
Conectar diretamente estados (sentenças) e 
ações (pré condições + efeitos) 
 
 Have(Money) 
Have(Money) Buy(Milk) Have(Milk) 
 Have(Milk) 
IDEIAS PRINCIPAIS 
Conectar diretamente estados (sentenças) e 
ações (pré condições + efeitos) 
 
 Have(Money) 
Have(Money) Buy(Milk) Have(Milk) 
 Have(Milk) 
IDEIAS PRINCIPAIS 
Adicionar ações ao plano quando necessárias. 
Ordem de planejamento ≠ ordem de execução 
Primeiro, o que é importante: Buy (Milk) 
 
Diminui fator de ramificação! 
IDEIAS PRINCIPAIS 
Aproveitar independência entre partes do mundo 
Subplano supermercado, 
Subplano loja de ferramentas. 
 
 
IDEIAS PRINCIPAIS 
Aproveitar independência entre partes do mundo 
Subplano supermercado, 
Subplano loja de ferramentas. 
 
 Não funciona sempre!!! 
LINGUAGENS 
● Suficientemente expressiva para descrever 
uma grande variedade de problemas. 
 
● Restritiva o bastante para permitir 
que algoritmos eficientes operem 
sobre ela. 
 
● Permitir decomposição 
em subproblemas. 
 
LINGUAGENS 
STRIPS: Stanford Research Institute Problem 
 Solver 
ADL: Action Description Language 
… 
PDDL: Planning Domain 
Definition Language 
CARACTERÍSTICAS 
Estado como conjunção de literais positivos. 
● literais proposicionais 
● literais de 1a ordem (sem variáveis e funções): 
Have(Milk) ∧ Have(Banana) 
 
Hipótese de mundo fechado: 
Literais não mencionados são falsos 
 
CARACTERÍSTICAS 
Objetivos: estados parcialmente especificados 
 
Um estado s satisfaz um objetivo 
g se s contém todos os literais de 
g (e possivelmente outros) 
 
CARACTERÍSTICAS 
Ação = Precondição + Efeito 
 
Action(Fly(p,from, to), 
 PRECOND: At(p,from) ∧ Plane(p) ∧ 
Airport(from) ∧ Airport(to) 
 EFFECT: ¬AT(p,from) ∧ At(p,to)) 
 
 
APLICAÇÃO DE AÇÕES 
Ação éaplicável em todos os estados que 
satisfazem as suas precondições. 
 
Resultado da execução de a em s é s’ 
obtido de s a partir dos efeitos de a: 
Literais positivos P adicionados a s’ 
Literais negativos ¬P removidos de s’ 
 
 
 
 
APLICAÇÃO DE AÇÕES 
 
s: Have(Money) 
 
Buy(Milk): pré-condição Have(Money) 
 efeito Have(Milk) ∧ ¬Have(Money) 
 
s’: Have(Milk) 
 
 
PLANEJAMENTO DE 
ORDEM PARCIAL 
 
Algoritmo que funciona 
independentemente sobre vários 
subobjetivos, os resolve com 
subplanos e depois combina os 
subplanos. 
 
PLANEJAMENTO DE 
ORDEM PARCIAL 
 
Estratégia do compromisso mínimo: 
retardar a escolha da ordem de 
aplicação de algumas ações 
durante a busca. 
 
 
EXEMPLO: calçar sapatos 
Goal(RightShoeOn ∧ LeftShoeOn) 
Init() 
 
Action(RightShoe, PRECOND: RightSockOn 
 EFFECT: RightShoeOn) 
Action(RightSock, PRECOND: 
 EFFECT: RightSockOn) 
 
 
Combinar duas sequências de ações: 
(1)leftsock, leftshoe 
(2)rightsock, rightshoe 
EXEMPLO: calçar sapatos 
PLANEJAMENTO DE 
ORDEM PARCIAL 
 
Qualquer algoritmo de planejamento 
que possa inserir duas ações em 
um plano sem especificar qual 
delas deve ser executada primeiro. 
 
ORDEM PARCIAL 
POP: BUSCA 
Estados são planos parciais. 
 
Cada plano possui 4 componentes: 
Um conjunto de ações (passos do plano) 
Um conjunto de restrições de ordem: A < B 
Um conjunto de vínculos causais 
Um conjunto de precondições abertas. 
 
POP: BUSCA 
Um plano é consistente se não 
existirem ciclos nas restrições de 
ordenação e nem conflitos com os 
vínculos causais. 
 
Um plano consistente sem 
precondições abertas é uma solução. 
 
POP: BUSCA 
 
Toda linearização de uma solução 
de ordem parcial é uma solução de 
ordem total cuja execução a partir 
do estado inicial alcançará um 
estado objetivo. 
RESOLVENDO POP 
O plano inicial contém Start e 
Finish, a restrição de ordenação 
Start < Finish, nenhum vínculo 
causal, e todas as precondições 
em Finish abertas. 
 
RESOLVENDO POP 
Função sucessor: 
● escolhe uma precondição aberta p em B 
● gera um plano sucessor para cada 
modo consistente de escolher 
uma ação que alcance p. 
● Teste de objetivo: nenhuma 
pré-condição aberta 
CONSISTÊNCIA 
● O vínculo causal A--p->B e a restrição de 
ordenação A < B são adicionados ao plano. 
 
● Resolver conflitos entre novos 
vínculos causais e B<C 
adicionando C<A ou A<B 
(exemplo - ir à loja de ferramentas 
antes de terminar compra no mercado) 
RESUMO DO PROCESSO 
Operadores em planos parciais 
Adicionar link de plano existente para 
precondição aberta. 
Adicionar um passo para satisfazer 
uma condição aberta. 
Ordenar dois passos para remover 
possíveis conflitos. 
 
RESUMO DO PROCESSO 
Gradualmente mover de planos 
incompletos para planos 
completos e corretos. 
 
Retroceder se uma condição 
aberta não for satisfazível ou se 
um conflito não tem solução. 
 
INTELIGÊNCIA ARTIFICIAL 
 
Planejamento 
 
 Linha de discussão: Fórum de dúvidas - Semana 7Inteligência Arti�cial - EEI101 - Turma 002 Fórum de discussão Fórum: Fórum de dúvidas - Semana 7
Linha de discussão: Fórum de dúvidas - Semana 7 
6 Postagem(ns) nesta linha de discussão 0 Não Lida 0 Respostas não lidas para mim
Selecionar: 
 
Todos Nenhum
Ações de mensagem  Expandir tudo Fechar tudo
Anônimo
 
Fórum de dúvidas - Semana 7
há 1 ano
Responder 
Discussões sobre o conteúdo da semana.
Citar
 
RE: Fórum de dúvidas - Semana 7
4 dias atrásGustavo Delgado Sacilotto 
Olá a todos!
Estamos iniciando a nossa última semana de estudos.
O conteúdo referente a Semana 7 já está disponível. O tema dessa semana é Planejamento: técnicas clássicas de construção de
sequências de ações.
Nesta semana também temos a nossa revisão de disciplina, na vídeo aula 08. Afinal a prova da disciplina já está marcada para a
próxima semana.
?
Atualizarr PesquisarF
https://ava.univesp.br/webapps/blackboard/execute/courseMain?course_id=_5968_1
https://ava.univesp.br/webapps/discussionboard/do/conference?action=list_forums&course_id=_5968_1&nav=discussion_board
https://ava.univesp.br/webapps/discussionboard/do/forum?action=list_threads&forum_id=_99744_1&conf_id=_29142_1&course_id=_5968_1&nav=discussion_board
javascript:expandAllMessagesInTheTree();
javascript:collapseAllMessagesInTheTree();
javascript:toggleReadByIcon('_318572_1')
javascript:toggleFlagByIcon('_318572_1')
E não se esqueçam da atividade avaliativa desta semana, para não perderam o prazo.
Quaisquer dúvidas que tiverem podem ser tiradas durante as Lives ou aqui no Fórum.
Lembrando que vocês podem participar da live de todas as turmas (1 e 2).
E em relação aos conteúdos de apoio, eles servem como um complemento para o conteúdo, não sendo obrigatório a sua leitura.
Obrigado a todos e bons estudos!
Gustavo D. Sacilotto.
▲ Ocultar 2 respostas
 
RE: Fórum de dúvidas - Semana 7
2 dias atrásRafael Fernandes Novais 
Olá!
Tudo bem?
Alguma devolutiva das questoes levantadas na semana 5?
Obrigado!
▲ Ocultar 1 resposta
 
RE: Fórum de dúvidas - Semana 7
1 dia atrásGustavo Delgado Sacilotto 
Olá Rafael,
Eu passei a devolutiva lá na semana em que você me mandou as questões, caso não consiga ver ou se tem alguma dúvida me
fala, por favor.
javascript:toggleReadByIcon('_320358_1')
javascript:toggleFlagByIcon('_320358_1')
javascript:toggleReadByIcon('_320762_1')
javascript:toggleFlagByIcon('_320762_1')
Selecionar: 
Obrigado
Gustavo D. Sacilotto.
 
RE: Fórum de dúvidas - Semana 7
4 dias atrásIgor Estevao Carrion 
Olá boa noite
Poderia disponibilizar um material de Revisao (em formato - texto) para facilitar a retomada dos conteúdos e auxiliar para a prova?
Grato.
▲ Ocultar 1 resposta
 
RE: Fórum de dúvidas - Semana 7
1 dia atrásGustavo Delgado Sacilotto 
Olá, boa noite,
Infelizmente eu só posso disponibilizar o que o professor autor publicou, que no caso é o vídeo com a revisão. 
Obrigado e bons estudos.
Gustavo D. Sacilotto.
Todos Nenhum
javascript:toggleReadByIcon('_318845_1')
javascript:toggleFlagByIcon('_318845_1')
javascript:toggleReadByIcon('_320897_1')
javascript:toggleFlagByIcon('_320897_1')
 Ações de mensagem  Expandir tudo Fechar tudo
← OK
javascript:expandAllMessagesInTheTree();
javascript:collapseAllMessagesInTheTree();
• 	 Descreva:
• 	 as seis ações de Shakey;Ações de Sharkey: 
• 	 Ir(x, y, r) 

Precondição: Em(Shakey, x)^Em(x, r)^Em(y, r)

Efeito: Em(Shakey, y)^¬Em(Shakey, x)
• 	 Empurrar(b, x, y, r)

Precondição: Em(Shakey, x)^Em(x, r)^Caixa(b)^Em(b, 
x)^Pode_empurrar(b)

Efeito: Em(b, y)^¬Em(b, x)^Em(Shakey, y)^¬Em(Shakey, 
x)
• 	 Subir(x, b)

Precondição: Em(Shakey, x)^Em(b, x)^Sobre(Shakey, 
Piso)^Caixa(b)

Efeito: Sobre(Shakey, b)^¬Sobre(Shakey, Piso)
• 	 Descer(b, x)

Precondição: Em(Shakey, x)^Em(b, x)^Sobre(Shakey, b) 

Efeito: Sobre(Shakey, Piso)^¬Sobre(Shakey, b)
• 	 Ligar(s, b)

Precondição: Sobre(Shakey, b)^Em(Shakey, x)^Em(s, 
x)^¬Ligado(s)

Efeito: Ligado(s)
• 	 Desligar(s, b)

Precondição: Sobre(Shakey, b)^Em(Shakey, x)^Em(s, 
x)^Ligado(s)

Efeito: ¬Ligado(s)
• 	 





• 	 o estado inicial da figura.Estado 
inicial:Em(Interruptor1, Sala1)^Em(Porta1, 
Sala1)^Em(Porta1, Corredor)^ 

Em(Interruptor2, Sala2)^Em(Porta2, Sala2)^Em(Porta2, 
Corredor)^ 

Em(Interruptor3, Sala3)^Em(Porta3, Sala3)^Em(Porta3, 
Corredor)^ 

Em(Interruptor4, Sala4)^Em(Porta4, Sala4)^Em(Porta4, 
Corredor)^ 

Em(Shakey, Sala3)^Em(Shakey, Xs)^Sobre(Shakey, Piso)^

Em(Caixa1, Sala1)^Em(Caixa2, Sala1)^Em(Caixa3, 
Sala1)^Em(Caixa4, Sala1)^

Em(Caixa1, X1)^Em(Caixa2, X2)^Em(Caixa3, X3)^Em(Caixa4, 
X4)^

Ligado(Interruptor1)^Ligado(Interruptor4)







• 	 Construa um planopara Shakey colocar a Caixa 2 na Sala 
2.Plano:

Ir(Xsl, Porta3, Sala3) 

Ir(Porta3, Porta1, Corredor) 

Ir(Porta1, X2, Sala1) 

Empurrar(Caixa2, X2, Porta1, Sala1) 

Empurrar(Caixa2, Porta1, Porta2, Corredor) 

Empurrar(Caixa2, Porta2, Xfinal, Sala2)



•