Expressing and Exploiting the Common Subgoal Structure of Classical Planning Domains Using Sketches: Extended Version

2021-05-10 · Dominik Drexler, Jendrik Seipp, Hector Geffner

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 over a set of Boolean and numerical features is a set of sketch rules 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 SIW_R 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.

📄 PDF Abstract BibTeX arXiv:2105.04250

Code (0)

등록된 구현이 없습니다.

Enhancing Cognitive Robotics with Commonsense through LLM-Generated Preconditions and Subgoals

2025-11-24 · Ohad Bachner, Bar Gamliel arxiv

Robots often fail at everyday tasks because instructions skip commonsense details like hidden preconditions and small subgoals. Traditional symbolic planners need these details to be written explicitly, which is time con…

Learning and Exploiting Multiple Subgoals for Fast Exploration in Hierarchical Reinforcement Learning

2019-05-13 · Libo Xing

Hierarchical Reinforcement Learning (HRL) exploits temporally extended actions, or options, to make decisions from a higher-dimensional perspective to alleviate the sparse reward problem, one of the most challenging prob…

Hierarchical Reinforcement Learning Montezuma's Revenge reinforcement-learning Reinforcement Learning+1

Probabilistic Subgoal Representations for Hierarchical Reinforcement learning

2024-06-24 · Vivienne Huiling Wang, Tinghuai Wang, Wenyan Yang, Joni-Kristian Kämäräinen 외

In goal-conditioned hierarchical reinforcement learning (HRL), a high-level policy specifies a subgoal for the low-level policy to reach. Effective HRL hinges on a suitable subgoal represen tation function, abstracting s…

Gaussian Processes Hierarchical Reinforcement Learning reinforcement-learning Reinforcement Learning

Subgoal Search For Complex Reasoning Tasks

2021-08-25 · NeurIPS 2021 12 · Konrad Czechowski, Tomasz Odrzygóźdź, Marek Zbysiński, Michał Zawalski 외

Humans excel in solving complex reasoning tasks through a mental process of moving from one idea to a related one. Inspired by this, we propose Subgoal Search (kSubS) method. Its key component is a learned subgoal genera…

Diversity Rubik's Cube Sokoban

Induction and Exploitation of Subgoal Automata for Reinforcement Learning

2020-09-08 · Daniel Furelos-Blanco, Mark Law, Anders Jonsson, Krysia Broda 외

In this paper we present ISA, an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves reinforcement learning with the induction of a subgoal automaton, an automaton…

Inductive logic programming reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)