Knowledge-Based Anytime Computation

Abdel-Illah Mouaddib, Shlomo ZilbersteinIJCAI 1995

Abstract

Knowledge-based systems (KBS) offer powerful symbolic reasoning but often lack the temporal predictability required for real-time applications. This paper presents the GREAT (Guaranteed REAsoning Time) model, which organizes knowledge into a hierarchy of granularity. This structure enables "anytime" computation, where solution quality improves monotonically with available time, providing a reliable performance profile for time-critical decision-making.

Introduction

Knowledge-based systems (KBS) excel at handling complex, symbolic reasoning tasks. However, their inherent unpredictability poses a significant challenge for time-critical domains such as robotics, medical monitoring, and air traffic control. In a standard KBS, the time required to reach a conclusion can vary drastically based on input, making them unsuitable for environments with strict deadlines.

To address this, researchers have explored "anytime algorithms"—computational processes that can be interrupted at any moment to return the best answer found so far. While effective in numerical domains, applying anytime principles to symbolic KBS has been difficult due to the lack of a reliable performance profile: a mathematical description of how output quality improves over time. Without this profile, a system controller cannot effectively allocate time to tasks. This paper introduces the GREAT (Guaranteed REAsoning Time) model, which layers knowledge to ensure predictable, incremental reasoning.

The GREAT Model: Hierarchical Reasoning

The core innovation of the GREAT model lies in its structured approach to knowledge and inference. It consists of two primary components: hierarchical knowledge organization and progressive reasoning cycles.

Hierarchical Knowledge Organization

Instead of treating rules and data as a flat pool, the GREAT model assigns a "granularity" level to data attributes. Low granularity represents coarse information (e.g., a general "tendency" to move left), while high granularity represents precise detail (e.g., a specific speed of 5.4 m/s). Rules are automatically categorized into "packages" based on the granularity of the data they process.

Hierarchical organization of attributes and reasoning levels in the GREAT model.

Progressive Reasoning Cycles

The inference engine operates iteratively. Each cycle involves a reasoning phase using a specific package of rules and an evaluation phase. The evaluation checks the solution's completeness, certainty, and precision. If time permits and higher precision is needed, the system advances to the next level of the hierarchy. If a deadline is reached, the system returns the most refined solution completed to that point.

Experimental Evaluation: Collision Avoidance

The model was evaluated using a simulated Collision Avoidance System for a railway network. The scenario involved a grid of $n$ horizontal and $n$ vertical tracks, creating $n^2$ potential crossing points. The system's task was to detect potential collisions and adjust train speeds accordingly.

Key Results and Performance Profiles

The simulation demonstrated that the GREAT model successfully transforms a KBS into a "well-behaved" anytime algorithm. The primary metric for quality was the ratio of activated reasoning levels to total levels, providing a monotonic measure of precision.

Performance profile showing the monotonic increase in solution quality relative to the computation deadline.

As shown in the performance profile, solution quality improves incrementally as the deadline increases. Furthermore, the system exhibits "graceful degradation": as problem complexity (the number of trains) increases, the quality for a fixed deadline decreases predictably rather than failing catastrophically. This ensures that a "safe," albeit less precise, answer is always available almost immediately.

Conclusion and Future Directions

The GREAT model provides a robust framework for integrating symbolic reasoning into real-time systems by enforcing predictability through hierarchical limitation. By restricting reasoning cycles to specific data regions, the variance in execution time is minimized.

Future work aims to automate the currently manual process of mapping domain knowledge into hierarchical structures. Additionally, the authors are exploring more objective measures of symbolic precision and investigating the application of this model to multi-agent environments where coordinated anytime reasoning is essential.

Summary updated

BibTeX
@inproceedings{mouaddib1995knowledge,
  author = {Abdel-Illah Mouaddib and Shlomo Zilberstein},
  title = {{Knowledge-Based Anytime Computation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure