PaperlayerView exact revision on arXiv

Source-linked AI summary

COLIN: Planning with Continuous Linear Numeric Change

Amanda J. Coles, Andrew I. Coles, Maria Fox, Derek Long

arXiv:1401.5857v1cs.AI

TL;DR

Planning systems have had limited ability to combine temporal constraints with numeric change that depends on elapsed time or action duration. COLIN combines forward-chaining search with linear-program reasoning and an extended temporal heuristic to solve this class of problems. The paper reports that COLIN solves complex continuous-change benchmarks, while identifying substantial opportunities for improved heuristic guidance, pruning, and expressive scope.

  • Problem

    The central gap is planning with tightly integrated temporal constraints, continuous linear change, and duration-dependent effects.

  • Method

    COLIN combines forward search, linear programs for temporal-numeric consistency and variable bounds, and a heuristic extended for continuous change.

  • Results

    COLIN solves interesting and complex continuous-change problems and demonstrates scalability across a range of benchmarks.

  • Takeaways & Limitations

    The work establishes benchmark problems and shows that LP and MILP tools can support state consistency, progression, heuristic guidance, and timestamp optimization.

  • Takeaways & Limitations

    COLIN struggles to detect implicit deadlines created when finite-energy torch actions are started in AUV problems.

Abstract

from arXiv · show

In this paper we describe COLIN, a forward-chaining heuristic search planner, capable of reasoning with COntinuous LINear numeric change, in addition to the full temporal semantics of PDDL. Through this work we make two advances to the state-of-the-art in terms of expressive reasoning capabilities of planners: the handling of continuous linear change, and the handling of duration-dependent effects in combination with duration inequalities, both of which require tightly coupled temporal and numeric reasoning during planning. COLIN combines FF-style forward chaining search, with the use of a Linear Program (LP) to check the consistency of the interacting temporal and numeric constraints at each state. The LP is used to compute bounds on the values of variables in each state, reducing the range of actions that need to be considered for application. In addition, we develop an extension of the Temporal Relaxed Planning Graph heuristic of CRIKEY3, to support reasoning directly with continuous change. We extend the range of task variables considered to be suitable candidates for specifying the gradient of the continuous numeric change effected by an action. Finally, we explore the potential for employing mixed integer programming as a tool for optimising the timestamps of the actions in the plan, once a solution has been found. To support this, we further contribute a selection of extended benchmark domains that include continuous numeric effects. We present results for COLIN that demonstrate its scalability on a range of benchmarks, and compare to existing state-of-the-art planners.

1. Introduction

Planning has advanced for independent temporal and metric features, but integrating time-dependent numeric change remains difficult. COLIN addresses this gap by extending heuristic forward search to continuous linear and duration-dependent change.

  • Existing planners handle independent temporal and metric conditions, but their integration with time-dependent numeric change remains relatively underexplored.
  • Duration-dependent effects allow action outcomes to vary with constrained durations, while continuous effects vary throughout execution.These extensions capture process behaviour more flexibly than fixed instantaneous updates.
  • Continuous change is relevant to energy management, restricted resources, chemical storage, robot motion, and efficient time use.
  • COLIN combines forward search with linear-program reasoning to handle variable duration-dependent change and continuous numeric effects.It extends CRIKEY3, whose discrete-change representation cannot handle these features.
  • The paper extends CRIKEY3’s temporal heuristic, develops benchmark domains, and evaluates COLIN’s scalability against existing planners.The paper also considers mixed-integer programming for optimizing timestamps after a solution is found.

2. Language Features in CRIKEY3 and COLIN

COLIN extends CRIKEY3 to support continuous linear numeric change while retaining selected temporal-planning features and total-time optimization. Its scope excludes nonlinear updates, general plan metrics, exogenous PDDL+ processes, and full conditional effects.

  • COLIN handles the full range of linear continuous numeric effects, whereas CRIKEY3 is restricted to discrete change.
  • COLIN can minimize the total-time cost of the shortest plan it finds.
  • COLIN supports Timed Initial Literals and a restricted conditional-effect form, but not full ADL or more general conditional effects.
  • COLIN does not handle PDDL+ processes and events, which represent continuous behaviour caused by exogenous world processes.Its continuous-change handling is restricted to effects expressed through durative actions.
  • The paper contrasts CRIKEY3 and COLIN across their supported language features.

