Compiling Temporal Numeric Planning into Discrete PDDL+: Extended Version

This paper presents a practical, polynomial-time compilation method that translates temporal planning with durative actions into the PDDL+ language, fully capturing the semantics while retaining plan length up to a constant factor and demonstrating effectiveness on hard temporal numeric problems.

The Gist

Imagine you are the director of a busy construction site. You have a list of tasks (actions) that need to get done to build a house (the goal). Some tasks are instant, like flipping a switch. Others take time, like pouring concrete or painting a wall.

In the world of Artificial Intelligence planning, there are two different "languages" or rulebooks for managing these tasks:

1. PDDL 2.1 (The "Duration" Rulebook): This is the standard way to describe tasks that take time. You say, "Paint the wall, and it will take 2 hours." The AI has to figure out when to start painting so it doesn't clash with the electrician working on the same wall.
2. PDDL+ (The "Process" Rulebook): This is a more complex, advanced language. Instead of saying "Paint for 2 hours," it describes the world as a flowing river. It uses Processes (things that happen continuously, like water flowing), Events (things that happen instantly when a condition is met, like a bucket overflowing), and Instant Actions (flipping a switch).

The Problem

For years, researchers knew that the "Duration" rulebook (PDDL 2.1) could theoretically be translated into the "Process" rulebook (PDDL+). However, no one had built a practical, working translator that didn't break the rules or lose information. It was like knowing you could translate a novel into a different language, but having no dictionary that actually worked.

The Solution: The "Time-Traveling Translator"

This paper presents a new, practical compiler (a translator) that takes a plan written in the simple "Duration" language and converts it perfectly into the complex "Process" language.

Here is how they did it, using some creative analogies:

1. The "Snap, Process, Snap" Trick

In the old "Duration" language, you just say "Action A takes 5 minutes."
In the new "Process" language, you can't just say "wait." You have to break the action down into three parts:

• The Snap (Start): You flip a switch to start the action.
• The Process (The Middle): A "machine" starts running that slowly ticks a clock and changes the world continuously (like a timer counting down).
• The Snap (End): When the clock hits zero, an "event" triggers to stop the action and clean up.

2. The "Traffic Cop" (The Lock Mechanism)

The hardest part of planning is making sure two workers don't try to use the same tool at the exact same time (e.g., the painter and the electrician both trying to use the same ladder).

