Cashing in on caching: An architecture for time-bounded knowledge-based problem solving

Knowledge-based computing, in general, suffers from an inherent open-endedn ess that precludes its application in time-bounded domains where an answer must be computed within a stipulated rime limit. We examine a two-way impro vement of the shortcomings: a knowledge representation scheme that provides easy access to relevant knowledge and thereby reduces search time, and a r easoning 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 s toring 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 reaso ning 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 prob lems in the domain of shortwave radio transmission and evaluate its perform ance in observing imposed temporal bounds.