TRPG is employed in CRIKEY3. The durative actions are splitting into start and end snap-actions, possitive and negative effects, respectively.
[2] TRPG has three desirable qualities:
- Respect the PDDL start-end semantics. Relaxed plans are constructed from a classical RPG using snap-actions.
- Respect relationships between start and end snap-actions: Aend can only be applied if Astart has been applied before it. The start snap-action is augmented with a dummy precondition, which is used by the end snap-action. Thus, the end action is choosen at an earlier layer.
- Account for action durations: end effects of actions are only available sufficiently far after they have started. The actions are labelled with durations.
The algorithm to generate a TRPG without numeric variable is the next:
Where F is a state, E is an ordered list of ongoing actions, actions that have started but not yet finished, and T is a collection of temporal constraints over the actions in the relaxed plan. Each e in E is a tuple where:
- op is the identifier of a start snap-action.
- i is the index of the snap-action in the plan to reach F
- dmin, dmax are the minimun and maximun duration, determined in the state in which the action first executed.
[1] Description of a TRPG: The first fact layer corresponds to the state being evaluated.Following this are timestamped action and fact layers, with action layers containing both start and end actions and fact layers their (positive) effects.
The durations of actions are used to offset start and end points between fact layers in order to capture the temporal relationships between the starts and ends of actions.
If a start action Astart appears at layer t in the planning graph, its end is delayed until layer t+dur-min(A). This is the earliest point at which the end could be applied, given that it has to follow the start.
For each action that started before the current state (ongoing action) but has not yet finished, the TRPG maintains an upper bound on the elapsed time since the start. The corresponding end action is delayed until the layer timestamped with the minimum duration of the action minus that bound.
The TRPG also contains bounds estimates for numeric variables, mantained and used in the same way as Metrics-FF.
[2] Adding deadlines - Timed Initial Literals (TIL)
A TILs is encoded as effects in a dummy TIL action, that should be executed at each time point, and can be added to the relaxed plan.
They include a propositional fact p which is true in the initial state, is not added or deleted by any action, but is deleted by a TIL dummy action at time d and not added by any subsequent TIL dummy action.
Example:
[1] Forward-Chaining Partial-Order Planning
[2] Planning with Problems Requiring Temporal Coordination
