Planejamento em Inteligência Artificial

Leliane Nunes de Barros

LabIA 2003

2

Motivação

• Um dos principais objetivos da IA foi/é o desenvolvimento de um Solucionador Geral de Problemas (GPS) [Newell & Simon, 1961]

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

Problema Linguagem Planejador Solução

LabIA 2003

3

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

4

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

5

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

6

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 s0S

– um conjunto de estados meta SGS

– um conjunto de ações aplicáveis A(s)A, para sS

– uma função de transição sf(a,s), para s,sS e

aA(s)

– uma função custo c(a,s)>0, para sS e aA(s)

LabIA 2003

7

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 sensoriamentoplanejamento com incertezaplanejamento com recursosplanejamento temporal...

Modelos diferentes

LabIA 2003

8

• 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

Um problema simples

LabIA 2003

9

• Domínio = Espaço de Busca

• Problema:encontrar um caminho que ligue o estado inicial e o estado meta

Planejamento como busca progressiva

LabIA 2003

10

Espaço de estados

A

BC

AB

C

A B C ABC

AB C

ABCA

BC

A BC

A BC

ABC

AB

CAB C A

BC

LabIA 2003

11

Depots: Logística + Mundo dos Blocos

5 localizações, 3 pilhas, 100 containers 10277 estados

LabIA 2003

12

Outras áreas e modelos

• Modelos para PO, controle, combinatória, ...– programação linear– programação inteira– SAT– CSP ...

• Planejamento em IA difere de 2 maneiras:– trata uma classe diferente de modelos – modelos são representados implicitamente na

linguagem

Essas áreas começam a fazer a distinção entre

modelos e linguagens

LabIA 2003

13

Modelos Matemáticos em Planejamento

• Modelo de Estados: tipo mais simples• Modelo de Estados Probabilístico e Não-

determinístico: dinâmica mais complexa• Modelo de Estados Probabilístico e Não-

determiní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

14

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

15

Ingredientes de Planejamento

ModelosLinguagensAlgoritmos

LabIA 2003

16

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

17

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

18

Cálculo de situações

• Ontologia: situações, fluentes e ações

• Linguagem– s0

– do( , s)– poss( ,s)– holds(f , s)

LabIA 2003

19

Mundo dos Blocos

BA

C

s0

• fluentes:clear(X)ontable(X)on(X,Y)

• ações:stack(X,Y)unstack(X,Y)move(X,Y,Z)

LabIA 2003

20

• axiomas de observação: holds(clear(c),s0)holds(on(c,a),s0)...

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

Especificação lógica do domínio

BAC

s0

LabIA 2003

21

O problema da persistência

move(c,a,b)BA

s1 do(move(c,a,b),s0)

C

s0

BAC

holds( clear(b), s0)holds( clear(c), s0)holds( ontable(a), s0)holds( ontable(b), s0)holds( on(c,a), s0)

axiomas de persistência

holds( clear(c), s1)holds( ontable(a), s1)holds( ontable(b), s1)

axiomas de efeitoholds( clear(a), s1)holds( on(c,b), s1)

LabIA 2003

22

Dados:A : axiomatização do domínioI : situação inicialG : 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)

Planejamento dedutivo

LabIA 2003

23

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

BAC

s0

LabIA 2003

24

Consultando o planejador

?- plan(S), exec(S), holds(on(a,c),S).

S = do(stack(a,c),do(unstack(c,a),s0))yes

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

BAC

s0

LabIA 2003

25

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

26

A linguagem Strips• Os operadores oO 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

27

Strips: da linguagem aos modelos

Um problema Strips, P = <A, O, I, G> determina um modelo de estados S(P) em que:

• os estados sS são coleções de átomos;• o estado inicial s0 é I • os estados meta sSG são aqueles em que G s• as ações aA(s) são operadores oO 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

28

STRIPS: sintaxe e semântica

BACmove(c,a,b)

BAC

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)

clear(b)clear(c)ontable(a)ontable(b)on(c,a)clear(a)on(c,b)

clear(b)clear(c)ontable(a)ontable(b)on(c,a)

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

LabIA 2003

29

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

30

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

31

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

32

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

33

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

34

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

35

Ingredientes de Planejamento

ModelosLinguagensAlgoritmos

LabIA 2003

36

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

37

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

