Artificial Intelligence

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) ...

The MYCIN system has begun to exhibit a high level of performance as a consultant on the difficult task of selecting antibiotic therapy for bacteremia. This report discusses issues of representation and design for the system. We describe the basic task ...

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 ...

After discussing difficulties with previous proofs of A*'s optimality, new proofs are presented. In addition, examples are used to show: (1) that the value of (hn) may be a function of the state of the search as well as the available heuristic ...

Analysis of scenes of three-dimensional objects has, in the past, been largely limited to the world of polyhedra. Techniques for generating structured, symbolic descriptions of complex curved objects by segmenting them into simpler sub-parts are ...

Artificial intelligence tasks which can be formulated as constraint satisfaction problems, with which this paper is for the most part concerned, are usually by solved backtracking the examining the thrashing behavior that nearly always accompanies ...

This paper presents several methods for analysing finite state problems to discover certain types of symmetry. The methods are based on techniques used in Sequential Machine Theory, especially the use of partitions that have the Substitution Property. ...