Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Logic for Characterizing Multiple Bounded Agents

  • Published:
Autonomous Agents and Multi-Agent Systems Aims and scope Submit manuscript

Abstract

We describe a meta-logic for characterizing the evolving internal reasoning of various families of agents. We view the reasoning of agents as ongoing processes rather than as fixed sets of conclusions. Our approach utilizes a strongly sorted calculus, distinguishing the application language, time, and various syntactic sorts. We have established soundness and completeness results corresponding to various families of agents. This allows for useful and intuitively natural characterizations of such agents' reasoning abilities. We discuss and contrast consistency issues as in the work of Montague and Thomason. We also show how to represent the concept of focus of attention in this framework.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. C. Alchourron, P. Gardenfors, and D. Makinson, On the logic of theory change,” J.Symbolic Logicvol. 50, pp. 510.530, 1985.

  2. R. Alur and T. A. Henzinger, Logics and models of real time: A survey,” in J. W. de Bakker, C. Huizing, W. P. de Roever, and G. Rozenberg, editors, Proceedings of Real-Time: Theory in Practicevol. 600 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, Germany, June 1992, pp. 74-106.

    Google Scholar 

  3. A. B. Baker and Y. Shoham, “Nonmonotonic temporal reasoning,” in D. Gabbay, C. Hogger, and J. Robinson, editors, Handbook of Logic in Artificial Intelligence and Logic Programming, Oxford University Press, 1995.

  4. H. Barringer, M. Fisher, D. Gabbay, and A. Hunter, “Meta-reasoning in executable temporal logic,” in J. Allen, R. Fikes, and E. Sandewall, editors, Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning, San Mateo, CA, April 1991, pp. 40-49, Morgan Kaufmann Publishers, 1991.

  5. J. van Benthem, The Logic of Time, Kluwer Academic Publishers: Boston, MA, 1991.

    Google Scholar 

  6. J. van Benthem, “Temporal logic,” in D. Gabbay, C. Hogger, and J. Robinson, editors, Handbook of Logic in Arti_cial Intelligence and Logic Programming, Oxford University Press, 1995, pp. 241-350.

  7. A. Brogi and F. Turini, “Metalogic for knowledge representation,” in J. Allen, R. Fikes, and E. Sandewall, editors, Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning, San Mateo, CA, April 1991, pp. 61-69, Morgan Kaufmann Publishers, 1991.

  8. S. Ceri, G. Gottlob, and L. Tanca, Logic Programming and Databases, Springer-Verlag: New York, 1990, Sec. 11.2.

    Google Scholar 

  9. L. Chittaro and A. Montanari, “Editorial: Temporal representation and reasoning,” Annals of Mathematics and Arti_cial Intelligencevol. 22, pp. 1-4, 1998.

    Google Scholar 

  10. P. Cohen and H. Levesque, “Intention is choice with commitment,” Arti_cial Intelligencevol. 42, pp. 263-310, 1990.

    Google Scholar 

  11. J. de Rivifieres and H. Levesque, “The consistency of syntactical treatments of knowledge (how to compile quanti_cational modal logics into classical FOL,” Computational Intelligencevol. 4, pp. 31-41, 1988.

    Google Scholar 

  12. J. Dix, V. S. Subrahmanian, and G. Pick, “Meta agent programs,” Technical Report CS-TR-3927, University of Maryland, College Park, September 1998.

  13. C. Dixon, M. Fisher, and M. Wooldridge, “Resolution for temporal logics of knowledge,” Journal of Logic and Computationvol. 8, no. 3, pp. 345-372, 1998.

    Google Scholar 

  14. J. Doyle, “Rationality and its roles in reasoning,” Computational Intelligencevol. 8, no. 2, pp. 376-409, 1992.

    Google Scholar 

  15. J. Elgot-Drapkin, M. Miller, and D. Perlis, “Memory, reason, and time: The step-logic approach,” in R. Cummins and J. Pollock, editors, Philosophy and AI: Essays at the Interface, MIT Press: Cambridge, MA, 1991.

    Google Scholar 

  16. J. Elgot-Drapkin and D. Perlis, “Reasoning situated in time I: Basic concepts,” Journal of Experimental and Theoretical Artificial Intelligencevol. 2, no. 1, pp. 75-98, 1990.

    Google Scholar 

  17. E. A. Emerson, “Temporal and modal logic,” in J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, Elsevier Science Publishers: Amsterdam, The Netherlands, 1990, pp. 995-1072.

    Google Scholar 

  18. J. Engelfriet and J. Treur, “Semantics for default logic based on specific branching time models,” in Proc.of ECAI96, 1996, pp. 60-64.

  19. R. Fagin and J. Halpern, “Belief, awareness, and limited reasoning,” Artificial Intelligencevol. 34, no. 1, pp. 39-76, 1988.

    Google Scholar 

  20. R. Fagin, J. Halpern, Y. Moses, and M. Vardi. Reasoning about Knowledge, MIT Press: Cambridge, MA, 1995.

    Google Scholar 

  21. F. Giunchiglia and L. Serafini, “Multilanguage hierarchical logics (or: how we can do without modal logics),” Arti_cial Intelligencevol. 65, pp. 29-70, 1994.

    Google Scholar 

  22. F. Giunchiglia and P. Traverso, “A metatheory of a mechanized object theory,” Arti_cial Intelligencevol. 80, no. 2, pp. 197-241, 1996.

    Google Scholar 

  23. P. G¨ardenfors, Knowledge in Flux: Modeling the Dynamics of Epistemic States, MIT Press: Cambridge, MA, 1988.

    Google Scholar 

  24. P. Gmytrasiewicz, E. H. Durfee, and D. Wehe, “A logic of knowledge and belief for recursive modeling: Preliminary report,” in Proc.of AAAI-92, California, 1992, pp. 628-634.

  25. J. Y. Halpern, “Using reasoning about knowledge to analyze distributed systems,” Annual Review of Computer Sciencevol. 2, 1987.

  26. J. Y. Halpern and Y. Moses, “A guide to completeness and complexity for model logics of knowledge and belief,” Artificial Intelligencevol. 54, no. 3, pp. 319-379, 1992.

    Google Scholar 

  27. J. Y. Halpern and M. Y. Vardi, “The complexity of reasoning about knowledge and time. 1: Lower bounds,” Journal of Computer and System Sciencesvol. 38 no. 1, pp. 195-237, 1989.

    Google Scholar 

  28. E. Horvitz and A. Klein, “Reasoning, metareasoning, and mathematical truth: Studies of theorem proving under limited resources,” in P. Besnard, and S. Hanks, editors, Proceedings of the 11th Conference on Uncertainty in Arti_cial Intelligence (UAI'95), San Francisco, CA, August 1995, pp. 306-314, Morgan Kaufmann Publishers, 1995.

  29. Z. Huang, M. Masuch, and L. Polos, “ALX, an action logic for agents with bounded rationality. Arti_cial Intelligencevol. 82, no. 1.2, pp. 75-127, 1996.

    Google Scholar 

  30. G. Hunter, Metalogic: An Introduction to Metatheory of Standard First Order Logic, University of California Press: Berkeley and Los Angeles, 1971.

    Google Scholar 

  31. K. Konolige, “A deductive model of belief,” in Proceedings of the 8th Int'l Joint Conference on Artificial Intelligence, Karlsruhe, West Germany, 1983, pp. 377-381.

  32. R. Kowalski, “Using metalogic to reconcile reactive with rational agents,” in K. Apt and F. Turini, editors, Meta-Logics and Logic Programming, MIT Press: Cambridge, MA, 1995.

    Google Scholar 

  33. S. Kraus and D. Lehmann, “Knowledge, belief and time,” Theoretical Computer Sciencevol. 58, pp. 155-174, 1988.

    Google Scholar 

  34. S. Kraus and V. S. Subrahmanian, “Multiagent reasoning with probability, time and beliefs,” International Journal of Intelligent Systemsvol. 10, pp. 459-499, 1995.

    Google Scholar 

  35. G. Lakemeyer, “Limited reasoning in first-order knowledge bases,” Artificial Intelligencevol. 69, pp. 213-255, 1994.

    Google Scholar 

  36. H. Lee, J. Tannock, and J. S. Williams, “Logic-based reasoning about actions and plans in artificial intelligence,” The Knowledge Engineering Reviewvol. 11, no. 2, pp. 91-105, 1993.

    Google Scholar 

  37. Y. Lespfierance and H. Levesque, “Indexical knowledge and robot action.A logical account,” Artificial Intelligencevol. 73, no. 1 and 2, pp. 69-115, 1995.

    Google Scholar 

  38. H. Levesque, “A logic of implicit and explicit belief,” in Proceedings of the 3rd National Conf.on Artificial Intelligence, Austin, TX, 1984, pp. 198-202

  39. P. Lincoln, “Linear logic,” ACM SIGACT Newsvol. 23, no. 2, pp. 29-37, 1992.

    Google Scholar 

  40. Z. Manna and A. Pnueli, Temporal Logic of Reactive and Concurrent Systems, Addison Wesley: Reading, MA, 1992.

    Google Scholar 

  41. J. McCarthy, “Circumscription, a form of non monotonic reasoning,” Artificial Intelligencevol. 13, pp. 27-39, 1980.

    Google Scholar 

  42. D. McDermott and J. Doyle, Non-monotonic logic. I, Arti_cial Intelligencevol. 13, no. 1 and 2, pp. 41-72, 1980.

    Google Scholar 

  43. M. Miller and D. Perlis, “Presentations and this and that: Logic in action,” in Proceedings of the 15th Annual Conference of the Cognitive Science Society, Boulder, CO, 1993.

    Google Scholar 

  44. R Montague, “Syntactical treatments of modality, with corollaries on reflection principles and finite axiomatizability,” in Modal and Many-Valued Logics (Acta Philosophica Fennica,vol. 16. Academic Bookstore: Helsinki, 1963. Reprinted in R. Montague Formal Philosophy, New Haven, 1974, pp. 286.302.

  45. M. Morreau and S. Kraus, “Syntactical treatments of propositional attitudes,” Artificial Intelligence Journalvol. 106, pp. 161-177, 1998.

    Google Scholar 

  46. M. Nirkhe, S. Kraus, M. Miller, and D. Perlis, “How to (plan to) meet a deadline between now and then,” Journal of Logic Computationvol. 7, no. 1, pp. 109-156, 1997.

    Google Scholar 

  47. A. Rao and M. P Georgeff, “Asymmetry thesis and side-effect problems in linear-time and branchingtime intention logics,” in Proc.of IJCAI-91, Australia, 1991, pp. 498-504.

  48. A. S. Rao and M. P. Georgeff, “Modeling rational agents within a BDI-architecture,” in J. Allen, R. Fikes, and E. Sandewall, editors, Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning (KR-91), Cambridge, MA, May 1991, pp. 473-484.

  49. R. Reiter, “A logic for default reasoning,” Arti_cial Intelligencevol. 13, no. 1 and 2, pp. 81-132, 1980.

    Google Scholar 

  50. A. Scedrov, “Linear logic and computation: A survey,” in H. Schwichtenberg, editor, Proof and Computation, Proceedings Marktoberdorf Summer School 1993, NATO Advanced Science Institutes, Series F, Springer-Verlag: Berlin, 1994.

    Google Scholar 

  51. Y. Shoham, “Agent-oriented programming,” Artificial Intelligencevol. 60, pp. 51-92, 1993.

    Google Scholar 

  52. M. Singh, “A semantics for speech acts,” Annals of Mathematics and Artificial Intelligencevol. 8, pp. 47-71, 1993.

    Google Scholar 

  53. B. Thomas, Y. Shoham, A. Schwartz, and S. Kraus, “Preliminary thoughts on an agent description language,” International Journal of Intelligent Systemsvol. 6, no. 5, pp. 497-508, August 1991.

    Google Scholar 

  54. R. Thomason, “A note on syntactical treatments of modality,” Synthesevol. 44, pp. 391-395, 1980.

    Google Scholar 

  55. W. van der Hoek, B. van Linder, and J.-J. Ch. Meyer, “An integrated modal approach to rational agents,” in M. Wooldridge and A. Rao, editors, Foundations of Rational Agency, Kluwer, Dordrecht, The Netherlands, 1999, pp. 37-75.

  56. L. Vila, “A survey on temporal reasoning in artificial intelligence,” AI Communicationsvol. 7, no. 1, pp. 4-28, March 1994.

    Google Scholar 

  57. M. J. Wooldridge and N. R. Jennings, “Agent theories, architectures and languages: A survey,” in Intelligent Agents, Lecture Notes in Artificial Intelligence No. 890, Springer-Verlag: New York, 1995, pp. 1-39.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer and Information Sciences and Department of Mathematics, Towson University, Towson, MD, 21252, USA

    John Grant

  2. Department of Mathematics and Computer Science, Bar-Ilan University, Ramat-Gan, 52900, Israel and

    Sarit Kraus

  3. Institute for Advanced Computer Studies, University of Maryland, College Park, MD, 20742

    Sarit Kraus

  4. Department of Computer Science, University of Maryland, College Park, MD, 20742, USA

    Donald Perlis

Authors
  1. John Grant
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sarit Kraus
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Donald Perlis
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Grant, J., Kraus, S. & Perlis, D. A Logic for Characterizing Multiple Bounded Agents. Autonomous Agents and Multi-Agent Systems 3, 351–387 (2000). https://doi.org/10.1023/A:1010050603219

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1010050603219

Search

Navigation