zbMATH — the first resource for mathematics

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.

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
Full Text: DOI
[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, (), 377-382
[3] Vilain, M.; Kautz, H.; van Beek, P., Constraint propagation algorithms for temporal reasoning: A revised report, (), 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)
[8] Kautz, H.A.; Ladkin, P.B., Integrating metric and qualitative temporal reasoning, (), 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, (), 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
[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
[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
[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
[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, (), 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, (), 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
[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, (), 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)
[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
[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
[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 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
[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
[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
[42] Ligozat, G.F., A new proof of tractability for ORD-Horn relations, (), 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
[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, (), 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, (), 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
[53] Freksa, C., Temporal reasoning based on semi-intervals, Artificial intelligence, 54, 1-2, 199-227, (1996)
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.