PARALLELISM IN AI PROBLEM SOLVING: A CASE STUDY OF HEARSAY II
Original Publication Date: 1975-Oct-31
Included in the Prior Art Database: 2007-Mar-28
Software Patent Institute
Fennell, R.D.: AUTHOR [+3]
AbstractPARALLELISM IN A1 PROBLEM SOLVING: A CASE STUDY OF HEARSAY I1 R. D. Fennell and V. 8. Lesser
PARALLELISM IN A1 PROBLEM SOLVING: A CASE STUDY OF HEARSAY I1
R. D. Fennell and V. 8. Lesser
Department of Computer science1 Carnegie-Mcllon University
Pittsburgh, Pennsylvania 15213
The Hearsay I1 speech-understanding system (HSII) (Lesser, et al., 197q Fennell, 1975; Erman and Lesser, 1975) is an implementation of a knowledge-based multiprocessing A1 problem-solving organization. HSII is intended to represent a problem-solving organization which is applicable for implementation in a multiprocessing environment, and is, in particular, currently being implemented on the C.mmp multiprocessor system (Bell, et al., 1971) at Carnegie-Mellon University. The object of this paper is to explore several of the ramifications of such a problem-solving organization by examining the mechanisms and policies underlying HSlI which are necessary for supporting its organization as a multiprocessing problem-solving system. First, an abstract description of a class of problem-solving systems is given using the Production Systerri model of Newell (1973). Then, the HSII problem-solving organization is described in terms of this model. The various decisions made during the course of design necessitated the introduction of various multiprocessing mechanisms (e.g., mechanisms for maintaining data localization and data integrity), and these mechanisms are discussed. Finally, a simulation study is presented which details the effects of actually implementing such a problem-solving organization for use in a particular application area, that of speech understanding.
This research was supported in part by the Defense Advanced Research Projects Agency of the Office of the Secretary of Defense (Contract F44620-73-C-0074) and monitored by the Air Force Office of Scientific Research.
Many A1 problem-solving tasks require large amounts of processing power in order to achieve solution in any given computer implementation of a problem-solving strategy. The an~ount of processing power required is directly related to the size of the search space which is examined during the course of problem solution. Exhaustive search of the state space associated with almost any problem of interest is precluded due to the sheer size of the state space.l In most problem-solving attempts, heuristics are employed which prune the search space ta a more manageable size. However, searching even the reduced state space often requires large amounts of processing power. The demand for sufficient computing power becomes critical in tasks requiring real-time solution, as is the case in the speech-understanding task with which this paper is primarily concerned.. For exaniple, a speech-understanding system c...