Solving multi-granularity temporal constraint networks

Many problems in scheduling, planning, and natural language understanding have been formulated in terms of temporal constraint satisfaction problems (TCSP). These problems have been extensively investigated in the AI literature providing effective solutions for some fragments of the general model. Independently, there has been an effort in the data and knowledge management research community for the formalization of the concept of time granularity and for its applications. This paper considers a framework for integrating the notion of time granularity into TCSP, and investigates the problems of consistency and network solution, which, in this context, involve complex manipulation of the periodic sets representing time granularities. A sound and complete algorithm for consistency checking and for deriving a solution is presented. The paper also investigates the algorithm's computational complexity and several optimization techniques specific to the multi-granularity context. An application to e-commerce workflows illustrates the benefits of the framework and the need for specific reasoning tools.