Abstract
In classical AI planning, managing multiple hypothetical scenarios and the logic of prevention remains a significant challenge. This paper presents the Time Map Manager (TMM), a temporal reasoning module designed to handle disjunctions and counterfactuals by labeling beliefs with boolean formulas. By integrating techniques from truth maintenance systems with temporal networks, the TMM allows planners to reason about simultaneous contexts and the continued necessity of prevention-based tasks.
Introduction
Traditional AI planning systems often struggle with the "least commitment" strategy when faced with multiple ways to achieve a goal. While delaying decisions can prevent premature commitment to a failing path, it often obscures interactions between alternative plans. Furthermore, reasoning about "prevention"—actions taken solely to avoid a predicted negative state—requires a sophisticated understanding of counterfactuals. If the threat being prevented disappears, the system must recognize that the warrant for the preventive action has also vanished.
Thomas Dean’s research introduces the Time Map Manager (TMM), a system integrated into the FORBIN planner, to address these issues. The TMM provides a framework for tracking which beliefs and plans remain valid across various hypothetical worlds without requiring exhaustive simulation of every possible state.
The Time Map Manager (TMM) Framework
The TMM operates by maintaining a network of "time tokens" representing facts or events. These tokens are defined by start and end points connected by temporal constraints (upper and lower bounds on duration).
Boolean Labeling and Simultaneous Contexts
Drawing inspiration from deKleer’s Assumption-based Truth Maintenance Systems (ATMS), the TMM assigns a boolean label to every assertion in the time map. This label represents the specific set of choices or assumptions under which the assertion is true.
Unlike previous systems that explored one context at a time, the TMM’s boolean labeling allows the planner to reason about many sets of choices simultaneously. This enables the system to identify "fortuitous consolidations" (where one choice accidentally helps another) or mutual exclusions without performing a brute-force search of the state space.
Nonmonotonic Data Dependencies
The system utilizes nonmonotonic logic to manage "protections." A protection ensures that a fact remains true over a specific interval. If a new event is introduced that "clips" or contradicts a protected fact, the TMM triggers a notification, allowing the planner to resolve the conflict by reordering tasks or choosing different resources.
The Logic of Prevention and Counterfactuals
A core contribution of this work is the formalization of the "warrant" for an action. In many scenarios, a robot performs a task not to achieve a direct goal, but to prevent a predicted failure. The TMM treats these predictions as counterfactual warrants: "If action X is not performed, then state Y (a failure) will occur."
By tagging cleanup or maintenance tasks with these warrants, the TMM can monitor the environment for changes. If the underlying threat is removed—either by external factors or a change in the plan—the TMM identifies that the preventive task is no longer necessary, allowing the planner to "procrastinate" or cancel the task entirely.
Illustrative Results
The effectiveness of the TMM is demonstrated through two primary qualitative examples:
- The Machine Shop: A robot must perform drilling and facing on a part using either a mill or a lathe. The TMM tracks the tool setups as protected facts. It demonstrates that if the robot selects the mill for both tasks, the system can automatically suggest an ordering (e.g., facing before drilling) to prevent one task from invalidating the setup required for the other.
- The OSHA Inspection: A maintenance robot predicts a safety fine due to a cluttered corridor. This prediction warrants a cleanup task. If the inspection is subsequently canceled or a human clears the corridor, the TMM recognizes the loss of the warrant and informs the planner that the cleanup is no longer required.
Discussion and Limitations
While the TMM offers a robust mechanism for discovering plan interactions, it faces challenges regarding computational complexity. The management of boolean labels can lead to exponential growth in the number of labels as the domain complexity increases, a common bottleneck in ATMS-like architectures. Additionally, the TMM is a modular component; its utility is ultimately bounded by the host planner's ability to generate and evaluate the alternatives that the TMM labels.
Conclusion
The Time Map Manager represents a significant step toward more flexible AI planning. By treating planning as a process of managing temporal constraints and boolean contexts, it allows systems to reason about what-if scenarios and counterfactual justifications with greater efficiency than traditional state-space search methods.
Summary updated