Raciocínio Abdutivo usando Cálculo
de Eventos e sua correspondência
com Sistemas de Planejamento
Exame de Qualificação
Silvio do Lago Pereira
Introdução
•
•
•
•
•
Planejamento
Sistemas corretos versus práticos
Raciocínio e representação
O artigo de Green
O artigo de Shanahan
2
Objetivo
• Mostrar que
Sistemas de
planejamento
lógicos

Sistemas de
planejamento
algorítmicos
3
Suposições
• Sobre o mundo:




tempo atômico
efeitos determinísticos
onisciência
causa de mudança única
• Sobre o agente:




representa e mantém o estado do mundo
representa ações e os efeitos produzidos por elas
delibera sobre a construção de um plano de ações
raciocina sobre interação de ações e metas
4
Organização
•
•
•
•
Representação de conhecimento
Planejamento clássico
Planejamento abdutivo
Metodologia
5
Representação de Conhecimento
Cálculo de Situações
Representação STRIPS
Cálculo de Eventos
Cálculo de Situações
S0

Do(,S0)
n+1, ...,
Axiomas de efeito
1, ..., n
)
Holds(n+1
,Do(,S
i,S0
0))
n+j
1 , ..., i -1,
i+k, ..., n
Axiomas de quadro
7
Mundo dos Blocos
• Situações: S0 e S1
• Fluentes: Sobre(x,y) e Livre(x)
• Ação: Move(x,y)
8
O problema do Quadro
• Novo fluente: Cor(x,c)
• Nova ação: Pinta(x,c)
• Num domínio com m ações e n fluentes,
temos O(mn) axiomas de quadro
9
Circunscrição
• Lei do senso comum da inércia
• A conjectura de McCarthy
• A idéia básica da circunscrição
• CIRC[;] def   q[(q)  q]
• Raciocínio não-monotônico
10
Exemplo
• Seja  := Livre(B)  Livre(C)  Sobre(C,A).
• Por exemplo, temos  |= Livre(B), mas não
temos  |=Livre(A), nem  |= Livre(A).
• Temos CIRC[;Livre] |= Livre(A).
• De modo geral, temos CIRC[;Livre] |=
x[Livre(x)  (xB  xC)].
11
Representação STRIPS
• Evita os axiomas de quadro
• Baseado em estados do mundo
• Ações são representadas por operadores
OPERADOR(Move(C, A, M),
PRECONDS: {Sobre(C,A), Livre(C)},
EFEITOS: {Sobre(C,M), Sobre(C,A), Livre(A)})
12
Semântica
Seja  uma ação e  um estado do mundo:
•  é aplicável a  sse PRECONDS()
• O estado resultante da aplicação  a  é
  EFEITOS()  EFEITOS()
13
Representação ADL
• É uma extensão da representação STRIPS
OPERADOR(Move(x, y, z),
PRECONDS: {Pasta(x), Em(x,y) , xz},
EFEITOS: {Em(x,z), Em(x,y),
v(Objeto(v) 
(Dentro(v,x) 
(Em(v,z)  Em(v,y)) ))} )
14
Cálculo de Eventos
• Ontologia: eventos, intervalos de tempo e fluentes
• Linguagem:

Initiates(,,), Terminates(,,) e Releases(,,)

InitiallyP() e InitiallyN()

Happens(,1,2)

HoldsAt(,)

Clipped(1,,2) e Declipped(1,,2)
15
Axiomas EC
(EC1) HoldsAt(f,t) 
InitiallyP(f) 
Clipped(0,f,t)
(EC2) HoldsAt(f,t) 
Happens(a,t1,t2) 
Initiates(a,f,t1) 
t2t 
Clipped(t1,f,t)
16
(EC3) HoldsAt(f,t) 
InitiallyN(f) 
Declipped(0,f,t)
(EC4) HoldsAt(f,t) 
Happens(a,t1,t2) 
Terminates(a,f,t1) 
t2t 
Declipped(t1,f,t)
17
(EC5) Clipped(t1,f,t2) 
a, t3, t4 [ Happens(a,t3,t4) 
t1t3 
t4t2 
(Terminates(a,f,t3)  Releases(a,f,t3))]
(EC6) Declipped(t1,f,t2) 
a, t3, t4 [ Happens(a,t3,t4) 
t1t3 
t4t2 
(Initiates(a,f,t3)  Releases(a,f,t3))]
(EC7) Happens(a,t1,t2)  t1 t2
18
Planejamento Clássico
Busca no espaço de estados
Busca no espaço de planos
Representação de Conhecimento e
paradigmas de busca
Algoritmos de planejamento
Busca no Espaço de Estados


