Scaling-up Generalized Planning as Heuristic Search with Landmarks

• URL: http://arxiv.org/abs/2205.04850v1
• Date: Tue, 10 May 2022 12:42:48 GMT
• Title: Scaling-up Generalized Planning as Heuristic Search with Landmarks
• Authors: Javier Segovia-Aguas, Sergio Jim\'enez, Anders Jonsson and Laura Sebasti\'a
• Abstract summary: Generalized planning is usually addressed as a search in a given space of algorithmic solutions. This type of solution evaluation ignores any sub-goal information that is not explicit in the representation of the planning instances. node expansion in GP is a run-time bottleneck since it requires evaluating every child node over the entire batch of classical planning instances.
• Score: 9.653976364051564
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Landmarks are one of the most effective search heuristics for classical planning, but largely ignored in generalized planning. Generalized planning (GP) is usually addressed as a combinatorial search in a given space of algorithmic solutions, where candidate solutions are evaluated w.r.t.~the instances they solve. This type of solution evaluation ignores any sub-goal information that is not explicit in the representation of the planning instances, causing plateaus in the space of candidate generalized plans. Furthermore, node expansion in GP is a run-time bottleneck since it requires evaluating every child node over the entire batch of classical planning instances in a GP problem. In this paper we define a landmark counting heuristic for GP (that considers sub-goal information that is not explicitly represented in the planning instances), and a novel heuristic search algorithm for GP (that we call PGP) and that progressively processes subsets of the planning instances of a GP problem. Our two orthogonal contributions are analyzed in an ablation study, showing that both improve the state-of-the-art in GP as heuristic search, and that both benefit from each other when used in combination.

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)
• Depth-Bounded Epistemic Planning [50.42592219248395]
  We present a novel algorithm for planning based on dynamic epistemic logic. The novelty is that we limit the depth of reasoning of the planning agent to an upper bound b. We show it to be complete with respect to planning tasks having a solution within bound b of reasoning depth.
  arXiv  Detail & Related papers  (2024-06-03T09:30:28Z)
• Generalized Planning as Heuristic Search: A new planning search-space that leverages pointers over objects [10.850101961203748]
  This paper adapts the planning as search paradigm to the generalization requirements of Generalized Planning (GP) The paper defines a set of evaluation and computation functions for guiding a search in our new GP solution space. An upgraded version of our novel algorithm for GP called Best-First Generalized Planning (BFGP) implements a best-first search in our pointer-based solution space.
  arXiv  Detail & Related papers  (2023-01-26T13:25:39Z)
• Representation and Synthesis of C++ Programs for Generalized Planning [2.752817022620644]
  The paper introduces a novel representation for Generalized Planning (GP) problems, and their solutions, as C++ programs. Our C++ representation allows to formally proving the termination of generalized plans, and to specifying their complexity w.r.t. Characterizing the complexity of C++ generalized plans enables the application of a search that enumerates the space of possible GP solutions in order of complexity.
  arXiv  Detail & Related papers  (2022-06-29T09:13:21Z)
• Computing Programs for Generalized Planning as Heuristic Search [10.850101961203748]
  This paper adapts the planning as search paradigm to the particularities of Generalized Planning (GP) The BFGP algorithm for GP implements a best-first search in our program-based solution space.
  arXiv  Detail & Related papers  (2022-05-12T17:57:09Z)
• Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times [119.41129787351092]
  We show that sequential black-box optimization based on GPs can be made efficient by sticking to a candidate solution for multiple evaluation steps. We modify two well-established GP-Opt algorithms, GP-UCB and GP-EI to adapt rules from batched GP-Opt.
  arXiv  Detail & Related papers  (2022-01-30T20:42:14Z)
• Waypoint Planning Networks [66.72790309889432]
  We propose a hybrid algorithm based on LSTMs with a local kernel - a classic algorithm such as A*, and a global kernel using a learned algorithm. We compare WPN against A*, as well as related works including motion planning networks (MPNet) and value networks (VIN) It is shown that WPN's search space is considerably less than A*, while being able to generate near optimal results.
  arXiv  Detail & Related papers  (2021-05-01T18:02:01Z)
• Generalized Planning as Heuristic Search [12.160708336715489]
  This paper adapts the planning as search paradigm to the particularities of Generalized Planning (GP) The paper defines a novel GP solution space that is independent of number of planning instances in a GP problem, and the size of these instances. Lastly, the paper defines a GP algorithm, called Best-First Generalized Planning (BFGP), that implements a best-first search in the solution space guided by our evaluation/heuristic functions.
  arXiv  Detail & Related papers  (2021-03-26T12:35:10Z)
• 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.