Planejamento Baseado em
Lógica
André Novaes
CIn - UFPE
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
1
Roteiro
• Lógica e Planejamento
– STRIPS
– Cálculo de Situações
– Cálculo de Eventos
•
•
•
•
•
Abdução + Calculo de Eventos
Planejamento como Satisfação
Resolução de Restrições
Atualização de BD Dedutivo
Comparações
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
2
Lógica e Planejamento
• Codificar problema em alguma lógica
• Aplicar um provador de teoremas
– Extrair plano a partir das provas
• Vantagens
– Semântica declarativa
– Complexidade já determinada
– Reuso de técnicas de implementações de provadores de
teorema e compiladores de programas em lógica
• Desvantagem
– Mais lento?
• Como representar tempo, estados e ações?
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
3
Exemplo de Problema
B
A
C
A
B
C
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
4
STRIPS
• STanford Research Institute Problem Solver
• Linguagem Restrita
– Específica para planejamento
– Hipótese do mundo fechado
• Algoritmo Específico para linguagem
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
5
STRIPS
• Estados e Objetivo
– conjunção de literais sem variáveis e funções
– sobre(A,B) 
• Ação
– ação + precondições + efeitos
– Exemplo:
mover(Bloco,De,Para)
Precondicoes:
Limpo(Para)
Efeitos:
 Limpo(Bloco)  Sobre(Bloco,De)
sobre(Bloco,De)
 sobre(Bloco,Para)
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
6
Calculo de Situações
• Linguagem de Propósito Geral
– lógica da primeira ordem
– hipótese do mundo aberto
• Representação baseada em situações e ações
• do(A,S)
–
–
–
–
–
–
A: ação
S: estado anterior
do(A,S): novo estado
função parcial
predicado independente do domínio
permite implementar raciocínio monotónico reusando
máquinas de inferência monotónicas
– reifica fórmulas da lógica ao nível meta como termos lógicos
• Máquina de inferência: provador de teorema da lógica da
1a ordem
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
7
Calculo de Situações
Estado Inicial:
Sobre(B,A,S0)  Sobre(C,Mesa,S0) 
Limpo(B,S0)  Limpo(C,S0)
Descrição Geral:
Limpo(y,s)  Sobre(x,y,s)  (y=Mesa)
Efeitos:
Sobre(x,z,do(move(x,y,z),s)) 
 (x=z)  Limpo(z,s)  Limpo(x,s)  Sobre(x,y,s)
Frame Problem:
Limpo(u,do(move(x,y,z),s)) 
(u=z), limpo(u,s)
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
8
Calculo de Situações
• Estado Final + Axiomas + Estado Inicial 
Objetivo
• Tenta Provar Objetivo
– Sobre(A,C,s)  Limpo(A,s)  Limpo(B,s) 
Sobre(B,Mesa,s)  Sobre(C,Mesa,s)
• Estado obtido representa ações
– do(mover(A,Mesa,C),
do(mover(B,A,Mesa),s0))
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
9
Calculo de Situações
• Lado Negativo
– Problema do Frame
• Representação Explicita
– Expressividade limitada
• Sem representação de intervalos de tempo
• Sem ações concorrentes
• Lado Positivo
– Lógica madura
– Vários provadores de teorema
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
10
Calculo de Eventos
• Linguagem de Propósito Geral
– Lógica de Horn da primeira ordem
– Mundo Fechado
– Duas classes de cláusulas:
• As independentes do dóminio axiomatizando
raciocínio monotónico em cima de raciocínio
monotónico
• As particulares a cada domínio
– Ambas reificam fórmulas da lógica ao nível meta como
termos lógicos
• Representação explicita do Tempo
• Máquina de Inferência subjacente: Prolog
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
11
Calculo de Eventos
• Mudanças modeladas como eventos
– Happens(E,T)
– Evento E acontece no tempo T
• Estados modelados usando Fluentes e
proposições estáticas
– HoldsAt(F,T)
– F é verdade no tempo T
– E declarado como fato lógico é sempre verdade
• Estado Inicial
– Initially(F)
– Inicialmente F é verdade
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
12
Calculo de Eventos
• Conseqüências e Condições da ação
– Initiates(F,F,T)  Condições
• Evento E Torna F verdadeiro no tempo T
– Terminates(E,F,T)  Condições
• Evento E Torna F falso no tempo T
– Condições: conjunção de literais
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
13
Calculo de Eventos
• Axiomas independentes do domínio:
– Resolvem Problema do Frame
HoldsAt(f,t)  Initially(f)   Clipped(0,f,t)
HoldsAt(f,t2) 
Happens(a,t1)  t1< t2 
Initiates(a,f,t1)   Clipped(t1,f,t2)
Clipped(t1,f,t2) 
Happens(a,t)  Terminates(a,f,t)  t1<t  t<t2
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
14
Calculo de Eventos
Axiomas específicas do mundo do blocos
Estado Inicial:
Sobre(B,A,0)  Sobre(C,Mesa,0) 
Limpo(B,0)  Limpo(C,0)
Regras:
Initiates(mover(x,y,z),sobre(x,z),t) 
HoldsAt(Limpo(z),t)  HoldsAt(Limpo(x),t) 
HoldsAt(Sobre(x,y),t)  (x=z)
Terminates(mover(x,y,z),sobre(x,y),t) 
HoldsAt(Limpo(z),t)  HoldsAt(Limpo(x),t) 
HoldsAt(Sobre(x,y),t)  (x=z)
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
15
POP x Cálculo de Eventos
Descrição do Estado
Um conjunto de fluentes (f1,...,fn)
Mudanças no Estado
Ação a descrita por predicados:
Initiates(a,f,t) :- 
Terminates(a,f,t) :- 
Releases(a,f,t) :- 
Estado Inicial
Initially(f)
Elementos do Plano
Happens(a,t) ordenados por
before(t1,t2)
Causal-links / protected intervals
Clipped e declipped negados
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
16
Roteiro
• Lógica e Planejamento
– STRIPS
– Cálculo de Situações
– Cálculo de Eventos
•
•
•
•
•
Abdução + Calculo de Eventos
Planejamento como Satisfação
Resolução de Restrições
Atualização de BD Dedutivo
Comparações
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
17
Calculo de Eventos
• (Initiates + Terminates)  Ações  Estado Inicial
 Axiomas  Objetivo
