An introduction to temporal reasoning with granularities

Temporal constraint satisfaction problems have been widely studied but only recently have been deeply investigated problems where constraints can specify the minimum and maximum distance between two event occurrences in terms of different time granularities (e.g., days, weeks, business day, or academic semester). It was assumed that multi granularity problems could be easily converted in terms of a single granularity, which is not true, since the problem has now been proved to be inherently more difficult.

A formalism has been introduced for temporal constraints with granularities (TCG). For example, the constraint in the figure, indicates that the event associated to node 2 must occur two weeks later than the one associated to node 1, and in the same semester.

The GSTP system that we are demonstrating at ISD’03 is a web service which provides access to the implementation of a sound and complete algorithm for consistency of multi granularity networks. This service also provides a network solution and a view of refined explicit and implicit constraints in terms of any of the time granularities appearing in the network.

The conversion problem

In order to understand why a constraint in terms of a granularity cannot be simply substituted by a constraint in terms of a different granularity, consider how the constraint [1,1]day between Event1 and Event2 could be converted in terms of hours.

The tightest candidate constraint is [1,47]hours. Indeed, any value greater than 1 would exclude the solution of Event1 occurring in the last hour of one day and Event2 in the first hour of the next day; similarly, any value smaller than 47 would exclude the solution of Event1 occurring in the first hour of one day and Event2 in the last hour of the next day.

Thus, can we substitute [1,1]day with [1,47]hours?

NO. There are solutions for [1,47]hours which violate [1,1]day: if Event1 occurs at noon of one day and Event2 is 47 hours later, the second event is 2 days after the first one!

Conversion is used in the GSTP system only to derive implied constraints which do not substitute the original ones, but are very useful to refine the network as a pre-processing step for the consistency algorithm.

Specifying GSTP networks

A remote java-based interface enables the visual specification of a constraint network, its submission to the constraint solver, and the analysis of the output received from the solver.

A simplified real world example is presented during the demo: a distributed workflow process for the delivery of products resulting from online orders.

A temporal constraint network is designed by modeling some of the constraints involved in the process; this is an application example where the ability to work with multi granularity constraints can be particularly appreciated.

Constraint Network Processing

The GSTP interface offers a number of options to configure the request that will be sent to the GSTP web service, and then to the constraint solver. Once the network is submitted and the service has finished its job, the output will be available for analysis at the GSTP interface.

The constraint solver offers several services, the first one being a consistency check.

The second service is TCG refinement which proves to be particularly useful in the demo example.

The third service concerns implicit constraints. The visualization of the results in this case may be a problem.

The GSTP interface provides different tools: automatic positioning of nodes, visualization of arcs without constraints, views of selected arcs and constraints, views on specific granularities, and zooming functions.

Finally, the demo shows the GSTP service providing the minimum solution for the given network.