Delete Relaxations for Planning with State-Dependent Action Costs

Florian Geißer, Thomas Keller, Robert MattmüllerIJCAI 2015

Introduction

Classical automated planning typically assumes static action costs. However, real-world scenarios often involve State-Dependent Action Costs (SDAC), where the cost of an action (e.g., fuel consumption) varies based on the current state (e.g., vehicle speed or cargo weight). While SDAC allows for more realistic modeling, it complicates the calculation of effective planning heuristics. Standard delete-relaxation heuristics, which assume monotonic progress, struggle with SDAC because determining the minimum cost path becomes a complex combinatorial problem. Previous solutions often resulted in exponential action blowups or poor performance compared to blind search.

Methodology: Leveraging EVMDDs

To address these challenges, this research generalizes the additive heuristic ($h^{add}$) for SDAC. The core innovation lies in using Edge-Valued Multi-valued Decision Diagrams (EVMDDs) to compactly represent state-dependent cost functions. These diagrams represent functions by branching on variable values, allowing the planner to detect and exploit the internal logic of cost structures.

EVMDD representation of state-dependent cost functions.

The authors propose three primary methods for heuristic computation:

  1. Basic Action Compilation: A naive approach enumerating all state-cost pairs, which is impractical for large domains due to exponential state-space explosion.
  2. EVMDD-Based Action Compilation: This method uses EVMDDs to represent cost functions. By converting the diagram's edges into auxiliary actions, the planner can handle complex costs much more compactly.
  3. Direct RPG Integration: The most advanced method integrates the EVMDD structure directly into the Relaxed Planning Graph (RPG). By introducing the Input-node Augmented Decision Diagram (INADD), the planner can minimize costs across all diagram paths during heuristic evaluation, effectively treating the cost function as a sub-planning task.

Experimental Evaluation

The proposed methods were evaluated on the ACADEMIC ADVISING domain from the 2014 International Probabilistic Planning Competition (IPPC). This domain is notoriously difficult because the "cost" (or reward) of taking a course depends on which prerequisites have already been completed. The performance of the $h^{add}$ implementation was compared against a baseline and the Iterative Deepening Search (IDS) heuristic used in the state-of-the-art PROST planner.

Results and Discussion

The experimental results demonstrate that the EVMDD-based $h^{add}$ heuristic significantly improves scalability and performance on complex planning tasks.

Performance comparison on the Academic Advising domain.

As shown in the performance table, the naive compilation approach is infeasible for anything but the smallest tasks. While the standard IDS heuristic performs well on small problems, its performance degrades as complexity increases, eventually performing worse than the baseline. In contrast, the new $h^{add}$ implementation was the first approach capable of handling the hardest instances of the domain. On Instance 10, the largest task, $h^{add}$ achieved a score of 125.52, significantly outperforming both the baseline (200.00) and IDS (201.51), where lower scores indicate better cost minimization.

Conclusion

By exploiting the internal structure of cost functions through EVMDDs, this work provides a scalable framework for planning with state-dependent costs. The integration of these diagrams into the relaxed planning graph allows for efficient heuristic calculation, enabling the solution of complex problems that were previously intractable. Future work will focus on generalizing other heuristics like $h^{max}$ and automating variable ordering to further optimize EVMDD efficiency.

Summary updated

BibTeX
@inproceedings{geier2015delete,
  author = {Florian Geißer and Thomas Keller and Robert Mattmüller},
  title = {{Delete Relaxations for Planning with State-Dependent Action Costs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure