Homomorphisms and Embeddings of STRIPS Planning Models

• URL: http://arxiv.org/abs/2406.16555v1
• Date: Mon, 24 Jun 2024 11:43:18 GMT
• Title: Homomorphisms and Embeddings of STRIPS Planning Models
• Authors: Arnaud Lequen, Martin C. Cooper, Frédéric Maris,
• Abstract summary: We show that the first is GI-complete, and can thus be solved, in theory, in quasi-polynomial time. While we prove the remaining problems to be NP-complete, we propose an algorithm to build an isomorphism, when possible.
• Score: 4.594173051888471
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Determining whether two STRIPS planning instances are isomorphic is the simplest form of comparison between planning instances. It is also a particular case of the problem concerned with finding an isomorphism between a planning instance $P$ and a sub-instance of another instance $P_0$ . One application of such a mapping is to efficiently produce a compiled form containing all solutions to P from a compiled form containing all solutions to $P_0$. We also introduce the notion of embedding from an instance $P$ to another instance $P_0$, which allows us to deduce that $P_0$ has no solution-plan if $P$ is unsolvable. In this paper, we study the complexity of these problems. We show that the first is GI-complete, and can thus be solved, in theory, in quasi-polynomial time. While we prove the remaining problems to be NP-complete, we propose an algorithm to build an isomorphism, when possible. We report extensive experimental trials on benchmark problems which demonstrate conclusively that applying constraint propagation in preprocessing can greatly improve the efficiency of a SAT solver.

Related papers

• Intermediate Results on the Complexity of STRIPS$_{1}^{1}$ [4.706932040794695]
  It is unknown whether propositional STRIPS with operators that only have one precondition and one effect is NP-complete.<n>We call a SAT solver for small instances, introducing the literal graph, and mapping it to Petri nets.
  arXiv  Detail & Related papers  (2026-02-09T14:21:10Z)
• PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
  We propose PlanGEN, a model-agnostic and easily scalable agent framework with three key components: constraint, verification, and selection agents. Specifically, our approach proposes constraint-guided iterative verification to enhance performance of inference-time algorithms.
  arXiv  Detail & Related papers  (2025-02-22T06:21:56Z)
• Autoformulation of Mathematical Optimization Models Using LLMs [50.030647274271516]
  This paper approaches the problem of $textitautoformulation$: the automated creation of solver-ready optimization models from natural language problem descriptions.<n>We identify three core challenges of autoformulation: $textit(1)$ the vast, problem-dependent hypothesis space, and $textit(2)$ efficient and diverse exploration of this space under uncertainty.<n>We present a novel method leveraging $textitLarge Language Models$ with $textitMonte-Carlo Tree Search$, exploiting the hierarchical nature of optimization modeling to generate and systematically explore possible formulations
  arXiv  Detail & Related papers  (2024-11-03T20:41:38Z)
• Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models [4.007697401483925]
  We construct and compare algorithmic approaches to solve the Consistency Problem for preference statements based on hierarchical models. An instance is consistent if there exists an hierarchical model on the evaluation functions that induces an order relation on the alternatives. We develop three approaches to solve this decision problem.
  arXiv  Detail & Related papers  (2024-10-31T13:48:46Z)
• A $Δ$-evaluation function for column permutation problems [0.0]
  A new $Delta$-evaluation method is introduced for solving a column permutation problem defined on a sparse binary matrix with the consecutive ones property. This problem models various $mathcalNP$-hard problems in graph theory and industrial manufacturing contexts. The proposed evaluation method is generally competitive and particularly useful for large and dense instances.
  arXiv  Detail & Related papers  (2024-09-07T22:50:25Z)
• Sequence graphs realizations and ambiguity in language models [1.3108652488669736]
  Several popular language models represent local contexts in an input text $x$ as bags of words.<n>Some may be ambiguous, admitting several realizations as a sequence, while others may not admit any realization.<n>We study the realizability and ambiguity of sequence graphs from a and algorithmic point of view.
  arXiv  Detail & Related papers  (2024-02-13T22:22:51Z)
• A Fast Algorithm for Consistency Checking Partially Ordered Time [9.594432031144716]
  We consider the problem of deciding if a (likely incomplete) description of a system of events is consistent. While the classical complexity of this problem has been fully settled, comparably little is known of the fine-grained complexity of POT. We construct a much faster algorithm with a run-time bounded by $O*((0.26n)n)$.
  arXiv  Detail & Related papers  (2023-05-25T10:36:49Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  Many real-world problems have complicated non functional constraints and use a large number of data points. Our proposed method outperforms an existing method with the previously best-known result.
  arXiv  Detail & Related papers  (2022-12-19T14:48:54Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• Asymptotic Instance-Optimal Algorithms for Interactive Decision Making [35.76184529520015]
  In this paper, we design the first instance-optimal algorithm for general interactive decision making problems with finite number of decisions under mild conditions. Our results, instantiated on concrete problems, recover the classical gap-dependent bounds for multi-armed bandits and prior works on linear bandits.
  arXiv  Detail & Related papers  (2022-06-06T02:56:10Z)
• Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
  Dynamic programming (DP) is an algorithmic design paradigm for the efficient, exact solution of intractable, problems. This paper presents a rigorous algebraic formalism for systematically deriving DP algorithms, based on semiring.
  arXiv  Detail & Related papers  (2021-07-05T00:51:02Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classes is a new structural framework which permits generalization in reinforcement learning. The framework incorporates nearly all existing models in which a sample complexity is achievable. Our main result provides an RL algorithm which has sample complexity for Bilinear Classes.
  arXiv  Detail & Related papers  (2021-03-19T16:34:20Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  We present a differentially private learner for halfspaces over a finite grid $G$ in $mathbbRd$ with sample complexity $approx d2.5cdot 2log*|G|$. The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem.
  arXiv  Detail & Related papers  (2020-04-16T16:12:10Z)
• MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
  convex mixed-integer programming formulation for non-rigid shape matching. We propose a novel shape deformation model based on an efficient low-dimensional discrete model.
  arXiv  Detail & Related papers  (2020-02-28T09:54:06Z)

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.