Processo de Planejamento
Andrew Diniz da Costa
Agenda
• Processo de planejamento
• Exemplo “The Blocks World”
• Reconhecimento de planos
• Considerações finais
© LES/PUC-Rio
Processo de planejamento
• O processo de planejamento refere-se quando um certo
problema é solucionado a partir de um conjunto de subpartes (passos).
• A detecção dos passos é realizada durante o processo de
“resolução do problema”.
• Primeiro a verificação para depois a execução.
© LES/PUC-Rio
Processo de planejamento
• No entanto, nem sempre é possível prever corretamente o
plano (predicado) adequado para solucionar um certo
problema.
• Dividir um problema em subproblemas permite definir de
forma mais clara onde o plano falhou de forma especifica.
• Associar o passo com a razão da sua execução
• Através da técnica de dependência de planos com
bactracking é possível determinar qual o conjunto de passos
que devem ser trocados.
© LES/PUC-Rio
Processo de planejamento
• A geração de um plano é “backward”, ou seja, deve ser
definido a partir de um estado objetivo, torna-se fácil aplicar
as dependências.
• Já aplicar dependências usando o procedimento “foward”,
pode ser mais complicado.
• Geração de planos
– Achar a solução de um problema a partir de um estado inicial.
– O planejador tenta encontrar um conjunto de ações possíveis
que obterá algum objetivo do plano.
© LES/PUC-Rio
Exemplo - The Blocks World*
• Ações
a
b
– UNSTACK(a,b)
• Coletar bloco “a” que está em cima do bloco “b”. Bloco “a” não
pode ter ninguém acima dele.
b
– STACK(a,b)
• Colocar bloco “a” em cima do bloco “b”
– PICKUP(a)
• Coletar bloco “a”. O braço robô fica segurando o bloco “a”
– PUTDOWN(a)
• Colocar bloco a. O braço robô estava segurando o bloco “a”.
* Artificial Intelligence - International Student Edition, Elaine Rich, The University of Texas at Austin
© LES/PUC-Rio
The Blocks World
• Para especificar as condições em que uma operação pode
ser executada e os resultados, deve ser definido predicados
– ON(a,b): Bloco “a” em cima do “b”
– ONTABLE(a): Bloco “a” está na tabela
– CLEAR(a): Não já nenhum bloco em cima de “a”
– HOLDING(a): O braço robô está segurando o bloco “a”.
– ARMEMPTY: O braço robô não está segurando nenhum bloco.
• Possíveis diversas lógicas
x HOLDING(x) -> ~ARMEMPTY
E
– x ONTABLE(x) -> ~
x ON(x,y)
E
–
A
– etc
© LES/PUC-Rio
The Blocks World
STACK(A,B)
P: CLEAR(B) HOLDING(A)
D: CLEAR(B) HOLDING(A)
A: ARMEMPTY
ON(A,B)
V
V
V
© LES/PUC-Rio
ON(A, B, S0)
ONTABLE(B,S0)
CLEAR(A,S0)
V
B
V
A
The Blocks World
• Estado inicial
• Estado objetivo
• Conjunto de passos que levam o estado inicial ao estado
objetivo
© LES/PUC-Rio
The Blocks World
ON(B,A)
ONTABLE(A)
ONTABLE(C)
ONTABLE(D)
ARMEMPTY
Goal:
STACK(C,A)
ON(B,D)
ONTABLE(A)
ONTABLE(D)
© LES/PUC-Rio
B
A
D
ON(C,A)
ON(B,D)
ONTABLE(A)
ONTABLE(D)
V
D
V
V
V
Start:
C
V
A
C
V
V
B
The Blocks World
ON(B,A)
CLEAR(B)
ARMEMPTY
ON(B,A) CLEAR(B) ARMEMPTY
UNSTACK(B,A)
HOLDING(C)
CLEAR(A)
HOLDING(C)
STACK(C,A)
ON(B,D)
ONTABLE(A)
ONTABLE(D)
V
V
V
HOLDING(C)
CLEAR(A)
HOLDING(C)
STACK(C,A)
ON(B,D)
ONTABLE(A)
ONTABLE(D)
V
STACK(C,A)
ON(B,D)
ONTABLE(A)
ONTABLE(D)
CLEAR(A)
HOLDING(C)
CLEAR(A)
HOLDING(C)
STACK(C,A)
ON(B,D)
ONTABLE(A)
ONTABLE(D)
© LES/PUC-Rio
V
The Blocks World
HOLDING(C)
CLEAR(A)
HOLDING(C)
STACK(C,A)
ON(B,D)
ONTABLE(A)
ONTABLE(D)
V
UNSTACK(B,A)
STACK(B,D)
PICKUP(C)
STACK(C,A)
ONTABLE(C) CLEAR(C) ARMEMPTY
PICKUP(C)
CLEAR(A)
HOLDING(C)
STACK(C,A)
ON(B,D)
ONTABLE(A)
ONTABLE(D)
STACK(B,D)
ONTABLE(C) CLEAR(C) ARMEMPTY
PICKUP(C)
CLEAR(A)
HOLDING(C)
STACK(C,A)
ON(B,D)
ONTABLE(A)
ONTABLE(D)
© LES/PUC-Rio
The Blocks World
ON(B,A)
ONTABLE(A)
ONTABLE(C)
ONTABLE(D)
ARMEMPTY
B
A
D
Goal:
UNSTACK(B,A)
STACK(B,D)
PICKUP(C)
STACK(C,A)
© LES/PUC-Rio
ON(C,A)
ON(B,D)
ONTABLE(A)
ONTABLE(D)
V
D
V
V
V
Start:
C
V
A
C
V
V
B
The Blocks World
STACK(A,B)
ON(A,B)
STACK(B,C)
ON(B,C)
UNSTACK(x, B)
CLEAR(B)
CLEAR(C)
UNSTACK(A,x)
HOLDING(A)
ON(B,C)
HOLDING(B)
ON(A,B)
PICKUP(A)
STACK(B,C)
ON(x,B)
ARMEMPTY
ON(A,x)
CLEAR(X)
CLEAR(A)
CLEAR(A)
HOLDING(B)
ARMEMPTY
ONTABLE(A)
ARMEMPTY
CLEAR(B)
HOLDING(A)
CLEAR(B)
CLEAR(B)
HOLGIN(A)
ON(B,C)
ON(B,C)
ON(B,C)
...
© LES/PUC-Rio
CLEAR(C)
Reconhecimento de Planos
Uma pessoa vai ao aeroporto com suas malas de viagem e
pergunta no guiche de compras: -Qual o próximo vôo
disponível para Belém?
Com isso, podemos deduzir que a pessoa provavelmente
deseja comprar uma passagem para Belém em um horário
próximo.
© LES/PUC-Rio
Reconhecimento de Planos
• De maneira geral, consiste em encontrar uma explicação das ações
observadas, em termos das ocorrências delas em um ou mais
planos.
• Complexidade do problema surge ao tentar inferir planos
plausíveis de ações não observadas explicitamente, isto é, ações
que se encontram de forma implicita no conhecimento do agente.
• Reconhecimento pretendido (intended recognition)
• Este processo não é puramente dedutivo
– Modelo de representação do conhecimento
– Boas heurísticas
– Biblioteca de planos típicos
© LES/PUC-Rio
Reconhecimento de Planos
• Aplicação em sistemas
– Tradução
– Sistemas de help do Unix
– Resolvendo problemas colaborativos
– Etc
• Propostas de modelos de planos
© LES/PUC-Rio
Modeling the User’s Plans and Goals
• “Context Model” representa como uma ação pode contribuir
para um objetivo.
Gx
Gw
A5
A6
Gb
A2
Gz
Gy
A3
Gc
A4
Ga
A1
Carberry, S.:1988, ‘Modeling the User’s Plans and Goals’. Computational Linguistics 14(3), 23-37
© LES/PUC-Rio
A Formal Theory of Plan Recognition and its
Implementation
• Planos e ações são definidos como eventos
• O conhecimento do reconhecedor é representado por:
– Conjunto de axiomas
– Conjunto de predicados da lógica de primeira-ordem
(Hierarquia de Eventos)
• São tratados somente as instâncias dos planos nos quais os
tipos de eventos aparecem na hierarquia de eventos, pois o
conhecimento representado na hierarquia é completo.
Kautz H.A. "A Formal Theory of Plan Recognition", Morgan Kaufman,1987.
© LES/PUC-Rio
A Formal Theory of Plan Recognition and its
Implementation
© LES/PUC-Rio
Generation and selection of likely interpretations during
plan recognition in taskoriented consultation systems
• Sistema usa heurísticas para distribuir probabilidades para
os possíveis planos.
• Estimativa realizada a partir da experiência adquirida.
• Uso da regras de Bayes.
Raskutti B and I Zukerman “Generation and selection of likely interpretations during plan recognition in taskoriented
consultation systems” User Modeling and UserAdapted Interaction 1(4), 323-353.
© LES/PUC-Rio
Considerações finais
• Processo de planejamento
– Geração de planos
– Reconhecimento de planos
• Sistemas em diversas áreas.
• Indução é um ponto complexo.
© LES/PUC-Rio
Referências
• Raskutti B and I Zukerman “Generation and selection of likely
interpretations during plan recognition in taskoriented
consultation systems” User Modeling and UserAdapted Interaction
1(4), 323-353.
• Kautz H.A. "A Formal Theory of Plan Recognition", Morgan
Kaufman,1987.
• Carberry, S.:1988, ‘Modeling the User’s Plans and Goals’.
Computational Linguistics 14(3), 23-37.
• Artificial Intelligence - International Student Edition, Elaine Rich,
The University of Texas at Austin.
• Carberry, Sandra; Techniques for Plan Recognition, Department of
Computer Science.
• Nogueira, José H. M.;Alcazar, josé J. P.;Furtado, Antônio L.; Análise
e Implementação da Teoria Formal de Reconhecimento de Planos,
Departamento de Informática Pontifícia Universidade Católica do
Rio de Janeiro, Julho 2004.
© LES/PUC-Rio
Fim