REFLECTIONS on LOGIC PROGRAMMING and NONMONOTONIC REASONING by JACK MINKER UNIVERSITY OF MARYLAND
INTRODUCTION BEGINNINGS LOGIC PROGRAMMING DISJUNCTIVE LOGIC PROGRAMMING LP and NMR IMPLEMENTATIONS RECENT DEVELOPMENTS APPLICATIONS SUMMARY and CONCLUSIONS
BEGINNINGS McCARTHY  Common Sense Reasoning (1959)
 DEFINED ‘OLDEST’ PROBLEM IN AI
 LIFSCHITZ, McCAIN, REMOLINA, TURNER (2000) CCALC
 Situations, Actions, Causal Laws (1963)
 GOLOG (LEVESQUE, REITER (1997))
McCarthy and Hayes  Philosophical Problems and Frame Axioms (1969)
 Seeming Need for Large Number of Axioms to Represent Changes
 REITER (1980, 1991), SHANAHAN (1997)
Robinson (1965)  Resolution Principle for Automated Theorem Proving
Minsky Frame Paper and Critique of Logic in AI (1975)
``LOGICAL’’ REASONING IS NOT FLEXIBLE FOR THINKING INCONSISTENT DATA CANNOT BE HANDLED FEASIBILITY OF REPRESENTING KNOWLEDGE BY SMALL ``TRUE’’ PROPOSITIONS IS DOUBTFUL SEPARATION OF KNOWLEDGE AND RULES IS TOO RADICAL LOGIC IS MONOTONIC PROCEDURAL DESCRIPTIONS OVER DECLARATIVE DESCRIPTIONS
LOGIC PROGRAMMING BEGINNINGS HODES (1966) GREEN (1969) HEWITT (1969) ELCOCK (1971)  ABSYS and ABSET – Declarative Languages
HAYES (1973)  Computation and Deduction
COLMERAUER (1973) WARREN, PEREIRA, PEREIRA (1977)  EDINBURGH PROLOG
 Competitive With LISP
HORN LOGIC PROGRAMMING FOUNDATIONS HORN CLAUSES KOWALSKI and KUEHNER –SL Resolution (1971)  Descendant of Model Elimination (Loveland 1969)
 LUSH/SLD (Hill 1974, Apt and Van Emden 1982)
KOWALSKI (1974) Van EMDEN and KOWALSKI (1976)  FIXPOINT SEMANTICS
 MODEL THEORY SEMANTICS
 OPERATIONAL SEMANTICS
LOGIC and DATABASES (WORKSHOP 1977, BOOK 1978 Gallaire, Minker)  REITER (1978)
 NEGATION (REITER CLOSED WORLD ASSUMPTION)
 DOMAIN CLOSURE AXIOM
 UNIQUE NAME AXIOM
 CLARK (1978)
 NEGATION (CLARK COMPLETION THEORY COMP(P) – IFF)
 p(t1, …, tm) A1, …, An p(x1, …, xm) y1… yp (x1 = t1 Λ … Λ xn = tn Λ A1 … Λ An)
 Clark Equational Theory (CET)
SURVEYS ON NEGATION
DISJUNCTIVE LOGIC PROGRAMMING – FIRST STEP NON HORN CLAUSE (DISJUNCTIVE CLAUSE) P1, …, Pn A1, …, Am THEORY OF NEGATION  REITER’s CWA is INCONSISTENT for DISJUNCTION
 {P v Q} then by CWA, {not P} and {not Q}
Minker (1982)  GENERALIZED CLOSED WORLD ASSUMPTION
 MODEL THEORETIC  MINIMAL MODELS
 {P}, {Q}
 Positive Truths – True in every minimal model
 Negative Truths – Not True in any minimal model
 PROOF THEORETIC
P A1, A2, …An, not B1,…, not Bm  {p not q, q p} (not stratified)
 {p not q, r , q q, not r} rewritten for stratification as {r}, {q q, not r}, {p not q}
STRATIFIED LP  APT, BLAIR and WALKER (1988)
 VAN GELDER (1988)
 PRZYMUSINSKI (1988)
NORMAL LP  VAN GELDER, ROSS and SCHLIPF (1988)
 WELL FOUNDED SEMANTICS (WFS)
 {p not q, q not p} WFS: {p and q are unknown}
 GELFOND and LIFSCHITZ (1989)
STABLE MODELS GELFOND, LIFSCHITZ (1991) REDUCT PI of P w.r.t Interpretation I  Delete all rules with a negative false literal (w.r.t. I)
 Delete the negative literals from the bodies of the remaining literals
