Aula 07 Revisão 1a Avaliação

Prévia do material em texto

1.1 INTRODUÇÃO E CONCEITOS BÁSICOS
1.2 AGENTES INTELIGENTES E MULTIAGENTES
1.3 ESTRATÉGIAS DE PESQUISA EM ESPAÇO DE ESTADOS
1.4 REPRESENTAÇÃO DO RACIOCÍNIO
1.5 ELABORAÇÃO DE PLANOS (PLANEJAMENTO)
1.6 SISTEMAS CONEXIONISTAS (REDE NEURAIS)
UNIDADE I
O QUE É IA?
ESTRATÉGIAS DE 
ESTUDO DE IA
MEDEM FIDELIDADE
AO DESEMPENHO 
HUMANO
MEDEM UM 
CONCEITO IDEAL DE 
INTELIGÊNCIA: 
RACIONALIDADE
SE REFEREM AOS 
PROCESSOS DE 
PENSAMENTO E 
RACIOCÍNIO
SISTEMAS QUE 
PENSAM COMO SERES 
HUMANOS
SISTEMAS QUE 
PENSAM DE FORMA 
RACIONAL
SE REFEREM AO 
COMPORTAMENTO
SISTEMAS QUE ATUAM
COMO SERES 
HUMANOS
SISTEMAS QUE ATUAM 
DE FORMA RACIONAL
TESTE DE TURING
• O TESTE DE TURING, PROPOSTO POR ALAN 
TURING (1950), FOI PROJETADO PARA FORNECER
UMA DEFINIÇÃO OPERACIONAL SATISFATÓRIA DE 
INTELIGÊNCIA.
• AO INVÉS DE PROPOR UMA LISTA LONGA DE 
QUALIFICAÇÕES EXIGIDAS PARA INTELIGÊNCIA.
• O TESTE SE BASEIA NA IMPOSSIBILIDADE DE 
DISTINGUIR ENTRE ENTIDADES INEGAVELMENTE
INTELIGENTES – OS SERES HUMANOS.
TESTE DE TURING
CAPACIDADES QUE UM COMPUTADOR DEVE TER PARA PASSAR 
NO TESTE:
PROCESSAMENTO DE LINGUAGEM NATURAL
• PERMITIR QUE ELE SE COMUNIQUE COM SUCESSO EM UM 
IDIOMA NATURAL
REPRESENTAÇÃO DE CONHECIMENTO
• ARMAZENAR O QUE SABE OU OUVE
RACIOCÍNIO AUTOMATIZADO
• USAR AS INFORMAÇÕES ARMAZENADAS PARA RESPONDER 
AS PERGUNTAS E TIRAR CONCLUSÕES
APRENDIZAGEM DE MÁQUINA
• SE ADAPTAR A NOVAS CIRCUNSTÂNCIAS, E DETECTAR E 
EXTRAPOLAR PADRÕES
TESTE DE TURING TOTAL
• NO TESTE DE "TURING TOTAL" INCLUI UM 
SINAL DE VÍDEO, PARA TESTAR HABILIDADES
DE PERCEPÇÃO:
• PARA SER APROVADO O COMPUTADOR PRECISA
TAMBÉM TER A SEGUINTES CAPACIDADES:
• VISÃO POR COMPUTADOR: PARA PERCEBER 
OBJETOS
• ROBÓTICA: PARA MANIPULAR OBJETOS E 
MOVIMENTAR-SE
DISCIPLINAS DA IA
• ESSAS SEIS DISCIPLINAS COMPÕEM A MAIOR
PARTE DE IA:
• PROCESSAMENTO DE LIGUAGEM NATURAL
• REPRESENTAÇÃO DO CONHECIMENTO
• RACIOCÍNIO AUTOMATIZADO
• APRENDIZADO DE MÁQUINA
• VISÃO DE COMPUTADOR
• ROBÓTICA
IA
FILOSOFI
A
MATEM
Á-
TICA
ECONO-
MIA
NEURO-
CIÊNCIA
PSICO-
LOGIA
ENG. DE 
COMPUT
A-DORES
TEORIA DE 
CONTROLE
LINGUÍS-
TICA
DISCIPLINAS QUE 
CONTRIBUIRAM COM A IA
DISCIPLINAS QUE 
CONTRIBUÍRAM COM A IA
• FILOSOFIA: POSSIBILITOU QUE A IA FOSSE CONCEBÍVEL 
POR CONSIDERAR QUE A MENTE É DE ALGUMA FORMA 
UMA MÁQUINA QUE:
 OPERA O CONHECIMENTO DECODIFICADO EM ALGUMA 
LINGUAGEM INTERNA; E,
 O PENSAMENTO PODE SER UTILIZADO PARA ESCOLHER QUE 
