Abstract
Problems in robot planning are approached by proving theorems in a new formulation of situational logic. A machine-oriented deductive-tableau inference system is adapted to this logic, with special attention being paid to the derivation of conditional and recursive plans. Equations and equivalences of the situational logic have been built into a unification algorithm for the system. Inductive proofs of theorems for even the simplest planning problems have been found to require challenging generalizations.
This research was supported in part by the National Science Foundation under grants MCS-82-14523 and MCS-81-05565, by the Defense Advanced Research Projects Agency under Contract N00039-84-C-0211, by the United States Air Force Office of Scientific Research under Contract AFOSR-81-0014, by the Office of Naval Research under Contract N00014-84-C-0706, by United States Army Research under Contract DAJA-45-84-C-0040, and by a contract from the International Business Machines Corporation.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. S. Boyer and J S. Moore, A Computational Logic, Academic Press, Orlando, Fla., 1979.
V. J. Digricoli, Equality-based binary resolution, Journal of the ACM, Vol. 33, No. 2, April 1986, to appear.
M. Fay, First-order unification in an equational theory, Proceedings of the Fourth Workshop on Automated Deduction, Austin, Texas, Feb. 1979, pp. 161–167.
R. E. Fikes and N. J. Nilsson, STRIPS: A new approach to the application of theorem proving to problem solving, Artificial Intelligence, Vol. 2, No. 3–4, Winter 1971, pp. 189–208.
C. C. Green, Application of theorem proving to problem solving, Proceedings of the International Joint Conference on Artificial Intelligence, Washington, D.C., May 7–9, 1969, pp. 219–239.
J.-M. Hullot, Canonical forms and unification, Proceedings of the Fifth Conference on Automated Deduction, Les Arcs, France, July 8–11, 1980, pp. 318–334.
R. Kowalski, Logic for Problem Solving, North-Holland, New York, N.Y., 1979.
V. Lifschitz, Circumscription in the blocks world, Unpublished Report, Stanford University, Stanford, Calif., Dec. 1985.
J. McCarthy, Situations, actions, and causal laws, Technical Report, Stanford University, Stanford, Calif., 1963. Reprinted in Semantic Information Processing, Marvin Minsky, editor, MIT Press, Cambridge, Mass., 1968, pp. 410–417.
J. McCarthy and P. Hayes, Some philosophical problems from the standpoint of artificial intelligence, Machine Intelligence 4, B. Meltzer and D. Michie, editors, American Elsevier, New York, N. Y., 1969, pp. 463–502.
Z. Manna and R. Waldinger, A deductive approach to program synthesis, ACM Transactions on Programming Languages and Systems, Vol. 2, No. 1, Jan. 1980, pp. 90–121.
Z. Manna and R. Waldinger, The origin of the binary-search paradigm, Proceedings of the Ninth International Joint Conference on Artificial Intelligence, Los Angeles, Calif., Aug. 18–23, 1985, pp. 222–224.
Z. Manna and R. Waldinger, The Logical Basis for Computer Programming, Vol. 1: Deductive Reasoning, Addison-Wesley, Reading, Mass., 1985.
Z. Manna and R. Waldinger, Special relations in automated deduction, Journal of the ACM, Vol. 33, No. 1, Jan. 1986, pp. 1–60.
A. Martelli and G. Rossi, An algorithm for unification in equational theories, Proceedings of the Third Symposium on Logic Programming, Salt Lake City, Utah, Sept. 21–25, 1986 (to appear).
J. B. Morris, E-resolution: Extension of resolution to include the equality relation, International Joint Conference on Artificial Intelligence, Washington, D.C., May 7–9, 1969, pp. 287–294.
N. V. Murray, Completely nonclausal theorem proving, Artificial Intelligence, Vol. 18, No. 1, 1982, pp. 67–85.
G. Polya, How to Solve It, Doubleday and Company, Garden City, N.Y., 1957.
E. D. Sacerdoti, A Structure for Plans and Behavior, Elsevier North-Holland, New York, N. Y., 1977.
M. E. Stickel, Automated deduction by theory resolution, Journal of Automated Reasoning, Vol. 1, No. 4, 1985, pp. 333–355.
G. J. Sussman, A Computational Model of Skill Acquisition, Ph. D. Thesis, MIT, Cambridge, Mass., 1973.
R. J. Waldinger and R. C. T. Lee, PROW: A step toward automatic program writing, Proceedings of the International Joint Conference on Artificial Intelligence, Washington, D. C., May 7–9, 1969, pp. 241–252.
D. H. D. Warren, WARPLAN: A system for generating plans, Technical Report, University of Edinburgh, Edinburgh, Scotland, 1974.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1986 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Manna, Z., Waldinger, R. (1986). How to clear a block: Plan formation in situational logic. In: Siekmann, J.H. (eds) 8th International Conference on Automated Deduction. CADE 1986. Lecture Notes in Computer Science, vol 230. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-16780-3_126
Download citation
DOI: https://doi.org/10.1007/3-540-16780-3_126
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-16780-8
Online ISBN: 978-3-540-39861-5
eBook Packages: Springer Book Archive