Domain-Specific Heuristics in Answer Set Programming: A Declarative Non-Monotonic Approach
Authors: Richard Comploi-Taupe, Gerhard Friedrich, Konstantin Schekotihin, Antonius Weinzierl
JAIR 2023 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We tested our approach to declarative domain-specific heuristics by creating such heuristics for several example domains and solving these problem domains using our implementation in the Alpha system. Two concrete domains under investigation were the House Reconfiguration Problem (HRP) and the Partner Units Problem (PUP), and state-space search with A*. These two configuration problems are abstracted variants of typical configuration problems experienced in more than 25 years of applying AI technology in the area of automated configuration of electronic systems (Falkner et al., 2016). For all these applications, heuristics exist which allow the efficient generation of satisfying solutions. Furthermore, we realised general state-space search in our approach, using the well-known informed search method A*, by which we abstract from concrete domains. A* allows the incorporation of a heuristic evaluation function. By integrating A* into ASP, we can show that, on the one hand, we can exploit the power of informed (heuristic) search methods within ASP. On the other hand, we can employ the knowledge representation capabilities of ASP to specify states, actions, and their successor states declaratively. Depending on the quality of the heuristic function an optimal solution is generated and the number of generated nodes is reduced. We applied A* to two further search problems. All these applications are presented in Sections 6.2 to 6.4 below, along with heuristics in the language proposed in this work. To put ASP systems under stress, we used problem encodings and instances of varying sizes, where the larger instances were challenging to ground and solve. |
| Researcher Affiliation | Collaboration | Richard Comploi-Taupe (corresponding author) EMAIL Siemens AG Osterreich and Alpen-Adria-Universit at Klagenfurt, Austria Gerhard Friedrich EMAIL Alpen-Adria-Universit at Klagenfurt, Austria Konstantin Schekotihin EMAIL Alpen-Adria-Universit at Klagenfurt, Austria Antonius Weinzierl EMAIL TU Wien, Vienna, Austria |
| Pseudocode | Yes | Algorithm 1: Graph Search with A* (adapted from Figures 3.7 and 3.14 by Russell & Norvig, 2010) Input: P, a problem defined by the components specified in Definition 12. Output: A solution, or failure. Initialize frontier F, a priority queue ordered by f( ), initially containing the initial state of P Initialize explored set E to be empty while F is not empty do Pop node n with least f(n) from F if n contains a goal state then return the corresponding solution Add state of n to E foreach action a available in the state of n do Generate child node by applying action a on node n if the child state is neither in F nor in E then Insert the child node into F else if the child state is already in F, but with a higher path cost then Replace that node in F with child return failure |
| Open Source Code | Yes | Encodings (including heuristics) and instances, and the Alpha binaries used for our experiments, are available in the online appendix accompanying our article and on our website.8 5. Alpha sources and binaries can be found on https://github.com/alpha-asp/Alpha. Features described in this section have been implemented on the domspec heuristics extended branch. |
| Open Datasets | Yes | For PUP, competition instances were used additionally. All 18 instances from the ASP competitions (Calimeri, Ianni, & Ricca, 2014; Calimeri et al., 2016) that are satisfiable, belong to the subclass of PUP instances that can be polynomially decided, and in which the input graphs are connected have been used for our experiments. To test our A* encoding on real world routing problems, we obtained a graph representation of the walkable street network for the first district of Vienna, Austria, from Open Street Map,22 employing the OSMnx Python library (Boeing, 2017). |
| Dataset Splits | No | The paper uses |
| Hardware Specification | Yes | Each of the machines used to run the experiments was equipped with two Intel Xeon E5-2650 v4 @ 2.20GHz CPUs with 12 cores. Furthermore, each machine had 251 Gi B of memory and ran Ubuntu 16.04.1 LTS Linux. |
| Software Dependencies | Yes | For comparison, clingo11 (Gebser et al., 2019) was used in version 5.4.0 and dlv212 (Alviano et al., 2017) in version 2.1.0. The JVM running Alpha was called with command-line parameters -Xms1G -Xmx32G, thus initially allocating 1 Gi B for Java s heap and setting the maximum heap size to 32 Gi B. |
| Experiment Setup | Yes | Alpha was used without justification analysis (Bogaerts & Weinzierl, 2018) and without support for negative integers in aggregates because we observed these features to deteriorate performance in some cases. Apart from that, Alpha was used in its default configuration. The JVM running Alpha was called with command-line parameters -Xms1G -Xmx32G, thus initially allocating 1 Gi B for Java s heap and setting the maximum heap size to 32 Gi B. Time and memory consumption were measured by pyrunlim,14 which was also used to limit time consumption to 15 minutes per instance, memory to 40 Gi B and swapping to 0. All solvers were configured to search for the first answer set of each problem instance. |