Heterogeneous temporal probabilistic agents

Abstract

To date, there has been no work on temporal probabilistic agent reasoning on top of heterogeneous legacy databases and software modules. We will define the concept of a heterogeneous temporal probabilistic (HTP) agent. Such agents can be built on top of existing databases, data structures, and software code bases without explicitly accessing the internal code of those systems and can take actions compatible with a policy or operating principles specified by an agent developer. We will develop a formal semantics for such agents through the notion of a feasible temporal probabilistic status interpretation (FTPSI for short). Intuitively, an FTPSI specifies what all an HTP agent is permitted/forbidden/obliged to do at various times t. As changes occur in the environment, the HTP agent must compute a new FTPSI. HTP agents continuously compute FTPSIs in order to determine what they should do and, hence, the problem of computing FTPSIs is very important. We give a sound and complete algorithm to compute FTPSIs for a very large class of HTP agents called strict HTP agents. In a given state, many FTPSIs may exist. These represent alternative courses of action that the HTP agent can take. We provide a notion of an optimal FTPSI that selects an FTPSI optimizing an objective function and give a sound and complete algorithm to compute an optimal FTPSI.

References

1. Arsham, H. 2003. Time series analysis and forecasting techniques. Go online to http://obelia.jde.aca.mmu.ac.uk/resdesgn/arsham/opre330Forecast.htm.
2. Baral, C., Tran, N., and Tuan, L. 2002. Reasoning about actions in a probabilistic setting. In Proceedings of AAAI'02. AAAI Press, Menlo, Park, CA, 507--512.
3. Barringer, H., Fisher, M., Gabbay, D., Gough, G., and Owens, R. 1990. MetateM: A framework for programming in temporal logic. In REX Workshop, J. W. de Bakker, W. P. de Roever, and G. Rozenberg, Eds. Lecture Notes in Computer Science, vol. 430. Springer, Berlin, Germany.
4. Boole, G. 1854. The Laws of Thought. Macmillan, London, U.K.
5. Boutilier, C., Dean, T., and Hanks, S. 1999. Decision-theoretic planning: Structural assumptions and computational leverage. J. Artific. Intell. Res. 11, 1--94.
6. Boutilier, C., Dearden, R., and Goldszmidt, M. 1995. Exploiting structure in policy construction. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, C. Mellish, Ed. Morgan Kaufmann, San Francisco, CA, 1104--1111.
7. Boutilier, C., Reiter, R., Soutchanski, M., and Thrun, S. 2000. Decision-theoretic, high-level agent programming in the, situation calculus. In Proceedings of AAAI-00. 355--362.
8. Cattell, R. G. G., et al. 1997. The Object Database Standard: ODMG-93. Morgan Kaufmann, San Mateo, CA.
9. Chalupsky, H., Gil, Y., Knoblock, C., Lerman, K., Oh, J., Pynadath, D., Russ, T., and Tambe, M. 2001. Electric elves: Applying agent technology to support human organizations. In IAAI, H. Hirsh and S. Chien, Eds. AAAI Press, Menlo Park, CA.
10. Cormen, T. H., Leiserson, C. E., and Rivest, R. L. 1989. Introduction to Algorithms. MIT Press, Cambridge, MA, and McGraw-Hill, New York, NY.
11. Dean, T. and Kanazawa, K. 1988. Probabilistic Temporal Reasoning. In Proceedings AAAI. AAAI Press, Menlo Park, CA/MIT Press, Cambridge, MA, 524--529.
12. Dix, J., Kraus, S., and Subrahmanian, V. 2001. Temporal agent reasoning. Artific. Intell. 127, 1, 87--135.
13. Dix, J., Munoz-Avila, H., Nau, D., and Zhang, L. 2003. IMPACTing SHOP: Putting an AI planner into a multi-agent environment. Ann. Math. AI 4, 37, 381--407.
14. Dix, J., Nanni, M., and Subrahmanian, V. 2000. Probabilistic agent reasoning. ACM Trans. Computat. Logic 1, 2, 201--245.
15. Doherty, P., Gustafsson, J., Karlsson, L., and Kvarnstrom, J. 1998. (TAL) temporal action logics: Language specification and tutorial. Electron. Trans. Artific. Intell. 2, 3--4, 273--306.
16. Dubois, D., Land, J., and Prade, H. 1991. Towards possibilistic logic programming. In Proceedings of the Eigth International Conference on Logic Programming. MIT Press, Cambridge, MA, 581--595.
17. Dubois, D. and Prade, H. 1989. Processing fuzzy temporal knowledge. IEEE Trans. Syst. Man Cybernet. 19, 4, 729--744.
18. Dubois, D. and Prade, H. 1994. Possibilistic logic. In Handbook of Logic in Artificial Intelligence and Logic Programming Vol. 3, Nonmonotonic and Uncertain Reasoning, D. Gabbay, C. Hogger, and J. Robinson, Eds. Oxford University Press, Oxford, U.K., 439--513.
19. Eiter, T., Lukasiewicz, T., and Walter, M. 2001. A data model and algebra for probabilistic complex values. Ann. Math. Artific. Intell. 33, 2--4, 205--252.
20. Eiter, T., Subrahmanian, V., and Pick, G. 1999. Heterogeneous active agents, I: Semantics. Artific. Intell. 108, 1-2, 179--255.
21. Eiter, T., Subrahmanian, V., and Rogers, T. 2000. Heterogeneous active agents, III: Polynomially implementable agents. Artific. Intell. 117, 1, 107--167.
22. Fagin, R., Halpern, J., Moses, Y., and Vardi, M. 1995. Reasoning about Knowledge. MIT Press, Cambridge, MA.
23. Fagin, R., Halpern, J. Y., and Megiddo, N. 1990. A logic for reasoning about probabilities. Inform. Computat. 87, 1/2 (July/Aug.), 78--128.
24. Fisher, M. 1994. A survey of Concurrent MetateM---, the language and its applications. In Temporal Logic---Proceedings of the, First International Conference, D. M. Gabbay and H. J. Ohlbach, Eds. Lecture Notes in Computer Science, vol. 827. Springer, Berlin, Germany.
25. Friedman, N. and Halpern, J. Y. 1997. Modeling belief in dynamic systems, part I: Foundations. Artific. Intell. J. 95, 2, 257--316.
26. Friedman, N. and Halpern, J. Y. 1999. Modeling belief in dynamic systems, part II: Revision and update. J. Artific. Intell. Res. 10, 117--167.
27. Gmytrasiewicz, P. and Durfee, E. 1992. A logic of knowledge and belief for recursive modeling. In Proceedings of the 10th National Conference on Artificial Intelligence. AAAI Press, Menlo Park, CA/MIT Press, Cambridge, MA, 628--634.
28. Gmytrasiewicz, P., Durfee, E., and Wehe., D. 1991. A decision-theoretic approach to coordinating multiagent interactions. In Proceedings of the 12th International Joint Conference on Artificial Intelligence. Morgan Kaufmann, San Francisco, CA, 62--68.
29. Haddawy, P. 1991. Representing plans under uncertainty: A logic of time, chance and action. Ph.D. dissertation. Tech. rep. UIUCDCS-R-91-1719. University of Illinois--Urbana-Champaign, Urbana, IL.
30. Haddawy, P., Doan, A., and Goodwin, R. 1995. Efficient decision-theoretic planning: Techniques and empirical analysis. In UAI, P. Besnard and S. Hanks, Eds. Morgan Kaufmann, San Francisco, CA, 229--236.
31. Halpern, J. Y. and Tuttle, M. 1992. Knowledge, probability and adversaries. Tech. rep., IBM, Yorktown, Heights, NY.
32. Hanks, S. and McDermott, D. 1994. Modeling a dynamic and uncertain world I: Symbolic and probabilistic reasoning about change. Artific. Intell. 65, 2, 1--55.
33. Kanazawa, K. 1991. A logic and time nets for probabilistic inference. In Proceedings AAAI-91. AAAI Press, Menlo Park, CA/MIT Press, Cambridge, MA, 360--365.
34. Kifer, M. and Subrahmanian, V. 1992. Theory of generalized annotated logic programming and its applications. J. Logic Programm. 12, 4, 335--368.
35. Lakshmanan, V., Leone, N., Ross, R., and Subrahmanian, V. 1997. ProbView: A flexible probabilistic database system. ACM Trans. Datab. Syst. 22, 3 (Sept.), 419--469.
36. Lehmann, D. and Shelah, S. 1982. Reasoning with time and chance. Inform. Contr. 53, 165--198.
37. Lloyd, J. 1984, 1987. Foundations of Logic Programming. Springer-Verlag, Berlin, Germany.
38. Mittu, R. and Ross, R. 2003. Building upon the coalitions agent experiment (coax)---integration of multimedia information in gccs-m using impact. In Proceedings of the 9th International Workshop on Multimedia Information Systems (Ischia, Italy). 35--44.
39. Poole, D. 1997. The independent choice logic for modeling multiple agents under uncertainty. Artific. Intell. 94, 1--2, 7--56.
40. Puterman, M. 1994. Markov Decision Processes: Discrete Dynamic Programming. Wiley & Sons, Chicester, U.K., New York, NY/Brisbane, Australia.
41. Reiter, R. 1998. Sequential temporal golog. In Principles of Knowledge Representation and Reasoning: Proceedings of the Sixth International Conference (KR'98). Morgan Kaufman, San Francisco, CA, 547--556.
42. Sandewall, E. 1995. Features and Fluents: The Representation of Knowledge about Dynamical Systems. Oxford University Press, Oxford, U.K.
43. Scientific, T. 2003. Kalman Filter References. Go online to http://www.taygeta.com/kalrefs.html.
44. Shoham, Y. 1988. Reasoning about Change. MIT Press, Cambridge, MA.
45. Siegal, J. 1996. CORBA Fundementals and Programming. John Wiley & Sons, New York, NY.
46. Subrahmanian, V., Bonatti, P., Dix, J., Eiter, T., Kraus, S., Özcan, F., and Ross, R. 2000. Heterogenous Active Agents. MIT Press, Cambridge, MA.
47. T. Hammel, B. Y. and Rogers, T. 2003. Fusing live sensor data into situational multimedia views. In Proceedings of the 9th International Workshop on Multimedia Information Systems (Ischia, Italy). 145--156.
48. Tarski, A. 1955. A lattice-theoretical fixpoint theorem and its applications. Pacific J. Math. 5, 285--309.
49. Thomas, B., Shoham, Y., Schwartz, A., and Kraus, S. 1991. Preliminary thoughts on an agent description language. Internat. J. Intell. Syst. 6, 5 (Aug.), 497--508.
50. Wolfram, C. D. 1997. Strategic bidding in a multi-unit auction: An empirical analysis of bids to supply electricity in England and Wales. NBER Working Paper W6269.

Index Terms

• Computer systems organization

  • Architectures

    • Other architectures

      • Heterogeneous (hybrid) systems

• Computing methodologies

  • Artificial intelligence

    • Distributed artificial intelligence

      • Intelligent agents

• Information systems

  • Data management systems

    • Database design and models

    • Database management system engines

    • Information integration

      • Extraction, transformation and loading

• Software and its engineering

  • Software organization and properties

    • Extra-functional properties

      • Interoperability

• Theory of computation

  • Logic

    • Modal and temporal logics