Proc. Tenth Intl. Joint Conference on Artificial Intelligence (pp. 334-337). Milan, Italy: IJCAII.

Annual Review of Computer Science

IEEE Computer, pages 100-109, January

Review of Heuristics: Intelligent Search Strategies for Computer Problem Solving

In ICLP-86, pp. 84–98.

Research in AI within the Computer Science Department at the University of California, Los Angeles is loosely composed of three interacting and cooperating groups: (1) the Artificial Intelligence Laboratory, at 3677 Boelter Hall, which is concerned mainly with natural language processing and cognitive modelling, (2) the Cognitive Systems Laboratory, at 4731 Boelter Hall, which studies the nature of search, logic programming, heuristics, and formal methods, and (3) the Robotics and Vision Laboratory, at 3532 Boelter Hall, where research concentrates on robot control in manufacturing, pattern recognition, and expert systems for real-time processing.

A variety of proposals for preferred methodological approaches has been advanced in the recent artificial intelligence (AI) literature. Rather than advocating a particular approach, this article attempts to explain the apparent confusion of efforts in the field in terms of differences among underlying methodological perspectives held by practicing researchers. The article presents a review of such perspectives discussed in the existing literature and then considers a descriptive and relatively specific typology of these differing research perspectives. It is argued that researchers should make their methodological orientations explicit when communicating research results, to increase both the quality of research reports and their comprehensibility for other participants in the field. For a reader of the AI literature, an understanding of the various methodological perspectives will be of immediate benefit, giving a framework for understanding and evaluating research reports. In addition, explicit attention to methodological commitments might be a step towards providing a coherent intellectual structure that can be more easily assimilated by newcomers to the field.

About a year ago. I was approached by Phoebe Huang of Comtex Scientific Corporation who hoped that I would help devise a dramatically expanded index for topics in AI to aid Comtex in indexing the series of AI memos and reports that they had been gathering. Comtex had tried to get the ACM to expand and update its classification. But was told that ACM had just revised the listing two years ago or so ago, and did not intend to revise it again for a while: even if they did. The revision might require a year or more to complete. Comtex wanted the new classification within six to eight weeks. I agreed to take on the task, thinking it wouldn't be too hard. The major decision I had to make was whether to use the existing ACM index scheme and add to it, or start with a fresh sheet of paper and devise my own. I decided to stick with ACM's top two levels, only adding, not modifying, major headings.

The complexities of various search algorithms are considered in terms of time, space, and cost of solution path. It is known that breadth-first search requires too much space and depth-first search can use too much time and doesn't always find a cheapest path. A depth-first iterative-deepening algorithm is shown to be asymptotically optimal along all three dimensions for exponential tree searches. The algorithm has been used successfully in chess programs, has been effectively combined with bi-directional search, and has been applied to best-first heuristic search as well. This heuristic depth-first iterative-deepening algorithm is the only known algorithm that is capable of finding optimal solutions to randomly generated instances of the Fifteen Puzzle within practical resource limits.

This paper reports several properties of heuristic best-first search strategies whose scoring functions ƒ depend on all the information available from each candidate path, not merely on the current cost g and the estimated completion cost h. It is shown that several known properties of A* retain their form (with the minmax of f playing the role of the optimal cost), which helps establish general tests of admissibility and general conditions for node expansion for these strategies. On the basis of this framework the computational optimality of A*, in the sense of never expanding a node that can be skipped by some other algorithm having access to the same heuristic information that A* uses, is examined. A hierarchy of four optimality types is defined and three classes of algorithms and four domains of problem instances are considered. Computational performances relative to these algorithms and domains are appraised.