{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T07:01:14Z","timestamp":1762326074152,"version":"build-2065373602"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:p>Saturated cost partitioning (SCP) is one of the strongest\n\nmethods for admissibly combining heuristics for optimal\n\nclassical planning. The quality of an SCP heuristic depends\n\nheavily on the order in which its component heuristics are\n\nconsidered. For high accuracy, it is essential to maximize\n\nover multiple SCP heuristics computed using different\n\ncomponent orders. However, for n component heuristics, even\n\nenumerating all n! orders is usually infeasible.\n\nConsequently, previous work resorted to using greedy\n\nalgorithms and local optimization. In contrast, we present\n\nthe first practical method for computing the perfect SCP\n\nheuristic that is equivalent to considering all component\n\norders. We show that a set of SCP heuristics forms an\n\nadditive disjunctive heuristic, which allows us to\n\nconcisely represent component orders as a directed acyclic\n\ngraph. Furthermore, once certain components have been\n\nconsidered, the order of the remaining components often\n\nbecomes irrelevant. By exploiting this characteristic, we\n\ncan reduce the size of the heuristic representation by\n\nseveral orders of magnitude in practice. Finally, our work\n\nmakes it possible to compare the quality of existing SCP\n\nmethods with that of the perfect SCP heuristic, revealing\n\nthat existing approximations are nearly optimal for\n\nstandard benchmarks.<\/jats:p>","DOI":"10.24963\/kr.2025\/79","type":"proceedings-article","created":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:10:44Z","timestamp":1762323044000},"page":"821-831","source":"Crossref","is-referenced-by-count":0,"title":["Representing Perfect Saturated Cost Partitioning Heuristics in Classical Planning"],"prefix":"10.24963","author":[{"given":"Paul","family":"H\u00f6ft","sequence":"first","affiliation":[{"name":"Link\u00f6ping University"}]},{"given":"David","family":"Speck","sequence":"additional","affiliation":[{"name":"University of Basel"}]},{"given":"Jendrik","family":"Seipp","sequence":"additional","affiliation":[{"name":"Link\u00f6ping University"}]}],"member":"10584","event":{"name":"22nd International Conference on Principles of Knowledge Representation and Reasoning {KR-2025}","theme":"Artificial Intelligence","location":"Melbourne, Australia","acronym":"KR-2025","number":"22","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Academic College of Tel-Aviv","European Association for Artificial Intelligence","National Science Foundation"],"start":{"date-parts":[[2025,11,11]]},"end":{"date-parts":[[2025,11,17]]}},"container-title":["Proceedings of the TwentySecond International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:11:26Z","timestamp":1762323086000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2025\/79"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2025,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2025\/79","relation":{},"subject":[],"published":{"date-parts":[[2025,11]]}}}