On the generalization of learned constraints for ASP solving in temporal domains

• URL: http://arxiv.org/abs/2401.16124v2
• Date: Tue, 15 Oct 2024 11:19:21 GMT
• Title: On the generalization of learned constraints for ASP solving in temporal domains
• Abstract summary: A key factor in the performance of today's ASP solvers is conflict-driven constraint learning. We study conditions under which learned dynamic constraints can be generalized. We empirically evaluate the impact of adding the generalized constraints to an ASP solver.
• Score: 2.094218274474807
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The representation of a dynamic problem in ASP usually boils down to using copies of variables and constraints, one for each time stamp, no matter whether it is directly encoded or via an action or temporal language. The multiplication of variables and constraints is commonly done during grounding and the solver is completely ignorant about the temporal relationship among the different instances. On the other hand, a key factor in the performance of today's ASP solvers is conflict-driven constraint learning. Our question is now whether a constraint learned for particular time steps can be generalized and reused at other time stamps, and ultimately whether this enhances the overall solver performance on temporal problems. Knowing full well the domain of time, we study conditions under which learned dynamic constraints can be generalized. We propose a simple translation of the original logic program such that, for the translated programs, the learned constraints can be generalized to other time points. Additionally, we identify a property of temporal problems that allows us to generalize all learned constraints to all time steps. It turns out that this property is satisfied by many planning problems. Finally, we empirically evaluate the impact of adding the generalized constraints to an ASP solver. Under consideration in Theory and Practice of Logic Programming (TPLP).

Related papers

• Translating finite-domain integer constraint models to CP/SMT/ILP/PB/SAT solvers with CPMpy [6.498850269638911]
  Constraint solving is a declarative approach for solving satisfaction and optimization problems.<n>Our goal is to translate high-level constraint satisfaction and optimization problems into any lower-level formalism.<n>We present a modular framework for transforming our high-level modeling language to CP/SMT/ILP/PB and (Max)SAT solvers.
  arXiv  Detail & Related papers  (2026-08-15T09:38:09Z)
• AdapTime: Enabling Adaptive Temporal Reasoning in Large Language Models [65.97075015662318]
  AdapTime is an adaptive temporal reasoning method that dynamically executes reasoning steps based on the input context.<n>It integrates seamlessly with state-of-the-art LLMs and significantly enhances their temporal reasoning capabilities without relying on external support.
  arXiv  Detail & Related papers  (2026-04-27T08:34:40Z)
• Implementing Metric Temporal Answer Set Programming [0.9865428250766767]
  A central challenge is to maintain scalability when dealing with fine-grained timing constraints.<n>We leverage extensions of ASP with difference constraints, a simplified form of linear constraints, to handle time-related aspects externally.<n>Our approach effectively decouples metric ASP from the granularity of time, resulting in a solution that is unaffected by time precision.
  arXiv  Detail & Related papers  (2026-01-28T16:07:54Z)
• Temp-R1: A Unified Autonomous Agent for Complex Temporal KGQA via Reverse Curriculum Reinforcement Learning [51.79753403262177]
  Temporal Knowledge Graph Question Answering (TKGQA) is inherently challenging, as it requires sophisticated reasoning over dynamic facts with multi-hop dependencies and complex temporal constraints.<n>We propose Temp-R1, the first autonomous end-to-end agent for TKGQA trained through reinforcement learning.<n>Our 8B- parameter Temp-R1 achieves state-of-the-art performance on MultiTQ and TimelineKGQA, improving 19.8% over strong baselines on complex questions.
  arXiv  Detail & Related papers  (2026-01-26T09:23:53Z)
• Programming over Thinking: Efficient and Robust Multi-Constraint Planning [54.77940831026738]
  SCOPE is a framework that disentangles query-specific reasoning from generic code execution.<n>SCOPE achieves state-of-the-art performance while lowering cost and latency.
  arXiv  Detail & Related papers  (2026-01-14T02:58:07Z)
• GPU Accelerated Compact-Table Propagation [1.7249361224827533]
  This work focuses on a specific form of constraint, the so-called table constraint, used to specify conditions on the values of variables as an enumeration of alternative options.<n>Since every condition on a set of finite domain variables can be ultimately expressed as a finite set of cases, Table can, in principle, simulate any other constraint.<n>In this paper, we deal with the Compact-Table (CT) algorithm, the state-of-the-art propagation algorithms for Table.
  arXiv  Detail & Related papers  (2025-07-24T13:53:49Z)
