Learning Efficient Rules by Maintaining the Explanation Structure

AAAI 1996

TL;DR

This paper tackles the challenge of "non-contemporaneous constraints" that arise when knowledge compilation techniques, like Explanation-Based Learning (EBL), are applied to dynamic, real-time systems. The authors propose and evaluate several approaches to avoid learning rules that are impossible to satisfy due to changing environmental conditions, demonstrating that knowledge compilation can indeed be effective in interactive environments.

What Problem Does This Paper Address?

Intelligent systems often use hierarchical knowledge representations to manage complex tasks in real-time. Techniques like knowledge compilation aim to speed up these systems by transforming this hierarchical knowledge into more efficient, flat, reactive rules. However, these compilation methods, particularly Explanation-Based Learning (EBL), were primarily developed for static environments.

The core problem this paper addresses is the difficulty of applying knowledge compilation to dynamic environments where the state of the world can change during the execution of a task and the learning process itself. This leads to "non-contemporaneous constraints" – conditions in a compiled rule that refer to features of the environment that were true at one point during reasoning but are no longer true by the time the rule would need to match. This can result in learned rules that are impossible to satisfy, hindering the system's learning and performance. For example, a system learning to fly a plane might learn a rule that requires the plane to be both turning and have achieved its target heading simultaneously, which is physically impossible.

Methods

The authors explore several approaches to address non-contemporaneous constraints, categorizing them as follows:

  • A-1: Include All Tested Features: This naive approach includes all features tested during reasoning, regardless of their current state. This often leads to rules with impossible constraints that never match.
  • A-2: Prune Rules with Non-contemporaneous Constraints: This involves identifying and discarding rules that contain such constraints. However, this requires domain-specific knowledge to correctly identify these constraints.
  • A-3: Restrict Training Instances to Contemporaneous Features: This method bases explanations only on features present at a single point in time. While it avoids non-contemporaneous constraints, it can lead to over-general rules.
  • A-4: Freeze Input During Execution: This approach prevents the training instance from changing during reasoning, guaranteeing contemporaneous rules but sacrificing reactivity.
  • A-5: Deactivate Goals Following Any Change: This is a more drastic approach where persistent goals are removed whenever the environment changes, forcing reasoning to restart. This ensures goals are always based on current features but can be computationally expensive.
  • A-6: Deactivate Dependent Goal Structure Following Any Change: A refinement of A-5, this approach selectively deactivates only those goals and features that depend on the changing input, aiming for a more efficient but still reactive solution.
  • A-7: Eliminate the Persistence of Goals and Features: This approach removes all persistence, meaning the system has no memory, thus eliminating non-contemporaneous constraints but also losing the ability to retain information.
  • A-8: Extend Training Instances (and Domain Theories) To Include Temporal Dependencies: This involves augmenting the domain theory to explicitly represent and test temporal relationships and dependencies between features.

The paper focuses on implementing and evaluating A-5 (deactivation of goals) and its knowledge-based counterpart, TK-5, as they were deemed most promising. They also implemented a version of A-6 for a flight simulation domain.

Datasets

The paper uses a dynamic blocks world as a testbed for evaluating their approaches. This environment is described as a "test bed" that facilitates controlled experimentation and captures important properties of interactive domains. It differs from traditional planning benchmarks by having:

  1. Internal vs. External Actions: Primitive commands (e.g., "open gripper") are distinct from their simulator implementation.
  2. Dynamic Environment: Actions take time, simulated gravity exists, and exogenous events can occur.

The specific task used for quantitative results is a simple tower-building task.

Key Insights and Ideas

  • Non-contemporaneous constraints are a fundamental challenge: The paper clearly articulates why standard EBL struggles in dynamic environments, highlighting the mismatch between static learning assumptions and dynamic execution realities.
  • Deactivation approaches offer a viable solution: Approaches like A-5 and A-6, which involve deactivating or selectively removing goals when the environment changes, effectively prevent the learning of non-contemporaneous constraints.
  • Architectural vs. Knowledge-Based implementations: The paper distinguishes between implementing these solutions directly within the architecture (like A-5 in Soar) versus encoding them as domain-specific knowledge (like TK-5). Architectural solutions generally require less explicit knowledge engineering.
  • Trade-offs exist: While deactivation approaches successfully learn correct rules, they can initially require more execution steps before learning occurs. However, performance improves significantly after learning.
  • Domain theory refinement is often necessary: The deactivation approaches can reveal incompleteness in the original domain theory, requiring additions to handle situations where goals need to be managed dynamically.

Key Results

  • Successful learning: The implemented deactivation approaches (A-5 and TK-5) successfully learned rules without non-contemporaneous constraints for the tower-building task.
  • Performance improvement with learning: Both A-5 and TK-5 showed significant speedup (over three times) compared to the baseline after learning.
  • Architectural advantage: The architectural approach (A-5) was consistently better than the knowledge-based approach (TK-5) in terms of execution steps and CPU time, especially after learning.
  • Initial overhead: Deactivation approaches initially required about twice the number of execution steps as the baseline before learning.
  • CPU time reduction: While execution steps increased initially, the increase in CPU time was proportionally less, suggesting a reduction in average cycle time after learning.
  • A-6 implementation challenges: The A-6 approach, while conceptually appealing, proved difficult to implement and led to dramatically increased cycle times due to the overhead of managing knowledge dependencies.

Limitations and Future Work

  • Limited task scope: The current evaluation is primarily based on a simple tower-building task. While designed to capture key properties, more complex domains need to be tested.
  • Computational cost of A-6: The experience with A-6 highlights the potential computational expense of sophisticated dependency tracking.
  • 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 aim to investigate how the additional knowledge requirements of TK-5 scale with increasingly complex domain theories. The paper suggests that the problem of non-contemporaneous constraints is not debilitating and that several approaches are appropriate for performance and speed-up learning in external environments.

Summary updated

BibTeX
@inproceedings{1996learning,
  title = {{Learning Efficient Rules by Maintaining the Explanation Structure}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}

Loading related content...

Figure