×

The algebra \(\text{IA}^{\text{fuz}}\): a framework for qualitative fuzzy temporal reasoning. (English) Zbl 1131.68530

Summary: The aim of this work is to integrate the ideas of flexibility and uncertainty into Allen’s interval-based temporal framework, defining a new formalism, called \(\text{IA}^{\text{fuz}}\), which extends classical Interval Algebra (IA), in order to express qualitative fuzzy constraints between intervals. We generalize the classical operations between IA-relations to \(\text{IA}^{\text{fuz}}\)-relations, as well as the concepts of minimality and local consistency, referring to the framework of Fuzzy Constraint Satisfaction Problem. We analyze the most interesting reasoning tasks in our framework, which generalize the classical problems of checking consistency, finding a solution and computing the minimal network in the context of IA. In order to solve these tasks, we devise two constraint propagation algorithms and a branch and bound algorithm. Since these tasks are NP-difficult, we address the problem of finding tractable sub-algebras of \(\text{IA}^{\text{fuz}}\), by extending to our fuzzy framework the classical pointizable sub-algebras \(\text{SA}_c\) and SA, as well as the maximal tractable subalgebra \(\mathcal H\) introduced by Nebel. In particular, we prove that the fuzzy extension of the latter, called \(\mathcal{H}^{\text{fuz}}\), shares with its classical counterpart a maximality property, in that it is the unique maximal subalgebra of \(\text{IA}^{\text{fuz}}\) which contains the fuzzy extensions of Allen’s atomic relations.

MSC:

68T27 Logic in artificial intelligence
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T37 Reasoning under uncertainty in the context of artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allen, J. F., Maintaining knowledge about temporal intervals, Communication of the ACM, 26, 1, 832-843 (1983) · Zbl 0519.68079
[2] Vilain, M.; Kautz, H., Constraint propagation algorithms for temporal reasoning, (Kehler, T.; Rosenschein, S., Proceedings of the 5th National Conference on Artificial Intelligence (AAAI-86) (1986), American Association for Artificial Intelligence, Morgan Kaufmann: American Association for Artificial Intelligence, Morgan Kaufmann Los Altos, CA), 377-382
[3] Vilain, M.; Kautz, H.; van Beek, P., Constraint propagation algorithms for temporal reasoning: A revised report, (Weld, D. S.; de Kleer, J., Readings in Qualitative Reasoning about Physical Systems (1990), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 373-381
[4] Dechter, R.; Meiri, I.; Pearl, J., Temporal constraint networks, Artificial Intelligence, 49, 1-3, 61-95 (1991) · Zbl 0737.68070
[5] Dean, T. L.; McDermott, D. V., Temporal data base management, Artificial Intelligence, 32, 1, 1-55 (1987)
[6] Koubarakis, M., From local to global consistency in temporal constraint networks, Theoretical Computer Science, 173, 1, 89-112 (1997) · Zbl 0902.68016
[7] Meiri, I., Combining qualitative and quantitative constraints in temporal reasoning, Artificial Intelligence, 87, 1-2, 343-385 (1996) · Zbl 1506.68142
[8] Kautz, H. A.; Ladkin, P. B., Integrating metric and qualitative temporal reasoning, (Proceedings of the 9th National Conference on Artificial Intelligence (AAAI-91). Proceedings of the 9th National Conference on Artificial Intelligence (AAAI-91), Anaheim, CA (1991), AAAI Press/MIT Press), 241-246
[9] Dubois, D.; Fargier, H.; Prade, H., Possibility theory in constraint satisfaction problems: Handling priority, preference and uncertainty, Applied Intelligence, 6, 287-309 (1996) · Zbl 1028.91526
[10] Godo, L.; Vila, L., Possibilistic temporal reasoning based on fuzzy temporal constraints, (Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI-95). Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI-95), Montréal, Québec, Canada (1995), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 1916-1922
[11] Vila, L.; Godo, L., On fuzzy temporal constraint networks, Mathware and Soft Computing, 1, 3, 315-334 (1994) · Zbl 0833.68012
[12] L. Khatib, P. Morris, R. Morris, F. Rossi, Temporal constraint reasoning with preferences, in: B. Nebel (Ed.), Proceedings of the 17th International Conference on Artificial Intelligence (IJCAI-01), Seattle, WA, 2001, 322-327; L. Khatib, P. Morris, R. Morris, F. Rossi, Temporal constraint reasoning with preferences, in: B. Nebel (Ed.), Proceedings of the 17th International Conference on Artificial Intelligence (IJCAI-01), Seattle, WA, 2001, 322-327
[13] Knight, B.; Ma, J., Time representation: A taxonomy of temporal models, Artificial Intelligence Review, 7, 401-419 (1994) · Zbl 0806.68097
[14] L. Chittaro, C. Combi, Representation of temporal intervals and relations: Information visualization aspects and their evaluation, in: Proceedings of TIME 2001, Cividale del Friuli, Italy, 2001, pp. 13-20; L. Chittaro, C. Combi, Representation of temporal intervals and relations: Information visualization aspects and their evaluation, in: Proceedings of TIME 2001, Cividale del Friuli, Italy, 2001, pp. 13-20
[15] J.F. Allen, J. Koomen, Planning using a temporal world model, in: Proceedings of the Eighth International Joint Conference on Artificial Intelligence (IJCAI-83), Karlsruhe, FRG, 1983, pp. 741-747; J.F. Allen, J. Koomen, Planning using a temporal world model, in: Proceedings of the Eighth International Joint Conference on Artificial Intelligence (IJCAI-83), Karlsruhe, FRG, 1983, pp. 741-747
[16] van Beek, P.; Cohen, R., Exact and approximate reasoning about temporal relations, Computational Intelligence, 6, 132-144 (1990)
[17] Gerevini, A.; Schubert, L., On computing the minimal labels in time point algebra networks, Computational Intelligence, 11, 3, 443-448 (1995)
[18] Nebel, B.; Bürckert, H.-J., Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra, Journal of the ACM, 42, 1, 43-66 (1995) · Zbl 0886.68077
[19] M. Giacomin, From crisp to fuzzy constraint networks, in: Proceedings of CP ’01 Workshop “Modelling and Solving Problems with Soft Constraints”, Paphos, Cyprus, 2001; M. Giacomin, From crisp to fuzzy constraint networks, in: Proceedings of CP ’01 Workshop “Modelling and Solving Problems with Soft Constraints”, Paphos, Cyprus, 2001
[20] van Beek, P., Reasoning about qualitative temporal information, Artificial Intelligence, 58, 1-3, 297-326 (1992) · Zbl 0782.68106
[21] Ligozat, G. F., On generalized interval calculi, (Proceedings of the 9th National Conference on Artificial Intelligence (AAAI-91). Proceedings of the 9th National Conference on Artificial Intelligence (AAAI-91), Anaheim, CA (1991), AAAI Press/MIT Press), 234-240
[22] Ligozat, G. F., “Corner” relations in Allen’s algebra, Constraints, 3, 165-177 (1998) · Zbl 0911.68184
[23] Badaloni, S.; Giacomin, M., A fuzzy extension of Allen’s interval algebra, (AI*IA99: Advances in Artificial Intelligence, Selected Papers. AI*IA99: Advances in Artificial Intelligence, Selected Papers, Lecture Notes in Artificial Intelligence, vol. 1792 (2000), Springer-Verlag: Springer-Verlag Berlin), 155-165 · Zbl 0970.68603
[24] D. Dubois, H. Fargier, H. Prade, The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction, in: Proceedings of 2nd IEEE Conference on Fuzzy Systems, San Francisco, CA, 1993, pp. 1131-1136; D. Dubois, H. Fargier, H. Prade, The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction, in: Proceedings of 2nd IEEE Conference on Fuzzy Systems, San Francisco, CA, 1993, pp. 1131-1136
[25] Zadeh, L. A., Fuzzy sets, Information and Control, 8, 338-353 (1965) · Zbl 0139.24606
[26] Gerevini, A., Reasoning about time and actions in artificial intelligence: Major issues, (Stock, O., Spatial and Temporal Reasoning (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 43-70
[27] Schwalb, E.; Vila, L., Temporal constraints: A survey, Constraints, 2, 129-149 (1998) · Zbl 0911.68186
[28] Montanari, U., Networks of constraints: fundamental properties and application to picture processing, Information Science, 7, 95-132 (1974) · Zbl 0284.68074
[29] H. Fargier, Problèmes de satisfaction de constraintes flexibles—application à l’ordonnancement de production, Ph.D. thesis, Université P. Sabatier, Toulouse, France (1994); H. Fargier, Problèmes de satisfaction de constraintes flexibles—application à l’ordonnancement de production, Ph.D. thesis, Université P. Sabatier, Toulouse, France (1994)
[30] Dubois, D.; Fargier, H.; Prade, H., Fuzzy constraints in job-shop scheduling, Journal of Intelligent Manufacturing, 6, 215-234 (1995)
[31] S. Dutta, An event-based fuzzy temporal logic, in: Proceedings of 18th IEEE International Symposium on Multiple-Valued Logic, Palma de Mallorca, Spain, 1988, pp. 64-71; S. Dutta, An event-based fuzzy temporal logic, in: Proceedings of 18th IEEE International Symposium on Multiple-Valued Logic, Palma de Mallorca, Spain, 1988, pp. 64-71
[32] H.W. Guesgen, J. Hertzberg, A. Philpott, Towards implementing fuzzy Allen relations, in: Proceedings of ECAI-94 Workshop on Spatial and Temporal Reasoning, Amsterdam, The Netherlands, 1994, pp. 49-55; H.W. Guesgen, J. Hertzberg, A. Philpott, Towards implementing fuzzy Allen relations, in: Proceedings of ECAI-94 Workshop on Spatial and Temporal Reasoning, Amsterdam, The Netherlands, 1994, pp. 49-55
[33] Zadeh, L. A., Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets and Systems, 1, 3-28 (1978) · Zbl 0377.04002
[34] Dubois, D.; Prade, H., Possibility Theory: An Approach to Computerized Processing of Uncertainty (1988), Plenum Press: Plenum Press New York
[35] Da Costa Pereira, C.; Garcia, F.; Lang, J.; Martin-Clouaire, R., Planning with graded nondeterministic actions: a possibilistic approach, International Journal of Intelligent Systems, 12, 935-962 (1997)
[36] S. Badaloni, M. Giacomin, Flexible temporal constraints, in: Proceedings of the 8th Information Processing and Management of Uncertainty in Knowledge-Based System Conference (IPMU 2000), Madrid, Spain, 2000, pp. 1262-1269; S. Badaloni, M. Giacomin, Flexible temporal constraints, in: Proceedings of the 8th Information Processing and Management of Uncertainty in Knowledge-Based System Conference (IPMU 2000), Madrid, Spain, 2000, pp. 1262-1269
[37] Dubois, D.; Fargier, H.; Fortemps, P., Fuzzy scheduling: Modeling flexible constraints vs. coping with incomplete knowledge, European Journal of Operational Research, 147, 231-252 (2003) · Zbl 1037.90028
[38] Vidal, T.; Fargier, H., Handling contingency in temporal constraint networks: From consistency to controllabilities, Journal of Experimental and Theoretical Artificial Intelligence, 11, 1, 23-45 (1999) · Zbl 1054.68664
[39] N. Yorke-Smith, K.B. Venable, F. Rossi, Temporal reasoning with preferences and uncertainty, in: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI-03), Acapulco, Mexico, 2003, pp. 1385-1386; N. Yorke-Smith, K.B. Venable, F. Rossi, Temporal reasoning with preferences and uncertainty, in: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI-03), Acapulco, Mexico, 2003, pp. 1385-1386
[40] 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
[41] S. Badaloni, M. Giacomin, Fuzzy extension of interval-based temporal sub-algebras, in: Proceedings of the 9th Information Processing and Management of Uncertainty in Knowledge-Based System Conference (IPMU 2002), Annecy, France, 2002, pp. 1119-1126; S. Badaloni, M. Giacomin, Fuzzy extension of interval-based temporal sub-algebras, in: Proceedings of the 9th Information Processing and Management of Uncertainty in Knowledge-Based System Conference (IPMU 2002), Annecy, France, 2002, pp. 1119-1126
[42] Ligozat, G. F., A new proof of tractability for ORD-Horn relations, (Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-96). Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-96), Portland, OR (1996), AAAI Press/MIT Press), 395-402
[43] P. Balbiani, J.-F. Condotta, G.F. Ligozat, Reasoning about generalized intervals: Horn representability and tractability, in: Proceedings of the 7th International Workshop on Temporal Representation and Reasoning (TIME-00), Nova Scotia, Canada, 2000, pp. 23-30; P. Balbiani, J.-F. Condotta, G.F. Ligozat, Reasoning about generalized intervals: Horn representability and tractability, in: Proceedings of the 7th International Workshop on Temporal Representation and Reasoning (TIME-00), Nova Scotia, Canada, 2000, pp. 23-30
[44] Bellman, R.; Zadeh, L. A., Decision-making in a fuzzy environment, Management Science, 17-B, 4, 141-164 (1970) · Zbl 0224.90032
[45] Marin, R.; Cardenas, M. A.; Balsa, M.; Sanchez, J. L., Obtaining solutions in fuzzy constraints networks, International Journal of Approximated Reasoning, 16, 3-4, 261-288 (1997) · Zbl 0939.68116
[46] Dubois, D.; Prade, H., Processing fuzzy temporal knowledge, IEEE Transactions of Systems, Man and Cybernetics, 19, 4, 729-744 (1989)
[47] Barro, S.; Marin, R.; Mira, J.; Paton, A. R., A model and a language for the fuzzy representation and handling of time, Fuzzy Sets and Systems, 61, 2, 153-175 (1994)
[48] Marin, R.; Barro, S.; Bosch, A.; Mira, J., Modeling time representation from a fuzzy perspective, Cybernetics and Systems, 25, 2, 207-215 (1994) · Zbl 0809.68111
[49] Rossi, F.; Sperduti, A.; Venable, K. B.; Khatib, L.; Morris, P. H.; Morris, R. A., Learning and solving soft temporal constraints: An experimental study, (Proceedings of 8th International Conference on Principles and Practice of Constraint Programming (CP 2002). Proceedings of 8th International Conference on Principles and Practice of Constraint Programming (CP 2002), Ithaca, NY (2002), Springer-Verlag: Springer-Verlag Berlin), 249-263
[50] Bistarelli, S.; Montanari, U.; Rossi, F., Semiring-based constraint satisfaction and optimization, Journal of the ACM, 44, 2, 201-236 (1997) · Zbl 0890.68032
[51] Rossi, F.; Sperduti, A.; Khatib, L.; Morris, P. H.; Morris, R. A., Learning preferences on temporal constraints: A preliminary report, (Proceedings of the 8th International Symposium on Temporal Representation and Reasoning (TIME-01). Proceedings of the 8th International Symposium on Temporal Representation and Reasoning (TIME-01), Cividale del Friuli, Italy (2001), IEEE Computer Society), 63-68
[52] S. Dutta, A temporal logic for uncertain events and an outline of a possible implementation in an extension of PROLOG, in: Proceedings of the 4th AAAI Workshop on Uncertainty in Artificial Intelligence, Minnesota, 1988, pp. 90-97; S. Dutta, A temporal logic for uncertain events and an outline of a possible implementation in an extension of PROLOG, in: Proceedings of the 4th AAAI Workshop on Uncertainty in Artificial Intelligence, Minnesota, 1988, pp. 90-97
[53] Freksa, C., Temporal reasoning based on semi-intervals, Artificial Intelligence, 54, 1-2, 199-227 (1996) · Zbl 1506.68138
[54] Badaloni, S.; Falda, M.; Giacomin, M., Integrating quantitative and qualitative fuzzy temporal constraints, AI Communications, 17, 4, 187-200 (2004) · Zbl 1098.68101
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.