PaperlayerView exact revision on arXiv

Source-linked AI summary

An Approach to Temporal Planning and Scheduling in Domains with Predictable Exogenous Events

A. Gerevini, A. Saetti, I. Serina

arXiv:1110.2728v1cs.AI

TL;DR

Known-time exogenous events can constrain actions to predefined time windows, making duration-aware planning require temporal scheduling. The paper integrates disjunctive temporal reasoning into graph-based local-search planning, and IPC-4 analysis reports strong performance against recent temporal planners in CPU time and best-plan quality.

  • Problem

    Known-time exogenous events can restrict actions to predefined time windows, so planning with action durations must also reason about whether actions can be scheduled within them.

    Source: §1 · p. 1

  • Method

    The paper represents partial plans with TDA-graphs and integrates disjunctive constraint-based temporal reasoning into graph-based planning, using a polynomial method for the resulting temporal problems.

    Source: §1 · p. 2, §2.2 · pp. 5–6, §2.3 · p. 7

  • Results

    Statistical analysis of IPC-4 found that LPG-td performed very well against recent temporal planners in both CPU time to find a valid plan and quality of the best plan generated.

    Source: §6 · p. 35

  • Takeaways & Limitations

    The results support developing specialized techniques for the DTPs arising in this planning framework, since general DTP solvers are described as inadequate for that class.

    Source: DTPs · p. 31

    The first method for handling timed conditions is usable only when the number of time windows is relatively small; the second method was designed for problems with many windows.

    Source: §4.2 · p. 29

Abstract

from arXiv · show

The treatment of exogenous events in planning is practically important in many real-world domains where the preconditions of certain plan actions are affected by such events. In this paper we focus on planning in temporal domains with exogenous events that happen at known times, imposing the constraint that certain actions in the plan must be executed during some predefined time windows. When actions have durations, handling such temporal constraints adds an extra difficulty to planning. We propose an approach to planning in these domains which integrates constraint-based temporal reasoning into a graph-based planning framework using local search. Our techniques are implemented in a planner that took part in the 4th International Planning Competition (IPC-4). A statistical analysis of the results of IPC-4 demonstrates the effectiveness of our approach in terms of both CPU-time and plan quality. Additional experiments show the good performance of the temporal reasoning techniques integrated into our planner.

1. In tro du tion

Known-time exogenous events create action time windows that temporal planners must respect, especially when actions have durations. The paper integrates disjunctive temporal reasoning into graph-based planning and evaluates the resulting planner on IPC-4.

1. In tro du ction

  • Actions with durations must be scheduled within time windows determined by exogenous events, or the resulting plan is invalid and must be revised.These events occur at known times and cannot be influenced by the planning agent.Source: §1 · pp. 1–2
  • Earlier frameworks for action durations and time windows were often domain-dependent or too slow for large-scale problems.The proposed approach integrates constraint-based temporal reasoning into a graph-based planning framework.Source: §1 · p. 1
  • The approach represents temporal plans with a Temporally-Disjunctive Action Graph (TDA-graph), integrating disjunctive constraint-based temporal reasoning into graph-based planning.The paper also proposes a polynomial method for the resulting temporal reasoning problems and local-search techniques to guide planning.Source: §1 · p. 2
  • The planner focuses on timed initial literals, which represent predictable exogenous events, and treats them differently from derived predicates.Timed-initial-literal handling supports temporal plan representation and action scheduling; derived predicates use a rule-based inference system.Source: §1 · p. 2
  • IPC-4 analysis reports that LPG-td was a top performer on benchmark problems involving timed initial literals.The paper describes LPG-td as an implementation of the approach and reports its participation in IPC-4.Source: §1 · p. 2

2. T emp orally Disjun tiv e A tion Graph

This section develops Temporally-Disjunctive Action Graphs to represent temporal plans with action-duration, scheduling, and timed-initial-literal constraints, placing actions within associated time windows. It defines optimal induced STPs and schedules, and presents a polynomial-time method for computing them without backtracking.

