Abstract
Most agents can acquire information about their environments as they operate. A good plan for such an agent is one that not only achieves the goal, but is also executable, i.e., ensures that the agent has enough information at every step to know what to do next. In this paper, we present a formal account of what it means for an agent to know how to execute a plan and to be able to achieve a goal. Such a theory is a prerequisite for producing specifications of planners for agents that can acquire information at run time. It is also essential to account for cooperation among agents. Our account is more general than previous proposals, correctly handles programs containing loops, and incorporates a solution to the frame problem. It can also be used to prove programs containing sensing actions correct.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Agre, P.E., and D. Chapman, ‘What are plans for?', Robotics and Autonomous Systems 6 (1990), 17–34.
Davis, E., ‘Knowledge preconditions for plans', Journal of Logic and Computation 4,5 (1994), 721–766.
Etzioni, O., S. Hanks, D. Weld, D. Draper, N. Lesh, and M. Williamson. ‘An approach to planning with incomplete information', in B. Nebel, C. Rich, and W. Swartout (eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Third International Conference, Cambridge, MA, pp. 115–125, 1992.
Fikes, R., and N. Nilsson, ‘STRIPS: A new approach to the application of theorem proving to problem solving', Artificial Intelligence 2 (1971), 189–208.
Golden, K., and D. Weld, ‘Representing sensing actions: the middle ground revisited', in L. C. Aiello, J. Doyle, and S. C. Shapiro (eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Fifth International Conference, Cambridge, MA, pp. 174–185, 1996.
Green, C., ‘Theorem proving by resolution as a basis for question-answering systems', in B. Meltzer and D. Michie (eds.), Machine Intelligence, Vol. 4, New York: American Elsevier, pp. 183–205, 1969.
Haas, A. R., ‘The case for domain-specific frame axioms', in F. Brown (ed.), The Frame Problem in Artificial Intelligence: Proceedings of the 1987 Workshop, Lawrence, KA, pp. 343–348, 1987.
Krebsbach, K., D. Olawsky, and M. Gini, ‘An empirical study of sensing and defaulting in planning', in Proceedings of the First Conference on AI Planning Systems, San Mateo, CA, pp. 136–144, 1992.
Kripke, S. A., ‘Semantical considerations on modal logic', Acta Philosophica Fennica 16 (1963), 83–94.
Lakemeyer, G., and H. J. Levesque, ‘AOL: a Logic of acting, sensing, knowing, and only-knowing', in Principles of Knowledge Representation and Reasoning: Proceedings of the Sixth International Conference (KR-98), pp. 316–327, 1998.
Levesque, H. J., ‘What is planning in the presence of sensing?', in Proceedings of the Thirteenth National Conference on Artificial Intelligence, Portland, OR, pp. 1139–1146, 1996.
Levesque, H. J., R. Reiter, Y. LespÉrance, F. Lin, and R. B. Scherl, ‘GOLOG: a logic programming language for dynamic domains', Journal of Logic Programming 31 (1997), 59–84.
Lin, F. and H. J. Levesque, ‘What robots can do: robot programs and effective achievability', Artificial Intelligence 101,1–2 (1998), 201–226.
Lin, F., and R. Reiter, ‘State constraints revisited', Journal of Logic and Computation 4,5 (1994), 655–678.
McCarthy, J., and P. Hayes, ‘Some philosophical problems from the standpoint of artificial intelligence', in B. Meltzer and D. Michie (eds.), Machine Intelligence, Vol. 4, Edinburgh, UK, Edinburgh University Press, pp. 463–502, 1969.
Moore, R. C., ‘A formal theory of knowledge and action', in J. R. Hobbs and R. C. Moore (eds.), Formal Theories of the Common Sense World, Norwood, NJ, Ablex Publishing, pp. 319–358, 1985.
Morgenstern, L., ‘Knowledge preconditions for actions and plans', in Proceedings of the Tenth International Joint Conference on Artificial Intelligence, Milan, Italy, pp. 867–874, 1987.
Pednault, E. P. D., ‘ADL: exploring the middle ground between STRIPS and the situation calculus', in R. Brachman, H. Levesque, and R. Reiter (eds.), Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning, Toronto, ON, pp. 324–332, 1989.
Peot, M., and D. Smith, ‘Conditional nonlinear planning', in: Proceedings of the First Conference on AI Planning Systems, San Mateo, CA, pp. 189–197, 1992.
Reiter, R., ‘The frame problem in the situation calculus: a simple solution (sometimes) and a completeness result for goal regression', in V. Lifschitz (ed.), Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy, San Diego, CA: Academic Press, pp. 359–380, 1991.
Scherl, R. B., and H. J. Levesque, ‘The frame problem and knowledge-producing actions', in Proceedings of the Eleventh National Conference on Artificial Intelligence, Washington, DC, pp. 689–695, 1993.
Schoppers, M. J., ‘Building plans to monitor and exploit open-loop and closed-loop dynamics', in Proceedings of the First Conference on AI Planning Systems, San Mateo, CA, pp. 204–213, 1992.
Schubert, L., ‘Monotonic solution to the frame problem in the situation calculus: an efficient method for worlds with fully specified actions', in H. Kyberg, R. Loui, and G. Carlson (eds.), Knowledge Representation and Defeasible Reasoning, Boston, MA, Kluwer Academic Press, pp. 23–67, 1990.
Singh, M. P., Multiagent Systems, Berlin, LNAI 799, Springer-Verlag, 1994.
van der Hoek, W., B. van Linder, and J.-J. C. Meyer, ‘A logic of capabilities’, in A. Nerode and Y. V. Matiyasevich (eds.): Proceedings of the Third International Symposium on the Logical Foundations of Computer Science (LFCS'94), 1994.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Lespérance, Y., Levesque, H.J., Lin, F. et al. Ability and Knowing How in the Situation Calculus. Studia Logica 66, 165–186 (2000). https://doi.org/10.1023/A:1026761331498
Issue Date:
DOI: https://doi.org/10.1023/A:1026761331498