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: [email protected]

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
Deve ser uma ciência
empírica, envolvendo
hipóteses e confirmação
experimental.
Envolve uma
combinação de
matemática e
engenharia.
4
(Russell e Norvig, 2003)
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
Agentes Racionais
• Agente = Percepção + Ação
Agente
sensores
Que ação
tomar
Ambiente
Crença
Condiçõesregras
As verdades para esse agente
Sua base de conhecimentos
atuadores
6
O poder do conhecimento

Como adquirir/ gerar conhecimento?





Como armazenar?


Especialistas
Reconhecimento de Padrões
Redes Neurais
Seleção natural (algoritmos genéticos)
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:



Formalmente, podemos definir:



Representação formal;
Grafos;
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 = 1
17
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 aspirador
A={
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]
entrarSala1
[1;0;1]
aspirar
[2;0;0]
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]
entrarSala1
[1;0;1]
aspirar
[2;0;0]
20
Atividade 2:
Espaço de estados
FATEC – ADS
IA – Prof. Grace - 24/02/2012
Nome: Fulano de Tal – Matrícula: xxxxx-x
Atividade 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
21
estado sucessor.
Grafo do Espaço de Estados
[1;1;1]
entrarSala2
entrarSala1
[2;1;1]
aspirar
aspirar
[1;0;1]
entrarSala2
[2;0;1]
entrarSala1
[2;0;1]
entrarSala2
entrarSala1
[1;1;0]
aspirar
aspirar
[2;0;0]
entrarSala1
entrarSala2
[1;0;0]
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: [email protected]
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 Squares
27
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