3. Motivation

Hybrid discrete-continuous applications commonly rely on discretization or specialized solvers, but several domains require reasoning about continuous dynamics directly. These include industrial processes, energy management, time-dependent costs, and robotic motion.

  • Hybrid discrete-continuous applications are often handled by discretizing time, packaging continuous effects as steps, or combining propositional planning with specialized solvers.
  • Refineries and chemical plants require continuous modelling of material flows, mixing, reactions, heating, and cooling.
  • Aerospace power management uses continuous models to reason about power supply across solar-panel configurations.
  • Battery management may require reducing nonlinear dynamics to discrete or linear approximations with iterative validation and refinement.The cited battery problem is described as one that cannot be solved if continuous dynamics are removed.
  • Aircraft landing assigns time-dependent runway-use costs, while mobile-robot choreography couples continuous motion with task accessibility.

4. Problem Definition

Temporal-metric-continuous planning extends temporal-metric planning with linear continuous effects and duration-dependent effects. The Borrower Domain illustrates how concurrency and evolving numeric values shape alternative plans and makespan quality.

  • COLIN targets temporal-metric-continuous problems, a substantial subset of problems expressible in PDDL2.1.
  • A planning problem comprises an initial state, actions with temporal conditions and effects, goals, and optionally a metric optimization function.
  • Actions may impose duration constraints, and solutions are time-stamped action sequences with explicitly specified durations that satisfy all conditions.
  • Numeric conditions use comparisons over functions of metric fluents, while linear-normal-form expressions are weighted sums of variables plus constants.
  • Continuous effects change a variable at a constant rate, and duration-dependent effects allow action updates to depend on ?duration.Together, these extensions make variable values depend on elapsed time and assigned action duration.
  • The formalism excludes nonlinear continuous change and explicit events or processes, although modelling tricks can capture similar behaviours.
  • The Borrower Domain requires concurrency because saving, mortgage, and life-audit actions interact through the evolving money variable.
  • The longer-mortgage solution is preferable because its lower deposit allows earlier initiation and a shorter makespan than the alternative.

5. Background in Metric and Temporal Planning

Metric and temporal planners progressively moved beyond compressed action semantics toward explicit concurrency and temporal structure. Required concurrency is essential for continuous effects, while fixed time increments and compression impose important limits.

  • Metric planning: Metric-FF-style planning introduced numeric variables and optimistic bounds for testing linear numeric conditions.For w · v ≥ c1, the bound uses each fluent’s upper or lower bound according to its coefficient’s sign.
  • Temporal planning: Action compression simplifies temporal planning by replacing duration-wide semantics with weakest preconditions and strongest effects.This simplification can be incomplete for temporal problems requiring coordination between action start and end points.
  • Required concurrency: Required concurrency matters because both the timing and magnitude of continuous change affect conditions throughout execution.Discretising continuous change into endpoint effects would prevent reasoning about interactions during overlapping actions.
  • Required concurrency: CRIKEY3 avoids compression by searching over paired start and end snap-actions, enabling coordinated action interleavings.This increases the search space because each durative action becomes two snap-actions.
  • Temporal limitations: Uniform time-layer approaches are inadequate when no suitable increment exists for time-dependent effects or when action durations differ substantially.These limitations motivate planners that retain more explicit temporal structure.

6. CRIKEY3: A Forward-Chaining Temporal Planner

