Results


30 / SEARCH AND SEARCH REPRESENTATIONS

Classics (Collection 2)

Optimal Search Strategies for Speech Understanding Control W. A. Woods Bolt Beranek and Newman Inc. Cambridge, MA 02238 Abstract This paper describes two algorithms for finding the optimal interpretation of an unknown utterance in a continuous speech understanding system. These methods guarantee that the first complete interpretation found will be the best scoring interpretation possible. Moreover, unlike other optimal strategies, they do not make finite-state assumptions about the nature of the grammar for the language being recognized. One of the methods, the density method, is especially interesting because it is not an instance of the "optimal" A* algorithm of Hart, Nilsson, and Raphael, and appears to be superior to it in the domains in which it is applicable. The other method, the shortfall method, is an instance of the A* algorithm using a particular heuristic function.


Consistency in Networks of Relations

Classics (Collection 2)

Artificial intelligence tasks which can be formulated as constraint satisfaction problems, with which this paper is for the most part concerned, are usually solved by backtracking. By examining the thrashing behavior that nearly always accompanies backtracking, identifying three of its causes and proposing remedies for them we are led to a class of algorithms which can profitably be used to eliminate local (node, arc and path) inconsistencies before any attempt is made to construct a complete solution. A more general paradigm for attacking these tasks is the alternation of constraint manipulation and case analysis producing an OR problem graph which may be searched in any of the usual ways. Many authors, particularly Montanan i and Waltz, have contributed to the development of these ideas; a secondary aim of this paper is to trace that history. The primary aim is to provide an accessible, unified framework, within which to present the algorithms including a new path consistency ...


DEVISING HEURISTICS / 23 A PROBLEM SIMILARITY APPROACH TO DEVISING HEURISTICS: FIRST RESULTS

Classics (Collection 2)

John Gaschnig Department of Computer Science Carnegie-Mellon University Pittsburgh, PA 15213 Abstract Here we describe an approach, based upon a notion of problem similarity, that can be used when attempting to devise a heuristic for a given search problem (of a sort represented by graphs). The next step is to find an algorithm for finding paths in P2, then apply this algorithm in a certain way as a heuristic for P1. Using the As algorithm, we experimentally compare the performance of this "maxsort" heuristic for the 8-puzzle with others in the literature. Many combinatorially large problems cannot be solved feasibly by exhaustive case analysis or brute force search, but can be solved efficiently if a heuristic can be devised to guide the search. Research to date on devising heuristics has spanned several problem-solving domains and several approaches.


The B* Tree Search Algorithm: A Best-First Proof Proceduret

Classics (Collection 2)

ABSTRACT In this paper we present a new algorithm for searching trees. It does this by attempting to find both the best arc at the root and the simplest proof, in best-first fashion. This strategy determines the order of node expansion. Any node that is expanded is assigned two values: an upper (or optimistic) bound and a lower (or pessimistic) bound. During the course of a search, these bounds at a node tend to converge, producing natural termination of the search.


An Experiment in Knowledge-based Automatic Programming

Classics (Collection 2)

Human programmers seem to know a lot about programming. This suggests a way to try to build automatic programming systems: encode this knowledge in some machine-usable form. In order to test the viability of this approach, knowledge about elementary symbolic programming has been codified into a set of about four hundred detailed rules, and a system, called PECOS, has been built for applying these rules to the task of implementing abstract algorithms. The implementation techniques covered by the rules include the representation of mappings as tables, sets of pairs, property list markings, and inverted mappings, as well as several techniques for enumerating the elements of a collection. The generality of the rules is suggested by the variety of domains in which PECOS has successfully implemented abstract algorithms, including simple symbolic programming, sorting, graph theory, and even simple number theory.


Proceedings

Classics (Collection 2)

VICTORIA, B. C. 14, 15, 16 MAY 1980 3. Goal Subsumption - Goal subsumption gives rise to dramatic situations when a subsumption state is terminated. For example, if John is happily married to Mary, and then Mary leaves him, all the goals subsumed by their relationship may now be problematic - John may become lonely, and miss his social interactions with Mary, for instance. Closely related to problems based on goal subsumption are those caused by the elimination of normal physical states. For example, becoming very depressed or losing a bodily function can give rise to the inability to fulfill recurring goals, and can therefore generate some interesting problems. The resolution of goal subsumption termination involves establishing a new subsumption state to re-subsume the recurring goals.


The Fifth International Conference on

Classics (Collection 2)

In this paper we discuss a general approach to detecting conceptual change developed in our ongoing work on concept drift [Rissland et al., 1994]. We illustrate our approach on an actual, still evolving, legal example, the "good faith" concept in the law of personal bankruptcy. In our approach, we detect that a concept is changing by measuring changes in a structural representation of it, such as a decision tree. For example, prior to the energy crisis in 1973 a desirable car was one that had a smooth ride and a roomy interior, whereas in the 80's and early 90's a desirable car was one that gets high gas mileage; more recently there is evidence that the concept is creeping back to a meaning that includes good gas mileage plus certain aspects of its earlier meaning, like roominess. This type of change has been called concept drift [Schlinuner, 1987].


Pzoceeding30

Classics (Collection 2)

Sponsored by: Defense Advanced Research Projects Agency Information Science and Technology Office CASE-BASED REASONING from DARPA: Machine Learning Program Pia& INTRODUCTION There is mounting evidence that human experts rely heavily on memory of past cases when solving problems in domains such as law, mathematics, design, and strategic planning. Thus, it seems natural to exploit this idea in constructing Al systems. This is the focus of systems using case-based reasoning; it constitutes a fifth major paradigm of machine learning research. A related approach is that of reasoning by analogy. In case-based reasoning ("CBR"), one uses memory of relevant "past" cases to interpret or to solve a new problem case.


Offprint from Artificial Intelligence and Heuristic Programming Edinburgh University Press 1971

Classics (Collection 2)

A general game-playing program must know the rules of the particular playing game. These rules are: (1) an algorithm indicating the winning state; (2) an algorithm enumerating legal moves. A move gives a set of changes from the present situation. There are two means of giving these rules: (1) We can write a subroutine which recognizes if we have won and another which enumerates legal moves. Such a subroutine is a black box giving to the calling program the answer: 'you win' or'you do not win', or the list of legal moves.


On Automated Scientific Theory Formation: A Case Study using the AM Program

Classics (Collection 2)

A program called "AM" is described which carries on simple mathematics research, defining and studying new concepts under the guidance of a large body of heuristic rules. The 250 heuristics communicate via an agenda mechanism, a global priority queue of small tasks for the program to perform, and reasons why each task is plausible (for example, "Find generalizations of'primes', because'primes' turned out to be so useful a concept"). Each concept is represented as an active, structured knowledge module. One hundred very incomplete modules are initially supplied, each one corresponding to an elementary set-theoretic concept (for example, union). This provides a definite but immense space which AM begins to explore.