PROBLEM SOLVING



Towards a Typology of Expert Systems

Khurshid Ahmad

Department of Computer Science,

Trinity College, DUBLIN.

17 Nov 2008

Problem Solving and Symbol Manipulation 1

Towards a typology of problem solving and solution types 2

Structure Induction 3

Structural Transformation 3

Structural Arrangement 3

Computation and Problem Solving 3

Typology of problem solving methods based on applications 4

Basic activities of expert systems and problem solving typology 4

Interpretation 5

Prediction 6

Diagnosis 6

Generic operations of an expert problem solver 7

A worked example 9

Rule-based problem solving: Reduction and Reaction Systems 10

Problem Solving and Symbol Manipulation

Problem solving is defined as a strategy for ‘transforming a given situation into a goal situation when no obvious method of solution is available to the problem solver’ (Mayer, 1990: 284). For cognitive psychologists, the solution of the problem (if any) occurs in the mind/cognitive system of the problem solver and thus has to be inferred indirectly from the way in which the solver behaves during the solution of a given problem.

If we believe the cognitive psychologists, then the problem solving strategies should involve a process of abstraction: whatever the solver does, he or she does in his or her mind/cognitive system. This process of abstraction - simplification or modelling in computational terms - is referred to as symbol manipulation. This predicated symbol set, because you must have a set of symbols before they are manipulated, comprises the knowledge of the problem to be solved. Some of this knowledge will be shared with others equally capable of solving similar problems, the so-called domain knowledge. Some of this knowledge will relate to observations which the problem solver shares with others of similar intelligence but may or may not share the domain knowledge. And, some of this knowledge will relate to how the solver should make not of his or her failures and learn from them, how the solver should refine his or her knowledge whilst dealing with variations of extant problems and, indeed, new ones; and how the solver should articulate his or her knowledge.

Given that problem solving implies that it is ‘what goes on in a problem solver’s mind’, then the best way of understanding, and possibly making it open to inspection and verification, is to probe the behaviour of the problem solver. The problem solver has to be psychologically interviewed and his or her writings related to his or her domain of expertise will have to be analysed for potential repetitive and well-shaped patterns. These patterns may be behavioural patterns - since problem solvers hypothesise the existence of a solution and then look for data, or things given, to fit the hypothesis, others may do the opposite.

It also appears that the knowledge of how to solve problems is internalised through the use of a symbol set and that it is the manipulation of this symbol set which helps in the transformation of the ‘problem state’ to ‘goal state’. This vocabulary, comprising terms like symbol sets, transformation, states is used deliberately to ground this unobservable, essentially animal activity of problem solving, as an activity which involves distinction between valid reasoning and invalid reasoning during problem solving. Once we accept that problem solving is based on a systematic body of knowledge in that successful problem solvers, within a specialism, have similar behaviour patterns, then one can claim that this valid reasoning can be systematised and that notion relevant to it can be formally investigated. The subject-discipline of logic deals mainly ‘valid reasoning, its systematisation and the study of actions relevant to it’ (Lacey, 1986: 126).

The problem solver is expected to:

(a) identify problems within the problem space which are, in his or her view, solvable, based on personal experience or on the appearance of the problem;

(b) evaluate the extant knowledge bases: specialist domain knowledge and know-how, perhaps, is the first and then the shared world knowledge. The problem solving has a communication system comprising language and image-based symbols - the semes in a semiotic system - which comprises not only the knowledge of the language and other semes, but also how to use this knowledge to effectively communicate with others;

(c) find solutions which are relevant and cost effective.

The problem solver then generates a personal solution which is passed on to an end-user. The solver also uses the solution to revise and update his or her knowledge base.

Towards a typology of problem solving and solution types

Problem solving, as fashioned in logic and cognitive science, is related to reasoning, logical reasoning to be precise, and planning, for example organisation of a hierarchy of sub-goals for solving problems.

Problems can be divided into:

well-defined problems : game of chess

ill-defined problems : crisis management

routine problems : mathematical problems

non-routine problems : resource management

