Compiling Metric Temporal Answer Set Programming

A. Becker, P. Cabalar, M. Diéguez, J. Romero, S. Hahn, T. Schaub · 2025

Read Compiling Metric Temporal Answer Set Programming by A. Becker, P. Cabalar, M. Diéguez, J. Romero, S. Hahn, T. Schaub (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-08150.txt.

Introduction

Arvid Becker and co-authors present this 2025 compiler approach for logic programs that reason about time in numbers. Answer set programming solves problems by rules, but deadlines and durations measured finely, like milliseconds, blow up its grounding step. Their metric extension expresses such quantitative time constraints directly.

The trick is to hand the timing arithmetic to difference constraints, a simple kind of linear bound handled outside the main solver. Time precision then stops mattering: a problem stated in seconds or microseconds costs the same to ground. That decoupling keeps programs scalable as timing gets finer. The work targets scheduling and planning problems where both logic and exact timing are unavoidable.

Catalog record

CREATORA. Becker, P. Cabalar, M. Diéguez, J. Romero, S. Hahn, T. Schaub
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-08150

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Compiling Metric Temporal Answer Set Programming Thanks: Under consideration for publication in International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2024) A. Becker, P. Cabalar, M. Diéguez, J. Romero, S. Hahn, T. Schaub Abstract We develop a computational approach to Metric Answer Set Programming (ASP) to allow for expressing quantitative temporal constrains, like durations and deadlines. A central challenge is to maintain scalability when dealing with fine-grained timing constraints, which can significantly exacerbate ASP’s grounding bottleneck. To address this issue, we leverage extensions of ASP with difference constraints, a simplified form of linear constraints, to handle time-related aspects externally. Our approach effectively decouples metric ASP from the granularity of time, resulting in a solution that is unaffected by time precision. 1 Introduction Metric temporal logics [ 12 ] allow for expressing quantitative temporal constrains, like durations and deadlines. As an example, consider the dentist scenario [ 19 ] : D H O A D 0 20 30 40 H 20 0 15 15 O 30 15 0 20 A 40 15 20 0 Table 1: Durations between locations “Ram is at his office and has a dentist appointment in one hour. For the appointment, he needs his insurance card which is at home and cash to pay the doctor. He can get cash from the nearby Atm. Table 1 shows the time in minutes needed to travel between locations: Dentist, Home, Office and Atm. For example, the time needed to travel between Ram’s office to the Atm is 20 minutes. The available actions are: moving from one location to another and picking items such as cash or insurance. The goal is to find a plan which takes Ram to the doctor on time.” This example combines planning and scheduling, and nicely illustrates the necessity to combine qualitative and quantitative temporal constraints. Extensions to the Logic of Here-and-There and Equilibrium Logic [ 20 ] were developed in [ 9 , 6 ] to semantically ground the incorporation of metric constraints into Answer Set Programming (ASP; [ 18 ] ). Building upon these semantic foundations, we develop a computational approach to metric ASP. A central challenge in this is to maintain scalability when dealing with fine-grained timing constraints, which can significantly exacerbate ASP’s grounding bottleneck. To address this issue, we leverage extensions of ASP with difference constraints [ 15 ] , a simplified form of linear constraints, to handle time-related aspects externally. This approach effectively decouples metric ASP from the granularity of time, resulting in a solution that is unaffected by time precision. In detail, we (i) propose translations of metric logic programs into regular logic programs and their extension with difference constraints, (ii) prove the completeness and correctness of both translations in terms of equilibrium logic and its extensions with metric and difference constraints, and (iii) describe an implementation of both translations in terms of meta encodings and give some indicative experimental results. Conversely, we may consider metric logic programs as a high-level modeling language for logic programs with difference constraints in the context of temporal domains. We consider a simple yet expressive fragment in which the next operator can be supplied with a time frame expressed as an interval; the full paper shows how this extends to the entire language. Related work Pioneering work on extending ASP with linear integer constraints to express quantitative temporal relations was done in [ 4 , 19 ] . This work ultimately inspired the development of hybrid ASP systems such as clingcon [ 3 ] and clingo [ dl ] [ 15 ] . Metric equilibrium logic was defined in [ 9 , 6 ] by building on Linear temporal equilibrium logic [ 1 ] . The latter provides the logical foundations of the temporal ASP system telingo [ 8 ] . Metric concepts are also present in stream reasoning, notably, the approach of lars [ 5 ] . Metric extensions are also considered in Datalog [ 22 ] , where they led to the meteor [ 23 ] and (temporal) vadalog [ 7 ] systems. Actions with durations in ASP are explored in [ 21 ] . Finally, [ 14 ] considers reductions of (monotonic) Metric temporal logic to Linear temporal logic. A comprehensive comparative account of metric approaches in logic programming is given in [ 6 ] . 2 Background To ease the formal elaboration of our translations from metric ASP to regular logic programs and their extension with difference constraints, we put ourselves into the context of the logical framework of Here-and-There and Equilibrium Logic. The Logic of Here-and-There [ 20 ] . A formula over an alphabet \mathcal{A} is defined as \displaystyle\varphi \displaystyle::=\bot\mid a\mid\varphi\wedge\varphi\mid\varphi\vee\varphi\mid\varphi\to\varphi\quad\text{ where }a\in\mathcal{A}\ . We define the derived operators \neg\varphi=\varphi\to\bot and \top=\neg\bot . Elements a of \mathcal{A} are called (Boolean) atoms . A literal is an atom or an atom preceded by negation, viz. a or \neg a . A theory is a set of formulas. We sometimes write \varphi\leftarrow\psi instead of \psi\to\varphi to follow logic programming conventions. A program is a set of implications of the form \varphi\leftarrow\psi where \varphi is a disjunction of literals and \psi is a conjunction of literals. We represent an interpretation T as a set of atoms T\subseteq\mathcal{A} . An HT - interpretation is a pair \langle H,T\rangle of interpretations such that H\subseteq T ; it is said to be total if H=T . An HT-interpretation \langle H,T\rangle satisfies a formula \varphi , written \langle H,T\rangle\models\varphi , if 1. \langle H,T\rangle\models a if a\in H 2. \langle H,T\rangle\models\varphi\wedge\psi if \langle H,T\rangle\models\varphi and \langle H,T\rangle\models\psi 3. \langle H,T\rangle\models\varphi\vee\psi if \langle H,T\rangle\models\varphi or \langle H,T\rangle\models\psi 4. \langle H,T\rangle\models\varphi\to\psi if \langle H^{\prime},T\rangle\not\models\varphi or \langle H^{\prime},T\rangle\models\psi for each H^{\prime}\in\{H,T\} An HT -interpretation \langle H,T\rangle is an HT -model of a theory \Gamma if \langle H,T\rangle\models\varphi for each \varphi\in\Gamma . A total model \langle T,T\rangle of a theory \Gamma is an equilibrium model if there is no other model \langle H,T\rangle of \Gamma with H\subset T ; T is also called a stable model of \Gamma . The Logic of Here-and-There with Constraints [ 10 ] . The syntax of \textrm{HT}_{\!c} relies on a signature \langle\mathcal{X},\mathcal{D},\mathcal{C}\rangle , similar to constraint satisfaction problems, where elements of set \mathcal{X} represent variables and elements of \mathcal{D} are domain values (usually identified with their respective constants). The constraint atoms in \mathcal{C} provide an abstract way to relate values of variables and constants according to the atom’s semantics. For instance, difference constraint atoms are expressions of the form ‘ x-y\leq d ’, containing variables x,y\in\mathcal{X} and the domain value d\in\mathcal{D} . A constraint formula \varphi over \mathcal{C} is defined as \displaystyle\varphi \displaystyle::=\bot\mid c\mid\varphi\wedge\varphi\mid\varphi\vee\varphi\mid\varphi\rightarrow\varphi\quad\text{ where }c\in\mathcal{C} Concepts like defined operators, programs, theories, etc. are analogous to HT . Variables can be assigned some value from \mathcal{D} or left undefined . For the latter, we use the special symbol \bm{u}\not\in\mathcal{D} and the extended domain \mathcal{D}_{u}=\mathcal{D}\cup\{\bm{u}\} . A valuation v is a function v:\mathcal{X}\rightarrow\mathcal{D}_{u} . We let \mathbb{V} stand for the set of all valuations. We sometimes represent a valuation v as a set \{(x,v(x))\mid x\in\mathcal{X},v(x)\in\mathcal{D}\} of pairs, so that (x,\bm{u}) is never formed. This allows us to use standard set inclusion, v\subseteq v^{\prime} , for comparing v,v^{\prime}\in\mathbb{V} . The semantics of constraint

Read the complete text