Temporal Planning and Scheduling
Temporal planning and scheduling extend planning to handle actions that take time, may run concurrently, and consume limited resources, producing plans that specify not only what to do but when to do it.
Definition
Temporal planning produces a plan in which actions have durations and may overlap, subject to temporal and resource constraints; scheduling assigns start times (and resources) to a set of activities so that all constraints, such as ordering, deadlines, and capacities, are satisfied.
Scope
This topic covers planning and scheduling with explicit time and resources: durative actions, concurrency and temporal constraints, the representation and solution of temporal constraint networks (such as the simple temporal problem) and Allen's interval algebra, and the integration of planning with scheduling of resource-constrained activities. It addresses how time and resource feasibility are reasoned about alongside action selection. Pure resource-free classical planning is treated in the related topics.
Core questions
- How are durative actions and their start and end conditions represented?
- How are temporal constraints between events modeled and checked for consistency?
- How are limited resources allocated among concurrent activities?
- How are planning (deciding which actions) and scheduling (deciding when) combined or separated?
Key concepts
- durative actions
- concurrency and overlap
- temporal constraints
- simple temporal problem
- Allen's interval algebra
- resource constraints
- scheduling
- deadlines and makespan
Key theories
- Temporal constraint networks
- Quantitative temporal constraints between time points can be represented as a network whose consistency and tightest bounds are computed efficiently for the simple temporal problem, providing the temporal-reasoning backbone of many planners and schedulers.
- Interval algebra for qualitative time
- Allen's interval algebra captures the possible qualitative relations between time intervals (before, during, overlaps, and so on) and supports reasoning about temporal knowledge when exact times are unknown.
- Integrating planning with scheduling
- Realistic problems require choosing actions and assigning them times and resources together; the theory of automated planning treats durative actions, concurrency, and resource constraints as extensions that couple action selection with constraint-based scheduling.
Clinical relevance
Temporal planning and scheduling are essential in spacecraft and rover operations, manufacturing and project scheduling, transportation and crew scheduling, and any setting where timed, concurrent, resource-bounded activities must be coordinated; such systems have planned operations for real space missions.
History
Qualitative temporal reasoning was formalized by Allen's interval algebra (1983), and quantitative temporal constraint networks by Dechter, Meiri, and Pearl (1991). These foundations, together with durative-action models added to PDDL in the early 2000s, enabled temporal planners used in applications such as autonomous spacecraft control.
Key figures
- James F. Allen
- Rina Dechter
- Judea Pearl
- Itay Meiri
- Nicola Muscettola
Related topics
Seminal works
- dechter1991
- allen1983
Frequently asked questions
- What is the difference between planning and scheduling?
- Planning decides which actions to take to achieve goals, while scheduling decides when those actions occur and which resources they use, given ordering and capacity constraints. Many real problems require both, and temporal planning integrates action selection with timing and resource reasoning.
- What is the simple temporal problem?
- The simple temporal problem is a temporal constraint network in which each constraint bounds the difference between two time points by an interval. Its consistency and the tightest implied bounds can be computed efficiently, which makes it a practical core for temporal reasoning in planners and schedulers.