• Ações: Happens(a,t)
• Solução por Abdução:
- Dado:
- Conclusão: objetivo a atingir
- Premissas conhecidas: Estado Inicial, Descrição do
Domínio (Initiates e Terminates), e Axiomas Gerais
do Cálculo
- Abduzir:
- Premissa desconhecida: ações a efetuar (i.e., plano)
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
18
Abdução
• Premissas Conhecidas + Premissas
Desconhecidas  Conclusão
• Inverso da dedução: tenta descobrir causa a
partir do efeito
• Sobre(A,B)  Limpo(C)  ?  Sobre(A,C)
• ? = Limpo(A)
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
19
Abdução + Calculo de Eventos
• Efeitos das Ações  Ações  Axiomas  Estado
Inicial  Objetivo
– tenta abduzir ações
– happens, before
• Exemplo: Meta-Interpretador Prolog
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
20
Meta-Interpretador
Demo([]).
Demo([G|GS]) :axiom(G,Gs2),
append(Gs2,Gs1,Gs3),
demo(Gs3).
Demo([not(G)|Gs]) :not demo([G]),
demo(Gs).
Onde:
Axiom(H,[B1,...,Bn]) se H :- B1,...,Bn
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
21
Meta-Interpretador
holds_at(F,T3) :
happens(A,T1,T2), T2 < T3, initiates(A,F,T1),
not clipped(T1,F,T2).
demo([holds_at(F,T3)|Gs1]) :
axiom(initiates(A,F,T1),Gs2),
axiom(happens(A,T1,T2),Gs3),
axiom(before(T2,T3),[]),
demo([not clipped(T1,F,T3)]),
append(Gs3,Gs2,Gs4),
append(Gs4,Gs1,Gs5),
demo(Gs5).
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
22
Meta-Interpretador
• Transformando em Meta-Interpretador para abdução
– Resíduo Inicial
– Resíduo Final
– Literais Negados
abdemo([],R,R,N).
abdemo([G|Gs],R1,R3,N) :
abducible(G), abdemo_nafs(N,[G|R1],R2), abdemo(Gs,R2,R3,N).
abdemo([G|Gs1],R1,R2,N) :
axiom(G,Gs2), append(Gs2,Gs1,Gs3), abdemo(Gs3,R1,R2,N).
abdemo([not(G)|Gs],R1,R3,N) :
abdemo_naf([G],R1,R2), abdemo(Gs,R2,R3,[[G]|N]).
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
23
Meta-Interpretador
• abdemo_nafs:
–
–
–
–
para cada item N da lista de negados
provar que N  Resíduo  Fatos é verdade
N é uma lista [p0,...,pn] onde N :- p0,...,pn
É necessário provar apenas que um pi é verdadeiro
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
24
Meta-Interpretador
holds_at(F,T3) :
happens(A,T1,T2), T2 < T3, initiates(A,F,T1),
not clipped(T1,F,T2).
abdemo([holds_at(F,T3)|Gs1],R1,R4,N) :
axiom(initiates(A,F,T1),Gs2), escolhendo uma açao
abdemo_nafs(N,[happens(A,T1,T2),before(T2,T3)|R1],R2), adicionando
ação ao plano
abdemo_nafs([clipped(T1,F,T3)],R2,R3), protected link
append(Gs2,Gs1,Gs3),
demo(Gs3,R3,R4,[clipped(T1,F,T3)|N]).
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
25
Meta-Interpretador
• Ordenando ações
– para provar holdsAt
– holdsAt(F,T3) : happens(A,T1,T2), T2 < T3, initiates(A,F,T1), not
clipped(T1,F,T2).
– Para provar clipped
– clipped(t1,f,t2) :- happens(a,t) and terminates(a,f,t) and
before(t1,t) and before(t,t2)
– indiretamente, provar que before(t1,t2) é falso
– Solução: adicionar before(t2,t1) ao resíduo, checando se no
há inconsistência
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
26
Meta-Interpretador
• Unsoundness
– fluent range restricted
terminates(sell,have(X),T) :
holdsAt(have(X),T),
buys(Y,X),
holdsAt(at(Y),T).
– em algum exemplos de state constraints
holds_at(happy,T) : holds_at(rich,T)
initiates(rob_bank,rich,T).
initially(neg(rich)).
initially(neg(happy)).
• Incompleteness
– informação incompleta do estado inicial
initiates(vaccinate1,immune,T) : holds_at(type1,T).
initiates(vaccinate2,immune,T) : holds_at(neg(type1),T).
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
27
Roteiro
• Lógica e Planejamento
– STRIPS
– Cálculo de Situações
– Cálculo de Eventos
•
•
•
•
•
Abdução + Calculo de Eventos
Planejamento como Satisfação
Resolução de Restrições
Atualização de BD Dedutivo
Comparações
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
28
Planejamento como Satisfação
•
•
•
•
Codificar o plano como fórmula proposicional
Determinar se a fórmula pode ser satisfeita
Plano extraído da prova da fórmula
Assume-se que o plano tem n passos
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
29
Planejamento como Satisfação
• Transformar problema de planejamento em
problema de satisfação
• Definir tamanho máximo do plano
• Se necessário, incluir ações dummy
• Converter predicados para refletir tempo
– p(a1,...,an)  p(a1,...,an,an+1)
– an+1representa o tempo
• Fórmula a ser satisfeita inclui:
– estado inicial, objetivo, efeitos das ações
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
30
Planejamento como Satisfação
• Estado Inicial:
– Sobre(B,A,1)  Sobre(C,Mesa,1)  Limpo(B,1) 
Limpo(C,1)
• Efeitos:
– Sobre(x,z,do(move(x,y,z),s))   (x=z)  Limpo(z,s) 
Limpo(x,s)  Sobre(x,y,s)
– Instanciar para cada caso
– (Sobre(a,mesa,do(move(a,b,mesa),2))   (a=mesa) 
Limpo(mesa,2)  Limpo(a,2)  Sobre(a,b,2)) 
(Sobre(b,mesa,do(move(b,a,mesa),2))   (b=mesa) 
Limpo(mesa,2)  Limpo(b,2)  Sobre(b,a,2))  ...
• Apenas uma ação em cada passo
–  Mover_a_b_mesa,2)   Mover(b,a,mesa,2)
• Pelo menos uma ação em cada passo
– Mover(a,b,mesa,2)  Mover(b,a,mesa,2) ...
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
31
Planejamento como Satisfação
•
•
 é a fórmula inicial