AÇÃO TOMAR.
• MATEMÁTICA: PERMITIU QUE A IA DESSE UM SALTO PARA 
A CIÊNCIA FORMAL, ATRAVÉS DA FORMALIZAÇÃO 
MATEMÁTICA DA LÓGICA, DA COMPUTAÇÃO E DA 
PROBABILIDADE.
DISCIPLINAS QUE 
CONTRIBUÍRAM COM A IA
• ECONOMIA: ATRAVÉS DO ESTUDO DE COMO AS PESSOAS 
FAZEM ESCOLHAS E QUE LEVAM A RESULTADOS 
PREFERENCIAIS, OU “UTILIDADE”. DESTA FORMA, 
CONTRIBUIU MUITO PARA A NOÇÃO DE AGENTES RACIONAIS.
• NEUROCIÊNCIA: PELA DESCOBERTA DE FATOS SOBRE COMO O 
CÉREBRO TRABALHA E A FORMA EM QUE SÃO SIMILARES E 
DIFERENTES DOS COMPUTADORES.
• PSICOLOGIA: O ESTUDO DE PSICOLOGIA POSSIBILITOU 
VISUALIZAR O CÉREBRO COMO UM DISPOSITIVO DE 
PROCESSAMENTO DE INFORMAÇÕES. ADOTA A IDEIA QUE 
HUMANOS E ANIMAIS PODEM SER CONSIDERADOS MÁQUINAS
DE PROCESSAR INFORMAÇÃO.
DISCIPLINAS QUE 
CONTRIBUÍRAM COM A IA
• ENGENHARIA DE COMPUTADORES: O COMPUTADOR TEM 
SIDO O ARTEFATO PREFERIDO, E SUA RÁPIDA 
EVOLUÇÃO TECNOLÓGICA TEM CONTRIBUÍDO
SIGNIFICATIVAMENTE PARA O AVANÇO DA IA, ASSIM COMO 
A ÁREA DE SOFTWARE.
• TEORIA DO CONTROLE E CIBERNÉTICA: POSSIBILITOU 
QUE OS ARTEFATOS POSSAM SER OPERADOS SOB SEU 
PRÓPRIO CONTROLE.
• LINGUÍSTICA: MOSTRA A IMPORTÂNCIA DA CRIATIVIDADE 
NA LINGUAGEM, SUA TEORIA ERA FORMAL O BASTANTE 
PARA PODER, A PRINCÍPIO, SER PROGRAMADA.
1.2 Agentes Inteligentes e 
Multiagentes
AGENTES E AMBIENTES
A
M
B
IE
N
T
E
?
Agente
SENSORES
ATUADORES
AGENTES E AMBIENTES
• UM AGENTE ROBÓTICO PODERIA TER COMO 
SENSORES:
CÂMERA
DETECTOR DE INFRAVERMELHO
AGENTES E AMBIENTES
• UM AGENTE ROBÓTICO TEM COMO ATUADORES:
AGENTES E AMBIENTES
• UM AGENTE DE SOFTWARE:
• RECEBE ENTRADAS SENSORIAIS:
 SEQUÊNCIAS DE TECLAS DIGITADAS
 CONTEÚDO DE ARQUIVOS
 PACOTES DE REDE
• ATUA SOBRE O AMBIENTE ATRAVÉS DA:
 EXIBIÇÃO DE CONTEÚDO NA TELA
 GRAVAÇÃO DE ARQUIVOS
 ENVIO DE PACOTES NA REDE
AGENTES E AMBIENTES
• MATEMATICAMENTE, O COMPORTAMENTO DO 
AGENTE É DESCRITO PELA FUNÇÃO DE AGENTE
QUE MAPEIA QUALQUER SEQUÊNCIA DE 
PERCEPÇÕES ESPECÍFICA PARA UMA AÇÃO.
AGENTES E AMBIENTES
\ \A B
SEQUÊNCIA DE PERCEPÇÕES AÇÃO
[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
...
• MATEMATICAMENTE, O COMPORTAMENTO DO 
AGENTE É DESCRITO PELA FUNÇÃO DE AGENTE
QUE MAPEIA QUALQUER SEQUÊNCIA DE 
PERCEPÇÕES ESPECÍFICA PARA UMA AÇÃO.
BOM COMPORTAMENTO DO AGENTE
• UM AGENTE RACIONAL É AQUELE QUE FAZ TUDO CERTO!
• NÃO EXISTE UMA MEDIDA FIXA APROPRIADA PARA TODOS OS 
AGENTES;
• A MEDIDA DE DESEMPENHO DEVE ESTAR BASEADA NO 
RESULTADO DESEJADO NO AMBIENTE E NÃO NO 
COMPORTAMENTO ESPERADO DO AGENTE.
• PARA SABER O SUCESSO DO AGENTE, DEVE-SE CRIAR UM 
MÉTODO PARA MEDIR O SEU SUCESSO, ATRAVÉS DA 
DEFINIÇÃO DE UM AMBIENTE DE TAREFA.
RACIONALIDADE
• A RACIONALIDADE DO AGENTE DEPENDE DE QUATRO
FATORES:
 A MEDIDA DE DESEMPENHO, QUE DEFINE O CRITÉRIO DE 
SUCESSO;
 O CONHECIMENTO ANTERIOR, QUE O AGENTE TEM DO 
AMBIENTE;
 AS AÇÕES, QUE O AGENTE PODE EXECUTAR;
 A SEQUÊNCIA DE PERCEPÇÕES DO AGENTE ATÉ O MOMENTO.
• O AMBIENTE DE TAREFA ABRANGE ESSES QUATRO FATORES.
AMBIENTE DE TAREFA
ESPECIFICAÇÃO DE UM AMBIENTE DE TAREFA 
DE UM MOTORISTA DE TAXI AUTOMATIZADO:
MEDIDA DE DESEMPENHO: SEGURANÇA, DESTINO, 
CONFORTO, RENDIMENTO, ...
CONHECIMENTO DO AMBIENTE: RUAS, ESTRADAS, 
TRÁFEGO, PEDESTRES, TEMPO, ... 
ATUADORES: DIREÇÃO, ACELERADOR, CAMBIO, 
FREIOS, ... 
SENSORES: VELOCÍMETRO, SENSORES DO MOTOR, 
GPS, ...
AMBIENTE DE TAREFA
ESPECIFICAÇÃO DE UM AMBIENTE DE TAREFA 
CONTROLADOR DE REFINARIA:
MEDIDA DE DESEMPENHO: MAXIMIZAR A PUREZA, 
RENDIMENTO, SEGURANÇA, ...
CONHECIMENTO DO AMBIENTE: REFINARIA, 
OPERADORES, ...
ATUADORES: VÁLVULAS, BOMBAS, AQUECEDORES, 
MOSTRADORES, ... 
SENSORES: SENSORES DE TEMPERATURA, 
PRESSÃO, PRODUTOS QUÍMICOS
ESTRUTURA DE AGENTES
• O TRABALHO DA IA É 
PROJETAR O PROGRAMA DE 
AGENTE QUE IMPLEMENTA A 
FUNÇÃO DE AGENTE QUE 
MAPEIA PERCEPÇÕES EM 
AÇÕES;
• SUPOMOS QUE ESSE
PROGRAMA SERÁ
EXECUTADO EM ALGUM TIPO
DE DISPOSITIVO DE 
COMPUTAÇÃO COM 
SENSORES E ATUADORES
FÍSICOS, AO QUE CHAMAMOS
DE ARQUITETURA;
SEQUÊNCIA DE PERCEPÇÕES AÇÃO
[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
...
ESTRUTURA DE AGENTES
FUNÇÃO
DE
AGENTE
PROGRAMA 
DE 
AGENTE
ARQUITETURA
SENSORES ATUADORES
AGENTE = ARQUITETURA + PROGRAMA
PERCEPÇÃO AÇÃO
PERCEPÇÃO AÇÃO
ESTRUTURAS DE AGENTE
• A ARQUITETURA:
 TORNA AS PERCEPÇÕES DO SENSORES DISPONÍVEIS PARA O 
PROGRAMA;
 EXECUTA O PROGRAMA; E,
 ALIMENTA AS OPÇÕES DE AÇÃO DO PROGRAMA PARA OS ATUADORES
À MEDIDA QUE SÃO GERADOS.
• EM GERAL, PROGRAMAS DE AGENTE:
 RECEBEM A PERCEPÇÃO ATUAL COMO ENTRADA DOS SENSORES, E
 RETORNAM UMA AÇÃO PARA OS ATUADORES.
• ATENÇÃO:
1) O PROGRAMA DE AGENTE TOMA APENAS A PERCEPÇÃO ATUALCOMO 
ENTRADA;
2) A FUNÇÃO DE AGENTE, RECEBE O HISTÓRICO DE PERCEPÇÕES
COMPLETO.
PROGRAMAS DE AGENTES
• HÁ QUATRO TIPOS BÁSICOS DE PROGRAMAS
DE AGENTES QUE INCORPORAM OS PRINCÍPIOS
SUBJACENTES A QUASE TODOS OS SISTEMAS
INTELIGENTES:
AGENTES REATIVOS SIMPLES
AGENTES REATIVOS BASEADOS EM MODELO
AGENTES BASEADOS EM OBJETIVOS
AGENTES BASEADOS NA UTILIDADE
AGENTES REATIVOS SIMPLES
• SELECIONAM AÇÕES COM BASE NA PERCEPÇÃO
ATUAL, IGNORANDO O RESTANTE DO 
HISTÓRICO DE PERCEPÇÕES;
• É O CASO DO AGENTE ASPIRADOR DE PÓ, VISTO
PREVIAMENTE. SUA DECISÃO SE BASEIA
APENAS:
 NA POSIÇÃO ATUAL; E,
 NO FATO DE ESSA POSIÇÃO CONTER OU NÃO 
