Review of Heuristics: Intelligent Search Strategies for Computer Problem Solving

To resolve the search-incompleteness of depth-first logic program interpreters, a new interpretation method based on the tabulation technique is developed and modeled as a refinement to SLD resolution. Its search space completeness is proved, and a complete search strategy consisting of iterated stages of depth-first search is presented. It is also proved that for programs defining finite relations only, the method under an arbitrary search strategy is terminating and complete.

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.

Search algorithms for finding optimal solutions are, at least from the practical point of view, often enough intractible, so that the search for good ('satisficing') solutions becomes a research topic of its own interest. Satisficing solutions and different approaches to obtain them under various criteria is the subject of these notes, published in the series "Research notes in artificial intelligence". In an introductory chapter the author presents the known point - value and the point - { { set of values} } identification used in search- based decision-algorithms for guiding the search and discusses some of their advantages and disadvantages. This motivates the here studied alternative approach using that evaluation functions do not return a point - value or a range of values corresponding to a point (state) in a tree but now a distribution function, that describes the possible location of the'value' of the state. Chapter 2 introduces this model, Chapter 6 resumes the basic results.

Branch and Bound (B&B) is a problem-solving technique which is widely used for various problems encountered in operations research and combinatorial mathematics. Various heuristic search procedures used in artificial intelligence (AI) are considered to be related to B&B procedures. However, in the absence of any generally accepted terminology for B&B procedures, there have been widely differing opinions regarding the relationships between these procedures and B&B. This paper presents a formulation of B&B general enough to include previous formulations as special cases, and shows how two well-known AI search procedures (A∗ and AO∗) are special cases of this general formulation.

Optical transport networks based on wavelength division multiplexing (WDM) are considered to be the most appropriate choice for future Internet backbone. On the other hand, future DOE networks are expected to have the ability to dynamically provision on-demand survivable services to suit the needs of various high performance scientific applications and remote collaboration. Since a failure in aWDMnetwork such as a cable cut may result in a tremendous amount of data loss, efficient protection of data transport in WDM networks is therefore essential. As the backbone network is moving towards GMPLS/WDM optical networks, the unique requirement to support DOE's sciencemore » mission results in challenging issues that are not directly addressed by existing networking techniques and methodologies. The objectives of this project were to develop cost effective protection and restoration mechanisms based on dedicated path, shared path, preconfigured cycle (p-cycle), and so on, to deal with single failure, dual failure, and shared risk link group (SRLG) failure, under different traffic and resource requirement models; to devise efficient service provisioning algorithms that deal with application specific network resource requirements for both unicast and multicast; to study various aspects of traffic grooming in WDM ring and mesh networks to derive cost effective solutions while meeting application resource and QoS requirements; to design various diverse routing and multi-constrained routing algorithms, considering different traffic models and failure models, for protection and restoration, as well as for service provisioning; to propose and study new optical burst switched architectures and mechanisms for effectively supporting dynamic services; and to integrate research with graduate and undergraduate education.