|Norvig I 471
Reasoning/inference/artificial intelligence/AI research/Norvig/Russell: The three main formalisms for dealing with nonmonotonic inference—circumscription (McCarthy, 1980)(1), default logic (Reiter, 1980(2)), and modal nonmonotonic logic (McDermott and Doyle, 1980)(3) - were all introduced in one special issue of the AI Journal. Delgrande and Schaub (2003)(4) discuss the merits of the variants, given 25 years of hindsight.
Answer set programming can be seen as an extension of negation as failure or as a refinement of circumscription;
Norvig I 472
the underlying theory of stable model semantics was introduced by Gelfond and Lifschitz (1988)(5), and the leading answer set programming systems are DLV (Eiter et al., 1998)(6) and SMODELS (Niemel¨a et al., 2000)(7). The disk drive example comes from the SMODELS user manual (Syrjanen, 2000)(8). Lifschitz (2001)(9) discusses the use of answer set programming for planning. Brewka et al. (1997)(10) give a good overview of the various approaches to nonmonotonic logic. Clark (1978)(11) covers the negation-as-failure approach to logic programming and Clark completion. Van Emden and Kowalski (1976)(12) show that every Prolog program without negation has a unique minimal model. Recent years have seen renewed interest in applications of nonmonotonic logics to large-scale knowledge representation systems.
The BENINQ systems for handling insurance-benefit inquiries was perhaps the first commercially successful application of a nonmonotonic inheritance system (Morgenstern, 1998)(13). Lifschitz (2001)(9) discusses the application of answer set programming to planning.
Norvig I 473
Spatial reasoning: The earliest serious attempt to capture commonsense reasoning about space appears in the work of Ernest Davis (1986(14), 1990(15)). The region connection calculus of Cohn et al. (1997)(16) supports a form of qualitative spatial reasoning and has led to new kinds of geographical information systems; see also (Davis, 2006)(17). As with qualitative physics, an agent can go a long way, so to speak, without resorting to a full metric representation.
Psychological reasoning: Psychological reasoning involves the development of a working psychology for artificial agents to use in reasoning about themselves and other agents. This is often based on so-called folk psychology, the theory that humans in general are believed to use in reasoning about themselves and other humans. ((s) Cf. >Folk psychology/Philosophical theories).
When AI researchers provide their artificial agents with psychological theories for reasoning about other agents, the theories are frequently based on the researchers’ description of the logical agents’ own design. Psychological reasoning is currently most useful within the context of natural language understanding, where divining the speaker’s intentions is of paramount importance. Minker (2001)(18) collects papers by leading researchers in knowledge representation, summarizing 40 years of work in the field. The proceedings of the international conferences on Principles of Knowledge Representation and Reasoning provide the most up-to-date sources for work in this area.
1. McCarthy, J. (1980). Circumscription: A form of non-monotonic reasoning. AIJ, 13(1–2), 27–39.
2. Reiter, R. (1980). A logic for default reasoning. AIJ, 13(1–2), 81–132.
3. McDermott, D. and Doyle, J. (1980). Nonmonotonic logic: i. AIJ, 13(1–2), 41–72.
4. Delgrande, J. and Schaub, T. (2003). On the relation between Reiter’s default logic and its (major) variants. In Seventh European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, pp. 452–463.
5. Gelfond, M. and Lifschitz, V. (1988). Compiling circumscriptive theories into logic programs. In Non-
Monotonic Reasoning: 2nd International Workshop Proceedings, pp. 74–99.
6. Eiter, T., Leone, N., Mateis, C., Pfeifer, G., and Scarcello, F. (1998). The KR system dlv: Progress report, comparisons and benchmarks. In KR-98, pp. 406–417.
7. Niemela, I., Simons, P., and Syrjanen, T. (2000). Smodels: A system for answer set programming.
In Proc. 8th International Workshop on Non-Monotonic Reasoning.
8. Syrjanen, T. (2000). Lparse 1.0 user’s manual.saturn.tcs.hut.fi/Software/smodels.
9. Lifschitz, V. (2001). Answer set programming and plan generation. AIJ, 138(1–2), 39–54.
10. Brewka, G., Dix, J., and Konolige, K. (1997). Nononotonic Reasoning: An Overview. CSLI Publications.
11. Clark, K. L. (1978). Negation as failure. In Gallaire, H. and Minker, J. (Eds.), Logic and Data Bases, pp. 293–322. Plenum.
12. Van Emden, M. H. and Kowalski, R. (1976). The semantics of predicate logic as a programming language. JACM, 23(4), 733–742.
13. Morgenstern, L. (1998). Inheritance comes of age: Applying nonmonotonic techniques to problems in industry. AIJ, 103, 237–271
14. Davis, E. (1986). Representing and Acquiring Geographic Knowledge. Pitman and Morgan Kaufmann.
15. Davis, E. (1990). Representations of Commonsense Knowledge. Morgan Kaufmann
16. Cohn, A. G., Bennett, B., Gooday, J. M., and Gotts, N. (1997). RCC: A calculus for region based qualitative spatial reasoning. GeoInformatica, 1, 275–316.
17. Davis, E. (2006). The expressivity of quantifying over regions. J. Logic and Computation, 16, 891– 916.
18. Minker, J. (2001). Logic-Based Artificial Intelligence. Kluwer_____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010