Estendendo o Planejamento
Clássico para Aplicações do
Mundo Real
Tempo, prazos e recursos
Planejamento hierárquico
CIn-UFPE
1
Além da sintaxe... outras limitações de
POP-STRIPS
 O tempo não é levado em conta
• Diz “o que”, mas não “quando” nem “por quanto
tempo”
 A limitação dos recursos não é considerada
• Não custa nada agir (ex: orçamento, pessoas)
 Planos não são hierárquicos
• Planejamento a um único nível de granularidade
 Pré-condições e efeitos são simples demais
• Os operadores são essencialmente proposicionais
– ex: sem quantificador universal nos efeitos, não se pode
dizer que os componentes da aeronave sobem com ela
CIn-UFPE
2
Planejando com Tempo, Prazos e
Recursos
CIn-UFPE
3
Tempo e Prazos
 Job Shop Scheduling
• Completar conjunto de tarefas (seqüência de ações)
• Cada ação tem uma duração e pode precisar de recursos
• Encontrar o escalonamento mais rápido para a execução
das tarefas, respeitando restrições de recursos
 Exemplo de Job Shop Problem
• 2 tarefas (jobs): montar dois carros C1 e C2
• Ações: colocar motor, colocar rodas, inspecionar
• Ordem: motor antes das rodas e inspecionar no final
 Como lidar com isto?
CIn-UFPE
4
Tempo e Prazos
 Acrescentar Duration(d) para ações em STRIPS
 Exemplo...
• Init (Chassis(C1)  Chassis (C2)  Engine(E1,C1,30) 
Engine(E2,C2,60)  Wheels(W1,C1,30)  Wheels(W2,C2,15))
• Goal (Done(C1)  Done(C2))
• Action (AddEngine(e,c),
Precond: Engine (e,c,d)  Chassis(c)  EngineIn(c),
Effect: EngineIn(c)  Duration(d))
• Action (AddWheels(w,c),
Precond: Wheels(e,c,d)  EngineIn(c)  Chassis(c)
Effect: WheelsOn(c)  Duration(d))
• Action (Inspect(c),
Precond: EngineIn(c)  WheelsOn(c)  Chassis(c)
Effect: Done(c)  Duration(10))
CIn-UFPE
5
Tempo e Prazos
 Procedimento: “planejar antes e escalonar depois”
• Rodar POP-STRIPS normalmente e depois escalonar ações
(caminho mais rápido) usando programação dinâmica
• Abordagem usada na prática, sobretudo porque o plano pode
ser fornecido por um especialista
 Solução Encontrada pelo POP “normal”
AddEngine 1
AddWheels 1
Inspect 1
30
30
10
Start
CIn-UFPE
Finish
AddEngine 2
AddWheels 2
Inspect 2
60
15
10
6
Tempo e Prazos
 Método do Caminho Crítico (CPM)
• Caminho Crítico: caminho cujo tempo total é maior
• Para cada ação, indicar
– Tempo Mais Cedo de Início (ES – Earliest Start)
– Tempo Mais Tarde de Início (LS – Latest Start)
• Ações no caminho crítico não podem sofrer nenhum atraso
• Ações fora desse caminho podem sofrer atrasos de tolerância
LS - ES
CIn-UFPE
7
Plano
[0,15]
AddEngine1
30
[30,45]
AddWheels1
30
[60,75]
Inspect1
10
[0,0]
Start
[85,85]
Finish
[0,0]
AddEngine2
60
[60,60]
AddWheels2
15
[75,75]
Inspect2
10
Caminho crítico
Escalonamento
AddWheels1
AddEngine1
Inspect1
Inspect2
AddEngine2
AddWheels2
t
0
10
20
30
40
50
60
70
80
Restrição de Recursos
 Problemas reais de escalonamento são ainda mais
complexos devido a restrições sobre recursos
• Consumable resources - ex. grana
• Reusable resources - ex. um único guindaste para
levantar o motor
 Como resolver?
 Solução para recursos consumíveis
