Coordinated Problem Solvers
L. Gasser, Randall W. Hill · Annual Review of Computer Science · 1990
ion hierarchies. The decision to decompose a problem along a particular dimension affects the nature of the resulting subproblems. Hence the consequences of choosing a particular dimension must be weighed against alternatives. Tn many instances, a problem is broken into subproblems requiring fewer resources or less knowledge. The process of decomposition inherently involves matching the characteristics of the subproblem with the capa bilities and resources of an agent or the qualities of an operator (cf Davis & Smith 1983; Smith & Davis 1981). Other goals are to minimize the COORDINATED PROBLEM SOLVERS 2 1 9 dependencies between subproblems and to identify logical groupings of knowledge and tasks, to reduce communication and reasoning costs. Bond & Gasser ( l 988a) identified several dimensions commonly used for problem decomposition: • Abstraction level Knowledge in a problem-solving system can often be divided into levels of abstraction, each level representing a refinement or an aggregation of the knowledge from the previous level. Problem solvers can be associated with each level of abstraction; their task is to create new hypotheses based on hypotheses generated at lower levels. Hence, it is often natural to form a hierarchy of problem solvers based on the activities that occur at each abstraction level. In order to decom pose a system by abstraction it is necessary for the system designer to first identify the logical steps of knowledge aggregation in the overall problem solving process. Each step may result in a distinctly different class or type of hypothesis, and the problem-solving knowledge required to derive such an hypothesis may be unique. The consequence of decomposition by abstraction is that there is a natural dependency from one level of the abstraction to the next. Such a dependency affects several aspects of the problem-solving system: The order of activation of the problem solvers will be affected; the type of interactions and form of the communication among problem solvers may end up being up and down the abstraction hierarchy rather than lateral; the distribution of input data will likely be to the problem solvers at the lowest abstraction level; and the propagation of uncertainty and error will go from bottom to top. In many cases, choosing to decompose by abstraction level will influence the design of the coherency and control mechanisms in the system. Abstraction has been suggested as a method of decomposition in several systems (Lesser & Erman 1 980; Lesser & Corkill 1983; Wesson et al19 81) . • Availability of coordination When a problem is decomposed along a particular dimension it is necessary to ask whether there are adequate control and coordination mechanisms to handle the problem in this form. Of course, sometimes this cannot be determined until a problem solving attempt has been made; the main point here is to recognize that the decomposition of a problem should take into account the way that coordination is handled in the system and vice versa . • Control dependencies One may choose to decompose a task or a prob lem on the basis of trying to reduce control dependencies among problem solvers. Control is discussed in more detail in the section on coherent collective behavior below, but suffice it to say that control is often used as a means of guaranteeing the behavior of a collection of problem