Raymond A Marie
email: marie@irisa.fr.

Reduced Dependent Ordered Binary Decision Diagrams: An Extension of ROBDDs for Dependent Variables

Keywords: ROBDDs, Binary decision diagrams, Analytical models, Fault tolerant systems, Correlation, Failure analysis, Nonindependent component analysis ROBDDs, diagramme de décision binaire ordonné, système tolérant aux fautes, analyse de composants dépendants, corrélation

In this report, we presented an extension of robdds that is able to accommodate certain dependencies among their (Boolean) variables. In particular, this extension shows evidence of being applicable to evaluating the dependability (reliability, availability) of systems whose structures are representable by a Boolean function. This extension consists of three main parts. The first part is the notion of a phratry with its associated new definitions and constraints. The second part consists of the adaptation and complementation of the original rules used in the construction of robdds. The final part concerns additional custom-made steps needed to determine the functional valuations that are specific to solving measure in question.

Introduction

A Binary Decision Diagram (bdd) is a data structure that is used to represent a Boolean function on a computer. Its advantage is that it is a compressed representation permitting the execution of operations without any decompression step. The basic idea underlying the notion of a bdd is the Shannon decomposition formula of a Boolean function F (x, y, z, ...): F (x, y, z, ...) = x.F x=true (x, y, z, ...) + x.F x=f alse (x, y, z, ...) Recurrent use of this formula permits representation of a Boolean function as a binarytree with only two types of leaf nodes corresponding respectively to the Boolean values true and false, each internal node being labeled with a Boolean variable.

The success of this approach is due to the fact that a theoretical binary-tree can be transformed into a rooted, directed, acyclic graph. In turn, this graph can be reduced through recurrent use of two fundamental rules. This reduction results in a much simpler data structure that still represents the initial Boolean function. This reduction works only if the original bdd is ordered, i.e., if the different Boolean variables appear in the same order on all the paths going from the root to the leaves. This condition is not restrictive and such a bdd is called an Ordered bdd. The final graph is normally called a Reduced Ordered Binary Decision Diagram (robdd), although many people just say bdd when they refer to the latter.

The bdd originated in logic studies for the manipulation and computation of logical expressions and were used very early in the domain of switching circuit design. Initial efforts were those of Lee [START_REF] Lee | Representation of Switching Circuits by Binary-Decision Programs[END_REF] and Akers [START_REF] Sheldon | Binary Decision Diagrams[END_REF], followed by those of Bryant [START_REF] Bryant | Graph-based algorithms for Boolean function manipulation[END_REF] [START_REF] Bryant | Symbolic Boolean manipulation with ordered binary-decision diagrams[END_REF] who emphasized the use of a bdd as a fundamental data structure. Then came the applied domains of Computer Aided Design for VLSI and of reliability (either from Reliability Block Diagrams, or directly from Boolean expressions, or from Fault Tree representations) ( [START_REF] Doyle | Dependability Assessment using Binary Decision Diagrams[END_REF], [START_REF] Bouissou | An Ordering Heuristic for Building Binary Decision Diagrams from Fault Trees[END_REF], [START_REF] Zang | A BDD-Based Algorithm for Reliability Evaluation of Phased Mission System[END_REF]).

A limitation of this approach is the a priori condition that the different Boolean variables are mutually independent. Very often, this assumption is reasonable, e.g., when working in the domain of pure logic. But in certain practical applications such as the evaluation of system dependability, this condition may not be acceptable.

Quite often, in dependability studies, Boolean variables represent states of hardware/ software elements (such as "functioning/not functioning"). In such studies, probabilities are affected to the two possible values of the variables: P(x i = true) = 1-P(x i = f alse).

For different reasons, complex systems may contains several groups of correlated individual elements in the sens of dependability properties. In that case, P(x i | x j ) = P(x i ) and we cannot valuate the outgoing edges of node labeled by Boolean x i if we don't know the value of Boolean x j . But respectively, since (P(x i | x j ) = P(x i )) ⇒ (P(x j | x i ) = P(x j )), we cannot valuate the outgoing edges of node labeled by Boolean x j if we don't know the value of Boolean x i . In that case, we are facing a deadlock when trying to use the classical bdd approach. For small populations of correlated elements, we may determine a personalized model for the specific system. But the problem stays for coping with several groups of arbitrary size and with arbitrary location of the elements in the structure of the system. Moreover, in many situations, the joint probability distribution P(x i , x j ) depends on a (time) parameter and we have to consider probability distribution functions such as P(x i , x j , t).

The purpose of this paper is to present an extension of the robdd concept so as to handle dependencies such as this. One of the characteristics of the proposed extension is that all the components sharing a dependent behavior need to be considered in a proper suborder such that no other component can be included inside this proper suborder. In addition, the two traditional rules used to reduce a classical robdd will need to be extended in order to cope with the existence of correlated failures.

The paper is organized as follows, beginning in Section 2 with some background concerning robdds and how they differ from the proposed extension. Section 3 is then devoted to the presentation of the extension, per se. In turn, Section 4 describes an example illustrating its application, followed by a concluding section that summarizes the paper's contribution.

Background

The purpose of this section is two-fold. First, it provides a brief review of robbds for those who are not familiar with this concept. Secondly, it aims to help the reader understand the difference between the now classic robdd and the extension proposed herein, referred to as an rdobdd.

Except for the leaves, each node of a bdd has an out-degree of two, where the two outgoing edges are called the low edge and the high edge of the node. A function low(u) (respectively high(u)) gives the name of the node connected to node u by the low-edge (respectively. high-edge).

It is important to understand that in a bdd, each node corresponds to a Boolean function defined by the subtree initiated from that node. Let us consider a node n i labeled by a Boolean variable x j . The Boolean function F (n i ) associaded with node n i can be expressed in terms of the Boolean functions asociated with the two successor nodes in the following way:

F (n i ) = x j .F (high(n i )) + x j .F (low(n i )) F (high(n i )) is obtained from F (n i
) by assigning the Boolean variable x j to the true value, i.e., F (high(n i )) = F x j =true (n i ). Similarly, F (low(n i )) = F x j =f alse (n i ). With respect to node n i , the node connected to it by its high-edge (respectively, low-edge) is called its high node (respectively low-node).

The reduction of the binary tree is accomplished by applying the following two rules: R1: Merge any isomorphic subgraphs. R2: Eliminate any node whose two children are isomorphic. This set of reductions transforms the binary tree into a rooted directed acyclic graph that still represents the original Boolean function. Rule R1 preserves a unique representation of a unique Boolean sub-function. Rule R2 simply exploits the fact that if

F (high(n i )) = F (low(n i )), then F (n i ) = F (high(n i )) = F (low(n i )
) so that the node n i can be removed from the graph. These two rules are applied repeatedly as long as they're Inria applicable. Also, in graphical representations of the binary tree or of the rooted directed acyclic graph, the high-edge is drawn with a solid line while a dotted line is used for the low-edge. A nice property of an robdd is that any given Boolean function has, for a given ordering of the variables, a unique robdd (referred as its canonical form).

