This paper explores the paradigm that heuristics are discovered by consulting simplified models of the problem domain. After describing the features of typical heuristics on some popular problems, we demonstrate that these heuristics can be obtained by the process of deleting constraints from the original problem and solving the relaxed problem which ensues. We then outline a scheme for generating such heuristics mechanically, which involves systematic refinement and deletion of constraints from the original problem specification until a semidecomposable model is identified. The solution to the latter constitutes a heuristic for the former.

Artificial intelligence 20(4):393-425, July, 1983.

Almost all game tree search procedures used in artificial intelligence are variants on minimaxing. Until recently, it was almost universally believed that searching deeper on the game tree with such procedures would in general yield a better decision. However, recent investigations have revealed the existence of many game trees and evaluation functions which are ‘pathological’ in the sense that searching deeper consistently degrades the decision. This paper extends these investigations in two ways. First, it is shown that whenever the evaluation function satisfies certain properties, pathology will occur on any game tree of high enough constant branching factor.

An extention of the alpha-beta tree pruning strategy to game trees with ‘probability’ nodes, whose values are defined as the (possibly weighted) average of their successors' values, is developed. These ‘*-minimax’ trees pertain to games involving chance but no concealed information. Based upon our search strategy, we formulate and then analyze several algorithms for *-minimax trees. An initial left-to-right depth-first algorithm is developed and shown to reduce the complexity of an exhaustive search strategy by 25–30 percent. An improved algorithm is then formulated to ‘probe’ beneath the chance nodes of ‘regular’ *-minimax trees, where players alternate in making moves with chance events interspersed.

Three experiments have been conducted, and some novel designs and design rules have emerged. The paradigm for Eurisko's exploration is a loop in which it generates a new device configuration, computes its I/O behavior, tries to "parse" this into a functionally it already knows about and can use, and then evaluates the results. In the first experiment, this loop took place at the level of charged carriers moving under the effects of electric fields through abutted regions of doped and undoped semiconductors. This was unsurprising, as they were short sentences in the descriptive language we had defined (a language with verbs like Abut and ApplyEField, and with nouns like nDoped Region and IntrinsicChannellRegion).

Eurisko is an AI program that learns by discovery. We are applying Eurisko to the task of inventing new kinds of three- dimensional microelectronic devices that can then be fabricated using recently developed laser recrystallization techniques. Three experiments have been conducted, and some novel designs and design rules have emerged. The paradigm for Eurisko's exploration is a loop in which it generates a new device configuration, computes its I/O behavior, tries to "parse" this into a functionally it already knows about and can use, and then evaluates the results. In the first experiment, this loop took place at the level of charged carriers moving under the effects of electric fields through abutted regions of doped and undoped semiconductors. Many of the well-known primitive devices were synthesized quickly, such as the MOSFET, Junction Diode, and Bipolar Transistor. This was unsurprising, as they were short sentences in the descriptive language we had defined (a language with verbs like Abut and ApplyEField, and with nouns like nDoped Region and IntrinsicChannellRegion).

In this article we discuss a method for learning useful conditions on the application of operators during heuristic search. Since learning is not attempted until a complete solution path has been found for a problem, credit for correct moves and blame for incorrect moves is easily assigned. We review four learning systems that have incorporated similar techniques to learn in the domains of algebra, symbolic integration, and puzzle-solving. We conclude that the basic approach of learning from solution paths can be applied to any situation in which problems can be solved by sequential search. Finally, we examine some potential difficulties that may arise in more complex domains, and suggest some possible extensions for dealing with them.

A piece-of-advice suggests what goal should be achievednext while preserving some other condition. If this goal can be achieved in agiven problem-situation (e.g. a given chess position) then we say that the piece-ofadviceis 'satisfiable' in that position. In this way ALI makes it possible to breakthe whole problem of achieving an ultimate goal into a sequence of subproblems,each of them consisting of achievement of a subgoal prescribed by some pieceof-advice. The control structure which chooses what piece-of-advice to applynext consists of a set of 'advice-tables', each of them being specialized in acertain problem-subdomain.In Hayes, J. E., Michie, D., and Pao, Y.-H. (Eds.), Machine Intelligence 10. Ellis Horwood.

"The purpose of this paper is to compare various approaches to generalization in terms of a single framework. Toward this end, generalization is cast as a search problem, and alternative methods for generalization are characterized in terms of the search strategies that they employ. This characterization uncovers similarities among approaches, and leads to a comparison of relative capabilities and computational complexities of alternative approaches. The characterization allows a precise comparison of systems that utilize different representations for learned generalizations."Artificial Intelligence, 18 (2), 203-26.

ISIS-II takes a heuristic search approach to generating schedules. The key features of ISIS-II's approach is that it can represent and use a variety of different types of constraints to guide the search, and is able to selectively relax conflicting constraints. The plant under consideration** represents one of the most complex of scheduling tasks. The plant produces thousands of different parts,some of which are similar, some of which are not. Any part can be ordered in quantities from one to hundreds.