Non-routine and ill-defined problems require creativity, co-operation with others, and setting up of alternative goals for their solution. Extremely routine problems, which have no obstacles, are not classified as problems. Well-defined and routine problems do not directly involve human beings and their solutions are usually objective and transferable. Ill-defined and non-routine problems almost invariably involve human beings, their solutions are the subjective choice of the solver.

Problem solving is sometimes involved in discovering structures and structural organisation. These structures may be concrete, like physical components, or abstract, for example (interactive) layers in language (vocabulary, syntax, semantics). Such a classification leads to three different kinds of problem: Structure Induction; Structural Transformation; and Structural Arrangement.

Structure Induction

Structure Induction problems occur when a problem solver is given a series of instances and must discover a pattern or rule. Relatively common examples of this problem are those found in mathematical testing, like series completion, observational accuracy, for instance, analogy problems. Specialist examples include the identification of the chemical structure of a novel chemical when matched against an extant database of chemical structures.

Structural Transformation

Structural Transformation problems are where an initial state and a goal state is given and the problem solver is to prescribe/describe a sequence of legal operations for transforming an initial to a goal state. The well known Tower of Hanoi problem is a good example here. Whilst problems of structure induction require inductive reasoning, the structural transformation problems require inductive reasoning.

Structural Arrangement

Structural Arrangement problems are those where the rearrangement of the parts, presented as a problem, leads to the solution. Anagrams and cryptographic decipherment/encoding are good examples of this genre of problem. Problems in design and construction of artefacts are also good examples of structural arrangement.

Computation and Problem Solving

The key question for computer-based problem solving is to formulate problems in a manner which can be solved in a computationally efficient and effective way. There are two major problem formulations listed in the literature on computational problem solving:

Declarative Problem Formulations: such a formulation is particularly suited to problems about which we can make the following declaration:

Given a domain specification D, find a solution x such that x is a member of a set of possible solutions X and it satisfies the problem conditions c (Amarel, 1992: 1214).

It is essential, for this declaration to become a problem statement for a computer system, that both the set X and the conditions c are expressed in terms of concepts in D.

Procedural Problem Formulation: For a problem solving system to execute solution seeking activities, it must have a formulation which is in a form which can be assimilated/accepted by a procedural schema for problem solving that is available to the system. The assimilation/acceptance into a procedural schema is equivalent to the definition of a specific problem solving procedure.

The important point to remember here is that a declarative formulation helps the problem solving system to understand the problem statement, and then using a procedural formulation, the system can proceed to solve the problem.

Typology of problem solving methods based on applications

Peter Jackson (1990) has discussed ‘a number of rather difficult questions about the various problem solving methods that are available to expert systems practitioners and the kinds of applications that they are most suitable for’ (1990: 234). The author has looked at whether or not expert systems applications can be classified and if one can classify the ES applications, then whether or not there are problem solving methods, each with a differentiating idiosyncrasy, which may be relevant to classes of expert systems applications. Given that there is a class of expert systems for which a set of problem solving methods exist and are appropriate , then we can ask the question whether or not there are representation formalisms and reasoning strategies for operationalising a given problem solving method.

Basic activities of expert systems and problem solving typology

Waterman has argued that whilst expert systems have been built to solve many different types of problems, ‘their basic activities can be grouped [as follows]’(1986: 22-23):

| |Category | |Problem Addressed |

| | |Task |Descriptor |

|A |Interpretation |Infer |Situation descriptions from sensor data |

| |Prediction |Infer |Likely consequences of given situations |

| |Diagnosis |Infer |System malfunctions from observables |

|B |Design |Configure |Objects under constraints |

| |Planning |Generate |Sequences of activities that achieve stated goals |

| |Monitoring |Compare |Observations to expected outcomes |

|C |Debugging |Prescribe |Remedies for malfunctions (after DIAGNOSIS) |

| |Repair |Execute |Plans to administer prescribed remedies (after DIAGNOSIS and DEBUGGING) |

| |Control |Govern |Overall system behaviour by anticipating problems [PREDICTION], PLANNING |

| | | |solutions and MONITORING necessary action |

|D |Instruction |DIAGNOSE, DEBUG, |Student behaviour |

| | |REPAIR | |

