An Anthropocentric Tool for Decision Making Support

1 Introduction

In a context of short time, if not on-line, decision making for the control of industrial processes, we've been led to defining a new method for process control experts deci­ sion support . As the classical machine learning and total quality management tools are not fully convenient here because they may not fully account for flexibility and reuse, we have adopted an anthropocentric approach, putting back the expert operator in the center of the decision process so that the algorithm can turn his/her capacities as advantage.

This on-going work has been initialised in the frame of the European Brite-Euram project COMAPS (CO­ gnitive Management of Anthropocentric Production Sys­ tems- BE 96-3941) .

2 Cognitive model

We distinguish 3 phases in the life cycle of a process (see figure 1 and [Barthelemy et al., 1995]):

• a learning phase: the operator comes from the "novice" state to the. "expert" state. During this phase, the operator daily makes trials on the pro­ cess,
• a maintenance phase: the expert operator applies his/her know-how and adapts the process control rules,
• a reinitialisation phase (breaking/revision phase): the structural changes are so important that a sim­ ple adaptation is not enough anymore. A learning phase must be initialised once more.

In the frame of Anthropocentric Production Systems, which are forms of advanced manufacturing dependent upon a balanced integration between human skill, col­ laborative work organisation and adapted technologies, the human being is always inside the loop of the indus­ trial process. Consequently, we have to adapt classical machine learning techniques to give back to the expert user the possibility to intervene in the decision process.

The underlying cognitive models we've used in this aim suppose the operator is an expert, applying sta­ bilised process control rules for the usual maintenance of the production process. Once this restriction is cleared, we can apply the two following cognitive models:

• Bounded Rationality as described by Simon in [Si­ mon, 1979],
• Moving Basis Heuristic from Barthelemy and Mullet ([Barthelemy and Mullet, 1992]) .

2.1 Bounded Rationality

It assumes that the decision maker shows rationality (for situations in his/her usual domain of expertise) in the way that something is optimised. But this rationality is bounded by his/her cognitive abilities (of stocking and computing in short-term memory) and his/her satisfac­ tion.

It also supposes he/she uses a not too large set of stable strategies involving a small number of attributes. These strategies, constructed by his/her experience, are assumed to be stored in his/her long-term memory and they may be rather complex.

In addition, it supposes that some combinations of attributes are used more frequently than others.

As defined, this bounded rationality can be seen as a constraint for the expert to search among aspects (subset of attribute values) for a subcollection that should be short but large enough, with regards to its size and/or to its quality, to achieve decision.

2.2 Moving Basis Heuristic

The Moving Basis Heuristic (MBH) involves three cog­ nitive principles:

• parsimony: the decision maker manipulates a short subset of aspects due to his/her short-term memory capacity (storage capacity - there is no intermedi­ ate storage in the long-term memory - and compu­ tational abilities - strategies are computed in short­ term memory -) - see [Aschenbrenner and Kasubek, 1978] and [Johnson and Payne, 1985] -,
• reliabilityjwarrantability: the chosen sub-collection of aspects has to be large enough (size and/or qual­ ity) for individual or social justification- see [Adel­ bratt and Montgomery, 1980], [de Hoog and van der Wittenboer, 1986], [Montgomery, 1983] and [Ran­ yard and Crozier, 1983] -,
• decidabilityjfiexibility: the decision maker must ef­ fect . a choice by appropriate changes in the sub­ collection until a decision is taken (he/she has to achieve decision quickly in almost all cases) - see [Huber, 1986], [Montgomery, 1983], [Svenson, 1979]. Consequently, his/her strategies must be stable.

These principles, together with Bounded Rationality, show that the expert operator uses, at the same time, only a small amount of information.

We are not working in the classical expert system frame because:

• the operator modelling and the extraction strate­ gies are following these cognitive principles. The human expert uses complex strategies on a limited knowledge amount whereas expert systems use well­ known algorithms on a huge amount of information;
• the operator is always "in the loop", even for the strategies convergence to a pertinent set of process control rules;
• the protocol and the algorithmic techniques are spe­ cific to the incremental and iterative aspect under­ lying the maintenance phase of a process life cycle.

To represent the expert's decision space, we have cho­ sen to use a geometrical paradigm which is now de­ scribed.

3 Representation space

Experts are taking their decisions among a set X of n parameters xi together with their related value Xi· We call the tuple x = (x1 , ... , Xi, . .. , Xn) a parameters set­ ting. Each parameter Xi has its values domain Vi which can correspond to nominal as well as numerical, discrete or continuous, values set.

