Symbolic Numeric Planning with Patterns

• URL: http://arxiv.org/abs/2312.09963v3
• Date: Mon, 12 Feb 2024 09:52:37 GMT
• Title: Symbolic Numeric Planning with Patterns
• Authors: Matteo Cardellini, Enrico Giunchiglia, and Marco Maratea
• Abstract summary: We encode the problem of finding a plan for $Pi$ with bound $n$ as a formula with fewer variables and/or clauses than the state-of-the-art rolled-up and relaxed-relaxed-$exists$ encodings. We show that our planner Patty has remarkably good comparative performances on this year's International Planning Competition.
• Score: 1.450144681559089
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we propose a novel approach for solving linear numeric planning problems, called Symbolic Pattern Planning. Given a planning problem $\Pi$, a bound $n$ and a pattern -- defined as an arbitrary sequence of actions -- we encode the problem of finding a plan for $\Pi$ with bound $n$ as a formula with fewer variables and/or clauses than the state-of-the-art rolled-up and relaxed-relaxed-$\exists$ encodings. More importantly, we prove that for any given bound, it is never the case that the latter two encodings allow finding a valid plan while ours does not. On the experimental side, we consider 6 other planning systems -- including the ones which participated in this year's International Planning Competition (IPC) -- and we show that our planner Patty has remarkably good comparative performances on this year's IPC problems.

Related papers

• Parallel Strategies for Best-First Generalized Planning [51.713634067802104]
  Generalized planning (GP) is a research area of AI that studies the automated synthesis of algorithmic-like solutions capable of solving multiple classical planning instances. One of the current advancements has been the introduction of Best-First Generalized Planning (BFGP), a GP algorithm based on a novel solution space that can be explored with search. This paper evaluates the application of parallel search techniques to BFGP, another critical component in closing the performance gap.
  arXiv  Detail & Related papers  (2024-07-31T09:50:22Z)
• Planning as In-Painting: A Diffusion-Based Embodied Task Planning Framework for Environments under Uncertainty [56.30846158280031]
  Task planning for embodied AI has been one of the most challenging problems. We propose a task-agnostic method named 'planning as in-painting' The proposed framework achieves promising performances in various embodied AI tasks.
  arXiv  Detail & Related papers  (2023-12-02T10:07:17Z)
• Multi-Valued Partial Order Plans in Numeric Planning [14.290119665435121]
  We will start by reformulating a numeric planning problem known as restricted tasks as a search problem. We will then show how an NP-complete fragment of numeric planning can be found by using Booleans. To achieve this, we will develop the idea of multi-valued partial order plans.
  arXiv  Detail & Related papers  (2023-07-27T07:24:30Z)
• Lifted Sequential Planning with Lazy Constraint Generation Solvers [28.405198103927955]
  This paper studies the possibilities made open by the use of Lazy Clause Generation (LCG) based approaches to Constraint Programming (CP) We propose a novel CP model based on seminal ideas on so-called lifted causal encodings for planning as satisfiability. We report that for planning problem instances requiring fewer plan steps our methods compare very well with the state-of-the-art in optimal sequential planning.
  arXiv  Detail & Related papers  (2023-07-17T04:54:58Z)
• Capturing (Optimal) Relaxed Plans with Stable and Supported Models of Logic Programs [4.020523898765405]
  We show that given a planning problem, all subsets of actions that could be ordered to produce relaxed plans for the problem can be captured with stable models of a logic program. We introduce one causal and one diagnostic encoding of the relaxed planning problem as logic programs, both capturing relaxed plans with their supported models.
  arXiv  Detail & Related papers  (2023-06-08T09:34:38Z)
• Gradient-Based Mixed Planning with Discrete and Continuous Actions [34.885999774739055]
  We propose a quadratic-based framework to simultaneously optimize continuous parameters and actions of candidate plans. The framework is combined with a module to estimate the best plan candidate to transit initial state to the goal based on relaxation.
  arXiv  Detail & Related papers  (2021-10-19T14:21:19Z)
• Classical Planning in Deep Latent Space [33.06766829037679]
  Latplan is an unsupervised architecture combining deep learning and classical planning. Latplan finds a plan to the goal state in a symbolic latent space and returns a visualized plan execution.
  arXiv  Detail & Related papers  (2021-06-30T21:31:21Z)
• On Exploiting Hitting Sets for Model Reconciliation [53.81101846598925]
  In human-aware planning, a planning agent may need to provide an explanation to a human user on why its plan is optimal. A popular approach to do this is called model reconciliation, where the agent tries to reconcile the differences in its model and the human's model. We present a logic-based framework for model reconciliation that extends beyond the realm of planning.
  arXiv  Detail & Related papers  (2020-12-16T21:25:53Z)
• Plan2Vec: Unsupervised Representation Learning by Latent Plans [106.37274654231659]
  We introduce plan2vec, an unsupervised representation learning approach that is inspired by reinforcement learning. Plan2vec constructs a weighted graph on an image dataset using near-neighbor distances, and then extrapolates this local metric to a global embedding by distilling path-integral over planned path. We demonstrate the effectiveness of plan2vec on one simulated and two challenging real-world image datasets.
  arXiv  Detail & Related papers  (2020-05-07T17:52:23Z)
• Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
  We consider alternatives to an implicit sequential planning assumption. We propose Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS) for approximating the optimal plan. We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds.
  arXiv  Detail & Related papers  (2020-04-23T18:08:58Z)
• STRIPS Action Discovery [67.73368413278631]
  Recent approaches have shown the success of classical planning at synthesizing action models even when all intermediate states are missing. We propose a new algorithm to unsupervisedly synthesize STRIPS action models with a classical planner when action signatures are unknown.
  arXiv  Detail & Related papers  (2020-01-30T17:08:39Z)

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.