CRIKEY3 extends forward-chaining heuristic search to temporal planning by representing durative actions as separate starts and ends. Its states track facts, plans, active actions, and temporal constraints so invariants, durations, and completion can be checked during search.

  • Search: CRIKEY3 uses FF-style enforced hill-climbing and falls back to weighted A* when hill-climbing fails to find a solution.The search applies helpful-action filtering and validates candidate plans before accepting a goal state.
  • Action representation: Each durative action is compiled into start and end snap-actions, avoiding the expressivity restrictions of action compression.Coordinating these snap-actions allows plans with required concurrency, at the cost of a larger search space.
  • State representation: A CRIKEY3 state S = ⟨F, P, E, T⟩ records current facts and numeric values, the snap-action plan, active starts, and temporal constraints.The event list E records actions that have started but not finished.
  • Duration handling: Action durations are computed from the state at start, then retained as fixed minimum and maximum bounds while the action executes.The planner does not support durations constrained by conditions evaluated at action end.
  • State progression: Applicability requires both satisfied preconditions and effects that do not violate active invariants.Active invariants are derived from the currently executing actions represented in E.
  • Goal testing: A goal state requires the ordinary goal conditions and an empty event list, ensuring that all actions have completed.End snap-actions can only be applied when their corresponding starts are recorded in E.

7. Planning with Continuous Numeric Change

Continuous numeric planning combines temporal progression with changing state variables and has been addressed through planners based on processes, flow tubes, discretisation, and SAT or mixed-programming encodings. These approaches differ in their treatment of concurrency, time resolution, and scalability.

  • Problem setting: Hybrid temporal-numeric planning is challenging because metric fluent values can depend on elapsed continuous time and variable action duration.These problems combine temporal and numeric reasoning more tightly than standard temporal-metric planning.
  • Formal setting: PDDL2.1 combines instantaneous discrete transitions with continuous change while time passes between discrete changes.PDDL+ extends this model with exogenous processes and events represented using hybrid-automata semantics.
  • Earlier planners: Early continuous-process planners such as Zeno and OPTOP faced scalability or concurrency limitations when reasoning about interacting continuous actions.Zeno disallows concurrent continuous effects, while OPTOP’s plausible-progression heuristic does not sufficiently recognise interactions that block future actions.
  • SAT-based planning: TM-LPSAT compiles horizon-bounded continuous planning into SAT formulas plus linear constraints implementing PDDL+ semantics.It can represent variable durations, continuous effects, duration-dependent end-effects, and concurrent updates to continuous variables.
  • SAT-based planning: Reported empirical data indicates that TM-LPSAT is very slow and cannot solve plans longer than a few steps, while no public implementation enables further experiments.The passage distinguishes its broad theoretical coverage from its reported practical performance.
  • Flow-tube planning: Kongming represents continuous dynamics with flow tubes and discretised time layers, allowing variable rates but limiting plan depth to a few tens of layers.Unlike COLIN, it treats time as discretised and rates of change as variable.
  • Flow-tube planning: Kongming does not support concurrent continuous updates to the same state variable, creating an expressivity limitation relative to PDDL2.1.The text attributes this partly to unresolved semantics for combining concurrent dynamic constraints.
  • Discretisation-based planning: UPMurphi iteratively refines a guessed discretisation and constructs plans through planning-as-model-checking without heuristic search.It can additionally synthesise and robustify partial policies for uncertainty during hybrid-plan execution.

8. COLIN: Forward Chaining Planning With Continuous Linear Change

COLIN extends temporal planning to duration-dependent and continuous numeric change by integrating temporal and numeric constraints in a linear program. The LP supports plan consistency checking, state-variable bounds for action filtering, and representation of continuous effects between plan steps.

  • Temporal-numeric LP: COLIN integrates temporal and numeric constraints in an LP that replaces CRIKEY3’s STP-based plan-validity check.The LP represents action timestamps, temporal ordering, numeric effects, and their interactions in one consistency model.
  • Constraint construction: The LP includes temporal ordering, action-duration, numeric-precondition, invariant, and action-effect constraints for the plan.Action timestamps and future ends are represented as LP variables, while numeric conditions constrain the corresponding state-variable values.
  • LP state representation: The LP uses separate pre- and post-action vectors to represent discrete changes, while continuous effects modify variable gradients between action steps.Continuous gradients change when actions start or end, and the resulting constraints capture values over intervening intervals.
  • Continuous effects: For each variable, continuous-change gradients begin at zero, persist without relevant effects, increase when effects start, and decrease when effects terminate.These gradient updates provide the basis for adding continuous-change constraints to the LP.
  • Borrower example: LP-based scheduling resolves interactions that temporal constraints alone miss, producing timestamps that satisfy both temporal and numeric constraints in the Borrower example.A temporally feasible proposal violates a numeric constraint, whereas joint LP scheduling accounts for discrete effects, continuous effects, and invariants together.
  • Action applicability: COLIN relaxes action-applicability bounds into a filtering test, leaving the subsequent LP consistency check to determine true applicability.The bounds can admit combinations whose timestamp assignments conflict, so filtering removes only actions that are certainly inapplicable.