A Stable Model of a program P is an interpretation I such that I is an answer set of PI
DISJUNCTIVE LOGIC PROGRAMMING THEORY P1, P2, …, Pm A1, A2, …, An MINKER and RAJASEKAR (1987)  FIXPOINT OPERATOR
 MODEL THEORY
 PROOF THEORY
 LUST/SLI (MINKER, ZANON 1982, LOBO, MINKER,RAJASEKAR 1992)

 EXTENDED DLP (with Baral, Lobo, Ruiz, Seipel) (Gelfond and Lifschitz 1991)
 P1, P2, …, Pm A1, A2, …, An, not B1, not B2, …, not Bk
 Negation in body of clauses
 SLINF (MINKER, RAJASEKAR 1990)
LOBO, MINKER, RAJESEKAR (1992)  FOUNDATIONS of DISJUNCTIVE LOGIC PROGRAMMING
GELFOND and LIFSCHITZ  Classical Negation (1991)
 Answer Set Semantics (1999)
APPLICATIONS DISJUNCTIVE LP  BARAL, GELFOND (1995)
 BARAL (2002)
 Knowledge Representation, Reasoning and Declarative Problem Solving
OTHER APPLICATIONS  3 Color Problem
 Hamiltonian Path
 See Problems in LPNMR07 ASP Contest
ABDUCTIVE LOGIC PROGRAMMING ABDUCTION INTRODUCED BY PHILOSOPHER C.S, PIERCE (1955)  An Inference Process of Forming a hypothesis that explains given observed phenomena
Study of Abduction in LP Introduced in Late 1990s  Eshgi, Kowalski, Denecker, Kakas, Mancarella early workers in field
 Kowalski, Kakas and Toni (1993) ``Abductive Logic Programming’’
 Answer Set Programming used as basis for some implementations
 Performing Abduction in Disjunctive Logic Programming Studied by Eiter, Leone, Mateis, Pfeifer, Scarcello (1998) and by Sato and Inoue who discussed abduction and DLP
 Mancarella, Sadri, Terreni and Toni (2007 at LPNMR07), discuss the use of CIFF for abductive reasoning with constraints and show that their system compares favorably with ASystem, DLV and Smodels
NONMONOTONIC THEORIES CIRCUMSCRIPTION (McCARTHY 1980) DEFAULT REASONING (REITER 1980) AUTOEPISTEMIC REASONING (MOORE 1985)
CIRCUMSCRIPTION Let A be a sentence of FOL containing predicate symbol P(x1,…,xn) written as P(x). We write A(Ø) as result for replacing all predicates P in A by the predicate expression Ø. The CIRCUMSCRIPTION OF P IN A(P) is the sentence schema  A(Ø) Λ x(Ø(x) P(x)) x(P(x) Ø(x)) (1)
 LIFSCHITZ: POINTWISE, PRIORITIZED, PARALLEL, INTROSPECTIVE
DEFAULT REASONING DEFAULT REASONING  If is true and is consistent with a set of beliefs, then is believed  EXTENSIONS TO DEFAULT REASONING
 DISJUNCTIVE DEFAULTS (GELFOND,LIFSCHITZ, PRZYMUSINSKA, TRUSZCZYNSKI (1991))
 :1, …, m
 1  …  n  Generalizes the semantics of disjunctive and extended disjunctive databases
 CONSTRAINED (DELGRAND, SCHAUB, JACKSON (1999))
 CUMULATIVE DEFAULT LOGIC (BREWKA (1991))
 JUSTIFIED DEFAULT LOGIC (LUKASZIEWICZ (1988))
 RATIONAL DEFAULT LOGIC (MIKITIUK, TRUSZCZYNSKI (1988))
 DEFAULTS WITH PREFERENCES AND INHERITANCE (DELGRANDE, SCHAUB (2002))
MODAL THEORIES AUTOEPISTEMIC LOGIC  Modal Logic augments FOL by operators
 such as B (believes), K (knows) that take sentences as arguments rather than terms.
 Invented by Hintikka (1962). Kripke (1963) defined semantics of modal logic of knowledge in terms of possible worlds.
 Moore related modal logic of knowledge to reasoning about knowledge which refers directly to possible worlds in FOL.
