Temporal Decision Trees or the lazy ECU vindicated

1 Introduction

The adoption of on-board diagnostic software in modern vehicles and similar industrial products is becoming more and more important. This is due to the increasing complexity of systems and subsystems, esp. mechatronic ones like the ABS and fuel injection, and to the increasing demand for availability, safety and easy maintenance. However, in order to keep costs acceptable, esp. for large scale products like cars, limited hardware resources are available in Electronic Control Units (ECUs). Thus, although the model-based approach is very interesting and promising for the automotive domain and similar ones [Console and Dressler, 1999; Sachenbacher et al., 1998], it is still questionable if diagnostic systems can be designed to reason on first-principle models on board. For this reason the following compilation-based scheme to the design of on-board diagnostic systems for vehicles was experimented in the Vehicle Model Based Diagnosis (VMBD) BRITE-Euram Project (1996-99), and applied to a Common-rail fuel injection system [Cascio et al., 1999]:

• AFA model-based diagnostic system, which can be used to solve problems off-line (and then for off-board diagnosis

A3 This work was partially supported by the EU under the grant GRD-1999-0058, IDD (Integrated Diagnosis and Design), whose partners are: Centro Ricerche Fiat, Daimler-Chrysler, Magneti Marelli, OCC'M, PSA, Renault, Technische Universit¨at M¨unchen, Univerisit´e Paris XIII, Universit`a di Torino.

Daniele Theseider Dupr´e

Dip. di Scienze e Tecnologie Avanzate Universit`a del Piemonte Orientale Corso Borsalino 54 I-15100, Alessandria, Italy

dtd@mfn.unipmn.it

in the garage), is used to solve a set of significant cases (that is, at least a good sample of the cases that have to be faced on-board). The solution includes the set of candidate diagnoses and, more important, the recovery action(s) that should be performed on-board in that case.

• AF Cases and the corresponding recovery actions are used to generate a compact on-board diagnostic system. Specifically, in [Cascio et al., 1999] decision trees are generated, using an algorithm based on ID3 [Quinlan, 1986].

However, the system has a major limitation: even if some form of reasoning on the dynamics is used to achieve proper diagnostic results, all abnormal data are considered relative to a single snapshot, and therefore no temporal information is associated with the data in the table used by the compiler and then in the decision tree.

In this paper the decision tree generation approach is extended to take into account temporal information associated with the model, with the manifestations of faults and with the decisions to be made. Using the additional power provided by temporal information requires however new solutions for organizing and compiling the decision trees to be used on board.

The essential idea for generating small decision trees in the temporal case is that in some cases there is nothing better than waiting, in order to get a good discrimination, provided that safety and integrity of the physical system is kept into account.

2 Temporal diagnostic decision trees

Defining and compiling decision trees is conceptually simple in the atemporal case. Each node of the tree corresponds to an observable (e.g., a sensor reading) and has several descendants depending on the qualitative values associated with the sensor. The leaves of the tree correspond to actions that can be performed on board.

New opportunities and problems have to be faced in the temporal case. Each fault leads to a different evolution across time, and, for some fault, the appropriate recovery action must be performed within a given time to avoid unacceptable consequences as regards the car integrity and, most importantly, safety.

In the definition of the decision tree, temporal information can be exploited for discriminating faults based on temporal information, e.g. faults that lead to the same manifestations with different timing. Suppose, for example, that faults BY BD and BY BE both produce an abnormal value for sensor D7 BD , but BY BD produces an abnormal value for sensor D7 BE after time CS BD while BY BE produces the same abnormal value for D7 BE after time CS BE BQ CS BD . The two faults cannot be distinguished in an atemporal decision tree and, in general, without temporal information On the contrary, in the temporal case we can build a tree like the one in figure 1. After observing an abnormal value for D7 BD , the system waits for CS BD units of time, and then makes a decision, depending on whether at that time an abnormal value for D7 BE is read. However, this behavior is only reasonable in case the recovery actions associated with faults BY BD and BY BE allow the system to wait for CS BD more units of time after fault detection (i.e. in this example, observing an abnormal value for D7 BD ).

Timing information then leads to the definition of temporal diagnostic decision tree, i.e. a decision tree such that:

• AFEach node is labelled with a pair CWD7BN D8CX, where D7 is the name of an observable and D8 is a time delay.
• AFThe root corresponds to the sensor used for fault detection; in case more than one sensor may be used for such a purpose, there are multiple decision trees, one for each sensor.
• AFEach edge is labelled with one of the qualitative values of the sensor associated with its starting node.
• AFLeaves correspond to recovery actions.

The tree is used as follows:

1. Start from the root when a fault is first detected.
2. When moving to a node CWD7BN D8CX, wait for D8 units of time, then read sensor D7 and move to the descendant of D7 corresponding to the observed value for the sensor.
3. When moving to a leaf, perform immediately the corresponding recovery action.

In the following sections we present how a temporal diagnostic decision tree can be generated automatically. Before describing that, however, we must discuss the assumptions we make as regards the underlying model-based diagnostic approach.

3 The underlying model-based approach

As regards the temporal dimension, the architecture in [Cascio et al., 1999] relies on either static diagnosis (i.e. diagnosis based on a static model, or based on reasoning in a single state of the system) or a limited form of temporal diagnosis

(see [Brusoni et al., 1998] for a general discussion on temporal diagnosis) where the model of time is purely qualitative (a sequence of qualitative states), abnormal manifestations are assumed to be acquired in a single snapshot D8 and therefore matched with a single qualitative state, and normality of observations in times earlier than D8 is used to rule out diagnoses which predict abnormal manifestation that were not detected (see [Panati and Theseider Dupr´e, 2000]).

What is not exploited is the ability of discriminating among explanations for the observations at snapshot D8 using information acquired at subsequent snapshots, which is what we intend to exploit in the present paper, to extend the approach to other forms of temporal models and other notions of temporal diagnosis.

In particular, we consider models of temporal behavior in which temporal information is associated with the relations describing the behavior of a device. We do not make specific assumptions on the model of time, even though, as we shall see in the following, this has an impact on the cases which can be considered for the tree generation. Similarly, we do not make assumptions on the notion of diagnosis being adopted (in the sense of [Brusoni et al., 1998]). This means that the starting point of our approach is a table containing the results of running the model-based diagnostic system on a set of cases, (almost) independently of the model-based diagnostic system used for generating the table.

However, some discussion is necessary on the type of information in the table. In the static case, with finite qualitative domains, the number of possible combinations of observations is finite, and usually small, therefore there are two equivalent ways of building the table:

1. Simulation approach: for each fault BY, we run the model-based system to predict the observations corresponding to BY .
2. Diagnostic approach: we run a diagnosis engine on combinations (all relevant combinations) of observations, to compute, the candidate diagnoses for each one of these cases.

In either case, the resulting decision tree contains the same information as the table; if, once sensors are placed in the system, observations have no further cost, the decision tree is just a way to save space and speed up table lookup.

In the temporal case, if the model of time is purely qualitative, a table with temporal information cannot be built by prediction, while it can be built running the diagnosis engine on a set of cases with quantitative information: diagnoses which make qualitative predictions that are inconsistent with the quantitative information can be ruled out. Of course, this cannot in general be done exhaustively, even if observations are assumed to be acquired at discrete times; if it is not, the decision tree generation will be really learning from examples.

Thus a prediction approach can only be used in case the temporal constraints in the model are precise enough to generate predictions on the temporal location of the observations (e.g., in case the model included quantitative temporal constraints), while a diagnostic approach can be generate also in case of weaker (qualitative) temporal constraints in the model.

As regards the observations, we consider the general case where a set of snapshots is available; each snapshot is labelled with the time of observation and reports the value of the sensors (observables) at that time. This makes the approach suitable for different notions of time in the underlyingmodel and on the observations (see again the discussion in [Brusoni et al., 1998]).

We require that some knowledge is available on the recovery actions that can be performed on-board:

• AFA recovery action CP CX is associated with each fault BY CX .
• AFA cost CRB4CP CX B5 BE IR is associated with each recovery action CP CX , due to e.g. the reduction of functionality of the system as a consequence of the action.
• AFA partial order AU is defined on recovery actions: CP CX AU CP CY in case CP CY is stronger than CP CX , in the sense that all recovery effects produced by CP CX are produced also by CP CY . This means that CP CY also recovers from BY CX although it is stronger than needed. For example, for two recovery actions in the automotive domain [Cascio et al., 1999]: reduce performance AU limp home as the latter corresponds to a very strong reduction of car performances which simply allows the driver to reach the first workshop. Actions define a lattice, whose bottom corresponds to performing no action and whose top corresponds to the strongest action, e.g., stop engine in the automotive domain.
• AFCosts are increasing wrt AU, that is, if CP CX AU CP CY then CRB4CP CX B5 BO CRB4CP CY B5.
• AFActions CP BD and CP BE can be combined into BT BP mergeB4CP BD BN CP BE B5 defined as follows:

The merge can be extended to compound actions:

mergeB4BT BD BNBT BE B5 BP B4BT BD CJ BT BE B5 D2 CUCP CX BE B4BT BD CJ BT BE B5 CY BLCP CY BE B4BT BD CJBT BE B5 s.t. CP CX AU CP CY CV.

A simple action can be seen as a special case of compound action, identifying CP CX with CUCP CX CV. In general BT BD BN BT BE AM mergeB4BT BD BN BT BE B5.

• AFFor a compound action BT the cost is such that D1CPDC CP CX BEBT CUCRB4CP CX B5CV AK CRB4BTB5 AK  CP CX BEBT CRB4CP CX B5.

A merge of actions must be performed in case of a multiple fault or when alternative preferred (e.g. minimal, or minimum cardinality) diagnoses cannot be discriminated, either because no further sensors are available or there is no time to get further sensor readings.

This actions model is valid only if actions are not faultdependent, e.g. their cost does not depend on the actual fault(s) in the system. We will discuss this points in section 5.

We now have all the elements to describe the structure of the table in which we collect the results of applying the model-based system on the set of simulated cases:

• AFThe table has one row for each case.
• AFEach row contains:
• the set of observations corresponding to the case. In particular, for each observable CB CY we have the value in each snapshot (this will be denoted as CB B4CXBND8B5 CY where D8 identifies the snapshot and CX the row of the table);
• the recovery action to be performed and its cost. This is determined by considering the set of candidate diagnoses for the case under examination and, in case of multiple faults or multiple candidate diagnoses, merging the recovery actions associated with the individual faults occurring in the diagnoses;
• -a probability which corresponds to the prior probability of the candidate diagnoses associated with the row;
• the maximum number of snapshots that can be used for completing the diagnosis.

This table is the input to the algorithm for generating the temporal diagnostic decision tree.

4 Generating the tree

An important issue to be considered for the generation of decision trees is optimality. A standard decision tree is said to be optimal (with respect to the set of decision trees solving a particular decision problem) if its average depth is minimal. The ID3 algorithm exploits the quantity of information (or its opposite, entropy) carried by an observation as a heuristic to build a decision tree that is, if not optimal, at least good enough.

For temporal diagnostic decision trees depth is only a secondary issue, since the ability to select a suitable recovery action in the available time becomes more important. A suitable action is one that has the proper recovery effects, but that is not more expensive than necessary. Each time two actions are merged (because of lack of discrimination), we end up with performing an action that could have a higher cost than needed. An expected cost can be associated with a tree.

Definition. Let B4CCB5 denote the set of leaves of a tree CC, CAB4CCB5 the set of candidate rows the tree discriminates, CAB4D0B5 the set of candidate rows associated with a leaf D0 BE B4CCB5, BTB4D0B5 the recovery action for D0, and B4D0B5 the probability of D0. In particular we have

Then the expected cost CGB4CC B5 of CC can be defined as:

Since we are interested in building a tree that minimizes expected cost, some more considerations on costs are worth being made. For any tree CC , the set BWB4CCB5 BP CUCAB4D0B5CYD0 BE B4CCB5CV is a partition of CAB4CCB5. It is easy to see that if two trees CC BD

and CC BE are such that BWB4CC BD B5 is a subpartition of BWB4CC BE B5 then CGB4CC BD B5 AK CGB4CC BE B5. Intuitively, CC BD has a higher discriminating power than CC BE , and therefore it cannot have a higher expected cost. It follows that if we build the tree with highest discriminating power we automatically build a tree with minimum expected cost. However, maximum discriminating power is a relative, concept: it ultimately depends on the data available in the table from which the tree is built. Let us denote with
the set of all pairs CWobservableBN timeCX in the initial table. To fully exploit the discriminating power in
, a tree could be based on all the pairs in it. The partition induced on the set of candidates by such a tree is a subpartition of that induced by any other tree that makes use of pairs in
. Therefore the cost of this tree is the minimum achievable expected cost.

Unfortunately this is not the tree we want to build, since as well as minimum expected cost it has maximum depth. The algorithm we propose builds a tree with minimum expected cost while trying to minimize its depth, using the criterion of minimum entropy. The algorithm is essentially recursive. Each recursive call is composed of the following steps: (i) it takes as input a set of candidates, represented by table rows; (ii) it selects a pair CWobservableBN timeCX for the current tree node; (iii) it partitions the set of rows accordingly to the possible values of the selected attribute; (iv) it generates a child of the current node for each block of the partition; (v) it performs a recursive call on each child.

The difficult step is (ii). First of all, let us notice that, differently from what happens in ID3, the set of pairs from which we can choose is not the initial set
, nor it is the same in all recursive calls. The set of available pairs depends on the current snapshot - a tree node cannot consider a snapshot previous to that of its parent - and on the deadline, which in turns depends on the set of candidates. Choosing a pair with a time delay greater than BC for the current node means making all snapshots between the current one and the selected one unavailable for all the descendants of this node. A pair may be discarded that was necessary in order to attain the minimum expected cost. Of course, the higher the time delay, the higher the risk.

Step (ii) can then be divided in two substeps: first, determine the maximum time delay that does not compromise the minimum expected cost; second, select the pair with lowest entropy between those with a safe delay. In order to determine if a particular delay is safe, we must associate with each possible delay D8 the minimum expected cost AVB4D8B5 that it is possible to obtain after selecting it. Then, since a BC-delay is safe by definition, the delays D8 with AVB4D8B5 BP AVB4BCB5 can be declared safe.

The easiest way to compute AVB4D8B5 is to build the tree that considers all the pairs still available after D8, as in the definition of minimum achievable expected cost. Since we only need the leaves, and not the whole tree, we can simply consider the partition induced on the set of candidates by the combination of all available pairs. We will refer to this partition as the global partition for D8.

Doing this for all delays can be computationally expensive; luckily there is a more efficient way to obtain the same result. If we consider two possible delays D8 BD BN D8 BE with D8 BD BO D8 BE we have that the set of available pairs for D8 BE is a subset of that for D8 BD .

This means that, if we compute first the global partition for D8 BE , we can build the global partition for D8 BD starting from that of D8 BE and considering only the extra pairs available for D8 BD . If we apply this backward strategy to the set of all possible delays, we immediately see that we can compute AVB4D8B5 for all D8 while computing AVB4BCB5. In this way we will be able to determine which delays are safe and which are not looking only once at the set of pairs that are initially available. If we denote by  the number of rows in the table, by CB the number of sensors, by CC the number of snapshots, and by CZ the number of values that each sensor can assume, we have that in the worst case this algorithm behaves as B4  BE A1CC A1CB CZ B5. The algorithm as presented in this paper is an improvement, in terms of efficiency, of the original version we described in [Console et al., 2000].

4.1 The algorithm

The algorithm for compiling the tree is reported in figure 2. To start the algorithm up, the sensors used for fault detection must be determined, since a separate tree will be built for each of them. Notice that each tree covers a subset of cases, depending on which abnormal measurement activates diagnosis.

Given the sensor used as the root of the tree, the values the sensor can assume induce a partition on the set of cases, and a subtree must be generated for each block of the partition. This is done in the TEMPORALID3 function, that takes in input a set of cases CA and returns a temporal decision tree along with its expected cost.

In order to express delays instead of absolute times, TEMPORALID3 needs a notion of current snapshot that varies from one call to another, and that corresponds to the last snapshot considered. More precisely, since each call to TEMPORALID3 builds a subtree, the current snapshot is the one in which the parent nod `Es observation takes place. However, since the delay between fault occurrence and fault detection depends on which fault is supposed to occur, each candidate D6 BE CA has to maintain a pointer to its own current snapshot; we denote this pointer by ASB4D6B5. At the beginning, for each D6, ASB4D6B5 is set to the snapshot at which the fault (or combination of them) described by D6 is detected.

Moreover, we denote by B4D6B5 the prior probability of D6, by CCB4D6B5 its deadline for a recovery action, and by BTB4D6B5 its recovery action (either simple or compound).

Let us briefly describe TEMPORALID3. First, it considers all those situations in which it should simply return a tree leaf. This happens when: (i) the input set does not need further discrimination, that is, all the cases in CA have the same recovery action; or (ii) in the time left for selecting an action there are no more discriminating pairs (a particular case is when there is no time left at all). This means that it is not possible to distinguish between the candidates in CA and therefore the selected recovery action is the merge of CUBTB4D6B5 CY D6 BE CACV.

If none of the previous cases holds, TEMPORALID3 uses the backward strategy described earlier in order to compute, for each delay D8, the expected cost AVB4D8B5, thus finding out which delays are safe. It exploits three subfunctions: PAIRS, SPLIT and EXPECTEDCOST, which, for the sake of conciseness, we describe without providing their pseudocode.

function TEMPORALID3B4CAB5 returns a pair B4TreeBN CostB5 begin if BLBT BM BKD6 BE CAB4BTB4D6B5 BP BTB5 then CUall candidates in CA have the same recovery actionCV return B4Tree BP CWBTCXBN Cost BP CRB4BTB5B5; CC AWA0 minCUCC B4D6B5 A0 ASB4D6B5 CY D6 BE CACV; CUcurrent deadlineCV BTAWA0 mergeCUBTB4D6B5 CY D6 BE CACV; if CC BO BC then CUno time leftCV return B4Tree BP CWBTCXBN Cost BP CRB4BTB5B5; CUBackward strategy:CV DI D8 AWA0 undefined; AV AWA0 undefined; A5 AWA0 CUCACV; for each D8 in CUCCBN CC A0 BDBN BM BM BM BN BCCV do begin  AWA0 PAIRSB4D8BN D8B5; if  BIBP BN then begin do begin A5 AWA0 SPLITB4A5BN B5; for each AP BE A5 do begin CCB4APB5 AWA0minCUCCB4D6B5 A0 ASB4D6B5 CY D6 BE APCV;  AWA0 PAIRSB4CC B7 BDBN CC B4APB5B5; end while  BIBP BN; AV new AWA0 EXPECTEDCOSTB4A5B5; if B4AV is undefinedB5 or B4AV new BO AVB5 then begin AV AWA0 AV new; DI D8 AWA0 D8; end end if DI D8 is undefined then CUno more discriminating pairsCV return B4Tree BP CWBTCXBN Cost BP CRB4BTB5B5; CWD3 ok BN D8 ok CX AWA0 the pair with minimum entropy between those with BC AK D8 AK DI D8; for each D6 BE CA do CUUpdate the value of the current snapshot for each candidateCV D8B4D6B5 AWA0 D8B4D6B5 B7 D8 ok; A5 AWA0 SPLITB4CUCACVBN CUCWD3 ok BN D8 ok CXCVB5; for each AP BE A5 do CUBuild the subtreesCV B4SubtreeB4APB5BN CGB4APB5B5 AWA0 TEMPORALID3B4AP CX B5; return B4Tree BP CWCWD3 ok BN D8 ok CXBN CUSubtreeB4APB5 CY AP BE A5CVBN Cost BP  APBEA5  D6BEAP  B4D6B5  D6BECA  B4D6B5 A1 CGB4APB5B5; end.

PAIRS returns all the pairswith a delay between the specified values.

SPLIT splits an existing partition using the set of pairs in input. A partition block can be split by a pair only if the pair can provide a value for all the candidates in the block. This is important since some pairs are beyond the deadline and thus do not provide a value for all the candidates.

EXPECTEDCOST computes the expected cost associated with a partition. The partition can be regarded as a set of tree leaves, and therefore it is possible to apply the definition of expected cost.

When we compute AVB4D8B5, as a result of the backward strategy we can exploit the partition we created for a delay of D8 B7 BD. First of all we consider the "new" pairs that are available at snapshot D8, that is, those pairs returned by PAIRSB4D8BN D8B5. However it may be that for some blocks of the newly created partition there are some more pairs available, because these smaller blocks have a looser deadline than the older ones. Therefore we keep on (i) creating the new partition; (ii) computing the new deadline for each block; (iii) adding the new pairs due to the new deadline, if any. This is repeated until there are no more pairs to add.

After determining the maximum safe delay, denoted by DI D8, the algorithm selects the pair with minimum entropy among those with a delay D8 such that BC AK D8 AK DI D8. The selected pair is denoted by CWD3 ok BN D8 ok CX.

Finally, TEMPORALID3 updates the current snapshot pointers, partitions CA according to the selected pair, and calls recursively TEMPORALID3 on each block of the partition.

4.2 An example

Let us consider a simple example. There are three sensors, CB BD , CB BE and CB BF ; each one of them can have five possible values: normal (n), high (h), low (l), very low (v) and zero (z). Possible recovery actions are denoted by CP BD , CP BE , CP BF , CP BG , with the following partial order: CP BG AU CP BE AU CP BD , CP BG AU CP BF AU CP BD . The only compound action that can arise from a merge operation is CUCP BE BN CP BF CV and we assume its cost is CRB4CP BE B5B7CRB4CP BF B5 BP BEBC. We assume that the faults associated with the four rows have the same prior probability. Initial data are shown in table 1.

We will build the tree whose root is sensor CB BE ; this is the only tree to be built since each fault in the table is first detected on CB BE . If, for example, cases CA BD and CA BE were first detected on CB BE while CA BF and CA BG on CB BD , we would have had to build two separate trees, the first with root CB BE dealing with CA BD BN CA BE and the second with root CB BD dealing with CA BF BN CA BG .

The root of the tree is thus CWCB BE CX but it does not partition the set of candidates, so we still have CA BP CUCA BD BNCA BE BNCA BF BNCA BG CV, and ASB4CA CX B5 BP BD for CX BP BDBN BEBN BFBN BG. In this example all faults show themselves with the same delay wrt fault occurrence; this is the reason why all ASB4CA CX B5s have the same value. In a different situation each would point to the first snapshot for which sensor CB BE has a non-normal reading. Diagnosis must be completed by snapshots BG, corresponding to a delay of BF snapshots. Using the backward strategy we first find out that with a delay of BF we would not be able to discriminate CA BD and CA BE , and therefore AVB4BFB5 BP BHBF. On the other hand, if we consider a delay of BE we are able to discriminate all faults, thus AVB4BCB5 BP AVB4BDB5 BP AVB4BEB5 BP BFBCBMBH. The minimum entropy criterion prompts us to choose the pair CWCB BE BN BECX, and we obtain the partition CA BD BP CUCA BD CVBN CA BE BP CUCA BE BN CA BF CVBN CA BF BP CUCA BG CV. For CA BD and CA BF the diagnosis is completed and the algorithm returns respectively CWCP BD BN BDBCBCCX and CWCP BG BN BECX. For CA BE we have that the deadline is moved, and we can choose between delays BCBN BD and BE. However it is immediately clear that AVB4BCB5 BP AVB4BDB5 BP AVB4BEB5 BP BDBC; moreover all available pairs have the same entropy (quite obvious since there are only two candidates left). We can choose for example CWCB BE BN BDCX and the recursive calls return CWCP BE BN BDBCCX and CWCP BF BN BDBCCX.

The resulting decision tree is shown in figure 3.

5 Conclusions

In this paper we introduced a new notion of diagnostic decision tree that takes into account temporal information on the observations and temporal constraints on the recovery actions to be performed. In this way we can take advantage of the discriminatory power that is available in the model of a dynamic system. We presented an algorithm that generates temporal diagnostic decision trees from a set of examples, discussing also how an optimal tree can be generated.

The automatic compilation of decision trees seems to be a promising approach for reconciling the advantages of modelbased reasoning and the constraints imposed by the on-board hardware and software environment. It is worth noting that this is not only true in the automotive domain and indeed the idea of compiling diagnostic rules from a model has been investigated also in other approaches (see e.g., [Darwiche, 1999; Dvorak and Kuipers, 1989]). [Darwiche, 1999], in particular, discusses how rules can be generated for those platforms where constrained resources do not allow a direct use of a model-based diagnostic system.

Future work on this topic is mainly related to recovery actions. While developing the algorithm, we assumed to have a model of actions and costs where actions are not faultdependent (see section 3). Modeling such a situation would mean to introduce (a) a more sophisticated cost model where the cost of an action can depend on the behavioral mode of some system components, and (b) a more detailed deadlines model, that expresses the cost of not meeting a deadline. Notice that this does not affect the core part of the algorithm, i.e. the one that computes the expected costs related to different choices. However having fault-dependent costs requires a different criterion for stopping the discrimination process and building a tree leaf, since meeting the deadline becomes a matter of costs and benefits rather than a strict requirement.

Some other generalizations are more challenging, since they affect also the core part of the algorithm. As an example, we are currently investigating how to integrate actions and candidate discrimination, e.g. including probing actions (which modify the system state) and sequences of actions interleaved with measurements.