RI: Small: Design and Implementation of Goal-directed Solvers for Answer Set Programming

University Of Texas At Dallas, Richardson TX

Investigators

Abstract

This project is focused on the development of an efficient Answer Set Programming (ASP) solver, advancing the state-of-the-art in logic based knowledge representation, logic programming and artificial intelligence. ASP is an elegant way to represent knowledge and perform advanced reasoning (common sense reasoning, non-monotonic reasoning, planning, constraint satisfaction, etc.). ASP is based on the stable model semantics proposed by Gelfond and Lifschitz. It has gained wide acceptance in the last fifteen years in the knowledge representation (KR) and artificial intelligence (AI) research communities due to its incorporation of negation, its expressiveness and simple, intuitive syntax. Considerable past research has been done in developing the ASP paradigm as well as its implementations and applications. Implementation techniques for realizing answer set solvers range from simple guess-and-check based methods to those based on SAT solvers and complex heuristics. Applicability of current ASP systems is limited due to (i) the current implementation methods not being goal-directed (i.e., not being query-driven), (ii) need for grounding the answer set program if predicates are present, (iii) being forced to find the model of the entire program (even though to answer a given query only a small subset of the model needs to be computed), and (iv) no answer being produced even if a minor inconsistency (unrelated to the query) is present in the knowledge base. This project addresses these problems by developing a query-driven implementation of answer set programs containing predicates. Current systems have to process the entire knowledge base (expressed as an answer set program) to compute an answer. In contrast, the query-driven method developed in this project only accesses and processes parts of the knowledge base that are involved in answering the query. Query-driven execution allows predicates to be directly included in answer set programs. It also leads to efficiency in execution. The query-driven method is based on PI's group's recent discovery of coinductive logic programming. Coinductive logic programming imparts operational semantics to greatest fixed point-based computations. Given a query and an answer set program, this coinduction-based operational semantics is used to compute (partial) answer sets that contain the query goal(s). With query-driven execution, predicates can be supported directly, i.e., answer set programs containing predicates no longer have to be grounded first. The main tasks of this project are the following: (i) develop an efficient query-driven, top-down execution strategy for propositional answer set programs; (ii) extend this query-driven execution strategy to handle Datalog ASP (without grounding the program first); (iii) further extend this query-driven execution strategy to handle Predicate ASP (without grounding the program first); (iv) develop coinductive extension of ASP and its implementation; (v) develop a query-driven abductive reasoning engine based on ASP; and, (vi) further extend the engine to incorporate constraints over reals. The key intellectual contributions of the research is the investigation of techniques for query-driven execution of answer set programs and advanced reasoning systems that employ negation. The research tests the claim that a query-driven implementation can more elegantly (and efficiently) support constraints and abduction in ASP. The broader impacts of this work include the availability of more powerful applications of knowledge representation; mechanisms for common sense reasoning; integration of advanced ASP systems into education and research venues; and the development of the research careers of graduate and undergraduate students, including those from under-represented groups.