RELATIONSHIPS AE/DEFAULT/CIRCUMSCRIPTION PERLIS (1988)and LIFSCHITZ (1989)  VARIANTS OF CIRCUMSCRIPTION ANALOGOUS TO AEL
KONOLIGE (1987) MAREK/TRUSZCZYNSKI (1989) MAREK/SUBRAHMANIAN (1989)  RELATE FORMAL MODELS OF NORMAL PROGRAMS AND EXPANSIONS OF AE THEORIES
ADDITIONAL RELATIONSHIPS AE/CIRCUMSCRIPTION/DEFAULT/LP REITER (1982)  FIRST TO RELATE CIRCUMSCRIPTION TO LOGIC PROGRAMMING
Marek and Truszczynski (1989)  Stable Models for Default Logic
GELFOND (1987)  GENERAL LOGIC PROGRAMS TRANSLATE TO AEL
GELFOND/LIFSCHITZ (1988)  STABLE MODEL SEMATICS EQUIVALENT TO TRANSLATION OF LOGIC PROGRAMS TO AEL
LIFSCHITZ (1989)  AEL, STABLE MODELS AND INTROSPECTIVE CIRCUMSCRIPTION PROVIDE 3 EQUIVALENT DESCRIPTIONS OF PROPOSITIONAL LOGIC PROGRAMS
PRZYMUSINSKI (1988)  RELATIONSHIPS BETWEEN LP AND NMR
 EXTENDS AEL TO GENERALIZED AEL AND RELATES
 AEL TO REITER’S CWA
 GAEL TO MINKER’S GCWA
ADDITIONAL RELATIONS Bonatti (1993)  AEL Programs Generalize Ideas in LP
 Stable, Supported WFS, Fitting’s and Kunen’s Semantics and Abduction can be Captured by AEL Translations
 Generalized SLDNF and a Generate and Test Method To Provide Sound and Complete Methods for AE Programs
Lin, ZHOU (2007)  Answer Sets and Circumscription
 Map Pearce Equilibrium Logic (2001) and Ferraris’s General Logic Programs (2005) to Lin and Shoham’s Knowledge of Justified Assumptions (1992) (a nonmonotonic modal logic that includes as special cases Reiter’s default logic in propositional case and Moore’s AEL).
 Allows a Mapping from general logic programming to propositional circumscription.
IMPLEMENTATIONS at LBAI 2000 Niemela, Simon (1997) Marek and Truszczynski Warren, et al. (1999)  XSB (Well Founded Models)
Eiter, Leone, Mateis, Pfeifer, Scarcello (1997)  DLV (Disjunctive Theories)
Zaniolo, Arni, Ong (1993)
IMPLEMENTATIONS at LBAI 2000 (CON’T) PLANNING  TLPlan (Bacchus et al.)
 GPT (Bonet/Geffner)
 Blackbox (Kautz/Selman/Huang)
 CCALC (Lifschitz/McCain/Turner)
 Golog (Levesque et al.)
INDUCTIVE LOGIC PROGRAMMING  CPROLOG (Muggleton/Srinivasan)
MULTIAGENT APPLICATIONS  IMPACT (Subrahmanian et al.)
NONMONOTONIC REASONING PARADIGM Use any NMR Theory to Define your Problem Translate the Theory to LP/DLP system Depending upon your translation and whether or not the translation has recursion through negation, select an existing system that best meets your needs Dominant semantics is Answer Set Semantics Implement and Test your System Build Capabilities Using Existing Systems  AProlog Implemented on Top of Smodels (Gelfond et al.) (2002)
 GnT Built on Top of Smodels to achieve disjunction
IMPLEMENTATION REPOSITORY DAGSTUHL INITIATIVE PROPOSAL (1996)  Minker Proposed Developing a Database of Information about LP System Implementations and Applications.
 University of Koblenz developed web site listing systems and applications. (Furbach)
 32 SYSTEMS LISTED (Last updated 2000)
 Applications Page Inaccessible
DAGSTUHL INITIATIVE PROPOSAL (2002)  Develop infrastructure for benchmarking ASP solvers
 Environment for submitting and archiving benchmarking problems and instances in which ASP systems can be benchmarked under equal and reproducible conditions, leading to independent results.
 Asparagus Web Site http://asparagus.cs.unipotsdam.de/
 International Board
 Assure Continuation and Generate Continued Interest
 Consider Broadening the Material in the Asparagus Web Site, not necessarily for the contest
 Information about other nonmonotonic systems (WFS), Successful Real Applications, Cognotive Robotics, Logic Planning Programs, …
 FIRST INTERNATIONAL CONTEST ASP SYSTEMS LPNMR 07
 Evaluation Committee: GEBSER, LIU, NAMASIVAYAN, NEUMANN, TRAUB, TRUSZCZYNSKI
 SYSTEMS: Asper, Angers; Assat, Hong Kong; Clasp Potsdam; Cmodels, Texas; dlv, Vienna/Rende; gnt, Helsinki; lp2sat, Helsinki; nomore, Potsdam; pbmodels, Kentucky; Smodels, Helsinki
 37 problems listed for First Answer Set Programming System Contest
 THE COMPETITION COMMITTEE HAS AUTHORIZED ME TO ANNOUNCE THE WINNER IS:

