Inteligência Artificial Resolucao Problemas Busca Cega

  • View
    7.817

  • Download
    0

Embed Size (px)

Text of Inteligência Artificial Resolucao Problemas Busca Cega

Resoluo de ProblemasInteligncia Artificial Prof. Patrick Pedreira Silva

1

Agente de Resoluo de Problemas (1/2)O agente reativo Escolhe suas aes com base apenas nas percepes atuais no pode pensar no futuro, no sabe aonde vai4 7 5 1 2 8 6 3

?

1 4 7

2 5 8

3 6

J o agente baseado em objetivo... sabe, pois segue um objetivo explcito2

1

Agente de Resoluo de Problemas (2/2)Dentre as maneiras de implementar um agente baseado em objetivo existe o chamado Agente de Resoluo de Problemas serve para alguns tipos de problemas requer pouco conhecimento explcito basicamente busca uma seqncia de aes que leve a estados desejveis (objetivos)

Questes O que um problema e como formul-lo? Como buscar a soluo do problema?3

Problemas e Solues bem Definidos (1/2)Um problema em IA definido em termos de... 1) um espao de estados possveis, incluindo um estado inicial e um estado final (objetivo) exemplo 1: dirigir de Conquista a Ilhus exemplo 2: jogo de 8-nmeros4 5 8 1 6 7 2 3 1 2 3 4 5 6 7 8

2) um conjunto de aes (ou operadores) que permitem passar de um estado a outro ex1. dirigir de uma cidade a outra ex2. mover uma pea do jogo de n-nmeros (npuzzle)4

2

Problemas e Solues bem Definidos (2/2)Espao de Estados: conjunto de todos os estados alcanveis a partir do estado inicial por qualquer seqncia de aes.

Definio do objetivo: propriedade abstrata ex., condio de xeque-mate no Xadrez

conjunto de estados finais do mundo ex., estar em na cidade-destino

Soluo: caminho (seqncia de aes ou operadores) que leva do estado inicial a um estado final (objetivo).5

Solucionando o Problema:formulao, busca e execuoFormulao do problema e do objetivo: quais so os estados e as aes a considerar? qual (e como representar) o objetivo?

Busca (soluo do problema): processo que gera/analisa seqncias de aes para alcanar um objetivo soluo = caminho entre estado inicial e estado final.

Execuo: Executar (passo a passo) a soluo completa encontrada

6

3

Agentes Solucionadores de Problemasformulao, busca e execuofuno Agente-Simples-SP(p) retorna uma ao Agente- Simples- SP entrada: p, um dado perceptivo estado Atualiza-Estado (estado, p) Atualizase s (seqncia de aes) est vazia ento o (objetivo) Formula-Objetivo (estado) Formulaproblema Formula-Problema (estado, o) Formulas Busca (problema) ao Primeira (s, estado) s Resto (s, estado) retorna ao7

Medida de Desempenho na BuscaDesempenho de um algoritmo de busca: 1. O algoritmo encontrou alguma soluo? 2. uma boa soluo? custo de caminho (qualidade da soluo)

3. uma soluo computacionalmente barata? custo da busca (tempo e memria)

Custo total custo do caminho + custo de busca

Espao de estados grande: compromisso (conflito) entre a melhor soluo e a soluo mais barata8

4

Outro Exemplo: Ir de Conquista a Ilhus

Distncias e ligaes fictcias Cidades da Bahia e Minas Gerais

9

Exemplo ViagemIda para Conquista: estados = cada possvel cidade do mapa estado inicial = Conquista teste de trmino = estar em Ilhus operadores = dirigir de uma cidade para outra custo do caminho = nmero de cidades visitadas, distncia percorrida, tempo de viagem, grau de divertimento, etc

10

5

Mais um Exemplo...Aspirador de p estados = estado inicial = teste de trmino = operadores = custo da soluo =

11

Custo Diferente => Soluo DiferenteFuno de custo de caminho(1) nmero de cidades visitadas, (2) distncia entre as cidades, (3) tempo de viagem, etc.

Soluo mais barata:(1) Conquista, Potiragu, Itagimirim, ... (2) Conquista, Potiragu, Itagimirim, ... (3) Conquista, Brumado, Macabas, Bom Jesus da Lapa,...12

6

Importncia da formulao: 8 rainhasJogo das 8 Rainhas dispor 8 rainhas no tabuleiro de forma que no possam se atacar no pode haver mais de uma rainha em uma mesma linha, coluna ou diagonal

somente o custo da busca conta no existe custo de caminho

Existem diferentes estados e operadores possveis essa escolha pode ter conseqncias boas ou nefastas na complexidade da busca ou no tamanho do espao de estados13

Importncia da formulao: 8 rainhasFormulao A (incremental) estados: qualquer disposio com n (n 8) rainhas operadores: adicionar uma rainha a qualquer quadrado 64^8 possibilidades: vai at o fim para testar se d certo

Formulao B (incremental) estados: disposio com n (n 8) rainhas sem ataque mtuo (teste gradual) operadores: adicionar uma rainha na coluna vazia mais esquerda em que no possa ser atacada melhor (2057 possibilidades), mas pode no haver ao possvel

