| Temporal reasoning is important to many application areas. These include robotics, causal reasoning, visualization, molecular biology, natural language understanding, circuit design, databases, simulation, scheduling and planning. Reasoning over an expressive temporal constraint language is known to be an NP-Hard problem. This thesis develops a method for tractable temporal reasoning on large scale problems without giving up expressiveness of constraints. This method relies on database partitioning and the explicit control of inference and propagation. It does not rely on a meta-reasoner but rather on pre-compiled control strategies to determine the next cycle of computation. Importantly, the approach taken enables temporal reasoning in dynamic and incremental environments as well as resource constrained environments. The effectiveness of this approach is demonstrated with a series of empirical evaluations on large scale temporal reasoning problems. Performance profiles, dynamic query methods and quality analyses are presented to show the utility of this approach, particularly for resource bounded applications. The empirical results are presented to support the idea that even simple control strategies have useful and efficient performance profiles. These strategies provide flexible approaches to trading off computational efficiency and relative completeness at any particular time in the problem solving. The solutions provided are 'relatively complete' with respect to the computational resources available as the solution quality is relative to the amount of computational resources expended and constraint compiler used. The framework and strategies are intended to provide flexibility in application of temporal reasoning to a wide variety of circumstances. |