38

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

39

Busca no espaço de planos

stack(a,b)

stack(b,c)stack(a,b) stack(b,c)

stack(a,b)

unstack(c,a)

stack(b,c)

stack(a,b)

unstack(c,a)

stack(b,c)

stack(a,b)

LabIA 2003

40

Ordem parcial, vínculos e ameaças

a1

a2

a3

antecipar

a1

a2

a3

postergar

a1

a3

a2

ameaça

LabIA 2003

41

Ordem parcial, vínculos e ameaçasa0

clear(b) clear(c) ontable(a) ontable(b) on(c,a)

a

on(a,b) on(b,c)

S = {a0, a}O = {a0a}L = {}

on(b,c) clear(c) ontable(b)

clear(b) clear(c) ontable(b)stack(b,c)

clear(b) ontable(a) on(a,b)

clear(a) clear(b) ontable(a)stack(a,b)

S = {stack(a,b), a0, a}O = {a0stack(a,b)a, a0a}L = {stack(a,b)on(a,b)@a}

S = {stack(b,c), stack(a,b), a0, a}O = {a0stack(b,c)a, a0stack(a,b)a, a0a}L = {stack(b,c)on(b,c)@a, stack(a,b)on(a,b)@a}

S = {stack(b,c), stack(a,b), a0, a}O = {a0stack(b,c)a, a0stack(a,b)a, a0a}L = {a0clear(b)@stack(b,c), stack(b,c)on(b,c)@a, stack(a,b)on(a,b)@a}

S = {stack(b,c), stack(a,b), a0, a}O = {stack(b,c)stack(a,b) , a0stack(b,c)a, a0stack(a,b)a, a0a}L = {a0clear(b)@stack(b,c), stack(b,c)on(b,c)@a, stack(a,b)on(a,b)@a}

LabIA 2003

42

Algoritmo POP

function POP(initial, goal, operators) returns planplan Make-Minimal-Plan(initial, goal)loop do

if Solution? (plan) then return planSneed , c Select-Subgoal(plan)

Choose-Operator(plan, operators, Sneed, c)

Resolve-Threats(plan) endfunction 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

43

POP algorithm (cont.)

procedure Chose-Operator(plan,operators, Sneed , c ) choose a step Sadd from operators or Steps(plan) that has c as an effectif there is no such step then failadd 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

44

POP algorithm (cont.)

procedure Resolve-Threats(plan)for each Sthreat that threatens a link Si

c Sj in Links(plan) dochoose either

Demotion: Add Sthreat < Si to Orderings(plan)

Promotion: Add Si < Sthreat to Orderings(plan)

if not consistent(plan) then failend

POP é correto, completo e sistemático (busca sem repetição)

LabIA 2003

45

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

46

Grafo de Planejamento

• Planning Graph [Blum&Furst 1997]– expansão do grafo

0 i-1 i i+1

proposições proposiçõesações

LabIA 2003

47

Grafo de Planejamento

• Grafo de Planejamento– Relações de Mutex

Efeitos Inconsistentes

Interferência Necessidadesconflitantes

SuporteInconsistente

LabIA 2003

48

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

49

Grafo de Planejamento

LabIA 2003

50

SATPLAN

História: Kautz and Selman, 1992 • Inspiração nos avanços dos algoritmos de

satisfazibilidadeIdé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

51

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

52

SATPLAN: Jantar Surpresa

• Símbolos Proposicionais (schemas de fluentes)lixo(I)maos_limpas(I)silencio(I)jantar(I)presente(I)

Schemas de açõescozinhar( I )embrulhar( I )carregar_lixo( I )triturar_lixo( I )

LabIA 2003

53

SATPLAN: Jantar Surpresa• Símbolos Proposicionais1 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 )…32TOTAL: cnf 32 143

LabIA 2003

54

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

55

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

56

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

57

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

58

SATPLAN: Axiomas de Persistênciac [ 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

59

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

60

SATPLAN: plano totalmente ordenado• Apenas uma ação em cada instante

– Schemas de axiomas de não paralelismo de açõescozinhar( 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

61

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

62

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

63

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

64

Planejamento Heurístico: HSPFunçã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

)(pcs0

))((1min )( opPreccspOop

se p scaso contrário{

Gp

s pcsh )()(Heurística do HSP (não-admissível):