SUJEIRA.
AGENTES REATIVOS BASEADOS
EM MODELOS
• O MODO MAIS EFETIVO DE LIDAR COM A 
POSSIBILIDADE DE OBSERVAÇÃO PARCIAL É O 
AGENTE CONTROLAR PARTE DO MUNDO QUE ELE
NÃO PODE VER AGORA;
• O AGENTE DEVE MANTER ALGUM TIPO DE “ESTADO 
INTERNO” QUE DEPENDA DO HISTÓRICO DE 
PERCEPÇÕES; E,
• ASSIM, REFLITA PELO MENOS EM ALGUNS DOS 
ASPECTOS NÃO-OBSERVADOS DO ESTADO ATUAL.
AGENTES BASEADOS EM 
OBJETIVOS
• CONHECER O ESTADO ATUAL DO AMBIENTE NEM SEMPRE É 
SUFICIENTE PARA SE DECIDIR O QUE FAZER;
• COMO EXEMPLO, O CARRO AUTÔNOMO PODE CHEGAR EM UM 
ENTRONCAMENTO, ONDE PODE VIRAR À DIREITA, À 
ESQUERDA, OU PODE SEGUIR EM FRENTE.
• DA MESMA FORMA QUE O AGENTE PRECISA DE UMA DESCRIÇÃO
DO ESTADO ATUAL, ELE TAMBÉM PRECISA DE ALGUMA
ESPÉCIE DE INFORMAÇÃO SOBRE OBJETIVOS, COMO POR
EXEMPLO ESTAR NO DESTINO DO PASSAGEIRO.
AGENTES BASEADOS NA 
UTILIDADE
• APENAS OS OBJETIVOS NÃO SÃO REALMENTE SUFICIENTES
PARA GERAR UM COMPORTAMENTO DE ALTA QUALIDADE NA 
MAIORIA DOS AMBIENTES;
• EXEMPLO, EXISTEM MUITAS SEQUÊNCIAS DE AÇÕES QUE 
LEVARÃO O TÁXI ATÉ SEU DESTINO, MAS ALGUMAS PODEM SER
MAIS RÁPIDAS, MAIS SEGURAS, MAIS CONFIÁVEIS, OU MESMO, 
MAIS ECONÔMICAS;
• ESTES AGENTES UTILIZAM UMA FUNÇÃO DE UTILIDADE QUE 
MAPEIA OS ESTADOS (OU SEQUENCIA DE ESTADOS) EM UM 
NÚMERO REAL, QUE DESCREVE O “GRAU DE FELICIDADE” 
ASSOCIADO.
1.3 Estratégias de 
Pesquisa em Espaço de 
Estados
MÉTODOS DE RESOLUÇÃO 
DE PROBLEMAS
• AGENTES REATIVOS, BASEIAM SUAS AÇÕES EM UM 
MAPEAMENTO DIRETO DE ESTADOS EM AÇÕES.
• TAIS AGENTES NÃO PODEM OPERAR BEM EM AMBIENTES PARA 
OS QUAIS ESSES MAPEAMENTO SERIA GRANDE DEMAIS PARA:
1) ARMAZENAR; E,
2) APRENDER.
• AGENTES DE RESOLUÇÃO DE PROBLEMAS DECIDEM O QUE 
FAZER ENCONTRANDO SEQUÊNCIAS DE AÇÕES QUE LEVAM A 
ESTADOS DESEJADOS.
AGENTE DE RESOLUÇÃO 
DE PROBLEMA
1ª PASSO PARA 
RESOLUÇÃO DE PROBLEMA
Formulação de Objetivos
Situação 
Atual
Medida de 
Desempenho
2º PASSO PARA 
RESOLUÇÃO DE PROBLEMA
Formulação do Problema
Definir 
Estados
Definir 
Ações
Formulação do Objetivos
Situação Atual
Medida de 
Desempenho
3º PASSO RESOLUÇÃO 
DE PROBLEMA
Busca
Examinar
Sequência 
de
Ações
Formulação do Problema
Definir 
Estados
Definir 
Ações
Formulação do Objetivo
Situação Atual
Medida de 
Desempenho
AGENTE DE RESOLUÇÃO 
DE PROBLEMA
Formulação 
do 
Objetivo
Formulação 
do 
Problema
Busca
Escolher a 
Melhor 
Sequência
PROBLEMAS E SOLUÇÕES 
BEM DEFINIDOS
UM PROBLEMA PODE SER DEFINIDO POR CINCO COMPONENTES:
1) ESTADO INICIAL: ONDE O AGENTE COMEÇA. Ex.: Em(Arad)
2) AÇÕES: DESCRIÇÃO DAS AÇÕES POSSÍVEIS ESTANDO O AGENTE EM UM 
DETERMINADO ESTADO.
• Ex.: A partir do estado em(Arad) as ações possíveis são {Ir(Sibiu), Ir(Timisoara), 
Ir(Zerind)}
3) MODELO DE TRANSIÇÃO: DESCRIÇÃO DO QUE UMA AÇÃO FAZ, ESPECIFICADO POR 
UMA FUNÇÃO RESULTADO(estado,ação)
• Ex.: RESULTADO(Em(Arad),Go(Zerind))= Em(Zerind)
4) TESTE DE OBJETIVO, pode ser
• Explícito: x = “em Bucareste”
• Implícito: Chequemate(x)
5) CUSTO DE CAMINHO (aditivo)
• Ex.: Soma das distâncias (Km, m, etc), número de ações executáveis, etc.
• c(x,a,y) é o “custo do passo”, que deve ser sempre >= 0
PROBLEMAS E SOLUÇÕES 
BEM DEFINIDOS
• UMA SOLUÇÃO PARA UM PROBLEMA É UM CAMINHO DESDE
O ESTADO INICIAL ATÉ UM ESTADO OBJETIVO;
• UMA SOLUÇÃO ÓTIMA TEM O MENOR CUSTO DO CAMINHO.
• A QUALIDADE DO SOLUÇÃO ESCOLHIDA É MEDIDA ATRAVÉS 
DE UM FUNÇÃO DE CUSTO.
BUSCA DE SOLUÇÕES
• A SOLUÇÃO DE PROBLEMAS PERCORRE ESPAÇOS DE 
ESTADOS ATRAVÉS DE TÉCNICAS DE BUSCAS, QUE 
UTILIZAM ÁRVORES DE BUSCA.
• UMA ÁRVORE É UM TIPO DE GRAFO, E POSSIBILITA 
QUE OS ESTADOS PODEM SER ALCANÇADOS POR 
DIFERENTES CAMINHOS.
ESPAÇO DE ESTADOS ÁRVORE DE BUSCA (GRAFO)
BUSCA DE SOLUÇÕES
• A RAIZ DA ÁRVORE DE BUSCA É UM NÓ DE 
BUSCA, QUE CORRESPONDE A UM ESTADO 
INICIAL DE UMA OCORRÊNCIA DO PROBLEMA.
BUSCA DE SOLUÇÕES
• PRIMEIRO, É TESTADO SE O NÓ RAIZ É O ESTADO 
OBJETIVO.
• CASO NÃO SEJA, OCORRE UMA EXPANSÃO NO 
ESTADO ATUAL, ATRAVÉS DA FUNÇÃO
RESULTADO, QUE GERA UM NOVO CONJUNTO DE 
ESTADOS.
• AGORA, DEVE-SE ESCOLHER QUAIS DOS NÓS
EXPANDIDOS DEVE SER CONSIDERADO NA BUSCA, 
O QUE É DETERMINADO PELA ESTRATÉGIA DE 
BUSCA.
BUSCA DE SOLUÇÕES
BUSCA DE SOLUÇÕES
BUSCA DE SOLUÇÕES
TÉCNICAS DE BUSCAS EM ESPAÇOS DE 
ESTADOS
A COLEÇÃO DE NÓS DE QUE FORAM GERADOS PELA FUNÇÃO 
SUCESSORA, E AINDA NÃO FORAM EXPANDIDOS SÃO 
DENOMINADOS DE BORDA.
MEDIÇÃO DE DESEMPENHO 
DE RESOLUÇÃO DE PROBLEMAS
• UMA ESTRATÉGIA DE BUSCA É DEFINIDA PELA ESCOLHA DA ORDEM DA 
EXPANSÃO DOS NÓS.
• OS ALGORITMOS DE RESOLUÇÃO DE PROBLEMA PODEM SER AVALIADOS
POR QUATRO ASPECTOS:
• COMPLETEZA: O algoritmo encontra a solução se ela existe?
• OTIMIZAÇÃO: A estratégia encontra a solução ótima?
• COMPLEXIDADE DE TEMPO: Número de nós gerados.
• COMPLEXIDADE DE ESPAÇO: Número máximo de nós na memória.
MEDIÇÃO DE DESEMPENHO 
DE RESOLUÇÃO DE PROBLEMAS
COMPLEXIDADE DE TEMPO E ESPAÇO É MEDIDO ATRAVÉS
DE:
 b – MÁXIMO FATOR DE RAMIFICAÇÃO DE ÁRVORE
