Abstract
The effective reasoning capability of an agent can be defined as its capability to infer, within a given space and time bound, facts that are logical consequences of its knowledge base. In this paper we show how to determine the effective reasoning capability of an agent with limited memory by encoding the agent as a transition system and automatically verifying whether a state where the agent believes a certain conclusion is reachable from the start state. We present experimental results using the Model Based Planner (mbp) which illustrates how the length of the deduction varies for different memory sizes.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ågotnes, T., Walicki, M.: Complete axiomatizations of finite syntactic epistemic states. In: Baldoni, M., Endriss, U., Omicini, A., Torroni, P. (eds.) DALT 2005. LNCS (LNAI), vol. 3904, pp. 33–50. Springer, Heidelberg (2006)
Alechina, N., Logan, B., Whitsey, M.: A complete and decidable logic for resource-bounded agents. In: Proceedings of the Third International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2004), pp. 606–613. ACM Press, New York (July 2004)
Benerecetti, M., Giunchiglia, F., Serafini, L.: Model Checking Multiagent Systems. Journal of Logic and Computation, Special Issue on Computational & Logical Aspects of Multi-Agent Systems 8(3), 401–423 (1998)
Berger, M., Bauer, B., Watzke, M.: A scalable agent infrastructure. In: Proceedings of the Second Workshop on Infrastructure for Agents, MAS and Scalable MAS (held in conjuction with Autonomous Agents’01), Montreal (2001)
Bibel, W.: A deductive solution for plan generation. New Generation Computing 4, 115–132 (1986)
Cimatti, A., Pistore, M., Roveri, M., Traverso, P.: Weak, Strong, and Strong Cyclic Planning via Symbolic Model Checking. Artificial Intelligence 147(1,2), 35–84 (2003)
Duc, H.N.: Reasoning about rational, but not logically omniscient, agents. Journal of Logic and Computation 7(5), 633–648 (1997)
Elgot-Drapkin, J., Miller, M., Perlis, D.: Memory, reason and time: the Step-Logic approach. In: Philosophy and AI: Essays at the Interface, pp. 79–103. MIT Press, Cambridge, Massachusetts (1991)
Elgot-Drapkin, J.J., Perlis, D.: Reasoning situated in time I: Basic concepts. Journal of Experimental and Theoretical Artificial Intelligence 2, 75–98 (1990)
Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M.Y.: Reasoning about Knowledge. MIT Press, Cambridge, Massachusetts (1995)
Fikes, R.E., Nilsson, N.J.: STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence 2, 187–208 (1971)
Fisher, M., Ghidini, C.: Programming Resource-Bounded Deliberative Agents. In: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI 1999), pp. 200–206. Morgan Kaufmann, San Francisco (1999)
Horrocks, I., Patel-Schneider, P.F.: A proposal for an OWL rules language. In: Proceedings of the 13th international conference on World Wide Web, WWW 2004, pp. 723–731. ACM, New York (2004)
Jacopin, E.: Classical AI planning as theorem proving: The case of a fragment of linear logic. In: AAAI Fall Symposium on Automated Deduction in Nonstandard Logics, pp. 62–66. AAAI Press, Palo Alto, California (1993)
Kacprzak, M., Lomuscio, A., Penczek, W.: Verification of multiagent systems via unbounded model checking. In: Kudenko, D., Kazakov, D., Alonso, E. (eds.) Adaptive Agents and Multi-Agent Systems II(AAMAS). LNCS (LNAI), vol. 3394, Springer, Heidelberg (2005)
Kautz, H., Selman, B.: Pushing the envelope: Planning, propositional logic, and stochastic search. In: Proceedings of the Thirteenth National Conference on Artificial Intelligence, pp. 1194–1201. AAAI Press, Stanford, California, USA (1996)
Russell, S.J.: Rationality and intelligence. Artificial Intelligence 94(1-2), 57–77 (1997)
Tarkoma, S., Laukkanen, M.: Supporting software agents on small devices. In: Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2002), pp. 565–566. ACM Press, New York, NY, USA (2002)
van Benthem, J., Liu, F.: Diversity of agents in games. Philosophia Scientiae, vol. 8(2) (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alechina, N., Bertoli, P., Ghidini, C., Jago, M., Logan, B., Serafini, L. (2007). Verifying Space and Time Requirements for Resource-Bounded Agents. In: Edelkamp, S., Lomuscio, A. (eds) Model Checking and Artificial Intelligence. MoChArt 2006. Lecture Notes in Computer Science(), vol 4428. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74128-2_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-74128-2_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74127-5
Online ISBN: 978-3-540-74128-2
eBook Packages: Computer ScienceComputer Science (R0)