General Policies, Serializations, and Planning Width

• URL: http://arxiv.org/abs/2012.08033v2
• Date: Wed, 23 Dec 2020 16:14:01 GMT
• Title: General Policies, Serializations, and Planning Width
• Authors: Blai Bonet and Hector Geffner
• Abstract summary: 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.
• Score: 22.112881443209726
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: It has been observed that in many of the benchmark planning domains, atomic goals can be reached with a simple polynomial exploration procedure, called IW, that runs in time exponential in the problem width. Such problems have indeed a bounded width: a width that does not grow with the number of problem variables and is often no greater than two. Yet, while the notion of width has become part of the state-of-the-art planning algorithms like BFWS, there is still no good explanation for why so many benchmark domains have bounded width. In this work, we address this question by relating bounded width and serialized width to ideas of generalized planning, where general policies aim to solve multiple instances of a planning problem all at once. 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 results are extended to much larger class of domains with bounded serialized width where the general policies do not have to be optimal. The study leads also to a new simple, meaningful, and expressive language for specifying domain serializations in the form of policy sketches which can be used for encoding domain control knowledge by hand or for learning it from traces. The use of sketches and the meaning of the theoretical results are all illustrated through a number of examples.

Related papers

• DGMamba: Domain Generalization via Generalized State Space Model [80.82253601531164]
  Domain generalization(DG) aims at solving distribution shift problems in various scenes. Mamba, as an emerging state space model (SSM), possesses superior linear complexity and global receptive fields. We propose a novel framework for DG, named DGMamba, that excels in strong generalizability toward unseen domains.
  arXiv  Detail & Related papers  (2024-04-11T14:35:59Z)
• 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)
• General Policies, Subgoal Structure, and Planning Width [19.373790756767278]
  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.
  arXiv  Detail & Related papers  (2023-11-09T16:30:22Z)
• Multi-Domain Long-Tailed Learning by Augmenting Disentangled Representations [80.76164484820818]
  There is an inescapable long-tailed class-imbalance issue in many real-world classification problems. We study this multi-domain long-tailed learning problem and aim to produce a model that generalizes well across all classes and domains. Built upon a proposed selective balanced sampling strategy, TALLY achieves this by mixing the semantic representation of one example with the domain-associated nuisances of another.
  arXiv  Detail & Related papers  (2022-10-25T21:54:26Z)
• Single-domain Generalization in Medical Image Segmentation via Test-time Adaptation from Shape Dictionary [64.5632303184502]
  Domain generalization typically requires data from multiple source domains for model learning. This paper studies the important yet challenging single domain generalization problem, in which a model is learned under the worst-case scenario with only one source domain to directly generalize to different unseen target domains. We present a novel approach to address this problem in medical image segmentation, which extracts and integrates the semantic shape prior information of segmentation that are invariant across domains.
  arXiv  Detail & Related papers  (2022-06-29T08:46:27Z)
• 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)
• Compound Domain Generalization via Meta-Knowledge Encoding [55.22920476224671]
  We introduce Style-induced Domain-specific Normalization (SDNorm) to re-normalize the multi-modal underlying distributions. We harness the prototype representations, the centroids of classes, to perform relational modeling in the embedding space. Experiments on four standard Domain Generalization benchmarks reveal that COMEN exceeds the state-of-the-art performance without the need of domain supervision.
  arXiv  Detail & Related papers  (2022-03-24T11:54:59Z)
• 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)
• Generalizing to Unseen Domains: A Survey on Domain Generalization [59.16754307820612]
  Domain generalization deals with a challenging setting where one or several different but related domain(s) are given. The goal is to learn a model that can generalize to an unseen test domain. This paper presents the first review for recent advances in domain generalization.
  arXiv  Detail & Related papers  (2021-03-02T06:04:11Z)
• Hierarchical Width-Based Planning and Learning [8.776765645845012]
  Width-based search methods have demonstrated state-of-the-art performance in a wide range of testbeds. We present a hierarchical algorithm that plans at two levels of abstraction. We show how in combination with a learned policy and a learned value function, the proposed hierarchical IW can outperform current flat IW-based planners in Atari games with sparse rewards.
  arXiv  Detail & Related papers  (2021-01-15T15:37:46Z)
• Learning General Policies from Small Examples Without Supervision [18.718037284357834]
  Generalized planning is concerned with the computation of general policies that solve multiple instances of a planning domain all at once. It has been recently shown that these policies can be computed in two steps: first, a suitable abstraction in the form of a qualitative numerical planning problem (QNP) is learned from sample plans. In this work, we introduce an alternative approach for computing more expressive general policies which does not require sample plans or a QNP planner.
  arXiv  Detail & Related papers  (2021-01-03T19:44:13Z)

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.