General Policies, Subgoal Structure, and Planning Width
- URL: http://arxiv.org/abs/2311.05490v1
- Date: Thu, 9 Nov 2023 16:30:22 GMT
- Title: General Policies, Subgoal Structure, and Planning Width
- Authors: Blai Bonet and Hector Geffner
- Abstract summary: It has been observed that planning domains with atomic goals can be solved by means of a simple exploration procedure, called IW, that runs in time exponential in the problem width.
Yet, there is no good explanation for why so many benchmark domains have bounded width when atomic goals are considered.
- Score: 19.373790756767278
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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 non-optimally in polynomial time by a suitable 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 small examples. Sketches express general problem
decompositions in terms of subgoals, and sketches of bounded width express
problem decompositions that can be solved in polynomial time.
Related papers
- Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models [79.70436109672599]
We derive non-vacuous generalization bounds for large language models as large as LLaMA2-70B.
Our work achieves the first non-vacuous bounds for models that are deployed in practice and generate high-quality text.
arXiv Detail & Related papers (2024-07-25T16:13:58Z) - Improving Retrieval Augmented Open-Domain Question-Answering with Vectorized Contexts [83.57864140378035]
This paper proposes a method to cover longer contexts in Open-Domain Question-Answering tasks.
It leverages a small encoder language model that effectively encodes contexts, and the encoding applies cross-attention with origin inputs.
After fine-tuning, there is improved performance across two held-in datasets, four held-out datasets, and also in two In Context Learning settings.
arXiv Detail & Related papers (2024-04-02T15:10:11Z) - Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications [8.438718130535296]
We prove upper bounds on the covering number of sets in Euclidean space.
We show that bounds improve the best known general bound by Yomdin-Comte.
We illustrate the power of the result on three computational applications.
arXiv Detail & Related papers (2023-11-09T03:06:59Z) - Toward Unified Controllable Text Generation via Regular Expression
Instruction [56.68753672187368]
Our paper introduces Regular Expression Instruction (REI), which utilizes an instruction-based mechanism to fully exploit regular expressions' advantages to uniformly model diverse constraints.
Our method only requires fine-tuning on medium-scale language models or few-shot, in-context learning on large language models, and requires no further adjustment when applied to various constraint combinations.
arXiv Detail & Related papers (2023-09-19T09:05:14Z) - Text Reading Order in Uncontrolled Conditions by Sparse Graph
Segmentation [71.40119152422295]
We propose a lightweight, scalable and generalizable approach to identify text reading order.
The model is language-agnostic and runs effectively across multi-language datasets.
It is small enough to be deployed on virtually any platform including mobile devices.
arXiv Detail & Related papers (2023-05-04T06:21:00Z) - Decidability of Querying First-Order Theories via Countermodels of Finite Width [3.712362524473752]
We propose a generic framework for establishing the decidability of a wide range of logical entailment problems (briefly called querying)
We identify logics exhibiting width-finite finitely universal model sets, warranting decidable entailment for a wide range of homomorphism-closed queries.
We explain how finite partitionwidth sets of rules subsume other known abstract decidable classes but - leveraging existing notions of stratification - also cover a wide range of new rulesets.
arXiv Detail & Related papers (2023-04-13T08:57:17Z) - Learning Sketches for Decomposing Planning Problems into Subproblems of
Bounded Width: Extended Version [18.95007906887466]
Sketches have been introduced as a general language for representing the subgoal structure of instances drawn from the same domain.
We present a problem of learning sketches automatically given a planning domain, some instances of the target class of problems, and the desired bound on the sketch width.
The sketch learner and SIW_R planner yield a domain-independent planner that learns and exploits domain structure in a crisp and explicit form.
arXiv Detail & Related papers (2022-03-28T15:49:08Z) - Expressing and Exploiting the Common Subgoal Structure of Classical
Planning Domains Using Sketches: Extended Version [17.63517562327928]
We use a simple but powerful language for expressing problem decompositions introduced recently by Bonet and Geffner, called policy sketches.
A policy sketch R consists of a set of Boolean and numerical features and a set of sketch rules that express how the values of these features are supposed to change.
We show that many planning domains that cannot be solved by SIW are provably solvable in low time with the SIW_R algorithm.
arXiv Detail & Related papers (2021-05-10T10:36:18Z) - InfinityGAN: Towards Infinite-Resolution Image Synthesis [92.40782797030977]
We present InfinityGAN, a method to generate arbitrary-resolution images.
We show how it trains and infers patch-by-patch seamlessly with low computational resources.
arXiv Detail & Related papers (2021-04-08T17:59:30Z) - General Policies, Serializations, and Planning Width [22.112881443209726]
We show that bounded width is a property of planning domains that admit optimal general policies in terms of features that are explicitly or implicitly represented in the domain encoding.
The study leads also to a new simple, meaningful, and expressive language for specifying domain serializations in the form of policy sketches.
arXiv Detail & Related papers (2020-12-15T01:33:59Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
We present a general framework for mining constraints from data.
In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem.
We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
arXiv Detail & Related papers (2020-06-18T20:09:53Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.