On the base of this parameters setting, an expert has to take a decision, that is to say he/she has to answer the question: "What do I have to modify on the process parameters setting to obtain a good quality for my prod­ uct (which is defined by the product parameters setting) ?". His/her answer consists of assigning a valued to the control parameter D, called decision outcome and the couple cs = (x, d) is called a control situation.

We work in an n-dimensional space, each point of which corresponds to a parameters setting. The control situations, i.e. parameters settings which have already been examined by the expert, are labelled with the value d of the decision outcome D.

As experts' decisions are taken on a restricted sub­ set of the available parameters that describe the process and/or the product to be manufactured, a process con­ trol rule R will have, as premises, a conjunction of a few number p of attributes aspects Ai, i.e. subsets of pa­ rameters values domain (Aj C Vj). For example a rule R can be: ·

This means that the attributes not appearing in these preconditions can take any value without influencing the current decision process. In an n-dimensional space, a rule R can then be seen as a cylinder W for which the dimensions are all free except those corresponding to the restricted aspects of R's preconditions. This cylinder is labelled with the value of R's decision outcome. Figure 2 shows, in the 3-dimensional space X= xl X x2 X x3, the cylinder corresponding to the rule

The dimension corresponding to X 2 is free, every value of x2 in v2 is valid.

The cylinder base B(W) is the hypercube defined by the rule R preconditions:

It has a dimension d(W) corresponding to the number of preconditions d(W) = IB(W) I· A set of cylinders is called a paving P.

4 COMAPS algorithm

4.1 Three distinct phases

The CO MAPS tool has been divided into 3 distinct parts which correspond more or less to the 3 phases of the process life cycle:

• the learning phase allows the extraction of an initial cylinders set Po from a learning data set - a set of control situations that have already been examined by the expert - , called history and denoted H, using more standard but adapted machine learning - and especially decision tree learning- techniques;
• the maintenance phase takes the result Po of the learning phase as well as H as inputs and it consists of an on-line update of the paving P according to new incoming control situations. This phase is the one we will further develop in this paper;
• a conflict solving phase is called when no acceptable - for the expert or for the maintenance phase algo­ rithm - modification is found to correctly update the current paving. This kind of conflict mostly appears when important technological changes are observed on the process. For more details concerning this phase, see [Saunier, 1998].

Whereas the learning phase consists of an off-line pro­ cess, the maintenance phase has to work at least at the pace the expert does: the algorithm is a kind of machine learning algorithm under cognitive constraints. But maintaining a paving consistent with the history to which one adds new control situations leads to face sev­ eral NP-complete problems.

4.2 NP-complete problems encountered

P1 : Search for maximal cylinders

Let vl, ... , Vn n finite sets and v = vl X ... X Vn, D a finite set, H ~ V x D, man integer and j E D.

Is there a cylinder W, corresponding to the decision outcome j for H (i.e. W H-compatible with j) , of di­ mension d, so that I WI ;::: m ?

Searching for such a cylinder W, i.e. trying to find a cylinder covering as much control situations as possible, becomes NP-complete since d;::: 2.

P2 : Covering by a minimal number of cylinders having at most d dimensions

Let vl, ... ' Vn n finite sets and v = vl X ... X Vn, D a finite set, H ~ V x D, s an integer, j E D and HJ = {cs = (x,y) E H/x E V andy ED withy= j}.

Does it exist a set of s cylinders W1 , ... , Ws so that Vi, Wi isH-compatible with j, d(Wi) :S d and U1<i<s Wi 2 HJ? --

The covering problem by a minimal number of cylin­ ders which dimension does not exceed a given integer d is NP-complete since d;::: 2.

P3: Consistency checking problem

Let dan integer, {W1 , ... , Wm} a set of cylinders dif­ ferently labelled and so that d(Wi) ;::: d.

Do we have nl<i<m Wi -:j:. 0?

If we have cylinders corresponding to different decision outcome values, we will have to verify the consistency of the paving, checking their intersection is empty and this becomes a NP-complete problem since d ;::: 3.

Most of the work to tune the maintenance phase consists then in finding heuristics to bypass these NP­ complete problems.

4.3 Main notions

Covering notion

Because:

• not every point of the space can be a real parameters setting, some values combinations being impossible or known as giving a far too bad result according to the product quality,
• we are searching for maximal cylinders but their base is bounded according to the extreme param­ eters values of the control situations in H,

the cylinders space paving is not complete and thus, a control situation - i.e. a labelled point - can have several status:

• not covered: the parameters setting doesn't fit with any of the cylinders bases. In any other case, the control situation is covered,
• bad covered: the control situation is covered but the labelling of the covering cylinder(s) is not the same as its own decision outcome value,
• well covered: the control situation is covered and the covering cylinder(s) has (have) the same decision outcome value.

