Planejamento e Agendamento Temporal

O planejamento e agendamento temporal estendem o planejamento para lidar com ações que levam tempo, podem ser executadas concomitantemente e consomem recursos limitados, produzindo planos que especificam não apenas o que fazer, mas também quando fazê-lo.

Definition

O planejamento temporal produz um plano no qual as ações têm durações e podem se sobrepor, sujeitas a restrições temporais e de recursos; o agendamento atribui tempos de início (e recursos) a um conjunto de atividades para que todas as restrições, como ordenação, prazos e capacidades, sejam satisfeitas.

Scope

Este tópico abrange o planejamento e agendamento com tempo e recursos explícitos: ações durativas, concorrência e restrições temporais, a representação e solução de redes de restrições temporais (como o problema temporal simples) e a álgebra de intervalos de Allen, e a integração do planejamento com o agendamento de atividades com recursos restritos. Ele aborda como a viabilidade temporal e de recursos é considerada juntamente com a seleção de ações. O planejamento clássico puro, livre de recursos, é tratado em tópicos relacionados.

Core questions

• Como as ações durativas e suas condições de início e fim são representadas?
• Como as restrições temporais entre eventos são modeladas e verificadas quanto à consistência?
• Como os recursos limitados são alocados entre atividades concorrentes?
• Como o planejamento (decidir quais ações) e o agendamento (decidir quando) são combinados ou separados?

Key concepts

• ações durativas
• concorrência e sobreposição
• restrições temporais
• problema temporal simples
• álgebra de intervalos de Allen
• restrições de recursos
• agendamento
• prazos e makespan

Key theories

Redes de restrições temporais

Restrições temporais quantitativas entre pontos no tempo podem ser representadas como uma rede cuja consistência e limites mais apertados são calculados eficientemente para o problema temporal simples, fornecendo a espinha dorsal do raciocínio temporal de muitos planejadores e agendadores.

Álgebra de intervalos para tempo qualitativo

A álgebra de intervalos de Allen captura as possíveis relações qualitativas entre intervalos de tempo (antes, durante, sobrepõe, e assim por diante) e apoia o raciocínio sobre o conhecimento temporal quando os tempos exatos são desconhecidos.

Integração do planejamento com o agendamento

Problemas realistas exigem a escolha de ações e a atribuição de tempos e recursos a elas em conjunto; a teoria do planejamento automatizado trata as ações durativas, a concorrência e as restrições de recursos como extensões que acoplam a seleção de ações com o agendamento baseado em restrições.

Clinical relevance

O planejamento e agendamento temporal são essenciais em operações de naves espaciais e rovers, agendamento de manufatura e projetos, agendamento de transporte e tripulação, e em qualquer cenário onde atividades cronometradas, concorrentes e com recursos limitados devem ser coordenadas; tais sistemas têm operações planejadas para missões espaciais reais.

History

O raciocínio temporal qualitativo foi formalizado pela álgebra de intervalos de Allen (1983), e as redes de restrições temporais quantitativas por Dechter, Meiri e Pearl (1991). Essas bases, juntamente com os modelos de ações durativas adicionados ao PDDL no início dos anos 2000, possibilitaram planejadores temporais usados em aplicações como o controle autônomo de naves espaciais.

Key figures

• James F. Allen
• Rina Dechter
• Judea Pearl
• Itay Meiri
• Nicola Muscettola

Seminal works

• dechter1991
• allen1983

Frequently asked questions

Qual a diferença entre planejamento e agendamento?

O planejamento decide quais ações tomar para atingir objetivos, enquanto o agendamento decide quando essas ações ocorrem e quais recursos elas utilizam, dadas as restrições de ordenação e capacidade. Muitos problemas reais exigem ambos, e o planejamento temporal integra a seleção de ações com o raciocínio de tempo e recursos.

O que é o problema temporal simples?

O problema temporal simples é uma rede de restrições temporais na qual cada restrição limita a diferença entre dois pontos no tempo por um intervalo. Sua consistência e os limites implícitos mais apertados podem ser calculados eficientemente, o que o torna um núcleo prático para o raciocínio temporal em planejadores e agendadores.