The 10 categories above have been subdivided into four super-categories, ‘A’, ‘B’, ‘C’ and ‘D’. Supercategory A involves the INFERENCING tasks; Supercategory B involves three independent tasks - CONFIGURATION, GENERATION and COMPARISON. Supercategory C contains categories with tasks which are to be executed only after one or more tasks in Categories A and B have been executed. The last supercategory, D, has only one application instruction whose tasks in themselves are generic categories in A, B and C. there is an interdependence in these general categories. Such interdependence mitigates against the general nature of the categories. We will see that the authors have criticised Waterman’s classification because the categories are not ‘mutually exclusive’. But more of this later; first we will elaborate on some of the categories mentioned in the table above. Our elaboration will be based on references to expert systems which fall into these categories, together with an exemplar rule for the category.

Interpretation

This involves the processing of different kinds of data (obtained usually through a sensor) for determining characteristic features, signatures, meanings and so on. The following table shows three data types processed by various expert systems for inferring a range of situation descriptions:

|System |Response Data |Situation Described |

|Vision system |visual images |infer features |

|Natural language processing systems |audio signals |infer meaning |

|Chemical interpretation systems |X-ray diffraction; mass spectra, NMR |infer chemical structure |

| |spectra | |

|Geological Interpretation Systems |Dipmeter logs |infer subsurface geological structure |

|Medical interpretation systems |patient monitoring data: heart rate, |diagnose and treat illnesses |

| |blood pressure, etc. | |

|Military interpretation systems |Radar/sonar input |perform situation assessment and target |

| | |identification |

Exemplar Rule: INFLAMMATORY CONDITIONS EXPERT SYSTEM

IF the tracing pattern is ‘asymmetric gamma’

AND the gamma quality is normal

THEN the concentration of gammaglobulin is within normal range

Prediction

This typically involves assessing damage by some agent or event caused to other, or the estimation of quantities based on qualitative/subjective input. Prediction systems sometimes use simulation programs for generating situations and scenarios based on models of real-world activities. The simulation results taken together with knowledge about processes form the basis for prediction.

Kenneth Yip’s KAM program is an expert system which comprises a knowledge base of non-linear dynamics and can reason about the implications of a difference equation, Michel Henon’s star motion system, KAM performs [autonomously] a number of simulations and determines regular regions and regions with chaotic orbits (cited in Winston, 1992: 8-9).

Diagnosis

Diagnosis involves the use of situation descriptions, behaviour characteristics of a system, acknowledge about (system) components to INFER probable causes of system malfunctions. Medical diagnosis and diagnosis of computers or other complex systems’ malfunctions are good examples of a diagnosis system.

MYCIN is a good example of a diagnosis system.

Generic operations of an expert problem solver

Overlapping categories in a classification system indicate that the categories do not effectively take into account the key differences and important similarities amongst objects that are being classified. The existence of overlapping categories in Waterman’s classification of expert systems indicate these 10 categories, of which many are overlapping, can be categorised further. Clancey has suggested that they way in which we can classify expert systems should include ‘the kinds of operation such an [expert systems] program can perform with respect to a real-world system’. The real world systems may be engineering systems, for example the systems for manufacturing portable telephones or computers, biological systems, like the respiratory organs of an animal, and so on. The real-world system is essentially a composite of objects with protocols, based on theories and rules, that govern the emergence of these objects, and their location, and the interaction between system objects and between the system and objects (and systems) that are external to the system.

Clancey suggests that an expert system may perform analytic operations that may interpret the real-world system.

[pic]The interpretation operation comprises identification, prediction and control. The identification operation will result in understanding what kind of a real-world system a knowledge engineer has to deal with. The prediction operation will indicate the potentail outputs of the real-world system given the inputs. The control operation helps in understanding how a known real-world can be made to output desired output for a pre-determined input. The identification operation is an umbrella term for two specialised operations: monitoring, that detects discrepant behaviour, and diagnosis that explains the discrepant behaviour.

And, that an expert system can perform synthetic operations that may construct a real-world system:

[pic]

The specification operation states the constraints that any design of a real-world system must satisfy. The design operation generates an arrangement of parts that can satisfy the constraints. The assemble operation realises the design by putting the parts of the real-world system together. The design operation comprises two kinds of design operations: configuration operation concentrates on the actual structure of the real-world system and planning operation concentrates on how that structure will be assembled.

