Temporal Planning for Interacting Durative Actions with Continuous Effects

Serdar Kecici, Sanem Sariel TalayAAAI 2010 · DOI

Abstract

Standard temporal planners often fail to find optimal solutions because they restrict action starts to specific "decision epochs"—typically the end points of previous actions. This paper introduces action lifting, a technique that decouples action selection from immediate temporal grounding. By allowing planners to commit to actions without pinning them to a specific start time, the proposed method enables the discovery of optimal schedules in complex environments where agents share continuous resources, such as narrow corridors.

Introduction

In automated planning, temporal planners must determine both the sequence and the timing of actions. Most forward-chaining planners simplify this search by only considering decision epochs: specific moments in time when a currently running action finishes. However, this discretization creates a "blind spot" in domains with continuous linear effects. For example, if two robots share a narrow hallway, a standard planner might wait for the first robot to completely exit before starting the second. In reality, the second robot could often enter safely at an intermediate time. This limitation leads to sub-optimal plans with unnecessarily long total durations (makespans).

Methodology: Action Lifting

To address the sub-optimality of epoch-based planning, we propose an extension to the TLPLAN system incorporating Action Lifting. This approach uses four successor generators to explore the search space more flexibly:

  1. Schedule: Apply an action immediately at the current world clock.
  2. Advance Clock: Progress the world clock to the next scheduled decision epoch.
  3. Lift: Select an action to perform but leave its start time "open" by adding it to a set of lifted actions.
  4. Ground: Anchor a previously lifted action to the earliest valid start time between the previous and current decision epochs.

By "lifting" an action, the planner defers temporal commitment, allowing it to "fill in the gaps" between discrete events once the surrounding timeline is better defined.

Experimental Evaluation: The Path Sharing Problem

The approach was evaluated using a custom Path Sharing Problem. The environment consists of eight rooms (R0–R7) connected by a single, one-lane corridor.

The Path Sharing Problem environment featuring eight rooms connected by a central one-lane corridor.

In this domain, multiple agents must navigate from start to goal rooms without colliding. The corridor's availability is treated as a continuous resource defined by agent speed, entrance/exit positions, and start times. This formulation allows for granular scheduling, such as agents following each other at safe intervals rather than waiting for the corridor to be entirely vacant.

Results and Discussion

The extended TLPLAN successfully identifies makespan-optimal solutions where standard planners fail. The core advantage lies in overcoming the "Decision Epoch Trap."

Comparison of standard vs. lifted scheduling. Standard planners wait until t2 to start Agent 2, while action lifting allows a start at t1.

As illustrated in the figure above, a standard planner forces Agent 2 to wait until Agent 1 has finished its move at $t_2$. The "Lifted" version recognizes that Agent 2 can safely begin its movement at an intermediate time $t_1$. By grounding the lifted action at the earliest possible valid timestamp, the planner minimizes the total plan duration.

Conclusion and Future Work

Action lifting restores completeness to temporal planning in continuous domains, ensuring the discovery of optimal schedules. However, this flexibility increases computational complexity by expanding the search branching factor. Future research will focus on pruning techniques to identify temporally identical states and the development of more sophisticated heuristics to guide the planner toward optimal solutions more efficiently.

Summary updated

BibTeX
@inproceedings{kecici2010temporal,
  author = {Serdar Kecici and Sanem Sariel Talay},
  title = {{Temporal Planning for Interacting Durative Actions with Continuous Effects}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7785},
}
Figure