Estendendo o Planejamento
Clássico para Aplicações do
Mundo Real
Tempo, prazos e recursos
CIn-UFPE
1
Relembrando sobre POP-STRIPS
 Diferenças principais entre busca e planejamento?
•
•
•
•
Tipo de problema
Representação de estados e ações
Planos gerados
Processo de geração do plano
 Vantagens de planejamento de POP-STRIPS?
• Flexibilidade, expressividade,...
• Redução de complexidade (STRIPS, forma de planejar,...)
 Limitações
• Ambientes acessíveis, deterministas, estáticos...
• E várias outras: quais?
CIn-UFPE
2
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)
 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
3
Planejando com Tempo, Prazos e
Recursos
CIn-UFPE
4
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
5
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),
Effect: EngineIn(c)  Duration(d))
• Action (AddWheels(w,c),
Precond: Wheels(e,c,d)  Chassis(c)^ EngineIn(c)
Effect: WheelsOn(c)  Duration(d))
• Action (Inspect(c),
Precond: EngineIn(c)  WheelsOn(c)  Chassis(c)
Effect: Done(c)  Duration(10))
CIn-UFPE
6
Tempo e Prazos
 Procedimento: “planejar antes e escalonar depois”
• Rodar POP-STRIPS normalmente e depois escalonar ações
(caminho mais rápido)
• 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
7
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
8
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. dinheiro
• 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)  (Money(g) > 100)
Effect: EngineIn(c)  Duration(d)  Money(g-100))
CIn-UFPE
10
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
11
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)
EFFECT: EngineIn(c)  Duration(d)
RESOURCE: EngineHoist(1) )
Action (AddWheels(w, c),
PRECOND: Wheels(w, c, d)  Chassis(c)  EngineIn(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
12
Exemplo: Montagem de Dois Carros
EngineHoist(1)
AddEngine 1
AddEngine 2
AddWheels 1
WheelStations(1)
AddWhls 2
Inspect 1
Inspectors(2)
Inspect 2
0
30
60
70
90
105
115
Recursos reusáveis
 Encontrar o melhor escalonamento que obedece as
restrições de recursos é um problema NP-hard
 Heurística mais usada: Minimum Slack Algorithm
(greedy)
1. A cada interação: identifica as ações não escalonadas
cujos predecessores já foram todos escalonados e para as
quais existem recursos disponíveis
2. Escalona a que começo o mais cedo possível (earliest
start)...
3. Atualiza ES e LS da ação, e recomeça
CIn-UFPE
14