Formulao C estados: disposio com 8 rainhas, uma em cada coluna operadores: mover uma rainha atacada para outra casa na mesma coluna14

7

Importncia da formulao: 8-nmerosJogo de 8 nmeros: estados = cada possvel configurao do tabuleiro estado inicial = qualquer um dos estados possveis teste de trmino = ordenado, com branco na posio [3,3] operadores = mover branco (esquerda, direita, para cima e para baixo) custo da soluo = nmero de passos da soluo

cima

4 5 8 1 6 7 2 3direita

baixo

5 8 4 1 6 7 2 3baixo direita

4 5 8 1 6 7 2 3

4 5 8 7 1 6 2 3

1 2 3 4 5 6 7 8

15

Algumas Aplicaes

16

8

Aplicaes de Busca: Toy ProblemsJogo das n rainhas Jogo dos n nmeros (n-puzzle) Criptoaritmtica Torre de Hanoi Palavras cruzadas Canibais e missionrios17

send + more --------money

Aplicaes: Problemas ReaisClculo de rotas (pathfinding) rotas em redes de computadores sistemas de planejamento de viagens planejamento de rotas de avies Caixeiro viajante Jogos de computadores (rotas dos personagens)

Alocao (Scheduling) Salas de aula

Projeto de VLSI Cell layout (disposio de clulas na rea do chip) Channel routing (rota para fios passando por espaos vazios entre as clulas)

18

9

Aplicaes: Problemas ReaisNavegao de robs: generalizao do problema da navegao robs movem-se em espaos contnuos, com um conjunto (infinito) de possveis aes e estados controlar os movimentos do rob no cho, e de seus braos e pernas requer espao multi-dimensional

Montagem de objetos complexos por robs: ordenar a montagem das diversas partes do objeto

etc...19

Buscando SoluesBusca Cega

20

10

Busca em espao de estadosUma vez o problema bem formulado... o estado final deve ser buscado Em outras palavras, deve-se usar um mtodo de busca para saber a ordem correta de aplicao dos operadores que levar do estado inicial ao final Uma vez a busca terminada com sucesso, s executar a soluo (= conjunto ordenado de operadores a aplicar)

21

Busca em espao de estados: Gerao e testeFronteira do espao de estados Ns (estados) a serem expandidos no momento

Algoritmo:Obs.: O algoritmo comea com a fronteira contendo o estado inicial do problema. 1. Selecionar o primeiro n (estado) da fronteira do espao de estados; Se a fronteira est vazia, o algoritmo termina com falha Se sim, ento retornar n a busca termina com sucesso

2. Testar se o n um estado final (soluo) 3. Gerar um novo conjunto de estados pela aplicao dos operadores ao estado selecionado; 4. Inserir os ns gerados na fronteira, de acordo com a estratgia de busca usada, e voltar para o passo (1).22

11

Exemplo: viajar de Conquista a Ilhusestado inicial => Conquista Conquista Brumado Potiragu fronteira

fronteira

Conquista Brumado Potiragu

fronteira

Guanambi

Macabas

Belo Campo

23

Espao de Estados: ImplementaoEspao de Estados Podem ser representados como uma rvore onde os estados so ns e as operaes so arcos

Os ns da rvore podem guardar mais informaes do que apenas o estado: So uma estrutura de dados com 5 componentes:1. 2. 3. 4. 5. O estado correspondente O seu n pai O operador aplicado para gerar o n (a partir do pai) A profundidade do n O custo do n (desde a raiz)24

12

Busca em Espao de Estados: ImplementaoAlgoritmo: Funo-Insere: controla a ordem de insero de ns na fronteira do espao de estados Funo Busca-Genrica (problema, Funo-Insere) retorna uma soluo ou falha fronteira Faz-Fila (Faz-N (Estado-Inicial[problema])) loop do se fronteira est vazia ento retorna falha n Remove-Primeiro (fronteira) se Teste-Trmino[problema] aplicado a Estado [n] tiver sucesso ento retorna n fronteira Funo-Insere (fronteira, Operadores[problema])25

Mtodos de BuscaBusca exaustiva cega No sabe qual o melhor n da fronteira a ser expandido = menor custo de caminho desse n at um n final (objetivo) Estratgias de Busca (ordem de expanso dos ns): busca em largura busca em profundidade Direo de Busca: Do estado inicial para o objetivo Do objetivo para o estado inicial Busca heurstica informada Estima qual o melhor n da fronteira a ser expandido com base em funes heursticas => conhecimento Estratgia de busca: best-first search (melhor escolha) Direo de Busca: idem busca cega26

13

Critrios de Avaliao das Estratgias de BuscaCompletude: A estratgia sempre encontra uma soluo quando existe alguma?

Custo de tempo: Quanto tempo gasta para encontrar uma soluo?

Custo de memria: Quanta memria necessria para realizar a busca?

Otimalidade/qualidade (optimality): A estratgia encontra a melhor soluo quando existem diferentes solues?27

Buscando SoluesBusca Cega

28

14

Busca CegaEstratgias para determinar a ordem de ramificao dos ns:1. Busca em largura 2. Busca de custo uniforme 3. Busca em profundidade 4. Busca com aprofundamento iterativo

Direo da ramificao:1. Do estado inicial para um estado final 2. De um estado final para o estado inicia