20
Planejamento Progressivo
Algoritmo PROG(, , , )
Entrada: A descrição das ações .
A descrição do estado corrente .
A descrição de um estado meta .
Um plano parcialmente especificado .
Saída: FALHA ou um plano completo .
1. Se  então devolva .
2. Seja A := { |    PRECONDS() }.
3. Escolha   A.
3.1. Seja  := PROG(, +EFEITOS+()EFEITOS(), ,  ).
3.2. Se   FALHA então devolva .
3.3. Retroceda.
4. Devolva FALHA.
21
Planejamento Regressivo
Algoritmo REGR(, , , )
Entrada: A descrição das ações .
A descrição do estado inicial .
A descrição do estado corrente .
Um plano parcialmente especificado .
Saída: FALHA ou um plano completo .
1. Se  então devolva .
2. Seja A := { |    EFEITOS()  EFEITOS()}.
3. Escolha   A.
3.1. Seja  := REGR(, , +PRE()+EFEITOS()EFEITOS+(), ).
3.2. Se   FALHA então devolva .
3.3. Retroceda.
4. Devolva FALHA.
22
Busca no Espaço de Planos
• O espaço de planos como um grafo

nós: planos parcialmente especificados

arestas: operações de refinamento do plano
• Ordem das ações no plano

total

parcial
23
Planejamento de Ordem Total
Planejamento de
ordem total
como busca no
espaço de
planos

Planejamento
regressivo como
busca no espaço
de estados
24
Planejamento de Ordem Parcial
Plano Vazio
Vínculo
Ameaça
Causal
A0
p
p


t
c
c
A

25
Representação de Conhecimento
e Paradigmas de Busca
• Cálculo de Situações 
Planejamento de ordem total
como busca no espaço de estados
• Cálculo de Eventos 
Planejamento de ordem parcial
como busca no espaço de planos
26
Algoritmos de Planejamento
• UCPOP - suporta a representação ADL
• SNLP - planejamento sistemático
• HTN - decomposição hierárquica
27
Planejamento Abdutivo
Abdução
Planejamento Abdutivo com EC
Meta-interpretador Abdutivo para EC
Abdução
Sejam  a descrição de um domínio e 0 a
descrição de uma observação.
Abdução consiste em encontrar um conjunto de
sentenças , explicação abdutiva de 0, tal que

 é consistente

 |= 0
29
SLDA-Refutação
Sejam  um conjunto de cláusulas definidas e 0 uma
cláusula objetivo. Uma SLDA-refutação é uma seqüência
0,0, , n,n
onde cada i+1,i+1 é obtido a partir de i,i.
Seja  o literal selecionado de i:


se  é abdutível, i+1 := i e i+1 := i{}
senão, a resolução é efetuada e i+1 := i
30
Exemplo
(1) grama-molhada  choveu
(2) grama-molhada  irrigada
(3) sapatos-molhados  grama-molhada
(4)  sapatos-molhados , { }
(5)  grama-molhada , { }
(6)  choveu , { }
(7)  irrigada , { }
(8)  , { irrigada }



