Planejamento
(Cap. 11 do Russell)
Prof. Paulo Santos
Mestrado FEI
Aula baseada nos slides de Tom Lenaerts
(INRIA)
Planning





O problema de planejamento
Planejamento como busca em espaço de
estados
Planejamento de ordem parcial
Grafos de Planejamento
Planejamento em lógica proposicional
2
O problema de planejamento

Gerar sequências de ações para executar tarefas e atingir
objetivos.



Representação: states, actions and goals
Busca por soluções de problemas sobre um espaço de
planos.
Auxiliar em aplicações práticas, ex.:
design e produção
 operações militares
 jogos
 exploração espacial

3
O problema de planejamento


aumento de escala para problemas complexos
(comparando com os agentes busca e lógico vistos até
aqui)
Planejamento clássico:


ambientes completamente observáveis, determinísticos,
finitos, estáticos e discretos
(Planejamento não-clássico:

ambientes parcialmente observáveis ou estocásticos)
4
Questões centrais

Para um agente de planejamento utilizando métodos de
busca…
Quais ações são relevantes?
 Encontrar boas funções heurísticas?




Estimativa para o custo de um estado?
Heurística dependente ou independente do problema
como tirar proveito da decomposição do problema?

Suposição: a maioria dos problemas reais é quase-decomponível.
I.e., o planejador pode trabalhar em sub-objetivos
independentemente, mas talvez deva realizar algum trabalho
adicional para combinar os subplanos resultantes.
5
A linguagem de problemas de
planejamento

O que seria uma “boa” linguagem?




Suficientemente expressiva para descrever uma
grande variedade de problemas.
Restritiva o bastante para permitir que algoritmos
eficientes operem sobre ela.
Deve permitir a decomposição de problema em
subproblemas.
Linguagens:




STRIPS: Stanford Research Institute Problem Solver
ADL: Action Description Language
...
PDDL: Planning Domain Definition Language
6
Características gerais das linguagens

Representação de estados

Decompor o mundo em condições lógicas que
representam um estado como uma conjunção de literais
positivos



Hipótese de mundo fechado


literais proposicionais: Poor  Unknown
literais de 1a ordem (básicos -- grounded e livres de funções):
At(Plane1, Melbourne)  At(Plane2, Sydney)
(quaisquer condições não mencionadas em um estado são falsas)
Representação de objetivos (goals)
Estado parcialmente especificado, representado como
uma conjunção de literais básicos positivos
 Um estado proposicional s satisfaz a um objetivo g se s
contém todos os literais em g (e possivelmente outros).

7
Características gerais das linguagens

Representação de ações
Ação = Precondição + Efeito
Action(Fly(p,from, to),
PRECOND: At(p,from)  Plane(p)  Airport(from)  Airport(to)
EFFECT: ¬AT(p,from)  At(p,to))
= esquema de ação (p, from, to devem ser instanciadas)



Nome da ação e lista de parâmetros
PRECOND: Precondição (conj. de literais livres de função)


o que deve ser verdadeiro em um estado antes da
aplicação da ação
EFFECT : Efeito (conj. de literais livres de função que descrevem
como o estado se altera quando a ação é executada)


literais positivos devem ser considerados verdadeiros no
estado sucessor à ação; e negativos, falsos.
Add-list vs delete-list in Effect
8
Semântica da linguagem

Como as ações afetam os estados...


Uma ação é aplicável em todos os estados que
satisfazem as suas precondições.
Para esquemas de ações de primeira ordem, as
suas aplicabilidades envolvem uma substituição 
para as variáveis em PRECOND.
At(P1,JFK)  At(P2,SFO)  Plane(P1)  Plane(P2)  Airport(JFK)
 Airport(SFO)