(NÚMERO MÁXIMO DE SUCESSORES DE QUALQUER NÓ)
 d – PROFUNDIDADE DO NÓ OBJETIVO MAIS RASO
 m – O COMPRIMENTO MÁXIMO DE QUALQUER CAMINHO
NO ESPAÇO DE ESTADOS (PODE SER INFINITO )
MEDIÇÃO DE DESEMPENHO 
DE RESOLUÇÃO DE PROBLEMAS
d=0
d=1
d=2
d+1
 b = 3, d = 2 e m = 3 
MÉTODOS DE BUSCAS
TÉCNICAS DE BUSCAS EM ESPAÇOS DE 
ESTADOS
BUSCA SEM INFORMAÇÃO 
(OU, BUSCA CEGA)
• NÃO TEM NENHUMA 
INFORMAÇÃO ADICIONAL, 
ALÉM DAS FORNECIDAS NA 
DEFINIÇÃO DO PROBLEMA
• TUDO O QUE PODEM FAZER 
É:
• GERAR SUCESSORES
• DISTINGUIR UM 
“ESTADO OBJETIVO” DE 
UM “ESTADO NÃO-
OBJETIVO”
BUSCA COM INFORMAÇÃO 
(OU, HEURÍSTICA)
• SABEM SE UM ESTADO NÃO-
OBJETIVO É “MAIS 
PROMISSOR” QUE O 
OUTRO.
• O QUE CONTRIBUI DE 
FORMA SIGNIFICATIVA 
ALCANÇAR UM ESTADO 
OBJETIVO.
BUSCA SEM INFORMAÇÃO
 BUSCA EM EXTENSÃO OU LARGURA (BREADTH-FIRST)
 BUSCA DE CUSTO UNIFORME
 BUSCA EM PROFUNDIDADE (DEPTH-FIRST)
 BUSCA EM PROFUNDIDADE LIMITADA
 BUSCA POR APROFUNDIDADE ITERATIVO EM PROFUNDIDADE
 BUSCA BIDIRECIONAL