A worked example

The following expert systems were developed to solve problems in different disciplines:

|System |Description |

|XCON |(eXpert CONfigurer ) configures DEC computer systems. From a customer's order it |

| |decides what components must be included to produce a complete operational system and|

| |determines the spatial relationships between all of the components. |

|VM |(Ventilator Manager) provides diagnostic and therapeutic suggestions about |

| |post-surgical patients in an intensive care unit (ICU). |

|SACON |(Strucural Analysis CONsultant) helps an engineer to determine analysis strategies |

| |for particular structural analysis problems. SACON was developed as a front-end for |

| |a non-linear finite element analysis program, MARC. |

Using Clancey's typology of expert systems, based on the two generic operations, synthesis and analysis, for classifying the above mentioned expert systems, describe why Clancey's typology was better than other expert systems' tyoplogies, for example, Hayes-Roth's classification or that of Saul Amarel's?

An expert system may perform a mixture of synthetic and analytic operations on the image of the real-world problem domain (domain objects and their inter-relationships etc.) Synthetic operations include the specification design and assembly of the objects (and relationships and constraints). The design tasks include those of configuration and planning. The analytic operations enable an expert system to monitor, predict and control. The identification tasks include monitoring and diagnosis tasks.

The above generic operations, synthetic and analytic, now provide a good typology of expert systems in that they deal with the questions of problem-solving at an abstract level and deal with the questions of overlapping tasks like monitoring and diagnosis or configuration and planning. According to Clancey, the synthetic operations enable an expert system to construct the image and the analytic operations help to interpret the image.

Thus the classification of expert systems can be organised according to the tasks they perform:

|Interpret |

|Task |Subtasks |SACON |VM |SOPHIE |XCON |

|Identify |monitor | |Patients' state |State of the circuit | |

|Identify |diagnose |Identity structure |Faulty modules and | | |

| | | |components | | |

|Predict | |Structure's behaviour | | | |

|Control | | | | | |

|Construct |

|Specify | | | |Constraints on | |

| | | | |components and their | |

| | | | |containers | |

|Design |Configure | | |Configure components | |

|Design: |Plan | | | | |

|Assemble |Modify |Structure State/Loading |Breathing rate and drug | | |

| | |Profile |therapy | | |

In addition, Amarel (1989) has proposed a derivation/formulation typology of problem solving behaviour

Rule-based problem solving: Reduction and Reaction Systems

Patrick Winston in his book Artificial Intelligence (1992)has argued that expert systems can be classified as deduction or reduction systems. MYCIN, the microbial infection therapy expert system, is classified as a deduction system and X-CON, the expert system used in the configuration of expert system, as reaction system.

So what is the principal difference between a deduction system and a reaction system? In deduction systems, like MYCIN, the if parts of the some of the if-then rules specify combinations of assertions, and the then part specifies a new assertion to be deduced directly from the triggering combination. Deduction systems are designed with the view that such systems will deal with static worlds where nothing that is shown to be true ever becomes false.

In reaction systems, like XCON, the if parts specify the conditions that have to be satisfied and the then part specifies an action to be undertaken. Sometimes the action is to add new assertion; sometimes it is to delete an existing assertion; sometimes, it is to execute some procedure that does not involve assertions at all. Reaction systems deal with worlds where things change in that if something has been shown to be true there is a possibility that it may be proved false at some later stage. Reaction systems are characterised by a variation in the syntax of the rules: Rather than using the ubiquitous syntax:

if antecedents

then consequent(s)

which causes problems when assertions are to be removed from the working memory, e.g. if antecedents

then remove (some previous) asserted fact

consequent(s)

the reaction systems typically use the add-delete syntax:

if antecedents

delete (some previously) asserted fact

add consequent (s).

References:

Winston, Patrick H. 91992). Artificial Intelligence (3rd Edition). Reading (Mass.):Addison-Wesley Publishing.

Jackson, Peter (1990). Introduction to Expert Systems (Second Edition). Wokingham (England): Addison-Wesley Publishing Company.

Lacey, P. (1996). A Dictionary of Philosophy. London: Routledge.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download