Resolução de ProblemasProf. Valmir Macário Filho

Resolução de problemas por meio de buscaCapítulo 3 – Russell & NorvigSeções 3.1, 3.2 e 3.3

Agents ação =

AgentFn(percepção)

sensores

agentfn

atuadores

3

Agentes de resolução de problemas

•Agentes reativos não funcionam em ambientes para quais o número de regras condição-ação é grande demais para armazenar.

•Nesse caso podemos construir um tipo de agente baseado em objetivo chamado de agente de resolução de problemas.

4

Busca•Um agente com várias opções imediatas

pode decidir o que fazer comparando diferentes sequências de ações possíveis.

•Esse processo de procurar pela melhor sequência é chamado de busca.

•Formular objetivo → buscar → executar

5

Problemas de Busca• Um proplema de busca consiste de:

▫ Espaço de estados:

▫ Ações:

▫ Estado inicial, ▫ Teste de objetivo▫ Função de custo do caminho

• A solução é uma sequência de ações (um plano), que transforma o estado inicial no estado objetivo

N, 1

E, 1

Ações•Função sucessor:

▫Successors( ) = {(N, 1, ), (E, 1, )}

•Ações e resultados:▫Ações( ) = {N, E}▫Resultado( , N) = ; Result( , E)

=

▫Custo( , N, ) = 1; Cost( , E, ) = 1

Exemplo: Viagem•De férias em Pernambuco; atualmente em

Garanhuns.•Vôo sai amanhã de Recife.•Formular objetivo:

▫Estar em Recife•Formular problema:

▫estados: cidades▫ações: dirigir entre as cidades

•Encontrar solução:▫sequência de cidades, ex., Lajedo, Caruaru,

Gravatá, Recife.

8

Garanhuns

Lajedo

São Bentodo Una

Belo Jardim Taca

imbó

São Caetano

Cachoeirinha

Car

uar

u

Bez

erro

s

Gra

vatá

Vit

ória

de

San

to

Antã

o

Recife

CanhotinhoQuipapá

Palmares

Ribeirão

Escada

Cabo de santo Agostinho

42,3

21,3

40,7

1616 21,1

29 28 36,9

49,4

37,8

25,3

27,2

37,7

50,8

22,135

23,8

20,8

Exemplo: Viagem

Formulação de problemasUm problema é definido por quatro itens:

1. Estado inicial ex., “em Garanhuns"2. Ações ou função sucessor S(x) = conjunto de pares estado-

ação ▫ ex., S(Garanhuns) = {<Garanhuns Lajedo, Lajedo>, … }

3. Teste de objetivo, pode ser▫ explícito, ex., x = “em Recife"▫ implícito, ex., Cheque-mate(x)▫

4. Custo de caminho (aditivo)▫ ex., soma das distâncias, número de ações executadas, etc.▫ c(x,a,y) é o custo do passo, que deve ser sempre ≥ 0

10

Formulação de problemas•Solução

▫caminho (seqüência de ações) que leva do estado inicial a um estado final (objetivo).

▫Cuidado! A solução não é o estado final!▫Uma solução ótima é uma solução com o

menor custo de caminho.

11

Espaço de estados•O conjunto de todos os estados acessíveis

a partir de um estado inicial é chamado de espaço de estados.▫Os estados acessíveis são aqueles dados

pela função sucessora.

•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.

12

Selecionando um espaço de estados• O mundo real é absurdamente complexo

o espaço de estados é uma abstração • Estado (abstrato) = conjunto de estados reais• Ação (abstrata) = combinação complexa de

ações reais▫ ex., “Garanhuns " representa um conjunto complexo

de rotas, desvios, paradas, etc. ▫ Qualquer estado real do conjunto “em Garanhuns“ deve

levar a algum estado real “em Lajedo“.• Solução (abstrata) = conjunto de caminhos reais

que são soluções no mundo real• A abstração é útil se cada ação abstrata é mais

fácil de executar que o problema original.

13

Busca em Espaço de Estados Implementação do Algoritmo

Função-Insere: controla a ordem de inserção de nós na fronteira do espaço de estados.

função Busca-Genérica (problema formulado, Função-Insere) retorna uma solução ou falha

fronteira ¬ Estado-Inicial (problema)

