×

Let’s plan it deductively! (English) Zbl 0909.68166

Summary: The paper describes a transition logic, TL, and a deductive formalism for it. It shows how various important aspects (such as ramification, qualification, specificity, simultaneity, indeterminism etc.) involved in planning (or in reasoning about action and causality for that matter) can be modelled in TL in a rather natural way. (The deductive formalism for) TL extends the linear connection method proposed earlier by the author by embedding the latter into classical logic, so that classical and resource-sensitive reasoning coexist within TL. The attraction of a logical and deductive approach to planning is emphasized and the state of automated deduction briefly described.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anderson, A. R.; Belnap, N. D., (Entailment: The Logic of Relevance and Necessity, Vol. 1 (1975), Princeton University Press: Princeton University Press Princeton, NJ) · Zbl 0323.02030
[2] Agre, P., Computational research on interaction and agency, Artificial Intelligence, 72, 1-2, 1-52 (1995)
[3] Bibel, W.; Brüning, S.; Egly, U.; Rath, T., Towards an adequate theorem prover based on the connection method, (Plander, I., Proc. 6th International Conference on Artificial Intelligence and Information-Control of Robots (1994), World Scientific Publishing Company: World Scientific Publishing Company Singapore), 137-148
[4] Bibel, W.; del Cerro, L. F.; Fronhöfer, B.; Herzig, A., Plan generation by linear proofs: on semantics, (Metzing, D., Proc. GWAI-89 (1989), Springer: Springer Berlin), 49-62
[5] Blum, A. L.; Furst, M. L., Fast planning through planning graph analysis, (Proc. International Joint Conference on Artificial Intelligence (IJCAI-95). Proc. International Joint Conference on Artificial Intelligence (IJCAI-95), Montreal, Quebec (1995), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 1636-1642
[6] Brüning, S.; Groβe, G.; Hölldobler, S.; Schneeberger, J.; Sigmund, U.; Thielscher, M., Disjunction in plan generation by equational logic programming, (Horz, A., Beiträge zum 7 Workshop Planen und Konfigurieren, GI, Arbeitspapiere der GMD 723. Beiträge zum 7 Workshop Planen und Konfigurieren, GI, Arbeitspapiere der GMD 723, St. Augustin, Germany (1992)), 18-26
[7] Bibel, W.; Hölldobler, S.; Schaub, T., Wissensrepräsentation und Inferenz (1993), Vieweg: Vieweg Brauschweig
[8] Brüning, S.; Hölldobler, S.; Schneeberger, J.; Sigmund, U.; Thielscher, M., Disjunction in resource-oriented deductive planning, (Miller, D., Proc. International Logic Programming Symposium (ILPS). Proc. International Logic Programming Symposium (ILPS), Postersession (1993), MIT Press: MIT Press Cambridge, MA), 670
[9] Bibel, W., A deductive solution for plan generation, New Generation Computing, 4, 115-132 (1986) · Zbl 0624.68079
[10] Bibel, W., A deductive solution for plan generation, (Schmidt, J. W.; Thanos, C., Foundations of Knowledge Base Management (1986)), 413-436, Crete · Zbl 0645.68112
[11] Bibel, W., Automated Theorem Proving (1987), Vieweg: Vieweg Braunschweig · Zbl 0639.68092
[12] Bibel, W., Intellectics, (Shapiro, S. C., Encyclopedia of Artificial Intelligence (1992), John Wiley: John Wiley New York)
[13] Bibel, W., Towards predicative programming, (Lowry, M. R.; McCartney, R., Automating Software Design (1992), AAAI Press: AAAI Press Menlo Park, CA), 405-423
[14] Bibel, W., Deduction: Automated Logic (1993), Academic Press: Academic Press London · Zbl 0677.68094
[15] Brüning, S., Globally linear connection method, New Generation Computing Journal, 15, 369-402 (1997)
[16] Bornscheuer, S.-E.; Thielscher, M., Explicit and implicit indeterminism: reasoning about uncertain and contradictory specifications of dynamic systems, Journal of Logic Programming, 31, 1-3, 119-156 (1997) · Zbl 0883.68024
[17] Cervesato, I.; Pfenning, F., A linear logical framework, (Clarke, E., Proc. 11th Annual Symp. on Logic in Computer Science (1996), IEEE Computer Science Press: IEEE Computer Science Press Silverspring, MD), 264-275
[18] Crawford, J. M.; Auton, L. D., Experimental results on the crossover point in satisfiability problems, (Proc. 11th National Conference on Artificial Intelligence (AAAI-93). Proc. 11th National Conference on Artificial Intelligence (AAAI-93), Washington, DC (1993), AAAI Press: AAAI Press Menlo Park, CA), 21-27
[19] Cranefield, S. J.S., A logical framework for practical planning, (Proc. 10th European Conference on Artificial Intelligence (ECAI-92). Proc. 10th European Conference on Artificial Intelligence (ECAI-92), Vienna, Austria (1992), Wiley: Wiley London, UK), 633-637
[20] Eder, K.; Hölldobler, S.; Thielscher, M., An abstract machine for reasoning about situations, actions, and causality, (Dyckhoff, R.; Herre, H.; Schroeder-Heister, P., Proc. International Workshop on Extensions of Logic Programming (ELP). Proc. International Workshop on Extensions of Logic Programming (ELP), Lecture Notes in Artificial Intelligence, Vol. 1050 (1996), Springer: Springer Berlin), 137-151
[21] Fikes, R. E.; Nilsson, N. J., STRIPS: anew approach to the application of theorem proving to problem solving, Artificial Intelligence, 2, 189-208 (1971) · Zbl 0234.68036
[22] Frege, G., Begriffsschrift (1879), Louis Nebert: Louis Nebert Halle · JFM 11.0048.02
[23] Fronhöfer, B., Linearity and plan generation, New Generation Computing, 5, 213-225 (1987) · Zbl 0654.68100
[24] Fronhöfer, B., The Action-as-implication Paradigm (1996), CS Press: CS Press München
[25] Gallier, J., Constructive logics. Part II: Linear logic and proof nets, (Research Report PR2-RR-9 (May 1991), Digital Equipment Corporation: Digital Equipment Corporation Paris)
[26] Groβe, G.; Hölldobler, S.; Schneeberger, J.; Sigmund, U.; Thielscher, M., Equational logic programming, actions and change, (Apt, K., Proc. International Joint Conference and Symposium on Logic Programming (1992), MIT Press: MIT Press Cambridge, MA), 177-191
[27] Groβe, G.; Hölldobler, S.; Schneeberger, J., Linear deductive planning, Journal of Logic and Computation, 6, 2, 233-262 (1996) · Zbl 0854.68091
[28] Girard, J.-Y., Linear logic, Theoretical Computer Science, 50, 1, 1-102 (1987) · Zbl 0625.03037
[29] Green, C., Theorem proving by resolution as a basis for question-answering systems, (Meltzer, B.; Michie, D., Machine Intelligence, 4 (1969), Edinburgh University Press) · Zbl 0239.68015
[30] Groβe, G., State event logic, (Ph.D. Thesis (1996), Technical University Darmstadt: Technical University Darmstadt Darmstadt, Germany)
[31] Ginsberg, M. L.; Smith, D. E., Reasoning about action I: a possible worlds approach, Artificial Intelligence, 35, 2, 165-195 (1988) · Zbl 0645.68109
[32] Hölldobler, S.; Schneeberger, J., A new deductive approach to planning, New Generation Computing, 8, 225-244 (1990) · Zbl 0711.68026
[33] Hölldobler, S.; Thielscher, M., Actions and specificity, (Miller, D., Proc. International Logic Programming Symposium (1993)), 164-180
[34] Hölldobler, S.; Thielscher, M., Computing change and specificity with equational logic programs, Annals of Mathematics and Artificial Intelligence, 14, 99-133 (1995)
[35] Herrmann, C.; Thielscher, M., Reasoning about continuous processes, (Clancey, W.; Weld, D., AAAI-96—Proceedings of the National Conference on Artificial Intelligence. AAAI-96—Proceedings of the National Conference on Artificial Intelligence, Portland, OR (1996), AAAI Press: AAAI Press Palo Alto, CA), 639-644
[36] Kautz, H.; McAllester, D.; Selman, B., Encoding plans in propositional logic, (Aiello, L. C.; Doyle, J.; Shapiro, S., Proc. 5th International Conference on Principles of Knowledge Representation and Reasoning (KR-96). Proc. 5th International Conference on Principles of Knowledge Representation and Reasoning (KR-96), Cambridge, MA (1996), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 374-384
[37] Kowalski, R., Logic for Problem Solving (1979), North-Holland: North-Holland New York · Zbl 0426.68002
[38] Kautz, H.; Selman, B., Pushing the envelope: planning, propositional logic, and stochastic search, (Proc. National Conference on Artificial Intelligence (AAAI-96). Proc. National Conference on Artificial Intelligence (AAAI-96), Portland, OR (1996), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 1194-1201
[39] Kushmerick, N., Cognitivism and situated action: two views on intelligent agency, Computers and Artificial Intelligence, 15, 5, 393-417 (1996)
[40] Lambek, J., The mathematics of sentence structure, Amer. Math. Monthly, 65 (1958) · Zbl 0080.00702
[41] Lifschitz, V., Frames in the space of situations, Artificial Intelligence, 46, 365-376 (1990) · Zbl 0743.68122
[42] Lindner, M., Interactive planning for the assistance of human agents, (Ph.D. Thesis (1997), Techn. University: Techn. University Darmstadt, Germany)
[43] Laird, J. E.; Newell, A.; Rosenbloom, P. S., SOAR: an architecture for general intelligence, Artificial Intelligence, 33, 1, 1-64 (1987)
[44] Lin, F.; Reiter, R., Rules as actions: a situation calculus semantics for logic programs, Journal of Logic Programming, 31, 1-3, 299-330 (1997) · Zbl 0882.68031
[45] Letz, R.; Schumann, J.; Bayerl, S.; Bibel, W., SETHEO—a high-performance theorem prover for first-order logic, Journal of Automated Reasoning, 8, 2, 183-212 (1992) · Zbl 0759.68080
[46] McCarthy, J., Epistemological problems of artificial intelligence, (Proc. International Joint Conference on Artificial Intelligence. Proc. International Joint Conference on Artificial Intelligence, Cambridge, MA (1977), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 1038-1044
[47] McCune, W., Robbins algebras are boolean, Association for Automated Reasoning Newsletter, 35, 1-3 (1996)
[48] McCarthy, J.; Hayes, P., Some philosophical problems from the standpoint of artificial intelligence, (Meltzer, B.; Michie, D., Machine Intelligence, Vol. 4 (1969), Edinburgh University Press: Edinburgh University Press Edinburgh), 463-502 · Zbl 0226.68044
[49] Moser, M.; Ibens, O.; Letz, R.; Steinbach, J.; Goller, C.; Schumann, J.; Mayr, K., SETHEO and E-SETHEO, Journal of Automated Reasoning, 18, 2, 237-246 (1997)
[50] Masseron, M.; Tollu, C.; Vauzielles, J., Generating plans in linear logic, (Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 472 (1990), Springer: Springer Berlin), 63-75 · Zbl 0758.03017
[51] Nilsson, N. J., Logic and artificial intelligence, Artificial Intelligence, 47, 1-3, 31-56 (1991)
[52] Nirkhe, M.; Kraus, S.; Perlis, D., How to plan to meet a deadline between now and then, Journal of Logic and Computation (1994)
[53] Poole, D. L.; Mackworth, A. K.; Goebel, R. G., Computational Intelligence—A Logical Approach (1998), Oxford University Press: Oxford University Press New York · Zbl 0926.68104
[54] Poole, D. L., Probabilistic Horn abduction and Bayesian networks, Artificial Intelligence, 64, 1, 81-129 (1993) · Zbl 0792.68176
[55] Poole, D., Probabilistic partial evaluation: Exploiting rule structure in probabilistic inference, (Pollack, M., 15th International Joint Conference on Artificial Intelligence (IJCAI-97). 15th International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, Japan (1997), Morgan Kaufmann: Morgan Kaufmann Los Altos)
[56] M. Paramasivam, D.A. Plaisted, Automated deduction techniques for classification in description logic systems, Journal of Automated Reasoning, to appear.; M. Paramasivam, D.A. Plaisted, Automated deduction techniques for classification in description logic systems, Journal of Automated Reasoning, to appear. · Zbl 0893.68138
[57] Penberthy, J. S.; Weld, D., UCPOP: a sound, complete, partial order planner for ADL, (Proc. International Conference of Knowledge Representation and Reasoning (KR-92). Proc. International Conference of Knowledge Representation and Reasoning (KR-92), Cambridge, MA (1992), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 103-114
[58] Reiter, R., The frame problem in the situation calculus: a simple solution (sometimes) and a completeness result for goal regression, (Lifschitz, V., Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy (1991), Academic Press: Academic Press New York), 359-380 · Zbl 0755.68124
[59] Restall, G., On logics without contraction, (Ph.D. Thesis (1994), University of Queensland: University of Queensland Australia)
[60] Russell, S. J.; Norvig, P., Artificial Intelligence: A Modern Approach (1994), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[61] Sandewall, E., Combining logic and differential equations for describing real-world systems, (Brachman, R.; Levesque, H. J.; Reiter, R., Proc. International Conference on Principles of Knowledge Representation and Reasoning (KR-89). Proc. International Conference on Principles of Knowledge Representation and Reasoning (KR-89), Toronto, Ontario (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 412-420
[62] Stephan, W.; Biundo, S., A new logical framework for deductive planning, (Bajcsy, R., 13th International Joint Conference on Artificial Intelligence (IJCAI-93). 13th International Joint Conference on Artificial Intelligence (IJCAI-93), Chambery, France (1993), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 32-38
[63] Thielscher, M., Causality and the qualification problem, (Aiello, L. C.; Doyle, J.; Shapiro, S., KR-96—Proc. International Conference of Knowledge Representation and Reasoning (1996), KR Inc., Morgan Kaufmann: KR Inc., Morgan Kaufmann San Mateo, CA), 51-62
[64] Thielscher, M., Challenges for action theories: solving the ramification and qualification problem, (Habilitation thesis (1997), Techn. Universität Darmstadt: Techn. Universität Darmstadt Darmstadt, Germany)
[65] Thielscher, M., Ramification and causality, Artificial Intelligence, 89, 1-2, 317-364 (1997) · Zbl 1018.03514
[66] Wilkins, D. E.; Myers, K. L.; Lowrance, J. D.; Wesley, L. P., Planning and reacting in uncertain and dynamic environments, Journal of Experimental and Theoretical Artificial Intelligence, 6, 197-227 (1994)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.