| Title: |
Potential Heuristics: Weakening Consistency Constraints |
| Authors: |
Lauer, Pascal; Fišer, Daniel |
| Source: |
Proceedings of the International Conference on Automated Planning and Scheduling; Vol. 35 (2025): Proceedings of the Thirty-Fifth International Conference on Automated Planning and Scheduling; 218-222 ; 2334-0843 ; 2334-0835 |
| Publisher Information: |
Association for the Advancement of Artificial Intelligence |
| Publication Year: |
2025 |
| Collection: |
Association for the Advancement of Artificial Intelligence: AAAI Publications |
| Description: |
In classical planning, admissible potential heuristics are computed by solving linear programs (LPs) with constraints expressing consistency and goal-awareness of the heuristic. Potential heuristics can return negative estimates. So, given a potential heuristic h^P, the actual heuristic used in search is another heuristic defined as h^P_0+(s) = max(h^P(s),0) for every reachable state s. In this paper, we reformulate the LP constraints for consistency of h^P so that they ensure consistency of h^P_0+ instead. This leads to more informative heuristics with positive impact on the overall performance in exchange for a more time and memory demanding computation using mixed integer linear programs instead of LPs. |
| Document Type: |
article in journal/newspaper |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
https://ojs.aaai.org/index.php/ICAPS/article/view/36121/38275; https://ojs.aaai.org/index.php/ICAPS/article/view/36121 |
| DOI: |
10.1609/icaps.v35i1.36121 |
| Availability: |
https://ojs.aaai.org/index.php/ICAPS/article/view/36121; https://doi.org/10.1609/icaps.v35i1.36121 |
| Rights: |
Copyright (c) 2024 Association for the Advancement of Artificial Intelligence |
| Accession Number: |
edsbas.18C142EA |
| Database: |
BASE |