CIn-UFPE1

Estendendo o PlanejamentoClássico para Aplicações do

Mundo Real

Tempo, prazos e recursos

CIn-UFPE2

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-UFPE3

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-UFPE4

Planejando com Tempo, Prazos e Recursos

CIn-UFPE5

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-UFPE6

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-UFPE7

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

30

AddEngine 2

60

AddWheels 2

15

AddWheels 1

30

Inspect 1

10

Inspect 2

10

FinishStart

CIn-UFPE8

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

Caminho crítico

[0,0]Start

[0,15]AddEngine1

30

[0,0]AddEngine2

60

[30,45]AddWheels1

30

[60,60]AddWheels2

15

[60,75]Inspect1

10

[75,75]Inspect2

10

[85,85]Finish

Plano

0 10 20 30 40 50 60 70 80t

AddEngine1

Inspect2AddEngine2

AddWheels1

Inspect1

AddWheels2

Escalonamento

CIn-UFPE10

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-UFPE11

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-UFPE12

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) )

Exemplo: Montagem de Dois Carros

EngineHoist(1)

WheelStations(1)

Inspectors(2)

30 60 105 1150

AddEngine 1 AddEngine 2

AddWheels 1 AddWhls 2

Inspect 2

Inspect 1

9070

CIn-UFPE14

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