NDLI: On look-ahead heuristics in disjunctive logic programming

Content Provider	Springer Nature Link
Author	Faber, Wolfgang Leone, Nicola Ricca, Francesco Pfeifer, Gerald
Copyright Year	2008
Abstract	Disjunctive logic programming (DLP), also called answer set programming (ASP), is a convenient programming paradigm which allows for solving problems in a simple and highly declarative way. The language of DLP is very expressive and able to represent even problems of high complexity (every problem in the complexity class ${{\Sigma}_{2}^{P}} = {\rm NP}^{{\rm NP}}$ ). During the last decade, efficient systems supporting DLP have become available. Virtually all of these systems internally rely on variants of the Davis–Putnam procedure (for deciding propositional satisfiability [SAT]), combined with a suitable model checker. The heuristic for the selection of the branching literal (i.e., the criterion determining the literal to be assumed true at a given stage of the computation) dramatically affects the performance of a DLP system. While heuristics for SAT have received a fair deal of research, only little work on heuristics for DLP has been done so far. In this paper, we design, implement, optimize, and experiment with a number of heuristics for DLP. We focus on different look-ahead heuristics, also called “dynamic heuristics” (the DLP equivalent of unit propagation [UP] heuristics for SAT). These are branching rules where the heuristic value of a literal Q depends on the result of taking Q true and computing its consequences. We motivate and formally define a number of look-ahead heuristics for DLP programs. Furthermore, since look-ahead heuristics are computationally expensive, we design two techniques for optimizing the burden of their computation. We implement all the proposed heuristics and optimization techniques in DLV—the state-of-the-art implementation of disjunctive logic programming, and we carry out experiments, thoroughly comparing the heuristics and optimization techniques on a large number of instances of well-known benchmark problems. The results of these experiments are very interesting, showing that the proposed techniques significantly improve the performance of the DLV system.
Ending Page	266
Page Count	38
Starting Page	229
File Format	PDF
ISSN	10122443
e-ISSN	15737470
Journal	Annals of Mathematics and Artificial Intelligence
Issue Number	2-4
Volume Number	51
Language	English
Publisher	Springer Netherlands
Publisher Date	2008-03-05
Publisher Place	Dordrecht
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Logic programming Problem solving (heuristics, search strategies, etc.) Nonmonotonic reasoning Heuristics Stable models Mathematics Complexity Logic in artificial intelligence Answer set programming Computer Science Efficient evaluation Artificial Intelligence (incl. Robotics) Artificial intelligence
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Artificial Intelligence

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the relation among answer set solvers

Integrating answer set programming and constraint logic programming

Enhancing DLV instantiator by backjumping techniques

Improving local-search metaheuristics through look-ahead policies

Weight constraint programs with evaluable functions

A generalization of the Lin-Zhao theorem

Computing weighted solutions in ASP: representation-based method vs. search-based method

Dealing with explicit preferences and uncertainty in answer set programming

Set-structured and cost-sharing heuristics for classical planning

On look-ahead heuristics in disjunctive logic programming

Similar Documents

On the relation among answer set solvers

Integrating answer set programming and constraint logic programming

Enhancing DLV instantiator by backjumping techniques

Improving local-search metaheuristics through look-ahead policies

Weight constraint programs with evaluable functions

A generalization of the Lin-Zhao theorem

Computing weighted solutions in ASP: representation-based method vs. search-based method

Dealing with explicit preferences and uncertainty in answer set programming

Set-structured and cost-sharing heuristics for classical planning

On look-ahead heuristics in disjunctive logic programming