But the practical interest in obdds relies on the existence of efficient algorithms that have been implemented in software packages. These are now available within the scientific community and several of them can be found on the Web (see, for example, [START_REF] Somenzi | CUDD: Colorado University Decision Diagram package[END_REF], [START_REF] Lind-Nielsen | BuDDy: A BDD package[END_REF], [START_REF]Biddy: multi-platform academic BDD package[END_REF], [START_REF] Biere | The ABCD package, Johannes Kepler Universität[END_REF], [START_REF]The Berkeley CAL package[END_REF], [START_REF]The JavaBDD package[END_REF], [START_REF]The Vahidi's JDD package[END_REF]).

However, it is well known that the resulting robdd depends on the chosen ordering of the variables and, since the number of possible orderings of a set of n variables equals n!, the determination of a "good" variable order (where the number of nodes is reasonably close to optimal) is still an open problem (see [START_REF] Bollig | Improving the Variable Ordering of OBDDs Is NP-Complete[END_REF], for example). Nevertheless, some heuristic methods, based on particular types of applications, already exist ( [START_REF] Minato | Shared Binary Decision Diagram with Attributed Edges for Efficient Boolean Function Manipulation[END_REF], [START_REF] Fujita | On Variable Ordering of Binary Decision Diagrams for the Application of Multi-level Logic Synthesis[END_REF]). In addition, there are some recent studies that employ dynamic reordering, based for example on symmetry detection and shifting ( [START_REF] Kettle | An Anytime Algorithm for Generalized Symmetry Detection in ROBDDs[END_REF]).

Let us now examine an application of this methodology to the simple series/parallel reliability block diagram given by Figure 1. This reliability block diagram means that the system is able to execute it function only if components c 1 and c 2 are not broken or/and if components c 3 and c 4 are not broken. Introducing the four Boolean variables x i , i = 1, ..., 4, where x i represents the state of component c i , allows us to write the corresponding Boolean function characterizing the reliability of the system: F (x 1 , ..., x 4 ) = x 1 .x 2 + x 3 .x 3 . Then, from this Boolean function, we obtain the ordered bdd by recurrent application of Shannon's decomposition theorem to the ordered sequence x 1 < x 2 < x 3 < x 4 . This ordered bdd is shown in Figure 2. Then, using rule R1, we first merge all the isomorphic subgraphs which appear in this ordered bdd; the resulting graph is illustrated by Figure 3. In this figure, we see that there are several nodes whose two children are isomorphic. Using rule R2, we eliminate these nodes. This action produces the graph given by Figure 4. The last step consists of merging, respectively, all the 0-terminal nodes and all the 1-terminal nodes. This last step could have been made earlier (by application of rule R1) but we postponed this reduction for the sake of legibility of the overall process. The resulting robdd is shown in Figure 5 (for the order x 1 < x 2 < x 3 < x 4 ).

In many applications and, in particular, dependability evaluations, we do not use the 0-terminal node and the ingoing edges of this node. Consequently, we cut the "dead" part

0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 1 x 1 x 2 x 2 x 3 x 3 x 3 x 3 x 4 x 4 x 4 x 4 x 4 x 4 x 4 x 4
Figure 2: Ordered bdd of the example for the order of the robdd in order to keep only what we call the "positive" robdd. This gives us the graph shown in Figure 6. We could have also been tempted to call this final graph a Zero-Suppressed robdd but this term already exists for an important type of data structure referred to as a zdd. The latter was introduced by S. Minato [START_REF] Minato | Zero-suppressed BDDs for set manipulation in combinatorial problems[END_REF] and is able to manipulate families of sets.

x 1 < x 2 < x 3 < x 4 0 1 0 1 x 1 x 2 x 2 x 3 x 3 x 4 x 4 x 4
To emphasize the fact that the resulting robdd depends on the chosen ordering of the variables, Figure 7 depicts the positive robdd of the example for the order x 1 < x 3 < x 2 < x 4 . Comparing it with the one in Figure 6, we see that it has two extra nodes. Note, however, that all the Boolean expressions obtained with different variable orders correspond to the same Boolean function. Most of the time in dependability applications, the edges of a positive robdd are valued by elementary probabilities. These probabilities correspond generally to reliabilities or to Inria availabilities. From the point of view of robdds, these individual values are trivial since they consist of input data associated with an outgoing edge of a node and the name of the variable labeling that node. This remains so, even if their determination in a previous problem was not trivial! For our simple series/parallel example, if r i denotes the reliability of component c i , the edge-valued robdd is shown in Figure 8 for the order 1 < x 2 < x 3 < x 4 . Then, starting from the 1-terminal node, we compute the partial reliability function at each node, respecting the inverse order since we cannot compute the function of one node before treating its successors. For our simple example, we get, after a final simplification, the reliability function as illustrated in Figure 9:

R(x 1 , x 2 , x 3 , x 4 ) = r 1 r 2 + r 3 r 4 -r 1 r 2 r 3 r 4
Of course, the positive robdd associated with the order x 1 < x 3 < x 2 < x 4 yields the same answer, again after a final simplification.

Let us add that, for several application domains where we are only interested in positive robdds, we could use an additional initial rule R0: "Eliminate the dead sub-trees," i.e., those with only 0-terminal nodes as leaves. Indeed, in many dependability applications, it is easy to avoid constructing the majority of the dead sub-trees, just by examining the Boolean structure function which indicates whether the system under consideration is up or down as a function of the up-down values of its components. For example, a Boolean variable x j appears in all the monomials of the Boolean structure function if that component c j is in series in the reliability block diagram of the structure. Consequently, for any node n i labeled by the Boolean variable x j , the subtree issued from the low-edge is a dead subtree. Therefore, knowing the components in series in the reliability block diagram will allows us to avoid the construction the associated dead subtrees.

1 x 1 x 2 x 3 x 4 r 1 r 2 r 3 r 4 (1 -r 1 ) (1 -r 2 )
Figure 8: Positive robdd of the example for the order x 1 < x 2 < x 3 < x 4 , with elementary reliabilities labelling the edges.

1 x 1 x 2 x 3 x 4 r 1 r 2 r 3 r 4 (1 -r 1 ) (1 -r 2 ) [r 1 r 2 + r 3 r 4 -r 1 r 2 r 3 r 4 ] [r 2 + (1 -r 2 )r 4 r 3 ] [r 4 r 3 ] [r 4 ]
Figure 9: Positive robdd of the example for the order x 1 < x 2 < x < x 4 with answers (within brackets) from the bottom-up algorithm.

The extension

Due to the existence of subsets of Boolean variables corresponding to subsets of dependent components, we need to introduce new entities and new rules so as to evaluate dependability measures via a bdd approach.

We first distinguish a special set of Boolean variables as follows.

Definition 3.1. A phratry is a set of Boolean variables corresponding to a subset of mutually dependent components. Its cardinality equals that of the subset of components involved in a given dependence relation.

Accompanying this concept is the first of several additional rules called for by the extension.

Rule R0a(ordering rule): For every phratry, the chosen variable order must be such that the Boolean variables of a phratry are successive. Definition 3.2. If x i1 < x i2 < ... < x im corresponds to the chosen order for the Boolean variables of a phratry F i with cardinality m, the Boolean variable x i1 (respectively x im ) is called the eldest (respectively the benjamin) of the phratry. By extension, a node labeled by the eldest (respectively the benjamin) of the phratry is called an eldest node (respectively a benjamin node). Definition 3.3. In an obdd, a macro-edge is a labeled and valuated edge linking an eldest node to a successor node of a benjamin node belonging to the same phratry, and such that the benjamin node belongs to the subtree of the obdd associated with the considered eldest node.

Definition 3.4. The label of a macro-edge is the sequence of 0 and 1 values characterizing the sub-path connecting the eldest node to the successor node. The 0s and 1s corresponding Inria respectively to the low-edges and high-edges of the sub-path. Used when necessary, the valuation of the macro-edge corresponds to the dependability measure associated with the label (i.e., to the values of the Boolean variables of the phratry).

Note that for a given phratry, several macro-edges (with different labels) may have the same valuation.

In a classic robdd, the edges are valued by elementary dependability parameters, so that we don't really have to deal with these parameters during its construction. Here, however, determination of the valuations of the macro-edges is not trivial. For this reason, we will hereby refer to them as non-trivial valuations.

Rule R0b: Eliminate the "dead" sub-trees. This can be done by examining the corresponding Boolean structure function, as noted earlier with regard to constructing a positive obdd.

Rule R0c(phratry reductions): Replace the sub-paths of a phratry by macro-edges. Note that the application of rule R0c may transform the binary tree into a n-ary tree.

Due to the existence of the macro-edges, we now need to redefine the notion of isomorphic subgraphs. Definition 3.5. Two subgraphs are isomorphic if they have the same topology and the same nontrivial valuations (if any).

The next rule is identical to the former rule R1 but uses the new definition of isomorphic subgraphs.

Rule R1: Merge any isomorphic subgraphs, The former rule R2 cannot be stated as before, it needs to be adapted to existence of macro-edges.

Rule R2a: If the Boolean variable labeling the node does not belong to a phratry, then eliminate any node whose two children are isomorphic.

Rule R2b: If the Boolean variable labeling the node do belongs to a phratry, and if n, n ≥ 2, (outgoing) macro-edges are directed to the same subgraph, then replace the n macro-edges by a unique macro-edge whose valuation equals the sum of the valuations of the previous n macro-edges.

Example

In order to put the introduced rules in concrete form, let us consider a toy example: the series/parallel reliability block diagram shown in Figure 10. The components c 11 and c 12 are identical (as are the elements c 21 and c 22 ) but here the breakdown of one element may stress the other one. In the figure, the dependence between elements is indicated by means of a "D" and of zig-zag edges connecting the dependent elements. According to the figure, there are two phratries: {x 11 , x 12 } and {x 21 , x 22 }. We consider the ordered sequence x 5 < x 11 < x 12 < x 21 < x 22 (respecting rule R0a) and the corresponding ordered bdd whose interesting part is shown in Figure 11.

Following rule R0b, we eliminate the dead sub-trees in order to obtain the "positive" part of the bdd (cf. Figure 12). Next, we undertake the phratry reductions (rule R0c) consisting of three steps. The first one, very simple, is the replacement of the sub-paths of a phratry by macro-edges with their labels (cf. figure 13).

The second step is more complex since we have to assign the valuations of the macroedges. Each valuation corresponds to the value of the dependability measure associated with the label of each macro-edge. In our example, the dependability measure is the transient probability that the elements of the phratry are in the states characterized by the label of the macro-edge. Note that, because of symmetries, macro-edges with different labels may have the same valuation.

Let F 1 and F 2 respectively denote the two phratries {x 11 , x 12 } and {x 21 , x 22 }. Let v i (j), i = 0, 1, ... denote the different valuations associated with the different macro-edges of phratry j, j = 1, 2. Here, each valuation v i (j) corresponds to a transient probability. The determination of these different valuations needs to be done by someone familiar with dependability studies. Because the two elements of a phratry are here identical, the transient probabilities associated with labels 01 and 10 are also identical (for each of the two phratries). As a consequence, for phratry j, j = 1, 2, we use v 0 (j) to denote the valuation of macro-edge with label 11 (no down element) and v 1 (j) to denote the valuation of the two macro-edges associated with labels 01 and 10 (one down element) (cf. Figure 14).

The final step of the phratry reductions consists just in dropping the labels since they are no more useful (cf. Figure 15). x 5

v 0 (1) v 1 (1) v 1 (1) v 0 (2) v 0 (2) v 0 (2) v 1 (2) v 1 (2) v 1 (2) v 1 (2)
x 11 Then we are ready to apply rule 1 and merge the isomorphic subgraphs. On this example, two nodes labeled with the Boolean variable x 21 are the roots of two isomorphic subgraphs (note that the nontrivial valuations are identicalfor the two subgraphs). There also several isomorphic subgraphs consisting of just 1-terminal nodes. Applying rule 1 for all these isomorphic subgraphs, we have the graph given by Figure 16.

x 21 x 21 x 21 v 0 (1) v 1 (1) v 1 (1) v 0 (2) v 0 (2) v 0 (2) v 1 (2) v 1 (2) v 1 (2) v 1 (2)
We see that nodes labeled by Boolean variables x 11 and x 21 have isomorphic children but since these two Boolean variables are members of phratries, we use rule 2b to merge the (outgoing) macro-edges. We finally obtain the graph shown in Figure 17.

Finally, exploiting the graph of the rdobdd given by this figure, we get the reliability expression of the structure:

R(t) = r 5 (t) [2v 1 (1) (v 0 (2) + v 1 (2)) + v 1 (1) (v 0 (2) + 2v 1 (2))]
where the expressions of the non-trivial valuations are supposed to be obtained from the specialist.

Although no similar rule exists in regular robdd, it might be of interest, in the application domain of dependability evaluation, to add a final rule that would eliminate nodes with single ingoing and single outgoing macro-edges. This rule would be written as:

Rule R3: Eliminate any node with single ingoing and single outgoing macro-edges and take the product of the two nontrivial values as the nontrivial value of the new macro-edge.

Let us remark that, from a formal point of view, it would be necessary to enlarge the definition of the macro-edge in order to introduce this last rule, allowing the new object macro-edge to represent a set of states of more than one phratry. x 5

x 11

x 21 x 21 v 0 (1) v 1 [START_REF] Lee | Representation of Switching Circuits by Binary-Decision Programs[END_REF] v 1 (1) In this paper, we presented an extension of robdds that is able to accommodate certain dependencies among their (Boolean) variables. In particular, this extension shows evidence of being applicable to evaluating the dependability (reliability, availability) of systems whose structures are representable by a Boolean function. This extension consists of three main parts. The first part is the notion of a phratry with its associated new definitions and constraints. The second part consists of the adaptation and complementation of the original rules used in the construction of robdds. The final part concerns additional custom-made steps needed to determine the functional valuations that are specific to solving measure in question.

v 0 (2) v 0 (2) v 1 (2) v 1 (2) v 1 (2)
Despite the extra difficulty introduced by the existence of macro-edges and despite the extra effort in obtaining the functional valuation, we believe that this approach is potentially useful for several classes of applications.

c 1 c 2 c 3 c 4 Figure 1 :

 41 Figure 1: Series/parallel reliability block diagram

Figure 3 : 4 Figure 4 : 4 Figure 5 :

 34445 Figure 3: Merging isomorphic subgraphs

4 Figure 6 : 4 Figure 7 :

 4647 Figure 6: Positive robdd of the example for the order x 1 < x 2 < x 3 < x 4

Figure 10 :

 10 Figure 10: Series/parallel reliability block diagram of the example

Figure 12 :

 12 Figure 12: Eliminating of the dead sub-trees (rule R0b)

Figure 13 :

 13 Figure 13: phratry reductions -labeling (rule R0c)

Figure 14 :

 14 Figure 14: Phratry reductions -valuating (rule R0c)

Figure 15 :

 15 Figure 15: Phratry reductions -dropping the labels (rule R0c)

Figure 16 :Figure 17 :

 1617 Figure 16: Merging isomorphic subgraphs (rule R1)

RR n°7984

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399


Sławomir B Ąk

Duc-Phu Chau

Julien Badie

Etienne Corvee

Francois Brémond

Monique Thonnat

MULTI-TARGET TRACKING BY DISCRIMINATIVE ANALYSIS ON RIEMANNIAN MANIFOLD

Keywords: tracking, controller, re-identification, covariance matrix

This paper addresses the problem of multi-target tracking in crowded scenes from a single camera. We propose an algorithm for learning discriminative appearance models for different targets. These appearance models are based on covariance descriptor extracted from tracklets given by a short-term tracking algorithm. Short-term tracking relies on object descriptors tuned by a controller which copes with context variation over time. We link tracklets by using discriminative analysis on a Riemannian manifold. Our evaluation shows that by applying this discriminative analysis, we can reduce false alarms and identity switches, not only for tracking in a single camera but also for matching object appearances between non-overlapping cameras.

INTRODUCTION AND RELATED WORK

Tracking multiple objects in real world scenes involves dealing with strong occlusions, illumination changes, and cluttered or moving backgrounds. In dense scenarios, similar object appearance and complex interactions between different targets often result in incorrect trajectories with fragmentation and identity switches.

Recent studies focus on detection-based tracking methods as the result of significant improvement in object detection algorithms. These tracking methods detect objects of interest, and then associate detection responses using several cues, such as appearance, motion, size, and other geometrical constraints. Unfortunately, missed detections and inaccurate responses frequently occur, which provides misleading information to tracking algorithms. Thus, detection-based tracking must overcome these difficulties by using different tracking strategies.

In [START_REF] Xing | Multi-object tracking through occlusions by local tracklets filtering and global tracklets association with detection responses[END_REF], a two-stage approach (local and global) is presented. At the local stage, humans are tracked using body parts and particle filter. At the global stage, trajectories are associated by the Hungarian algorithm. The association cost matrix is computed using a simple appearance model based on color histogram, object height and velocity. A more complex appearance model is presented in [START_REF] Snidaro | Dynamic models for people detection and tracking[END_REF]. This appearance model discriminates between the object and the background by employing Haar wavelet features and local binary patterns. Features are combined using a boosting scheme, in which negative samples are generated by randomly selected background regions.

Many approaches either focus on tracking strategies using simple features as color histograms, or develop the appearance models discriminating a target from the background [START_REF] Collins | Online selection of discriminative tracking features[END_REF]. However, few studies have been undertaken to resolve ambiguities between the different targets. In [START_REF] Ch | Multi-target tracking by on-line learned discriminative appearance models[END_REF], the authors propose an online learning strategy which extracts appearance model for a set of targets in a sequence, to enhance the robustness of tracklet linking. This model is learned to maximize inter-tracklet variation whilst minimizing intra-tracklet variation.

For the last six years, the person re-identification problem has been the focus of intense research. Person reidentification can be seen as an extension of the tracking task to a multi camera scenario, in which the appearance of the same object registered in disjoint camera views has to be matched. Significant appearance changes, caused by variations in view angle, illumination and object pose, make the problem much more challenging than the single-camera tracking. As the person re-identification problem is particularly hard, the appearance models which tackle this problem should be able to handle difference in illumination, pose and camera parameters.

In this paper, we propose to take advantage of robust reidentification descriptor [START_REF] Bak | Multiple-shot Human Re-Identification by Mean Riemannian Covariance Grid[END_REF] for linking trajectories during the tracking procedure. We show that the re-identification descriptor which handles significant appearance changes across disjoint cameras, is able to merge tracklets extracted from a single camera.

This paper makes the following contributions:

• We propose to use Mean Riemannian Covariance Grid (MRCG) descriptor [START_REF] Bak | Multiple-shot Human Re-Identification by Mean Riemannian Covariance Grid[END_REF] for linking tracklets into longer ones to form the final tracking results in a single camera. The tracklets are obtained by a controller-based short-term tracking algorithm (Section 3).

• We present a new approach for discriminative appearance learning based on a sliding time window. Each tracklet is learned to highlight its distinctive features. We show that this technique can be easily applied to tracking systems, without extracting any additional reference dataset for learning (Section 4).

The overview of our technique is given in Section 2. Section 3 describes a short-term tracking controller. Then, in Section 4 a discriminative learning is presented. We evaluate our approach in Section 5 before discussing future work and concluding.

OVERVIEW OF OUR APPROACH

The proposed approach consists of 3 main steps: (1) object detection;

(2) short-term tracking and (3) linking trajectories using online discriminated appearances (see Figure 1). The first step, object detection, can be achieved by applying simple motion detection algorithms or specialized object detectors e.g. a human detector. In our case we combine both: motion and HOG-based detector [START_REF] Corvee | Body parts detection for people tracking using trees of histogram of oriented gradient descriptors[END_REF].

In the second stage, we generate tracklets associating detection responses by using a short-term tracking algorithm (Section 3). The short-term tracking is designed to produce reliable tracklets, by employing spatial, temporal and appearance descriptors. We develop a controller [START_REF] Chau | Dynamic and robust object tracking for activity recognition[END_REF], which assigns specific weights to these descriptors depending on the context of the video, thus generating reliable tracklets.

Finally, the last step of our approach consists in linking the tracklets using MRCG descriptor. We propose a linking strategy examining similarity between tracklets in a sliding time window. For each tracklet computed in sliding time window w, we build its MRCG representation. MRCG was designed to discriminate one appearance vs the reference appearances. We propose to discriminate each tracklet vs the rest of tracklets computed in given w. At that stage, the distinctive features of the tracked objects are enhanced, thus improving the linking accuracy. Unlike [START_REF] Ch | Multi-target tracking by on-line learned discriminative appearance models[END_REF], for each tracklet we learn online the specific representation of the tracklet appearance, highlighting distinctive features of the particular object. It means that for N tracklets, we obtain N models, each highlighting its differences. In [START_REF] Ch | Multi-target tracking by on-line learned discriminative appearance models[END_REF] only one model for a set of targets is learned to maximize discriminative appearance matching.

SHORT-TERM TRACKING

The short-term tracking is supervised by a controller [START_REF] Chau | Dynamic and robust object tracking for activity recognition[END_REF] which automatically tunes the object descriptors to cope with the scene context variations.

Tracking Algorithm

The tracking algorithm takes as input the video stream and a list of objects detected in a sliding time window. First, a link score is computed between any two detected objects appearing in this time window using a linear combination of 8 object descriptors T extracted from 2D, 3D geometrical information, various colour descriptors and gradient cues (i.e. HOG). Successive links form several paths on which an object can undergo within this temporal window. Each possible path of an object is associated with a score given by all the scores of the links it contains. The object trajectory is simply determined by maximizing the path score.

Controller

The aim of the controller is to automatically adapt the object descriptors T to the context of a video. We train our controller with various scene contexts and then we employ the controler to improve tracking accuracy. Training Phase. The training phase generates the context clusters. Videos are divided into video chunks where the context of each chunk is assumed constant. Using manually annotated objects (ground truth), video chunk contexts are modeled by 6 contextual features: the spatial density of detected objects; the object occlusion level; the object contrast with regard to the surrounding background; the variance of this contrast; the object 2D area and the variance of this area. The Quality Threshold (QT) clustering algorithm is used to cluster all the video chunk clusters from all the training videos. The Adaboost algorithm is then used for computing weights of each object descriptor for each context cluster to maximize object tracking performance. In the result, the training algorithm produces a learned database which contains several video context clusters associated with the best object descriptor weights. Online Control Process. The goal of the online control process is to tune the weights of object descriptors T over time using the learned data from the offline training phase. For every video chunk of a predefined number of frames, we determine the context cluster membership. Depending on this cluster membership, we select the learned weights of object descriptors T to guide the tracking process. In the result, the tracking algorithm is able to cope with the context variations, thus producing reliable tracklets.

ONLINE DISCRIMINATED APPEARANCES

Appearance model

Short-term tracking algorithm generates short but reliable tracklets. A tracklet is represented by a set of cropped images corresponding to the tracked regions. We use this set of images for computing MRCG descriptor.

MRCG [START_REF] Bak | Multiple-shot Human Re-Identification by Mean Riemannian Covariance Grid[END_REF] refers to Mean Riemannian Covariance Grid, which has been designed to describe a set of images. MRCG forms a dense grid structure with spatially overlapping square regions (cells). These cells are described using mean covariance matrix. Since covariance matrices do not form a vector space, this mean covariance is computed on a Riemannian manifold. The mean covariance is an intrinsic average, which blends appearances from multiple images, holding information on feature distribution, their spatial correlations and their temporal changes during tracking. In the result, each tracklet is represented by MRCG. We employ a discriminative method to enhance distinctive characteristics of each tracklet w.r.t. the others, thus improving linking accuracy.

Discriminative method

The discriminative method assigns weights to MRCG cells of a specific object, reflecting their relevance. Given a set of signatures S w = {s i } n i=1 , where s i is signature i computed from the tracklet registered in sliding time window w, we represent MRCG by s i = {µ i,1 , µ i,2 , . . . , µ i,m }, µ i,j is the mean Riemannian covariance and m is the number of cells in the grid. For each µ i,j we compute its relevance defined as variance σ i,j in a set of tracklet signatures extracted in window w. This variance is computed on a Riemannian manifold, projecting µ k,j on tangent plane at µ i,j

σ i,j = 1 n -1 n k=1;k =i log µi,j (µ k,j ) 2 µi,j , (1)
where operator log µi,j is uniquely defined on the Riemannian manifold, enabling distance computation. Using this discriminative technique, we focus on the features which are distinctive and at the same time we disregard common patterns (often corresponding to background). Each signature is discriminated vs the rest of signatures computed in sliding time window w.

Linking the tracklets

Tracklet Similarity: Appearance of each tracklet is represented by MRCG signature. The similarity between two tracklet signatures s A and s B is defined as

S(s A , s B ) = 1 |K| i∈K σ A,i + σ B,i ρ(µ A,i , µ B,i ) (2)
where K stands for the set of cells in the grid structure; ρ is the geodesic distance (see [START_REF] Bak | Multiple-shot Human Re-Identification by Mean Riemannian Covariance Grid[END_REF] for details); σ A,i and σ B,i are the weights of the corresponding cells computed by discriminative method (Section 4.2).

Linking: Given a set of tracklets, we search for the possible matching candidates based on temporal constraints. We assume that two tracklets can not overlap in time to be a candidate for linking. This assumption is based on the observation that one object can not belong to two different trajectories at the same time. Using tracklet similarity we link trajectories based on the threshold strategy applied to our similarity function. Two tracklets are linked together when their similarity is high enough (S(s A , s B ) > θ). Threshold θ is learned by maximizing true matches, while using the data employed for controller training.

EXPERIMENTAL RESULTS

We evaluate the effectiveness of our approach using two public surveillance datasets: CAVIAR1 dataset and 2008 i-LIDS Multiple-Camera Tracking Scenario (MCTS)2 dataset.

Single camera tracking -CAVIAR data

Caviar dataset contains 26 videos, 6 of them are used for training our controller and the remaining 20 are used for evaluation. We carry out an experiment employing the commonly used metrics [START_REF] Ch | Multi-target tracking by on-line learned discriminative appearance models[END_REF]: GT -the number of trajectories in the ground truth; MT -the percentage of trajectories that are successfully tracked for more than 80% divided by GT; PT -the percentage of trajectories that are tracked between 20% and 80% divided by GT; ML -the percentage of trajectories that are tracked for Method GT MT (%) PT (%) ML (%)

Multi camera tracking -i-LIDS data

We perform two experiments on i-LIDS data with multi cameras. The evaluation is presented in the light of linking the tracklets across disjoint camera views. i-LIDS-AA [START_REF] Bak | Boosted human re-identification using riemannian manifolds[END_REF]: This dataset contains 100 individuals registered in two non-overlapping cameras. For each individual a different number of cropped images is given, forming the tracklet. Our aim is to link correctly the tracklets from the first camera with the tracklets from the second camera. Although i-LIDS-AA was originally extracted for evaluating the person re-identification problem, this dataset can also be applied to test our approach. In experiments we set sliding window w = 10 individuals (based on the order in the dataset), which simulates our sliding time window. Assuming a regular flow of individuals from the first camera to the second camera, we successfully linked 72% of tracklets. It is worth noting that the best performance for re-identification achieved on this data reached 43% for the first rank in CMC curve [START_REF] Bak | Multiple-shot Human Re-Identification by Mean Riemannian Covariance Grid[END_REF].

The results show that our discriminative learning can handle such challenging aspects as different color responses and different camera settings. i-LIDS-crowded: 3 This dataset contains a dense scenario with strong occlusions and complex interactions between objects. Crowded environment makes the object detection and the object tracking very challenging. We applied our shortterm tracking to obtain the tracklets from both cameras. During linking the tracklets from the first camera with the tracklets from the second camera we tuned the similarity threshold to ensure 100% precision. Finally, 33.3% of ground-truth objects were linked together across disjoint camera views.

CONCLUSION

We proposed a new approach for linking tracklets in a single and multi camera scenario. By applying discriminative learning on appearances registered in a sliding time window, we

Fig. 1 .

 1 Fig. 1. The overview of the tracking approach in T frames: (a) The raw detection results; (b) the results of the short-term tracking; (c) the results of linked trajectories using online discriminated appearances.

Table 1 .

 1 Tracking results on Caviar dataset. less than 20% divided by GT. The tracking results are presented in Table1. Our results show that, although detection responses are missed (high ML), our discriminative method achieves high MT = 84.6%, reaching state of the art performances.

	Wu et al.[8]	140	75.7	17.9	6.4
	Xing et al.[9]	140	84.3	12.1	3.6
	Huang et al.[10] 143	78.3	14.7	7.0
	Li et al.[11]	143	84.6	14.0	1.4
	Kuo et al.[4]	143	84.6	14.7	0.7
	Our approach 140	84.6	9.5	5.9

CAVIAR: http://homepages.inf.ed.ac.uk/rbf/CAVIARDATA1

i-LIDS: http://www.homeoffice.gov.uk/science-research/hosdb/i-lids/

TrecVid/Dev08/: 2007-11-01-CAM1-2 and 2007-11-01-CAM3-2are able to enhance the linking accuracy. The approach was evaluated on CAVIAR and i-LIDS datasets. In the future we will investigate how to improve object detection responses to minimize ML metric.

Acknowledgements

This work has been supported by VANAHEIM and VICOMO project.


Rébecca Deneckère
email: rebecca.deneckere@univ-paris1.fr

Irina Rychkova
email: irina.rychkova@univ-paris1.fr

Selmin Nurcan
email: selmin.nurcan@univ-paris1.fr

Modeling the role variability in the MAP process model

Keywords:

Business process modeling is a valuable technique helping organizations to specify their processes, to analyze their structure and to improve their performance. Conventional process modeling techniques are proven to be inefficient while dealing with non-repetitive, knowledge-intensive processes such as Case Management processes. In this work we use the MAP notation to model a Mortgage Approval Process as defined in Banking. To increase the navigability and practical value of map models, we extend the MAP notation with the concepts of Roles, Relations between roles, and Role Configuration Rules.

INTRODUCTION

In the modern economy, companies are more and more interested in expanding their businesses and exploring new markets. Proliferation of Information and Communication Technologies (ICT) fosters collaboration and makes people across the globe work together as they are sitting in one office. Working cultures, local policies and regulations, however, remain specific to a country or a region forcing the companies to customize their processes for each particular case and to take into account where and under which conditions the process is executed) [START_REF] Rychkova | Towards Adaptability and Control for Knowledge-Intensive Business Processes: Declarative Configurable Process Specifications[END_REF].

