Parallel Strategies for Best-First Generalized Planning

• URL: http://arxiv.org/abs/2407.21485v2
• Date: Fri, 2 Aug 2024 16:58:02 GMT
• Title: Parallel Strategies for Best-First Generalized Planning
• Authors: Alejandro Fernández-Alburquerque, Javier Segovia-Aguas,
• Abstract summary: 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.
• Score: 51.713634067802104
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In recent years, there has been renewed interest in closing the performance gap between state-of-the-art planning solvers and generalized planning (GP), 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 heuristic search, one of the foundations of modern planners. This paper evaluates the application of parallel search techniques to BFGP, another critical component in closing the performance gap. We first discuss why BFGP is well suited for parallelization and some of its differentiating characteristics from classical planners. Then, we propose two simple shared-memory parallel strategies with good scaling with the number of cores.

Related papers

• Novelty and Lifted Helpful Actions in Generalized Planning [14.513354207511151]
  We introduce the notion of action novelty rank, which computes novelty with respect to a planning program. We propose novelty-based generalized planning solvers, which prune a newly generated planning program if its most frequent action repetition is greater than a given bound $v$.
  arXiv  Detail & Related papers  (2023-07-03T03:44:12Z)
• 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)
• 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-up Generalized Planning as Heuristic Search with Landmarks [9.653976364051564]
  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.
  arXiv  Detail & Related papers  (2022-05-10T12:42:48Z)
• 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)
• Incremental Ensemble Gaussian Processes [53.3291389385672]
  We propose an incremental ensemble (IE-) GP framework, where an EGP meta-learner employs an it ensemble of GP learners, each having a unique kernel belonging to a prescribed kernel dictionary. With each GP expert leveraging the random feature-based approximation to perform online prediction and model update with it scalability, the EGP meta-learner capitalizes on data-adaptive weights to synthesize the per-expert predictions. The novel IE-GP is generalized to accommodate time-varying functions by modeling structured dynamics at the EGP meta-learner and within each GP learner.
  arXiv  Detail & Related papers  (2021-10-13T15:11:25Z)
• 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.