2.1 Ba kground: Linear A tion Graph and Disjun tiv e T emp oral Constrain ts

  • Linear action graphs alternate fact and action levels, encode mutex and causal ordering constraints, and provide the graph-based planning representation extended by the paper.Disjunctive temporal problems are NP-hard, whereas simple temporal problems with unary constraints can be solved in polynomial time.Source: §2.1 · pp. 3–4

2.2 Augmen ting the LA-graph with Disjun tiv e T emp oral Constrain ts

  • TDA-graphs add duration and scheduling constraints to linear action graphs, with scheduling constraints requiring actions with timed preconditions to execute during associated time windows.The paper identifies the representation and treatment of scheduling constraints as a major contribution.Source: §2.2 · pp. 4–5
  • A TDA-graph comprises a linear action graph, assigned real-valued node times, action start- and end-time variables, and ordering, duration, and scheduling constraints.It represents a partial plan whose action start times are assigned by the node-time values.Source: §2.2 · p. 6
  • An optimal schedule is an optimal solution of an optimal induced STP, which minimizes the makespan of the represented plan.A complete induced STP is optimal for a point variable when its solution assigns that point a value no greater than any solution of another complete induced STP.Source: §2.2 · p. 7

2.3 Solving the DTP of a TD A-graph

  • The TDA-graph algorithm computes an optimal induced STP in polynomial time without backtracking.Computing a complete induced STP is generally NP-hard, but the structure of TDA-graph temporal constraints permits this method.Source: §2.3 · p. 7
  • The method assumes each time window for a timed precondition is at least as long as its action’s duration and that each action has at most one timed precondition.If a window is too short, it is removed; if none remain, the action cannot be used in a valid plan.Source: §2.3 · p. 7
  • Timed conditions can be compiled in polynomial time into one equivalent timed precondition by intersecting their windows and translating at-start and at-end conditions into over-all conditions.The text allows multiple windows for a timed condition.Source: §2.3 · pp. 7–8

Solve-DTP(X ; S )

Solve-DTP operates on meta-variables and a partial meta-CSP solution, selecting variables and values and applying a forward check before returning a solution or failure.

Solve-DTP(X ; S )

  • Solve-DTP takes the meta-variables of a DTP's meta-CSP and a partial solution as input, and returns either a solution or fail.The supplied pseudocode identifies these inputs and outputs.Source: Solve-DTP(X ; S ) · p. 9
  • The algorithm selects a variable and a value, then updates the partial solution and the variable's remaining domain.It saves domain values during the update.Source: Solve-DTP(X ; S ) · p. 9
  • After the update, the algorithm applies ForwardCheck-DTP to test the partial assignment.The pseudocode proceeds conditionally on the forward-check result.Source: Solve-DTP(X ; S ) · p. 9

