1

Resolução de Problemas

Como um agente pode encontrar uma sequência

de ações que alcança seus objetivos quando

nenhuma ação isolada é capaz de fazê-lo.

Resolução de Problemas

• Agente reativo simples: baseia suas ações em um mapeamento direto de estados em ações.

• Se o mapeamento é grande demais este agente não conseguirá operar bem.

4 5 8

1 6

7 3 2

1 2 3

4 6

7 8

5 ?

Resolução de Problemas

• O agente baseado em objetivos: combina seu objetivo com as informações sobre os resultados de ações possíveis e escolhe ações que o levem à realização de seus objetivos.

• O agente de resolução de problemas é um tipo de agente baseado em objetivos.

4

Resolução de Problemas

• Os agentes inteligentes devem maximizar sua

medida de desempenho.

• Se o agente adotar um objetivo que deseja

satisfazer, pode facilitar a maximização.

• É importante a definição do objetivo.

Formulação do objetivo

Estático

Observável

Discreto

Determinístico

Episódico

Acesso ao estado completo do ambiente em cada instante

O próximo estado do ambiente é completamente determinado pelo estado atual e pela ação executada pelo agente

Cada episódio consiste na percepção do agente , e depois na execução de uma única ação

O ambiente não se altera enquanto o agente está deliberando

O estado do ambiente, as percepções e ações do agente são tratadas em tempo discreto.

6

Resolução de Problemas

• Um objetivo é um estado do conjunto de estados do mundo onde esta definido o problema

• Quais estados e que tipo de ações devem-se considerar para atingir o estado objetivo?

• A formulação de problemas é o processo de decidir que ações e estados devem ser considerados, dado um objetivo.

7

Resolução de Problemas

• O processo de procurar a sequência de ações que alcançam o objetivo é chamado de busca.

• Algoritmo de busca: – Entrada: um problema,

– Saída a solução sob a forma de uma sequência de ações.

• Logo de encontrada a solução, as ações recomendadas podem ser executadas.

• Tem-se então um simples projeto de “formular, buscar, executar”

8

Resolução de Problemas

Observações:

• Enquanto o agente está executando a sequência de solução ignora sua percepção ao escolher uma ação.

• Os teóricos de controle chamam isso de um sistema de malha aberta, pois ignorar a percepção quebra o laço entre o agente e o ambiente.

9

Definindo o problema

Um problema pode ser definido por quatro componentes:

1. O estado inicial em que o agente começa: “Em (Arad)”

2. Uma descrição das ações possíveis que estão disponíveis para o agente. Formulação mais comum é a função sucessor.

– Dado um estado 𝑥, função SUCESSOR (𝑥) retorna pares <ação,

𝑠𝑢𝑐𝑒𝑠𝑠𝑜𝑟>: “<Em (Arad), Ir (Zerind)>, Em (Arad), Ir (Sibiu),...”

10

Definindo o problema

3. O teste de objetivo, que determina se um dado estado é um estado final (objetivo): “Em (Bucharest)”

4. Função de custo de caminho, atribui um custo numérico a cada caminho: “distâncias de uma cidade a outra”

11

Espaços de estado

• O estado inicial e a função sucessor definem o espaço de estados do problema

• Espaços de estado é o conjunto de todos os estados acessíveis a partir do estado inicial.

• O espaço de estados forma uma rede dirigida ou um grafo em que os nós são estados e os arcos entre os nós são ações.

• Um caminho no espaço de estados é uma sequência de estados conectados por uma sequência de ações.

12

Solucionando o problema

• Formulação do problema e do objetivo: – quais são os estados e as ações a considerar?

– qual é (e como representar) o objetivo?

• Busca (solução do problema):

– processo que gera/analisa seqüências de ações para alcançar um objetivo

– solução = caminho entre estado inicial e estado final.

• Execução:

– Executar (passo a passo) a solução completa encontrada

14

Problemas clássicos de IA

• Prova automática de teoremas.

• O quebra-cabeças 3x3

• O jogo da velha

• O Caixeiro Viajante

• As Torres de Hanói