BUSCA EM EXTENSÃO
BUSCA EM EXTENSÃO
• ESTADO OBJETIVO: G
• RAMIFICAÇÃO: b = 2
• PROFUNDIDADE: d = 2
d=0
d=1
d=2
d+1
BUSCA DE CUSTO UNIFORME
C=0
C=1
C=3 C=2 C=5 C=6
C=4 C=2
BUSCA DE CUSTO UNIFORME
C=0
C=1
C=3 C=2 C=5 C=6
C=4 C=2
BUSCA DE CUSTO UNIFORME
• ESTADO OBJETIVO: G
• CUSTO TOTAL: C*=5
• FATOR DE RAMIFICAÇÃO b=3
d=0
d=1
d=2
BUSCA EM PROFUNDIDADE
BUSCA EM PROFUNDIDADE 
LIMITADA
• PRINCÍPIO: BUSCA EM PROFUNDIDADE UTILIZANDO UM LIMITE
DE PROFUNDIDADE, ISTO É, NÓS COM PROFUNDIDADE l NÃO
TEM SUCESSORES.
• l=3
BUSCA POR APROFUNDAMENTO 
ITERATIVO EM PROFUNDIDADE
• l=0
• l=1
• l=2
BUSCA POR APROFUNDAMENTO 
ITERATIVO EM PROFUNDIDADE
• l=3
OBS.: É COMO SE COMBINASSE A BUSCA EM PROFUNDIDADE COM A BUSCA EM EXTENSÃO.
BUSCA BIDIRECIONAL
Início
Obje-
tivo
ATIVIDADE 1 – QUAL A SEQUENCIA
QUEOS NÓS SÃO ACESSADOS:
• BUSCA EM PROFUNDIDADE
• BUSCA EM EXTENSÃO
• BUSCA DE CUSTO UNIFORME
ATENÇÃO: CRIEM MODELOS MAIS COMPLEXOS PARA 
ESTUDAR
ATIVIDADE 1 – QUAL A SEQUENCIA
QUE OS NÓS SÃO ACESSADOS:
• BUSCA EM PROFUNDIDADE:
BP = { A, B, D, E, C, F}
ATIVIDADE 1 – QUAL A SEQUENCIA
QUE OS NÓS SÃO ACESSADOS:
• BUSCA EM EXTENSÃO:
BP = { A, B, C, D, E, F}
ATIVIDADE 1 – QUAL A SEQUENCIA
QUE OS NÓS SÃO ACESSADOS:
• BUSCA DE CUSTO UNIFORME
BC = { A, B, E, C, D, G, F}
ESTRATÉGIA DE BUSCA COM INFORMAÇÃO, OU 
HEURÍSTICA
MÉTODOS DE BUSCA COM INFORMAÇÃO
• A HEURÍSTICA INTRODUZ UMA MÉTRICA QUE 
PERMITE AO AGENTE DE BUSCA ESTIMAR A 
DISTÂNCIA DESDE O ESTADO ATUAL ATÉ UM 
OBJETIVO;
• COMO EXEMPLO: USAMOS A HEURÍSTICA 
“DISTÂNCIA EM LINHA RETA” ENTRE O 
OBJETIVO (ARAD) E O OBJETIVO 
(BUCARESTE).
BUSCA COM INFORMAÇÃO
 BUSCA PELA MELHOR ESCOLHA UTILIZA UMA FUNÇÃO DE 
AVALIAÇÃO f(n) PARA ESCOLHER ENTRE OS NÓS DA BORDA O QUE 
POSSUI O MENOR f(n), E SE DIVIDE EM DUAS ESTRATÉGIAS DE 
BUSCA:
•BUSCA GULOSA PELA MELHOR ESCOLHA: 
 UTILIZA f(n) = h(n)
•BUSCA A*: 
 UTILIZA f(n) = g(n) + h(n)
ONDE:
g(n) É CUSTO PARA ALCANÇAR CADA NÓ, E
h(n), O CUSTO PARA IR DO NÓ ATÉ O OBJETIVO EM LINHA RETA.
BUSCA GULOSA PELA MELHOR ESCOLHA
Menor distância 
a Bucareste
BUSCA GULOSA PELA MELHOR ESCOLHA
BUSCA A*
BUSCA A*
1.4 REPRESENTAÇÃO E
RACIOCÍNIO
UNIDADE I
AGENTES LÓGICOS
BASE DE 
CONHECIMENTO
BASE DE CONHECIMENTO
 UMA BASE DE CONHECIMENTO (BC) É UM CONJUNTO
DE SENTENÇAS;
 CADA SENTENÇA É EXPRESSA EM UMA LINGUAGEM
CHAMADA “LINGUAGEM DE REPRESENTAÇÃO DE 
CONHECIMENTO”, E REPRESENTA ALGUMA AFIRMAÇÃO
SOBRE O MUNDO.
 A LÓGICA É UMA LINGUAGEM FORMAL QUE PERMITE
