Planejamento Hierárquico
e Planejamento em Jogos
Sergio Queiroz
[email protected]
Planejamento: Até agora...
• Um plano consiste em uma sequência de
ações atômicas
• Adequado para tarefas complexas?
– Exemplo: planejamento de duas semanas de férias
em Porto de Galinhas
Férias em Porto de Galinhas
• Planejamento em nível atômico
– Ações são ativações de músculos do corpo
– Há cerca de 103 músculos no corpo (conta-se às
vezes 639, mas há músculos com subunidades)
– Há ativação pode ser feita por volta de 10 vezes
por segundo
– Estando acordados 16 horas por dia durante 15
dias teremos:
• 15 x 16 x 60 x 60 x 10 x 103 x 2 = 1,728 x 1010 possíveis
planos do que fazer na viagem...
Férias em Porto de Galinhas
• Não parece que o cérebro planeja assim...
• Aparentemente planejamos em níveis de
abstração mais altos
– No primeiro dia, pela manhã, vou até as piscinas
naturais...
• Veja que ir até as piscinas naturais pode ser
decomposta em uma sequência de ações
– Vestir a roupa de banho, passar protetor solar...
Férias em Porto de Galinhas
• Ações podem permanecer em nível abstrato
até a sua execução
– Não preciso decidir de imediato de vou andando
ou se vou pegar uma jangada, quando chegar na
praia eu decido...
• Ideia subjacente fundamental:
– DECOMPOSIÇÃO HIERÁRQUICA
Decomposição Hierárquica
• Decomposição hierárquica é uma idéia que permeia quase todas as
tentativas de gerenciar a complexidade. Por exemplo, software
complexo é criado a partir de uma hierarquia de sub-rotinas ou classes
de objetos; exércitos operam como uma hierarquia de unidades;
governos e corporações têm hierarquias de departamentos, subsidiárias
e filiais. O principal benefício da estrutura hierárquica é que, em cada
nível da hierarquia, uma tarefa computacional, missão militar, ou função
administrativa é reduzida a um pequeno número de atividades do
próximo nível abaixo, de modo que o custo computacional de encontrar
a maneira correta de organizar essas atividades para o problema atual é
pequena. Métodos não hierárquicos, por outro lado, reduzem a tarefa a
um grande número de ações individuais; para problemas de grande
escala, isso é completamente impraticável.
(AIMA, 3ª. Ed, Seção 11.2)
Planejamento Hierárquico
• Área de origem: Hierarchical Task Networks
(HTN)
• Conceitos
– Ações primitivas: como no planejamento clássico
– Ação de alto nível (HLA – high level action)
• Possui um ou mais “refinamentos”
– Refinamento
• Sequência de ações, cada uma das quais pode ser uma
ação primitiva ou uma HLA.
Planejamento Hierárquico
• Conceitos
– Implementação de uma HLA
• Refinamento que possui apenas ações primitivas
– Plano de alto nível (High-Level Plan)
• Uma sequência ações (com pelo menos uma HLA)
– Implementação de um plano de alto nível
• Concatenação das implementações de cada ação que o
compõe em sequência
– Um plano de alto nível alcança o objetivo a partir de
um determinado estado se pelo menos uma de suas
implementações alcança o objetivo a partir deste
estado
Biblioteca de Planos
• Uma ideia fundamental é o ganho de
eficiência pelo reuso de planos previamente
construídos
– A partir de experiências passadas...
– É necessário ter poder de generalização
• Passar protetor solar antes de ir à praia, independente
de qual seja o nome da praia...
Planejamento em Jogos
Slides selecionados de “Game Applications of HTN
Planning with State Variables, Dana Nau, Dept. of
Computer Science, and
Institute for Systems Research
University of Maryland
Pyhop - nomemclatura
Pyhop - nomemclatura
Pyhop - nomemclatura