TO BE ANNOUNCED BY THE First Answer Set Programming System Competition Committee
SIGNIFICANT DEVELOPMENTS 1 IMPRESSSED BY WORK THAT HAS COMBINED THEORY, COMPLEXITY, IMPLEMENTATION AND EXPERIMENTAL WORK, PRIMARILY ON ANSWER SET PROGRAMMING EXTENSIONS TO ANSWER SET PROGRAMMING  SMODELS  Choice Rules, Cardinality and Weight Constraints (NIEMELA, SIMONS 2000)
 Cardinality Constraint L{a1, …, an, not b1, …, bm}U
 Cardinality and Weight Constraints are form of AGGREGATES that correspond to COUNT and SUM (first to introduce into non stratified programs)
 Disjunction capability, GnT, Built on Top of Smodels (~2000)
 Unfolding Partiality and Disjunctions in Stable Model Semantics (Janhusen, Niemela, Seipel, Simons, You 2006)
 Develop Implementation methodology for partial & disjunctive stable models where partiality and disjunctions are unfolded
 Implementation of stable models of normal (disjunctionfree) logic programs can be used to compute stable models for disjunctive logic programs
 They show partial stable models can be captured by total stable models using a simple linear & modular program transformation.
 Experiments on several classes of problems compares favorably with DLV
SIGNIFICANT DEVELOPMENTS 2 DLV  Generate & Test Paradigm (Eiter, Leone 2002)
 Disjunctive Rule ``Guesses’’ Solution Candidate S
 Integrity constraints which check admissibility of S
 Recursive Aggregates in Disjunctive Logic Programming; Semantics and Complexity (Faber, Leone, Pfeifer 2004) (Faber and Leone )
 Enhancing Magic Sets for Disjunctive Datalog (Cumbo, Faber, Greco, Leone)
 Magic Sets and Data Integration (Faber, Greco, Leone 2007)
INFOMIX (Calabria, Roma, Vienna, Warsaw Groups 2005)  Data Integration
 Integrity Constraints over global schema
 Sound and complete logicbased methods for query answering
 Deal with incomplete and inconsistent data
 DLV and disjunctive data
SIGNIFICANT DEVELOPMENTS  3  Extensions to Handle Ordered Disjunctions and Inconsistencies, CRPROLOG2 (Consistency Restoring ) (BALDUCCINI, MELLARKOD 2004)
 r: A1, …, Ak l1, …, lm, not lm+1, …, not ln
 r. A1 x … x Ak l1, …, lm, not lm+1, …, not ln (introduced by Brewka, Niemela, Syrajnen 2003)
 cr. H + l1, …, lm, not lm+1, …, not ln
 ``may possibly’’ believe one of the elements of the head if agent has no way to obtain a consistent set of beliefs using regular rules only.
 Extend ASP to Include Probabilities  Allows Probabilistic Causal Reasoning (BARAL, GELFOND, RUSHTON 2007)
 Combines ASP with ideas of Judea Pearl
 Allows reasoning with causal probabilities and probabilistic updates
 AI@50 Debated whether AI should be logicbased or probability based. This work indicates that there need not be a dichotomy.
SIGNIFICANT DEVELOPMENTS  4  Loop Formulas (Lin, Zhao 2002)
 Relationship Between Clark’s Completion and Stable Models
 Loop formulas are those needed to be added to the Clark completion of the Program to get exact characterization of its stable models
 Loop {pq, qp} program has a unique answer set
 comp: {pq, qp} has 2 models {{p}, {q}}
 Loop formula (p q) false – none of them can be in answer set
 Serves as new basis to implement stable model semantics (ASSAT)
 Complete the program
 Conjoin with loop formulas
 Invoke SAT solver to find satisfying truth assignments
 Output truth assignments as stable models of program
APPLICATIONS ACADEMIC APPLICATIONS – USEFUL FOR TESTING AND INTRODUCING NEW FEATURES (3COLOR, HAMILTONIAN CIRCUIT, …) NONACADEMIC REALISTIC APPLICATIONS NEEDED  DEMONSTRATE UTILITY OF LPNMR
 HANDLE LARGE APPLICATIONS (E.G. INTERFACE WITH SQL SYSTEM)
 HANDLE PROBLEMS NEEDED by USERS, EFFECTIVE INTERFACES, DEBUGGERS, OPTIMIZERS, HEURISTICS, …
 TRANSFER TECHNOLOGY TO USER
