Time Map Manager
Introduction:

The TMM is a unique tool for representing and reasoning about temporal information. The TMM supports the representation of both ordering and metric constraints, reasoning about state changes, and dynamic database updates, all in a tool that has been engineered specifically to support large-scale temporal reasoning problems. This technology developed for TMM serves as the basis for almost all scheduling software at HTC. TMM has been rewritten and extensively modified to facilitate its use for scheduling.

Papers:

Temporal Reasoning for Planning and Scheduling in Complex Domains: Lessons Learned

Mark S. Boddy

Abstract: Over the past five years, we have implemented and applied efficient, general purpose temporal reasoning as a substrate for building planning and scheduling systems. We have also investigated the kinds of temporal reasoning that will be most useful, and for what problems. Our results confirm that temporal reasoning is a sufficiently self-contained activity to be implemented entirely independently of the overlying application, modulo some assumptions about how problem-solving is to proceed. We have also shown that constraint-based temporal reasoning supports a "least-commitment" style of planning and scheduling that is efficacious in a wide variety of complex problem domains. There have been some surprises, as well, for example in the fact that causal reasoning in general, and projection in particular, have been less useful than we anticipated. In this paper, we sketch the design, implementation, and semantics of our current temporal reasoning engine, loosely based up on Dean's Time Map Manager (TMM), discuss how that engine has been applied to a range of planning and scheduling problems, and draw some conclusions. The primary lesson to be drawn is that constraint-based temporal reasoning provides an effective basis for building planning and scheduling systems, particularly in applications where problem solving is only weakly directed by domain-specific solution methods.

Temporal Reasoning for Planning and Scheduling

Mark S. Boddy.

Abstract: We briefly describe the current implementation of the Time Map Manager (TMM), followed by a description of the system's suitability for and application to planning and scheduling tasks. Introduction As part of the DARPA/Rome Lab Planning Initiative, Honeywell's Systems and Research Center has developed a new implementation of Dean's Time Map Manager (TMM), involving improvements in robustness, efficiency, user interface, and documentation, in addition to a number of extensions in functionality . The TMM development contract is a 3 year, $1M effort, on which work commenced in August 1990. Honeywell's TMM software and User Manual were initially released in August 1992, with several incremental releases since. The TMM is a unique tool for representing and reasoning about temporal information. The TMM supports the representation of both ordering and metric constraints, reasoning about state changes, and dynamic database up dates, all in a to ol that has been engineered specifically to support large-scale temporal reasoning problems. Using the TMM, we are now developing tools that add a new dimension of flexibility and power to planning and scheduling applications. In this paper, we provide a brief overview of TMM capabilities, a description of the system's employment as a basis for building planning and scheduling tools, and a description of selected problems to which these tools have been applied.

Time Map Manager Final Report

Jim Carciofini

Abstract: This is the final report for Honeywell's contract to produce a production-quality version of the Time Map Manager (TMM). The TMM is a system for representing and reasoning about temporal information, designed specifically to simplify the construction of planners and schedulers by abstracting out and implementing a common functionality: making assertions or assumptions about facts and events over time, asserting an intent to perform some action(s) in a specified order or at a specified time, and inferring the consequences (what will be true when) for a given set of facts and events. TMM keeps track of the conclusions that should be drawn from the current information in the database (or allows users to draw their own conclusions) and then retracts those conclusions when they are no longer warran ted ("temporal reason maintenance"). It includes flexible and powerful mechanisms for handling inconsistencies and assumption failures. Honeywell's tasks under this contract were to improve TMM's efficiency, robustness, user interface, and documentation, to demonstrate the utility of the approach on problems relevant to transportation planning, and to support the use of the system within the ARPA/Rome Lab Planning Initiative. Over the course of the contract, we hav e provided several releases of the TMM software, along with extensive documentation of the system's architecture, operation, and design features (incorporated in the User's Manual, available as a Honeywell Tech Report), and implemented interfaces for fitting the system in to the Common Prototyping Environment (CPE). We have also demonstrated the use of the system for transportation planning in three separate demonstrations, described in more detail below. In addition to usage within the Planning Initiative, there has been considerable interest in obtaining the TMM from other research organizations. Here at Honeywell, we have used the TMM as a basis for developing a wide variety of planning and scheduling tools, for both internal and external applications. Several published papers related to the TMM and its application in planning and scheduling appear as appendices to this report. In the rest of this report, we present a detailed discussion of accomplishments under this contract, including participation in and support of the Planning Initiative (Section 3), completion of contract deliverables (Section 2), and demonstration of TMM capabilities and application (Section 4). We also discuss in moderate detail the current TMM implementation (Section 5), and describe related work carried out at Honeywell's Systems and Research Center (SRC) on applying TMM-based tools in other domains (Section 6). We conclude with a summary of the current state of affairs and some suggestions on the likely future course of research and development on temporal reasoning in particular.

Managing Disjunction for Practical Temporal Reasoning

Robert Schrag, Mark Boddy, and Jim Carciofini

Abstract: Ambiguous conclusions are inescapable in temporal reasoning. Lack of precise information about what events happen when results in uncertainty regarding the events' effects. Incomplete information and nonmonotonic inference result in situations where there is more than one set of possible conclusions, even when there is no temporal uncertainty at all. In an implemented system, this ambiguity is a computational problem as well as a semantic one. We discuss some of the sources of this ambiguity, which we treat as explicit disjunction, in the sense that ambiguous information can be interpreted as defining a set of possible inferences. Three ways of handling this disjunction are to represent it explicitly, to remove it by limiting the expressive pow er of the system, or to approximate a set of disjuncts using a weaker form of representation. We have employed primarily the latter two of these approaches to implement an expressive and efficient temporal reasoning engine that performs sound inference in accordance with a well-defined formal semantics.

Time Map Manager Introduction:

Time Map Manager
Introduction: