Planejamento em
Inteligência Artificial
Leliane Nunes de Barros
Motivação
• Um dos principais objetivos da IA foi/é o
desenvolvimento de um Solucionador Geral
de Problemas (GPS) [Newell & Simon, 1961]
Problema
Linguagem
Planejador
Solução
• Idéia: problemas são descritos numa
linguagem de alto-nível de abstração e são
resolvidos automaticamente
• Objetivo: facilitar a modelagem de problemas
com um prejuízo mínimo em termos de
desempenho.
LabIA 2003
2
Escopo do planejador
• Planejamento não é tão geral como GPS!
– a solução do Cubo Mágico é uma sequência de
ações
– a solução para um problema de diagnóstico é uma
estratégia de ações sendo a determinação precisa
dos testes a serem realizados (ações), uma
função das observações coletadas ==> técnica de
planejamento condicional ou planejamento e
execução
• Para definir uma linguagem e um algoritmo
é preciso definir um escopo
LabIA 2003
3
Modelos Matemáticos
Modelos permitem definir o escopo de um
planejador
– o que é um problema de planejamento
– o que é uma solução (plano)
– o que é uma solução ótima
LabIA 2003
4
Componentes de Planejamento
• Modelos para compreender os algoritmos e
estabelecer classes de problemas e tipos de
solução
• Linguagens para representação de
problemas
• Algoritmos para resolver esses problemas
(usando informações disponíveis na
linguagem de representação de problemas)
LabIA 2003
5
Planejamento Clássico
Pode ser caracterizado como um Modelo de Estados
– um espaço de estados S , finito e não-vazio
– um estado inicial s0S
– um conjunto de estados meta SGS
– um conjunto de ações aplicáveis A(s)A, para sS
– uma função de transição sf(a,s), para s,sS e aA(s)
– uma função custo c(a,s)>0, para sS e aA(s)
LabIA 2003
6
Modelo de Estados
Uma solução é uma sequência de ações aplicáveis que
mapeiam s0 num estado meta SG .
Uma solução ótima minimiza a soma dos custos das ações.
planejamento com sensoriamento
planejamento com incerteza
planejamento com recursos
planejamento temporal
...
LabIA 2003
Modelos diferentes
7
Um problema simples
• Domínio = Estados (posições dos blocos) + Ações (move)
• s0: (“red on table”, “blue on table”, “green on blue”)
• SG: (“red on table”, “green on blue”, “blue on green”)
• Plano: (“move green on red”  “move blue on green”)
• Problema de Planejamento:
Dado um domínio (estados e ações), um estado inicial e o estado meta,
o problema de planejamento é encontrar um plano de ações que
transforma o estado inicial no estado meta
LabIA 2003
8
Planejamento como busca progressiva
• Domínio = Espaço de Busca
• Problema:
encontrar um caminho que ligue o estado inicial e o
estado meta
LabIA 2003
9
Espaço de estados
C
A
B
B
A
C
A
BC
A
BC
B
C
A
B
A
C
A
A BC
C
A B
C
A B
C
B
A
B
C
A
B
C
A
C
B
LabIA 2003
10
Depots: Logística + Mundo dos Blocos
5 localizações, 3 pilhas, 100 containers  10277 estados
LabIA 2003
11
Outras áreas e modelos
• Modelos para PO, controle, combinatória, ...
–
–
–
–
programação linear
programação inteira
SAT
CSP ...
Essas áreas começam
a fazer a distinção entre
modelos e linguagens
• Planejamento em IA difere de 2 maneiras:
– trata uma classe diferente de modelos
– modelos são representados implicitamente na
linguagem
LabIA 2003
12
Modelos Matemáticos em Planejamento
• Modelo de Estados: tipo mais simples
• Modelo de Estados Probabilístico e Nãodeterminístico: dinâmica mais complexa
• Modelo de Estados Probabilístico e Nãodeterminístico com informação parcial do
mundo: percepção mais complexa
(realimentação)
• modelos ainda mais complexos envolvem
aspectos de escalonamento: recursos,
tempo, ações durativas, concorrência, etc
LabIA 2003
13
Modelos Lógicos em Planejamento
Modelos lógicos além de definerem o escopo de
planejamento também definem a linguagem e o
tipo de raciocínio
– Cálculo de Situações com raciocínio dedutivo
(originalmente proposto em 63)
• tipo de raciocínio natural para planejamento: dedução
– Cálculo de Eventos com raciocínio abdutivo
• tipo de raciocínio natural para planejamento: abdução
– outras lógicas
A grande maioria das lógicas de ações não “deliberam”
planos (planejam) mas só permitem o raciocínio sobre
ações e planos (dados).
LabIA 2003
14
Ingredientes de Planejamento
Modelos
Linguagens
Algoritmos
LabIA 2003
15
Linguagens de Planejamento
Linguagens de planejamento servem para:
– descrever problemas
– descrever estados
– descrever ações
Ocupam dois papéis:
– especificação: descrição precisa do problema
– computação: revelam informações heurísticas
LabIA 2003
16
Linguagem dos Modelos Lógicos
• Adota-se uma linguagem lógica para descrever
estados, ações e problemas
• Vantagem: pode-se utilizar um mecanismo de
inferência lógica como algoritmo
Robótica Cognitiva:
A melhor maneira de se explicar o
comportamento inteligente é interpretando-o
como produto de um raciocínio correto sobre
uma representação correta.
LabIA 2003
17
Cálculo de situações
• Ontologia: situações, fluentes e ações
• Linguagem
–
–
–
–
LabIA 2003
s0
do( , s)
poss( ,s)
holds(f , s)
18
Mundo dos Blocos
s0
• fluentes:
clear(X)
ontable(X)
on(X,Y)
• ações:
stack(X,Y)
unstack(X,Y)
move(X,Y,Z)
LabIA 2003
C
A
B
19
Especificação lógica do domínio
• axiomas de observação:
s0
holds(clear(c),s0)
holds(on(c,a),s0)
...
C
A B
• axiomas de efeito:
holds(clear(Y), do(move(X,Y,Z),S))
holds(on(X,Z), do(move(X,Y,Z),S))
...
• axiomas de precondições:
poss(move(X,Y,Z),S) 
holds(clear(X),S)  holds(clear(Z),S)  holds(on(X,Y),S)
…
• axioma de persistência (frame axiom):
holds(F,do(A,S)) :- poss(A,S), holds(F,S), not affects(A,F).
LabIA 2003
20
O problema da persistência
s0
C
A
s1  do(move(c,a,b),s0)
move(c,a,b)
B
holds( clear(b), s0)
holds( clear(c), s0)
holds( ontable(a), s0)
holds( ontable(b), s0)
holds( on(c,a), s0)
A
axiomas de efeito
C
B
holds( clear(a), s1)
holds( on(c,b), s1)
holds( clear(c), s1)
holds( ontable(a), s1)
holds( ontable(b), s1)
axiomas de persistência
LabIA 2003
21
Planejamento dedutivo
Dados:
A : axiomatização do domínio
I : situação inicial
G : meta de planejamento
O planejamento consiste em provar que
A  I | S[exec(S)  G(S)],
sendo executabilidade definida indutivamente por:
exec(s0)
exec(do(A,S))  poss(A,S)  exec(S)
LabIA 2003
22
Um planejador em PROLOG
holds(clear(b),s0).
holds(clear(c),s0).
holds(ontable(a),s0).
holds(ontable(b),s0).
holds(on(c,a),s0).
holds(on(X,Y),do(stack(X,Y),S)).
holds(clear(Y),do(unstack(X,Y),S)).
holds(ontable(X),do(unstack(X,Y),S)).
s0
C
A B
poss(stack(X,Y),S) :- holds(ontable(X),S), holds(clear(X),S), holds(clear(Y),S), X\=Y.
poss(unstack(X,Y),S) :- holds(clear(X),S), holds(on(X,Y),S).
holds(F,do(A,S)) :- poss(A,S), holds(F,S), not affects(A,F).
affects(stack(X,Y),clear(Y)).
affects(stack(X,Y),ontable(X)).
affects(unstack(X,Y),on(X,Y)).
exec(s0).
exec(do(A,S)) :- poss(A,S), exec(S).
plan(s0).
plan(do(A,S)) :- plan(S).
LabIA 2003
23
Consultando o planejador
s0
?- plan(S), exec(S), holds(on(a,c),S).
S = do(stack(a,c),do(unstack(c,a),s0))
yes
C
A B
?- plan(S), exec(S), holds(on(a,b),S), holds(on(b,c),S).
S = do(stack(a,b),do(stack(b,c),do(unstack(c,a),s0)))
yes
?- holds(F, do(stack(a,b),do(stack(b,c),do(unstack(c,a),s0)))).
F = on(a,b) ;
F = on(b,c) ;
F = clear(a) ;
F = ontable(c) ;
no
LabIA 2003
24
A linguagem Strips (Fikes e Nilsson, 1971)
• Strips (Stanford Research Institute Problem-Solving)
é a mais antiga, simples e usada linguagem de
planejamento (sistema Strips)
• Evolução: Strips  ADL  PDDL2.1  PDDL+
• Um problema em Strips é uma tupla <A, O, I, G>
- A é o conjunto de todos os átomos (variáveis
booleanas descritores de estados),
- O é um conjunto de todos os operadores (ações
proposicionais), e
- I  A representa a situação inicial (descrição
completa de estado)
- G  A representa as situações meta (descrição
parcial de estados)
LabIA 2003
25
A linguagem Strips
• Os operadores oO são representados por
três listas:
– lista Pre, Pre  A
– lista Add, Add(o)  A
– lista Del, Del  A
Intuitivamente: Pre(o) especifica os átomos que
devem ser verdadeiros para o ser aplicável, Add(o)
especifica os átomos que passam a ser
verdadeiros após a execução de o e Del(o)
especifica os átomos que passam a ser falsos
após a execução de o
Qual é a solução para o problema do quadro?
LabIA 2003
26
Strips: da linguagem aos modelos
Um problema Strips, P = <A, O, I, G> determina um modelo
de estados S(P) em que:
• os estados sS são coleções de átomos;
• o estado inicial s0 é I
• os estados meta sSG são aqueles em que G  s
• as ações aA(s) são operadores oO tal que Prec(o)  s
• a função de transição f mapeia estados s em estados
s' = f(s, a), tal que s' = s - Del(a) + Add(a) para a A(s)
• os custos das ações são iguais a 1
• a solução (ótima) de um problema de planejamento é a
solução (ótima) do Modelo de Estados S(P)
LabIA 2003
27
STRIPS: sintaxe e semântica
oper(act: move(c,a,b),
pre: { clear(c), clear(b), on(c,a) },
add: { clear(a), on(c,b) },
del: { clear(b), on(c,a) })
move(c,a,b)
C
A B
clear(b)
clear(c)
ontable(a)
ontable(b)
on(c,a)
LabIA 2003
clear(b)
clear(c)
ontable(a)
ontable(b)
on(c,a)
clear(b)
clear(c)
ontable(a)
ontable(b)
on(c,a)
clear(a)
on(c,b)
C
A B
clear(b)
clear(c)
ontable(a)
ontable(b)
on(c,a)
clear(a)
on(c,b)
28
ADL e PDDL
• Inclui: tipos, funções, variáveis numéricas,
ações durativas, funções de otimização ==>
planejamento/escalonamento
• AIPS 2002 Planning Competition
http://www.dur.ac.uk/d.p.long/competition.htm
LabIA 2003
29
PDDL - ação Strips
(:action turn_to
:parameters (?s - satellite ?d_new - direction ?d_prev - direction)
:precondition (and (pointing ?s ?d_prev)
(not (= ?d_new ?d_prev))
)
:effect (and (pointing ?s ?d_new)
(not (pointing ?s ?d_prev))
)
)
LabIA 2003
30
PDDL - ação Strips-numérico
(:action turn_to
:parameters (?s - satellite ?d_new - direction ?d_prev - direction)
:precondition (and (pointing ?s ?d_prev)
(not (= ?d_new ?d_prev))
(>= (fuel ?s) (slew_time ?d_new ?d_prev))
)
:effect (and
(pointing ?s ?d_new)
(not (pointing ?s ?d_prev))
(decrease (fuel ?s) (slew_time ?d_new ?d_prev))
(increase (fuel-used) (slew_time ?d_new ?d_prev))
)
)
LabIA 2003
31
PDDL - ação Strips-temporal
(:durative-action turn_to
:parameters (?s - satellite ?d_new - direction ?d_prev - direction)
:duration (= ?duration 5)
:condition (and
(at start (pointing ?s ?d_prev))
(over all (not (= ?d_new ?d_prev)))
)
:effect (and
(at end (pointing ?s ?d_new))
(at start (not (pointing ?s ?d_prev)))
)
)
LabIA 2003
32
PDDL - ação Strips-temporal*
(:durative-action turn_to
:parameters (?s - satellite ?d_new - direction ?d_prev - direction)
:duration (= ?duration (slew_time ?d_prev ?d_new))
:condition (and
(at start (pointing ?s ?d_prev))
(over all (not (= ?d_new ?d_prev)))
)
:effect (and
(at end (pointing ?s ?d_new))
(at start (not (pointing ?s ?d_prev)))
)
)
LabIA 2003
33
PDDL - ação Strips-temporal*
(:durative-action take_image
:parameters (?s - satellite ?d - direction ?i - instrument ?m - mode)
:duration (= ?duration 7)
:condition (and
(over all (calibrated ?i))
(over all (on_board ?i ?s))
(over all (supports ?i ?m) )
(over all (power_on ?i))
(over all (pointing ?s ?d))
(at end (power_on ?i))
(at start (>= (data_capacity ?s) (data ?d ?m)))
)
:effect (and
(at start (decrease (data_capacity ?s) (data ?d ?m)))
(at end (have_image ?d ?m))
(at end (increase (data-stored) (data ?d ?m)))
)
LabIA 2003
34
Ingredientes de Planejamento
Modelos
Linguagens
Algoritmos
LabIA 2003
35
Algoritmos para resolver probelmas em ME
• Problemas de planejamento podem ser resolvidos
por algoritmos de busca no espaço de estados S(P)
==> técnica considerada ineficiente até
recentemente …
• Espaço de busca:
– Planejador progressivo (forward planning)
– Planejador regressivo (backward planning)
• Algoritmos de busca exaustiva
– Os estados meta não são levados em conta:
DFS, BFS, Custo Uniforme, ID
LabIA 2003
36
Algoritmos para resolver Modelos de Estado
• Algoritmos de busca informada
– Para controlar o processo, a busca usa uma
função h(s) que estima a distância (custo) do
estado s aos estados SG: A*, IDA*, Best First
Search, Hill Climbing, Branch & Bound
LabIA 2003
37
Planejadores conhecidos
• Algoritmo Strips (71): planejamento totalmente
ordenado:
– Análise means-ends (50): adicione ações no plano
que sejam aplicáveis e que atinjam sub-metas de G
– Dificuldade: em geral, para problemas interessantes
não existem ações que sejam aplicáveis e relevantes
para satisfazer a meta, ao mesmo tempo.
– Solução Strips: construir estados da busca mais
complicados mantendo uma hierarquia de sub-metas
(pilha de sub-metas) e planos incompletos ==>
Busca num Espaço de Planos
LabIA 2003
38
Busca no espaço de planos
stack(a,b)
stack(b,c)
unstack(c,a)
stack(a,b)
unstack(c,a)
stack(a,b)
stack(b,c)
stack(b,c)
stack(b,c)
stack(a,b)
stack(a,b)
LabIA 2003
39
Ordem parcial, vínculos e ameaças
a1
a3


a2
ameaça
LabIA 2003
a3

a1

a1
a2

a2
a3

antecipar
postergar
40
Ordem parcial, vínculos e ameaças
a0
clear(b) clear(c) ontable(a) ontable(b) on(c,a)
clear(a) clear(b) ontable(a)
clear(b) clear(c) ontable(b)
stack(a,b)
stack(b,c)
 clear(b)
ontable(a) on(a,b)
on(b,c) clear(c) ontable(b)
on(a,b) on(b,c)
a
S = {stack(b,c),
{a0, a}
{stack(a,b),
stack(a,b),
a0, a}
a0, a}
O = {stack(b,c)stack(a,b)
{a0stack(b,c)a
a}
stack(a,b)a
a00stack(a,b)a
a
, a}0stack(b,c)a
a}0stack(a,b)a, a0a}

,, a
, a0a
, 
{} 0clear(b)@stack(b,c),
L = {a
{stack(a,b)on(a,b)@a
{stack(b,c)on(b,c)@a
stack(b,c)on(b,c)@a}, stack(a,b)on(a,b)@a}
,}stack(a,b)on(a,b)@a
LabIA 2003
41
Algoritmo POP
function POP(initial, goal, operators) returns plan
plan  Make-Minimal-Plan(initial, goal)
loop do
if Solution? (plan) then return plan
Sneed , c  Select-Subgoal(plan)
Choose-Operator(plan, operators, Sneed, c)
Resolve-Threats(plan)
end
function Select-Subgoal(plan) returns Sneed , c
pick a plan step Sneed from Steps(plan)
with a precondition c that has not been achieved
return Sneed , c
LabIA 2003
42
POP algorithm (cont.)
procedure Chose-Operator(plan,operators, Sneed , c )
choose a step Sadd from operators or Steps(plan) that has c as an
effect
if there is no such step then fail
add the causal link Sadd c Sneed to Links(plan)
add the ordering constraint Sadd < Sneed to Orderings(plan)
if Sadd is a newly added step from operators then
add Sadd to Steps(plan)
add Start < Sadd < Finish to Orderings(plan)
LabIA 2003
43
POP algorithm (cont.)
procedure Resolve-Threats(plan)
for each Sthreat that threatens a link Si c Sj in Links(plan) do
choose either
Demotion: Add Sthreat < Si to Orderings(plan)
Promotion: Add Si < Sthreat to Orderings(plan)
if not consistent(plan) then fail
end
POP é correto, completo e sistemático (busca sem repetição)
LabIA 2003
44
Planejadores modernos
• Graphplan (1995 - …)
– constrói um grafo de planejamento contendo todos os
planos possíveis de um determinado comprimento para
então extrair um plano por meio de uma busca
regressiva no grafo
• SatPlan (1996 - …) mapeia problemas de
planejamentp em um problema SAT e usa um
SATsolver eficiente* .
• Blackbox: = Satplan + Graphplan
• Planejamento como Busca Local com uso de
Heurísticas … algoritmos de maior sucesso nas
últimas competições de planejamento
LabIA 2003
45
Grafo de Planejamento
• Planning Graph [Blum&Furst 1997]
– expansão do grafo
0
i-1
i
proposições
i+1
proposições
ações
LabIA 2003
46
Grafo de Planejamento
• Grafo de Planejamento
– Relações de Mutex
Efeitos
Inconsistentes
LabIA 2003
Interferência
Necessidades
conflitantes
Suporte
Inconsistente
47
Domínio Jantar
cozinhar
:prec (mãos_limpas)
:efeito (jantar)
embrulhar :prec (silêncio)
:efeito (presente)
carregar_lixo
:prec (lixo)
:efeito ( ¬lixo, ¬mãos_limpas)
triturar_lixo
:prec (lixo)
:efeito (¬lixo, ¬silêncio)
LabIA 2003
48
Grafo de Planejamento
LabIA 2003
49
SATPLAN
História: Kautz and Selman, 1992
• Inspiração nos avanços dos algoritmos de
satisfazibilidade
Idéia
• Codificar o problema de planejamento como
uma grande fórmula lógica do tipo:
Initial- state & all- possible- actions & goal
• encontrar uma valoração qua satisfaça a
fórmula que resulte no plano
LabIA 2003
50
SATPLAN
• Codificação baseada no Cálculo de
Situações
• Tempo: assume valores inteiros
• Estado Inicial: Lixo  MaosLimpas  Silencio
• Meta: Jantar  Presente  Lixo
LabIA 2003
51
SATPLAN: Jantar Surpresa
• Símbolos Proposicionais (schemas de fluentes)
lixo(I)
maos_limpas(I)
silencio(I)
jantar(I)
presente(I)
Schemas de ações
cozinhar( I )
embrulhar( I )
carregar_lixo( I )
triturar_lixo( I )
LabIA 2003
52
SATPLAN: Jantar Surpresa
• Símbolos Proposicionais
1 lixo( 1 )
2 maos_limpas( 1 )
3 silencio( 1 )
4 jantar( 1 )
5 presente( 1 )
6 lixo( 2 )
7 maos_limpas( 2 )
8 silencio( 2 )
9 jantar( 2 )
10 presente( 2 )
11 lixo( 3 )
…
32
TOTAL:
LabIA 2003 cnf 32 143
53
SATPLAN: Axiomas de Efeito
• Ações implicam seus efeitos
– Schemas de Axiomas de efeitos
cozinhar( I ) -> jantar( I + 1 )
embrulhar( I ) -> presente( I + 1 )
– Efeitos conjuntivos devem ser descritos por uma
cláusula para cada efeito
carregar_lixo( I ) -> ~lixo( I + 1 )
carregar_lixo( I ) -> ~maos_limpas( I + 1 )
triturar_lixo( I ) -> ~lixo( I + 1 )
triturar_lixo( I ) -> ~silencio( I + 1 )
LabIA 2003
54
SATPLAN: Axiomas de Precondições
• Ações implicam em suas pré-condições
– Schemas de Axiomas de pré-condições
cozinhar( I ) -> maos_limpas ( I )
embrulhar( I ) -> silencio( I )
LabIA 2003
55
SATPLAN: Axiomas de Persistência
Ações implicam em fluentes que não são
afetados por ela
– aparecem sentenças do tipo:
A(I) ^ B(I) -> A(I+1)
– que correspondem a cláusula:
~A(I) v ~B(I) v A(I+1)
LabIA 2003
56
SATPLAN: Axiomas de Persistência
[ lixo( I ) ^ cozinhar( I ) ] -> lixo( I + 1 )
[ ~lixo( I ) ^ cozinhar( I ) ] -> ~lixo( I + 1 )
c [ lixo( I ) ^ embrulhar( I ) ] -> lixo( I + 1 )
c [ ~lixo( I ) ^ embrulhar( I ) ] -> ~lixo( I + 1 )
c [ maos_limpas( I ) ^ cozinhar( I ) ] -> maos_limpas( I + 1 )
c [ ~maos_limpas( I ) ^ cozinhar( I ) ] -> ~maos_limpas( I + 1 )
c [ maos_limpas( I ) ^ embrulhar( I ) ] -> maos_limpas( I + 1 )
c [ ~maos_limpas( I ) ^ embrulhar( I ) ] -> ~maos_limpas( I + 1 )
c [ maos_limpas( I ) ^ triturar_lixo( I ) ] -> maos_limpas( I + 1 )
c [ ~maos_limpas( I ) ^ triturar_lixo( I ) ] -> ~maos_limpas( I + 1 )
c [ silencio( I ) ^ cozinhar( I ) ] -> silencio( I + 1 )
c [ ~silencio( I ) ^ cozinhar( I ) ] -> ~silencio( I + 1 )
c [ silencio( I ) ^ embrulhar( I ) ] -> silencio( I + 1 )
c [ ~silencio( I ) ^ embrulhar( I ) ] -> ~silencio( I + 1 )
c [ silencio( I ) ^ carregar_lixo( I ) ] -> silencio( I + 1 )
c [ ~silencio( I ) ^ carregar_lixo( I ) ] -> ~silencio( I + 1 )
LabIA 2003
57
SATPLAN: Axiomas de Persistência
c [ jantar( I ) ^ embrulhar( I ) ] -> jantar( I + 1 )
c [ ~jantar( I ) ^ embrulhar( I ) ] -> ~jantar( I + 1 )
c [ jantar( I ) ^ carregar_lixo( I ) ] -> jantar( I + 1 )
c [ ~jantar( I ) ^ carregar_lixo( I ) ] -> ~jantar( I + 1 )
c [ jantar( I ) ^ triturar_lixo( I ) ] -> jantar( I + 1 )
c [ ~jantar( I ) ^ triturar_lixo( I ) ] -> ~jantar( I + 1 )
c [ presente( I ) ^ cozinhar( I ) ] -> presente( I + 1 )
c [ ~presente( I ) ^ cozinhar( I ) ] -> ~presente( I + 1 )
c [ presente( I ) ^ carregar_lixo( I ) ] -> presente( I + 1 )
c [ ~presente( I ) ^ carregar_lixo( I ) ] -> ~presente( I + 1 )
c [ presente( I ) ^ triturar_lixo( I ) ] -> presente( I + 1 )
c [ ~presente( I ) ^ triturar_lixo( I ) ] -> ~presente( I + 1 )
LabIA 2003
58
SATPLAN: continuidade no plano
• Deve ser escolhida uma ação em cada instante
– Schemas de axiomas de continuidade no plano
cozinhar( I ) v embrulhar( I ) v carregar_lixo( I ) v
triturar_lixo( I )
LabIA 2003
59
SATPLAN: plano totalmente ordenado
• Apenas uma ação em cada instante
– Schemas de axiomas de não paralelismo de
ações
cozinhar( I ) -> ~embrulhar( I )
cozinhar( I ) -> ~carregar_lixo( I )
cozinhar( I ) -> ~triturar_lixo( I )
embrulhar( I ) -> ~cozinhar( I )
embrulhar( I ) -> ~carregar_lixo( I )
embrulhar( I ) -> ~triturar_lixo( I )
carregar_lixo( I ) -> ~cozinhar( I )
carregar_lixo( I ) -> ~embrulhar( I )
carregar_lixo( I ) -> ~triturar_lixo( I )
triturar_lixo( I ) -> ~cozinhar( I )
triturar_lixo( I ) -> ~embrulhar( I )
triturar_lixo( I ) -> ~carregar_lixo( I )
LabIA 2003
60
Planejamento como busca heurística
• UNPOP [Drew McDermott, 96] Greedy
Regression-Match Graphs
• HSP [Geffner, 97] Heuristic Search Planner
• FF [Hoffmann, 2000] Fast Forward
• ...
LabIA 2003
61
Planejamento Heurístico
• Heurística h(s) é computada resolvendo um
problema relaxado. Exemplo:
– distância de Manhattan
– comprimento do plano solução de um problema
relaxado em que são removidas todas as listas de
eliminação das ações
• Heurística informativa e admissível … mas
ainda recai num problema intratável
LabIA 2003
62
HSP
• Forward planning
• algoritmos de busca: Hill-Climbing ou A* com
uso de uma função heurística derivada de
uma descrição de alto-nível de ações
LabIA 2003
63
Planejamento Heurístico: HSP
Função heurística aditiva
• heurística h(s) é uma estimativa do número de passos
necessários para resolver o problema relaxado, ou
seja, ações sem listas de eliminação.
• s: estado, p: proposição,
• cs(p): estimativa do custo para atingir p apartir de s
• cs(Prec(op): custo estimado para se atingir as
precondições da ação op de s
{
cs (p) 
0
se p s
minopO( p ) [1+ cs (Prec(op))] caso contrário
Heurística do HSP (não-admissível): h( s ) 
c ( p)
p G
LabIA 2003
s
64