8. Solve-DTP(X

This section presents Solve-DTP, a constraint-based method for solving temporal scheduling constraints during planning. It uses variable and value ordering plus incremental temporal-constraint reasoning to find complete or partial solutions, with polynomial runtime in the number of action nodes and the maximum number of time windows per scheduling constraint.

8. Solve-DTP(X

  • Variable ordering follows the TDA-graph’s level structure, prioritizing single-valued ordering, duration, and scheduling constraints before scheduling constraints with multiple time windows.For multi-valued scheduling constraints, value ordering selects the earliest available time window.Source: §8 · pp. 9–10
  • When the meta-CSP is solvable, Solve-DTP finds a solution without backtracking, and that solution is an optimal induced STP.The algorithm selects single-valued constraints before multi-valued scheduling constraints and chooses the earliest available time window.Source: §8 · pp. 10–11
  • Replacing Solve-DTP’s backtracking step with immediate failure yields a correct backtrack-free algorithm even when the meta-CSP has no solution.The method uses the TDA-graph’s LA-graph to decompose the DTP into a sequence of growing DTPs.Source: §8 · pp. 10, 12
  • Solve-DTP processes the DTP’s meta-CSP in polynomial time in the number of action nodes and the maximum number of time windows in any scheduling constraint.Source: §8 · p. 12
  • Solve-DTP’s runtime depends on the maximum number of scheduling windows and repeated consistency checks over action-time variables.The consistency checks operate on the original CSP’s action start and end times; the passage gives a complexity bound, but its exponents are corrupted in the supplied text.Source: §8 · p. 13
  • The solver initializes ordering and duration variables, leaving only scheduling variables unassigned, and performs forward checking once per meta-variable.If the meta-CSP is solvable, the first selected value is feasible; otherwise the solver can stop, and it can omit saving and restoring variable domains.Source: §8 · p. 13
  • For incremental updates, the solver recomputes sub-solutions only for affected meta-variable subsets and reuses the other variables’ previous assignments.The affected subsets correspond to action-node additions or removals during planning.Source: §8 · p. 13
  • When no complete solution exists, the solver continues processing remaining meta-variables and returns a partial induced STP whose optimal solution defines the T-assignment.This change supports the local-search techniques described in the following section.Source: §8 · p. 13

3. Lo al Sear h T e hniques for TD A-Graphs

The section presents Walkplan, a local-search procedure that repairs flawed TD A-graphs by adding or removing actions. Its heuristics estimate both the search and temporal costs of candidate repairs.

3. Lo cal Sear h T e hniques for TD A-Graphs

  • A TD A-graph flaw is either an unsupported precondition or an unscheduled action; a valid plan has no flawed levels.An action is helpful if inserting it at or before a flawed level removes a propositional flaw, and harmful if removing it would remove such a flaw or decrease an unscheduled action's time value.Source: §3 · p. 14
  • Walkplan searches among TD A-graphs by adding helpful actions or removing harmful ones to repair the earliest flawed level.Adding an action can extend the graph and shift actions at that level forward; removing one shrinks the graph. The DTP and schedule are updated after either change.Source: §3 · pp. 14–15
  • The evaluation function combines estimated search cost with temporal cost, including the candidate action's contribution to plan makespan.Search cost is estimated using a relaxed temporal plan and counts its actions plus newly unscheduled actions, unsatisfied timed preconditions, and scheduling constraints estimated to be unsatisfiable.Source: §3 · p. 15
  • Walkplan selects a lowest-combined-cost neighbor, with noise to escape local minima and a short tabu list also used to escape them.The planner's initial graph contains only a dummy action; each search step considers graphs formed by adding a helpful action or removing a harmful one.Source: §3 · pp. 14–15
  • The relaxed temporal plan estimates the actions needed to achieve unsupported preconditions, remaining propositional flaws, and preconditions threatened by a candidate action.It also estimates additional temporal flaws, including actions made unscheduled and timed preconditions or scheduling constraints that cannot be satisfied under the estimate.Source: §3 · p. 15

8. T (b) ComputeEFT (b; t

The section extends relaxed-plan construction with temporal estimates and constraints. RelaxedTimePlan returns a set of actions and an estimated earliest finishing time.

8. T (b) ComputeEFT (b; t

  • RelaxedTimePlan runs twice: first to achieve an action's preconditions, then to achieve unsupported facts and threats, reusing actions from the first run and the action being evaluated.It returns the relaxed-plan action set and its estimated earliest finishing time.Source: §8 · p. 18
  • The action chosen to achieve a subgoal accounts for support needs, threats to supported preconditions, unsatisfied timed preconditions, and scheduled actions it may disrupt.These criteria are combined in BestAction's action-selection method.Source: §8 · p. 18
  • The estimated earliest start time uses lower bounds from reachability, earlier graph actions, and the relaxed plan's estimated precondition-achievement time; earliest finish adds the action's duration.The resulting start and finish estimates are used to count timed preconditions that cannot be satisfied.Source: §8 · p. 19

Example of \TimedPre"

The examples illustrate how timed preconditions constrain action scheduling and how estimated timing can reveal whether adding an action threatens another action's feasible window.

Example of \TimedPre"

  • For b3, the estimated earliest start is the maximum of its lower bound, 15, and the estimated time its preconditions are supported, 20.The example gives an estimated start of 20 and duration of 10; with q's window [0,20), b3 cannot be scheduled.Source: Example of \TimedPre" · p. 19
  • Slack is the maximum amount by which an action’s T-value can be consistently increased in S without violating its chosen scheduling window; starting at 35 + δ yields a finish of 125 + δ against [75,125).Source: Example of \TimedPre" · pp. 19–20
  • The search evaluates adding an action by estimating delay to another action and comparing that delay with the available slack.The example treats b4 as a time threat to a, but not b3.Source: Example of \TimedPre" · p. 20

4. Exp erimen tal Results

The experiments evaluate LPG-td on benchmark problems with timed initial literals, comparing solution rates, CPU time, and plan quality with IPC-4 planners. They also assess its temporal reasoning against a general DTP solver, including the growth of classical DTP translations with the number of time windows.

4. Exp erimen tal Results

  • LPG-td generates a sequence of valid plans, each improving on the previous plan’s quality.The planner was implemented for the IPC-4 metric-temporal track, where it received second prize.Source: §4 · p. 20

4.1 LPG-td and Other IPC-4 Planners

  • LPG-td and SGPlan were the only planners supporting all major PDDL2.1 and PDDL2.2 features, and both had success ratios close to 80%.Downward and YAHSP had higher success ratios but handled only propositional domains; LPG-td also omitted some variants that required unsupported equality conditions.Source: §4.1 · p. 22
  • In Airport, LPG-td solved 45 problems over 50, versus SGPlan’s 43, P-MEP’s 12, and TilSapa’s 7; it was faster than SGPlan on nearly all problems.LPG-td’s plan quality was similar to P-MEP and TilSapa, while SGPlan generally produced worse-quality plans.Source: §4.1 · p. 22, Figure 6 · p. 23
  • In PipesWorld with timed initial literals, LPG-td solved 23 problems over 30, compared with 3 for TilSapa, and performed much better.These were the only two IPC-4 planners to attempt this domain variant.Source: §4.1 · p. 22, Figure 6 · p. 23
  • In the flawed Umts variant, LPG-td solved all 50 problems versus SGPlan’s 27 and was about one order of magnitude faster on every solved problem.LPG-td’s best-quality plans were much better than SGPlan’s except on the simplest problems, where their plan quality was similar.Source: §4.1 · p. 22, Figure 6 · p. 23
  • LPG-td was consistently faster than Tilsapa and P-MEP, significantly often faster than SGPlan, and consistently produced better-quality plans; Figure 9 compares its speed and makespan with optimal planners.Source: §4.1 · pp. 25–26, Figure 9 · p. 26
  • LPG-td found plans much faster than any optimal planner, and its best plan was optimal on nearly every problem; best-plan CPU time was often below AllOthers-Opt except four Airport problems.The exceptions were problems 12, 16, 18, and 20 of Airport; LPG-td’s first plan was generally good.Source: §4.1 · p. 26
  • About 90% of metric-temporal problems had an optimal or near-optimal best plan; 60% of first plans were optimal or near-optimal, and only about 25% were over 0.5 worse than optimal.Figure 10 analyzes plan-quality distances across metric-temporal and STRIPS IPC-4 variants; STRIPS showed similar results, with somewhat fewer near-optimal first plans and slightly more best plans over 50% worse.Source: §4.1 · p. 27, Figure 10 · p. 27

4.2 T emp oral Reasoning in LPG-td

  • LPG-td solved all modified Rovers and ZenoTravel problems; degradation from 1 to 10 windows was generally moderate, and tests with 1 to 10,000 windows scaled well.The first window-generation method can make problems unsolvable when many windows are too small; the second was designed to avoid this and test many-window cases.Source: §4.2 · p. 29, Figure 11 · p. 29, Figure 12 · p. 30
  • For the first ZenoTravel problem, runtime rose from 10 milliseconds with 1 window to about 1 second with 10,000 windows, mainly because preprocessing became heavier.Source: §4.2 · p. 29
  • Table 3 reports CPU time for LPG-td’s temporal reasoning techniques alongside tsat++ (Armando, Castellini, Giunhiglia, & Maratea, 2004), a state-of-the-art general DTP solver.The supplied passages do not provide the table’s values or establish which solver is faster.Source: §4.2 · p. 30
  • The DTPs evaluated are the same sets of temporal constraints in the TDA-graph at each search as those in Table 2.Source: §4.2 · p. 30
  • Classical DTP translation of a scheduling constraint can require exponentially many disjuncts as the number of time windows increases.For a timed precondition with windows [25, 50) and [75, 125), the passage says the constraint translates into four classical DTP constraints.Source: §4.2 · p. 30

DTPs

The planner’s specialized temporal reasoning solver handles the DTPs generated during planning far more efficiently than a general solver, while incremental solving improves runtime further. The comparison is scoped to this subclass of DTPs, and the specialized solver also produces an optimal schedule when a DTP is satisfiable.

DTPs

  • The comparison uses tsat++, a general solver designed to handle a much larger class of DTPs, because the authors found no more specialized alternative for this scheduling-constraint subclass.The authors’ stated aim is to show that general DTP solvers are inadequate for these problems and that specialized techniques can be more efficient.Source: DTPs · p. 31
  • In Rovers problem 15, LPG-td generated 77 DTPs over 77 search steps.The paper uses this example to illustrate the number of temporal reasoning problems generated during planning.Source: DTPs · p. 31
  • Solve-DTP is several orders of magnitude faster than an efficient general DTP solver on the temporal reasoning problems generated during planning.The authors state that the comparison is intended to show the inadequacy of general DTP solvers for this subclass, not to determine which solver is better overall.Source: DTPs · p. 31
  • For satisfiable DTPs, Solve-DTP also finds an optimal schedule, whereas tsat++ only decides satisfiability.The reported tsat++ CPU time excludes DTP generation and parsing.Source: DTPs · p. 31
  • The basic Solve-DTP version averages one to three orders of magnitude more CPU time than its incremental version, but remains one to four orders faster than tsat++.These comparisons apply to the problems in Table 3.Source: DTPs · p. 32

5. Related W ork

Related work spans temporal planners, graph-based planning, and general DTP solvers. The paper distinguishes its approach through temporal-level handling of timed events and specialized polynomial reasoning for the scheduling constraints in its representation.

5. Related Work

  • Some general DTP techniques have exponential worst-case complexity, and experiments indicate that a state-of-the-art general solver is inadequate for the subclass arising in this planning framework.The planner instead uses a polynomial solver specialized to that subclass.Source: §5 · pp. 32, 34
  • Explicit event nodes in an action graph could make graphs and search neighborhoods very large when timed initial literals are numerous, increasing memory use and heuristic-evaluation cost.The paper’s approach handles exogenous events at the temporal rather than logical-causal level.Source: §5 · p. 33
  • The tgp extension represents predictable exogenous events, but supports only a subclass of PDDL2.1 durative actions and does not scale adequately; it is optimal under a conservative concurrency model.LPG-td is described as near-optimal rather than optimal.Source: §5 · p. 33
  • Edelkamp (2004) assumes one time window per timed precondition, whereas this approach supports multiple windows and computes optimal schedules for partially ordered plans in polynomial time.The paper presents its temporal reasoning as more general while preserving polynomiality.Source: §5 · p. 34
  • Cresswell and Coddington (2004) represent timed initial literals as deadline actions and manage resulting constraints with a general linear-programming solver; LPG-td uses a different representation and specialized algorithm.LPG-td manages temporal and scheduling constraints without encoding timed initial literals as special actions.Source: §5 · p. 34
  • Unlike SAPA’s relaxed-plan-only slack analysis, LPG-td uses slack to estimate scheduling-constraint violations and considers both relaxed-plan and real-plan actions.Candidate actions causing fewer violations are preferred.Source: §5 · p. 34

6. Con lusions

The paper integrates temporal reasoning with graph-based local search to plan around predictable exogenous events, where timed preconditions constrain action scheduling. Its IPC-4 analysis reports strong performance in CPU time and plan quality, while further experiments find the temporal reasoning techniques efficient for the DTPs in this setting.

6. Con lusions

  • The TDA-graph combines graph-based plan representation with constraint-based temporal reasoning, while stochastic local search guides planning.The specialized temporal-constraint algorithm has polynomial worst-case complexity and was reported to be very efficient in practice.Source: §6 · p. 35
  • The search heuristics extend earlier LPG methods to account for action-scheduling constraints using relaxed temporal plans and dynamic reachability information.The paper also identifies future work on limited-persistence effects, delays, and predictable events affecting numeric fluents.Source: §6 · p. 35
  • IPC-4 analysis found that LPG-TD performed very well against recent temporal planners on CPU time and best-plan quality, and often produced plans of very good or optimal quality.Additional experiments found that its temporal reasoning techniques managed the DTPs arising in this context very efficiently.Source: §6 · p. 35

A kno wledgmen ts

The paper acknowledges research support and contributions to the planner’s PDDL2.2 parser. The accompanying reachability material describes heuristic estimates of action counts and earliest times, incorporating scheduling constraints.

A kno wledgmen ts

  • The work received partial support from MIUR grant anemone and a Marie Curie Fellowship.The authors also thank anonymous reviewers and Paolo Toninelli, who extended the LPG-TD parser for new PDDL2.2 language features.Source: A kno wledgmen ts · p. 36
  • Reachability information estimates the minimum actions needed to reach action preconditions and the earliest finishing time, accounting for scheduling constraints.The resulting earliest-finish estimates help evaluate search neighborhoods and can identify actions that cannot fit their timed-precondition windows for pruning.Source: A kno wledgmen ts · p. 36

RequiredA tions(I ; G)

The reachability procedure estimates action counts and temporal feasibility from an initial state or a set of facts. It updates earliest and latest action finishing times under scheduling constraints, revisiting actions when prerequisite estimates improve.

RequiredA tions(I ; G)

  • The procedure estimates the minimum actions required to reach facts or action preconditions and the earliest times facts become reachable and actions finish.It uses the initial state and ground actions as input, or facts and a target set of preconditions in the related required-actions procedure.Source: RequiredA tions(I ; G) · p. 37
  • Accounting for scheduling constraints improves earliest-finish estimates and can prune actions that cannot fit their timed-precondition windows.This information is used to evaluate search neighborhoods and select actions for temporal relaxed plans.Source: RequiredA tions(I ; G) · p. 38
  • Actions are reconsidered when estimated earliest times of their preconditions decrease, which can improve finish-time estimates and is necessary for algorithm correctness.Overestimating an action’s earliest finish could wrongly deem a necessary action unschedulable and the problem unsolvable.Source: RequiredA tions(I ; G) · p. 38
  • Earliest finishing time is computed from the maximum estimated earliest time of an action’s preconditions, its duration, and its scheduling constraints.The procedure also computes latest finishing time; if earliest finish exceeds latest finish, it skips further processing of that action.Source: RequiredA tions(I ; G) · p. 40
  • The appendix evaluates planner CPU time and plan quality with Wilcoxon tests, treating differences as statistically significant when p-values are below 0.001.The analysis uses a 99.9% confidence level; table cells and partial-order diagrams encode planner comparisons.Source: RequiredA tions(I ; G) · p. 40

Referen es

The references include work on temporal planning, planning graphs, local search, scheduling, and disjunctive temporal reasoning.

Referen es

  • The bibliography includes research on planning graphs, stochastic local search, and temporal action graphs.Examples include Blum and Furst (1997) and Gerevini, Saetti, and Serina (2003).Source: Referen es · pp. 42–43
  • References address temporal planning with durations, time windows, deadlines, and exogenous events.The list includes work by Gerevini, Saetti, and Serina (2005a), and Do, Kambhampati, and Zimmerman (2004).Source: Referen es · pp. 42–43
  • The bibliography also covers disjunctive temporal reasoning and temporal constraint methods.It includes Tsamardinos and Pollack (2003) and Dechter, Meiri, and Pearl (1991).Source: Referen es · pp. 42, 45
Loading 1110.2728v1…