IA_Aula03

Prévia do material em texto

*
PUCC
Inteligência Artificial
*
PUCC
Agenda - Aula 03
 Buscas
Agentes que Planejam
*
PUCC
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
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
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
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
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
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
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
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
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
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
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
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
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