Business process modeling is a valuable technique helping organizations to specify their processes, to analyze their structure and to improve their performance. Conventional techniques for business process modeling are imperative -they encourage the early specification of the control flow [START_REF] Jarzabek | Model-based support for business reengineering[END_REF][3] [START_REF] Marca | IDEF0/SADT: Business Process and Enterprise Modeling[END_REF]. Using these techniques, specification of numerous options and variations in a process model related to its context of execution becomes tedious if at all possible [START_REF] Lee | Extending the Potts and Bruns Model for Recording Design Rationale[END_REF][6] [START_REF] Rummler | Improving Performance[END_REF] [START_REF] Yu | Using Goals, Rules and Methods to Support Reasoning in Business Process Reengineering[END_REF].

Similar problem statements have been identified and studied in the area of process engineering.

For more than ten years process engineering remains a key issue for the information system (IS) communities [START_REF] Rolland | A Comprehensive View of Process Engineering[END_REF]. For instance, [START_REF] Dowson | Software Process Themes and Issues[END_REF] [START_REF] Armenise | A survey and assessment of software process representation formalisms[END_REF] [12] [START_REF] Jaufman | Requirements for flexible software development processes within large and long taking projects[END_REF] show that an improved development process leads to improved productivity of the software systems industry and improves systems quality.

