Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

PARALLELISM IN AI PROBLEM SOLVING: A CASE STUDY OF HEARSAY II

IP.com Disclosure Number: IPCOM000147914D
Original Publication Date: 1975-Oct-31
Included in the Prior Art Database: 2007-Mar-28
Document File: 50 page(s) / 3M

Publishing Venue

Software Patent Institute

Related People

Fennell, R.D.: AUTHOR [+3]

Abstract

PARALLELISM IN A1 PROBLEM SOLVING: A CASE STUDY OF HEARSAY I1 R. D. Fennell and V. 8. Lesser Department of Computer science1 Carnegie-Mcllon UniversityPittsburgh, Pennsylvania 15213 October, 1975 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 text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 4% of the total text.

Page 1 of 50

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

October, 1975

ABSTRACT

       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.

[This page contains 1 picture or other non-text object]

Page 2 of 50

[This page contains 1 picture or other non-text object]

Page 3 of 50

INTRODUCTION

       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...