• adicionar precondições e efeitos
• Action (AddEngine(e,c),
Precond: Engine (e,c,d)  Chassis(c)  EngineIn(c)
 (Money(g) > 100)
Effect: EngineIn(c)  Duration(d)  Money(g-100))
CIn-UFPE
9
Restrição de Recursos
 Solução para recurso reutilizável:
• Mais complicado porque a quantidade de recursos
permanece inalterada depois da ação!
• Incrementar representação do problema para incluir novo
campo
– “Resource: R(k)”, k unidades de R são necessárias
• Funciona tanto como
– uma pré-condição (não se pode fazer sem ele)
– um efeito temporário (indisponível pela duração da ação)
 Voltando ao exemplo...
• 1 guindaste, um macaco mecânico e 1 inspetor disponível
CIn-UFPE
10
Exemplo: Montagem de Dois Carros
Init (Chassis(C1)  Chassis(C2)  Engine(E1, C1, 30)  Engine(E2, C2, 60) 
Wheels(W1, C1, 30)  Wheels(W2, C2, 15)  EngineHoists(1) 
WheelStations(1)  Inspectors(2) )
Goal (Done(C1)  Done(C2)
Action (AddEngine(e, c, m),
PRECOND: Engine(e, c, d)  Chassis(c)   EngineIn(c)
EFFECT: EngineIn(c)  Duration(d)
RESOURCE: EngineHoist(1) )
Action (AddWheels(w, c),
PRECOND: Wheels(w, c, d)  Chassis(c)
EFFECT: WheelsOn(c)  Duration(d)
RESOURCE: WheelStations(1) )
Action (Inspect(c),
PRECOND: EngineIn(c)  WheelsOn(c)  Chassis(c)
EFFECT: Done(c)  Duration(10)
RESOURCE: Inspectors(1) )
CIn-UFPE
11
Exemplo: Montagem de Dois Carros
EngineHoist(1)
AddEngine 1
AddEngine 2
AddWheels 1
AddWhls 2
Inspect 1
Inspectors(2)
WheelStations(1)
Inspect 2
0
30
60
70
Complexidade: problema NP-hard
90
105
115
Planejamento Hierárquico
CIn-UFPE
13
Decomposição Hierárquica
 Benefício de uma estrutura hierárquica
• A cada nível a quantidade de tarefas é pequena
comparada com o todo
– Ex. planejamento militar e administrativo
 De fato...
• Instruções detalhadas provocam explosão combinatória
– Ex. “Avançar(1 m), Girar(40°), ...”
 Embora...
• instruções abstratas não são diretamente implementáveis
no mundo real.
– Ex. Go(Supermarket), Buy(Milk), Build(House)
CIn-UFPE
14
Planejamento Hierárquico
 Hierarchical Task Network (HTN) Planning
• Planejar refinando um plano inicial completo apenas com
decomposição hierárquica de operadores abstratos
 Operadores
• Primitivos: diretamente executáveis
• Abstratos: não primitivos
 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
CIn-UFPE
15
Exemplo de decomposição hierárquica
BuildHouse
Decomposes to
land
Get
Permit
Start
money
Construction
Hire
Builder
Pay
Builder
house
Decomposes to
Build
Foundation
Build
Frame
Build
Roof
Build
Walls
Build
Interior
Finish
Planejamento Hierárquico
 Planejamento hierárquico híbrido
• Na prática, se mistura operadores de decomposição
(HTN) com outros operadores padrão (POP)
 Como implementa?
 Estendendo STRIPS
• Decomposição de operadores abstratos
– c/ indicação de quem são ou não os operadores abstratos
 Redefinindo POP
• Como decompor operadores não primitivos
CIn-UFPE
17
Exemplo de Decompose(o,p)
 Operador Decompose()
Ex. 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:{},
Links:{S1 Foundation S2, S2 Frame S3, S2 Frame S4,
S3 Roof S5, S4 Walls S5}))
CIn-UFPE
18
Planejamento Hierárquico
 Algoritmo