Similarly to a business process, IS development process was traditionally organized into sequences of activities (e.g., "analysis," "design," "coding," "testing") [START_REF] Royce | Managing the development of large software systems: concepts and techniques[END_REF] [START_REF] Boehm | A Spiral model of software development and enhancement[END_REF], with a rigid control flow. Later on, these activity sequences were replaced by values and practices [START_REF] Beck | Extreme programming eXplained: embrace change[END_REF] [START_REF] Abrahamsson | Agile software development methods: Review and analysis[END_REF]. However, [START_REF] Ralph | A Teleological Process Theory of Software Development[END_REF] highlights that, in practice, IS engineers are faced with countless methodical choices: they can choose to execute one activity completely or partially, to combine aspects of two or more different activities, or to ignore an activity. Thus, decisions made through the IS development process should reflect the situation at hand and help an IS engineer to specify and enact a unique process adapted to this situation.

In response to this problem, several methodologies supporting intentions have been developed [START_REF] Van Lamsweerde | Reasoning About Alternative Requirements Options[END_REF] [START_REF] Amyot | URN: Towards a New Standard for the Visual Description of Requirements[END_REF] [START_REF] Rolland | A Multi-Model View of Process Modeling[END_REF]. Intention-oriented process modeling focuses on what the process is intended to achieve (i.e. what is the reason behind the process execution), instead of how it is going to achieve. [START_REF] Dietz | Basic Notions Regarding Business Processes and Supporting Information Systems[END_REF]. Nevertheless, many of these methodologies do not employ the concept of intention/goal as an integral part of their process model. These process models focus on how the process is performed and externalize what the process is intended to accomplish -the intention. In MAP process models, [START_REF] Rolland | A Multi-Model View of Process Modeling[END_REF], in contrast, the intentional level is used to guide engineers through IS processes by dynamic choices of the executable service sequences. Each time when an intention is realized, the model suggests an executable service (or several alternative services) that can be invoked on the next step. The resulting IS development process is adaptive and flexible as it is constructed dynamically following the situation.

