AI research at CMU is closely integrated with other activities in the Computer Science Department, and to a major degree with ongoing research in the Psychology Department. Although there are over 50 faculty, staff and graduate students involved in various aspects of AI research, there is no administratively (or physically) separate AI laboratory. To underscore the interdisciplinary nature of our AI research, a significant fraction of the projects listed below are joint ventures between computer science and psychology.

Finally, abstraction can be extended to involve multiple complexity. In particular, one of the most costly behaviors levels, leading to a hierarchy of plans, each serving as a of the basic problem solving strategies is their inefficiency skeleton for the problem solving process at the next level in dealing with goal descriptions that include conjunctions. of detail. The search process at each level of detail can Because there is usually no good reason for the problem thus be reduced to a sequence of relatively simple solver to prefer to attack one conjunct before another, an subproblems of achieving the preconditions of the next incorrect ordering will often be chosen. This can lead to step in the skeleton plan from an initial state in which the an extensive search for a sequence of actions to try to previous step in the skeleton plan has just been achieved.

Artificial Intelligence

In Clarke, M. R. B. (Ed.), Advances in Computer Chess 2, pp. 103-109. Edinburgh University Press

In Clarke, M. R. B. (Ed.), Advances in Computer Chess 2, pp. 103-109. Edinburgh University Press

In AAAI-80, pp. 102–104.

ACM Computing Survey 12:213-253

Earlier version in IJCAI 6 (1979). Artificial Intelligence, 14 (2), 165-203.

An algorithm based on state space search is introduced for computing the minimax value of game trees. The new algorithm SSS∗ is shown to be more efficient than α-ß in the sense that SSS∗ never evaluates a node that α-ß can ignore. Moreover, for practical distributions of tip node values, SSS∗ can expect to do strictly better than α-ß in terms of average number of nodes explored. In order to be more informed than α-ß, SSS∗ sinks paths in parallel across the full breadth of the game tree. The penalty for maintaining these alternate search paths is a large increase in storage requirement relative to α-ß.

The determination of subgraph and graph isomorphisms is an important application for the algebraic manipulation of networks of binary constraints. Simplified and streamlined arc consistency and tree search algorithms are introduced, and experimental results show substantial reduction in timings compared with previous algorithms for determining isomorphisms. Several path consistency algorithms, including a new one, have been timed experimentally on isomorphism problems, and found not to be cost effective despite their theoretical appeal. The importance of this result is enhanced by the absence of previously published experimentation with path consistency. A theoretical study of the new path consistency algorithm provides insight into the experimental results.