GUS is the first of a series of experimental computer systems that we intend to construct as part of a program of research on language understanding. In large measure, these systems will fill the role of periodic progress reports, summarizing what we have learned, assessing the mutual coherence of the various lines of investigation we have been following, and suggesting where more emphasis is needed in future work. GUS (Genial Understander System) is intended to engage a sympathetic and highly cooperative human in an English dialog, directed towards a specific goal within a very restricted domain of discourse. As a starting point, GUS was restricted to the role of a travel agent in a conversation with a client who wants to make a simple return trip to a single city in California. There is good reason for restricting the domain of discourse for a computer system which is to engage in an English dialog.

By placing various restrictions on the heuristic estimator it is possible to constrain the heuristic search process to fit specific needs. This paper introduces a new restriction upon the heuristic, called the “bandwidth” condition, that enables the ordered search to better cope with time and space difficulties. In particular, the effect of error within the heuristic is considered in detail. Beyond this, the bandwidth condition quite naturally allows for the extension of the heuristic search to MIN/MAX trees. The resulting game playing algorithm affords many desirable practical features not found in minimax based techniques, as well as maintaining the theoretical framework of ordered searches.

We present a rule-based system for computer-aided circuit analysis. The set of rules, called EL, is written in a rule language called ARS. Rules are implemented by ARS as pattern-directed invocation demons monitoring an associative data base. Deductions are performed in an antecedent manner, giving EL's analysis a catch-as-catch-can flavour suggestive of the behavior of expert circuit analyzers. We call this style of circuit analysis propagation of constraints.

An analysis of the efficiency of the alpha-beta algorithm is carried out based on a probabilistic model in which terminal node scores depend on random branch values. Explicit expressions are derived for the expected number of terminal nodes scored for the cases of uniform trees of fanout N and of depths 2 and 3. For trees of depth 2, the expected number is of order O(NHN); for trees of depth 3, the expected number is of order O(N2). An upper bound on the expected number of terminal nodes scored for trees of depth 4 is shown to be no greater than O(N2HN2) and no less than O(N2).

Chess programs can differ in depth of search or in the evaluation function applied to leaf nodes or both. Over the past 10 years, the notion that the principal way to strengthen a chess program is to improve its depth of search has held sway. Improving depth of search undoubtedly does improve a program's strength. However, projections of potential gain have time and again been found to overestimate the actual gain. We examine the notion that it is possible to project the playing strength of chess programs by having different versions of the same program (differing only in depth of search) play each other.

A relational production system (rps) is a general purpose, formal information processing model developed to support research in artificial intelligence and related areas where a conjunction of predicate calculus literals is a convenient state description language. Rps maintains a strong analogy with type O string grammars. It consists of a “situation”, which is a conjunction of literals, and an unordered set of “relational productions”, analogous to type O string productions. These productions cause the replacement of a subset of literals in the situation by other literals, just as type O string productions cause the replacement of substrings by other substrings. Predictably, this system resembles the more empirical, existing knowledge representation systems, particularly STRIPS, while maintaining a mathematical precision and simplicity which allows proof of useful results.

There are a number of transportation applications that require the use of a heuristic shortest path algorithm rather than one of the standard, optimal algorithms. This is primarily due to the requirements of some transportation applications where shortest paths need to be quickly identified either because an immediate response is required (e.g., in-vehicle route guidance systems) or because the shortest paths need to be recalculated repeatedly (e.g., vehicle routing and scheduling). For this reason a number of heuristic approaches have been advocated for decreasing the computation time of the shortest path algorithm. This paper presents a survey review of various heuristic shortest path algorithms that have been developed in the past. The goal is to identify the main features of different heuristic strategies, develop a unifying classification framework, and summarize relevant computational experience.

This paper analyzes the complexity of heuristic search algorithms, i.e. algorithms which find the shortest path in a graph by using an estimate to guide the search. In particular, algorithm A∗, due to Hart, Nilsson and Raphael, is shown to require O(2N) steps, in the worst case, for searching a graph with N nodes, if the so called “consistency assumption” does not hold for the estimate. Furthermore, a new search algorithm is presented which runs in O(N2) steps in the worst case and which never requires more steps than A∗.

This paper describes krl, a Knowledge Representation Language designed for use in understander systems. It outlines both the general concepts which underlie our research and the details of KRL-0, an experimental implementation of some of these concepts. These forms provide a variety of ways to express the logical structure of the knowledge, in order to give flexibility in associating procedures (for memory and reasoning) with specific pieces of knowledge, and to control the relative accessibility of different facts and descriptions. The formalism for declarative knowledge is based on structured conceptual objects with associated descriptions. These objects form a network of memory units with several different sorts of linkages, each having well-specified implications for the retrieval process.

Cutting-edge and "big-picture" in perspective, this popular introduction to cognitive development focuses on both the fascinating nature of children's thinking and the excitement and change in work in this area. Using an integrated topical approach, it explores the developmental aspects of social cognition, perception, memory, and language. Theoretically balanced, it considers the full spectrum of approaches--from Piaget's developmental stages, to information-processing (including connectionism), dynamic systems, contextual, theory-change, neo-Piagetian, evolutionary, neuroscience, and constraint approaches.