Search: onr:"swepub:oai:DiVA.org:liu-204189" >
Expressing and Expl...
Expressing and Exploiting Subgoal Structure in Classical Planning Using Sketches
-
- Drexler, Dominik, 1993- (author)
- Linköpings universitet,Artificiell intelligens och integrerade datorsystem,Tekniska fakulteten,University of Freiburg, Freiburg, Germany,AIICS
-
- Seipp, Jendrik (author)
- Linköpings universitet,Artificiell intelligens och integrerade datorsystem,Tekniska fakulteten
-
- Geffner, Hector (author)
- Linköpings universitet,Artificiell intelligens och integrerade datorsystem,Tekniska fakulteten,Rhein Westfal TH Aachen, Germany
-
(creator_code:org_t)
- AI ACCESS FOUNDATION, 2024
- 2024
- English.
-
In: The journal of artificial intelligence research. - : AI ACCESS FOUNDATION. - 1076-9757 .- 1943-5037. ; 80, s. 171-208
- Related links:
-
https://urn.kb.se/re...
-
show more...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- Width-based planning methods deal with conjunctive goals by decomposing problems into subproblems of low width. Algorithms like SIW thus fail when the goal is not easily serializable in this way or when some of the subproblems have a high width. In this work, we address these limitations by using a simple but powerful language for expressing finer problem decompositions introduced recently by Bonet and Geffner, called policy sketches. A policy sketch R over a set of Boolean and numerical features is a set of sketch rules C -> E that express how the values of these features are supposed to change. Like general policies, policy sketches are domain general, but unlike policies, the changes captured by sketch rules do not need to be achieved in a single step. We show that many planning domains that cannot be solved by SIW are provably solvable in low polynomial time with the SIWR algorithm, the version of SIW that employs user-provided policy sketches. Policy sketches are thus shown to be a powerful language for expressing domain-specific knowledge in a simple and compact way and a convenient alternative to languages such as HTNs or temporal logics. Furthermore, they make it easy to express general problem decompositions and prove key properties of them like their width and complexity.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- classical planning
- subgoal structure
- knowledge representation languages
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database