Raciocínio Abdutivo usando Cálculo de Eventos e sua correspondência

com Sistemas de Planejamento

Exame de Qualificação

Silvio do Lago Pereira

2

Introdução

• Planejamento

• Sistemas corretos versus práticos

• Raciocínio e representação

• O artigo de Green

• O artigo de Shanahan

3

Objetivo

• Mostrar que

Sistemas de planejamento lógicos

Sistemas de planejamento algorítmicos

4

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

5

Organização

• Representação de conhecimento

• Planejamento clássico

• Planejamento abdutivo

• Metodologia

Representação de Conhecimento

Cálculo de Situações

Representação STRIPS

Cálculo de Eventos

7

Cálculo de Situações

S0

1, ..., n

Do(,S0)

1 , ..., i -1,i+k, ..., n

n+1, ..., n+j

Holds(i,S0)Holds(n+1,Do(,S0))

Axiomas de quadro

Axiomas de efeito

8

Mundo dos Blocos

• Situações: S0 e S1

• Fluentes: Sobre(x,y) e Livre(x) • Ação: Move(x,y)

9

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(mn) axiomas de quadro

10

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

11

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) (xB xC)].

12

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)})

13

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()

14

Representação ADL

• É uma extensão da representação STRIPS

OPERADOR(Move(x, y, z),

PRECONDS: {Pasta(x), Em(x,y) , xz},

EFEITOS: {Em(x,z), Em(x,y),

v(Objeto(v) (Dentro(v,x) (Em(v,z) Em(v,y)) ))} )

15

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)

16

Axiomas EC

(EC1) HoldsAt(f,t) InitiallyP(f)

Clipped(0,f,t)

(EC2) HoldsAt(f,t) Happens(a,t1,t2)

Initiates(a,f,t1)

t2t

Clipped(t1,f,t)

17

(EC3) HoldsAt(f,t) InitiallyN(f) Declipped(0,f,t)

(EC4) HoldsAt(f,t) Happens(a,t1,t2) Terminates(a,f,t1) t2t Declipped(t1,f,t)

18

(EC5) Clipped(t1,f,t2)

a, t3, t4 [ Happens(a,t3,t4) t1t3 t4t2 (Terminates(a,f,t3) Releases(a,f,t3))]

(EC6) Declipped(t1,f,t2)

a, t3, t4 [ Happens(a,t3,t4) t1t3 t4t2 (Initiates(a,f,t3) Releases(a,f,t3))]

(EC7) Happens(a,t1,t2) t1 t2

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

20

Busca no Espaço de Estados

21

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.

22

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.

23

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

24

Planejamento de Ordem Total

Planejamento de ordem total como busca no espaço de planos

Planejamento regressivo como busca no espaço de estados

25

Planejamento de Ordem Parcial

A0 A

Plano Vazio

A0 Ap c

Vínculo Causal

A0 A

p c

t

Ameaça

26

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

27

Algoritmos de Planejamento

• UCPOP - suporta a representação ADL

• SNLP - planejamento sistemático• HTN - decomposição hierárquica

Planejamento Abdutivo

Abdução

Planejamento Abdutivo com EC

Meta-interpretador Abdutivo para EC

29

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

30

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

31

Exemplo

(1) grama-molhada  choveu (2) grama-molhada  irrigada (3) sapatos-molhados  grama-molhada (4)  sapatos-molhados , { } 0

(5)  grama-molhada , { } R(4,3)(6)  choveu , { }

R(5,1)(7)  irrigada , { } R(5,2)(8) , { irrigada } A(7)

32

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

33

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 |=

34

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).

35

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).

36

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).

37

(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).

38

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).

39

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).

40

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).

41

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

42

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).

43

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

Metodologia

Atividades

Cronograma

45

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

46

Cronograma

Mar Abr Mai Jun Jul Ago Set Out Nov DezEstudar e implementar algunsalgoritmos de planejamentoselecionados da literatura

x x x x

Estender o meta-interpretadorAECP de modo a implementaresses algoritmos

x x x x x x

Avaliar a eficiência dessasextensões

x x x x x

Redigir a dissertação x x x x x xDefender a dissertação x