Tópicos em Sistemas
Inteligentes
PUCC
1
Agenda - Aula 03
• Buscas
•Agentes que Planejam
PUCC
2
Memória X Computação
• Agentes Reativos fazem muito pouca
computação. Suas ações são definidas:
–
–
–
–
projetistas
aprendizado
processos evolutivos
combinação dos itens
• As ações são implementadas:
– tabelas
– Regras de Produção
– combinação de circuitos lógicos
PUCC
3
Memória X Computação
• Uma máquina reativa, capaz de realizar tarefas
complexas requer memória “infinita”
• O projetista dessa máquina teria que ter uma
capacidade de previsão sobre humana para
antecipar ações apropriadas.
• Assim, devemos considerar trade offs:entre tempo e
espaço e entre adaptação e projeto explícito.
• Devemos pensar em computações que prevejam
conseqüências das ações em qualquer situação
• O mais importante dessas computações é o
aprendizado e a evolução automático.
PUCC
4
Memória X Computação
• Assim, o agente usando de “programas” será
capaz de selecionar ações apropriadas
mesmo em ambientes que o projetista não foi
capaz de prever inicialmente.
• Para prever as conseqüências das ações, os
agentes devem ter um modelo do mundo que
“habita” e um modelo dos efeitos das suas
ações sobre o modelo do seu mundo.
PUCC
5
Grafo
• Empilhar três brinquedos:
– Na ordem A, B, C
– O robo pode mover qualquer bloco que não tenha
outro em cima.
– O modelo dessas ações é dada pela função
move(x,y) onde x= A,B ou C e y= A,B,C ou chão.
– O robo é capaz de modelar cada uma de suas
ações em seu ambiente. Mundo antes e depois da
ação.
PUCC
6
Grafo
• Suponha um robo capaz de modelar os
efeitos de cada uma de suas ações no seu
ambiente.
• “Par” de modelos do mundo. Um que
representa os estado do mundo antes da
ação e outro o estado do mundo após sua
ação.
• Grafo de Estado
PUCC
7
Grafo
• Conjunto de nós e arcos
• Olhar uma passo a frente em simulações
pode produzir previsões úteis. Olhar vários
passos pode evitar movimentos inúteis.
• A estrutura mais útil para acompanhar os
efeitos de várias seqüências alternativas de
ações é um grafo direto.
• O conjunto de “mundos” que o agente pode
produzir através de suas ações pode ser
representado por um grafo.
PUCC
8
Grafo
• Nesse grafo, os nós são rotulados como
“mundos individuais” enquanto os arcos são
rotulados por operadores.
• Se o número de situações diferentes do
mundo é pequena, um grafo pode
representar todas as possíveis ações e
situações explicitamente.
• Esse grafo é chamado de Grafo de Estado.
(state-space graph)
PUCC
9
Grafo
• Uma das vantagens de representar os
mundos “possíveis” numa estrutura de grafo
é que qualquer nó do grafo pode representar
um objetivo.
• Esta flexibilidade em realizar tarefas
diferentes constrasta com os agentes vistos
até agora, que eram capazes de realizar uma
única tarefa.
PUCC
10
Planejar
• Os operadores que são atributos dos arcos podem
ser agrupados em uma seqüência denominada
PLANO.
• A busca por essa seqüência é denominada
PLANEJAMENTO.
• Se o agente consegue representar todas as
situações relevantes do seu mundo por nós do grafo;
se conhecemos o resultados das ações; se o agente
é capaz de reconhecer o nó inicial; se não existe
outro agente mudando o mundo e; se temos tempo
suficiente para computações: é possível planejar
uma seqüência completa de ações sem necessidade
do retorno de sensores.
PUCC
11
Notação de Grafos
• Um grafo consiste de um conjunto de nós.
• Certos pares de nós são conectados por
arcos. Esses arcos são direcionados de um
nó para outro.
• Se um arco é direcionado de ni para nj então
nj é um sucessor (ou filho) de ni. Nesse caso,
ni é pai de nj.
• Um par de nós pode ser sucessor deles
mesmos se substituirmos arcos por ramos.
PUCC
12
Busca em Grafos
• Buscas envolvem a propagação de marcas
nos nós dos grafos.
• Busca em Largura
– Rotule o nó origem com Zero
– Propague números inteiros crescentes em ondas
através dos arcos até que um inteiro atinja o nó
destino.
– Realize um backtrack acompanhando uma
seqüência decrescente dos rótulos.
PUCC
13
Notação de Grafos
• Grafos que só contêm ramos são chamados
grafos não direcionados.
• Uma árvore direcionada é um caso particular
de um grafo onde cada nó, exceto um, tem
um único pai. Esse nó da exceção é
chamado de raiz.
• A raiz possui nível 0. O nível de cada nó da
árvore é o do seu pai mais 1.
• Um nó que não possua sucessores é
chamado de folha.
PUCC
14
Notação de Grafos
• Aos arcos são atribuídos custos positivos,
para representar o custo de realização de
uma ação.
• O custo de um passo entre dois nós é dado
pela soma dos custos de todos os arcos
conectando esses dois nós no passo.
• Caminho Mínimo
• Árvore Geradora de Custo Mínimo
PUCC
15