• Compiling Metric Temporal Answer Set Programming [2.3861066707217202]
  A central challenge is to maintain scalability when dealing with fine-grained timing constraints.<n>We leverage extensions of ASP with difference constraints, a simplified form of linear constraints, to handle time-related aspects externally.<n>Our approach effectively decouples metric ASP from the granularity of time, resulting in a solution that is unaffected by time precision.
  arXiv  Detail & Related papers  (2025-06-09T18:56:57Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive. LCD can distort the global distribution over strings, sampling tokens based only on local information. We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30:18Z)
• From Instructions to Constraints: Language Model Alignment with Automatic Constraint Verification [70.08146540745877]
  We investigate common constraints in NLP tasks, categorize them into three classes based on the types of their arguments. We propose a unified framework, ACT (Aligning to ConsTraints), to automatically produce supervision signals for user alignment with constraints.
  arXiv  Detail & Related papers  (2024-03-10T22:14:54Z)
• ConstraintChecker: A Plugin for Large Language Models to Reason on Commonsense Knowledge Bases [53.29427395419317]
  Reasoning over Commonsense Knowledge Bases (CSKB) has been explored as a way to acquire new commonsense knowledge. We propose **ConstraintChecker**, a plugin over prompting techniques to provide and check explicit constraints.
  arXiv  Detail & Related papers  (2024-01-25T08:03:38Z)
• Towards Robust Temporal Reasoning of Large Language Models via a Multi-Hop QA Dataset and Pseudo-Instruction Tuning [73.51314109184197]
  It is crucial for large language models (LLMs) to understand the concept of temporal knowledge. We propose a complex temporal question-answering dataset Complex-TR that focuses on multi-answer and multi-hop temporal reasoning.
  arXiv  Detail & Related papers  (2023-11-16T11:49:29Z)
• Toward Unified Controllable Text Generation via Regular Expression Instruction [56.68753672187368]
  Our paper introduces Regular Expression Instruction (REI), which utilizes an instruction-based mechanism to fully exploit regular expressions' advantages to uniformly model diverse constraints. Our method only requires fine-tuning on medium-scale language models or few-shot, in-context learning on large language models, and requires no further adjustment when applied to various constraint combinations.
  arXiv  Detail & Related papers  (2023-09-19T09:05:14Z)
• Generalizing Level Ranking Constraints for Monotone and Convex Aggregates [0.0]
  In answer set programming (ASP), answer sets capture solutions to search problems of interest. One viable implementation strategy is provided by translation-based ASP. We take level ranking constraints into reconsideration, aiming at their generalizations to cover aggregate-based extensions of ASP.
  arXiv  Detail & Related papers  (2023-08-30T09:04:39Z)
• Unlocking Temporal Question Answering for Large Language Models with Tailor-Made Reasoning Logic [84.59255070520673]
  Large language models (LLMs) face a challenge when engaging in temporal reasoning. We propose TempLogic, a novel framework designed specifically for temporal question-answering tasks.
  arXiv  Detail & Related papers  (2023-05-24T10:57:53Z)
• CoreDiag: Eliminating Redundancy in Constraint Sets [68.8204255655161]
  We present a new algorithm which can be exploited for the determination of minimal cores (minimal non-redundant constraint sets) The algorithm is especially useful for distributed knowledge engineering scenarios where the degree of redundancy can become high. In order to show the applicability of our approach, we present an empirical study conducted with commercial configuration knowledge bases.
  arXiv  Detail & Related papers  (2021-02-24T09:16:10Z)
• ASP(AC): Answer Set Programming with Algebraic Constraints [20.559497209595822]
  We introduce Answer Set Programming with Algebraic Constraints (ASP(AC)), where rules may contain constraints that compare semiring values to weighted formula evaluations. This work is under consideration for acceptance in Theory and Practice of Logic Programming.
  arXiv  Detail & Related papers  (2020-08-10T10:20:49Z)
• An ASP semantics for Constraints involving Conditional Aggregates [9.289905977910378]
  We elaborate upon the formal foundations of hybrid Answer Set Programming (ASP) We extend its underlying logical framework with aggregate functions over constraint values and variables. We put some emphasis on logic programs with linear constraints and show how common ASP aggregates can be regarded as particular cases of so-called conditional linear constraints.
  arXiv  Detail & Related papers  (2020-02-17T12:25:01Z)

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.