NONACADEMIC APPLICATIONS 1 XSB (Warren)  Ontology Management Work from textual database fields and technical drawings
 Extracted and inferred attributes of parts from textual database fields so organization could better understand what they had: how many parts used, or how many parts included a strategic material such as titanium.
 Written in XSB with SQL server as a backing store, and included some parsing, a bit of ontological reasoning and a little bit of NMR  in parts using a WFS preference logic for parsing.
 Deductive Spread Sheet
 Implemented as addin to MS Excel. Allows users to create deductive systems in a spreadsheet environment. XSB is backend computation engine and spreadsheet can be viewed as showing base data and the results of tabled computations. Whenever the user changes a spreadsheet cell that other cells depend on, those other cells are immediately updated.
 This is implemented using the new XSB incremental table maintenance facility.
NONACADEMIC APPLICATIONS 2 SPACE SHUTTLE REACTION CONTROL SYSTEM (GELFOND ET AL. 2001)  Primary responsibility  maneuver aircraft while in space.
 Consists of fuel and oxidizer tanks, valves and other plumbing needed to provide propellant to shuttle’s maneuvering jets. Includes electronic circuitry: both to control valves in fuel lines and to prepare jets to receive firing commands.
 During normal shuttle operations, prescripted plans tell astronauts what to do to achieve certain goals. System failures change situation. The number of possible sets of failures is too large to preplan for all of them. Continued correct operation of the RCS is then needed to allow mission completion of the mission and ensure crew safety. An intelligent system to verify and generate plans was needed.
 RCS/USAAdvisor is part of a decision support system for shuttle controllers. It is based on a reasoning system and a user interface. The reasoning system is capable of checking correctness of plans and finding plans for the operation of the RCS.
 Employs a programming methodology based on AProlog, algorithms for computing answer sets of programs of AProlog, and programming systems implementing these algorithms.
 User interface written in Java. Allows the user to specify the reasoning task to be performed, and then assembles into a program various AProlog modules, chosen according the components of the RCS that are involved in the task. Finally, the interface invokes program smodels to compute the answer sets of the AProlog program, and presents the results to the user.
SPACE SHUTTLE (CON’T) Large Practical System written in AProlog Importance of Careful Initial Design Simplified the Program Java Interface to Select Modules to Solve a Problem and Integrate Modules into Final AProlog Worked Well Structuring Problems as LP modules Useful for Reusability and Proving Correctness of Integration. System of Substantial Size Used for Planning Built on Theory of Action and Changes AProlog Allowed Use of Recursive Causal Laws System Tested and Worked. Not yet Used on a Space Mission. Demonstrates Practical Use of LPNMR Important to Collect and Publicize Successes in LPNMR
LPNMR COMPANIES XSB, INC. (Warren, XSB)  Advanced Techniques To Transform Unstructured Data
NEOTIDE (Simon, SMODELS) HERZUM (COLLABORATION with EXECURA –SPINOFF, CALABRIA, DLV)  Market OLEX (Semantic Categorizer) and
 HiLeX Advanced Semantic Information Extractor
SUMMARY AND CONCLUSIONS SIGNIFICANT DEVELOPMENTS/RELATIONSHIPS IN LPNMR LPNMR IS MATURE DISCIPLINE: THEORY/IMPLEMENTATIONS  BASED ON LOGICAL FOUNDATIONS – NOT ADHOCKERY
 SIGNIFICANT IMPLEMENTATIONS
 TOOLS AVAILABLE FOR REAL WORLD APPLICATIONS
 SEVERAL SYSTEMS SCALE TO LARGE PROBLEMS
 ADDITIONAL TOOLS NEEDED FOR USERS
FUTURE DIRECTIONS  ASP and Grounding – Extend to Variables Without Grounding
 SIGNIFICANT REALISTIC APPLICATION NEEDED
 EXPAND IMPLEMENTATION REPOSITORY
 EXPAND WORK TO LOGICBASED AI (and PROBABILISTIC METHODS)
 AGENTS AND BELIEFS, LOGIC AND LANGUAGE, MECHANICAL CHECKING, LOGIC FOR CAUSATION AND ACTIONS, COGNITIVE ROBOTICS, BIOLOGIC MODELS, …
 SEMANTIC WEB
Do'stlaringiz bilan baham: 