SLIDE 5 IA 2015 1 IMPRIMIR

Resolução de problemas por meio de busca

Introdução
• Agentes Autônomos:
– Entidades autônomas capazes de observar o ambiente e agir de forma a atingir determinado objetivo. • Tipos de Agentes:
– Agentes reativos simples;
– Agentes reativos baseado em modelo;
– Agentes baseados em objetivos;
– Agentes baseados na utilidade;
– Agentes baseados em aprendizado;

Objetivo
Formulação de Objetivos
Limitar os objetivos que o agente esta tentando alcançar.
Considerando que um ambiente possui uma série de estados possíveis, busquemos o estado em que o objetivo é satisfeito.

Formulação de Problemas
Definir quais são as ações e estados que serão considerados.

Formular – Buscar - Executar
Busca – Definição da sequência de ações que leva a um estado objetivo.
Execução – implementar a sequência, ignorando novas reflexões ou percepções

Problema de Busca
Bucharest

Timisoara

Sibiu

Zerind
Arad

Problema de Busca

Relações com o capítulo anterior Considerando os conceitos até aqui estudados sobre agentes, podemos definir algumas características. Nos casos de buscas: O ambiente é observável
O ambiente é discreto
O ambiente é estático
O ambiente é determinístico

Definição de um Problema
• Estado Inicial
• Função Sucessor
– Espaço de Estados
– Caminho
• O teste de objetivo
• Custo de caminho
– Custo de Passo
– Solução
– Solução Ótima

Exemplo: Aspirador de Pó
•

Espaço de Estados: 8 estados possíveis (figura ao lado);

•

Estado Inicial: Qualquer estado;

•

Estado Final: Estado 7 ou 8 (ambos quadrados limpos);

•

Ações Possíveis: Mover para direita, mover para esquerda e limpar;

•

Custo: Cada passo tem o custo 1, assim o custo do caminho é definido pelo numero de passos;

Exemplo: Aspirador de Pó

Exemplo: 8-Puzzle
•

Espaço de Estados: 181.440 possíveis estados;

•

Estado Inicial: Qualquer estado;

•

Estado Final: Figura ao lado – Goal State;

•

Ações Possíveis: Mover o quadrado vazio para direita, para esquerda, para cima ou para baixo;

•

Custo: Cada passo