Advertisement

Introduction to Logic-Based Artificial Intelligence

  • Jack Minker
Chapter
  • 417 Downloads
Part of the The Springer International Series in Engineering and Computer Science book series (SECS, volume 597)

Abstract

In this chapter I provide a brief introduction to the field of Logic-Based Artificial Intelligence (LBAI). I then discuss contributions to LBAI contained in the chapters and some of the highlights that took place at the Workshop on LBAI from which the papers are drawn. The areas of LBAI represented in the book are: commonsense reasoning; knowledge representation; nonmonotonic reasoning; abductive and inductive reasoning; logic, probability and decision making; logic for causation and actions; planning and problem solving; logic, planning and high-level robotics; logic for agents and actions; theory of beliefs; logic and language; computational logic; system implementations; and logic applications to mechanical checking and data integration.

Keywords

Actions and agents abductive reasoning beliefs commonsense reasoning computational logic inductive reasoning knowledge base system implementations knowledge representation logic and causation in planning logic and data integration logic applications to mechanical checking logic planning and high-level robotics natural language and logic nonmonotonic reasoning planning and problem solving possibilistic logic 

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Allen, J. (1984). Towards a general theory of action and time. Artificial Intelligence, 23:123–154.zbMATHCrossRefGoogle Scholar
  2. Apt, K., Blair, H., and Walker, A. (1988). Towards a theory of declarative knowledge. In Minker, J., editor, Foundations of Deductive Databases and Logic Programming, pages 89–148. Morgan Kaufmann Pub., Los Altos, CA.Google Scholar
  3. Apt, K. R. and van Emden (1982) Contributions to the theory of logic programming J. ACM, 29(3):841–862.zbMATHCrossRefGoogle Scholar
  4. Bacchus, F., Grove, A., Halpern, J., and Koller, D. (1993). Statistical foundations for default reasoning. Proc. IJCAI-93, pages 563–569.Google Scholar
  5. Bacchus, F. (1990) Representing and Reasoning with Probabilistic Knowledge. MIT Press.Google Scholar
  6. Bacchus, F. and Kabanza, F. (2000). Using temporal logics to express search control knowledge for planning. Artificial Intelligence, 16:123–191.MathSciNetCrossRefGoogle Scholar
  7. Baral, C. and Gelfond, M. (1994). Logic programming and knowledge representation. Journal of Logic Programming, 19/20:73–148.MathSciNetCrossRefGoogle Scholar
  8. Boutilier, C., Reiter, R., Soutchanski, M., and Thrun, S. (2000). Decision-theoretic, high level agent programming in the situation calculus. In Proc. Amer. Assoc. for Artificial Intelligence — 2000.Google Scholar
  9. Boyer, R. S. and Moore, J. S. (1979). A Computational Logic. Academic Press.Google Scholar
  10. Boyer, R. S. and Moore, J. S. (1997). A Computational Logic Handbook, Second Edition. Academic Press.Google Scholar
  11. Brass, S., Dix, J., and Przymusinski, T. C. (1996). Super logic programs. Knowledge Representation, pages 529–540.Google Scholar
  12. Brooks, R. A. (1991). Intelligence without reason. pages 569–595. Morgan Kaufmann.Google Scholar
  13. Cadoli, M. and Lenzerini, M. (1991). The complexity of closed world reasoning and circumscription. Knowledge Representation, pages 550–555.Google Scholar
  14. Cadoli, M. and Schaerf, M. (1992). A survey on complexity results for nonmonotonic logics. Technical report, University di Roma “La Sapienza”, Dipartiment o di Informatica e sistemistica, Roma, Italy.Google Scholar
  15. Chandra, A. and Harel, D. (1985). Horn clause queries and generalizations. Journal of Logic Programming, 2(1):1–15.MathSciNetzbMATHCrossRefGoogle Scholar
  16. Chang, C. L. and Lee, R. C. T. (1973). Symbolic Logic and Mechanical Theorem Proving. Academic Press, New York.zbMATHGoogle Scholar
  17. Cholewiński, P., Marek, V. W. and Mikitiuk, A., and Truszczyński, M. (1999). Computing with default logic. Artificial Intelligence, 112.Google Scholar
  18. Cholewiński, P., Marek, W., and Truszczyński, M. (1996). Default reasoning system deres. In Proceedings of KR-96, pages 518–528, San Francisco, California. Morgan Kaufmann.Google Scholar
  19. Clark, K. L. (1978). Negation as Failure. In Gallaire, H. and Minker, J., editors, Logic and Data Bases, pages 293–322. Plenum Press, New York.CrossRefGoogle Scholar
  20. Colmerauer, A. (1985). Prolog in 10 figures. Communications of the ACM, 28(12):1296–1310.MathSciNetCrossRefGoogle Scholar
  21. Colmerauer, A., Kanoui, H., Pasero, R., and Roussel, P. (1973). Un systeme de communication homme-machine en francais. TR, Groupe de Intelligence Artificielle Univ. de Aix-Marseille II, Marseille.Google Scholar
  22. Dantsin, E., Eiter, T., Gottlob, G., and Voronkov, A. (1997). Complexity and expressive power of logic programming. In Proc. of 12th annual IEEE Conference on Computational Complexity, pages 82–101.Google Scholar
  23. Davis, E. (1998). The naive physics perplex. AI Magazine, 19(14):51–79.Google Scholar
  24. Davis, E. (1999). Guide to axiomatizing domains in first-order logic. Electronic Newsletter on Reasoning About Actions and Change.Google Scholar
  25. Davis, M. and Putnam, H. (1960). A computing procedure for quantification theory. J. ACM, 7:201–215.MathSciNetzbMATHCrossRefGoogle Scholar
  26. Dimopoulos, Y. and Kakas, A. (1995). Abduction and inductive learning. In De Raedt, L., editor, Proc. 5th Inductive Logic Programming Workshop (ILP95), pages 25–28, Leuven, Belgium. KU Leuven.Google Scholar
  27. Eiter, T., Leone, N., Mateis, C., Pfeifer, G., and Scarcello, F. (1997). A deductive system for nonmonotonic reasoning. In Dix, J., Furbach, U., and Nerode, A., editors, Proc. 4th Int’l. Conf. on Logic Programming and Nonmonotonic Reasoning, number 1265 in Lecture Notes in AI. Springer.Google Scholar
  28. Fikes, R. and Nilsson, N. (1971). STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence, 5(2): 189–208.CrossRefGoogle Scholar
  29. Fikes, R. and Nilsson, N. (1993). STRIPS, a retrospective. Journal of Artificial Intelligence, 59(1/2):227–232.CrossRefGoogle Scholar
  30. Fitting, M. C. (2000). Fixpoint semantics for logic programming — a survey. Theoretical Computer Science. To appear.Google Scholar
  31. Gallaire, H. and Minker, J., editors (1978). Logic and Databases. Plenum Press, New York.Google Scholar
  32. Gallaire, H., Minker, J., and Nicolas, J.-M. (1984). Logic and databases: A deductive approach. ACM Computing Surveys, 16(2):153–185.MathSciNetzbMATHCrossRefGoogle Scholar
  33. Geffner, H. (1990). Causal theories for nonmonotonic reasoning. In Proc. AAAI-90, pages 524–530. AAAI Press.Google Scholar
  34. Gelfond, M. and Lifschitz, V. (1988). The stable model semantics for logic programming. In Kowalski, R. and Bowen, K., editors, Logic Programming: Proc. 5th Int’l Conf. and Symp., pages 1070–1080.Google Scholar
  35. Gelfond, M. and Lifschitz, V. (1990). Logic programs with classical negation. In Warren, D. and Szeredi, P., editors, Proc. 7th Int’l Conf. on Logic Programming, pages 579–597, Jerusalem, Israel. MIT Press.Google Scholar
  36. Gelfond, M. and Lifschitz, V. (1992). Representing actions in extended logic programming. In Apt, K., editor, Proc. Joint Int’l Conf. and Symp. on Logic Programming, pages 559–573.Google Scholar
  37. Gelfond, M. and Lifschitz, V. (1993). Representing actions and change by logic programs. Journal of Logic Programming, 17(2,3,4):301–323.MathSciNetzbMATHCrossRefGoogle Scholar
  38. Gelfond, M. and Lifschitz, V. (1998). Action languages. Electronic Transactions on AI, 3. (http://www.ep.liu.se/ea/cis/1998/016)
  39. Gelfond, M., Lifschitz, V., and Rabinov, A. (1991). What are the limitations of the situation calculus? In Boyer, R., editor, Automated Reasoning: Essays in Honor of Woody Bledsoe, pages 167–179. Kluwer.Google Scholar
  40. Ginsberg, M. and Smith, D. (1988a). Reasoning about action I: a possible world approach. Artificial Intelligence, 35:165–195.MathSciNetzbMATHCrossRefGoogle Scholar
  41. Ginsberg, M. and Smith, D. (1988b). Reasoning about action II: the qualification problem. Artificial Intelligence, 35:311–342.MathSciNetzbMATHCrossRefGoogle Scholar
  42. Giunchiglia, E. and Lifschitz, V. (1998). An action language based on causal explanation: Prelim. Rpt. In Proc. AAAI-98, pages 623–630. AAAI Press.Google Scholar
  43. Green, C. (1969). Theorem proving by resolution as a basis for question — answering systems. In Michie, B. M. D., editor, Machine Intelligence 4, pages 183–205. Edinburgh University Press, New York.Google Scholar
  44. Green, C. and Raphael, B. (1968a). Research in intelligent question answering systems. Proc. ACM 23rd National Conf., pages 169–181.Google Scholar
  45. Green, C. and Raphael, B. (1968b). The use of theorem-proving techniques in question-answering systems. Proc. ACM 23rd National Conf..Google Scholar
  46. Haas, A. (1987). The case for domain-specific frame axioms. In Brown, F. M., editor, The Frame Problem in Artificial Intelligence, (Proc. 1987 Workshop).Google Scholar
  47. Hanks, S. and McDermott, D. (1987). Nonmonotonic logic and temporal projection. Artificial Intelligence, 33(3):379–412.MathSciNetzbMATHCrossRefGoogle Scholar
  48. Hayes, P. (1973a). Computation and deduction. In Proceedings of the 2nd Symp. on Mathematical Foundations of Computer Science, pages 107–113, Czechoslovakia: Czechoslovakian Academy of Sciences.Google Scholar
  49. Hayes, P. (1985a). Naive physics i: ontology for liquids. In Hobbs, J. and Moore, R., editors, Formal Theories of the Commonsense World, chapter 3, pages 71–107. Ablex, Norwood, New Jersey.Google Scholar
  50. Hayes, P. (1985b). The second naive physics manifesto. In Hobbs, J. and Moore, R., editors, Formal Theories of the Commonsense World, chapter 1, pages 1–36. Ablex, Norwood, New Jersey.Google Scholar
  51. Hayes, P. J. (1973b). The frame problem and related problems in artificial intelligence. Artificial and Human Thinking, pages 45–59.Google Scholar
  52. Jaffar, J. and Maher, M. (1994). Constraint logic programming: a survey. Journal of Logic Programming, 19–20:503–581.MathSciNetCrossRefGoogle Scholar
  53. Jenkin, M., Lespérance, Y., Levesque, H., Lin, F., Lloyd, J., Marcu, D., Reiter, R., Scherl, R., and Tam, K. (1997). A logical approach to portable high-level robot programming. In Proc. 10th Australian Joint Conf. on Artificial Intelligence (AI’97), Perth, Australia.Google Scholar
  54. Jennings, N. R., Sycara, K., and Wooldridge, M. (1998). A roadmap of agent research and development. Autonomous Agents and Multi-Agent Systems, 1:7–38.CrossRefGoogle Scholar
  55. Kakas, A. C., Kowalski, R. A., and Toni, F. (1993). Abductive logic programming. Journal of Logic and Computation, 6(2):719–770.MathSciNetGoogle Scholar
  56. Kaufmann, M. and Moore, J. S. (1997). An industrial strength theorem prover for a logic based on Common Lisp. IEEE Transactions on Software Engineering, 23(4):203–213.CrossRefGoogle Scholar
  57. Kaufmann, M. and Moore, J. S. (1999). The ACL2 user’s manual. http://www.cs.utexas.edu/users/moore/acl2/acl2-doc.html.
  58. Kautz, H. and Selman, B. (1999b). Unifying sat-based and graph-based planning. In Proc. of IJCAI 99, pages 318–325.Google Scholar
  59. Kowalski, R. (1974). Predicate logic as a programming language. Proc. IFIP 4, pages 569–574.Google Scholar
  60. Lespérance, Y., Levesque, H., Lin, F., Marcu, D., Reiter, R., and Scherl, R. (1994). A logical approach to high-level robot programming — a progress report. In Control of the Physical World by Intelligent Systems, Working Notes of the 1994 AAAI Fall Symp.Google Scholar
  61. Lespérance, Y., Levesque, H. J., Lin, F., Marcu, D., Reiter, R., and Scherl, R. B. (1994). A logical approach to high-level robot programming: A progress report. In B. Kuipers, editor, Control of the Physical World by Intelligent Systems: Papers from 1994 AAAI Fall Symp..Google Scholar
  62. Levesque, H., Reiter, R., Lespérance, Y., Lin, F., and Scherl, R. (1997). GOLOG: a logic programming language for dynamic domains. J. of Logic Programming, Special Issue on Actions, 31(1–3):59–83.zbMATHGoogle Scholar
  63. Lifschitz, V. (1987). On the semantics of STRIPS. In Georgeff, M. and Lansky, A., editors, Reasoning about Actions and Plans, pages 1–9. Morgan Kaufmann, Morgan Kaufmann, CA.CrossRefGoogle Scholar
  64. Lin, F. (1995). Embracing causality in specifying the indirect effects of actions. In Proc. IJCAI-95, pages 1985–1991.Google Scholar
  65. Lobo, J., Minker, J., and Rajasekar, A. (1992). Foundations of Disjunctive Logic Programming. MIT Press.Google Scholar
  66. Loveland, D. (1978). Automated Theorem Proving: A Logical Basis. North-Holland Publishing Co.Google Scholar
  67. Loveland, D. (1999). Automated deduction: Looking ahead. AI Magazine, 20(l):77–98.Google Scholar
  68. Marek, V. and Truszczyński, M. (1993). Nonmonotonic Logic: Context-Dependent Reasoning. Springer-Verlag.Google Scholar
  69. McCain, N. and Turner, H. (1997). Causal theories of action and change. In Proc. AAAI-97, pages 460–465.Google Scholar
  70. McCarthy, J. (1959). Programs with commonsense. In Proc. Teddington Conf. on the Mechanisation of Thought Processes, pages 75–91, London. Her Majesty’s Stationery Office. Reprinted (with an added section on ‘Situations, Actions and Causal Laws’) in Semantic Information Processing, ed. M. Minsky (Cambridge, MA: MIT Press (1963)).Google Scholar
  71. McCarthy, J. (1963). Situations, actions and causal laws. Memo 2. AI Laboratory, Stanford University, Stanford, CA.Google Scholar
  72. McCarthy, J. (1977). Epistemological problems in artificial intelligence. In Proc. 5th International Conference on Artificial Intelligence, pages 1038–1044.Google Scholar
  73. McCarthy, J. (1978). History of lisp. In Wexblatt, R., editor, History of Programming Languages: Proc. of the ACM SIGPLAN Conf., pages 3–57. Academic Press. Published in 1981 (Conf. date: 1978).Google Scholar
  74. McCarthy, J. (1980). Circumscription — a form of non-monotonic reasoning. Artificial Intelligence, 13(1 and 2):27–39.MathSciNetzbMATHCrossRefGoogle Scholar
  75. McCarthy, J. and Hayes, P. (1969b). Some philosophical problems from the standpoint of artificial intelligence. In Meltzer, B. and Michie, D., editors, Machine Intelligence 4, pages 463–502. Edinburgh University Press.Google Scholar
  76. McCune, W. (1997). Solution of the Robbins problem. J. Automated Reasoning, 19(3):263–276.MathSciNetzbMATHCrossRefGoogle Scholar
  77. Minker, J. (1988). Perspectives in deductive databases. Journal of Logic Programming, 5:33–60.MathSciNetCrossRefGoogle Scholar
  78. Minker, J. (1993). An overview of nonmonotonic reasoning and logic programming. Journal of Logic Programming, 17(2, 3 and 4):95–126.MathSciNetzbMATHCrossRefGoogle Scholar
  79. Minker, J. (1994). Overview of disjunctive logic programming. Journal of Artificial Intelligence & Mathematics, 12(1–2): 1–24.MathSciNetCrossRefGoogle Scholar
  80. Minker, J. (1996). Logic and databases: a 20 year retrospective. In Pedreschi, D. and Zaniolo, C., editors, Logic in Databases, pages 3–57. Springer. Proc. Int. Workshop LID’96, San Miniato, Italy.Google Scholar
  81. Minker, J. (1999a). Logic and databases: a 20 year retrospective — updated in honor of Ray Reiter. In Levesque, H. J. and Pirri, F., editors, Logical Foundations for Cognitive Agents: Contributions in Honor of Ray Reiter, pages 234–299. Springer.Google Scholar
  82. Minker, J. (1999b). The workshop on logic-based artificial intelligence. AI Magazine, 20(4):21–47.Google Scholar
  83. Minsky, M. (1975). A framework for representing knowledge. In Winston, P., editor, The Psych. of Computer Vision, pages 211–277. McGraw-Hill, NY.Google Scholar
  84. Moore, R. C. (1985). Semantical considerations on nonmonotonic logic. Artificial Intelligence, 25(l):75–94.MathSciNetzbMATHCrossRefGoogle Scholar
  85. Niemela, I. and Simons, P. (1997). Smodels — an implementation of the stable model and well-founded semantics for normal logic programs. In Dix, J., Furbach, U., and Nerode, A., editors, Logic Programming and Nonmonotonic Reasoning — 4th Int. Conf., pages 420–429, Dagstuhl, Germany. Springer.CrossRefGoogle Scholar
  86. Nilsson, N. (1982). Principles of Artificial Intelligence. Springer-Verlag.Google Scholar
  87. Nilsson, N. (1984). Shakey the robot. Technical Note 323, SRI International, Menlo Park, California.Google Scholar
  88. Pednault, E. (1989). ADL: Exploring the middle ground between STRIPS and the situation calculus. In Brachman, R., Levesque, H., and Reiter, R., editors, Proc. First Int%l Conf. on Principles of Knowledge Representation and Reasoning, pages 324–332.Google Scholar
  89. Peirce, C. S. (1883). A theory of probable inference. note b. the logic of relatives. In Studies in logic by members of the Johns Hopkins Univ., pages 187–203.CrossRefGoogle Scholar
  90. Plotkin, G. (1969). A note on inductive generalisation. In Meltzer, B. and Michie, D., editors, Machine Intelligence 5, pages 153–163. Edinburgh University Press, Edinburgh.Google Scholar
  91. Plotkin, G. (1971). Automatic Methods of Inductive Inference. PhD thesis, Edinburgh University.Google Scholar
  92. Przymusinski, T. C. (1988). On the declarative semantics of deductive databases and logic programming. In Minker, J., editor, Foundations of Deductive Databases and Logic Programming, chapter 5, pages 193–216. Morgan Kaufmann Pub., Washington, D.C.Google Scholar
  93. Quillian, R. (1968). Semantic Memory. In Minsky, M., editor, Semantic Information Processing, pages 216–270. MIT Press, Cambridge, Massachusetts.Google Scholar
  94. Rao, P., Sagonas, K., Swift, T., Warren, D., and Friere, J. (1997). XSB: A system for efficiently computing well-founded semantics. In Dix, J., Ferbach, U., and Nerode, A., editors, Logic and Nonmonotonic Reasoning — 4t h Int’l. Conf., LPNMR’97, pages 430-440.CrossRefGoogle Scholar
  95. Reiter, R. (1980). A Logic for Default Reasoning. Artificial Intelligence, 13(1 and 2):81–132.MathSciNetzbMATHCrossRefGoogle Scholar
  96. Reiter, R. (1991). The frame problem in the situation calculus: A simple solution (sometimes) and a completeness result for goal regression. In Lifschitz, V., editor, AI and Mathematical Theory of Computation: Papers in Honor of John McCarthy, pages 359–380. Academic Press.Google Scholar
  97. Reiter, R. (1993). Proving properties of states in the situation calculus. Artificial Intelligence, 64:337–351.MathSciNetzbMATHCrossRefGoogle Scholar
  98. Robinson, J. A. (1965). A machine oriented logic based on the resolution principle. Journal of the ACM, 12:23–41.zbMATHCrossRefGoogle Scholar
  99. Russell, S. and Norvig, P. (1995). Artificial Intelligence: A Modern Approach. Prentice Hall.Google Scholar
  100. Sandewall, E. (1995). Features and Fluents, volume 1. Oxford University Press.Google Scholar
  101. Schank, R. and Abelson, R. (1977). Scripts, Plans, Goals, and Understanding. Lawrence Erlebaum.Google Scholar
  102. Schubert, L. (1990). Monotonic solution of the frame problem in the situation calculus: an efficient method for worlds with fully specified actions. In Kyburg, H., Loui, R., and Carlson, G., editors, Knowledge Representation and Defeasible Reasoning, pages 23–67. Kluwer.Google Scholar
  103. Shanahan, M. P. (1997). Solving the Frame Problem: A Mathematical Investigation of the Common Sense Law of Inertia. MIT Press.Google Scholar
  104. van Emden, M. and Kowalski, R. (1976). The Semantics of Predicate Logic as a Programming Language. J. ACM, 23(4):733-742.zbMATHCrossRefGoogle Scholar
  105. Van Gelder, A. (1988). Negation as failure using tight derivations for general logic programs. In Minker, J., editor, Found. of Deductive Databases and Logic Programming, pages 149–176. Morgan Kaufmann.Google Scholar
  106. Van Gelder, A., Ross, K., and Schlipf, J. (1988). Unfounded sets and well-founded semantics for general logic programs. In Proc. 7th ACM Symp. on Principles of Database Systems., pages 221–230.Google Scholar
  107. Warren, D. S. (1999). The XSB programming system. Technical report, State University of New York at Stonybrook. http://www. cs.sunysb.edu/sbprolog/xsb-page.html.
  108. Wooldridge, M. and Jennings, N. (1995). Intelligent agents: Theory and practice. The Knowledge Engineering Review, 10(2): 115–152.CrossRefGoogle Scholar
  109. Zaniolo, C., Arni, N., and Ong, K-L. (1993). Negation and aggregates in recursive rules. Proceedings of DOOD93, pages 204–221.Google Scholar

Copyright information

© Springer Science+Business Media New York 2000

Authors and Affiliations

  • Jack Minker
    • 1
  1. 1.Department of Computer Science and Institute for Advanced Computer StudiesUniversity of MarylandCollege ParkUSA

Personalised recommendations