Abstract
Modern knowledge representation often requires a combination of qualitative logical reasoning and quantitative constraint processing. While Answer Set Programming (ASP) provides a robust framework for non-monotonic reasoning, its integration with Constraint Processing (CP)—known as Constraint ASP (CASP)—has historically treated constraints as monotonic. This creates a semantic gap where default reasoning cannot be applied to numeric variables. This paper introduces $HT_C$, a formal logic that extends the Logic of Here-and-There to include constraint atoms. By allowing for partial valuations and defining a new semantics for foundedness, $HT_C$ enables a seamless integration of default reasoning and constraint satisfaction.
Introduction
Answer Set Programming (ASP) has emerged as a leading paradigm for declarative problem solving, particularly in domains requiring non-monotonic reasoning (the ability to retract conclusions given new information). However, ASP faces significant challenges when dealing with large numeric domains, as representing every possible integer as a distinct symbol leads to a combinatorial explosion in memory usage.
To address this, Constraint ASP (CASP) was developed to offload numeric computations to dedicated constraint solvers. Despite its success, most CASP systems are hybrid architectures that maintain a strict boundary between the ASP solver (non-monotonic) and the constraint solver (monotonic). This boundary prevents "default reasoning" for numeric variables; for instance, it is difficult to express a rule such as "Assign variable $x$ the value 10 unless there is a specific reason to do otherwise." In standard CASP, variables are typically expected to have a fixed value, and the system lacks a formal mechanism to handle undefined variables or default assignments.
The $HT_C$ Framework
The authors propose a new logical foundation called $HT_C$, which extends the Logic of Here-and-There (HT)—the mathematical basis for ASP—to natively incorporate constraint atoms. This approach places both logical propositions and numeric constraints on the same semantic footing.
Partial Valuations and Undefinedness
A core innovation of $HT_C$ is the introduction of partial valuations. In traditional constraint satisfaction, every variable in a system must be assigned a value from its domain. In $HT_C$, variables are allowed to be "undefined." This allows the logic to represent states of incomplete knowledge where a variable only takes on a value if it is explicitly justified by the program rules. This "undefinedness" is not a failure of the system but a feature that enables more flexible knowledge representation.
Foundedness and Directional Assignments
To prevent circular logic and ensure that every variable assignment has a clear justification, the authors introduce the concept of foundedness. They propose a specific syntax for rule heads:
$$x := \alpha .. \beta$$
This notation represents a directional assignment, ensuring that a variable $x$ is assigned a value within the range $[\alpha, \beta]$ only if the rule's conditions are met. This ensures that the resulting stable models are "founded," meaning they are the minimal models necessary to satisfy the program's constraints and rules.
Implementation and Practical Application
While $HT_C$ provides a theoretical breakthrough, the authors also demonstrate its practical utility. They developed a translation method to convert high-level $HT_C$ programs into standard CASP code. This allows $HT_C$ logic to be executed on existing, high-performance solvers like clingcon.
The 8-Queens Benchmark
The paper utilizes the 8-Queens Puzzle as a primary benchmark. In this context, $HT_C$ allows for the elegant expression of complex heuristics. For example, a programmer can easily specify a default position for the first queen (e.g., column 1) while allowing the solver to override this default if it conflicts with the requirement that no two queens threaten each other. This level of expressivity is significantly more concise than what is possible in traditional CASP frameworks.
LC2CASP
The authors released LC2CASP, a front-end implementation that facilitates this translation. LC2CASP acts as a bridge, taking programs written with $HT_C$ semantics and preparing them for the CLINGCON solver. This implementation proves that the theoretical benefits of $HT_C$ do not come at the cost of computational feasibility.
Key Results
The research establishes several critical formal properties:
- Generalization: $HT_C$ is proven to be a proper generalization of both standard ASP and the foundational CASP framework established by Gebser et al. (2009).
- Rigid Recovery: By adding specific axioms (such as $x=x$), users can force variables to behave "rigidly" (always defined), allowing $HT_C$ to mimic the behavior of traditional monotonic constraint systems when necessary.
- Soundness and Completeness: The authors provide formal proofs ensuring that the translation from $HT_C$ to standard CASP is correct and reliable.
Conclusion and Future Work
$HT_C$ represents a significant step forward in unifying logic-based reasoning with numeric constraint processing. By allowing constraints to participate in non-monotonic reasoning, it opens new possibilities for expert systems and automated planning.
Future research directions include extending the framework beyond linear integer constraints to include non-linear constraints and real numbers. Additionally, the authors suggest exploring "value minimization" techniques, which would allow the system to automatically find the smallest valid integer for a variable—a common requirement in optimization tasks. Finally, while the current translation-based approach is effective, developing a "native" $HT_C$ solver could provide further performance optimizations.
Summary updated