Satisfazem : At(p,from)  Plane(p)  Airport(from)  Airport(to)
com  ={p/P1,from/JFK,to/SFO}
Portanto, a ação Action(Fly(p,from, to) é aplicável.
9
Semântica da linguagem

O resultado da execução da ação a em um estado s é o
estado s’, em que:

s’ é o mesmo que s exceto que


Qualquer literal positivo P no efeito de a é adicionado a s’
Qualquer literal negativo ¬P é removido de s’
At(P1,SFO)  At(P2,SFO)  Plane(P1)  Plane(P2)  Airport(JFK) 
Airport(SFO)

Hipótese de STRIPS:


todo literal não mencionado em efeito permanece inalterado
(evita o problema do quadro representacional)
10
Expressividade e extensões

STRIPS: tornar os alg. de planejamento mais simples e
eficientes
simplificação principal: literais livres de função
 permite a proposicionalização de qualquer esquema de
ação



STRIPS é insuficientemente expressiva para alguns
domínios reais:
Variante do STRIPS:Action Description language (ADL)
Action(Fly(p:Plane, from: Airport, to: Airport),
PRECOND: At(p,from)  (from  to)
EFFECT: ¬At(p,from)  At(p,to))
11
Expressividade e extensões

Vários formalismos de planejamento foram sistematizados em uma
linguagem padrão: Planning domain definition language (PDDL)


permitindo que diferentes sistemas permutem problemas
benchmark e comparem seus resultados;
Inclui sublinguagens correspondentes a STRIPS, ADL e às redes
hierárquicas
12
Ex: Transporte aéreo de cargas
Representação do problema de planejamento STRIPS:
Init(At(C1, SFO)  At(C2,JFK)  At(P1,SFO)  At(P2,JFK)  Cargo(C1)  Cargo(C2) 
Plane(P1)  Plane(P2)  Airport(JFK)  Airport(SFO))
Goal(At(C1,JFK)  At(C2,SFO))
Action(Load(c,p,a)
PRECOND: At(c,a) At(p,a) Cargo(c) Plane(p) Airport(a)
EFFECT: ¬At(c,a) In(c,p)
Action(Unload(c,p,a)
PRECOND: In(c,p) At(p,a) Cargo(c) Plane(p) Airport(a)
EFFECT: At(c,a)  ¬In(c,p)
Action(Fly(p,from,to)
PRECOND: At(p,from) Plane(p) Airport(from) Airport(to)
EFFECT: ¬ At(p,from)  At(p,to)
Possível plano:
[Load(C1,P1,SFO), Fly(P1,SFO,JFK), Load(C2,P2,JFK), Fly(P2,JFK,SFO)]
13
Ex: Pneu sobressalente
Representação do problema em ADL:
Este exemplo está alem do STRIPS: literal negativo na pre-condição
Init(At(Flat, Axle)  At(Spare,trunk))
Goal(At(Spare,Axle))
Action(Remove(Spare,Trunk)
PRECOND: At(Spare,Trunk)
EFFECT: ¬At(Spare,Trunk)  At(Spare,Ground))
Action(Remove(Flat,Axle)
PRECOND: At(Flat,Axle)
EFFECT: ¬At(Flat,Axle)  At(Flat,Ground))
Action(PutOn(Spare,Axle)
PRECOND: At(Spare,Ground) ¬At(Flat,Axle)
EFFECT: At(Spare,Axle)  ¬At(Spare,Ground))
Action(LeaveOvernight
PRECOND:
EFFECT: ¬ At(Spare,Ground)  ¬ At(Spare,Axle)  ¬ At(Spare,trunk)  ¬ At(Flat,Ground) 
¬ At(Flat,Axle) )
14
Ex: Mundo dos blocos
Init(On(A, Table)  On(B,Table)  On(C,Table)  Block(A)  Block(B)  Block(C)  Clear(A) 
Clear(B)  Clear(C))
Goal(On(A,B)  On(B,C))
Action(Move(b,x,y)
PRECOND: On(b,x)  Clear(b)  Clear(y)  Block(b)  (b x)  (b y)  (x y)
EFFECT: On(b,y)  Clear(x)  ¬ On(b,x)  ¬ Clear(y))
Action(MoveToTable(b,x)
PRECOND: On(b,x) Clear(b)  Block(b)  (b x)
EFFECT: On(b,Table)  Clear(x)  ¬ On(b,x))
Ações espúrias são possíveis: Move(B,C,C)
15
Planejamento como busca em
espaço de estados


São possíveis ambos: encadeamento para frente e para
trás
Planejamento por progressão
busca por encadeamento para frente
 Considerar os efeitos de TODAS as ações em um dado
estado


Planejamento por regressão
busca por encadeamento para trás
 Para atingir um objetivo, buscar o que deve ser verdadeiro
no estado anterior (e assim recursivamente).

16
Progressão e regressão
17
Algoritmo de progressão

Formulação como busca em um espaço de estados:

estado inicial = estado inicial do problema de
planejamento


Ações = aplicáveis se precondições são satisfeitas





Literais não presentes são falsos
Adicionar efeitos positivos, excluir (deletar) os negativos
Teste de objetivo = verifica se o estado satisfaz o objetivo
do problema de planejamento
custo do passo = cada ação custa 1
Sem símbolos funcionais … qualquer algoritmo
(completo) de busca é um algoritmo de planejamento
completo.
Ineficiente: (1) muitas ações irrelevantes são geradas (2) a
abordagem fracassa sem uma boa heurística.
18
Algoritmo de Regressão

Como determinar predecessores?

Quais são os estados a partir dos quais a aplicação de
uma dada ação leva ao objetivo?
Objetivo = At(C1, B)  At(C2, B)  …  At(C20, B)
Ação relevante para o primeiro literal: Unload(C1,p,B)
Funciona somente se as precondições forem satisfeitas. I.e. qqr estado
predecessor deve incluir estas precondições, no caso: At(C1, p) At(p, B)
Predecessor = In(C1, p)  At(p, B)  At(C2, B)  …  At(C20, B)
o subobjetivo At(C1,B) não deve estar presente neste estado.


Ações não devem desfazer literais desejados: ações
devem ser consistentes)
Vantagem principal: somente ações relevantes são
consideradas (fator de ramificação < que progressão).

Uma ação é relevante para um objetivo se ela alcança um
dos elementos da conjunção do objetivo.
19
Algoritmo de Regressão

Processo geral para a construção de predecessores


Dada uma descrição de objetivo G, seja A uma ação
relevante e consistente
O predecessor correspondente é descrito a seguir:




Quaisquer efeitos positivos de A que aparecem em G são
eliminados.
Cada literal de precondição de A é adicionado, a menos que já
apareça.
Qualquer dos algoritmos de busca pode ser usado para
executar a busca.
O término acontece quando é gerada uma descrição de
predecessor que é satisfeita pelo estado inicial do
problema de planejamento.

No caso de 1a ordem, a satisfação pode requerer uma
substituição de variáveis na descrição de predecessor.
20
Algoritmo de Regressão
A principal vantagem da busca por regressão é que ela nos
permite gerar somente ações relevantes.
 considere o problema de ter 20 itens no aeroporto B:
In(C1,B) ^ In(C2,B) ^ ... ^ In(C20,B)
 Regredir do objetivo até a ação
Descarregar(C1, p, B)

gera o primeiro elemento da conjunção, levando a um predecessor:
In(C1,p) ^ In(p,B) ^ ... ^ In(C20,B)

Este estado é satisfeito pelo estado inicial:
In(C1,P12) ^ In(P12, B) ^ In(C2,B) ^ ... ^ In(C20,B)

considerando-se a substituição {p/P12} e a ação
Descarregar(C1,P12,B)
21
Heuristicas para planejamento em
espaço de estados

Nenhum dos algoritmos de progressão ou regressão são
eficientes sem uma boa heurística
Quantas ações são necessária para atingir o objetivo?
 A solução completa é NP-difícil, deve-se encontrar uma
boa estimativa

22
Heuristicas para planejamento em
espaço de estados

Dois procedimentos para se encontrar uma heurística
admissível:

Encontrar a solução ótima para um problema relaxado.


Remover todas as precondições das ações
hipótese de independência de subobjetivo:
O custo de resolver uma conjunção de objetivos é aproximadamente
igual ao somatório dos custos de resolver cada subobjetivo
independentemente.
 Otimista: quando existem interações negativas entre os subplanos
correspondentes a cada subobjetivo (e.g. quando uma ação em um
subplano exclui um objetivo atingido por outro subplano)
 Pessimista (inadmissível): quando os subplanos contêm ações
redundantes
23
Planejamento de ordem parcial

Planejamento por progressão ou regressão no
espaço de estado são formas de busca de planos
totalmente ordenados.


Exploram sequências estritamente lineares de
ações conectadas de forma direta ao início ou ao
objetivo. Não podem tirar proveito da decomposição
do problema.
Sempre tomam decisões sobre como definir
sequências de ações sobre todos os subproblemas
24
Planejamento de ordem parcial


A idéia é desenvolver um algoritmo que
funcionasse independentemente sobre vários
subobjetivos, os resolvesse com subplanos e
depois combinasse os subplanos
Estratégia do compromisso mínimo (Least
commitment strategy):

retardar a escolha da ordem de aplicação de
algumas ações durante a busca.
25
Exemplo:
calçar um par de sapatos
Goal(RightShoeOn  LeftShoeOn)
Init()
Action(RightShoe, PRECOND: RightSockOn
EFFECT: RightShoeOn)
Action(RightSock, PRECOND:
EFFECT: RightSockOn)
Action(LeftShoe,
PRECOND: LeftSockOn
EFFECT: LeftShoeOn)
Action(LeftSock, PRECOND:
EFFECT: LeftSockOn)
Planejador: combinar duas sequências de ações
(1)leftsock, leftshoe (2)rightsock, rightshoe
26
Planejamento de ordem parcial

Qualquer algoritmo de planejamento que possa
inserir duas ações em um plano sem especificar
qual delas deve ser executada primeiro.
27
Planejamento de ordem parcial
28
POL : problema de busca

Estados são planos não terminados.


O plano vazio contém somente as ações início e fim.
Cada plano possui 4 componentes:
Um conjunto de ações (passos do plano)
 Um conjunto de restrições de ordenação: A < B



Cíclos representam contradições.
Um conjunto de vínculos causais (causal links)
p
A


B
 Um plano não pode ser estendido com a adição de uma nova ação
C que entra em conflito com o vínculo causal (se o efeito de C for
¬p e se C pode vir depois de A e antes de B)

Um conjunto de precondições abertas.

Precondição aberta: não é alcançada por alguma ação no plano. Os
planejadores
trabalharão para reduzir o número de precondições

abertas até o conjunto vazio (sem inserir contradições)
29
POL : problema de busca



Um plano é consistente sse não existirem ciclos nas
restrições de ordenação e nem conflitos com os vínculos
causais..
Um plano consistente sem precondições abertas é uma
solução.
Toda linearização de uma solução de ordem parcial é uma
solução de ordem total cuja execução a partir do estado
inicial alcançará um estado objetivo.
30
Resolvendo POL

Assumindo problemas de planejamento
proposicionais:


O plano inicial contém Start e Finish, a restrição de
ordenação Start < Finish, nenhum vínculo causal, e
todas as precondições em Finish abertas.
Função successor:
escolhe uma precondição aberta p em uma ação B e
 gera um plano sucessor para todo modo consistente
possível para escolher uma ação A que alcance p.


Teste de objetivo
31
Impondo consistência

Quando da geração de um plano sucessor:

O vínculo causal A--p->B e a restrição de ordenação
A < B é adicionada ao plano.



se A é novo, adicione também start < A
Resolver conflitos entre novos vínculos causais e
todas as ações existentes no plano
Resolver conflitos entre a ação A (se nova no plano)
e todos os vínculos existentes no plano.
32
Exemplo: problema do pneu
furado
Init(At(Flat, Axle)  At(Spare,trunk))
Goal(At(Spare,Axle))
Action(Remove(Spare,Trunk)
PRECOND: At(Spare,Trunk)
EFFECT: ¬At(Spare,Trunk)  At(Spare,Ground))
Action(Remove(Flat,Axle)
PRECOND: At(Flat,Axle)
EFFECT: ¬At(Flat,Axle)  At(Flat,Ground))
Action(PutOn(Spare,Axle)
PRECOND: At(Spare,Groundp) ¬At(Flat,Axle)
EFFECT: At(Spare,Axle)  ¬Ar(Spare,Ground))
Action(LeaveOvernight
PRECOND:
EFFECT: ¬ At(Spare,Ground)  ¬ At(Spare,Axle)  ¬ At(Spare,trunk)  ¬ At(Flat,Ground) 
¬ At(Flat,Axle) )
33
Pneu furado

Plano inicial: iniciar com os EFFECTS da ação Start e as
PRECOND da ação Finish.
34




Tomar uma precondição aberta: At(Spare, Axle)
Somente PutOn(Spare, Axle) é aplicável
At(Spare ,Axle)

Finish
Adicione vínculo causal: PutOn(Spare, Axle) 
Adicione restrição : PutOn(Spare, Axle) < Finish

35




Tomar outra precondição aberta: At(Spare, Ground)
Somente Remove(Spare, Trunk) é aplicável
Adicione o vínculo causal:
At ( Spare ,Ground )
Re move(Spare, Trunk) 

 PutOn(Spare, Axle)
Adicionar restrição : Remove(Spare, Trunk) < PutOn(Spare,Axle)
36





Tomar uma precondição aberta: At(Spare, Axle)
LeaveOverNight é aplicável
At(Spare ,Ground )
 PutOn(Spare, Axle)
conflito: Re move(Spare,Trunk) 
Para resolver, adicionar restrição :
LeaveOverNight < Remove(Spare, Trunk)

Adicionar vínculo causal:
,Ground )
LeaveOverNightAt(Spare



PutOn(Spare, Axle)
37




Tomar uma precondição aberta: At(Spare, Trunk)
Somente Start é aplicável
Adicionar vínculo:
Start At(Spare
,Trunk

 )Re move(Spare,Trunk)
Conflito: do vínculo com o efeito At(Spare,Trunk) de LeaveOverNight


Nenhum reordenamento é possível.
retroceder

38



Remover LeaveOverNight e vínculos causais
Adicionar agora Remove(Flat, Axle)
Termina o plano
39
Grafos de planejamento
(Para vosso divertimento)

Utilizados para produzir boas heurísticas


Soluções podem ser também obtidas por GRAPHPLAN.
Consistem de uma sequência de níveis correspondentes a
passos no plano .


Nível 0 é o estado inicial.
Cada nível consiste de um conjunto de literais e ações.


Literais = tudo o que poderia ser verdade naquele instante,
dependendo das ações executadas nos passos anteriores.
Ações = todas as ações que poderiam ter suas precondições
satisfeitas, dependendo dos literais verdadeiros naquele passo.
40
Exemplo: Bolo
Init(Have(Cake))
Goal(Have(Cake)  Eaten(Cake))
Action(Eat(Cake), PRECOND: Have(Cake)
EFFECT: ¬Have(Cake)  Eaten(Cake))
Action(Bake(Cake), PRECOND: ¬ Have(Cake)
EFFECT: Have(Cake))
41

Inicia no nível S0 e determina o próximo nível de ações A0 e o
próximo nível S1.
A0 >> todas as ações cujas precondições são satisfeitas nos
níveis anteriores.
 Conectar precondições e efeitos das ações S0 --> S1
 Inação é representada por “ações de persistência”.


Nível A0 contém as ações que podem ocorrer

Conflitos entre ações são representados por vínculos mutex (vínculos de
exclusão mútua).
42

Continuar até que dois níveis consecutivos sejam idênticos: nivelamenteo
43

Um vínvulo mutex ocorre quando duas ações:

efeitos inconsistentes: uma ação nega os efeitos de uma outra.
Interferência: um dos efeitos de uma ação é a negação de uma precondição de uma

Necessidades concorrentes: uma das precondições de uma ação é mutuamente


outra ação.
excludente com uma das precondições de outra ação.
Um vínculo mutex ocorre entre dois literais se (inconsistent support):


um é a negação do outro OU
Se cada par possível de ações que alcançariam os dois literais são mutuamente
exclusivas
44
Grafos de planejamento e
heurísticas

GP’s fornecem informações sobre o problema

Um literal que não aparece no último nível do grafo não
pode ser alcançado por qualquer plano.



Um literal inatingível tem custo h(n) = infinito.
O nível em que todos os literais do objetivo aparecem
O grafo pode ser utilizado como um problema relaxado.
45
The GRAPHPLAN Algorithm

Como extrair soluções diretamente do grafo
function GRAPHPLAN(problem) return solution or failure
graph  INITIAL-PLANNING-GRAPH(problem)
goals  GOALS[problem]
loop do
if goals all non-mutex in last level of graph then do
solution  EXTRACT-SOLUTION(graph, goals, LENGTH(graph))
if solution  failure then return solution
else if NO-SOLUTION-POSSIBLE(graph) then return failure
graph  EXPAND-GRAPH(graph, problem)
46
GRAPHPLAN example





Inicialmente o plano consiste dos 5 literais do estado inicial e da hipótese
de mundo fechado (S0).
Adicionar ações cujas precondições são satisfeitas por EXPAND-GRAPH
(A0)
adicionar ações de persistência e vínculos mutex.
Adicionar os efeitos no nível S1
Repetir até que o objetivo esteja no nível Si
47
GRAPHPLAN example

Em S2, os literais do objetivo existem e não são mutex com nenhum outro


Uma solução pode existir e EXTRACT-SOLUTION tentará encontra-la
Processo de busca de caminho em um grafo.
48