RI: SMALL: Efficient Implementations of Goal-Directed Solvers for Answer Set Programming

University Of Texas At Dallas, Richardson TX

Investigators

Abstract

The goal of this project is to develop efficient implementation techniques for realizing automated reasoning systems that emulate human-style common sense reasoning. Automating common sense reasoning is important for developing advanced applications of artificial intelligence (AI), particularly, in areas where the thought process of an expert needs to be automated, e.g., reasoning performed by a medical doctor during diagnosis and prescribing a treatment. Human reasoning is difficult to emulate on a computer, as humans simplify reasoning by using default conclusions (e.g., if Tweety is a bird, it must fly) coupled with raising exceptions (if Tweety turns out to be a penguin later, retract the conclusion about Tweety's flying abilities). Because of this peculiar nature of human reasoning, approaches based on standard logic do not work very well: one has to resort to a non-monotonic logic, i.e., a logic in which conclusions reached now may be withdrawn later as new information becomes available. Research conducted in this project will result in efficient, query-driven implementations of these non-monotonic logics. Successful completion of this project will result in advanced applications such as an automated system that can advise a physician on how to treat a particular disease, or a self-driving car's decision-making system that can emulate a human's driving expertise. The project will rely on the paradigm of answer set programming (ASP) to represent common sense knowledge. An answer set program consists of rules containing (possibly negated) predicates. Current ASP systems rely on first grounding the answer set program to obtain an equivalent propositional program, and then using a Boolean satisfiability (SAT) solver to find models of this propositional program that contain the answer that is sought by the user. The grounding requirement restricts the range of programs that can be executed. This project builds upon earlier research on directly executing predicate answer set programs, i.e., without grounding them first. It aims to realize faster implementations of such systems by designing a virtual machine to which an answer set programs will be compiled to and executed.