Titulo Estágio
Modular Minimal Hypotheses Reasoning Engine for Logic Programs
Área Tecnológica
Inteligência Artificial
Local do Estágio
DEI-FCTUC
Enquadramento
Logic Programs (LPs) have long been used as one of the most successful Knowledge Representation and Reasoning (KRR) based approaches to the development of intelligent systems, and are used everyday for applications as diverse as planning, search, constraint-solving, diagnosis, abductive/hypothetical reasoning, and many others. LPs consist of sets of if-then logic rules with default negation. This non-classical, non-monotonic kind of negation, characteristic of LPs, give them their particular KRR power which allows their use for rational reasoning even in the face of incomplete or uncertain information without the need for the numerical quantification of uncertainty.
The well-known Prolog programming language embodies an approximation to the logic programming paradigm but, besides allowing for several non-declarative constructs, the query-answering procedures of its implementations are defined only for a restricted class of LPs. However, the full expressive and reasoning power of logic programming comes exactly from the kinds of LPs not allowed by Prolog implementations. For this reason there is a need for LP interpreters and reasoning engines capable of dealing with all classes of LPs.
From the set of rules that constitute an LP certain conclusions might follow, and a good part of the history of logic programming has been the pursuit of the good semantics for LPs, i.e., the right way to identify which conclusions can be inferred from the rules — the chosen semantics having a paramount and direct impact on the types and quality of the reasoning that can be done with the LP. Several semantics have been proposed and, although there is a reasonable consensus among the international scientific community around the Stable Models (SM) semantics [1], it is well known that it suffers from several problems, namely lacking some important formal properties. These problems with the SM semantics have very concrete practical impacts: e.g., since the SMs are also not applicable the all LPs, SMs do not guarantee the safety of updatable LPs; in general, query-answering tasks perform irrelevant computations; abductive (i.e., hypothetical) reasoning is unnecessarily inefficient, amongst others.
In [2,3] the author defined the Minimal Hypotheses (MH) semantics for LPs which is the first semantics for all LPs that enjoys a host of useful formal properties while also capturing all the SMs as particular cases of MH solutions. Whereas there are several implementations of the SM semantics available and used [4,5,6,7] there are still none for the MH semantics, simply because the latter has been only so recently defined. The development of an efficient MH-based interpreter and reasoning engine is therefore essential to allow, for the first time, the use of this semantics as the underlying framework in the development of practical intelligent systems.
This project is the first part of a larger work plan conducive to the implementation and dissemination of a Hybrid KRR System drawing its power from the synergistic combination of both Description Logic [8] (DL) and First-Order (non-ground) Logic Programs with Integrity Constraints, where the DL reasoning will be delegated to already available DL-reasoners such as [9,10,11]. Such a Hybrid KRR System will also be a contribution to the realization of the Semantic Web (SW) vision of developing systems more “capable of analyzing all the data on the Web” since the languages and reasoning mechanisms behind the SW are exactly the Description Logic and Logic Programs.
[1] The stable model semantics for logic programs, by M. Gelfond, V. Lifschitz - Proceedings of the 5th ICLP, 1988
[2] Every normal logic program has a 2-valued semantics: theory, extensions, applications, implementations, by A. M. Pinto - PhD thesis, Universidade Nova de Lisboa, 2011
[3] Every normal logic program has a 2-valued minimal hypotheses semantics, by A. M. Pinto and L. M. Pereira. - In Proceedings of EPIA, 2011
[4] The Smodels System, by T. Syrjänen, I Niemelä - In Proceedings of LPNMR, 2001
[5] Smodels: An implementation of the stable model and well-founded semantics for normal logic programs, by I. Niemelä, P. Simons - In Proceedings of LPNMR, 1997
[6] The DLV system for knowledge representation and reasoning, by N. Leone, W. Faber, G. Pfeifer, T. Eiter, G. Gottlob, S. Perri, F. Scarcello - ACM Transactions on Computational Logic, 2002
[7] clasp: A conflict-driven answer set solver, by M. Gebser, B. Kaufmann, A. Neumann, T. Schaub - In Proceedings of LPNMR, 2007
[8] The Description Logic Handbook — Theory, Implementation and Applications, 2nd Edition, Edited by: F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider, ISBN:9780521876254, 2007
[9] http://clarkparsia.com/pellet
[10] http://owl.man.ac.uk/factplusplus/
[11] http://hermit-reasoner.com/
Objetivo
The primary goal of this MSc thesis work is to design and develop an efficient interpreter of propositional Normal Logic Programs with Integrity Constraints and respective reasoning engine under the Minimal Hypotheses (MH) semantics. For this, the work plan is divided into the following sub-objectives:
1. Learning and Requirements analysis: through a series of short tutorial meeting sessions with the supervisor, the student will learn the basic concepts of logic programming concepts, which will help him/her on the requirements analysis process;
2. Design: specification of the application’s architecture, its components and interfaces, data structures and algorithms necessary to fulfill all the identified requirements;
3. Implementation: coding, using the C programming language, to implement the software tool previously designed;
4. Validation: besides checking for the correctness of the interpreter, a series of test cases, some of which correspondent to examples taken from [2], will be used to assess soundness and completeness of the reasoning engine with respect to the formal definition of the MH semantics;
5. Comparison: the system’s performance will be compared against that of SM-based systems [4,5,6,7] for solving SM-compatible problems;
6. Publication: besides the writing of the MSc thesis, and a short user manual for the application, a summary paper describing the work will also be written and submitted for publication at an international conference/workshop of the respective research area
With this set of goals it is thus expected that the student will participate in the writing of a scientific paper which can be the starting point of a research track.
Plano de Trabalhos - Semestre 1
In order to accomplish the objectives explained above, the work of this MSc thesis is divided into the following tasks:
Task T1 — Learning and Requirements
* Time frame: September 2012
* Description: Learning of the basic concepts of logic programming (syntax and semantics). Identification of all the requirements for the MH-based interpreter/reasoning engine. Analysis of the state-of-the-art SM-based engines. Set-up of the SM-based engines for the efficiency comparisons.
* Output: Requirements specification report. Draft descriptions of “Background”, “Motivation” and “Objectives” subsections of the “Introduction” section for the paper to be submitted.
Task T2 — Design
* Time frame: October-November 2012
* Description: Specification of the application’s architecture, its components and interfaces. Specification of the lexical and syntactical analyzers for the interpreter. Specification of the data structures and algorithms necessary to implement all reasoning capabilities identified and complying with the requirements. Setting of intermediate goals and detailed work plan.
* Output: Architecture specification report. Draft description of the “Approach” section for the paper to be submitted. Detailed work plan.
Task T3 — Mid-term report
* Time frame: December 2012
* Description: Writing of the mid-term MSc thesis report.
* Output: Mid-term MSc thesis report
Plano de Trabalhos - Semestre 2
Task T4 — Reviewing
* Time frame: January 2013
* Description: Adjustment of the work plan according to the mid-term report jury’s indications.
* Output: Reviewed goals and detailed plan.
Task T5 — Implementation and Validation
* Time frame: January-April 2013
* Description: Implementation of the interpreter and reasoning engine.
* Output: The application — completed, tested and validated. Draft description of the “Implementation Principles” section for the paper to be submitted.
Task T6 — Comparison and Publication
* Time frame: April-May 2013
* Description: Performance comparison between the MH-based tool and SM-based tools — such as Smodels, DLV, and Clasp — for SM-compatible classical problems, and for query-answering tasks. Writing and submission of the final version of the paper.
* Output: Detailed performance comparison report. Draft description of the “Comparisons” section for the paper to be submitted. Final version of the paper submitted.
Task T7 — MSc Thesis writing
* Time frame: January-May 2013
* Description: Writing of the MSc thesis final report
* Output: MSc thesis
Condições
This MSc work, with no funding, will take place at DEI-FCT-UC. The student will use his/her own laptop.
Observações
Candidates must fulfill the following minimal requisites:
* Solid knowledge of compilers/interpreters technologies and languages
* Excellent knowledge of efficient graph algorithms
* Excellent knowledge of the C programming language
* Fluent in english
Orientador
Alexandre Miguel Pinto
ampinto@dei.uc.pt 📩