PRODUCTION SYSTEM CONFLICT RESOLUTION STRATEGIES (31-Dec-1976)

PRODUCTSON SYSTEM CONFLICT RESOLUTION STRATEGIES

J. McDerrnott and C. Forgy

December, 1976

Abstract: Production systems designed to functior, and grow in environments that make large numbers of different, sometimes competing, and sometimes unexpected demands require support from their interpreters that is qualitatively different from the support required by systems that can be carefully hand crafted to function in constrained environments. In this paper we explore the role of conflict resolution in providing such support. Using criteria developed in the paper, we evaluate both individual conflict resolution rules and strategies that make use of several rules.

This work was supported in part by the Defense Advanced Research Projects Agency (F44620-73-C-0074) and monitored by the Air Force Office of Scientific Research.

     The typical Artificial Intelligence system of the sixties labored within a highly constrained environment. The recent development of a number of powerful programming tools has made it feasible to build systems that can function intelligently in more interesting environments. The production system control structure [Davis and King, 1976; Newell, 1973; Rychener, 19761 is one such tool. In this paper we argue that the production system control structure -- provided it makes use of a carefully devised conflict resolution strategy -- is particularly suitable for systems that must respond in reasonable fashion to frequent, sometimes competing, and sometimes unexpected demands from their environments.

     A production system consists of a collection of productions held in production memory and a collection of assertions held in working memory. A productioq, P, is a conditional statement composed of zero or more condition elements, C's, and zero or more action elements, A's; a production has the form

Most action elements modify working memory by deleting, adding, or modifying working memory elements. Condition elements are templates; when each can be matched by an element in working memory, the production containing them is said to be instantiated. An instantiation is an ordered pair of a production and the elements from working memory that satisfy the conditions of the production. The production system interpreter operates within a control framework called the recognize-act cycle. In recognition, it finds the instantiations to be executed, and in action, executes them, performing whatever actions occur in their action sides. The recognize-act cycle is

repeated until either no production can be instantiated or an action element explicitly stops the processing. Recognition can be further divided into match and conflict resolution. In match, the interpreter finds the gonflict...