Desenvolvimento de Sistemas Baseados em Conhecimento Planejamento com Tempo, Prazos e Recursos Planejamento Hierárquico

Desenvolvimento de Sistemas Desenvolvimento de Sistemas Baseados em ConhecimentoBaseados em Conhecimento

Planejamento com Tempo, Prazos e RecursosPlanejamento Hierárquico

Relembrando STRIPSAlgoritmo

Conjunto de Operadores

Estado Atual

.

.

.

Op(ACTION: PutOn(b, x, y),PRECOND: On(b, x) ^ Clear(b) ^ Clear(y),EFFECT: On(b, y) ^ Clear(x) ^ On(b, x) ^ Clear(y))

On(A,Table)On(B,Table)On(C,Table)

Clear(A)Clear(B)Clear(C)

On(A,B)

On(B,C) On(C,Table)Clear(A)

On(A,Table)On(B,Table)

On(C,Table)

Clear(A)Clear(B)

Clear(C)

PutOn(B, Table, C)

PutOn(A, Table, B)

On(B,C) Clear(Table)On(A,B)

Relembrando POP

StartStart

FinishFinishAt(Home)At(Home)Have(Milk)Have(Milk) Have(Ban.)Have(Ban.)Have(Drill)Have(Drill)

Buy(Ban.)Buy(Ban.)At(SM)At(SM) Sells(SM,Ban.)Sells(SM,Ban.)

Buy(Milk)Buy(Milk)At(SM)At(SM) Sells(SM,Milk)Sells(SM,Milk)

Go(SM)Go(SM)At(HWS)At(HWS)

Go(HWS)Go(HWS)At(Home)At(Home)

Buy(Drill)Buy(Drill)At(HWS), Sells(HWS,Drill)At(HWS), Sells(HWS,Drill)

Go(Home)Go(Home)At(SM)At(SM)

Relembrando POP

Limitações POP-STRIPS

• O tempo não é levado em conta– Diz “o que”, mas não “quando” nem “por quanto tempo”– “O modelo de planejamento temporal deve ser baseado

numa abordagem de intervalo explicito, o qual permita a representação de referências temporais quantitativas e qualitativas, assim como relações entre eles”.

I

IfIi

a

Duração = If - Ii


• A limitação dos recursos não é considerada– Não custa nada agir (ex: orçamento, pessoas)

» Os recursos de uma brigada de incêndio, assim como a própria brigada, são limitados

– Plano de viagem X orçamento


• Pré-condições e efeitos são muito limitados– Os operadores são essencialmente proposicionais

» ex: sem quantificador universal nos efeitos, não se pode dizer que os componentes de uma esquadrilha atacam juntos

Attack(target)

Identified(target), available(esq)

p Plane(p) p esq Attack(p,target)


• Planos não são hierárquicos– Planejamento em um único nível de granularidade


-Operadores de baixo nível:- Mover- Girar- Zoom câmera- Identificar cadáveres

Tempo e Prazos

• Job Shop Scheduling– Completar conjunto de tarefas (jobs)– Cada tarefa é composto por uma 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?

Tempo e Prazos

• Acrescentar Duration(d) para ações em STRIPS• Exemplo...

– Init (Car(C1) Car(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) Car(c) EngineIn(c), Effect: EngineIn(c) Duration(d))

– Action (AddWheels(w,c), Precond: Wheels(w,c,d) Car(c)

Effect: WheelsOn(c) Duration(d))– Action (Inspect(c),

Precond: EngineIn(c) WheelsOn(c) Car(c)Effect: Done(c) Duration(10))

Tempo e Prazos

• Procedimento: “planejar antes e escalonar depois”– Rodar POP 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”

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

Tempo e Prazos

[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

Caminho crítico

Restrição de Recursos

• Problemas reais de escalonamento são ainda mais complexos devido a restrições sobre recursos– Recursos Consumíveis (Consumable resources) - ex. dinheiro – Recursos Reutilizáveis (Reusable resources) - ex. um único guindaste

para levantar o motor

t

Full

Qf

t

2

1

extinguish(1, F1, t2)



QWReusable resource Consumable resource

extinguish(1, F1, t2)consume

extinguish(1, F2, t5)consume

producerefill(1,qx, tx)

qx


• Solução para recursos consumíveis– adicionar precondições e efeitos– Action (AddEngine(e,c),

Precond: Engine (e,c,d) Car(c) EngineIn(c) (Money(g) > 100)

Effect: EngineIn(c) Duration(d) Money(g-100))


• 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

Exemplo: Montagem de Dois Carros

Init (Car(C1) Car(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) Car(c) EngineIn(c)EFFECT: EngineIn(c) Duration(d) RESOURCE: EngineHoist(1) )

Action (AddWheels(w, c),PRECOND: Wheels(w, c, d) Car(c)EFFECT: WheelsOn(c) Duration(d) RESOURCE: WheelStations(1) )

Action (Inspect(c),PRECOND: EngineIn(c) WheelsOn(c) Car(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

Recursos Reusáveis

• 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...2. Escalona a com menor brecha/folga (slack)3. Atualiza ES e LS das ações, e recomeça

Slack = LS - ES LSES

LSES

Slack

textra

Slack’ = Slack - textra

Planejamento Hierárquico

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


• 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



• Planejamento hierárquico híbrido – Na prática, se mistura operadores de decomposição (HTN) com

outros operadores padrão (POP)

• Como implementa?• Estendendo/Redefinindo POP

– Decomposição de operadores abstratos» c/ indicação de quem são ou não os operadores abstratos

– Como decompor operadores não primitivos


• Planejamento hierárquico híbrido – Na prática, se mistura operadores de decomposição (HTN) com

outros operadores padrão (POP)

• Como implementa?• Estendendo/Redefinindo POP

– Decomposição de operadores abstratos» c/ indicação de quem são ou não os operadores abstratos

– Como decompor operadores não primitivos


• Operador Decompose( )


• Algoritmo– Construir POP inicial ao maior nível de abstração– Recursivamente decompor ações abstratas até POP final conter

apenas operadores primitivos (que podem ser executados pelo agente)

– Resolver ameaças e verificar consistência global do POP final

• Obs– Deve-se garantir que todo passo de um plano final P é primitivo

• Decomposição d’ para a ação a’ – Tarefa realizada em 3 fases...



• 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


• 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: menor engajamento

• 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 BuildHouse, é substituído por BuyLand land Permit

– Idem para as ligações causais do tipo a’ p C


• Vantagens de Sub-POPs independentes:– espaço de busca reduzido– conhecimento composicional – uso e reuso de sub-POPs pré-planejado

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

Aplicações Espaciais

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

Documents

Desenvolvimento de Sistemas Baseados em Conhecimento Planejamento com Tempo, Prazos e Recursos Planejamento Hierárquico