– CNF: (ab)(cd)
 é o plano
Satisfacao(,)
enquanto  ( = )
escolher um literal P tal que P ou P ocorra em 
enquanto existir um {L} em  (L é uma cláusula com um literal)
 <-  união {L}
para cada cláusula C em 
se L  C então
 <-  \ {C}
se L  C então
  ( \ {C})  (C \ {L})
end
end
end
exit with 
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
32
Planejamento como Satisfação
Fórmula Inicial
D  (D  A   B)  (D  A  B) 
(D  A  B)  (D  A  B)
Após eliminar D
 = (A   B)(AB)(AB) ,  = {D}
Após escolher A
 = BB , o que é uma contradição
Escolhemos  A
 =  B ,  = {D,  A}
Escolhendo  B
 =  ,  = {D,  A,  B}
Plano satisfeito
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
33
Roteiro
• Lógica e Planejamento
– STRIPS
– Cálculo de Situações
– Cálculo de Eventos
•
•
•
•
•
Abdução + Calculo de Eventos
Planejamento como Satisfação
Resolução de Restrições
Atualização de BD Dedutivo
Comparações
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
34
Constraint Logic Programming
• Estado é definido por variáveis Xi com valores
num domínio Di
• Restrições são definidas sobre os valores das
variáveis
• Uso de algoritmos e heurísticas de propósito
geral
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
35
parcPLAN
• Utiliza algoritmo em vários passos
– passo 1: inclusão de ações
– passo 2: resolução de restrições
– Passo 3: finalização do plano
• Ações podem ter um intervalo
• utiliza "least commitment"
• Ações definidas pôr
– condições, efeitos e restrições
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
36
parcPLAN
• Exemplo:
Acao:
move(Bloco,De,Para,Inicio,Fim)
Condição:
clear(To,T2,Fim),
clear(Bloco,T3,T4),
on(Bloco,De,T1,Inicio)
Efeitos
on(Bloco,Para, Fim,T5)
clear(De,T6,T7)
Restrições
Bloco!=De, Bloco!=Para
T6 = Inicio + 2, T2 < Fim - 2,
T3< Inicio, Fim < T4, Inicio + 5 <= Fim
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
37
parcPLAN
Plano
Problema
Action Introduction
Falha
Scheduling/
Resource Reasoning
Collapsing
Falha
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
38
parcPLAN
• Introduzir Ação
–
–
–
–
–
–
escolher um objetivo
escolher ação que tenha como efeito o objetivo
unificar com efeito
adicionar condições da ação ao objetivo
adicionar restrições
calcular custo
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
39
parcPLAN
• Segunda Parte
– Quando todos os objetivos podem ser unificados com a
base
– utilizar resolução de restrições
– cada objetivo é associado a um "finite domain variable"
– objetivos mais restritos são instanciados primeiro
• Se falhar
– Tentar achar nova ação
– Que seja mais geral
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
40
parcPLAN
• Terceira Parte
– finalizar plano
– restrições de tempo e recursos restantes
• Se falhar
– tentar novo colapso
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
41
Roteiro
• Lógica e Planejamento
– STRIPS
– Cálculo de Situações
– Cálculo de Eventos
•
•
•
•
•
Abdução + Calculo de Eventos
Planejamento como Satisfação
Resolução de Restrições
Atualização de BD Dedutivo
Comparações
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
42
Transaction Logic
• Permite atualização na base de fatos
• Transações Atômicas
– Atualização da base é desfeita em caso de erro
• P.ins, P.del
– P é um predicado
– Ex: sobre(A,B).del
• T1  T2
– Conjunção serial de transações
– T2 é executada após T1, na mesma transação
– Ex: Mover(B,A,Mesa)  Mover(A,Mesa,C)
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
43
Transaction Logic
• STRIPS
Ação
mover(Bloco,De,Para)
Precondições:
Limpo(Para)  Limpo(Bloco)  Sobre(Bloco,De)
Efeitos:
sobre(Bloco,De)  sobre(Bloco,Para)
• Transaction Logic
mover(Bloco,De,Para) 
Limpo(Para)  Limpo(Bloco)  Sobre(Bloco,De) 
sobre(Bloco,De).del  Sobre(Bloco,Para).ins
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
44
Transaction Logic
conseguir_mover(X,Y,Z) 
[conseguir_limpar(X) & conseguir_limpar(Z) &
conseguir_sobre(X,Y)]  mover(X,Y,Z)
conseguir_mover(X,Y,Z)  sobre(X,Z)  limpo(Y)
conseguir_limpar(X)  limpo(X)
conseguir_limpar(X)  conseguir_mover(Y,X,Z)
conseguir_sobre(X,Y)  sobre(X,Y)
conseguir_sobre(X,Y)  conseguir_mover(X,Z,Y)
?- [conseguir_sobre(a,c) & conseguir_limpo(b) &
conseguir_ limpo(a)] 
sobre(a,c)  limpo(b)  limpo(a)
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
45
Roteiro
• Lógica e Planejamento
– STRIPS
– Cálculo de Situações
– Cálculo de Eventos
•
•
•
•
•
Abdução + Calculo de Eventos
Planejamento como Satisfação
Resolução de Restrições
Atualização de BD Dedutivo
Comparações
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
46
Comparação
Linguagem
Algoritmo
Tempo
STRIPS
Específica
Especializado para
planejamento
Implícito
Cálculo de Situações
Geral - lógica da 1 1a
ordem
Provador de Teorema
Geral
Implícito
Cálculo de Eventos
Geral - lógica de horn
da 1a ordem
Máquina de inferência
para Abductive Logic
Programming
Explícito
Satisfação
Lógica proposicional
Satisfação de
Fórmula Lógica
Explícito
parcPLAN
Específica
Especifico para
planejamento
reusando máquina de
inferência para CLP
Explícito
Transaction Logic
Geral
Máquina de inferência
para Transaction
Logic Programming
Explícito
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
47
2a tabela de comparação
• linhas: abordagens
• colunas: features de PDDL suportados
• Hierarquia de expressividade N dimensionais a
partir de STRIPS até extensão de ADL
Planejamento Baseado em Lógica – André Novaes – CIn UFPE
48