Capítulo 11 Planejamento em Rede Hierárquica de Tarefas

1José de J. Pérez-Alcázar. Adaptado de Lectures Slides of Automated Planning: theory and practice (http://www.laas.fr/planning/). Licensed under the Creative Commons License: http://creativecommons.org/licenses/by-nc-sa/2.0/0/

Capítulo 11 Planejamento em Rede Hierárquica de

Tarefas

Planejamento em Inteligência Artificial

José de Jesús Pérez-Alcázar

MAC 5788 - IME/USPsegundo semestre de 2005


Motivação Nós podemos já ter uma idéia de como solucionar problemas em um

domínio de planejamento Exemplo: viagem para um destino longe:

Planejador independente do domínio:

» várias combinações de veículos e rotas Ser humano com experiência: usa um pequeno número de “receitas”

e.g., voar:1. comprar passagem do aeroporto local ao aeroporto remoto

2. viajar ao aeroporto local

3. voar para o aeroporto remoto

4. viajar ao destino final

Como facilitar o uso de tais receitas aos sistemas de planejamento?


Duas Abordagens Regras de controle (capítulo 10):

Escrever regras que eliminem (prune) toda ação que não se ajuste à receita

Planejamento em Rede Hierárquica de Tarefas (HTN) : Descreva as ações e sub-tarefas que se ajustam à receita


Planejamento HTN

método

travel(x,y)

get-ticket (a(x), a(y))

travel (x, a(x)) fly (a(x), a(y))

travel (a(y),y)

air-travel(x,y)

get-taxi ride-taxi (x,y) pay-driver

taxi-travel(x,y)

travel(UMD, LAAS)get-ticket(BWI, Toulouse)

go to Orbitzfind-

flights(BWI,Toulouse)buy-

ticket(BWI,Toulouse)travel(UMD, BWI)

get-taxiride-taxi(UMD, BWI)pay-driver

fly(BWI, Toulouse)travel(Toulouse, LAAS)

get-taxiride-taxi(Toulouse, LAAS)pay-driver

tarefa

Um tipo de problema de redução Decompor tarefas em subtarefas Manipular restrições (e.g., um taxi não é

bom para distâncias longas) Resolver interações (e.g., tomar um taxi

o bastante cedo para pegar o avião) Se necessário, retrocesso e tentar outra

decomposição


Planejamento HTN Planejadores HTN podem ser de domínio especifico

e.g., veja Capítulos 20 (robôtica) e 23 (bridge) Ou eles podem ser

domínio configuráveis Motor de planejamento

independente dodomínio

Descrição do domínio » métodos,

operadores Descrição do Problema

» descrição do domínio,estado inicial,rede de tarefas inicial


Rede de Tarefas Simples (STN) de Planejamento

Um caso especial de planejamento HTN Estados e operadores

O mesmo que no planejamento clássico Tarefa: uma expressão da forma t(u1,…,un)

t é um símbolo tarefa, e cada ui é um termo

Dois tipos de símbolos tarefa (e tarefas):

» primitivas: tarefas que nós conhecemos como executar diretamente

• símbolo tarefa é um nome de operador

» Não primitivas: tarefas que devem ser decompostas em sub tarefas

• usa métodos (próxima transparência)


Métodos Método totalmente ordenado : una 4-tuple

m = (nome(m), tarefa(m), precond(m), subtarefas(m)) nome(m): uma expressão da forma n(x1,…,xn)

» x1,…,xn são parâmetros – símbolos variáveis

tarefa(m): uma tarefa não primitiva precond(m): pré-condições (literais) subtarefas(m): uma seqüência

de tarefas t1, …, tk

air-travel(x,y)

tarefa: travel(x,y)

precond: long-distance(x,y)

subtarefas: buy-ticket(a(x),b(x)), travel(x,a(x)), fly(a(x),b(x)),

travel(b(x),y)

travel(x,y)

buy-ticket (a(x), a(y)) travel (x, a(x)) fly (a(x), a(y)) travel (a(y), y)

long-distance(x,y)

air-travel(x,y)


Método parcialmente ordenado : una 4-tupla m = (nome(m), tarefa(m), precond(m), subtarefas(m))

nome(m): uma expressão da forma n(x1,…,xn)


tarefa(m): uma tarefa não primitiva precond(m): pré-condições (literais) subtarefas(m): um conjunto parcialmente

ordenada de tarefas {t1, …, tk}

air-travel(x,y)

tarefa: travel(x,y)

precond: long-distance(x,y)

rede: u1=buy-ticket(a(x),b(x)), u2= travel(x,a(x)), u3= fly(a(x),b(x))

u4= travel(b(x),y), {(u1,u3), (u2,u3), (u3 ,u3)}

travel(x,y)

buy-ticket (a(x), a(y)) travel (x, a(x)) fly (a(x), a(y)) travel (a(y), y)

long-distance(x,y)

air-travel(x,y)

Métodos


Domínios, Problemas, Soluções domínio de planejamento STN: métodos, operadores problema de planejamento STN: métodos, operadores, estado

inicial, lista de tarefas domínio e problema de planejamento STN de ordem total:

Mesmo que acima exceto quetodos os métodos são totalmenteordenados

Solução: qualquer plano executável que pode ser gerado pela aplicação recursiva métodos para

tarefas não primitivas operadores para

tarefas primitivas

nonprimitive task

precond

method instance

s0 precond effects precond effectss1 s2

primitive taskprimitive task

operator instance operator instance


Exemplo Suponhamos que desejamos mover três pilhas de contenedores de

forma que preserve a ordem dos contenedores


Exemplo (continuação)

Uma forma mover cada pilha:

primeiro movo oscontenedoresde p para uma pilha

intermediariar

Então os

movemos de r para q


Formulação de Ordem Parcial


Formulação deOrdem Total


Solução de Problemas de Planejamento STN de ordem total

state s; task list T=( t1 ,t2,…)

action a

state (s,a) ; task list T=(t2, …)

task list T=( u1,…,uk ,t2,…)

task list T=( t1 ,t2,…)

method instance m


Expressividade Relativa do Planejamento Clássico

Qualquer problema de planejamento clássico pode ser traduzido num problema de planejamento ordenado de tarefas em tempo polinomial

Várias formas de fazer isto. Uma é aproximadamente como segue: Para cada meta ou pré-condição e, criar uma tarefa te

Para cada operador o e efeito e, criar um método mo,e

» Tarefa: te

» Subtarefas: tc1, tc2, …, tcn, o, onde c1, c2, …, cn sâo as pré-condições de o

» Restrições de ordenação Parcial: cada tci precede o

Existem problemas de planejamento em HTN que não podem ser traduzidos a problemas de planejamento clássico.

Exemplo na próxima página


Dois métodos: Sem argumentos Sem precondições

Dois operadores, a e b De novo, sem argumentos e sem pré-condições

Estado inicial é vazio, tarefa inicial é t Conjunto de soluções é {anbn | n > 0} Nenhum problema de planejamento clássico tem este conjunto de

soluções O sistema de transição estados é um autômato de estados finitos Nenhum autômato de estados finitos pode reconhecer {anbn | n >

0}

method1

bta

t

method2

ba

t

Exemplo


Comparação com buscaprogressiva e regressiva

No planejamento em espaço de estados, deve ser escolhido entre fazer uma busca progressiva ou regressiva

No planejamento HTN, há duas alternativas de direção: progressiva ou regressiva acima ou abaixo

TFD vaiabaixo eprogressiva

s0 s1 s2 …

task tm ……

task tn

op1 op2 opiSi–1

task t0

s0 s1 s2 … …op1 op2 opiSi–1


Comparação com buscaprogressiva e regressiva

Como a busca regressiva,TFD é dirigido pela meta Metas

correspondema tarefas

Como na busca progressiva, ele gera açõesna mesma ordem na qual elas serão executadas

Sempre que nós desejamos planejar a próxima tarefa Nós temos já planejado todo o que está antes dela Assim, nós sabemos o estado atual do mundo

s0 s1 s2 …

task tm …

…

task tn

op1 op2 opiSi–1

task t0


Us: East declarer, West dummyOpponents: defenders, South & NorthContract: East – 3NTOn lead: West at trick 3 East: KJ74

West: A2Out: QT98653

Incrementando a Expressividade ainda mais Conhecendo o estado atual facilita fazer coisas que seria difícil de

outra forma Estados podem ser estruturas de dados arbitrários

Pré-condições e efeitos podem incluir

» inferências lógicas (e.g., cláusulas de Horn)

» Cálculos numéricos complexos

» interações com outros pacotes de software e.g., SHOP:

http://www.cs.umd.edu/projects/shop


Exemplo

domínio simples do problema de planejamento de viagens Ir de uma localização a outra formulação de variáveis de Estado

(a,x,y)


Precond: distance(home,park) ≤ 2 Precond: cash(me) ≥ 1.50 + 0.50*distance(home,park)

Initial task: travel(me,home,park)

Precondition succeeds

travel-by-foot travel-by-taxi

Precondition failsDecomposition into subtasks

home park

Problema de Planning:I am at home, I have $20,I want to go to a park 8 miles away

s1 = {location(me)=home, location(taxi)=home, cash(me)=20, distance(home,park)=8}

Initial state

s0 = {location(me)=home, cash(me)=20, distance(home,park)=8}

call-taxi(me,home) ride(me,home,park) pay-driver(me,home,park)

Precond: …Effects: …



s2 = {location(me)=park, location(taxi)=park, cash(me)=20, distance(home,park)=8

s3 = {location(me)=park, location(taxi)=park, cash(me)=14.50, distance(home,park)=8}

Final state

s1 s2 s3 s0


Não pode misturar sub-tarefas de diferentes tarefas

Algumas vezes isto pode fazer coisas erradas

Necessário métodos que raciocinem globalmente no lugar de localmente

walk(a,b)pickup(p)walk(b,a)

get(p) get(q)

get-both(p,q)

goto(b)

pickup(p) pickup(q)

get-both(p,q)

Limitações do Planejamento com Tarefas Ordenadas

pickup-both(p,q)

walk(a,b)pickup(q)walk(b,a)

walk(a,b)

goto(a)

walk(b,a)


Generalizar os Métodos

Generalizar métodos para permitir que as sub-tarefas sejam parcialmente ordenadas

Conseqüência: planos podem misturar sub-tarefas de diferentes tarefas

Isto faz o algoritmo de planejamento mais complicado

walk(a,b) pickup(p)

get(p)

stay-at(b) pickup(q)

get(q)

get-both(p,q)

walk(b,a) stay-at(a)


Exemplo


Exemplo


Exemplo


π={a1 …, ak, a }; w’={t2,t3 …}

w={ t1 ,t2,…}

method instance m

w’={ u1,…,uk ,t2,…}

π={a1,…, ak}; w={ t1 ,t2, t3…}

operator instance a

Generaliza TFD para misturar sub-tarefas


Discussão PFD é correto e completo Pode ser generalizado da mesma forma que TFD

SHOP2: implementação de um algoritmo PFD-like + generalizações Ganhou um dos quatro majores prêmios na competição de

planejamento AIPS-2002 Freeware, open source Implementação disponível em

http://www.cs.umd.edu/projects/shop


Planejamento HTN Em STN, foram associados dois tipos de restrições a um método: de ordem e

pré-condições (as quais explicitamente não são validadas), elas são cumpridas na medida que se constroem redes de tarefas que as satisfazem.

Planejamento HTN é mesmo mais geral Pode ter restrições associadas com tarefas e métodos

» Coisas que devem ser verdade antes, durante, ou depois Alguns algoritmos usam elos causais e ameaças como esses em PSP

Redes de tarefas: par w = (U,C), onde U é um conjunto de nodos tarefa e C é um conjunto restrições.

Seja = <a1, ...,an> uma solução para w, U´U o conjunto de nodos tarefa em w, e A o conjunto de todas as ações em tal que na árvore de decomposição de , ai é um descendente de um nodo em U´. First(U´, ) = a1 e Last(U´, ) = an

Tipos de restrições: precedência, antes, depois e entre (between).


Planejamento HTN Restrição de precedência: expressão da forma , onde u e v são

nodos tarefas. Restrição before: generalização da noção de pré-condição em STN.

Uma restrição before(U´, l), onde U´ U é um conjunto de nodos tarefa e l é um literal. Ela diz que em qualquer solucao para P, o literal l deve ser verdadeiro no estado que ocorre antes de First(U´, ). Se tu = move(r2,l2,l3) entao a restricao before({u}, at(r2,l2))?

Restricao after. after(U´,l) diz que l deve ser verdade no estado que ocorre depois de Last(U´, ).

Restricao between. Between(U´, U´´, l) diz que l debe ser verdadeiro no estado depois de last(U´, ), antes de first(U´´, ), e todos os estados entre eles.

vu


Métodos HTN Um método HTN é um 4-tupla

m = (nome(m), tarefa(m), subtarefas(m), restrição(m)) nome(m): uma expressão da forma n(x1,…,xn)


tarefa(m): uma tarefa não primitiva (subtarefas(m), restrição(m)) : uma rede de tarefas.

Suponhamos que w = (U, C) é uma rede de tarefas, u U é um nodo tarefa, tu é a tarefa, m é uma instancia de um método, e tarefa(m) = tu m decompõe u em subtarefas(m´), produzindo a rede de tarefas:

(w,u,m) = ((U – {u}) subtarefas(m´), C´ restrição(m´))


Métodos HTN C´ é construido a partir de C.

Para toda restrição de precedência que contém u, troque-a com restrições de precedência que contém nodos de subtarefas(m´). Exemplo, se subtarefas(m´) = {u1,u2}, então troque pelas restrições e

Para toda restrição before, after, ou between, na qual há um conjunto de nodos U´ que contém u, troque U´ por (U´-{u}) subtarefas(m´). Exemplo, se subtarefas(m´)={u1,u2}, então troque a restrição before({u,v}, l) por before({u1,u2,v},l).

vu vu 1 vu 2


Exemplo


Exemplo


Problemas HTN e Soluções Semelhante a STN, mudam os métodos. Um domínio de planejamento HTN é um par

D = (O, M) Um problema de planejamento HTN é uma 4-tupla

P = (s0,w,O,M), s0 é o estado inicial, w é a rede de tarefas inicial, O conjunto de operadores, M conjunto de métodos HTN.

Agora, o que significa que um plano seja uma solução para P? Existem dois casos, dependendo de se w é primitivo ou não.


Problemas HTN e Soluções Se W = (U,C) é primitivo, então um plano = <a1, ..., ak> é uma solução para P,

se existir uma instância ground (U´,C´) de (U,C) e uma ordenação total <u1,...,uk> de todos os nodos de U tal que: As ações em são as relacionadas aos nodos u1, ...,uk. name(ai) = tui

O plano é executável no estado s0 A ordenação total satisfaz as restrições de precedência em C´. Para toda restrição before(U´,l) em C´, l é válido no estado si-1 que precede

imediatamente ai (ação associada ao primeiro nodo de U´). Para toda restrição after(U´,l) em C´, l é válido no estado sj, produzido pela

ação aj (ação associada ao último nodo de U´). Para toda restrição between(U´, U´´,l) em C´, l é válido em todo estado entre

ai e aj (ai associado a último nodo de U´ e aj associado ao primeiro nodo de U´´).

Se w é não primitivo (pelo menos uma tarefa não primitiva), então é uma solução para P, se existir uma seqüência de decomposição de tarefas para w que produz uma rede de tarefas w´ primitiva para qual é uma solução.


Procedimento de Planejamento

Função que pode fazermodificações arbitráriasPara uma rede de tarefas.Úteis para desenvolver cálculos específicos


Expressividade de TLPlan Comparada comSHOP e SHOP2

Potência expressiva equivalente Ambos são Turing-completo, porque ambos permitem símbolos

funcionais Ambos permitem procedimentos anexados, computações numéricas

Ambos conhecem o estado atual em cada passo do processo de planejamento,e usam isto para eliminar (prune) operadores

Ambos podem chamar sub-rotinas externas SHOP usa “eval” para chamar funções LISP Em TLPlan, um símbolo funcional pode corresponder a uma função

calculada Principal diferença

em SHOP e SHOP2, os métodos mencionam sobre o que pode ser feito» SHOP e SHOP2 não fazem algo a menos que um método o ordene

Regras de controle TLPlan falam sobre o que não pode ser feito» TLPlan tentará tudo o que as regras de controle não proibem.

Qual abordagem é mais conveniente depende do domínio do problema


Comparação Experimental Há vários anos, o grupo do Nau fez uma comparação de SHOP, TLPlan, e

Blackbox Blackbox é um planejador independente de domínio que usa uma

combinação de Graphplan e satisfatibilidade Um dois mais rápidos planejadores na competição de 1998

Domínio de teste: o domínio de logística Um problema de planejamento clássico

» Bem mais simples que o planejamento real de logística Cenário: uso de caminhões e aviões para o envio de pacotes Como uma versão simplificada do domínio DWR no qual contenedores não

podem ser empilhados sobre os outros Condições de teste

SHOP e TLPlan num Sun Ultra de 167-MHz com 64 MB de RAM Eles não conseguiram executar Blackbox na sua máquina Resultados publicados: Blackbox numa máquina mais rápida com 8 GB de

RAM


0

200

400

600

800

1000

1200

1400

1600

1800

1 5 9 13 17 21 25 29

CP

U t

ime

(se

c.)

Blackbox TLplan SHOP

Resultados do Domínio de Logística


Resultados do Domínio de Logística (continuação)

0.1

1

10

100

1000

10000

1 5 9 13 17 21 25 29


10

30

5070

90

110

130

1 5 9 13 17 21 25 29


Average Blackbox TLPlan SHOPCPU time 327.1 2.9 1.1

Average no. Blackbox TLPlan SHOPof actions 82.5 54.5 51.9

Mesmo grafo de antes, mas sobre uma escala logarítmica

Número de ações nos planos


Resumo TLPlan e SHOP gastam quantidades de tempo similar

Nesta experiência, SHOP foi ligeiramente mais rápido, mas em outras TLPlan pode ser mais rápido

Blackbox tomou ao redor de 1000 vezes mais tempoe precisou ao redor de 100 vezes mais memória

Razões do porque: Entradas do SHOP incluem métodos e axiomas específicos do domínio Entradas do TLPlan incluem regras de controle específicos do domínio

» Isto lhes facilitou achar soluções perto do ótimo em tempo e espaço polinomial

Blackbox é um planejador totalmente automatizado

» Nenhum conhecimento específico do domínio

» Busca de teste-e-erro, tempo e espaço exponencial


Planejadorescom domínio configurável comparados a

Planejadores Clássicos Desvantagem: escrever uma base de conhecimento pode ser

mais complicado que apenas escrever operadores clássicos Vantagem: pode codificar “receitas” como coleções de

métodos e operadores Expressar coisas que não podem ser expressadas no

planejamento clássico Especificar formas padrão de resolver problemas

» De outra forma, o sistema de planejamento teria que derivar estes sempre de “primeiros princípios,” cada vez que resolve um problema

» Pode melhorar o planejamento em várias ordenes de magnitude (e.g., tempo polinomial versus tempo exponencial)


Exemplo da Competição AIPS-2002 O domínio de satélites

Planejamento e escalonamento de tarefas de observação entre múltiplos satélites Cada satélite equipado de forma ligeiramente diferente

Várias versões diferentes. Serão apresentados resultados para o seguinte: Tempo simples:

» uso concorrente de diferentes satélites» dados pode ser adquiridos mais rapidamente se eles são usados eficientemente

Numérico: » custos de combustível para satélites to slew between targets; quantidades finitas

de combustível disponível.» dados ocupam espaço numa memória de capacidade finita» Planos tentam adquirir todos os dados necessários a um custo mínimo de

combustível. Hard Numeric:

» Nenhuma meta lógica mesmo – thus even the null plan is a solution» Planos que adquirem mais dados são melhores – assim o plano nulo não tem valor» Nenhum dos planejadores clássicos poderiam tratar isto








w={ t1 ,t2,…}

method instance m

w’={ u1,…,uk ,t2,…}

(w, u, m, ) tem uma definição complicada no livro. Isto é o que significa: Nós selecionamos t1 porque é possível que t1 vem primeiro Nós estamos planejando para t1 sob a suposição que ele virá

primeiro Insira restrições de ordem para ter certeza de que ele vira

primeiro As mesmas restrições também devem aplicar a todas as sub-

tarefas de t1

Generaliza TFD para misturar sub-tarefas

Documents

Capítulo 11 Planejamento em Rede Hierárquica de Tarefas