In this paper we use the MAP methodology to model a Mortgage Approval Process as defined in Banking. Providing a flexible mechanism for flexible and customizable process specification, original MAP notation, nevertheless, remains restrictive: it does not allow us to specify roles for this process.

The concept of Role is a key concept in process modeling. Roles are present in nearly all process models -they help the modeler to structure the process model, by grouping the responsibilities and answering the question "who does what?". IS designer, developer, stakeholder, decision-maker, client, clerk -are all examples of roles. According to [START_REF] Nurcan | Main concepts for cooperative work place analysis[END_REF] the role is the definition of an organizational intention shared by a collection of users, all of whom having the same privileges and obligations to a set of work processes in an organization. The role is also the main concept for the representation of cooperative processes. In other words, the role is the basic block of the organization perspective [START_REF] Daoudi | A benchmarking framework for methods to design flexible business processes[END_REF], which reflects information about the organizational structure and actors to which the business process is intended. Roles can be represented and used differently in process models depending on the notation.

The original MAP meta-model presented in [START_REF] Rolland | A Multi-Model View of Process Modeling[END_REF] does not include the concept of Role. However, roles implicitly participate in decision-making in all the levels of an organizational process expressed by a map. For example, it can be a specific role responsible for making a choice between several alternatives in the map. The notion of role will then be useful to explicitly define who can take the navigation decisions. Roles can also be present in the description of an executable service (e.g. some activities may be performed by specific roles and only them). Therefore, in order to improve guidance on maps, it is important to include the concept of role into the MAP metamodel.

