Planning with Numeric Timed Initial Fluents

Chiara Piacentini, Maria Fox, Derek LongAAAI 2015 · DOI

Abstract

Real-world planning scenarios often involve exogenous events where environmental conditions change independently of agent actions. While the Planning Domain Definition Language (PDDL) supports discrete changes via Timed Initial Literals (TILs), many domains require handling continuous or numeric shifts. This paper presents POPF-TIF, an extension of the POPF2 planner designed to manage Numeric Timed Initial Fluents (TIFs). By introducing a novel lookahead heuristic and hybrid search strategies, POPF-TIF effectively addresses complex temporal dependencies in numeric environments.

Introduction

In classical automated planning, the state of the world is typically assumed to be static unless altered by an agent's actions. However, practical applications—such as power grid management or autonomous rover operations—are subject to external factors like fluctuating electricity demand or varying solar intensity. These are known as exogenous events.

While Timed Initial Literals (TILs) allow for propositional "true/false" changes at specific times, they are insufficient for numeric constraints. For instance, in the Unit Commitment Problem (UCP), a planner must balance power generation against a continuously changing demand profile. These Numeric TIFs can violate "active constraints" during the execution of an action, requiring the planner to proactively balance external shifts with internal actions.

Methodology: The POPF-TIF Planner

The authors extend the POPF2 planner with two key innovations to handle the complexities of TIFs.

Lookahead Heuristic Evaluation

Standard planning heuristics, such as the FF relaxed plan, often fail to account for the future impact of TIFs. POPF-TIF modifies the heuristic evaluation to "look ahead" during the extraction of the relaxed plan. If a TIF is predicted to violate a constraint during an active action, that violation is treated as a new goal. This forces the planner to recognize and resolve potential temporal conflicts early in the search process, avoiding "temporal traps" where an action becomes invalid mid-execution.

Hybrid Search Strategies

To balance the speed of Enforced Hill Climbing (EHC) with the robustness of Breadth-First Search (BFS), two hybrid strategies were developed:

  • First Mixed Search (S1): When EHC reaches a dead end, it switches to BFS from the most recent "backup" states. Once a solution or a safe state is identified, it reverts to EHC.
  • Second Mixed Search (S2): Similar to S1, but upon switching to BFS, it initializes the search with the entire queue of previously explored backup states.

Experimental Evaluation

The planner was evaluated across four distinct domains: the Unit Commitment Problem (UCP), a numeric Rover domain, a smart home Temperature domain, and a Skier navigation domain. Each domain included 30 problems designed to test the planner's ability to handle time-varying numeric fluents.

Results and Discussion

The experimental results demonstrate that the lookahead mechanism significantly improves planner performance. As shown in the comparison below, increasing the lookahead depth (from la=0 to la=3) consistently leads to higher coverage (number of problems solved) across all search strategies.

Comparison of search strategies (EHC, BFS, First Mixed Search, Second Mixed Search) showing the impact of lookahead (la) on problem coverage over time.

Key observations from the evaluation include:

  • Heuristic Impact: The EHC strategy showed the most dramatic improvement. Because EHC is a greedy local search, the enhanced "vision" provided by the lookahead heuristic prevents it from entering unsolvable states.
  • Search Robustness: The First Mixed Search (S1) strategy generally provided the best overall coverage, effectively combining local search efficiency with a reliable BFS fallback.
  • TIF Complexity: Unlike propositional TILs, numeric TIFs allow for "balancing" (e.g., raising a value to counteract an external drop), creating a more complex but flexible search space.

Conclusion

POPF-TIF successfully bridges the gap between discrete temporal planning and continuous numeric environments. By incorporating future exogenous events directly into the heuristic evaluation and employing hybrid search techniques, the planner can solve complex real-world problems that were previously intractable. Future work will focus on handling relative TIF changes and more complex background functions.

Summary updated

BibTeX
@inproceedings{piacentini2015planning,
  author = {Chiara Piacentini and Maria Fox and Derek Long},
  title = {{Planning with Numeric Timed Initial Fluents}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9739},
}

Loading related content...

Figure