REPRESENTAR INFORMAÇÃO É EXTRAIR CONCLUSÕES:
 LÓGICA PROPOSICIONAL (FATOS)
 LÓGICA DE 1ª ORDEM (FATOS, OBJETOS, RELAÇÕES)
LÓGICA PROPOSICIONAL
 A LÓGICA PROPOSICIONAL, OU LÓGICA BOOLEANA, É MUITO
SIMPLES;
 AS SENTENÇAS ATÔMICAS CONSISTEM EM UM ÚNICO SÍMBOLO
PROPOSICIONAL;
 AS SENTENÇAS COMPLEXAS SÃO CONSTRUÍDOS A PARTIR DE 
SENTENÇAS MAIS SIMPLES COM A UTILIZAÇÃO DE CONECTIVOS
LÓGICOS:
LÓGICA DE PRIMEIRA ORDEM
ENQUANTO A LÓGICA PROPOSICIONAL ASSUME 
QUE O MUNDO CONTEM FATOS;
A LÓGICA DE PRIMEIRA ORDEM, ASSIM COMO A 
LINGUAGEM NATURAL, ASSUME QUE O MUNDO
TAMBÉM CONTÊM:
 OBJETOS: PESSOAS, CASAS, NÚMEROS, CORES, 
ETC.
 RELAÇÕES: PESSOAS MORAM EM CASAS, CASAS 
POSSUEM NÚMEROS, ETC.
LÓGICA DE PRIMEIRA ORDEM
RELAÇÕES: 
• RELAÇÕES UNÁRIAS OU PROPRIEDADES: VERMELHO, 
REDONDO, FALSO, PRIMO, ETC.
• RELAÇÕES N-ÁRIAS MAIS GERAIS COMO: IRMÃO DE, 
MAIOR QUE, PERTENCE A, FICA ENTRE, ETC.
• FUNÇÕES: PAI DE, MELHOR AMIGO, UMA UNIDADE 
MAIOR QUE, ETC.
LÓGICA DE PRIMEIRA ORDEM
EXEMPLO:
“O PERVERSO REI JOÃO GOVERNOU A INGLATERRA EM 
1200”
OBJETOS? ‘JOÃO’, ‘INGLATERRA’ E ‘1200’
RELAÇÃO N-ÁRIA? ‘GOVERNOU’
RELAÇÃO UNÁRIA OU PROPRIEDADE? ‘PERVERSO’ E ‘REI’
LPO – SINTAXE E SEMÂNTICA
 OS ELEMENTOS SINTÁTICOS BÁSICOS DA LPO:
 SÍMBOLOS DE CONSTANTES, QUE REPRESENTAM OBJETOS:
Em Irmão(Ricardo,João) “Ricardo” e “João” são constantes.
 SÍMBOLOS DE PREDICADOS, QUE REPRESENTAM RELAÇÕES:
Em Irmão(Ricardo,João) “Irmão” é predicado, porque podem 
haver vários irmãos.
 SÍMBOLOS DE FUNÇÕES, QUE REPRESENTAM FUNÇÕES:
Em Mãe(Ricardo) “mãe” é função, porque as pessoa possuem 
apenas uma mãe. Simplifica a relação Mãe(x,Ricardo).
.
CATEGORIAS E OBJETOS
A ORGANIZAÇÃO DE OBJETOS EM 
CATEGORIAS É UMA PARTE VITAL DA 
REPRESENTAÇÃO DO CONHECIMENTO;
APESAR DA INTERAÇÃO DO MUNDO REAL 
OCORRA NO NÍVEL DE OBJETOS 
INDIVIDUAIS, UMA GRANDE PARTE DO 
RACIOCÍNIO TEM LUGAR NO NÍVEL DE 
CATEGORIAS;
EXEMPLO: UM CONSUMIDOR TALVEZ TENHA 
INTERESSE EM COMPRAR UMA BOLA DE 
BASQUETE, E NÃO UMA BOLA DE 
BASQUETE DE DETERMINADA MARCA.
CATEGORIAS E OBJETOS
HÁ DUAS FORMAS DE REPRESENTAR
CATEGORIAS EM LÓGICA DE PRIMEIRA ORDEM:
A) PREDICADO: BolaDeBasquete(b) 
B) OBJETO: BolasDeBasquete, 
DESTA FORMA PODEMOS AFIRMAR:
Elemento(b,BolasDeBasquete) 
Subconjunto(BolasDeBasquete,Bolas)
b1
BolasDeBasquete
Bolas
b2
CATEGORIAS E OBJETOS
AS CATEGORIAS TAMBÉM SERVEM PARA ORGANIZAR E SIMPLIFICAR A 
BASE DE CONHECIMENTO POR HERANÇAS;
EXEMPLO, SE AFIRMAMOS QUE:
A) TODAS AS INSTÂNCIAS DA CATEGORIA Alimento SÃO COMESTÍVEIS;
B) Fruta É UMA SUBCLASSE DE Alimento;
C) Maças É UMA SUBCLASSE DE Fruta.
ENTÃO SABEREMOS QUE TODA MAÇA É COMESTÍVEL. AS MAÇAS 
INDIVIDUAIS HERDAM A PROPRIEDADE DE SEREM COMESTÍVEIS, NESSE 
CASO DE SUA CONDIÇÃO DE ELEMENTO DA CATEGORIA Alimento.
CATEGORIAS E OBJETOS
A IDEIA DE QUE UM OBJETO PODER FAZER PARTE DE OUTRO É 
BASTANTE FAMILIAR.
ParteDe(Bucareste, Romênia)
ParteDe(Romênia, EuropaOriental)
ParteDe(EuropoOriental, Europa)
ParteDe(Europa, Terra)
PARA TORNAR A RELAÇÃO ParteDe TRANSITIVA E REFLEXIVA, 
SEGUE AS REGRAS A SEGUIR, RESPECTIVAMENTE:
PODEMOS CONCLUIR: 
ParteDe(Bucareste, Terra) % TRANSITIVA
ParteDe(Bucareste, Bucareste) % REFLEXIVA
REDES SEMÂNTICAS
 AS REDES SEMÂNTICAS OFERECEM AUXÍLIO