9. Heuristic Computation

COLIN extends heuristic planning to time-dependent change by modifying temporal relaxed planning graphs to represent continuous and duration-dependent numeric effects. The refined heuristic improves guidance by preserving more accurate information about variable values over time, producing better action choices and makespan estimates.

  • Heuristic extensions: COLIN’s heuristic extends CRIKEY3’s Temporal Relaxed Planning Graph to reason about continuous and duration-dependent effects.The first modification approximates continuous change, while further modifications account for numeric constraints and bound initialization.
  • Basic heuristic: Continuous effects are relaxed as instantaneous start effects using an upper duration bound, while duration-dependent effects select the duration extreme producing the largest or smallest effect.This preserves a relaxed representation while retaining the timing of discrete effects at action starts or ends.
  • Refined heuristic: The refined heuristic attaches continuous gradients and duration-dependent effects to snap-actions, so longer execution accumulates change through the duration coefficient.At an action end, the effect assumes the minimum duration; additional duration contributes a continuous effect derived from the coefficient of the duration variable.
  • Refined heuristic: The refined heuristic advances the TRPG using bounds on variable rates of change and computes when numeric preconditions can become satisfied.This allows the heuristic to reason about evolving variable values rather than treating all continuous effects as immediately available.
  • Borrower problem: The basic heuristic assigns a cost of 5 but abstracts savings as immediately available, delaying the short mortgage and requiring an extra saveHard action.That guidance produces a non-optimal solution with makespan 20 + ... .
  • Borrower problem: The refined heuristic selects the long mortgage and guides the planner to the optimal plan by using more accurate savings values after saveHard starts.Its TRPG has six action layers before the goal, compared with four for the basic heuristic, and estimates a makespan of 12 + ϵ.

10. Improving Performance

COLIN improves performance through one-shot-action reasoning and post hoc optimization of final-plan timing. These techniques exploit action-duration bounds and LP/MILP representations while retaining efficient construction.

  • One-shot actions: One-shot actions let the relaxed planning graph track when continuous effects and duration-dependent effects must terminate.COLIN records remaining execution time and updates it across fact layers, restricting consideration to actions with time remaining.
  • One-shot actions: State-dependent duration bounds are incorporated by allowing one-shot actions to start at the earliest feasible layer and later exploit increased durations.The relaxation preserves both earlier effects and later starts with larger duration bounds.
  • One-shot actions: COLIN’s relaxation is weaker than it might be, but efficient to compute.
  • Plan optimization: Post hoc LP/MILP optimization reschedules the same actions to improve plan quality when timing changes the metric.The LP handles linear metrics, while integer variables support conditional effects on metric-tracking variables.
  • Plan optimization: Metric optimization applies to settings such as aircraft landing targets, satellite observation times, and delays between activities.The approach is useful only when identical action sets can receive different metric values through rescheduling.
  • Plan optimization: Conditional effects on metric-tracking variables preserve propositional outcomes while making numeric costs depend on action duration and timing.Airplane landing actions illustrate how early or late landing can change total-cost without changing whether the plane has landed.

11. Continuous Linear Benchmark Domains

