Abstract
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.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
References
Allen, J. F. 1984. Towards a general theory of actions and time.Artificial Intelligence 23(2): 123–154.
Bradtke, S., and Lehnert, W. G. 1988. Some experiments with case-sased search.Proc. AAAI-88: 133–138.
Brandau, R., Lemmon, A., and Lafond, C. 1991. Experience with extended episodes: Cases with complex temporal structure.Proc. DARPA Case-Based Reasoning Workshop, CA: Morgan Kaufmann, pp. 1–12.
Braun, G. 1982.Planning and Engineering of Shortwave Links. Siemens Aktiengesellschaft: John Wiley and Sons.
Chatterjee, N., and Campbell, J. A. 1992. A caching scheme for time-critical and case-based reasoning.Proc. EXPERSYS-92, IITT-International, 94 Promenade A. Ballu, F-93460 Gournay-sur-Marne, France, pp. 477–482.
Chatterjee, N., and Campbell, J. A. 1993. A caching scheme for time-critical knowledge-based computations.Proc. Sixth International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems. Yverdon, Switzerland: Gordon and Breach Science Publishers S.A., pp. 61–70.
Chatterjee, N., and Campbell, J. A. 1994. Adaptation Through interpolation for time-critical case-based reasoning. InTopics in Case-based Reasoning, Wess, S., Althoff, K., and Richter, M. M., eds. Lecture Notes in Artificial Intelligence, Volume 837, Springer-Verlag, Berlin, pp. 221–233.
Chatterjee, N., and Campbell, J. A. 1996. Knowledge interpolation: A new approach to rapid symbolic reasoning.Proc. International Conference on Knowledge-Based Computer Systems: Research and Application. Anjaneyulu, K. S. R., Sasikumar, M., and Ramani, S., eds., Narosa Publishing House, pp. 67–78.
Chatterjee, N., and Campbell, J. A. 1996a. Knowledge interpolation: A simple approach to rapid symbolic reasoning. To be published in issue “6/98” ofComputers and Artificial Intelligence.
Chatterjee, N., and Campbell, J. A. 1997. A knowledge-based approach to fast frequency and source allocation in shortwave radio spectrum. Departmental Research Note: RN/97/21, submitted toEngineering Applications of Artificial Intelligence.
Dean, T., and Boddy, M. 1988. An analysis of time-dependent planning.Proc. AAAI-88: 49–54.
Dean, T. L., and Wellman, M. P. 1991.Planning and Control. CA: Morgan Kaufmann.
Dodhiawala, R., Sridharan, N. S., Raulefs, P., and Pickering, C. 1989. Real-time AI systems: A definition and an architecture.Proc. IJCAI-89: 256–261.
Forgy, C. L. 1982. RETE: A fast algorithm for the many pattern/many object pattern matching problem.Artificial Intelligence 19(1): 17–37.
Garvey, A., and Lesser, V. 1993. Design-to-time real-time scheduling.IEEE Transactions on Systems, Man and Cybernetics 23(6): 1491–1502.
Garvey, A., and Lesser, V. 1996. Design-to-time scheduling and anytime algorithms.SIGART Bulletin 7(2): 16–19.
Gupta, A. 1985. Parallelism in production systems: The source and the expected speed up.Fifth International Workshop on Expert Systems and their Applications, Agence de l'Informatique, Avignon, France.
Hammond, K. J. 1986. CHEF: A model of case-based planning.Proc. AAAI-86: 267–271.
Hammond, K. J. 1989. Opportunistic memory.Proc. IJCAI-89: 504–510.
Kolodner, J. 1993.Case-Based Reasoning. CA: Morgan Kaufmann.
Kopeikina, L., Brandau, R., and Lemmon, A. 1988. Case-based reasoning for continuous control.Proc. DARPA Case-Based Reasoning Workshop. CA: Morgan Kaufmann, pp. 233–249.
Korf, R. E. 1985. Depth-first iterative deepening: An optimal admissible tree search.Artificial Intelligence 27(1): 97–109.
Korf, R. E. Real-time heuristic search: New results.Proc. AAAI-88: 139–144.
Ladkin, P. 1987. The completeness of a natural system for reasoning with time intervals.Proc. IJCAI-87: 462–467.
Laffey, T. J., Cox, P. A., Schmidt, J. L., Kao, S. M., and Read J. Y. 1988. Real-time knowledge-based systems.AI Magazine 9(1): 27–45.
Masui, S., McDermott, J., and Sobel, A. 1983. Decision making in time-critical situations.Proc. IJCAI-83: 233–235.
McDermott, D. 1982. A temporal logic for reasoning about processes and plans.Cognitive Science 6(2): 101–155.
Puschner, P., and Koza, C. H. 1993. Calculating the maximum execution time of real-time programs. InAdvances in Real-Time Systems, Stankovic, J. A., and Ramamritham, K., eds., IEEE Computer Society Press, pp. 322–339.
Rich, E., and Knight, K. 1991.Artificial Intelligence. McGraw-Hill.
Schnelle, K. D., and Mah, R. S. H. 1992. A real-time expert system for quality control.IEEE Expert 7(5): 36–42.
Shoham, Y. 1989. Time for action: On the relation between time, knowledge and action.Proc. IJCAI-89: 954–959.
Tsang, E. P. K. 1987. Time-structure for AI.Proc. IJCAI-87: 456–461.
Vila, L. 1994. A survey on temporal reasoning in artificial intelligence.AI Communications 7(1): 4–28.
Waugh, A. E. 1952.Elements of Statistical Methods. McGraw-Hill.
Zadeh, L. A. 1992. Knowledge representation in fuzzy logic. InAn Introduction to Fuzzy Logic Applications in Intelligent Systems, Yager, R. R., and Zadeh, L. A., eds., Kluwer Academic Publishers.
Zilberstein, S., and Russell, S. 1996. Optimal composition of real-time systems.Artificial Intelligence 82: 181–213.
Author information
Authors and Affiliations
Department of Computer Science, University College London, Gower Street, London, U.K, WC1E 6BT
Niladri Chatterjee & J. A. Campbell
- Niladri Chatterjee
You can also search for this author inPubMed Google Scholar
- J. A. Campbell
You can also search for this author inPubMed Google Scholar
Rights and permissions
About this article
Cite this article
Chatterjee, N., Campbell, J.A. Cashing in on Caching: An Architecture for Time-Bounded Knowledge-Based Problem Solving.Real-Time Systems15, 221–247 (1998). https://doi.org/10.1023/A:1008092314093
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative