**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 reasoningalgorithm*whichevaluatesthe*tightest*temporalconstraints,and(iii)providingsuitable*query-answeringfacilities*basedonit.

**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 ** preferences**a 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),someotherapproachesarebasedon*C-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 only**in 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,their

*overall*operationsfordeterminingthelabels(λfunction)of the graph’s edges (i.e., the

*whole*operationswhich provide as output the labels, i.e., both their

*preferences*

**and***distances*)

**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**

*do not**distributivity*of the

*extension*operator with respect to the

*resume*operator

**hold. Thus, Katib et al.’s constraint propagation approachis**

*doesnot**not ordering-independent*(see point (2) at the endof Section 3.4), so that it

**always provide the**

*does not**tightest*constraintsbetweeneachpairoftimepoints.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

*resume*and 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,”in*Proc.11thInternationalSymposiumonTemporalRepresentationandReasoning,2004.TIME2004.*,2004,pp.64–67.