GRÁFICO PARA VISUALIZAÇÃO DE UMA BASE DE 
CONHECIMENTO.
 GRAÇAS A UTILIZAÇÃO DE CATEGORIAS, AS REDES 
SEMÂNTICAS POSSIBILITAM O RACIOCÍNIO DE 
HERANÇA.
 AS REDES SEMÂNTICAS REPRESENTAM O 
CONHECIMENTO COMO GRAFOS, COM OS NÓS
CORRESPONDENDO A FATOS OU CONCEITOS
(OBJETOS) E OS ARCOS COMO RELAÇÕES OU
ASSOCIAÇÕES ENTRE OS OBJETOS.
REDES SEMÂNTICAS
(LUGER, 2004)
EXEMPLO DE 
FATOS OU
CONCEITOS
EXEMPLO DE 
RELAÇÕES E 
ASSOCIAÇÕES
SISTEMAS BASEADOS EM 
CONHECIMENTO
SISTEMAS BASEADOS EM CONHECIMENTO 
(SBC)
Utilizam o conhecimento representado
explicitamente sobre um determinado domínio
para resolver problemas; 
 Possuem como principal característica uma
base de conhecimento e um mecanismo de 
raciocínio capaz de realizar inferências sobre
essa base e tirar conclusões.
SISTEMAS BASEADOS EM CONHECIMENTO
SISTEMAS CONVENCIONAIS SISTEMAS BASEADOS EM 
CONHECIMENTO
ESTRUTURA DE DADOS REPRESENTAÇÃO DO CONHECIMENTO
DADOS E RELAÇÕES ENTRE DADOS CONCEITOS, RELAÇÕES ENTRE 
CONCEITOS E REGRAS
TIPICAMENTE USA ALGORITMO
DETERMINÍSTICOS
BUSCA HEURÍSTICA
CONHECIMENTO EMBUTIDO NO 
CÓDIGO DO PROGRAMA
CONHECIMENTO REPRESENTADO 
EXPLICITAMENTE E SEPARADO DO 
PROGRAMA QUE O MANIPULA E 
INTERPRETA
EXPLICAÇÃO DO RACIOCÍNIO É DIFÍCIL PODEM E DEVEM EXPLICAR SEU 
RACIOCÍNIO
ESTRUTURA GERAL DE UM SBC
NÚCLEO DO SISTEMA
BASEADO EM CONHECIMENTO
(OU SHELL)
BASE
DE
CONHECIMENTO
MEMÓRIA DE 
TRABALHO
BASE DE 
DADOS
IN
T
E
R
FA
C
E
ESTRUTURA GERAL DE UM SBC
NÚCLEO DO SBC É FORMADO POR:
1) MÓDULO COLETOR DE DADOS (MCD): Obtém informações
do problema em questão, através da formulação de 
sucessivas perguntas do problema em questão. 
2) MOTOR DE INFERÊNCIA (MI): Desenvolve o raciocínio
baseado nas informações obtidas pelo MCD e pelo
conhecimento representando na BC.
3) MÓDULO DE EXPLICAÇÃO (ME): Explica, ou justifica, as 
conclusões obtidas, e os motivos pelos quais o SBC fez 
determinadas perguntas.
REGRAS DE PRODUÇÃO
• Regras de Produção são utilizadas para representar o 
conhecimento em SBC;
• Baseia-se na ideia de que o processo de tomada de decisão
humano pode ser modeladado por meio de regras do tipo:
SE <condição> ENTÃO <conclusões> <ações>
• Entre várias alternativas de Representação do 
Conhecimento (Ex.: Redes Semânticas, entre outros), as 
regras constituem uma forma natural de representar o 
conhecimento de um especialista humano.
MOTOR DE INFERÊNCIA
cozinha_seca
E VAZAMENTO BANHEIRO
HALL MOLHADO
E PROBLEMA COZINHA
BANHEIRO SECO
E VAZAMENTO COZINHAJANELA FECHADA
OU SEM ÁGUA DE FORA
NÃO CHOVEU
JANELA
COZINHA
BANHEIRO HALL
REGRAS DE PRODUÇÃO
• UMA POSSIBILIDADE SERIA:
• R1: SE a cozinha = seca E hall = molhado
ENTÃO vazamento = banheiro
• R2: SE o banheiro = seco E o hall = molhado
ENTÃO cozinha com problema = sim
• R3: SE a janela = fechada OU choveu = não
ENTÃO água de fora = não
• R4: SE cozinha com problema = sim E água de fora = não
ENTÃO vazamento = cozinha
SISTEMA DE INFERÊNCIA FUZZY DE 
MANDANI
REDES BAYESIANAS
PLANEJAMENTO
UNIDADE I
PLANEJAMENTO
• UM PROCESSO DE DELIBERAÇÃO ABSTRATO E 
EXPLICITO E QUE ESCOLHE E ORGANIZA AÇÕES, 
ANTECIPANDO RESULTADOS ESPERADOS.
• A INTELIGÊNCIA ARTIFICIAL ESTUDAR E 
IMPLEMENTAR ESSES PROCESSOS DE 
DELIBERAÇÃO, ATRAVÉS DE PLANEJADORES 
(PLANNER).
PLANEJAMENTO
• COMO NOS PROBLEMAS DE BUSCA, PRECISAMOS 
REPRESENTAR OS SEGUINTES ELEMENTOS DO 
PROBLEMA DE PLANEJAMENTO:
ESTADO INICIAL
AS AÇÕES QUE ESTÃO DISPONÍVEIS EM UM ESTADO
O RESULTADO DE APLICAÇÃO DE UMA AÇÃO
O TESTE DE OBJETIVO
LINGUAGENS DE PLANEJAMENTO
• STRIPS: Stanford Research Institute Problem Solver
• ADL: Action Description Language (É UMA VARIANTE 
DO STRIPS)
• ...
• PDDL: Planning Domain Definition Language:
• DERIVADA DO STRIPS QUE É MAIS RESTRITIVA QUE O 
PDDL
• SERÁ APRESENTADA UMA VERSÃO SIMPLIFICADA
CARACTERÍSTICA GERAIS DA LINGUAGEM
• ESQUEMA DE AÇÃO:
Ação(Voar(p,de,para),
PRECOND: Em(p,de)  Avião(p) 
Aeroporto(de)  Aeroporto(para)
EFEITO: ¬Em(p,de)  Em(p,para)).
• AÇÃO INSTANCIADA QUE SUBSTITUÍ VALORES DAS VARIÁVEIS:
Ação(Voar(P1,BEL,MAO),
PRECOND: Em(P1,BEL)  Avião(P1) 
Aeroporto(BEL)  Aeroporto(MAO)
EFEITO: ¬Em(P1,BEL)  Em(P1,MAO)).
CARACTERÍSTICA GERAIS DA LINGUAGEM
• ESQUEMA DE AÇÃO:
Ação(Voar(P1,BEL,MAO),
PRECOND: Em(P1,BEL)  Avião(P1) 
Aeroporto(BEL)  Aeroporto(MAO)
EFEITO: ¬Em(P1,BEL)  Em(P1,MAO)).
• A PRECONDIÇÃO DEFINE OS ESTADOS EM QUE A AÇÃO
PODE SER EXECUTADA;
• AÇÃO PODE SER APLICADA, SOMENTE SE TODAS AS 
PRECONDIÇÕES FORAM SATISFEITAS.
• O EFEITO DEFINE O RESULTADO DA EXECUÇÃO DA AÇÃO.
CARACTERÍSTICA GERAIS DA LINGUAGEM
• UM CONJUNTO DE ESQUEMAS DE AÇÃO SERVE COMO UMA 
DEFINIÇÃO DO DOMÍNIO DE PLANEJAMENTO;
• UM ADIÇÃO DE UM ESTADO INICIAL E UM OBJETIVO 
DEFINEM UM PROBLEMA ESPECÍFICO DENTRO DE UM 
DOMÍNIO;
• O ESTADO INICIAL É UMA CONJUNÇÃO DE ÁTOMOS 
INSTANCIADOS. EX.: Em(Avião1,BEL)
• O OBJETIVO É EXATAMENTE COMO UMA PRECONDIÇÃO: 
UMA CONJUNÇÃO DE LITERAIS QUE PODEM CONTER 
VARIÁVEIS. EX.: Em(p,BEL) ʌ Avião(p)
Ex: Transporte aéreo de cargas
Início(Em(C1, BEL)  Em(C2, MAO)  Em(A1, BEL)  Em(A2, MAO)  Carga(C1) 
 Carga(C2)  Avião(A1)  Avião(A2)  Aeroporto(BEL)  Aeroporto(MAO))
