Search: onr:"swepub:oai:DiVA.org:liu-205437" >
General Policies, S...
General Policies, Subgoal Structure, and Planning Width
-
- Bonet, Blai (author)
- Univ Pompeu Fabra, Spain
-
- 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. 475-516
- Related links:
-
https://urn.kb.se/re...
-
show more...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- It has been observed that many classical planning domains with atomic goals can be solved by means of a simple polynomial exploration procedure, called IW, that runs in time exponential in the problem width, which in these cases is bounded and small. Yet, while the notion of width has become part of state-of-the-art planning algorithms such as BFWS, there is no good explanation for why so many benchmark domains have bounded width when atomic goals are considered. In this work, we address this question by relating bounded width with the existence of general optimal policies that in each planning instance are represented by tuples of atoms of bounded size. We also define the notions of (explicit) serializations and serialized width that have a broader scope, as many domains have a bounded serialized width but no bounded width. Such problems are solved nonoptimally in polynomial time by a variant of the Serialized IW algorithm. Finally, the language of general policies and the semantics of serializations are combined to yield a simple, meaningful, and expressive language for specifying serializations in compact form in the form of sketches, which can be used for encoding domain control knowledge by hand or for learning it from examples. Sketches express general problem decompositions in terms of subgoals, and terminating sketches of bounded width express problem decompositions that can be solved in polynomial time.
Subject headings
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database