IF67B C71 aula04

Prévia do material em texto

IF71B-C71 - Inteligeˆncia Artificial
Aula 04 - Resoluc¸a˜o de Problemas por Busca
Profa. Dra. Priscila T iemi çaeda Saito
k psaito@utfpr.edu.br
2o Semestre 2016
18/08/16
Roteiro
1 Resoluc¸a˜o de Problemas por Busca
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 2 / 49
Motivac¸a˜o
Estrate´gia de busca e´ uma das mais poderosas abordagens para
resoluc¸a˜o de problemas em IA
Explora sistematicamente as alternativas
Encontra a sequeˆncia de passos para uma soluc¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 3 / 49
Exemplo de Problema
Viajar de Corne´lio Proco´pio a Mar´ılia
I adotando a menor rota poss´ıvel
I 172 km - aprox. 2 horas e 10 minutos - Google Maps
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 4 / 49
Resoluc¸a˜o de Problemas
Primeiro passo: formular objetivos
I o que deve ser alcanc¸ado
F ir a Mar´ılia
I baseado em situac¸a˜o atual
F estamos em Corne´lio Proco´pio
I e medida de desempenho
F quero seguir a menor rota rodovia´ria poss´ıvel
Objetivo pode ser visto como um estado
I entre poss´ıveis estados do problema
F Ex.: estado: estar em alguma cidade
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 5 / 49
Resoluc¸a˜o de Problemas
Podem haver estados intermedia´rios no “caminho” da soluc¸a˜o
I Ex.: ha´ duas estradas saindo de Corne´lio Proco´pio (CP)
F CP → Assis
F CP → Santa Mariana
Descobrir que sequeˆncia de ac¸o˜es levara´ ao objetivos
Que cidades percorrer para chegar a Mar´ılia?
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 6 / 49
Resoluc¸a˜o de Problemas
Segundo passo: formular o problema
I processo de decidir que ac¸o˜es e estados devem ser considerados, dado
um objetivo
I No exemplo:
F Ac¸o˜es = direc¸o˜es
F Estados = cidades percorridas
F Objetivo = chegar a Mar´ılia a partir de Corne´lio Proco´pio usando
menor rota
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 7 / 49
Resoluc¸a˜o de Problemas
Terceiro passo: buscar soluc¸a˜o
I processo de procurar por sequeˆncia de ac¸o˜es que alcanc¸am o objetivo
I algoritmo de busca
F entrada = problema
F sa´ıda = sequeˆncia de ac¸o˜es para chegar a` soluc¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 8 / 49
Resoluc¸a˜o de Problemas
“Uma vez a soluc¸a˜o e´ encontrada, as ac¸o˜es recomendadas podem ser
executadas”
Execuc¸a˜o
I no exemplo consiste em seguir a rota de cidades recomendada
I execuc¸a˜o pode ser intercalada com a busca
F roboˆ percebendo o ambiente e enta˜o navegando
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 9 / 49
Resoluc¸a˜o de Problemas
Treˆs etapas principais:
I formulac¸a˜o do problema
I busca de soluc¸o˜es
I execuc¸a˜o da soluc¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 10 / 49
Outro Exemplo
Para o problema da Romeˆnia
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 11 / 49
Problema
Definido por cinco componentes:
1 Estado inicial
2 Ac¸o˜es/operadores poss´ıveis para gerar novo estado
3 Modelo de transic¸a˜o
4 Teste de objetivo
5 Uma func¸a˜o de custo de caminho
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 12 / 49
Problema
Estado inicial
I Ex.: Em(Arad)
Ac¸o˜es/operadores poss´ıveis para gerar novo estado
I Ex.: Em(Arad) = {Ir(Sibiu), Ir(Timisoara), Ir(Zerind)}
I Estado inicial e operadores definem espac¸o de estados
F conjunto de todos os estados acess´ıveis a partir do estado inicial
F forma um grafo
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 13 / 49
Problema
Modelo de transic¸a˜o
I descric¸a˜o do que cada ac¸a˜o faz
I Ex.: RESULTADO(Em(Arad), Ir(Zerind)) = Em(Zerind)
Teste de objetivo
I determinar se um dado estado e´ um estado objetivo
I No ex., o objetivo e´ o conjunto unita´rio {Em(Bucareste)}
Uma func¸a˜o de custo de caminho
I atribui custo nume´rico a cada caminho no grafo
I caminho e´ uma sequeˆncia de estados conectados
I geralmente reflete medida de desempenho
F no ex., menor caminho em km
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 14 / 49
Grafo
Representac¸a˜o gra´fica das relac¸o˜es entre elementos de dados
I G = {V, A}
F conjunto V de ve´rtices
F conjunto A de arestas
V = {1, 2, 3}
A = {(1,2),(1,3),(2,3)}
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 15 / 49
Exemplos
Rede de computadores
I ve´rtices = terminais
I arestas = cabos de rede
F custo = lateˆncia
F lateˆncia e´ o tempo que uma unidade de informac¸a˜o leva para transitar
pela rede de um ponto a outro
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 16 / 49
Exemplo
Rede social
I ve´rtices = pessoas
I arestas = relac¸a˜o social entre pessoas
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 17 / 49
Soluc¸a˜o
Uma soluc¸a˜o para um problema e´ um caminho desde o estado inicial
ate´ o estado objetivo
I soluc¸a˜o o´tima tem menor custo de caminho entre todas as poss´ıveis
soluc¸o˜es
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 18 / 49
Como Formular um Problema?
Como escolher estados e ac¸o˜es?
Abstrair detalhes irrelevantes
I na formulac¸a˜o do problema (ac¸o˜es e estados)
I nas func¸o˜es de custo de caminho e de busca
Exemplo: dirigir de Corne´lio Proco´pio a Mar´ılia
I na˜o e´ de interesse:
F nu´mero de passageiros
F o que toca no ra´dio (estado)
F cidades sem acesso rodovia´rio (estado)
F o que se come e bebe dentro do carro (ac¸o˜es)
F nu´mero de postos policiais no caminho (custo de caminho)
I e´ tarefa do projetista fazer as boas escolhas
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 19 / 49
Exemplo Problema 1
Aspirador de po´
I percorre quadrados e veˆ se tem sujeira a limpar
Operac¸o˜es poss´ıveis:
I mover para a direita
I mover para a esquerda
I aspirar po´
I na˜o fazer nada
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 20 / 49
Aspirador de Po´
Formulac¸a˜o do problema
I estados:
F 2 quadrados, contendo ou na˜o sujeira
F 8 estados poss´ıveis
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 21 / 49
Aspirador de Po´
Formulac¸a˜o do problema:
I estado inicial:
F qualquer um dos estados poss´ıveis
F ex.: estado 5
I ac¸o˜es: 3 (R, L e S)
I modelos de transic¸a˜o: sa˜o as setas da figura
F todas ac¸o˜es teˆm um efeito esperado
F exceto algumas (destacadas) que na˜o teˆm nenhum efeito
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 22 / 49
Aspirador de Po´
Formulac¸a˜o do problema:
I teste de objetivo:
F verificar se quadrados esta˜o limpos
I custo de caminho:
F cada passo custa 1
F custo do caminho e´ o nu´mero de passos do caminho
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 23 / 49
Aspirador de Po´
O estado inicial e´ um dos poss´ıveis estados: {1, 2, 3, 4, 5, 6, 7, 8}
Executar a ac¸a˜o moverDireita sempre vai levar o agente para um dos
estados:
I ?
A sequeˆncia de ac¸o˜es [MoverDireita, Limpar] sempre vai levar o
agente para um dos estados:
I ?
A sequeˆncia de ac¸o˜es [MoverDireita, Limpar, MoverEsquerda, Limpar]
sempre vai levar o agente para o estado:
I ?
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 24 / 49
Aspirador de Po´
O estado inicial e´ um dos poss´ıveis estados: {1, 2, 3, 4, 5, 6,7, 8}
Executar a ac¸a˜o moverDireita sempre vai levar o agente para um dos
estados:
I {2, 4, 6, 8}
A sequeˆncia de ac¸o˜es [MoverDireita, Limpar] sempre vai levar o
agente para um dos estados:
I ?
A sequeˆncia de ac¸o˜es [MoverDireita, Limpar, MoverEsquerda, Limpar]
sempre vai levar o agente para o estado:
I ?
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 24 / 49
Aspirador de Po´
O estado inicial e´ um dos poss´ıveis estados: {1, 2, 3, 4, 5, 6, 7, 8}
Executar a ac¸a˜o moverDireita sempre vai levar o agente para um dos
estados:
I {2, 4, 6, 8}
A sequeˆncia de ac¸o˜es [MoverDireita, Limpar] sempre vai levar o
agente para um dos estados:
I {4, 8}
A sequeˆncia de ac¸o˜es [MoverDireita, Limpar, MoverEsquerda, Limpar]
sempre vai levar o agente para o estado:
I ?
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 24 / 49
Aspirador de Po´
O estado inicial e´ um dos poss´ıveis estados: {1, 2, 3, 4, 5, 6, 7, 8}
Executar a ac¸a˜o moverDireita sempre vai levar o agente para um dos
estados:
I {2, 4, 6, 8}
A sequeˆncia de ac¸o˜es [MoverDireita, Limpar] sempre vai levar o
agente para um dos estados:
I {4, 8}
A sequeˆncia de ac¸o˜es [MoverDireita, Limpar, MoverEsquerda, Limpar]
sempre vai levar o agente para o estado:
I 7
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 24 / 49
Exemplo Problema 2
Quebra-cabec¸a de 8 pec¸as
I tabuleiro 3x3 com 8 pec¸as numeradas e um espac¸o vazio
I uma pec¸a pode deslizar para o espac¸o
I exemplo:
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 25 / 49
Quebra-cabec¸a
Formulac¸a˜o do problema: um estado especifica a posic¸a˜o de cada
pec¸a e do espac¸o vazio nos 9 quadrados
I estado inicial: qualquer estado
I ac¸o˜es: espac¸o vazio se desloca para esquerda, direita, cima ou baixo
I modelo de transic¸a˜o: dado um estado e ac¸a˜o, ele devolve estado
resultantes (move 6 para baixo)
I teste de objetivo: o estado e´ o final?
I custo do caminho: cada passo custa 1 e custo do caminho = # de
passos no caminho
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 26 / 49
Quebra-cabec¸a
Problema dos quebra-cabec¸as deslizantes
NP-completo
I ainda na˜o existem algoritmos determin´ısticos que encontram a soluc¸a˜o
em tempo polinomiais
F 8 pec¸as: 181440 estados poss´ıveis
F 15 pec¸as: 1.3 trilha˜o de estados
F 24 pec¸as: 1025 estados
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 27 / 49
Exemplo Problema 3
Problema das 8 rainhas
I posicionar 8 rainhas em um tabuleiro de xadrez de forma que nenhuma
rainha ataque outra
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 28 / 49
Exemplo Problema 3
Problema das 8 rainhas
I posicionar 8 rainhas em um tabuleiro de xadrez de forma que nenhuma
rainha ataque outra
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 29 / 49
8 rainhas
Formulac¸a˜o incremental: adiciona rainhas ao tabuleiro
I estados: qualquer disposic¸a˜o de 0 a 8 rainhas no tabuleiro. Ha´ 3x1014
poss´ıveis estados
I estado inicial: nenhuma rainha no tabuleiro
I ac¸o˜es: colocar uma rainha qualquer em um espac¸o vazio
I teste de objetivo: 8 rainhas no tabuleiro e nenhuma e´ atacada
I custo: na˜o e´ de interesse, pois apenas o estado final e´ importante
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 30 / 49
Outros Problemas
Torre de Hanoi
Canibais e missiona´rios
Treˆs missiona´rios e treˆs canibais va˜o atravessar de uma margem para a
outra de um rio, usando um barco onde so´ cabem duas pessoas de cada
vez. Os missiona´rios teˆm que ser cautelosos para que os canibais nunca os
excedam em nu´mero em nenhuma das margens do rio. Como podera˜o
passar todos para a outra margem, usando apenas aquele barco?
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 31 / 49
Problemas Reais
Problema de roteamento
I exemplos:
F roteamento de pacotes em rede de computadores
F planejamento de operac¸o˜es militares
F sistema de planejamento de viagens ae´reas
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 32 / 49
Exemplo - Viagens Ae´reas
Formulac¸a˜o do problema:
I estados: cada estado e´ uma posic¸a˜o (aeroporto) e hora atual
I estado inicial:
F especificado pelo problema
I ac¸o˜es:
F pegar qualquer voo a partir da posic¸a˜o atual
I modelo de transic¸a˜o:
F estado resultante tera´ o destino e hora´rio de chegada
I teste de objetivo:
F estar no destino apo´s um tempo especificado
I custo de caminho:
F tempo da viagem, tempo de espera, horario do voo, valor da moeda,
qualidade do assento, horario do dia, tipo de avia˜o, milhagem
acumulada
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 33 / 49
Problemas Reais
Problema do caixeiro-viajante
visitar um conjunto de cidades uma u´nica vez usando o percurso mais
curto
exemplo:
I planejar viagens
I planejar movimentos de ma´quinas
F perfurac¸a˜o de placas de circuito
F industriais
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 34 / 49
Problemas Reais
Layout de VLSI
I posicionamento de componentes e conexo˜es em chip minimizando
F a´rea
F retardos de circuitos
I e maximizando
F rendimento industrial
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 35 / 49
Problemas Reais
Navegac¸a˜o de roboˆs
I generalizac¸a˜o do problema de roteamento
I lidar tambe´m com erros em sensores e controles
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 36 / 49
Busca por Soluc¸o˜es
Resoluc¸a˜o dos problemas apo´s formulac¸a˜o
por meio de busca no espac¸o de estados
I sequeˆncia de ac¸o˜es poss´ıveis formam a´rvore de busca:
F com estado inicial na raiz
F ramos sa˜o as ac¸o˜es
F no´s sa˜o os estados no espac¸o de estados do problema
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 37 / 49
Exemplo
Para o problema da Romeˆnia
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 38 / 49
Exemplo
(a) Estado inicial
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 39 / 49
Exemplo
(b) Expandindo Arad
Qual escolher para futuras considerac¸o˜es?
Esseˆncia da busca: seguir uma opc¸a˜o e deixar as outras reservadas para
mais tarde, no caso da primeira na˜o levar a uma soluc¸a˜o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 40 / 49
Exemplo
(c) Supor escolha de Sibiu
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 41 / 49
Exemplo
(c) Expandindo Sibiu
Pode escolher entre quaisquer estados ainda na˜o visitados
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 42 / 49
Busca
Continua-se a escolher, testar e expandir ate´
I encontrar soluc¸a˜o ou
I na˜o existirem mais estados a serem visitados
A estrate´gia de escolha de estado a visitar e expandir e´ determinada
pela estrate´gia de busca
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 43 / 49
Algoritmo
Algoritmo geral de busca em a´rvore
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 44 / 49
A´rvore de Busca
Os no´s da a´rvore podem guardar mais informac¸a˜o do que apenas o
estado: estrutura de dados com pelo menos 5 componentes:
1 o estado correspondente
2 o seu no´ pai
3 o operador aplicado para gerar o no´ (a partir do pai)
4 a profundidade do no´
5 o custo do no´ (desde a raiz)
6 os no´s filhosUTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 45 / 49
A´rvore de Busca
Exemplo:
I No´ Sibiu
F pai = Arad
F operador = ir de Arad a Sibiu
F profundidade = 1
F custo = x km
F filhos = {Arad, Fagaras, Oradea, Rimmici}
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 46 / 49
Atividade da Disciplina
Resolver o problema apresentado no pro´ximo slide manualmente
Entregar um relato´rio apresentando respostas a`s seguintes questo˜es:
I Qual o estado inicial do problema?
I Qual foi a quantidade de passos que voceˆ executou para resolver o
problema?
I Voceˆ utilizou alguma estrate´gia para resolver o problema? Obs.: Caso
na˜o tenha utilizado nenhuma estrate´gia apenas indique que nenhuma
estrate´gia foi utilizada
Elaborar um v´ıdeo utilizando um software de captura de tela com a
sua resoluc¸a˜o manual do problema
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 47 / 49
Atividade da Disciplina
Acessar o site:
I http://www.goriya.com/java/sliders/sliders.shtml ou
I http://funmin.com/online-games/n-puzzle/
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 48 / 49
Refereˆncias
Livro Russel e Norvig, cap´ıtulo 3
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula04-Resoluc¸a˜o - Problemas 49 / 49
	Resolução de Problemas por Busca