Planejamento
Viviane Torres da Silva
[email protected]
http://www.ic.uff.br/~viviane.silva/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:
– Ex: Infeliz ^ Triste estado de uma pessoa
– Ex: Acima(B,A)
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), Livre(B), Livre(A)

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,A) ^ Livre(B) ^ Livre(Mesa)
– Pós-condições: ¬Acima(B,A) ^ Acima(B,Mesa) ^ ¬ Livre(Mesa)
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
Exemplo
Estado inicial: e1
 Estado objetivo (final): e10
 Conjunto de ações disponíveis: {a1, a2, a3, b1, b2, ...}

a1
e1
e2
estado final
ação
estado inicial
a2
e2
f1
a3
f1
b1
f2
estado inicial
a1
b1
b2
a4
e1
e2
e2
e3
……..
a2
b2
e4
a4
e4
e5
…
e9
b10
e10
estado final
e10
b10
e9
e3
f1 a
3
e8
e4
f
…2
e7
e5
e3
e6
Plano: {a1, b1, b2, a4, …, b10}
Ambiente precisa ter as seguintes características...

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,A) ^ Acima(B,C) ^ Livre(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,A) ^ Acima(B,Mesa) ^ Livre(A)
Algoritmos de Planejamento
Busca para frente
 Busca para trás

Estado inicial: Acima(B,A)
Acima(A,Mesa)
Acima(C,Mesa)
Acima(D,Mesa)
Livre(B)
Livre(C)
Livre(D)
Objetivo: Acima(C,A)
Acima(D,B)
Acima(A,Mesa)
Acima(B,Mesa)
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
Acima(B,A)
Acima(A,Mesa)
Acima(C,Mesa)
Acima(D,Mesa)
Livre(B)
Livre(C)
Livre(D)
Acima(A,Mesa)
Acima(D,Mesa)
Livre(B)
Livre(C)
Livre(D)
Acima(B,Mesa)
Acima(C,A)
C
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)
Mover(D,Mesa,B)
Acima(A,Mesa)
Acima(C,Mesa)
Acima(D,Mesa)
Livre(B)
Livre(C)
Livre(D)
Acima(B,Mesa)
Livre(A)
Acima(A,Mesa)
Livre(C)
Livre(D)
Acima(B,Mesa)
Acima(C,A)
Acima(D,B)
Mover(C,Mesa,A)
Mover(C,Mesa,B)
Mover(C,Mesa,D)
…
Mover(D,Mesa,A)
Mover(D,Mesa,C)
Mover(C,Mesa,A)
Mover(D,Mesa,B)
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(A,Mesa)
Acima(B,Mesa)
Acima(C,A)
Acima(D,B)
Livre(C)
Livre(D)
Acima(A,Mesa)
Acima(B,Mesa)
Livre(C)
Livre(D)
Acima(D,Mesa)
Livre(B)
Acima(C,Mesa)
Livre(A)
Move(D,Mesa,B)
Move(D,C,B)
Move(D,Mesa,B)
Move(C,Mesa,A)
Move(C,D,A)
MoveParaMesa(B,A)
B
Acima(A,Mesa)
Acima(B,Mesa)
Acima(C,A)
Livre(C)
Livre(D)
Acima(D,Mesa)
Livre(B)
Acima(A,Mesa)
Livre(C)
Livre(D)
Acima(D,Mesa)
Livre(B)
Acima(C,Mesa)
Acima(B,A)
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)
B
A
C
D
Ordenação parcial dos planos

Trabalhar com uma abordagem que considere que existem
vários sub-objetivos independentes

Cada sub-objetivo será tratado por um sub-plano
Combinar os sub-planos para alcançar o objetivo



É possível escolher os sub-objetivos mais importantes para
começar
Ex.: Planejar uma viagem de avião de casa no Rio ao hotel
em 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
Estado inicial: e1,
estado objetivo (final): e10
 Conjunto de ações disponíveis: {a1, a2, a3, b1, b2, ...}

a1


e1
e2
a2
e2
f1
a3
f1
f2
b1
e2
e3
b2
e3
e4
a4
e4
…
e5
e9
b10
e10
a1
b1
Plano final: {a1, b1, b2, a4, …, b10}
Sub-estados: {e2, e3, e4, …, e9}
b2
a4
e2
e10
b10
e9
e3
e8
e4
e7
e5
e2 = sub-estado inicial
b1
b2 e3 sub-plano1={b1, b2, a4}
e4
a4
e5 = sub-estado objetivo
……..
e1
a1
sub-plano1
e1
……..
e2
e5
a5
e10
e6
sub-plano2
a5
Plano final: {a1, sub-plano1, a5, sub-plano2}
e6
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)