In this work we extend the MAP notation with the concepts of Roles, Relations between roles, and Role Configuration Rules. These modeling concepts were introduced as a part of DeCo (Declarative Configurable Process Specification) approach in [START_REF] Rychkova | Towards Adaptability and Control for Knowledge-Intensive Business Processes: Declarative Configurable Process Specifications[END_REF]. This mechanism allows us to anticipate abundant variations of context as, even within the same bank, different agencies may have different stuffing and thus, different distribution of responsibilities between employees. As a result, different actors may be required/available to execute the Mortgage Approval Process. We will demonstrate how these variations can be incorporated within the same map.

The reminder of this paper has the following structure. In Section 2 we discuss the related works and identify the advantages of MAP applied to modeling case management processes. We also explain the limitations of the existing MAP notation and provide the rationale for its extension. In Section 3 we present an example of the Mortgage Approval Process and explain the MAP meta-model on this example. In Section 4 we extend the MAP notation with the mechanism to explicit Role variability modeling. In Section 5 we present our conclusions and discuss our future work.

II. RELATED WORK

A. Process flexibility

Business process modeling is a valuable technique helping organizations to specify their business processes, analyze their structure and improve their performance. Conventional techniques for business process modeling are imperative -they encourage the early specification of the control flow. However, for certain forms of business processes the control flow cannot be identified at design time. [START_REF] Keith | Mastering the Unpredictable. How adaptive case management will revolutionize the way the knowledge workers get things done[END_REF]. The case management process can be characterized as follows: it (i) has a descriptive nature, (ii) varies largely depending on its execution context, (iii) involves a lot of, often implicit, decision making resulted from communication/ negotiation among human actors, (iv) is based on the available/emerging case-related knowledge [START_REF] Rychkova | The Old Therapy for the New Problem: Declarative Configurable Process Specifications for the Adaptive Case Management Support[END_REF]. For such processes, early specification of the control flow is not only challenging but also unnecessary and even harmful.

One of the examples is a Case Management Process

As advocated in [START_REF] Nurcan | Main concepts for cooperative work place analysis[END_REF] an unstructured (i.e. without predefined control flow) process cannot be represented in terms of flow of tasks or activities or operations... The model proposed in [START_REF] Nurcan | Main concepts for cooperative work place analysis[END_REF] allows to represent it as a 'black box' associated to a set of resources that it uses and produces and a set of participating roles. The key concept of such kind of unstructured processes is the information and knowledge sharing in the work group (i.e. among actors playing roles).

Another paradigm to deal with non-prescriptive or non imperative processes is provided by conversation models. The latter are based on the speech act theory and on the principle that each sentence expressed by someone represents an intention, a commitment [START_REF] Searle | A taxonomy of illocutionary acts[END_REF]. For instance, the Action model [START_REF] Medina-Mora | The Action Workflow Approach to Workflow Management Technology[END_REF] defines a structure to represent the conversation relationship between two participants, customer and performer.

The type of process models addressed in [START_REF] Dellen | Knowledge Based Techniques to Increase the Flexibility of Workflow Management[END_REF], [START_REF] Faustmann | Enforcement vs. Freedom of Action-An Integrated Approach to Flexible Workflow Enactment[END_REF], [START_REF] Nurcan | Special issue of the Business Process Management Journal on "Goaloriented business process modeling[END_REF] is based on the decision-oriented paradigm according to which the successive transformations of the product are considered as consequences of decisions. The underlying paradigm is that a process model does not have only to specify the linking of activities or product states but also the intention behind the execution of activities and their ordering at the run time. Decision-oriented models guide the decision making process that shapes the business and thus help reasoning about the rationale of decisions [START_REF] Mclean | Design Rationale: The argument behind the artifact[END_REF]. This paradigm seems to be the particularly appropriate for representing processes requiring flexibility. This paradigm does not require modeling the process control flow in advance and allows alternative strategies to be considered.

B. Variability

In [34][35] the concept of configurable process has been presented and the modeling formalism to deal with process configurability at multiple perspectives is defined. Namely the authors present the Configurable Integrated EPC (C-iEPC) modeling notation that extends the well-known Event Process Chain (EPC) notation and addresses the process configurability along the control-flow, data, and resource perspectives. According to this approach, "Given a configurable process model, analysts are able to define a configuration of this model by assigning values to its variation points based on a set of requirements. Once a configuration is defined, the model can be individualized automatically."

In [START_REF] Rychkova | The Old Therapy for the New Problem: Declarative Configurable Process Specifications for the Adaptive Case Management Support[END_REF] the method for Declarative Configurable process specifications (DeCo) is presented. This method defines an extension to BPMN [START_REF]Object Management Group, Business Process Model and Notation (BPMN) FTF Beta 1 for Version 2.0 OMG[END_REF] graphical notation and identifies three types of relations between roles: synonym, alternative and specialization.

C. Roles and Actors

The concept of Role is closely related to the concept of Actor in modeling methodologies. Various definitions of Actors and Roles can be found in literature. The most common definition states that an Actor specifies a Role played by a user or any other system that interacts with the subject [START_REF]OMG Unified Modeling Language (OMG UML)[END_REF]. In I* [START_REF] Van Lamsweerde | Reasoning About Alternative Requirements Options[END_REF], actors are considered as "active entities that carry out actions to achieve goals by exercising their know-how and could be composed of Agents, Roles and Positions, each of which is an actor in a more specialized sense". OPF [START_REF] Henderson-Sellers | Process meta-modeling and process construction: examples using the OPF[END_REF] gives another definition of an actor (a producer) which is "a core abstract method component that models someone or something that performs work units" (produces work products or provides services).

Several attempts have been made to introduce the concept of Role in the MAP notation [39][23]. In [START_REF] Deneckere | Process Line Configuration -an Indicator-based Guidance of the Intentional Model MAP[END_REF], the MAP metamodel has been extended with the concept of Indicator. Indicators are used to help decision-making in the navigation through a process map. A typology of indicators was defined based on well-known project characteristics (for instance the cost, the duration, the formality degree, and so on). This indicator typology includes a particular indicator, which represents the Expert role. This indicator is used to define which roles are linked to each executable services of a map. However, this information, even if it helps the guidance through a map, doesn't give the user enough information about the variability inherent to the role concept. For instance, it cannot be used to know if a specific expert role is related to other expert roles in the project.

In [START_REF] Nurcan | Business Process Modeling for developing Process Oriented IT Systems[END_REF] the concept of Role has been added to the MAP meta-model in order to support the "operationalization" of MAP process models. Namely, this concept provides an explicit relation between an intentional process perspective captured by MAP process model and its organizational perspectives described by a business process. Enhancing the MAP notation using the role concept also allowed us to explicitly link navigation guidelines associated to a map with the roles executing them. Namely, for the intention selection and the strategy selection guidelines, the role taking the navigation decisions can be specified. For the intention achievement guidelines, the role executing the corresponding section in the map can be specified. The third capability added to the MAP notation thanks to the role was the possibility to deal with non-structured processes as suggested previously in [START_REF] Nurcan | Main concepts for cooperative work place analysis[END_REF]. While improving the traceability between different process perspectives, the extended MAP process model presented in [START_REF] Nurcan | Business Process Modeling for developing Process Oriented IT Systems[END_REF] provides little guidance for process users and does not enable process customizations.

The purpose of this work is to enhance the concept of Role in MAP and to provide the mechanisms for (i) expressing role variability and (ii) role configuration. These mechanisms will improve the guidance on maps taking into account all the role relationships present in the project.

III. APPLYING MAP TO CASE MANAGEMENT PROCESS MODELING

A. Example: The Mortgage Approval Process

