×

Probabilistic temporal networks: A unified framework for reasoning with time and uncertainty. (English) Zbl 0931.68125

Summary: Complex real-world systems consist of collections of interacting processes/events. These processes change over time in response to both internal and external stimuli as well as to the passage of time itself. Many domains such as real-time systems diagnosis, story understanding, and financial forecasting require the capability to model complex systems under a unified framework to deal with both time and uncertainty. Current models for uncertainty and current models for time already provide rich languages to capture uncertainty and temporal information, respectively. Unfortunately, these semantics have made it extremely difficult to unify time and uncertainty in a way which cleanly and adequately models the problem domains at hand. Existing approaches suffer from significant trade offs between strong semantics for uncertainty and strong semantics for time. In this paper, we explore a new model, the Probabilistic Temporal Network (PTN), for representing temporal and atemporal information while fully embracing probabilistic semantics. The model allows representation of time constrained causality, of when and if events occur, and of the periodic and recurrent nature of processes.

MSC:

68T37 Reasoning under uncertainty in the context of artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Constantin, F.; Gregory, A. F.; Cooper, A., Structurally and temporally extendend Bayesian belief network model: definitions, properties, and modeling techniques, (Proceedings of the Twelfth Annual Conference on Uncertainty in Artificial Intelligence (UAI-96) (1996)), 28-39
[2] Allen, J. F., Maintaining knowledge about temporal intervals, Commun. ACM, 26, 11, 832-843 (1983) · Zbl 0519.68079
[3] Allen, J. F., Towards a general theory of action and time, Artificial Intelligence, 23, 2, 123-154 (1984) · Zbl 0567.68025
[4] Allen, J. F.; Koomen, J. A., Planning using a temporal world model, (Proceedings of the Eight International Joing Conference on Artificial Intelligence (August 1983)), 741-747
[5] Buchanan, B. G.; Shortliffe, E. H., Rule-Based Expert Systems (1984), Addison-Wesley: Addison-Wesley New York
[6] Charniak, E., Bayesian networks without tears, AI Magazine, 12, 4, 50-63 (1991)
[7] Charniak, E.; Shimony, S. E., Probabilistic semantics for cost based abduction, (Proceedings of the AAAI Conference (1990)), 106-111 · Zbl 0742.68076
[8] Cooper, G. F., Probabilistic inference using belief networks is NP-hard, (Technical Report KSL-87-27 (1987), Medical Computer Science Group, Stanford University: Medical Computer Science Group, Stanford University Reading, MA)
[9] Dean, T.; Wellman, M., Planning and Control (1991), Morgan Kaufmann
[10] Dechter, R.; Meiri, I.; Pearl, J., Temporal constraint networks, Artificial Intelligence, 49, 61-95 (1991) · Zbl 0737.68070
[11] Druzdel, M. J., There is more than one way to skin a cat: Commentary on john lemmer’s the causal markov condition: Fact or artifact?, ACM SIGART Bulletin, 7, 4, 1-2 (1996)
[12] Freska, C., Temporal reasoning based on semi-intervals, Artificial Intelligence, 54, 199-227 (1992)
[13] Gonzalez, A. J.; Dankel, D. D., The Engineering of Knowledge-Based Systems: Theory and Practice (1993), Prentice-Hall: Prentice-Hall Los Altos, CA
[14] Hanks, S.; Madigan, D.; Gavrin, J., Probabilistic temporal reasoning with endogenous change, (Proceedings of the Eleventh Annual Conference on Uncertainty in Artificial Intelligence (UAI-95) (August 1995))
[15] Hobbs, J. R.; Stickel, M.; Martin, P.; Edwards, D., Interpretation as abduction, (Proceedings of the 26th Annual Meeting of the Association for Computational Linguistics (1998)), 95-103
[16] Josephson, J. R.; Josephson, S. G., Abductive Inference: Computation, Philosophy, Technolog (1994), Cambridge University Press: Cambridge University Press Englewood Cliffs, NJ · Zbl 0813.68021
[17] Kanazawa, K., Reasoning about Time and Probability, (Thesis (May 1992), Brown University: Brown University Cambridge, NY)
[18] Kirman, J.; Nicholson, A.; Lejter, M.; Santos, E.; Dean, T., Using goals to find plans with high expected utility, (Proceedings of the Second European Workshop on Planning (1993))
[19] U. Kjaerulff, dhugin: A computational system for dynamic time-sliced bayesian networks, International Journal of Forecasting, Special Issue on Probability Forecasting, to appear.; U. Kjaerulff, dhugin: A computational system for dynamic time-sliced bayesian networks, International Journal of Forecasting, Special Issue on Probability Forecasting, to appear.
[20] Ladkin, P. B.; Maddux, R. D., On binary constraint problems, Journal of the ACM, 41, 3, 435-469 (1994) · Zbl 0813.03045
[21] Lemmer, J. F., The causal markov condition, fact or artifact?, ACM SIGART Bulletin, 7, 3, 3-16 (1996)
[22] Ligozat, G., Weak representations of interval algebras, (Proceedings of the AAAI Conference (1990)), 715-720
[23] Losiewicz, P. B., Complexity, ontology, and the causal markov assumption, ACM SIGART Bulletin, 7, 4, 13-18 (1996)
[24] Manna, Z.; Pnueli, A., The Temporal Logic of Reactive and Concurrent Systems: Specification (1992), Springer
[25] McDermott, D. V., A temporal logic for reasoning about processes and plans, Cognitive Science, 6, 101-155 (1982)
[26] (Nemhauser, G. L.; Rinnooy Kan, A. H.G.; Todd, M. J., Optimization: Handbooks in Operations Research and Management Science, vol. 1 (1989), North-Holland: North-Holland New York)
[27] Pearl, J., Probabilistic reasoning in intelligent systems: Networks of plausible inference (1988), Morgan Kaufmann: Morgan Kaufmann Amsterdam
[28] Peng, Y.; Reggia, J. A., Abductive Inference Models for Diagnostic Problem-Solving (1990), Springer: Springer San Mateo, CA · Zbl 0723.68096
[29] Santos, E., On the generation of alternative explanations with implications for belief revision, (Proceedings of the Conference on Uncertainty in Artificial Intelligence (1991)), 337-347
[30] Santos, E., On modeling time and uncertainty for diagnosis through linear constraint satisfaction, (Proceedings of International Congress on Computer Systems and Applied Mathematics Workshop on Constraint Processing (1993)), 93-106
[31] Santos, E., Unifying time and uncertainty for diagnosis, Journal of Experimental and Theoretical Artificial Intelligence, 8, 75-94 (1996)
[32] Shafer, G. A., Mathematical Theory of Evidence (1979), Princeton University Press: Princeton University Press Berlin, New York
[33] Shoham, Y., Reasoning About Change: Time and Causation from the Standpoint of Artificial Intelligence (1988), MIT Press: MIT Press Princeton, NJ
[34] Shortliffe, E. H., Computer-Based Medical Consultation: MYCIN (1976), Elsevier: Elsevier Cambridge, MA
[35] Shortliffe, E. H.; Buchanan, B. G., A model of inexact reasoning in medicine, Mathematical Biosciences, 23, 351-379 (1975)
[36] Suppes, P., A Probabilistic Theory of Causality, (Acta philosophica Fennica. Fasc., 24 (1970), North-Holland: North-Holland Amsterdam) · Zbl 0202.29603
[37] van Beek, P.; Manchak, D. W., The design and experimental analysis of algorithms for temporal reasoning, Journal of Artificial Intelligence Research, 4, 1-18 (1996) · Zbl 0900.68389
[38] Vilain, M.; Kautz, H., Constraint propagation algorithms for temporal reasoning, (Proceedings of the AAAI Conference (1986)), 377-382
[39] Joel, D.; Santos, Y. E., Introduction to temporal bayesian networks, (Gasser, M., Online Proceedings of the 1996 Midwest Artificial Intelligence and Cognitive Science Conference (April 1996))
[40] Zadeh, L. A., The role of fuzzy logic in the management of uncertainty in expert systems, Fuzzy Sets and Systems, 11, 199-227 (1983) · Zbl 0553.68049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.