• Construir POP inicial ao maior nível de abstração
• Recursivamente decompor ações abstratas até POP final
conter apenas de operadores primitivos (que podem ser
executados pelo agente)
• Resolver ameaças e verificar consistência global do POP
final e
 Obs
• Não há necessariamente uma estratégia de escolha entre
decompor um não primitivo ou resolver pré-condição
aberta
• O plano P é uma solução igual ao POP mas com teste
adicional para garantir que todo passo de P é primitivo
CIn-UFPE
19
Planejamento Hierárquico
 Decomposição d’ para a ação a’
• Igual a uma cirurgia de transplante: tudo tem de ficar
conectado!
• Pré-condições e efeitos adicionais podem aparecer com a
decomposição (ex. GetLoan)
• Obs.: Não há especificação de duração dos passos de d’
 Tarefa realizada em 3 fases...
CIn-UFPE
20
Planejamento Hierárquico
 Fase 1: Substituir a’ por d’
• Remover a’
– ex. BuildHouse
• Inserir cada passo de d’
• Transcrever restrições internas à d’
– ex. GetPermit antes Contruction
• Introduzir novos passos quando for o caso
– ex. GetLoan
• Ou, eventualmente, reutilizar um passo já existente
(chamado de compartilhamento)
– ex. GetLoan poderia ser compartilhado por BuildHouse e
MakeWine, para uma fazenda. Senão poderia até estar
dentro da decomposição
CIn-UFPE
21
Planejamento Hierárquico
Buy Land
Start
land
a’
BuildHouse
house
Decomposes to
Buy Land
Get Loan
Start
land
Finish
d’
Get
Permit
Hire
Builder
Construction
Pay
Builder
house
Finish
Balanço
 Fase 2: Transcrever as restrições de ordenamento
• Dado um passo qualquer B < a’ (ou B > a’), como ele fica
em relação à d’?
– solução 1: B antes (ou depois) de todos os passos de d’
=> muito restritivo, pois BuyLand não precisa vir antes de
HireBuilder
– solução 2: gravar as razões de um ordenamento de forma a
poder relaxá-lo onde ele não for necessário
 Fase 3: Ligações causais
• Se B p a’, troque ela por um conjunto de ligações para
todos os passo de d’ contendo a pré-condição p
– Ex.BuyLand
land Permit
land
BuildHouse, é substituído por BuyLand
• Idem para as ligações causais do tipo a’
CIn-UFPE
p
C
23
Balanço
 Vantagens de Sub-POPs independentes:
• espaço de busca reduzido
• conhecimento composicional
• uso e reuso de sub-POPs pré-planejados
 Observações
• Enquanto ações primitivas são pontuais, as não-primitivas
podem interagir no tempo e merecem atenção
CIn-UFPE
24
Algumas Aplicações
CIn-UFPE
25
Aplicações Industriais (Job Shop)
 Sistema Tosca na Hitachi
• planejamento mensal para 350 produtos diferentes, 35
máquinas de montagem, mais de 2000 operações
• menor engajamento (ex. classe de máquina a ser usada)
 Sistema Isis na Westinghouse
• milhares de lâminas de turbinas e várias máquinas de
montagem
• o tempo atribuído depende da prioridade do pedido
• menor engajamento, planejamento hierárquico
CIn-UFPE
26
Aplicações Industriais (Job Shop)
 Sistema Optimun-AIV
• Montagem, integração e verificação de aeronaves
• Gera planos, monitora execução (feita por seres
humanos) e replaneja rapidamente
• Melhor que Pesquisa Operacional para problemas
complexos pois pode replanejar automaticamente
• Implementado com O-Plan (Currie & Tate 91) que
estende POP-Strips (+ tempo, recursos e hierarquia)
CIn-UFPE
27