In this paper we consider an example of processing a mortgage claim as defined by different financial institutions in the USA. The information provided below results from our study of multiple information sources (e.g. http://www. homebuyinginstitute.com/, http://www.mortgage-resourcecenter.com/, http://homebuyereducation.bankofamerica.com/, http://www.homeloancenter.com/ etc.). It represents a compilation of guidelines, recommendations, and descriptions of the Mortgage Approval Process, provided by different loan consulting firms, financial advisors, and banks, available on the web.

A mortgage is a loan for buying a house. On the USA market, there exist various mortgages that will be appropriate for special situations such as bad credit loans, first time homebuyer, etc. The terms and length of the mortgages are negotiable and can be adapted for the applicant's situation.

The mortgage approval process can be divided into the following steps:

1. Pre-qualification 2. Formal application 3. Document review 4. Pre-approval 5. Property appraisal 6. Final Approval 7. Closing

The goal of the pre-qualification step is to determine the potential mortgage amount that the applicant is eligible for. The purpose of the formal application is to provide the lender with a package of documents characterizing in details the current financial situation (assets) of the applicant as well as his/her employment and credit history. Document review follows the formal application and may include the preapproval step. The pre-approval letter issued as a result of a pre-approval indicates that a thorough analysis of the applicant's credit, income, and assets has been completed and that the applicant is pre-approved by a lender for a specific loan amount. Being optional, this letter, however, may represent a valuable negotiation instrument for an applicant while searching for a property. When the applicant selects the property, the potential mortgage lender initiates the Property appraisal. The result of the appraisal defines the amount of the mortgage and a corresponding down payment that has to be paid by the applicant. The lender makes "approve", "not approve", or "approve with conditions" final decisions based on the document review and the appraisal results. If the loan is approved, a commitment letter is issued for the applicant, and a closing date is set up. Closing (also called settlement) is a final step. During the mortgage closing, the mortgage lenders will purchase the house and hold the title, as the applicant makes payments to them.

Pre-qualification and Pre-approval are compulsory steps; Pre-approval and Property appraisal can be considered as parts of a Document review and serve as a ba approval.

Below, we illustrate how this process using the MAP meta-model.

B. The MAP meta-model

Goal modeling is an effective way requirements of software systems b understanding the intentions of the involved [START_REF] Yu | Understanding "why" in software process modeling, analysis, and design[END_REF] and the process model MAP is an exam that has been conceived to meet this c expression provides a synthetic view of th process in a relatively easy to understand w revealed in two ways, by the gradual mo different levels of a top map, and by strategies/paths available at a given map intentional MAP meta-model has been intr engineering domain [START_REF] Rolland | A Multi-Model View of Process Modeling[END_REF] and validated i requirement engineering [START_REF] Prakash | Systems Design for requirements expressed as a map[END_REF], method e enterprise knowledge development [START_REF] Barrios | Model Driven Architectures for Enterprise Information Systems[END_REF] and [START_REF] Rolland | A Multi-Model View of Process Modeling[END_REF].

The map corresponding to the mortgage a presented in Fig. 1. intentions. An edge enters a no be used to achieve the target in there can be multiple edges en represent multiple ways to achi Fig. 1 (a) represents a Hig approval process defined in the intensions specified on this leve and Approve Mortgage Applic realized when the Formal validated (steps 1 and/or 2 of th when Final Approval decision The final intention (Stop) termination and can be realized (in case of a positive approval d of the mortgage claim otherwis Fig. 2 shows the MAP mo The key element of a map is a triplet: a source intention, a t linking these source and t corresponds to a process of ach a specific situation following a the triplet <Define Mortgage ap with pre-approval, Approve mo a section that can be inter application has been completed continue to its final approval f with a pre-approval intermediat ode if its associated strategy can ntention (the given node). Since ntering a node, a map is able to eve an intention.

gh-level map of the mortgage e previous section. There are two el: Define Mortgage Application cation. The former intention is application is completed and he example); the latter is realized is made (step 6 of the example). corresponds to the process d either by Closing the mortgage decision) (step 7) or by rejection e. del using the UML formalism. a section. A section represents a target intention, and a strategy arget intentions. The section hieving the target intention from a particular strategy. In Fig. 1 Three kinds of relationships are defined for sections: thread, path and bundle.

A thread relationship represents the possibility to achieve a target intention from the source intention following several different paths (defined by a different strategy). Each of these paths can be seen as a section in the map. Multiple strategies leading to an intension describe multiple ways to realize this intension. On the High-level map shown in Fig. 1 (a), the Approve Mortgage Application intention can be realized either by complete document revision, which include Document review (step 3) and Property Appraisal (step 5) or by complete revision with Pre-approval (steps 3-4-5).

A path relationship represents the precedence (or the order) between sections. We say that one section succeeds (precedes) another if and only if the source (target) intention of the former is the target (source) intention of the latter. There is absolutely no path predefined as the engineer constructs his own path following the situation at hand. Given the thread and the path relationships, an intention can be achieved by several combinations of sections. In our example, the mortgage lender can navigate through the map presented in Fig. 1 (a) in order to approve a mortgage. Several paths are possible, e.g. the application can be submitted directly or following the prequalification procedure first; approval can be granted without the pre-approval step or with the latter, etc.

A bundle relationship shows the possibility for several sections having the same source and target intentions to be mutually exclusive. (Mutual exclusion is depicted by dashed lines in a map). In Fig. 1 (a) the strategy "By closing" linking the Approve Mortgage Application intention to the terminal intention Stop represents a bundle relationship. It combines two sections that are mutually exclusive: either the closing is done in escrow or face-to-face.

A section in a map may be refined with another map using the refinement relationship. Refinement is an abstraction mechanism by which a complex assembly of sections at level i+1 is viewed as a unique section at level i. This relationship introduces levels in the process representation as each map may be represented as a hierarchy of maps. Fig. 1 (b) represents the refinement of a section of the high level map illustrated in Fig. 1 (a) and provides more details on Final Approval process of a mortgage application.

When a section cannot be refined any further, an Executable Service that fulfills the intention may operationalize it. It implies the transformation of the product under development with the execution of a service (which can be a guideline, a workflow, an algorithm, a business process model, etc.).

A map specifies one 'Intention Selection Guideline' (ISG) per each intention I i , except for 'Stop' intention. Given an intention I i , an ISG identifies the set of intentions {I j } that can be achieved in the next step and proposes arguments to select one of them. There is also one 'Strategy Selection Guideline' (SSG) per intentions pair <I i ,I j >. Given two Intentions I i , I j and a set of possible strategies S ij1 , S ij2 , ..S ijn applicable to I j , the associated SSG guides the selection of a S ijk . We can say that ISGs and SSGs describe the know-how of a domain in socalled decision process chunks [START_REF] Nurcan | Business Process Modeling for developing Process Oriented IT Systems[END_REF].

IV. EXTENDING MAP FOR ROLE AND ROLE VARIABILITY MODELING

Enabling multiple strategic choices, the MAP specification does not provide enough information for realization of these choices. One of the recurrent problems is the role assignment.

As specified in DeCo [START_REF] Rychkova | Towards Adaptability and Control for Knowledge-Intensive Business Processes: Declarative Configurable Process Specifications[END_REF], synonyms, alternatives, optional/obligatory process elements and hierarchies of elements defined by generalization/specialization relations provide a mechanism for modeling process variability. The configuration rules, on the other hand, support the configuration of variants based on the situation.

In this work we apply these mechanisms to model variability of roles in maps. In our example, the roles associated with the Mortgage Approval Process can vary not only from country to country and from one bank to another following theirs internal policies, but also from one agency to another within one bank (e.g. based on the size of this agency). Whereas some sections of an abstract mortgage process illustrated in Fig 1(a) can be assigned to abstract actors (e.g. Mortgage lender), concrete role assignments for the refined Mortgage Approval Process (Fig. 1(b)) may depend on the financial institution: small banks have only several (2-4) roles associated with the process, whereas in big agencies the application processing and decision making is more likely to be assigned to a number of different roles with different responsibilities. As our study shows, the same responsibility can also be performed by several roles or delegated from one role to another according to some internal rules.

As a result, different actors may be required/available to execute the Mortgage Approval Process. Thus, to provide the efficient guidance for both administration and personnel of a bank, an explicit specification of roles, relations between them (e.g. hierarchy, alternatives or possible replacements, and synonyms) is required.

A. Enhanced MAP concepts

Role variability is important in the real life process descriptions: in the organizations the same responsibilities are often associated to multiple roles, at the same time, some role names can have double meaning depending on the project or process. Thus, the process gets overloaded with exceptions and becomes extremely complex providing little support and guidance. To get more practical value, the explicit specification of roles, their relations and rules of role configuration/ assignment is required.

Figure 3 represents an extended meta-model of MAP and includes the following concepts: Role, Relations between roles, and Role Configuration Rule. These concepts enable a mechanism for modeling role variability in MAP process models. Variability of roles in business process models is a mechanism to address the organizational complexity. It was discussed in [START_REF] Rosa | Configurable multi-perspective business process models[END_REF]. A role is the definition of an organizational intention shared by a number of actors [START_REF] Nurcan | A meta-model for goal driven cooperative work processes[END_REF]. Role can be identified with a set of responsibilities and can be fulfilled by one or several actors in the organization. Loan consultant, Loan officer, and Appraisal agent -are examples of roles.

In the enhanced MAP meta-model, the concept of role is specialized into individual role and group role. For example, Loan Consultant is an individual role whereas a Loan Processor is a group role. A group role contains several individual roles.

As in [START_REF] Rychkova | The Old Therapy for the New Problem: Declarative Configurable Process Specifications for the Adaptive Case Management Support[END_REF] [1], we define three types of relations between roles: Synonym, Alternative and Configuration.

Role configuration expresses possible instantiation of a generic role into configured roles. For instance, the Mortgage Lender may be configured into several other roles, as the Loan Consultant, the Loan processor, the Closing Agent and so on. Within a configuration, different roles can be related via synonym or alternative relations.

Synonym relation expresses the fact that a specific role can be found in different organizations/processes under different names while still encapsulating the same set of responsibilities (i.e. this role has "synonyms"). For example, in the Mortgage Approval Process, the Loan Consultant role is a synonym to the Loan Broker role. Thus, during the process instantiation, both roles can be assigned to the same actor.

Alternative relation expresses the fact that, under specific conditions, the responsibilities associated with one role can be fulfilled by another role (or delegated to it). For example, if the local agency does not have its own Appraisal agent, an External Appraisal agent can be recruited to perform the property appraisal task. Along those lines, the role of the Loan Processor, that performs an application revision and decision making, can be fulfilled by a Loan Broker (for the smaller agencies).

We associate the executable service supporting a map section to one or several roles. This captures the knowledge about which tasks can be taken by which role and offers a better guidance of the map execution. The executable service (i.e. a business process chunk [START_REF] Nurcan | Business Process Modeling for developing Process Oriented IT Systems[END_REF], a method chunk [START_REF] Rolland | Capturing system intentionality with maps[END_REF]...) encapsulates a process knowledge specified in the organizational layer (by answering what, who, when, where and how questions).

B. Modeling the Role hierarchy for Mortgage

Approval Process A rectangle with thick outline and the "C" in the right corner is a "compact" notation that refers to a role that can be further configured in the process model based on the situation or context. We envisage integrating the Role element into the MAP notation using this compact representation. For convenience, the configuration details can be shown on a separate diagram as represented in Fig. 4.

In our example, the abstract role Mortgage lender combines a set of complementary and possibly overlapping responsibilitie. These responsibilities can be fulfilled by a single actor or shared by a group of actors, giving a rise to more specific roles: Loan Consultant, Loan Processor, Underwriter, etc.

In the diagram representing the details of role configuration, we define another two types of relations Namely, the synonym relation refers to t context of a given process, two roles have ab responsibilities. Thus, they can be defined in different organizations for example). In ou Broker and Loan Officer roles are synon Consultant role as within the mortgage appr fulfill the same responsibilities.

