Temporal Planning

Unlike classical planning where actions are instantaneous, temporal planning models actions with explicit start times and durations. This is formally represented in languages like PDDL2.1 using :duration and :durative-action constructs. The planner must reason about the passage of time to schedule actions correctly, which is essential for applications like robotic task scheduling or manufacturing process planning where operations take non-zero time to complete.

A core capability is the scheduling of multiple actions to occur in parallel, provided they do not conflict. The planner must manage:

• Resource conflicts: Ensuring two actions requiring the same limited resource (e.g., a robot arm) are not scheduled to use it simultaneously.
• Mutual exclusions: Preventing logically incompatible actions (e.g., 'heat metal' and 'quench metal') from overlapping. This concurrency enables the generation of efficient, compact timelines rather than strictly sequential plans.

Plans must satisfy complex temporal constraints between events. These are often expressed as inequalities linking action start/end times. Key constraint types include:

• Deadlines: A goal must be achieved by a specific time.
• Windows: An action must start or end within a specific time interval.
• Precedence: Action A must end at least X time units before Action B starts.
• Synchronization: Two actions must start or end simultaneously. These constraints are critical for coordinating subsystems in domains like logistics or spacecraft operations.

Temporal planners often reason about continuous numeric state variables that change linearly over time during an action's execution. Examples include:

• Battery level decreasing during a drone's flight.
• Temperature increasing during a heating process.
• Fuel level depleting. Preconditions and effects can check or modify these variables, requiring the planner to solve linear equations to ensure constraints (e.g., battery > 0) hold throughout an action's duration. This integrates planning with simple forms of numeric simulation.

Solving temporal problems efficiently requires specialized heuristics. Temporal landmarks are facts that must be true at some specific time point or interval in every solution. For example, 'Package P must be at Airport A between 10:00 and 12:00'. Planners like LPG or Temporal Fast Downward use:

• Landmark extraction to discover necessary timed events.
• Relaxed plan graphs that include time layers.
• Critical path analysis to estimate the earliest possible achievement time for goals, guiding the search toward feasible schedules.

The output of a temporal planner is not just a sequence but a temporal plan or schedule. This is typically a set of timed initial literals and durative actions with precise start times. Formally, it can be represented as { (t1, a1), (t2, a2), ... } where t is a start time and a is a durative action. The plan's makespan (total time from start to finish) is a primary optimization metric. Validation requires a temporal simulation to ensure all conditions hold continuously over the plan's execution, not just at discrete snapshots.

A Simple Temporal Network is a constraint graph formalism for representing and solving temporal constraints between events. It consists of:

• Time Points: Variables representing the start or end of events.
• Temporal Constraints: Bounded intervals ([lb, ub]) between time points (e.g., Event B must start between 5 and 10 minutes after Event A). Algorithms like the Bellman-Ford variant check for consistency and compute the earliest/latest feasible times for all events, forming the scheduling backbone of many temporal plans.

A Temporal Action Graph is a data structure used by planners like TFD (Temporal Fast Downward) to encode the planning problem over time. It extends the classical planning graph by:

• Adding time layers to represent progression.
• Tracking mutexes (mutual exclusions) between actions that cannot overlap due to resource conflicts or interfering preconditions/effects.
• Enabling the search for plans with concurrent actions, where the planner must reason about overlapping action durations and their combined effects.

In temporal planning, a chronicle is a partial description of a plan that specifies:

• A set of events (instantaneous happenings).
• A set of persistent conditions that must hold over specific intervals.
• Temporal constraints linking events and intervals. Planners like IXTeT and HSTS use chronicles as a core representation. The planning process involves gradually refining a chronicle by adding events and constraints until it represents a complete, consistent temporal plan.

This distinction is critical for real-world execution of temporal plans.

• A Scheduled Plan has fixed, absolute start times for all actions (e.g., Action A starts at t=5). It is brittle to minor execution delays.
• A Dispatchable Plan specifies a set of temporal constraints (e.g., Action B starts between 2 and 4 seconds after Action A ends). A dispatcher module monitors execution and chooses precise start times online, within the constraints, providing robustness to uncertainty. Temporal planners often generate dispatchable plans.

A Temporal Landmark is a fact that must be true at some specific time point or during a time interval in every solution to a temporal planning problem. For example, "the robot must be at the charging station between hours 2 and 3."

• Ordering Landmarks: Specify that landmark L must be achieved before landmark K.
• Time-Bounded Landmarks: Specify the landmark must hold within a temporal window. Identifying landmarks provides powerful heuristic guidance, pruning the search space by enforcing necessary temporal orderings early.