Objetivo(Em(C1, MAO)  Em(C2, BEL))
Ação(Carregar(c, p, a)
PRECOND: Em(c, a)  Em(p, a)  Carga(c)  Avião(p)  Aeroporto(a)
EFEITO: ¬Em(c, a)  Dentro(c, p))
Ação(Descarregar(c, p, a)
PRECOND: Dentro(c, p)  Em(p, a)  Carga(c)  Avião(p)  Aeroporto(a)
EFEITO: Em(c, a)  ¬Dentro(c, p))
Ação(Voar(p, de, para)
PRECOND: Em(p, de)  Avião(p)  Aeroporto(de)  Aeroporto(para)
EFEITO: ¬Em(p, de)  Em(p, para))
Qual seria um possível plano???
Ex: Transporte aéreo de cargas
Início(Em(C1, BEL)  Em(C2, MAO)  Em(A1, BEL)  Em(A2, MAO)  Carga(C1) 
 Carga(C2)  Avião(A1)  Avião(A2)  Aeroporto(BEL)  Aeroporto(MAO))
Objetivo(Em(C1, MAO)  Em(C2, BEL))
Ação(Carregar(c, p, a)
PRECOND: Em(c, a)  Em(p, a)  Carga(c)  Avião(p)  Aeroporto(a)
EFEITO: ¬Em(c, a)  Dentro(c, p))
Ação(Descarregar(c, p, a)
PRECOND: Dentro(c, p)  Em(p, a)  Carga(c)  Avião(p)  Aeroporto(a)
EFEITO: Em(c, a)  ¬Dentro(c, p))
Ação(Voar(p, de, para)
PRECOND: Em(p, de)  Avião(p)  Aeroporto(de)  Aeroporto(para)
EFEITO: ¬Em(p, de)  Em(p, para))
Possível plano:
[Carregar(C1, P1, BEL), Voar(P1, BEL, MAO), Descarregar(C1, P1, MAO)]
[Carregar(C2, P1, MAO), Voar(P1, MAO, BEL), Descarregar(C2, P1, BEL)]
ALGORITMOS DE PLANEJAMENTO
• HÁ DUAS GATEGORIAS:
1. ALGORITMOS DE PROGRESSÃO
• BUSCA POR ENCADEAMENTO PARA FRENTE
• CONSIDERAR OS EFEITOS DE TODAS AS AÇÕES EM UM DADO 
ESTADOS
• O QUE TORNA A BUSCA PROPENSA A EXPLORAR AÇÕES 
IRRELEVANTES.
2. ALGORITMOS DE REGRESSÃO 
• BUSCA POR ENCADEAMENTO PARA TRÁS
• PARA ATINGIR UM OBJETIVO, BUSCA APENAS O QUE DEVE 
SER VERDADEIRO NO ESTADO ANTERIOR (E ASSIM 
RECURSIVAMENTE).
• SOMENTE É POSSÍVEL SE SOUBER COMO REGREDIR DE UM 
ESTADO PARA UM ESTADO PREDECESSOR.
ALGORITMOS DE PROGRESSÃO E 
REGRESSÃO
Em(P1, A)
Em(P2, A)
Voar(P1,A,B)
Voar(P2,A,B)
Em(P1, B)
Em(P2, A)
Em(P1, A)
Em(P2, B)
Em(P1, B)
Em(P2, B)
Voar(P2,A,B)
Voar(P1,A,B)
Em(P1, B)
Em(P2, A)
Em(P1, A)
Em(P2, B)
(a)
(b)
Abordagens para a busca de um plano. (a) Busca para frente (progressão). (b) Busca 
para trás (regressão).
BOM ESTUDO & BOA PROVA!!