View
28
Download
1
Category
Preview:
DESCRIPTION
Inteligência Artificial. Aula 03 – Espaço de Estados Grace Borges. Atividade 1 – Aplicações IA. Pesquise na internet ou em jornais e revistas especializadas um exemplo de aplicação de IA. Envie para: atividadesia@yahoo.com.br Assunto/ Subject: Atividade 1 – Aplicações de IA Identifique-se: - PowerPoint PPT Presentation
Citation preview
Inteligência Artificial
Aula 03 – Espaço de Estados
Grace Borges
Atividade 1 – Aplicações IA
Pesquise na internet ou em jornais e revistas especializadas um exemplo de aplicação de IA.
Envie para: atividadesia@yahoo.com.br Assunto/ Subject: Atividade 1 – Aplicações de IA Identifique-se:
Nome: Fulano de Tal Matrícula: xxxxx-x
2
Inteligência Artificial
É a área da Computação que estuda como simular comportamento ou pensamento inteligente usando métodos computacionais.
É uma ampla área de pesquisa que subdivide-se em diversas sub-áreas e está associada a várias aplicações práticas: Resolução de problemas, tomada de decisões; Jogos; Demonstração de teoremas; Compreensão visual, linguagem natural;
3
Abordagens da Inteligência Artificial
Abordagem centrada nos seres humanos
Abordagem racionalista
(Russell e Norvig, 2003)
Deve ser uma ciência empírica, envolvendo
hipóteses e confirmação experimental.
Envolve uma combinação de matemática e engenharia.
4
Abordagens de IA
Cada área da IA adota diferentes abordagens e trata diferentes problemas que, em geral, são de alta complexidade (para os quais ainda não temos soluções satisfatórias);
Porém, é possível utilizarmos abordagens híbridas, ou seja, combinar ferramentas de diferentes abordagens para se obter uma solução para um determinado problema;
5
• Agente = Percepção + Ação
Agente sensores
atuadores
Crença
Que ação tomar
Condições-regras
Am
bie
nte
Agentes Racionais
As verdades para esse agenteSua base de conhecimentos
6
O poder do conhecimento Como adquirir/ gerar conhecimento?
Especialistas Reconhecimento de Padrões Redes Neurais Seleção natural (algoritmos genéticos)
Como armazenar? Bases de conhecimento (diversas estruturas)
Como usar/recuperar esses conhecimentos? Algoritmos de Busca Máquina de inferências
7
Em busca de soluções
Um agente pode ter uma enorme quantidade de conhecimento armazenado;
Assim como nós, ele precisa usar apenas parte de seu conhecimento para resolver um problema;
Estratégia de busca serve para decidir que parte do conhecimento armazenado deve ser explorada em busca da solução;
8
Em busca de soluções
Busca: técnica de procura de soluções para um determinado problema;
Problema real problema de busca: Situação inicial (Estado inicial) Ações possíveis (Transições entre estados
possíveis do problma) Estado meta (solução)
Exemplo: uma caneta que funcione
9
Em busca de soluções
Problema: tenho 4 canetas na minha escrivaninha e preciso de 1 que funcione Estado inicial: 4 canetas (não sei se funcionam) Ações: experimentar cada caneta, descarta se não
funciona (se funcionar, atingiu a meta) Meta: achar 1 caneta que funcione
Estratégia: busca exaustiva E se fossem 400 canetas? Espaço de busca muito grande Desperdício de esforço (processamento)
10
Busca exaustiva ou Força bruta
Exige velocidade de processamento; Nem sempre alcança a solução em tempo aceitável; Muitos problemas podem levar a uma explosão
combinatória: número de possibilidades não aumenta de maneira linear, mas numa taxa muito mais rápida. Ex.: Fábula do tabuleiro de xadrez e os grãos de trigo (4
séculos de produção de trigo) Pode ser usado após redução do espaço de busca
(heurística); Utiliza suposições ou pistas para solução de um problema –
elementos do mundo real para ajudar nas buscas.11
Busca de soluções Qualquer tentativa de resolução de um problema
pressupõe que existe uma solução; Não faz sentido desenvolver sistema inteligente
para procurar infinitamente uma solução que não existe;
Saber que a solução existe num dado espaço de busca pode ser útil para o projeto de planejamento e estratégia de busca.
Quanto maior o espaço de busca, maior a probabilidade de conter a solução, porém,
menor a probabilidade de encontrá-la. 12
Como definir o espaço de Busca?
Existem vários algoritmos de busca que serão
estudadas ao longo da disciplina;
Porém, todos eles fazem suas buscas pela solução
dentro de conjunto de possibilidades possíveis para
o seu problema.
A representação de: Todos os possíveis estados de um problema e
As ações possíveis que levam um estado a outro
é chamado de Espaço de Estados.
13
O que é espaço de estados?
Como representar esses estados? Podemos usar 2 representações para nosso problema:
Representação formal; Grafos;
Formalmente, podemos definir: um conjunto S de estados e; um conjunto A de ações que mapeiam um estado em
outro. Exemplo: Mundo do aspirador [Russel]
14
Mundo do aspirador
Nesse mundo, o agente é um aspirador cuja função é limpar as salas de um edifício;
Suponhamos que o mundo desse agente seja composto de apenas duas salas, cada uma delas podendo estar limpa ou suja;
O aspirador é capaz de executar apenas três ações: entrarSala1 entrarSala2 aspirar
15
Representação dos estados Como representar este problema?
Indicar se o aspirador está na sala 1 ou na sala 2 Se a sala 1 está limpa ou suja Se a sala 2 está limpa ou suja
Podemos usar uma estrutura da forma [X, Y, Z]:X indica a posição do aspirador: {1,2}Y indica se a primeira sala está suja: {0, 1}Z indica se a segunda sala está suja: {0, 1}
Ex.: Aspirador na sala 2 e apena a 1 está limpa = [2; 0; 1]
Pergunta: Quantos estados tem este problema?16
Representação das ações
As ações podem ser representadas por operadores:
oper(α; s; s’) β
Onde α é uma ação que transforma o estado s em s’ dado que a condição β esteja satisfeita.
Por exemplo, a ação aspirar pode ser representada pelos seguintes operadores:
oper(aspirar; [1; Y; Z]; [1; 0; Z]) Y = 1
oper(aspirar; [2; Y; Z]; [2; Y; 0]) Z = 117
Representação das ações
Outra forma:oper(aspirar; [1; 1; Z]; [1; 0; Z])
oper(aspirar; [2; Y; 1]; [2; Y; 0])
Conjunto de ações do aspiradorA = { oper(entrarSala1; [2; Y;Z]; [1; Y;Z]),
oper(entrarSala2; [1; Y;Z]; [2; Y;Z]),
oper(aspirar; [1; 1;Z]; [1; 0;Z]),
oper(aspirar; [2; Y; 1]; [2; Y; 0]) }18
Estados sucessores
Dado um estado s pertencente ao conjunto S, seus estados sucessores são todos aqueles que podem ser atingidos, a partir de s, pela aplicação de um dos operadores do domínio.
Por exemplo, expandindo o estado [2; 0; 1], obtemos como estados sucessores [1; 0; 1] e [2; 0; 0].
[2;0;1]
[2;0;0][1;0;1]
entrarSala1 aspirar
19
Estados sucessores
Esses estados são gerados pela aplicação dos operadores entrarSala1 e aspirar, respectivamente.
Note, por exemplo, que o operador entrarSala2 não pode ser usado na expansão do estado [2; 0; 1]; já que, nesse estado, a condição implícita do operador (i.e. Y = 1) não está satisfeita.
[2;0;1]
[2;0;0][1;0;1]
entrarSala1 aspirar
20
Atividade 2: Espaço de estados
FATEC – ADS IA – Prof. Grace - 24/02/2012Nome: Fulano de Tal – Matrícula: xxxxx-xAtividade 2 – Espaço de estados
Desenhe um grafo representando o espaço de estados para o Mundo do Aspirador.
Nesse grafo, cada nó será um estado do mundo e cada arco (rotulado com uma ação) será uma transição entre dois estados.
Os arcos devem ser direcionados do estado para seu estado sucessor. 21
Grafo do Espaço de Estados
[2;0;1]
[2;0;0]
[1;0;1]
entrarSala1
aspirar
[1;1;1]
[1;1;0]
[1;0;0]
[2;0;1]
[2;1;1]entrarSala2
entrarSala2
entrarSala1
aspirar
aspirar aspirar
entrarSala2 entrarSala2entrarSala1 entrarSala1
22
Atividade 3: Aspirador com 2 pisos Considere uma versão do Mundo do Aspirador
onde há um prédio com dois pisos;
Cada piso possui duas salas (1 e 2) e um
saguão (0).
Não há passagem direta de uma sala para
outra, de modo que o aspirador tem que estar
no saguão para entrar numa sala ou para
mudar de piso.23
Atividade 3:Aspirador com 2 pisos Para representar os estados nessa versão do
problema, podemos usar uma estrutura da forma
[Pos; Piso1; Piso2], onde:
Pos = [Piso; Sala], podendo Piso assumir {1, 2} e
Sala {0, 1, 2}: indica a posição corrente do
aspirador.
Piso1 = [X; Y ], podendo X e Y assumir {0, 1}: indica
se as salas 1 e 2 do piso 1 estão limpas ou sujas.
Piso2 = [X; Y ], podendo X e Y assumir {0, 1}: indica
se as salas 1 e 2 do piso 2 estão limpas ou sujas. 24
Atividade 3:Aspirador com 2 pisos Exemplo: [[1; 0]; [0; 0][1; 0]].
Pos = [1; 0]: aspirador está no 1º piso, no saguão Piso1 = [0; 0]: salas 1 e 2 estão limpas no 1º piso Piso2 = [1; 0]: sala 1 suja e sala 2 limpa no 2º piso
Com base nessa representação, codifique os operadores para as ações subir, descer, entrarSala1, entrarSala2, aspirar e sair.
Obs.: Não precisa desenhar o grafo. Pergunta: Quantos estados este problema possui?
25
Atividade 4 - Missionários
Três missionários e três canibais vão atravessar de uma
margem para a outra de um rio, usando um barco onde
só cabem duas pessoas de cada vez.
O número de canibais não pode exceder o número de
missionários em nenhuma das margens do rio.
Encontre uma forma de levar todos para a outra
margem do rio, utilizando este barco.
Formule o problema (represente estados e ações).
Enviar atividade para: atividadesia@yahoo.com.br
26
Seminários e Grupos
1. Planejamento
2. Visão Computacional
3. Aprendizagem e Redes Neurais
4. Data mining e Sistemas de recomendação
5. Proc. Ling. Natural e Text Mining
6. Chatter Bot
7. Jogo 1 – Sudoku
8. Jogo 2 – Jogo da onça
9. Jogo 3 – Pet Squares27
Calendário de aulas (previsão)
24/Fev – Espaço de Estados 02/Mar – Algoritmos de Busca 09/Mar – Algoritmos de Busca 16/Mar – Não haverá aula (evento externo) 23/Mar – Sem. 1 – Planejamento 30/Mar – Sem. 2 – Visão Computacional 06/Abr – Semana Santa 13/Abr – Não haverá aula (evento externo) 28
Calendário de aulas (previsão)
20/Abr – Sem. 3 – Aprendizagem e Redes Neurais 27/Abr – Sem. 4 - Data Mining e Sist. Recomendação 04/Mai - Sem. 5 – Proc. Ling. Natural e Text Mining 11/Mai – Sem. 6 – Chatter Bot 18/Mai – Não haverá aula (evento externo) 25/Mai – Sem. 7 – Sudoku 01/Jun – Sem. 8 e 9 – Jogo da Onça e Pet Squares 08/Jun – Corpus Christi 15/Jun – Não haverá aula (evento externo) 22/Jun - Entrega de Notas 29
Recommended