• The Analogy: Imagine every tool has a Traffic Light.
  • If you want to read a tool (check if it's there), you need a Green Light.
  • If you want to change a tool (paint it or move it), you need to turn the light Red so no one else can touch it.
• The Magic: The authors created a system where, at every tiny moment in time, a "Reset Button" (an event) turns all the lights back to Green. This ensures that if two workers try to grab the same tool at the exact same split-second, the system catches the conflict and says, "No, you can't do that!" This prevents chaos and ensures the plan is safe.

3. The "Zeno Paradox" Fix

In continuous time, if you try to reset things infinitely fast, you get stuck in a loop (like Zeno's paradox where you never reach the wall because you always have to go half the distance).

• The Fix: The authors decided to treat time as discrete steps (like frames in a movie) rather than a smooth, continuous flow. They use a "time quantum" (a tiny slice of time). This allows the "Reset Button" to work perfectly without causing the system to crash into an infinite loop.

Why Does This Matter? (The Experiment)

The authors didn't just write a theory; they tested it. They took difficult problems involving numbers and time (like managing water resources or sailing boats with deadlines) and ran them through their new translator.

• The Result: They used a powerful PDDL+ planner (called ENHSP) to solve these translated problems.
• The Surprise: The translated problems were solved faster and more often than by the specialized planners designed specifically for the "Duration" language.
• The Takeaway: It turns out that the complex "Process" language, when fed a good translation, is actually a super-powerful engine for solving time-based problems. It's like realizing that a Swiss Army knife (PDDL+) is actually better at cutting wood than a specialized saw (PDDL 2.1), if you know how to use the right attachment.

Summary

This paper is the "Rosetta Stone" for AI planning. It proves that you can take a simple plan involving time and duration, translate it into a more complex language of processes and events, and actually get better results. It solves a 20-year-old puzzle, provides a rigorous mathematical proof that the translation works, and shows that this method is a game-changer for solving hard, real-world scheduling problems.

Technical Summary

1. Problem Statement

The paper addresses the challenge of Temporal Numeric Planning, specifically problems defined in PDDL 2.1 Level 3. These problems involve:

• Durative Actions: Actions that take time to execute, with conditions that must hold at the start, end, and throughout the duration (invariants).
• Numeric Fluents: Continuous variables that change over time.
• Non-Self-Overlapping Constraint: A specific semantic rule where actions cannot overlap with themselves (an action cannot start before a previous instance of the same action finishes).

While it was theoretically known that PDDL 2.1 durative actions could be modeled using PDDL+ (which uses processes, events, and instantaneous actions), no practical, rigorous compilation existed in the literature. Existing approaches relied on direct search in the space of schedules or bounded reductions. The authors aim to bridge this gap by providing a polynomial-time compilation that transforms PDDL 2.1 problems into equivalent PDDL+ problems, allowing the use of powerful PDDL+ planners for temporal numeric tasks.

2. Methodology

The authors propose a formal compilation $\Pi \to \bar{\Pi}$ that maps a temporal planning problem into a PDDL+ problem. The core intuition is to emulate durative actions using a combination of instantaneous actions, processes, and events.

Key Components of the Compilation:

1. State Variables:

   • Lock Predicates: For every fluent $f$, three boolean locks are introduced: rlf (read lock), alf (assignment lock), and ilf (increment lock). These enforce mutual exclusion to prevent interfering actions from occurring simultaneously.
   • Action Tracking:
     • ra: A boolean indicating if durative action $a$ is currently running.
     • ca: A numeric clock tracking the elapsed time since action $a$ started.
     • oc: A counter tracking the number of open (started but not finished) actions.
     • gc: A global clock used to manage time steps and reset locks.
   • Control Flag: An ok predicate that remains true unless a constraint is violated (e.g., invariant failure), effectively "aborting" invalid plans.

2. Encoding Durative Actions:

   • Start (a⊢): An instantaneous action that checks preconditions, sets ra to true, resets ca to 0, and increments oc.
   • Process (pa): A process active while ra is true, continuously increasing ca ($d/dt \ ca = 1$).
   • End (a⊣ or Event e⊣a):
     • For variable duration actions: An instantaneous action triggered by the planner when $la \le ca \le ua$.
     • For fixed duration actions: An event triggered exactly when $ca = la$.
   • Invariant Checking: An event e↔a triggers if ra is true but the invariant $\gamma_a$ is false, setting ok to false (invalidating the plan).

3. Handling Interference (The "Lock" Mechanism):
   To satisfy the non-self-overlapping and non-interference constraints of PDDL 2.1:

   • Every action (start, end, or instantaneous) includes lock preconditions (requiring specific locks to be true) and lock effects (setting specific locks to false).
   • A global process pE continuously increments gc.
   • A global event eE triggers whenever gc > 0, resetting all locks to true and setting gc to 0.
   • Logic: This creates a "superdense" time step where actions execute, locks are set to false, and then eE resets them for the next time step. This prevents two actions from reading/writing the same variable within the same time step without time passing, effectively simulating the discrete semantics required.

4. Discretization:
   The compilation assumes a discrete time quantum $\delta$. The authors prove that for any valid temporal plan, there exists a sufficiently small $\delta$ such that a corresponding valid PDDL+ plan exists.

3. Key Contributions

• First Practical Formal Compilation: Provides the first fully spelled-out, rigorous formal account of compiling PDDL 2.1 durative actions into PDDL+.
• Soundness and Completeness:
  • Soundness: Proves that any valid PDDL+ plan generated by the compiler corresponds to a valid PDDL 2.1 plan.
  • Completeness: Proves that for any valid PDDL 2.1 plan, there exists a discretization $\delta$ that allows the compiler to generate a valid PDDL+ plan.
• Polynomial Complexity: The compilation is polynomial in the size of the input problem, and the resulting plan length increases by at most a constant factor (doubled).
• Handling Complex Features: The method naturally supports numeric state variables, delayed effects, and timed initial literals by leveraging PDDL+ events and processes.

4. Experimental Results

The authors evaluated the compilation on 80 instances across 5 domains (MatchCellar, MaJSP, T-Plant-Wat, T-Sailing, and others), comparing the compiled approach (using the ENHSP planner with Lazy Greedy and $WA^*$ engines) against state-of-the-art native temporal planners (ARIES, NextFLAP, TFLAP, OPTIC, TAMER, Patty).

• Coverage: The ENHSP-WA (Weighted A*) engine achieved the highest coverage (solving 67 out of 80 instances), outperforming all native temporal planners.
• Performance on Numeric Problems: On domains requiring intertwined numeric and temporal reasoning (e.g., MaJSP, T-Plant-Wat), the compiled approach was significantly superior to native planners.
• Complementarity: While native planners were faster on purely temporal domains, the compiled approach excelled in complex numeric scenarios.
• Scalability: The approach demonstrated robust performance, solving difficult instances that other planners timed out on.

5. Significance

• Bridging the Gap: This work demonstrates that PDDL+ is not just a theoretical alternative but a practically superior target for solving complex temporal numeric planning problems.
• Planner Reuse: It allows researchers and practitioners to leverage the advanced heuristics and search capabilities of PDDL+ planners (like ENHSP) for problems originally modeled in PDDL 2.1, without needing to develop new temporal-specific solvers.
• Insight into Planning Difficulties: The results suggest that the core difficulty in temporal numeric planning lies in the interaction between numeric constraints and concurrency, which PDDL+ handles efficiently through its process/event model.
• Future Directions: The authors propose extending this to PDDL 2.1 Level 4 (continuous change) and exploring continuous time semantics for PDDL+ to avoid the discretization assumptions.

In summary, the paper successfully transforms a theoretical equivalence into a practical tool, showing that compiling temporal planning into PDDL+ yields state-of-the-art performance on hard numeric temporal problems.