15

Características dos problemas de IA

• São solucionáveis por seres humanos e, neste caso, sua solução esta associada à inteligência.

• Formam classes de complexidade variável existindo desde instâncias triviais até complexas.

• São problemas de conhecimento total, isto é, tudo que é necessário saber para solucioná-los é conhecido, o que facilita sua formalização.

• Suas soluções tem a forma de uma sequencia de situações “legais” e as maneiras de passar de uma situação para outra são em número finito e conhecidas.

Problema: jarros

• Dados uma bica d`agua, um jarro de capacidade 3 litros e um jarro de capacidade 4 litros (ambos vazios). Como obter 2 litros no jarro de 4?

Solução: jarros

Método de solução de Problemas: Busca de Soluções

• Desenvolver programas, não com os passos de solução de um problema, mas que produzam estes passos;

• Construir um espaço de estados para encontrar uma sequência de ações cuja aplicação resolve um problema;

• Recebe um problema e retorna uma solução

• Um problema de busca pode ser formalizado através de espaço de estados.

19

Exemplos de Problemas

• Miniproblemas

– Utilizado para ilustrar ou exercitar diversos métodos de resolução de problemas.

– Pode ter uma descrição concisa e exata – pode ser utilizado com facilidade por diferentes sistemas de busca, com a finalidade de comparar o desempenho de algoritmos.

• Problemas do mundo real

– Tendem a não apresentar uma única descrição consensual, mas é possível fornecer uma ideia geral de suas formulações.

20

Exemplos de Problemas

• Exemplos: Miniproblemas – Mundo do Aspirador de Pó – Problema do Quebra-cabeça de 8 Peças

• Exemplos: Problemas do mundo real

– Problema de Roteamento – Problema de Viagens Aéreas – Problema de Tour – Problema do Caixeiro Viajante – Problema de Navegação de Robôs – Problema da Sequência Automática de Montagem – Problema de Pesquisas na Internet

21

Miniproblemas

• Exemplo 1: Mundo do aspirador de pó com apenas 2 locais.

22

Miniproblemas

Problema do Mundo do Aspirador de Pó - Formulação

• Estados – O agente está em uma entre duas posições, cada uma das quais

pode conter sujeira ou não.

– Há 2 x 22 = 8 estados do mundo possíveis.

• Estado inicial – Qualquer estado pode ser designado como estado inicial.

• Função Sucessor – Gera os estados válidos que resultam da tentativa de executar as três

ações (Esquerda, Direita e Aspirar).

23

Miniproblemas Espaço de estados para o mundo do aspirador de pó.

Os arcos denotam ações: E = Esquerda, D = Direita, A = Aspirar

24

Miniproblemas

Problema do Mundo do Aspirador de Pó - Formulação

• Teste de objetivo – Verifica se todos os quadrados estão limpos.

• Custo de caminho – Cada passo custa 1, e assim o custo do caminho é o número de passos

do caminho.

• Esse miniproblema tem posições discretas, sujeira discreta, limpeza confiável e nunca é desorganizado depois de limpo.

• Ambiente com n posições: n x 2n estados

25

Miniproblemas

Exemplo 2: Uma instância típica do quebra-cabeça de 8 peças

26

Miniproblemas

Problema do Quebra-cabeça de 8 Peças - Formulação

• Estados – Uma descrição de estado especifica a posição de cada uma das oito

peças e do espaço vazio em um dos nove quadrados.

• Estado inicial – Qualquer estado pode ser designado como estado inicial.

• Função Sucessor – Gera os estados válidos que resultam da tentativa de executar as três

ações (o espaço vazio se desloca para a Esquerda, Direita, Acima ou Abaixo).

27

Miniproblemas

Problema do Quebra-cabeça de 8 peças - Formulação

• Teste de objetivo – Verifica se o estado corresponde à configuração de objetivo

mostrada na figura (São possíveis outras configurações de objetivos)

• Custo de caminho – Cada passo custa 1, e assim o custo do caminho é o número de

passos do caminho.

28

Miniproblemas

Problema do Quebra-cabeça de 8 Peças - Formulação

• Abstrações incluídas – As ações são reduzidas a seus estados iniciais e finais, ignorando-se

as posições intermediárias por onde o bloco está deslizando.

– Foram abstraídas ações como sacudir o tabuleiro quando as peças ficam presas ou extrair as peças com uma faca e colocá-las de volta no tabuleiro.

29

Miniproblemas

Problema do Quebra-cabeça de 8 Peças - Formulação

• Pertence à família de quebra-cabeças de blocos deslizantes – usados com freqüência como problemas de teste para novos algoritmos de busca em IA.

• Número de estados acessíveis – Quebra-cabeça de 8 peças: 9!/2 = 181.440

– Quebra-cabeça de 15 peças (tabuleiro de 4 x 4): aproximadamente 1,3 trilhão (instâncias aleatórias podem ser resolvidas de forma ótima em alguns ms pelos melhores algoritmos de busca).

30

Espaço de estados para o Quebra-cabeça de 8 Peças .

31

Problemas do mundo real Problema de Roteamento (pathfinding):

– Roteamento em redes de computadores

– Planejamento de operações militares

– Sistemas de planejamento de viagens (tour)

– Planejamento de rotas de aviões

– Caixeiro viajante

– Jogos de computadores (rotas dos personagens)

Problema de Alocação (scheduling): – Salas de aula

– Máquinas industriais (job shop)

Problema de Navegação de robôs

Problema da Seqüência Automática de Montagem

32

Problemas do mundo real

Problema de Rotas de aviões – Formulação

• Estados – Cada um é representado por uma posição (p.ex.: um aeroporto) e pela

hora atual.

• Estado inicial – É especificado pelo problema.

• Função Sucessor – Retorna os estados resultantes de tomar qualquer voo programado

que parte depois da hora atual somada ao tempo de trânsito no aeroporto, desde o aeroporto atual até outro.

• Teste de objetivo – Estamos no destino após algum tempo especificado?

33

Problemas do mundo real

Problema de Rotas de aviões – Formulação

• Custo de caminho – Depende do custo monetário, do tempo de espera, do tempo de vôo,

dos procedimentos alfandegários, da hora do dia, ...

• Um sistema realmente bom deve incluir planos de contingência. Exemplo: reservas substitutas em voos alternativos.

34

Problemas do mundo real

Problemas de Tour – Formulação

• Estreitamente relacionados aos problemas de roteamento

• Diferença: cada estado deve incluir não apenas a posição atual, mas também o conjunto de cidades que o agente visitou.

35

Problemas do mundo real

Problema do Caixeiro-Viajante (PCV) – Formulação

• É um problema de tour em que cada cidade deve ser visitada exatamente uma vez.

• Objetivo: encontrar o percurso mais curto.

• Outras aplicações: planejamento do movimento de máquinas automáticas para perfuração de placas de circuitos e de máquinas industriais em fábricas.

36

Problemas do mundo real

Problema da Navegação de Robôs – Formulação

• Generalização do problema de roteamento.

• Característica: um robô pode se mover em um espaço contínuo com (em princípio) um conjunto infinito de ações e estados possíveis.

• Robô com movimento circular sobre uma superfície plana: espaço bidimensional.

• Robô com braços e pernas ou rodas – espaço de busca com várias dimensões.

37

Problemas do mundo real

Problema da Seqüência Automática de Montagem – Formulação

• Objetivo: encontrar uma ordem na qual devem ser montadas as peças de algum objeto.

• Outro problema de montagem: projeto de proteínas – Objetivo: encontrar uma seqüência de aminoácidos que serão

incorporados em uma proteína tridimensional com as propriedades adequadas para curar alguma doença.

• Alanina (ALA ou A) é um dos aminoácidos que formam as proteínas nos seres vivos.

• Estrutura química tridimensional de uma ligação peptídica entre a alanina e um aminoácido adjacente.

39

Problemas do mundo real Problema de Pesquisas na Internet – Formulação

• Objetivo: procurar respostas para perguntas, informações inter-relacionadas ou oportunidades de compras