Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width: Extended Version

• URL: http://arxiv.org/abs/2203.14852v1
• Date: Mon, 28 Mar 2022 15:49:08 GMT
• Title: Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width: Extended Version
• Authors: Dominik Drexler, Jendrik Seipp, Hector Geffner
• Abstract summary: 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.
• Score: 18.95007906887466
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, sketches have been introduced as a general language for representing the subgoal structure of instances drawn from the same domain. Sketches are collections of rules of the form C -> E over a given set of features where C expresses Boolean conditions and E expresses qualitative changes. Each sketch rule defines a subproblem: going from a state that satisfies C to a state that achieves the change expressed by E or a goal state. Sketches can encode simple goal serializations, general policies, or decompositions of bounded width that can be solved greedily, in polynomial time, by the SIW_R variant of the SIW algorithm. Previous work has shown the computational value of sketches over benchmark domains that, while tractable, are challenging for domain-independent planners. In this work, we address the 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. We present a logical formulation of the problem, an implementation using the ASP solver Clingo, and experimental results. The sketch learner and the SIW_R planner yield a domain-independent planner that learns and exploits domain structure in a crisp and explicit form.

Related papers

• Do Generalised Classifiers really work on Human Drawn Sketches? [122.11670266648771]
  This paper marries large foundation models with human sketch understanding. We demonstrate what this brings -- a paradigm shift in terms of generalised sketch representation learning. Our framework surpasses popular sketch representation learning algorithms in both zero-shot and few-shot setups.
  arXiv  Detail & Related papers  (2024-07-04T12:37:08Z)
• 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)
• Abstracting Sketches through Simple Primitives [53.04827416243121]
  Humans show high-level of abstraction capabilities in games that require quickly communicating object information. We propose the Primitive-based Sketch Abstraction task where the goal is to represent sketches using a fixed set of drawing primitives. Our Primitive-Matching Network (PMN), learns interpretable abstractions of a sketch in a self supervised manner.
  arXiv  Detail & Related papers  (2022-07-27T14:32:39Z)
• I Know What You Draw: Learning Grasp Detection Conditioned on a Few Freehand Sketches [74.63313641583602]
  We propose a method to generate a potential grasp configuration relevant to the sketch-depicted objects. Our model is trained and tested in an end-to-end manner which is easy to be implemented in real-world applications.
  arXiv  Detail & Related papers  (2022-05-09T04:23:36Z)
• SketchLattice: Latticed Representation for Sketch Manipulation [30.092468954557468]
  Key challenge in designing a sketch representation lies with handling the abstract and iconic nature of sketches. We propose a lattice structured sketch representation that not only removes the bottleneck of requiring vector data but also preserves the structural cues that vector data provides. Our lattice representation could be effectively encoded using a graph model, that uses significantly fewer model parameters (13.5 times lesser) than existing state-of-the-art.
  arXiv  Detail & Related papers  (2021-08-26T08:02:21Z)
• Domain-Smoothing Network for Zero-Shot Sketch-Based Image Retrieval [66.37346493506737]
  Zero-Shot Sketch-Based Image Retrieval (ZS-SBIR) is a novel cross-modal retrieval task. We propose a novel Domain-Smoothing Network (DSN) for ZS-SBIR. Our approach notably outperforms the state-of-the-art methods in both Sketchy and TU-Berlin datasets.
  arXiv  Detail & Related papers  (2021-06-22T14:58: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)
• 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)
• Sketch-BERT: Learning Sketch Bidirectional Encoder Representation from Transformers by Self-supervised Learning of Sketch Gestalt [125.17887147597567]
  We present a model of learning Sketch BiBERT Representation from Transformer (Sketch-BERT) We generalize BERT to sketch domain, with the novel proposed components and pre-training algorithms. We show that the learned representation of Sketch-BERT can help and improve the performance of the downstream tasks of sketch recognition, sketch retrieval, and sketch gestalt.
  arXiv  Detail & Related papers  (2020-05-19T01:35:44Z)
• Sketchformer: Transformer-based Representation for Sketched Structure [12.448155157592895]
  Sketchformer is a transformer-based representation for encoding free-hand sketches input in a vector form. We report several variants exploring continuous and tokenized input representations, and contrast their performance. Our learned embedding, driven by a dictionary learning tokenization scheme, yields state of the art performance in classification and image retrieval tasks.
  arXiv  Detail & Related papers  (2020-02-24T17:11: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.