Compilation of Non-Contemporaneous Constraints

AAAI 1996

TL;DR

This paper tackles the challenge of applying knowledge compilation techniques to real-time systems operating in dynamic environments. They introduce the problem of "non-contemporaneous constraints" that arise when compiled rules incorrectly mix conditions from different points in time. The authors propose and evaluate several solutions, demonstrating that knowledge compilation can indeed be effective for interactive systems.

What Problem Does This Paper Address?

Intelligent systems often use hierarchical knowledge to break down complex tasks into smaller, manageable subgoals. This allows them to react dynamically to changing environments. Knowledge compilation is a technique used to speed up these systems by transforming hierarchical knowledge into more efficient, flat, reactive rules. However, existing compilation methods, like Explanation-Based Learning (EBL), were primarily developed for static environments.

The core problem this paper addresses is that when a system operates in a dynamic environment, the conditions that trigger a subgoal might change while that subgoal is being processed. If knowledge compilation then tries to create a rule based on conditions from different points in time (e.g., a condition that was true when the subgoal started and another that is true when it finishes), it can lead to "non-contemporaneous constraints." These are essentially impossible conditions that make the compiled rules useless or even detrimental. This is a significant hurdle for applying compilation to interactive, real-time systems.

Methods

The authors explore several approaches to overcome non-contemporaneous constraints:

  • Include All Tested Features: Simply include every feature tested during reasoning, even if it's no longer present. This often leads to rules that never match.
  • Prune Rules with Non-contemporaneous Constraints: Detect and discard rules that contain these problematic constraints. This requires domain-specific knowledge to identify what constitutes a constraint.
  • Restrict Training Instances to Contemporaneous Features: Base compiled rules only on features present at a single point in time. This can lead to over-generalization if the rule's correctness depends on a feature's change over time.
  • Freeze Input During Execution: Prevent the training instance from changing during rule generation. This sacrifices reactivity.
  • Deactivate Goals Following Any Change: Force the system to restart reasoning whenever the environment changes. This can be computationally expensive.
  • Deactivate Dependent Goal Structure Following Any Change: A more refined version of the above, where only goals and features dependent on the change are deactivated.
  • Eliminate Persistence of Goals and Features: Make goals and features active only as long as the rules that generate them match. This effectively removes memory.
  • Extend Training Instances to Include Temporal Dependencies: Augment the domain theory to explicitly represent and test temporal relationships between features.

The paper focuses on implementing and evaluating the "deactivation approaches" (A-5 and TK-5) and compares them to a baseline. They use the Soar architecture, which supports hierarchical knowledge, learning, and interaction with external environments.

Datasets

The paper introduces a dynamic blocks world as a testbed for evaluating their approaches. This environment simulates actions, has dynamic gravity, and allows for scheduled exogenous events, making it more realistic than static planning benchmarks. They specifically use a simple tower-building task within this environment for their quantitative results.

Key Insights and Ideas

  • Non-contemporaneous constraints are a real problem: The paper clearly demonstrates how standard EBL can fail in dynamic environments by creating impossible rule conditions.
  • Deactivation approaches offer a viable solution: The "deactivation" strategies (A-5 and TK-5) successfully learned rules without non-contemporaneous constraints in their test tasks.
  • Architectural vs. Knowledge-Based Implementation: Implementing deactivation as part of the architecture (A-5) generally leads to better performance and less knowledge engineering overhead compared to implementing it via domain-specific rules (TK-5).
  • Trade-offs exist: While deactivation approaches can initially require more execution steps, they significantly improve performance after learning. There's a trade-off between initial cost and long-term learning benefits.
  • Knowledge compilation is applicable to interactive systems: The success of their proposed solutions suggests that knowledge compilation is not limited to static domains and can be beneficial for real-time, interactive agents.

Key Results

  • The deactivation approaches (A-5 and TK-5) successfully learned rules without non-contemporaneous constraints on the tower-building task.
  • After learning, the deactivation approaches achieved an average speedup factor of more than three compared to the baseline.
  • The architectural approach (A-5) consistently outperformed the knowledge-based approach (TK-5) in terms of execution steps and CPU time, especially after learning.
  • While deactivation approaches initially required more execution steps, their performance improved significantly with learning.
  • A-5 required minimal additions to the domain theory and no domain-independent rules, making it more tractable than TK-5.

Limitations and Future Work

  • Limited Task Scope: The quantitative results are based on a single, simple tower-building task. While designed to highlight the problem, it may not fully represent the complexity of all dynamic domains.
  • Computational Overhead: The deactivation approaches, particularly A-6, can lead to increased cycle times due to the overhead of managing knowledge dependencies.
  • Future Work: The authors plan to explore a compromise approach that tracks goal dependencies on changing input but avoids the extensive effort of tracking persistent feature dependencies. They also suggest further investigation into how the additional knowledge requirements of TK-5 scale with increasingly complex domain theories. The evaluation of A-6 in a flight simulation domain is also mentioned as ongoing work.

Summary updated

BibTeX
@inproceedings{1996compilation,
  title = {{Compilation of Non-Contemporaneous Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}

Loading related content...

Figure