Planejamento
Viviane Torres da Silva
[email protected]
http://www.ic.uff.br/~viviane.silva/2010.1/isma
Planos

As tarefas associadas aos planos são:
– Planejamento: criação de planos
– Seleção de planos
– Execução dos planos
Objetivos
Estado inicial
Ações

Planejamento
p{i}
Seleção
p
Execução
Planejamento
– A criação dos planos é feita a partir de um conjunto de sub-passos (ou
ações)
Representações

Representação de estados:
– Infeliz ^ Triste
– Acima(B,A)

estado de uma pessoa
estado do bloco B
B
A
Representação de objetivos:
– É um estado especial, estado futuro que se deseja alcançar
– Ex.: Feliz ^ Contente
A
– Ex.: Acima (B,Mesa)

Representação de ações:
– É descrita por suas pré-condições e suas pós-condições
– Ex: Mover(B,A,Mesa)
– Pré-condições: ¬Acima(B,Mesa) ^ Acima(_,B) ^ MesaLivre
– Pós-condições: Acima(B,Mesa) ^ ¬ MesaLivre
B
B
A
Representações

Uma ação pode ser executada em qualquer estado no qual o
conjunto de pré-condições da ação seja verdadeiro

Depois da execução da ação, suas pós-condições refletem o
estado do ambiente

Um plano é uma seqüência de ações que quando executado a
partir de um estado inicial resulta em um estado final que
alcance o objetivo
Ambiente

Observável: podemos observar o estado das entidades no
ambiente

Determinista: sabemos qual é a conseqüência da execução de
uma ação

Estático: ambiente se modifica somente quando o agente
executa uma tarefa

Discreto: número fixo e finito de ações e objetos
Exemplo: O mundo dos blocos

Só um único bloco pode estar diretamente acima de outro
bloco
Um robô pode pegar um único bloco de cada vez e mover o
bloco para outra posição
O robô não pode pegar um bloco que leve outro em cima

Objetivo: colocar os blocos em uma determinada posição


Exemplo: O mundo dos blocos

Estados:
– Acima(B,A): B está acima de A (A pode ser a mesa)
– Livre(C): C não tem nenhum bloco acima

Ações:
– Mover(B,A,C): Mover B de A para C
• Precondições: Acima(B,A) ^ Livre(B) ^ Livre(C)
• Póscondições: Acima(B,C) ^ Livre(A) ^ ¬ Acima(B,A)
^ ¬ Livre(C)
– MoverParaMesa(B,A): Mover B de A para a mesa
• Precondição: Acima(B,A) ^ Livre(B)
• Póscondições: Acima(B,Mesa) ^ Livre(A) ^ ¬ Acima(B,A)
Algoritmos de Planejamento


Busca para frente
Busca para trás
Estado inicial: Acima(B,A)
Livre(B)
Livre(C)
Livre(D)
Objetivo: Acima(C,A)
Acima(D,B)
Livre(D)
Livre(C)
B
A
C
D
C
D
A
B
Busca para frente

Quais são as ações aplicadas ao estado atual que podem gerar o
objetivo?

Começamos considerando o estado inicial

Selecionamos as ações que podem ser aplicadas a partir do
estado inicial
– As ações aplicadas são aquelas cujas pré-condições são subconjunto do
estado inicial
– As pós-condições da ação aplicada gera o próximo estado

Aplicamos o passo anterior até encontrar o objetivo
– O objetivo deve ser o estado representado nas pós-condições das ações
Exemplo
B
A
C
Acima(B,A)
Livre(B)
Livre(C)
Livre(D)
Acima(C,A)
Livre(B)
Livre(C)
Livre(D)
D
Mover(B,A,C)
Mover(B,A,D)
Mover(C,Mesa,B)
MoverParaMesa(B,A)
Mover(C,Mesa,D)
Mover(D,Mesa,C)
Mover(D,Mesa,B)
MoverParaMesa(B,A)
…
Acima(C,A)
Acima(D,B)
Livre(C)
Livre(D)
Livre(A)
Livre(B)
Livre(C)
Livre(D)
Mover(C,Mesa,A)
Mover(C,Mesa,B)
Mover(C,Mesa,D)
…
Mover(D,Mesa,A)
Mover(D,Mesa,C)
Mover(D,Mesa,B)
Mover(C,Mesa,A)
Mover(B,Mesa,A)
Mover(B,Mesa,C)
Mover(B,Mesa,D)
…
Mover(A,Mesa,B)
Mover(A,Mesa,C)
Mover(A,Mesa,D)
C
D
A
B
Busca para trás