loop do

se fronteira está vazia então retorna falha

nó ¬ Remove-Primeiro (fronteira)

se Teste-Término (problema, nó) tiver sucesso

então retorna nó

fronteira ¬ Função-Insere (fronteira, Ações (nó) )

end

Solucionando o problema: formulação, busca e execução

•Formulação do problema e do objetivo (manual)▫quais são os estados e as ações a considerar?▫qual é (e como representar) o objetivo?

Em extensão ou intensão?•Busca (processo automático)

▫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 (manual ou automática)

15

Custo da Busca

•Custo total da busca = ▫custo de busca (tempo e memória, i.e.

custo computacional) -> busca da solução▫+ custo do caminho -> execução da

solução•Espaço de estados grande

▫compromisso (conflito) entre determinar a melhor solução em termos de custo do

caminho (é uma boa solução?) e a melhor solução em termos de custo

computacional (é computacionalmente barata?)

16

Exemplo: Espaço de Estados do Mundo do Aspirador de Pó

• Estados: Definidos pela posição do robô e sujeira (8 estados)

• Estado inicial: Qualquer um• Função sucessor: pode-se executar qualquer uma das

ações em cada estado (esquerda, direita, aspirar)• Teste de objetivo: Verifica se todos os quadrados estão

limpos• Custo do caminho: Cada passo custa 1, e assim o custo

do caminho é o número de passos do caminho

Aula 3 - 18/08/2010

17

Exemplo 2: O quebra-cabeça de 8 peças

• Estados: especifica a posição de cada uma das peças e do espaço vazio.

• Estado inicial: qualquer um dos estados possíveis.• Ações/operadores: mover peças numéricas para espaços livres

(em branco) (esquerda, direita, para cima e para baixo)• Teste de objetivo: tabuleiro ordenado, com branco na posição

[3,3].• Custo do caminho: Cada passo custa 1, e assim o custo do

caminho é o número de passos do caminho

18

Árvore de busca para o Jogo dos 8 números

19

4 5 81 6

7 32

5 84 1 67 32

4 5 87 1 6

32

4 5 86

7 32

1

para cimaPara baixodireita

1 2 34 67 8

5

Para baixo

direita

Exemplos de formulação de problema

Dirigir de Recife (PE) a Juazeiro do Norte (CE)◦ Espaço de estados = todas as cidades do mapa

alcançáveis a partir do estado inicial◦ Estado inicial = estar em Recife◦ Teste de término (já atingimos o objetivo?) =

estar em Juazeiro do Norte◦ Ações/operadores = dirigir de uma cidade para

outra (se houver estrada entre elas!)◦ Função Custo do caminho = número de cidades

visitadas, distância percorrida, tempo de viagem, grau de divertimento, etc

20

Custo do caminho diferente => Solução diferente

•Função de custo de caminho

(1) distância entre as cidades

(2) tempo de viagem, etc.

•Solução mais barata:

(1) Camaragibe, Carpina, Patos, Milagres,...

(2) Moreno, Vitória de S. Antão, Caruaru, Salgueiro,...

apesar de mais longa, pega estradas melhores e evita as cidades.

21

Reci

fe –

Ju

aze

iro d

o

Nort

e

Reci

fe –

Ju

aze

iro d

o

Nort

e

Exemplo: viajar de Recife a Juazeiro

24

RecifeEstado inicial =>

Recife

Camaragibe Moreno Olinda

Recife

Camaragibe Moreno Olinda

Carpina Goiana

Aplicações de Busca: Problemas Reais

• Cálculo de rotas▫ rotas em redes de computadores▫ sistemas de planejamento de viagens▫ planejamento de rotas de aviões▫ caixeiro viajante

• Alocação (Scheduling)▫ Salas de aula▫ Máquinas industriais (job shop)

• Projeto de VLSI▫ Cell layout

25

Aplicações de Busca: Problemas Reais

•Navegação de robôs:▫generalização do problema da navegação▫robôs movem-se em espaços contínuos, com

um conjunto (infinito) de possíveis ações e estados

▫controlar os movimentos do robô no chão, e de seus braços e pernas requer espaço multi-dimensional

•Montagem de objetos complexos por robôs:▫ordenar a montagem das diversas partes do

objeto•etc...

26