0
R(4,3)
R(5,1)
R(5,2)
A(7)
31
SLDNFA-Refutação
• Negação e a hipótese do mundo fechado
• Pode-se inferir  de um programa lógico 
se não existe uma SLD-refutação para  a
partir de 
• Interferências entre negação e abdução
32
Planejamento Abdutivo com
Cálculo de Eventos
• Domínio : Initiates, Terminates e Releases
• Situação inicial : InitiallyN e InitiallyP
• Meta : ()HoldsAt
• Plano : Happens e <
• Planejamento:
CIRC[; Initiates,Terminates,Releases] 
CIRC[;Happens]  EC   |= 
33
Meta-interpretador Abdutivo
para Cálculo de Eventos
(1) demo([]).
(2) demo([G|Gs1]) :axiom(G,Gs2),
append(Gs2,Gs1,Gs3),
demo(Gs3).
(3) demo([not(G)|Gs]) :not demo(G),
demo(Gs).
34
Meta-interpretador Abdutivo
(1) abdemo([],R,R).
(2) abdemo([G|Gs],R1,R2) :abducible(G),
abdemo(Gs,[G|R1],R2).
(3) abdemo([G|Gs1],R1,R2) :axiom(G,Gs2),
append(Gs2,Gs1,Gs3),
abdemo(Gs3,R1,R2).
35
Estendendo Abdução com
Negação por Falha
(1) abdemo([],R,R,N,N).
(2) abdemo([G|Gs],R1,R3,N1,N2) :abducible(G),
abdemo_nafs(N1,[G|R1],R2),
abdemo(Gs,R2,R3,N1,N2).
(3) abdemo([G|Gs1],R1,R2,N1,N2) :axiom(G,Gs2),
append(Gs2,Gs1,Gs3),
abdemo(Gs3,R1,R2,N1,N2).
(4) abdemo([not(G)|Gs],R1,R2,N1,N2) :abdemo_naf([G],R1,R2),
abdemo(Gs,R2,R3,[[G]|N1],N2).
36
(5) abdemo_nafs([],R,R).
(6) abdemo_nafs([N|Ns],R1,R3) :abdemo_naf(N,R1,R2),
abdemo_nafs(Ns,R2,R3).
(7) abdemo_naf([G|Gs1],R,R) :not resolve(G,R,Gs2).
(8) abdemo_naf([G1|Gs1],R1,R2) :findall(Gs2,(resolve(G1,R1,Gs3),
append(Gs3,Gs1,Gs2)),Gss),
abdemo_nafs(Gss,R1,R2).
( 9) resolve(G,R,[]) :- member(G,R).
(10) resolve(G,R,Gs) :- axiom(G,Gs).
37
Compilação de Axiomas
A cláusula
  1, 2, , n
Pode ser compilada como
demo([|Gs1]) :axiom(1,Gs2),
append(Gs2,[2,,n|Gs1],Gs3),
demo(Gs3).
38
Compilando os Axiomas do
Cálculo de Eventos
holds_at(F,T3) :happens(A,T1,T2),
T2<T3,
initiates(A,F,T1),
not clipped(T1,F,T2).
39
Compilando os Axiomas do
Cálculo de Eventos
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).
40
Tratamento de Informação
Incompleta
• Informação incompleta e negação por falha
• Tratamento no meta-nível
 O predicado before
 O predicado holds_at
41
O Sistema de Planejamento AECP
abdemo([holds_at(F1,T3)|Gs1],R1,R5,N1,N4) :abresolve(initiates(A,F1,T1),R1,Gs2,R1),
abresolve(happens(A,T1,T2),R1,[],R2),
abresolve(before(T2,T3),R2,[],R3),
add_neg([clipped(T1,F1,T3)],N1,N2),
abdemo_nafs(N2,R3,R4,N2,N3),
append(Gs2,Gs1,Gs3),
abdemo(Gs3,R4,R5,N3,N4).
42
Exemplos de Análises
•
•
•
•
•
•
•
Tarefas de refinamento
Sistematicidade
Representação ADL
Multicontribuidores
Decomposição hierárquica
Planejamento de ordem total
Ações de percepção
43
Metodologia
Atividades
Cronograma
Atividades
• Estudar e implementar algoritmos eficientes
da literatura de planejamento
• Alterar o meta-interpretador AECP de modo
a implementar esses algoritmos, mantendo o
propósito original de sua especificação
• Comparar os passos de planejamento nos
sistemas algorítmicos com aqueles
observados nos sistemas lógicos
45
Cronograma
Mar Abr Mai Jun Jul Ago Set Out Nov Dez
Estudar e implementar alguns
algoritmos de planejamento
selecionados da literatura
Estender o meta-interpretador
AECP de modo a implementar
esses algoritmos
Avaliar a eficiência dessas
extensões
Redigir a dissertação
Defender a dissertação
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
46