INF 1771 – Inteligência Artificial
Aula 12 – Hierarchical Task Network (HTN)
Edirlei Soares de Lima
<elima@inf.puc-rio.br>
Planejamento Hierárquico
Hierarchical Task Network (HTN) Planning
Planejamento que busca refinar um plano com a
decomposição hierárquica de operadores abstratos.
Em planejamento HTN, o plano inicial que descreve o
problema, é visto como uma descrição de alto nível do
que deve ser feito.
Faz uma busca no espaço de redes de tarefas através
das diferentes decomposições de ações compostas.
Ações compostas representam sub-metas de alto nível.
Ações primitivas representam ações.
Exemplo
BuildHouse
Decomposes to
Get
Permit
land
Start
house
Pay
Builder
Finish
Construction
Hire
Builder
money
Decomposes to
Build
Roof
Build
Foundation
Build
Frame
Build
Interior
Build
Walls
Planejamento Hierárquico
Plan library:
Contém várias decomposições de ações abstratas
em menos abstratas ou mesmo planos inteiros pré-
concebidos.
Cada ação abstrata tem pré-condições e efeitos
que são comuns a todas as instanciações dela.
As decomposições podem ser expressadas da seguinte
maneira Decompose(a, d) - uma ação a um pode
ser decomposta em plano d.
Planejamento Hierárquico
Planejamento hierárquico híbrido
Na prática, se mistura operadores de decomposição HTN
com outros operadores do planejamento de ordem
parcial.
Decompose(Contruction,
Plan(STEPS:{S1: Build(Foundation),S2:Build(Frame),
S3: Build(Roof), S4:Build(Walls),
S5: Build(Interior)}
Orderings:{S1<S2<S3<S5, S2<S4<S5},
Bindings:{},
Foundation
S2, S2 Frame S3, S2 Frame S4,
S5}))
Links:{S1
S3
Roof
Walls
S5, S4
Planejamento Hierárquico
Algoritmo:
Constrói-se um plano de ordem parcial inicial no maior
nível de abstração.
Recursivamente decompõem-se ações abstratas até o
plano de ordem parcial final conter apenas operadores
primitivos (que podem ser executados pelo agente).
Resolve-se ameaças e verifica-se a consistência
global do plano de ordem parcial final.