Cashing in on Caching: An Architecture for Time-Bounded Knowledge-Based Problem Solving

Knowledge-based computing, in general, suffers from an inherent open-endedness that precludes its application in time-bounded domains where an answer must be computed within a stipulated time limit. We examine a two-way improvement of the shortcomings: a knowledge representation scheme that provides easy access to relevant knowledge and thereby reduces search time, and a reasoning scheme that is algorithmic in nature and thus makes computational requirements meaningfully estimable. In this work, we offer a cache-based architecture that is capable of both storing knowledge in different formats (e.g. rules, cases), and invoking an appropriate reasoning scheme to fit the available computing time. The cache helps in retrieving the most relevant pieces of knowledge (not only exact matches) required for solving a given problem. This cache relies on a reasoning tactic, knowledge interpolation, that can generate a solution from two near-matches in an algorithmic way, to generate time-bounded solutions. We illustrate the design of such a cache for solving resource allocation problems in the domain of shortwave radio transmission and evaluate its performance in observing imposed temporal bounds.