Priority between cylinders

As P3 is NP-complete, we have decided not to guarantee a paving without any intersection. To cope with poten­ tial intersection, we have introduced a notion of priority between cylinders. We say that a cylinder W1 has the priority over a cylinder W2, noted W1 Pr W2, if

and if

where a and T are thresholds either fixed with the tool configuration or adapted dynamically according to the size of H and to the proportion of each label in H.

Two cylinders W1 and W2 of different labels can thus intersect without having neither W1 Pr W2 nor W2 Pr W1 and this can happen if:

• their intersection is empty, i.e. no control situation has already been seen in this area of the space,
• there are not enough control situations in the inter­ section according to the threshold a,
• none of the two labels in competition is related to a number of control situations significantly higher according to the threshold T.

Evaluation of a cylinder accuracy

As we cannot guarantee to generate a paving with cylin­ ders only covering control situations labelled in the same way and without any intersection of differently labelled cylinders, we need to be able to measure the "quality" of the paving and thus the "quality" of a cylinder with regards to H.

The quality of a cylinder, which we call CF(W), is estimated by the ratio between the number of control situations it covers well and the number of control situ­ ations it covers:

Of course, a cylinder W is too weak if CF(W) is not at least equal to the proportion of control situations having d( cs) = label (W). In the same way as for the priority computation, we have defined a threshold f3 under which a new cylinder to be integrated to the paving can not be accepted.

Furthermore, the global quality of the paving is de­ fined as the average of the n constituting cylinders qual­ ities:

As the aim of maintenance phase is to update the cur­ rent paving, this quality evaluation is also used to deter­ mine if a possible modification has to be applied or not. The criterion is then that the quality of the rule after modification is at least as good as the old rule one.

"Wait and see" policy

As the expert's rules are supposed to be stabilised, the algorithm is designed in a way that no action on the current paving is immediately tried. It waits until a sufficient number of control situations have confirmed something has to be modified. The arrival of an in­ consistent (i.e. bad or not covered) control situation implies a modification only if there are enough con­ trol situations with the same decision outcome value in its neighbourhood. This neighbourhood can be defined in several ways according to the inconsistent type. For example, for a not covered control situation cs = ((x1, . .. ,Xi, ... ,xn),d), we define it is an hyper­ cube which aspects are [xi - a(Vi), Xi + a(Vi)J, for nu­ merical attributes and {xi} for nominal attributes. If the control situation examined appears at the intersection of at least two rules, this neighbourhood is the intersection itself.

5 The maintenance phase

We remind that its aim is to update continuously the cylinders paving, starting with an initial paving Po which is consistent with the history H of the process and taking into account, as they arrive, new control situations the expert user has just added, with regards to the follow­ ing constraints, highly linked to the cognitive principles which have to be followed:

• remaining consistent with H at each step, i.e. mod­ ifying the cylinders so that H is still correctly de­ scribed by the updated rules set underlying the cylinders paving,
• keeping a small number of dimensions (at most 4 to be compatible with the expert's short-term memory abilities) in the cylinders base - a cylinder can be based on more than 4 dimensions but it should not be more than a temporary state, corresponding for example to a less common situation for the expert, during which he has to adapt a bit further his/her own rules -,
• keeping a small number of cylinders in the paving.

5.1 Cylinders modification functionalities

Different modification functions have been implemented that can be applied to one or several cylinders of the current paving, according to the status of the control situation to be integrated to H:

1. generalisation of an existing cylinder by suppressing one constrained dimension: d(Wt) = d(wt-1) - 1 wt-1 c wt
2. generalisation of an existing cylinder by extending the possible values over one dimension. For one i so that Ai C Vi, At-1 c At wt-1 c wt t t
3. creation a cylinder by dividing a cylinder into two: wt- 1 -+ Wf EB W:§ with label(Wf) = label(Wt- 1 ) and label(Wi) -j.label(wt- 1 )

1. creation a new cylinder, according to the current control situation cs = ( x, d), by creating aspects for all the attributes 1 and taking the conjunction of at most four of them to define the new cylinder base, which will have d as a label.
2. restriction of a cylinder that is unnecessarily large by adding some constraints on one dimension: d(Wt) = d(wt-1) + 1 wt c wt-1
3. restriction of a cylinder by restricting the aspect extension on one of its dimension. For one i so that Ai c Vi, At c At-1 wt c wt-1

1. modification of the priority between the cylinders covering the current control situation by recomput­ ing it.

5.2 Functionalities use

Of course, these modifications are not used in any case. If the new control situation to be treated is already well covered, the only thing we might try is the first function: as the cylinder is confirmed by the arrival of a well classified example, we can try to see if all its dimen­ sions are needed or if it can be extended without loosing its quality (using function (1.).

For a control situation currently not covered, the algo­ rithm will first try to integrate it to an existing cylinder of the same label using function (2.) and, if it doesn't work, to create a new cylinder to cover it using function ( 4.).

For a bad covered control situation cs, and according to the inconsistency type with regards to the cylinder(s) involved- i.e. considering the "environment": number of cylinders covering cs, number of different labels, priority value(s) , ... - several of these seven modifications can be tried to improve the situation. But, as the expert rules are supposed to be stabilised, the order in which these functions are applied is strongly dependent on how deep the resulting modification is for the paving.

Indeed, according to the cognitive model, cylinders must stay large - i.e. with not too constrained bases, which corresponds to short rule premises conjunction - and not too numerous.

One of the criteria involved while sorting the functions is that they imply local or more global modifications: function (7.) - priority modification - is clearly the one that leads to the most local modification whereas func­ tion ( 4.) - cylinder creation - leads to far deeper changes so it is the last one tested.

Function (1.) is not sorted with the other ones: it is a bit different because it is applied only in case the current control situation is well covered by a too restricted, and thus not satisfying, cylinder - i.e. corresponding to a rule for which there are more than four aspects in the premise-.

1 We don't describe here the way these aspects are computed.

As the modifications implied by function (2.) - exten­ sion of an aspect values - remain local , it is the second the algorithm tests. Then, the third alternative is func­ tion (3.) - cylinder division -: of course it creates a new cylinder but in an area that is already covered by a more general cylinder.

Finally, functions (5.) and (6.) are tried, in this order, because they both imply smaller cylinders - i.e. more constrained premises for the rules -, which contradicts one of the cognitive principles.

6 Comparison with previous works m this domain

This kind of approach, using Bounded Rationality and MBH principles as underlying cognitive principles to an anthropocentric algorithm, has already been led and val­ idated in [Barthelemy et al., 1995] and [Laurent et al., 1994]. The improvements we've brought for COMAPS are of three kinds:

• we don't assume anymore any hypothesis on the or­ der of the attributes modalities: the previous works were turning this order, which corresponds to the decision maker's attractiveness scales, to advantage because the representation space was derived from Galois' lattices, but these scales are difficult to ob­ tain without using verbalisation techniques and they are different from an expert to another;
• the formerly defined methods were rapidly limited by the number of attributes taken into account for the computation. As for real industrial processes we often have to deal with more than 20 parame­ ters, it was a real need to find a way to push back this limit, especially because we can not afford long computation time for an on-line control;
• the expert is observed in his/her real decision mak­ ing process: after the initial set of rules has been extracted off-line, every new control situation is given a decision outcome value on-line by the expert and is immediately treated by the algorithm. The former developments were using dynamically com­ puted questionnaires to ask the expert its decision in a given situation but this was not his/her normal task, and if something was changing in his/her de­ cision rules, it could be modified in the computed rules only by starting again to answer a new set of questions.

7 Current results and work perspectives

In the frame of this european project, we have the pos­ sibility to test our program on three real industrial pro­ cesses, in the fields of copper foil production, printed cir­ cuit boards manufacturing and brake pads production.

7.1 Current results

Real data being confidential, we've been testing the algo­ rithm through a mockup with coded data. The first tests have been led without the expert, dividing the coded data set into a training set for the learning phase and an incoming situations set for the maintenance phase.

With one of the pilot sites data, we had the possibility to test the behaviour of the maintenance phase facing a known evolution of the process control. Starting from a set of 6 institutional rules and an history of 1086 cs, the rules set has been updating according to 556 new cs.

The results according to the quality of the rules are summarized in Figure 3, the last column corresponding to the type of modification applied according to the list presented in 5.1. All the results have been shown to the expert and they were validated.

7.2 Work perspectives

We still have to improve the internal model of priority between cylinders: at this time, it is represented by a boolean matrix where P(i,j) is 1 if W;PrWj and is 0 otherwise. This doesn't give any information concerning the priority status for an intersection of more than two cylinders and it's not possible to deduce it looking at the priority between every pair of cylinders involved. On the opposite, this kind of deduction could lead to a non­ sense: if we have, for example, three cylinders wl ' w2 and W3 with W1PrW2, W2PrW3 and W3PrW1, which of them should have the priority ?

In addition, we wait for a prototype, now under de­ velopment, to be installed (benchmarking in April this year) to be able to make some more tests, but this time in a real decision context and not only with a posteriori validation.

Some comparisons between classical machine learning tools, and especially decision tree learning tools like ID3 [Quinlan, 1986] and C4.5 [Quinlan, 1993] are also under way.