Quais são os estados a partir dos quais aplicando uma ação se
gera o objetivo?

Começamos considerando o estado final, o objetivo

Selecionamos as ações que podem ter sido aplicadas para gerar
o objetivo
– As ações aplicadas são aquelas cujas pós-condições geram uma das
condições do objetivo
– Somente consideramos ações relevantes, as que sabemos que podem
chegar ao objetivo
– As pré-condições da ação aplicada definem o próximo estado

Aplicamos o passo anterior até encontrar o estado inicial
Exemplo
C
D
C
A
B
A
Acima(C,A)
Acima(D,B)
Livre(C)
Livre(D)
Livre(A)
Livre(B)
Livre(C)
Livre(D)
Move(D,Mesa,B)
Move(D,C,B)
Move(D,Mesa,B)
Move(C,Mesa,A)
Move(C,D,A)
…
D
B
Acima(C,A)
Livre(B)
Livre(C)
Livre(D)
MoveParaMesa(B,D)
MoveParaMesa(B,C)
Move(C,Mesa,A)
MoveParaMesa(D,B)
MoveParaMesa(D,C)
Move(C,Mesa,A)
Move(C,B,A)
Move(C,D,A)
Acima(B,A)
Livre(B)
Livre(C)
Livre(D)
B
A
C
D
Ordenação parcial dos planos

Trabalhar com uma abordagem que considere que existem
vários sub-objetivos independentes

Solucionar cada um como um sub-plano

Combinar os sub-planos

É possível escolher os sub-objetivos mais importantes para
começar
Ex.: Planejar uma viagem de avião de Rio a Madrid

1. Encontrar um vôo de Rio a Madrid
2. Verificar como chegar da nossa casa até o aeroporto
3. Verificar como chegar do aeroporto de Madrid ao hotel
Exemplo: Colocar os sapatos

Objetivo: ter os sapatos postos
– Sub-objetivos: ter a meia direita posta, ter a meia esquerda posta, ter o
sapado direito posto e ter o sapato esquerdo posto

Ações:
– Colocar a meia direita
– Colocar a meia esquerda
– Calçar o sapato direito
– Calçar o sapato esquerdo

Existe uma ordem entre meia e sapado mas não existe ordem
entre esquerda e direita
– Colocar a meia esquerda tem que vir antes de calçar o sapato esquerdo
– Mas não é necessário executar exatamente antes
Quando consideramos organizações

Agentes na organização interagem para alcançar objetivos da
organização
Existem três tipos de planejamento:
 Planejamento centralizado para sistemas multi-agentes
– Um único agente faz o planejamento para os demais agentes

Coordenação centralizada dos planos parciais (ou sub-planos)
– Cada agente faz o planejamento de sub-planos para alcançar seus objetivos
individuais
– Um coordenador central tenta coordenar a execução dos sub-planos

Planejamento distribuído
– Não existe um coordenador central
– Os agentes negociam para coordenar suas ações e solucionar problemas
Planejamento centralizado para SMA

As tarefas que o agente tem que executar quando está
planejando para um conjunto de agentes ou para um único
agente são similares
1.
Ver o plano como um diagrama de estados acíclicos
(os estados são as ações)
2.
3.
Determinar quais ações podem ser executadas em paralelo e
introduzir ponto de sincronização
Distribuir a execução das ações para os vários agentes
Coordenação centralizada de planos parciais

Cada agente tem um objetivo e é capaz de criar seu próprio
plano e de executá-lo

Cada plano é enviado a um coordenador central

O coordenador:
– Sincroniza a execução de todos os sub-planos
– Encontra os conflitos
– Elimina os conflitos (arrumando as ações ou determinando os pontos de
sincronização)