LP Heuristics over Conjunctions: Compilation, Convergence, Nogood Learning

Marcel Steinmetz, Jörg HoffmannIJCAI 2018 · DOI

TL;DR

This paper explores how to make Linear Programming (LP) based heuristics for AI planning more powerful by incorporating "conjunctions" – combinations of facts that must hold true together. They introduce a compilation method (IC) that allows these heuristics to converge to the optimal solution and demonstrate its effectiveness in improving the detection of unsolvable planning problems.

What Problem Does This Paper Address?

Classical AI planning aims to find a sequence of actions to reach a goal state from an initial state. Heuristics are crucial for guiding search algorithms, and LP-based heuristics have shown great promise by approximating the cost-to-goal. However, these heuristics often struggle with complex relationships between facts, leading to suboptimal performance. One way to improve them is by considering "conjunctions" of facts, but efficiently integrating these into LP heuristics and ensuring they lead to optimal solutions has been a challenge. This paper addresses how to effectively use conjunctions with LP heuristics, focusing on their convergence properties and their application in "nogood learning" – the process of identifying and learning from unsolvable states.

Methods

The core contribution lies in the IC compilation (inspired by Haslum [2012]) which explicitly represents a set of conjunctions within the planning task. This compilation allows for the development of LP heuristics that are guaranteed to converge to the perfect heuristic ($h^*$) in the limit. The authors also introduce a refinement method for nogood learning that iteratively adds new conjunctions to the set $C$ to improve the heuristic's ability to prune unsolvable states. This method is designed to work with both the state equation heuristic (SEQ) and potential heuristics. They also analyze the properties of potential heuristics derived from this compilation, showing how they can be made consistent and goal-aware.

Datasets

The paper evaluates their approach on the Unsolvability-IPC (UIPC) 2016 benchmarks and unsolvable resource-constrained (RCP) benchmarks.

Key Insights and Ideas

  • IC Compilation for Convergence: The IC compilation is shown to be a powerful tool for ensuring that LP heuristics, when augmented with conjunctions, can eventually converge to the optimal heuristic ($h^*$). This is a significant theoretical result for the expressiveness of LP heuristics.
  • Partial Variable Merges vs. IC Compilation: For tasks in transition normal form (TNF), the paper demonstrates that partial variable merges are strictly dominated by the IC compilation, meaning IC can achieve the same or better results with potentially smaller overhead.
  • Nogood Learning Refinement: The proposed refinement method for nogood learning is effective in identifying new conjunctions that improve the heuristic's ability to prune dead-end states. This is crucial for proving the unsolvability of planning problems.
  • Potential Heuristics and Convergence: The paper shows that potential heuristics derived from the IC compilation can be made consistent and goal-aware. Furthermore, with a suitable upper bound, these potential heuristics can converge to $h^*$ for states below that bound.
  • Practical Impact of Conjunction Order: Experiments highlight that the order in which conjunctions are generated during refinement can significantly impact performance, suggesting that robust strategies need to consider multiple orders.

Key Results

  • The proposed IC compilation and refinement method lead to significant performance improvements in detecting unsolvable planning problems on both UIPC and RCP benchmarks.
  • In the UIPC NoMystery domain, their methods achieve strictly higher coverage than any competitor, albeit by a small margin.
  • Their approach demonstrates near-top performance in both UIPC (LP heuristics strength) and RCP (conjunction learning strength) benchmark categories, a feat not achieved by other configurations.
  • Forward-search nogood learning consistently outperforms proving unsolvability on the initial state.
  • The number of conjunctions needed to prove a state unsolvable is typically small, indicating the efficiency of the learned conjunctions.

Limitations and Future Work

  • Computational Cost of IC Compilation: While the IC compilation enables convergence, it can lead to an exponential increase in the number of actions in the compiled task, which can be computationally expensive. The paper mentions that this can be partially mitigated with mutex information.
  • Conjunction Order Sensitivity: The performance of the refinement method is sensitive to the order in which facts are removed from candidate conjunctions. While they address this by combining multiple orders, it remains an area for potential improvement.
  • Future Work: The authors suggest exploring conjunction refinement for optimal planning within A* search and for satisficing planning heuristics. They also mention investigating conjunction refinement for descending and dead-end avoiding heuristics.

Summary updated

BibTeX
@inproceedings{steinmetz2018lp,
  author = {Marcel Steinmetz and Jörg Hoffmann},
  title = {{LP Heuristics over Conjunctions: Compilation, Convergence, Nogood Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/672},
}
Figure