MANAGING TEMPORAL CONSTRAINTSWITH PREFERENCES: REPRESENTATION, REASONING, AND QUERYING

 

ABSTRACT

Representing and managing temporal knowledge, in the form of temporal constraints, is a crucial task in many areas, includingknowledge representation, planning, and scheduling. The current literature in the area is moving from the treatment of “crisp” temporal con-straints to fuzzy or probabilistic constraints, to account for preferences and\or uncertainty. Given a set of temporal constraints, the evaluationof the tightest implied constraints is a fundamental task, which is essential also to provide reliable query-answering facilities.  However, whilesuch tasks have been widely addressed for “crisp” temporal constraints, they have not attracted enough attention in the “non-crisp” contextyet. We overcome such a limitation, by (i) extending quantitative temporal constraints to cope with preferences, (ii) defining a temporal reasoningalgorithmwhichevaluatesthetightesttemporalconstraints,and(iii)providingsuitablequery-answeringfacilitiesbasedonit.

EXISTING SYSTEM:

In all the approaches to temporal constraints mentionedso far, temporal constraints are “crisp”, in the sense that theyrepresent a set of “equally possible” temporal relations\constraintsbetween two time units. All of these proposalsrely on the framework of Constraint SatisfactionProblem (CSP), in that they face the relevant reasoning tasksby representing the temporal objects as variables with temporaldomains, and the available temporal knowledge as aset of constraints between these variables. Unfortunately,these temporal constraint-based reasoning approaches inheritfrom CSP a number of fundamental limitations, mainly relatedto a lack of flexibility and a limited representation ofuncertainty. Specifically, many problems lead to a largeset of possible solutions, but often there may be preferencesa them, while standard CSP approaches would considereachofthemas“equallypossible”

 

PROPOSED SYSTEM:

In this work, we aim at providing a non-crisp extensionto quantitative constraints, supporting the possibility of expressingalternative distances between time points, and ofassociating a preference to each alternative, to grant flexibilityand expressiveness in the representation of quantitativetemporal constraints. Second, and more important, we aim atsupporting temporal reasoning and query answering facilitiesonKBsofsuchconstraints.Toachievesuchagoal,andtogrant for the absolute reliability of query answering, wepropose a temporal reasoning algorithm which we prove thatcomputes the tightest constraints (i.e., the all-to-all shortestpaths between time points).

CONCLUSIONS

The literature about temporal constraint is moving from thetreatment of “crisp” temporal constraint to fuzzy or probabilisticconstraints, to account for preferences and\or uncertainty. However, until now, no approach to “non-crisp”temporal constraints has focused on the evaluation of thetightest temporal constraints, and on query answering. In the wide literature in the area (see the introductory section),someotherapproachesarebasedonC-semirings.TheapproachbyKathib et al. is the closestto our one.  Khatib et al. consider quantitative temporal constraintsassociating preferences to distances. Indeed,Kathib et al. define their resume and extension (usinga different terminology) operations between preferences onlyin such a way that they form a C-semiring. On the otherhand, they adopt standard STP/TCSP composition andintersection operators to propagate distances. As a consequence,theiroveralloperationsfordeterminingthelabels(λfunction)of the graph’s edges (i.e., the whole operationswhich provide as output the labels, i.e., both their preferencesand distances) do not form a C-semiring. For instance,it is easy to show that in Katib et al.’s approach, inthe evaluation of edges’s labels, the distributivity of the extensionoperator with respect to the resume operator doesnot hold. Thus, Katib et al.’s constraint propagation approachis not ordering-independent (see point (2) at the endof Section 3.4), so that it does not always provide the tightestconstraintsbetweeneachpairoftimepoints.Our approach provides a main advance with respect to thestate of the art: it is the first approach to the propagation of“not-crisp” temporal constraints that aims at  (i) giving to users reliable query-answering facilities(ii) providing the evaluation of the tightest constraints be-tween temporal entities. To achieve (ii), we defined our resume and extension opera-tor in such a way that they form a C-semiring structure, sothat we can exploit the properties of Cormen et al.’s all-toallshortest path algorithm . Notably, if one neglects theinitialization phase (lines 1–5), the Compute-Summaries algorithmis a generalization of Floyd-Warshall’s algorithm(in which min and addition are generalized by the resumeand the extension operators respectively), which is widelyused to compute the minimal network (i.e., the tightest constraints)for STP temporal constraints. In this sense, we cansay that we extend classical approaches to “crisp” quantitative(STP)temporalconstraintstoconsideralsopreferences.Thisconsideration suggests a possible evolution. Recently,several algorithms have been devised in order to optimizeFloyd-Warshall’s algorithm in the evaluation of STP minimalnetworks(consider,forinstance,delt.In our future work, we aim at investigating whethersuch optimizations can be used also in our context, in whichalso preferences have to be taken into account. Moreover,the work in  presents several interesting advances withrespect to the state of the art, including the capability of copingwith four different types of preferences: numeric andsymbolic temporal preferences, composite preferences andconditional preferences. In our future work, we aim at investigatingwhether our approach could be extended to providesuch an additional expressiveness.

 

REFERENCES 

[1] L. Vila, “A Survey on Temporal Reasoning in Artificial Intelligence,”AICommun,vol.7,no.1,pp.4–28,1994.

[2] E. Schwalb and L. Vila, “Temporal Constraints: A Survey,” Constraints,vol.3,no.2–3,pp.129–149,Jun.1998.

[3] P. Terenziani, “Reasoning about Time,” in Encyclopedia of CognitiveScience,JohnWiley&Sons,Ltd,2006,pp.869–874.

[4] J. F. Allen, “Maintaining knowledge about temporal intervals,”Commun. ACM, vol. 26, no. 11, pp. 832–843, Nov. 1983.

[5] M. B. Vilain and H. A. Kautz, “Constraint Propagation Algorithmsfor Temporal Reasoning,” in Proceedings of the 5th National ConferenceonArtificialIntelligence.Philadelphia,PA,August11-15,1986.Volume1:Science,1986,pp.377–382.

[6] R. Dechter, I. Meiri, and J. Pearl, “Temporal Constraint Networks,”Artif Intell, vol. 49, no. 1–3, pp. 61–95, May 1991.

[7] M. Koubarakis, “From local to global consistency in temporal constraintnetworks,”Theor.Comput.Sci.,vol.173,no.1,pp.89–112,Feb.1997.

[8] I. Meiri, “Combining Qualitative and Quantitative Constraints inTemporal Reasoning,” Artif Intell, 87, no. 1–2, pp. 343–385, 1996.

[9] H. A. Kautz and P. B. Ladkin, “Integrating Metric and QualitativeTemporal Reasoning,” in Proceedings of the Ninth National ConferenceonArtificialIntelligence-Volume1,Anaheim,California,1991,pp.241–246.

[10] D. Dubois, H. Fargier, and H. Prade, “Possibility theory in constraintsatisfactionproblems:Handlingpriority,preferenceanduncertainty,”Appl.Intell.,vol.6,no.4,pp.287–309,Oct.1996.

[11] V. Ryabov and A. Trudel, “Probabilistic temporal interval networks,”inProc.11thInternationalSymposiumonTemporalRepresentationandReasoning,2004.TIME2004.,2004,pp.64–67.