The paper introduces benchmark domains that exercise continuous numeric effects and duration-dependent behavior. These extensions adapt established Rovers, Satellite, AUV, and Airplane Landing tasks to model processes more realistically.

  • Benchmark scope: COLIN’s evaluation required new benchmarks because few existing domains used continuous linear change and non-fixed duration-dependent effects.The authors released domain and problem descriptions to support evaluation and future planner comparisons.
  • Rovers: Rovers replaces instantaneous navigation energy loss with a continuous gradient of −8/5 and an over-all nonnegative-energy condition.The revised model preserves the original net decrease while representing power use throughout the action.
  • Rovers: Journey-recharge uses a duration constraint to model battery charging, allowing charging to stop before restoring full capacity.The revised constraint changes equality to an upper-bound inequality.
  • Satellite: The Satellite domain models illumination as a continuous process whose level affects image-taking duration.Illumination increases in sunlight, decays during drift, and contributes residual effects when an action ends.
  • AUVs: The AUV domain extends continuous numeric reasoning to cooperating underwater vehicles performing sampling and imaging operations.The domain includes waypoint movement and science-gathering activities requiring coordination between vehicles.
  • Airplane Landing: Airplane Landing represents earliest, latest, and target landing times for scheduling aircraft on a runway.

12. Evaluation

COLIN is evaluated against temporal planners, heuristic variants, post hoc scheduling, and optimal planning across temporal and continuous benchmarks. The results show strong plan quality and useful heuristic improvements, alongside computational overheads and scaling limits.

  • Comparison with Existing Temporal Planners: COLIN incurs computation-time overhead on temporal problems without continuous dynamics, especially simple problems where the temporal baseline performs well.The overhead is lower on complex temporal problems, while COLIN produces good-quality plans, particularly there.
  • Heuristic Variants: The refined heuristic has negligible additional cost in Airplane Landing and Rovers, where it produces the same relaxed plans as the basic heuristic.In these domains, limited time-number interaction leaves relaxed-plan selection unchanged despite tracking gradient effects.
  • Heuristic Variants: The refined heuristic generally produces better Satellite Cooled makespans by capturing the relationship between time and numeric variables more precisely.The benefit varies with satellite orientation and required images: minimal reorientation creates the greatest opportunity for improvement.
  • Heuristic Variants: 30 AUV problems are solved with the refined heuristic, compared with 27 using the basic heuristic.A Wilcoxon matched-pairs test rejects the null hypothesis that the refined heuristic is no better on mutually solved problems at p ≤0.05.
  • Heuristic Variants: The refined heuristic improves AUV coverage by accounting for drifting bounds that produce relaxed plans containing otherwise omitted localisation actions.This mechanism explains the difference between the basic and refined approaches in the AUV domain.
  • Post Hoc Plan Optimisation: Post hoc scheduling gives large plan-quality improvements in the Airport burning-fuel variant, while improvements are modest for Airplane Landing.Airplane Landing has fixed landing order, whereas scheduling can place burning-fuel actions later and finish them earlier in the Airport variant.

13. Conclusions

The paper extends planning to continuous effects by combining state progression, consistency checking, and heuristic guidance, while establishing benchmarks for evaluation. It demonstrates the practical relevance of continuous-effects planning but identifies substantial room for improving heuristics, pruning, and expressiveness.

  • Contributions: COLIN uses LP and MILP tools to check state consistency, model progression, compute heuristics, and optimize plan timestamps.These operations support search in the large spaces created by continuous effects.
  • Contributions: The paper contributes benchmark problems that support empirical evaluation of planning with continuous effects.The authors describe benchmark creation and propagation as aids to technological development and comparison.
  • Future work: The approach remains limited by opportunities to improve heuristic informedness, early dead-end pruning, and the range of expressible effects.The paper specifically identifies non-linear continuous effects as an important direction for future work.
  • Significance: Continuous-effects planning is presented as relevant to increasingly complex robotic systems requiring predictive control.The paper positions planning as a possible tool for meeting autonomy demands beyond low-level control strategies.

Appendix B. The Metric Relaxed Planning Graph Heuristic

The metric relaxed planning graph extends relaxed reachability analysis to numeric variables by maintaining optimistic bounds and propagating them through action layers. Its extracted relaxed plan supplies the heuristic estimate and helpful actions.

  • Graph construction: Metric-FF generalizes delete relaxation to numeric variables by maintaining optimistic bounds during relaxed graph expansion.Propositional deletes are ignored, while numeric bounds are updated through relaxed effects.
  • Numeric propagation: At each layer, increasing and decreasing numeric effects are collected using bounds that maximize the relevant direction.The lower and upper bounds of variables are updated from assignment effects and aggregate increases or decreases.
  • Numeric propagation: The next-layer bounds choose between the most extreme single assignment and the sum of all compatible increase or decrease effects.Graph expansion continues after computing bounds for every variable and identifying newly applicable actions.
  • Heuristic extraction: Solution extraction regresses goals through the graph, and the resulting relaxed-plan length becomes h(S).Actions selected from the first action layer also define helpful actions for search restriction.

