Representation and Synthesis of C++ Programs for Generalized Planning
- URL: http://arxiv.org/abs/2206.14480v1
- Date: Wed, 29 Jun 2022 09:13:21 GMT
- Title: Representation and Synthesis of C++ Programs for Generalized Planning
- Authors: Javier Segovia-Aguas, Yolanda E-Mart\'in, Sergio Jim\'enez
- Abstract summary: 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.
- Score: 2.752817022620644
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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 asymptotic complexity w.r.t. the number of world objects. Characterizing
the complexity of C++ generalized plans enables the application of a
combinatorial search that enumerates the space of possible GP solutions in
order of complexity. Experimental results show that our implementation of this
approach, which we call BFGP++, outperforms the previous GP as heuristic search
approach for the computation of generalized plans represented as
compiler-styled programs. Last but not least, the execution of a C++ program on
a classical planning instance is a deterministic grounding-free and search-free
process, so our C++ representation allows us to automatically validate the
computed solutions on large test instances of thousands of objects, where
off-the-shelf classical planners get stuck either in the pre-processing or in
the search.
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) - Origami: (un)folding the abstraction of recursion schemes for program
synthesis [0.0]
Genetic Programming searches for a correct program that satisfies the input specification.
One particular challenge is how to handle loops and recursion avoiding programs that never terminate.
Recursion Schemes generalize the combination of data production and consumption.
arXiv Detail & Related papers (2024-02-21T14:17:45Z) - Recursive Visual Programming [53.76415744371285]
We propose Recursive Visual Programming (RVP), which simplifies generated routines, provides more efficient problem solving, and can manage more complex data structures.
We show RVP's efficacy through extensive experiments on benchmarks including VSR, COVR, GQA, and NextQA.
arXiv Detail & Related papers (2023-12-04T17:27:24Z) - ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis [54.18659323181771]
We characterize several different forms of compositional generalization that are desirable in program synthesis.
We propose ExeDec, a novel decomposition-based strategy that predicts execution subgoals to solve problems step-by-step informed by program execution at each step.
arXiv Detail & Related papers (2023-07-26T01:07:52Z) - 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) - A Divide-Align-Conquer Strategy for Program Synthesis [8.595181704811889]
We show that compositional segmentation can be applied in the programming by examples setting to divide the search for large programs across multiple smaller program synthesis problems.
A structural alignment of the constituent parts in the input and output leads to pairwise correspondences used to guide the program search.
arXiv Detail & Related papers (2023-01-08T19:10:55Z) - 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) - Searching for More Efficient Dynamic Programs [61.79535031840558]
We describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a search procedure to improve this metric.
We show that in practice, automated search can find substantial improvements to the initial program.
arXiv Detail & Related papers (2021-09-14T20:52:55Z) - Representing Partial Programs with Blended Abstract Semantics [62.20775388513027]
We introduce a technique for representing partially written programs in a program synthesis engine.
We learn an approximate execution model implemented as a modular neural network.
We show that these hybrid neuro-symbolic representations enable execution-guided synthesizers to use more powerful language constructs.
arXiv Detail & Related papers (2020-12-23T20:40:18Z) - Parallel Scheduling Self-attention Mechanism: Generalization and
Optimization [0.76146285961466]
We propose a general scheduling algorithm, which is derived from the optimum scheduling for small instances solved by a satisfiability checking(SAT) solver.
Strategies for further optimization on skipping redundant computations are put forward as well, with which reductions of almost 25% and 50% of the original computations are respectively achieved.
The proposed algorithms are applicable regardless of problem sizes, as long as the number of input vectors is divisible to the number of computing units available in the architecture.
arXiv Detail & Related papers (2020-12-02T12:04:16Z) - 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.