The alternative relation refers to the sit responsibilities of one role can be delegate otherwise not having those responsibilities. Fig. 4, Loan Processor role has an alternative role. This alternative is bounded by a condi with a shaded circle) meaning that whenev agents in the local agency is less then responsibilities in the Mortgage approval fulfilled by a Loan Processor can (will) be f Officer.

Along those lines, External Appraisal Attorney are alternative roles for the bank A Attorney respectively. These alternatives whenever their corresponding roles insid unavailable.

We emphasize here that all the considere defined for a given process only, e.g. where two roles can be considered as synonyms, fo this will not necessarily be the case responsibilities fulfilled by the same role processes might be different.

We specify configuration rules for the rol rules define the conditions when the synon relation between roles can be activated; they in a form of a predicate evaluating to Tru satisfied at a given context of False otherwis depicted in Fig. 4 the Rule R1 describes activating alternative relation: it states tha agency employees should be less than 6 in or alternative relation between the Loan Pro Officer roles. Otherwise, in a bigger agenc revision should not be delegated to a Loan Of Fig. 5 illustrates other examples of rules t configure the roles: the availability of a giv environment, geographical location of an ag many other factors can affect the configurat model, in particular imposing the role and act The extended map with the in Fig. 6. The mortgage application c a pre-qualification process appointment in a bank (we ca Loan Consultant is a role res through both of these processes completed, the document revi mortgage lender; this process c be accomplished following diff the mortgage is assigned to a s The final approval should be ca and should be accompanied by carried out by the Appraisal assigned for the closing process 6 be defined on the level of a on, and/or its local branch or e role specifications is illustrated oval process enhanced maps e depicts the high level view on ss. The section A represents the ortgage approval as executed by signed to the abstract role of represents the refinement of this as follows: can be made either by following or by directly making an all it "a personal contact"). The sponsible for guiding the client s. After the formal application is iew process is initiated by the consists of several steps and can ferent paths. The pre-approval of single role (the Loan Processor). arried out by the Loan Processor y the property appraisal process l agent. There are three roles s. Grateful

V. CONCLUSION AND FUTURE WORK

This paper proposes a mechanism to model roles and role variability in the intentional meta-model MAP. Namely, we extended the MAP notation with the concepts of Roles, Relations between roles, and introduced the Role Configuration Rules (formalization of these concepts will be addressed in our future publications).

The proposed mechanism enables a better guidance and navigation on maps as each process step can be defined for specific roles only. The number of proposed alternatives to navigate through the map is then reduced to the steps compatibles with the user role.

We illustrated our modeling process on the example of the Mortgage Approval process as defined in the USA banks (the simplified specification has been considered). The Mortgage approval process is an example of Case Management process. As shown in [START_REF] Rychkova | The Old Therapy for the New Problem: Declarative Configurable Process Specifications for the Adaptive Case Management Support[END_REF], modeling this process using traditional imperative modeling style can be difficult if at all possible. In this paper we demonstrated the advantages of intentional modeling using MAP enriched with role modeling mechanism. The first advantage is that the main user (the mortgage lender in our example) has a perfect view of the stakeholders involved into processes. The second advantage is that the resulting model allows us to anticipate variations of context (e.g. different bank agencies having different distribution of responsibilities between employees) while managing the model complexity.

Proposed notation for modeling role variability is not limited for MAP; as proposed in DeCo [START_REF] Rychkova | Towards Adaptability and Control for Knowledge-Intensive Business Processes: Declarative Configurable Process Specifications[END_REF], it can be used to extend another process modeling notations such as BPMN [START_REF]Object Management Group, Business Process Model and Notation (BPMN) FTF Beta 1 for Version 2.0 OMG[END_REF].

In future, we plan to extend the notation proposed in this work by adding cardinality constraints.

Figure 1 .

 1 Figure 1. High level map of the Mortgage Approval Pr map of the section A of this map A map is a diagram composed of nodes are intentions to realize and edges are strateg

Figure 2

 2 Figure 2. MA

  (a) pplication, By complete revision ortgage application> represents rpreted as follows: when the d and validated, the process can following the complete revision te step.

Figure 3 .

 3 Figure 3. Enhanced MAP meta-model

Figure 4 .

 4 Figure 4. Role hierarchy and relations between roles in Mortgage Approval Process Figure 4 illustrates the hierarchy of Roles defined in Mortgage Approval Process. The roles are modeled as rectangles (following the UML notation) with the name in the upper compartment.

  Synonym relation, depicted with a tag "syn" and Alternative relation, d line with a tag "alt". These relations refle organization and are used to explicitly de what" based on the concrete context.

Figure 5 .

 5 Figure 5. Role configuration rule exam

Figure 6 .

 6 Figure 6. Mortgage appro The upper part of the figure the Mortgage Approval Proces process of our interest -the Mo a Bank. This section is ass Mortgage Lender. The bottom part of Fig. 6 r section and can be interpreted a