Appendix C. Temporal Reasoning in Relaxed Planning Graphs

Temporal relaxed planning graphs assign real timestamps to fact and action layers while preserving durative-action ordering, durations, and start–end semantics. They expand only at relevant times and can identify dead ends early.

  • Temporal requirements: Temporal relaxed planning graphs must represent durative-action ordering, delayed end effects, and PDDL2.1 start–end semantics.These requirements distinguish temporal reasoning from ordinary relaxed planning graphs.
  • Temporal heuristic: CRIKEY3 combines duration handling with start–end semantics without the action compression that can create false dead ends under required concurrency.COLIN uses this CRIKEY3 temporal relaxed planning graph as the basis for its heuristic.
  • Initialization: The graph initializes a time-zero fact layer and tracks unfinished action ends that must remain reachable.If the initial state is not already a goal and required ends cannot be reached, the state is treated as a dead end.
  • Layer expansion: Expansion advances to new facts, delayed end times, or timed initial literals rather than creating layers at every epsilon interval.When no further relevant layer exists, the state can be pruned as a dead end.
  • Output: A successfully constructed temporal graph contains finite fact and action layers associated with real time values.Relaxed solution extraction schedules corresponding starts when an end action supports a goal.

Appendix D. Post-Hoc Plan Optimisation

Post-hoc optimization uses mixed-integer constraints to adjust action timestamps so conditional effects triggered by time windows or numeric conditions are represented correctly. The formulation encodes logical satisfaction through binary switch variables.

  • Scope: The MILP construction extends the paper’s post-hoc plan-optimization method to conditional effects dependent on time-specified propositions and numeric conditions.It is presented as an appendix-level elaboration of the MILP construction.
  • Temporal conditions: Binary switch variables encode whether action timestamps fall within specified windows and whether the associated conditions hold.For over-all conditions, both action endpoints must satisfy the relevant window constraints.
  • Objective encoding: When a switch is active, the corresponding conditional reward is added to the plan’s terminal reward variable.The formulation links time-window satisfaction to the objective through k × switch terms.
  • Logical conditions: Conjunctive conditions are represented by additional switch constraints that activate only when every component condition is satisfied.The same mechanism updates the terminal reward when the conjunction holds.
  • Numeric conditions: For linear numeric change, checking values immediately before and after action times is sufficient for over-all conditions.The formulation then uses switch variables to encode whether the numeric condition holds across the required vectors.

D.3 Optimising Time-Dependent Conditions

COLIN extends duration-dependent conditional effects so that action outcomes can depend on duration, with MILP optimization handling the resulting timing choices after a plan is found.

  • Duration-dependent conditional effects allow action conditions and outcomes to refer to an action's duration.
  • The airplane-landing example uses mutually exclusive early and late outcomes selected by duration-dependent conditions.
  • MILP switch variables encode whether the plane lands early or late, linking each outcome to the corresponding timing condition.
  • Duration-dependent conditional effects make the MILP objective quadratic because switch variables multiply duration-dependent terms.
  • The added optimization cost is incurred only once, after a solution plan has been found.

Appendix E. Details of Empirical Evaluation of Colin

The appendix reports runtime and plan-quality comparisons for COLIN and other planners across simple and more complex temporal-planning domains, using figures and tables of best and corresponding results.

  • Figures report solver runtime comparisons for simple and more complex temporal-planning benchmarks.
  • Other figures report plan-quality comparisons across simple and more complex benchmark sets.
  • The evaluation compares COLIN with LPG-td, LPG.s, Sapa, and a temporal baseline planner on temporal-planning benchmarks.
  • A planner absent from a dataset did not solve any problem in that collection.
  • Tables report each domain's best solving time with its corresponding quality, and best quality with its corresponding time.
Loading 1401.5857v1…