Sylvain Kubler

William Derigent

Eric Rondeau

André Thomas

Information dissemination process for context-aware products

Keywords: Distributed databases, Data dissemination, Internet of Things, Pervasive computing

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Information dissemination process for context-aware products S. Kubler * W. Derigent * É. Rondeau * A. Thomas *

INTRODUCTION

New challenges and opportunities arise with concepts such as Internet of Things (IoT), Ubiquitous/Pervasive Computing [START_REF] Weiser | The computer for the 21st century[END_REF]]. Through these concepts, objects of the real world are linked with the virtual world. Thus, connections are not just people to people or people to computers, but people to things and most strikingly, things to things [START_REF] Sundmaeker | Vision & challenges for realising the Internet of Things[END_REF]]. Such applications rely on ever more complex information systems combined with ever increasing data volumes, which are stored in a large number of information vectors. These vectors may be either fixed (desktop computers) or mobile (wireless devices, RFID. . . ). The IoT based on the RFID usage enables accessing data disseminated on any kind of physical object and developing new smart services [START_REF] Yan | The Internet of Things: From RFID to the Next-Generation Pervasive Networked Systems[END_REF]].

Although widely explored in the Computer Science field, IoT applications in the framework of SCM or Material Flow Management are limited. However, such a concept may turn out to be a good strategy. Indeed, during its lifecycle, a product passes through numerous companies dedicated to specific activities (manufacturing, usage. . . ). Technical, semantic and organizational interoperability between these companies is not always ensured, thus, conducing to information loss . If one considers the product as an information vector (i.e. on which information could be stored), it would contribute to improve interoperability all along the product lifecycle. According to [START_REF] Meyer | Intelligent products: A survey[END_REF], few research has been conducted on intelligence at object, i.e. products carrying their own information and intelligence (one can talk about active products). In fact, most of the time, products are only given an identifier (e.g. RFID) referring to a software agent or a database. This mode of information management is diametrically opposed to works initiated since 2003 by the PDS (Product-Driven Systems) community, which advocates physical information distribution within the product (i.e. information needed for managing its evolution). Meyer et al. concur with the PDS community by stressing the fact that, in an increasingly interconnected world involving many actors, information should not be stored in a single database but should be distributed throughout the supply chain network. That said, substantial information distribution improves data accessibility/availability compared to centralized architectures, but they are more complicated to design because data consistency/integrity has to be maintained. In short, product information may be allocated both to fixed databases and/or to the product itself. One might then wonder what the optimal data distribution is.

To do so, we define a four-step data dissemination methodology, discussed in section 2. The section 3 focuses on one important step of this methodology which concerns the identification of relevant information that should be stored on the product. The identification method is then implemented on a case study in section 4. This work focuses on the product information management through its lifecycle. According to [START_REF] Meyer | Intelligent products: A survey[END_REF], our study considers the product as intelligent and takes a focus on the dimension related to the location of intelligence (i.e. at object and/or through the network).

PROCESS OF INFORMATION DISSEMINATION

This section provides an overview of the global process to disseminate information between fixed databases and active products. In our process, information is represented through a Logical Data Model1 (LDM). The process consists of 4 steps as depicted in Fig. 1. This paper is in particular focused on step 2 since steps 1, 3 and 4 have been already dealt with in our previous works [Kubler et al. (2011a,b)]. We resume briefly these works (steps): Process step 1 consists in implementing the database system architecture, which can be either centralized or distributed. Many works in the literature help the designer to choose Storage of data on the product 4 or 0 1 1 0 0 1 1 000 1 Fig. 1. Proposition of a data dissemination methodology the more suitable system according to his expectations and the application constraints [START_REF] Ozsu | Principles of Distributed Database Systems[END_REF]].

Step 3 deals with the system performance, which depends on multiple factors as the physical architecture, the data distribution, etc. [START_REF] Kubler | Key factors for information dissemination on communicating products and fixed databases[END_REF] propose an approach to evaluate each possible data fragment distribution between products and databases in order to identify the best one (regarding a given performance criterion which is the time for achieving a set of manufacturing operations). Once the data allocation is chosen, data fragments are allocated to databases and/or to products. This is performed in step 4. To store data fragments on the product, it is necessary to instrument it. [START_REF] Kubler | Prototyping of a communicating textile[END_REF] propose a new concept referred to as communicating material, which considers the material as intrinsically communicating thanks to a large amount of RFID µtags scattered into it (a textile prototype was designed). Based on a specific architecture, it is then possible to allocate (i.e. to read/write) data fragments. This last research work has shown that it is technically feasible to set up a communicating product containing its own data. Moreover, the physical performance assessment (step 3) could select adequate data distributions regarding specific performance criteria (e.g. delay), but these may not be adapted to the context. As a result, an additional step (step 2) is required to select relevant data according to the context (subject of the rest of the paper). Let us note that this framework, and especially the steps 2, 3 and 4 will be performed online (i.e. during a given activity of the product lifecycle: cf. Fig. 3), when the product needs to be written or read.

IDENTIFICATION METHOD OF RELEVANT DATA RELATIVE TO THE PRODUCT

During its lifecycle, a product is shared by many actors and undergoes various operations. It is therefore essential to identify information that is relevant to users, but it is not that easy. For this reason, we propose an identification method which is based on the Logical Data Model (LDM). Fig. 2 gives insight into a part of such a LDM (which is considered in the case study proposed in section 4). A given entity of LDM corresponds to a relational table, where the attributes listed in each entity correspond to the table columns and, each table row is referred to as a tuple/instance of the relation. A view of such tables is given in Fig. 5 for 3 entities among the 5 depicted in Fig. 2: ManufacturingBill, MaterialDefinition and Materi-alLot. The identification method consists in two stages: (1) identification of all tuples through the entire LDM which are relative to the product instance (i.e. the product to which we intend to attach relevant data such as production orders). The product instance, denoted i p in this paper, may be of different types (e.g. product lot, single product) and consequently, will refer to distinct tables in the database;

(2) assessment of what is their relevance to be stored on the product according to the user concerns, the product environment, etc. For this purpose, we propose to implement and to adapt the approach developed by [START_REF] Chan | Context-sensitive mobile database summarisation[END_REF]. This approach is interesting in the sense that they try to match the context with data in order to select context-sensitive information. Other procedures through the literature could be used to assess the data relevance. For instance, the Analytic Hierarchy Process methods which has the flexibility to be integrated with different techniques like Fuzzy Logic, etc. [START_REF] Vaidya | Analytic hierarchy process: An overview of applications[END_REF]]. It would therefore be interesting to compare such methods with the one proposed by Chan and Roddick. Initially, we opt for their approach because it is developed in the framework of distributed databases, based on criteria which suit to our concerns. Both stages of the identification method are detailed in the next sections.

★ : Primary Key (PK)

✩ : Secondary Key (SK)

x : relation number

MaterialLot ID MatLot ★ Description Status Quantity ID MatDef ✩ ManufacturingBill ID ManBill ★ Description Quantity ID MatDef ✩ ID ProdDef ✩ ProductDefinition ID ProdDef ★ Description PublishedDate MaterialDefinition ID MatDef ★ Description Value ID MatClass ✩ MaterialClass ★ ID MatClass Description Value 2 1 4 3 Fig. 2. Example of a Logical Data Model (LDM)
3.1 Adaptation of the method of [START_REF] Chan | Context-sensitive mobile database summarisation[END_REF] As stated above, the method for assessing the data relevance is based in part on the approach developed by [START_REF] Chan | Context-sensitive mobile database summarisation[END_REF]. Their approach uses the notion of priorities (or weights) to select the appropriate data for the expected situation. In their model these priorities are computed at the level of the data item2 . The priorities are numerical values either supplied or generated through observation and experimentation and are assigned through a multifaceted evaluation of different criteria (8 in total). In our approach, we implement 3 of the 8 criteria that we consider to be the most appropriate according to our context (i.e. SCM). For each criterion, the calculation of a relative priority, ρ x (where x represents a criterion), and an assigned priority, Φ x , are defined and combined in a single formula which gives a prioritization P d for each data item. Data items will therefore be classified in order of relevancy (according to P d ). The first priority (relative) which criteria are more important and the second one (assigned) corresponds to the priority/weight value (between 0 and 1) computed by the criterion. The 3 criteria used in our approach are: (1) Enumeration, (2) Contextual and (3) Model-based. In the first one, an agent enumerates data that he considers as useful (i.e. data that he recommends to attach to the product). Φ e is 0 or 1 depending on whether the data is enumerated or not (section 3.2 details what is an enumerated data). The second criterion (Contextual ) can be used to include

End of Life

Dismantlers & Recyclers

Step 7 Step 6

Step 5

Step 4

Step 3

Step In fact, this criterion needs to compute distances between a reference table A and any other table B. Indeed, the shorter the distance between tables, the higher the data correlation. The distance corresponds to the shortest path to reach B from A (i.e. the number of relation which separate them). For instance, let MaterialLot be the reference table A and MaterialClass be the table B in Fig. 2. The distance between both tables equals 2 (relations ①-③). Note that the reference table is defined as that which includes i p . This table is at the centre of our concerns and then, the weight Φ m would decrease as the modeled distance increases. Chan and Roddick propose the formula:

Φ m = k -a with k ∈ [1; ∞] a constant, a ∈ N the distance.
As mentioned previously, ρ x and Φ x (with x the given criterion) are combined in a single formula (equation 1), which gives a prioritization P d for each data item, where len d is the length (e.g. in byte) of the data item. The ρ value for each criterion (given the importance of this one) may be accommodated by the system designer.

P d = x ρ x .Φ x ln (len d + 1) (1)
The next section details when and how to contextualize/enumerate information during the product lifecycle. Moreover, It is necessary to define a protocol to identify which tuples are relative to this product in order to assess only this information (subject of section 3.3).

Contextual and Enumerated adjustments

This section details when and how data are contextualized and enumerated during the product lifecycle. ISO (2003b) defines a project as: a unique process, consisting of a set of coordinated and controlled activities with start and finish dates, undertaken to achieve an objective conforming to specific requirements. Fig. 3 gives a global view of a product lifecycle consisting of several steps (Step 1 to 7) which in turn, are composed of organized activities. In our method, the contextual weight adjustment (for a given product) is done before the product begins its physical life, through an "Expert consensus". It consists in defining the importance of a group of entities (data) for each step. Indeed, specific entity groups may be identified through the LDM. In fact, information relative to the product is quite often scattered within organizations: it is a matter of materials adopted, of applications used to manage technical data (e.g. Product Data Management systems -PDM), of applications that manage business and product information (e.g. Enterprise Resource Planning -ERP) and so on.

Let us note that models ensuring the interoperability of these systems have emerged like IEC 62264, B2MML, ISA-88 [START_REF] Baïna | Product oriented modelling and interoperability issues[END_REF]]. Moreover, some works through the literature emphasized when information related to such systems has an interest regarding the product and the process (e.g. data from PDM is highly important at the beginning of life for both the product and the process, ERP all along the product lifecycle, etc.). Accordingly, the definition of the entity groups and the contextual weight adjustment could be performed based on such recommendations [START_REF] Terzi | Product lifecycle management-from its history to its new role[END_REF]]. Once all entity groups are defined, the weight adjustment for each one may be performed. Fig. 4 gives insight into what could be the weight pattern for 4 distinct groups of entities regarding each lifecycle step. For instance, the "Expert consensus" strongly recommends to provide to the users, information related to Entity group 1 at step 1 and 6. In opposition, data related to Entity group 1 at step 4 will likely not be useful for the actors. The relevance levels defined through the terms strong, high, medium and weak correspond, in fact, to values between 0 and 1. Note that the weight related to a given group impacts all entities/attributes involved in that one. The following ones are proposed in an arbitrary way: Φ c (weak )=0.1, Φ c (medium)=0.3, Φ c (high)=0.6 and Φ c (strong)=1. Let us note that the current method does not allow to deal with several opinions and thus with disagreement among experts. As a result, works subsequent to this paper have been led to design a method for collecting a multitude of opinions and then, to fix the most suitable values. This method is based on a fuzzy-AHP approach.

Entity group 4

Entity group 3

Entity group 2

Entity group 1

Step

Step

Step

Step The enumerated weight adjustment is achieved at each step by an agent expert in his own field. He knows better than anyone which information relative to his product could be useful for the subsequent actors. However, he has generally a short knowledge regarding the entire product lifecyle and consequently, he could omit information relevant to other actors. As a result, the contextual criterion enables to moderate and to balance the enumerated one. Thus, if the agent moves in the direction of the contextual specifications, the data relevance (i.e. the prioritization P d ) will increase and, if not, will be moderated. Regarding the enumerated weight adjustment, the agent specifies the class attributes he expects to see stored on the product: Φ e is 1 when an attribute is enumerated and 0 otherwise.

With regard to the model-based criterion, nothing needs to be specified by a human since only the LDM structure is taken as input to compute Φ m .

Protocol for identifying data relative to the product

The purpose before performing the assessment method (i.e. the prioritization computation via equation 1) is to retrieve all tuples/instances from all relational tables which are related to a given product. After that, computations will be exclusively applied on this set of data. In our approach, the idea is to extract when the time comes (i.e. when the framework is implemented in a given activity to write data on the product), all tables in a matrix format and then, to explore them thanks to an algorithm named RetrievedData (see Algorithm 1). It aims to retrieve all tuples from both the initial instance i p and the set of tables T . The program output provides the list Lt of all tuples (through the entire LDM) which are related to i p . Due to a lack of space, the subfunctions ExplorePK, ExploreSK, Neighbor used in Algorithm 1 are not detailed, but we implement RetrievedData on a basic example.

Algorithm 1. RetrievedData(T , ip) Variables: T : the set of tables composing the LDM; T e: contains the tables already explored; I: contains data items which need to be explored (I k : k th element); I ′ : contains data items which need to be explored for a given table ;  Lt ′ : list of tuples (of a given table) related to ip; N : contains tables (not explored yet) neighboring of tables explored; Output: Lt: list of tuples (through the entire LDM) related to ip;

1: I ← I ∪ {i p } 2: Lt ← ∅ 3: T e ← ∅ 4: while I = ∅ do 5: while I = ∅ do 6: [Lt ′ , I ′ ] ← ExplorePK(T , I 1 ) 7:
Lt ← Lt ∪ Lt ′ 8:

I ← I ∪ I ′ 9:
T e ← T e ∪ I 1 10:

I ← I -I 1 11:
end while 12:

N ← Neighbor(T e)

13:

I ← I ∪ ExploreSK(T , N ) 14: end while

The function named ExplorePK(T , I k ) returns both the set of tuples Lt ′ related to the data item I k (tuples belonging exclusively to the table containing I k ), and the list I ′ of data items which remain to be explored. Note that ExplorePK may not be sufficient to explore the entire LDM. Accordingly, a function named ExploreSK is introduced in order to avoid such a break. It returns new data Fig. 5. Tuples retrieving via RetrievedData items which will be used again as input into ExplorePK. ExploreSK(T , N ) requires, as input, the set of tables N not explored yet, which are directly linked to tables already explored (T e ). T e is provided by Neighbor(T e). To better understand Algorithm 1, consider 3 tables in Fig. 5: MaterialLot, MaterialDefinition, ManufacturingBill (respectively noted MatLot, MatDef, ManBil in the algorithm steps given below). RetrievedData(T , i p ) is then implemented where i p is defined as the data item LPB61 which refers to the primary key (PK) of MatLot (noted {MatLot:row2,col1} in the algorithm steps). A tuple is noted by the row number (e.g. {MatLot:row2}) and an algorithm step (line x) refers to the algorithm line number: In line 1:

I={MatLot:row2,col1}; In line 7:

Lt ′ ={MatLot:row2} , I ′ ={MatDef:row2,col1};

➥ First, the entire tuple related to ip is returned (i.e. MatLot:row2).

Secondly, the function checks if there are secondary keys (SK) in the current table. If so (there is IDMatDef), the function select in tables related to SK (i.e. the table MatDef) the data item for which PK is equal to that one (i.e. MatDef:row2,col1 which has for value MDP-B).

In In line 14: I={ManBil:row1,col1; ManBil:row3,col1};

➥ At this step, the algorithm is blocked since we cannot explore any other table. As a result, ExploreSK aims at returning new data items (if possible). It checks first in tables belonging to N if there are SK. If so (2 SK are identified in ManBil), it matches the identified SK with the PK of tuples belonging to Lt in order to determine if there are similar keys. If so (it is the case with MDP-B), the data item (PK) relative to the new tuples (i.e. MBC-C2 and MBH-H2) are returned.

In line 7:

Lt ′ ={ManBil:row3} , I ′ = ∅; and so on

In resume, the method to determine relevant product data consists at each step of the product lifecycle, in identifying all tuples which are somehow related to the product (via Algorithm 1) and then, in computing the data relevance (via equation 1). For that, two weight patterns need to be specified by human experts (enumeration/contextual) and one (Model-based) is based on the LDM structure.

CASE STUDY

Scenario definition and specification

In our case study, a specific LDM is implemented which is based in part on the B2MML standard 3 ISO (2003a). The model used in this paper consists of 19 entities (extracted from B2MML) which are clustered into 4 groups, namely:

• Product data group: MaterialLot, MaterialDefinition, MaterialClass, ManufacturingBill, ActualMaterialLot, MaterialSegmentSpecification,

• Personal data group: Person, ActualPersonSegment, PersonClass, PersonSegmentSpecification,

• Production data group: ProductionOrder, SegmentRequire- ment, SegmentResponse, ProductSegment, ProductDefinition,

• Equipment data group: Equipment, EquipmentClass ActualEquipmentSegment, EquipmentSegmentSpecification,

The Equipment and Personal data groups report information about equipments and persons which/who are somehow related to the product (e.g. equipments used for manufacturing it). The Product and Production data groups relate respectively information about the product composition (e.g. raw materials) and operations (e.g. production rules). Fig. 5 illustrates 3 of the 19 entities, which belong to Product data group.

Let us assume that the "Expert consensus" has defined the contextual weight pattern as shown in Fig. 4, where "Entity group 1, 2, 3, 4" correspond respectively to the Product, Personal, Production and Equipment data groups.

Moreover, the agent in step 7 enumerates the table attributes listed in Table 1. These patterns are defined for any lot instance of blue textile pieces. The LDM is not shown in this paper but the distance values will be specified when needed for calculations.

Table 1. Henceforth, the identification method can be applied. Assume now that the product is being treated in a given activity of step 7 (see Fig. 3) and that the machine performing the operation needs to write information on that one. For that, the machine gets the product lot instance i p =LPB61 and runs the identification method: first, all tuples (Lt) are retrieved via Algorithm 1, as explained in section 3.3 (cf. Fig. 5). The weight patterns of each criterion is now matched with this set of tuples. Fig. 6 Regarding now the last matching (Model-based), the weight is equal to k -1 because the distance between MaterialDefinition and MaterialLot 4 equals 1 (see Fig. 2). Calculations are then performed for each data item of each table via equation 1 (see the example P 2,1 in Fig. 6). In our case study, k is fixed to 2 and the criterion importance ρ e , ρ c , ρ m respectively to 100, 75, 50 (as defined by Chan et al.).

Enumeration pattern

Contextual pattern

Model-based pattern Fig. 6. Matching between tuples and weight patterns

Results about data relevance

In this section, we comment the results of the data item relevance obtained after calculations. The term list is used in what follows to refer to all data items having a prioritization P d > 0. Fig. 7(a) provides the resulting list ordered from the highest P d to the smallest. The most relevant data item is the one located at row 2, column 4 in MaterialLot (cf. Fig. 5). Due to the large amount of data items included in the list (around 230), we the results in the form of diagrams (pie chart and wisker diagram). First, let us look at the wisker diagram Fig. 7(b). For each table is given the min, the 1 st /3 th quartile, the mean and the max P d of the set of data items included in the list and belonging to the table. We can see that the highest prioritizations (in average) are relative to MaterialLot (which includes the 1 st data item of the list : P d = 191.15), but also to MaterialDefinition, ProductSegment, ProductionOrder. This is due to the fact that some attributes of these tables are enumerated (cf. Table 1) in addition to a high and strong recommendation by the "Expert consensus" regarding respectively the Product and Production data group (which contain these four tables). Let us focus now on the pie chart Fig. 7(c) which is another representation of results. The equation P er gr provided in Fig. 7(c than the other due to the enumeration choices and the "Expert consensus" decisions. In opposition, Personal data group is not relevant (with 2%) since there is no enumeration and no high recommendation from the "Expert consensus" (Φ c =weak ). The identification method is now applied by taking into account the contextual specifications of Step 2 (cf. Fig. 4), with the same enumeration pattern (cf. Table 1). The Personal data group is now relatively important compared to Step 7. Indeed, there is still no enumeration but now, the "Expert consensus" recommends highly to provide information relative to this group. In resume, if the agent moves in the direction of the contextual specifications, the data relevance (P d ) will significantly increase and, if not, will be balanced. Finally, it can be concluded, regardless the physical system performance (i.e. the step 3), that data items at the top of the list have a high probability of being stored on the product in opposition to the ones at the bottom (see Fig. 7(a)).

CONCLUSION

Concepts such as Internet of Things, Ubiquitous Computing redefine how we interact with the information. It is therefore necessary to control the different ways information is diffused. To do so, a four-step data dissemination methodology in the framework of the Supply Chain Management is introduced in this paper, and one of these steps is then detailed. It aims at determining which information could be stored on the manufactured product and, to assess what would be their relevance (according to the context). This is achieved via an identification method which is applied on a case study. Current works are lead in order to achieve the four-step integration.

Fig. 3 .

 3 Fig. 3. The various weight adjustments throughout the product lifecycle data related to the user's details or environment. Indeed, knowledge of the context of use can be useful in inferring the data that may be needed by users. The weight range Φ c is detailed in section 3.2. The Model-based criterion is based on the relationships implied through the LDM.In fact, this criterion needs to compute distances between a reference table A and any other table B. Indeed, the shorter the distance between tables, the higher the data correlation. The distance corresponds to the shortest path to reach B from A (i.e. the number of relation which separate them). For instance, let MaterialLot be the reference table A and MaterialClass be the table B in Fig.2. The distance between both tables equals 2 (relations ①-③). Note that the reference table is defined as that which includes i p . This table is at the centre of our concerns and then, the weight Φ m would decrease as the modeled distance increases. Chan and Roddick propose the formula:Φ m = k -a with k ∈ [1; ∞] a constant, a ∈ N the distance.As mentioned previously, ρ x and Φ x (with x the given criterion) are combined in a single formula (equation 1), which gives a prioritization P d for each data item, where len d is the length (e.g. in byte) of the data item. The ρ value for each criterion (given the importance of this one) may be accommodated by the system designer.

Fig. 4 .

 4 Fig. 4. Contextual Weight adjustment

:

  model exploration based on Primary Keys (cf. function ExplorePK) : model exploration based on Secondary Keys (cf. function ExploreSK) : initial instance ip provided by the machine PK,SK : tuples/instances related to the initial instance : means "Primary Key" & "Secondary Key"

  line 8 Lt={MatLot:row2}; In line 9-10: basic operations (memory effect); In line 11: I={MatDef:row2,col1}; In line 7: Lt ′ ={MatDef:row2} , I ′ = ∅; In line 8 Lt={MatLot:row2; MatDef:row2}; In line 11: I = ∅; In line 13: N ={ManBil}; ➥ ManBil is a neighbor of MatDef and has not been explored yet.

  (a) List of data items ordered from the highest P d to the smallest

Table :

 :

			PK		Material Lot	SK
			IDLot Description		StatusQuantityIDMatDef
		1	LBB01 Consists of blue Bobbins	Full	8	MDB-B
		2	LPB61 Consists of blue Textile Pieces	Full	50	MDP-B
		3	. . .		. . .		. . .	. . .	. . .
			PK	Table: Material Definition
			IDMatDef Description		Value
		1	MDB-B Textile bobbin of blue color Blue
		2	MDP-B	Textile piece of blue color Blue
		3	MDP-R	Textile piece of red color	Red
		4	. . .		. . .		. . .
		PK		Table: Manufacturing Bill	SK	SK
		IDManBilDescription	Quantity IDMatDef IDProdDef
	1	MBC-C2 Materials required to de-sign cushion of type C2	3	MDP-B	PS101
	2	MBH-H1 . . . to design headrest H1	1	MDY-1	PS001
	3	MBH-H2 . . . to design headrest H2	8	MDP-B	PS332
	4	. . .			. . .	. . .	. . .	. . .

  Table attributes enumerated in step 7

  depicts for MaterialDefinition the matching result "data/pattern" for the 3 criteria. All tuples without any relation with i p are set to 0. Regarding the enumeration matching, the attributes IDMatDef and Value are set to 1 because they are 3 B2MML (Business To Manufacturing Markup Language) is meant to be a common data format to link business enterprise applications (e.g. ERP) with manufacturing enterprise applications (e.g. MES). enumerated (cf. Table1), in opposition to Description. Regarding the contextual matching, all attributes are set to 0.8 since the "Expert consensus" has specified a high level at Step 7 for the group 1 (i.e. Product data group), which contains the table MaterialDefinition.

Table giving

 giving

			Assessed Table: Material Definition
		IDMatDef Description	Value
		MDB-B Textile bobbin of blue color Blue
		MDP-B	Textile piece of blue color Blue
		MDP-R	Textile piece of red color	Red
			. . .		. . .		. . .
				Matching with the weight patterns
	IDMatDef Description Value	IDMatDef Description Value
	0	0	0			0	0	0
	1	0	1		k -1	k -1	k -1
	0	0	0 IDMatDef Description Value 0	0	0
	. . .	. . .	. . . 0	0	. . . 0	. . .	. . .
			0.8	0.8	0.8
			0		0	0
			. . .		. . .	. . .
						the data relevance
					IDMatDef Description Value
	P 2,1 = 1×ρe+0.8×ρc+k -1 ×ρm ln(len(MDP-B)+1)	P 1,1 P 2,1	P 1,2 P 2,2	P 1,3 P 2,3
					P 3,1	P 3,2	P 3,3
					. . .	. . .	. . .

  ) allows to compute the percentage relative to an entity group gr, where len(list) is the number of data items into the list and P d k is the

	Rang 1 st 2 th 3 th	Table Name MaterialLot ManufacturingBill ManufacturingBill	Attribute Name Quantity (col4) Quantity (col3) Quantity (col3)	Primary Key Value LPB61 (row2) MBH-H2 (row3) MBC-C2 (row1)	Cell Value 50 8 3	Relevance (P d ) 191.1502 112.6170 112.6170	High probability that data items are attach-ed to the product
	. . . 224 th	. . . ActualPersonSegment	. . . Unit of Measure (col3)	. . . MBH-H2 (row3)	. . . 8	. . . 1.7441	Lesser probability of being attached
	225 th	PersonClass	Description	PCPLW01	Worker Line...	0.9313	to the product

Table name (

 name b) Result of Step 7 detailed for each table in a wisker diagram Result of Step 2 and 7 in form of a pie chartFig. 7. Results of the data item relevance prioritization value of the data item k. A high group percentage might mean two things: (1) P d values relative to data items belonging to the group are relatively high compared to the rest of the list ; (2) a large majority of data items belong to the group. The pie chart (Step 7) clearly reflects the previous explanations, where the product & production data groups are more relevant (37% and 47%)

		14%
	7
	Step	37%	47%
		2%			Product Group
		22%			Personnel Group
	Step 2	28%	32%	Production Group Equipment Group
		18%
		P er gr =	len(list) k=1	P d k |d k ∈gr P d k	× 100
	(c)

we assume that a common data model exists between the actors of the product lifecyle, which once derived gives rise to a LDM.

it refers to a table cell (i.e. the intersection of a given tuple/row and a given attribute/column of a relational table).


Duong Dang

Florent Lamiraux

Jean-Paul Laumond

A framework for manipulation and locomotion with realtime footstep replanning

Keywords: locomotion, footsteps, replanning, realtime, visual servoing

This paper focuses on realization of tasks with locomotion on humanoid robots. Locomotion and whole body movement are resolved as one unique problem. The same planner and controller are used for both stages of the movement. Final posture and footprint placements are found by resolving an optimization problem on the robot augmented by its footprints. Footstep replanning is done in realtime to correct perception and execution errors. The framework is demonstrated with the HRP-2 robot in a number of different scenarios.

I. INTRODUCTION

L OCOMOTION and manipulation are among the most exciting topics in humanoid robotics research. Numerous works have been carried out in the past years in walking and running generation [START_REF] Sugihara | Real-time humanoid motion generation through zmp manipulation based on inverted pendulum control[END_REF]- [START_REF] Kagami | A fast dynamically equilibrated walking trajectory generation method of humanoid robot[END_REF], notably with the introduction of the zero momentum point (ZMP). On manipulation, task-based methods have been developed since the eighties of the last century for industrial robot and robotic arms, [START_REF] Nakamura | Taskpriority based redundancy control of robot manipulators[END_REF], [START_REF] Khatib | A unified approach for motion and force control of robot manipulators: The operational space formulation[END_REF]. These methods have been extended to humanoids in recent years as more and more robots have been made available for research [START_REF] Ott | A humanoid two-arm system for dexterous manipulation[END_REF]- [START_REF] Gienger | Task-oriented whole body motion for humanoid robots[END_REF].

While both locomotion and manipulation generate on their own great interests for research and can be treated separatedly as is often the case, it is intriguing how much one can extend the capability of robots when combining these two problems in the same context. With locomotion coupled with manipulation, the robot is no longer constrained to manipulate only objects in its workspace. In fact, the workspace is extended with locomotion that just becomes another task. In addition to creating new capability and new task, there is a real need to build the bridge between locomotion and manipulation. There are many cases where the coupling is so important that one cannot separate both problems. A humanoid robot might need to make steps before manipulating some objects. A dynamically demanding manipulation scenario might require that the robot end up at some exact configuration at the end of the locomotion stage. For instance, to manipulate an object at ground level, constraints have to be put on feet placement and affect the way locomotion should be conducted.

Resolving locomotion and a complex upper body manipulation is, however, not a simple task in practice. Typically, a computationally expensive planning stage is involved at first. The resulting plan may be expressed either in configuration This work was not supported by any organization D. Dang, J-P. Laumond and F. Lamiraux are with CNRS, LAAS, 7, avenue du Colonel Roche, F-31077 Toulouse, France. nddang@laas.fr Footprints replanning during locomotion in a waling-grasping scenario on HRP2.

(Videos available at http://homepages.laas.fr/nddang/humanoids2011) space, which can be executed directly on the robot, or in terms of tasks to be given to the controller. Yet, no sensing system is perfect, the information obtained at the planning stage is usually different from reality. In addition, execution errors, due for instance to sliding while walking make open loop execution unrealistic. As a consequence, correction has to be done online. This is a challenging task since a time-consuming replanning can prevent the robot from being reactive. Online generation of footsteps have been studied previously by several research groups [START_REF] Chestnutt | Footstep planning for the honda asimo humanoid[END_REF]- [START_REF] Perrin | On the problem of online footsteps correction for humanoid robots[END_REF] but usually in the context of a decoupled locomotion problem.

In this paper, a framework is proposed to treat both manipulation and locomotion with online replanning. Sources of errors such as perception system, execution error, moving objective are taken into account online by the motion planner, which in turn, produces in real time up-to-date instructions to the controller in the form of task space trajectories for the feet (steps) and for the upper-body (manipulation).

Approach and contribution

The motion planner in this paper extends the work of Kanoun et al. [START_REF] Oussama Kanoun | Prioritizing linear equality and inequality systems: application to local motion planning for redundant robots[END_REF], [START_REF] Kanoun | Planning foot placements for a humanoid robot: A problem of inverse kinematics[END_REF], where robot motion is resolved in the form of an optimization problem. The humanoid robot is augmented by its footprints and tasks are expressed on this this augmented robot. Modifications have been made to the initial method in order to make it run on-line. First, instead of resolving the problem in the configuration space of the robot, only an intermediate state of the resolution is performed and fed to the controller: namely final posture and foot placements during walking.

The main contribution of this paper is the integration of the method described in [START_REF] Oussama Kanoun | Prioritizing linear equality and inequality systems: application to local motion planning for redundant robots[END_REF] achieves real time replanning during walking. The entire framework is then validated with a number of different scenarios on the dynamic simulator OpenHRP and validated on the real robot with the scenario described in Section IV-C (Figure 1).

II. IMPLEMENTATION

A. Architecture overview

Figure 2 depicts how different components interact with each other. At first, a complete plan is made and fed to the system. This is done only once hence the dotted arrow. In the execution loop, images from the robot cameras are transmitted to the perception module. This module analyses the images to detect and localize objects of interest in the environment with respect to the robot. The visual servo uses 3D position of tracked object to replan in real time upcoming footprints and upper body tasks (hand task, posture task, etc.). Footprints are passed to a preview controller which also computes trajectories of critical operation points of the lower body, which is responsible for walking or keep the robot balanced while standing, namely, trajectories of left foot, right foot and the center of mass. The controller combines these tasks all together within a prioritized stack and computes the appropriate control signal that is sent to the robot. Since the controller makes no distinction between walking and object manipulation, it only executes tasks, there is no "gap" between the walking and manipulation stages.

B. Footstep and posture planning

The core of the plannner is the resolution of a hierachical system of inequality and equality tasks [START_REF] Oussama Kanoun | Prioritizing linear equality and inequality systems: application to local motion planning for redundant robots[END_REF], [START_REF] Kanoun | Planning foot placements for a humanoid robot: A problem of inverse kinematics[END_REF]. The special feature of this approach is the possibility of having inequality tasks in higher priority than equality task. This is extremely helpful in humanoid robots where a lot of contraints have to be expressed as inequality tasks.

1) Prioritized linear and inequality systems: Considering a system of linear equalities and inequalities:

Ax = b (1) Cx ≤ d (2)
for which the solution can be expressed as an optimization problem

min x∈Ω,w∈ℜ n 1 2 ||Ax -b|| 2 + 1 2 ||w|| 2 (3)
subject to

Cx -w ≤ d (4)
In an prioritized linear system, one can resolve 3 iteratively at each level as follows:

S 0 = ℜ n (5)
S k+1 = arg min min x∈Ω,w∈R n 1 2 ||Ax -b|| 2 + 1 2 ||w|| 2 (6) subject to C k x -w ≤ d k (7)
In robotics, a task is typically represented by its Jacobian J. The classic example is a position task in operational space with T (q) = 0 is the goal and T (q) = c the current error. The solution q to achieve exponential convergence c = C 0 exp(-λt) is written as

J q = -λc , J = ∂T ∂q (q) (8)
Other tasks can be written as inequalities T (q) ≤ 0 such as collision and self-collision avoidance, joint limits, etc ˙. The resolution of a prioritized set of task can be computed by: Find q * ∈ S k :

S 0 = ℜ n S i = arg min q∈Si-1 1 2 ||J i q -e i || 2
for equality tasks

S i = arg min w, q∈Si-1 1 2 ||w|| 2 s.t. J i q -e i ≤ w
for inequality tasks

2) Application to footstep planning: As explained earlier, the determination of footsteps and final posture defining the motion executed on the robot is achieved in one problem by using the previous resolution of equality and inequality system. The main idea of this approach is to add a virtual joint (Figure 3) with three degree of freedoms for each step. Let us consider a robot of n degrees of freedom executing k steps, the resulting virtual kinematic chain adds 3k degrees of freedom to the real robot to form a n + 3k d.o.f. kinematic chain. Constraints on how far the robot can physically step or turn become joint limits for theses new joints. The constraints that the robot should not step one foot on one another becomes auto-collision avoidance. On this new robot with this set of constraints in addition, a set of appropriate tasks can then be applied, namely: • inequality constraints, in order, joint limits, projection of the center of mass, self-collision avoidance of robot, selfcollision avoidance for the virtual manipulator, position and orientation of the supporting foot • object manipulation task. e.g. grasp, reach for an object with 2 hands, etc. • parallel task for the upper body during walking,

• gaze task (keep objects of interest in the vision field). Figure 5 depicts how the upperbody task "attracts" the augmented robot hence initiate footeps. The last n degrees of freedoms in the result represent the final posture, and the final position of the virtual kinematic chain represents footsteps. The complete motion in configuration space can then be found by passing the footsteps to a preview controller which output trajectories for left foot, right foot and the center of mass. These trajectories in turn, in addition with the upper body task at the final step can be given as equality tasks to the prioritized stack. The resulting motion is therefore never computed before-hand. It is instead the result of the control architecture.

Determine the number of steps: In the previous section, it was assumed that the number of steps k was known before hand. However, the target detected by the vision system can be found in a wide range of distance. Therefore, it is difficult to guess in advance how many steps the robot should make. One important point in this section and also the first modification made on this paper to the original method is the fact this parameter k can be found automatically by the optimizer. The algorithm is summarized as follows:

Figure 5. depicts the exploration of the virtual kinematic chain in space.

III. ONLINE FOOTSTEP REPLANNING

One big challenge in our context is the use of stereo-vision to detect and localize objects. Localization errors grow dramatically with the distance between the object and the sensor. Usually, this distance is maximal in the initial configuration of the robot, when motion planning is performed. The resolution to a complete motion in joint space described in previous section typically takes up to one minute for a long motion. Yet, to be reactive, replanning should finish at least once every stepping interval of the robot (typically under a second). It is clear that replanning the motion up to configuration space motion is not feasible in practice.

A. Footsteps and final posture replanning

As explained ealier intermediate results, i.e. final posture and footsteps, of the planning stage are sufficient for the controller. This is where replanning becomes feasible since the computation of footsteps and posture is typically from 3 to 10s, a replanning could be well below 1s and hence guarantee reactivity. The augmented robot then starts at previous state and update its tasks according to new sensory information about landmarks. Algorithm 2 describes the stages of planning, the results are shown in Figure 6. The solver converges more quickly than planning footsteps and posture from initial position since the current configuration is already closed to the goal configuration. Table I shows replanning time for a grasping task with goal as a ball on the ground at a distance around 2 meters. The modification is taken randomly in arbitrary directions.

TABLE I CPU TIME FOR REPLANNING OF FINAL POSTURE AND FOOTSTEPS (MILISECONDS) FOR A LOCOMOTION-GRASP TASK (FIGURE 1)

The replanning process for the whole-body and footsteps depends greatly on configuration and it is not guarantied a computing time less than stepping time (0.8s). Without modification, small corrections (e.g. due to drifting) can be dealt with. Otherwise, an execution strategy must be applied at the planning-control bridge to deal with large errors, such as the case of stereo vision system.

Stop and go: One obvious approach to address the realtime issue is to stop the robot or let it step in place if the planner takes too long to response.

Interative optimisation: As shown in Section II-B, the complexe robot tends towards the goal during the optimisation process. At early stages, i.e. when the robot starts, having the full solution with all footsteps and final pose is not necessary. In fact, even a full solution is found, it is highly likely that this solution will change during walking motion to compensate sensory errors. The planner can keep up with the controller by only replan, at each correction, to an intermediate state. Namely, line 14 in Algorithm 2 will be modified to: "replan to new solution or timeout", where the timeout chosen is one stepping period.

While stop and go strategy guarantees optimised trajectory at each replanning stage, it produces unnatural movements on the robot. Using interative approach, the robot does not have to stop while correcting its paths towards the new goal. However, this method relies on the assumption that the intermediate 1) stage found at each timeout is safe for the robot.

As it turns out, there exists a third strategy which consists in reducing the dimension of the optimisation problem in replanning stage by blocking some or all joints belonging to the upper body. At each replanning step, optimised foot placements and posture are found without compromising the time constraint. Without having to interupt the optimisation process at each timeout as the second approach, this method is also simpler to implement on the robot. This thrird strategy is chosen for experiement and is detailed in the following section.

B. Realtime footstep replanning

While footsteps have to be changed to correct execution drift or perception error, the posture does not. In fact, unless new obstacles are found near the goal the previous posture stays valid. For example, if the robot is to approach and open a door, even the position of the door on its reference has change, the previous posture still guarantees dynamic equilibium. This scenario covers most cases in experiment. The most part of the last n degrees of freedom of the the augmented robot can be 'frozen' while other joints are free to move. Suppose l degrees of freedom are locked. This translates into reducing the dimension of the Jacobians, hence the complexity of the problem.

Table II shows replanning time in a grasping scenario similar to the one described in previous section with the posture of the standing robot "frozen". This is the other extreme case compared to Table I where every joint in the standing robot is free to move. In the first replanning scheme, the robot can barely correct small errors, so the robot has to make many small corrections at a time, hence a large amounts of supplement steps have to be added to the locomotion stage. In the second replanning schema however, the replan time is much less than time necessary for the robot to make a step. This guarantees a realtime replanning running behind the scene and updating robot footprints continuously.

Extension to footstep replanning of an arbitrary initial path:

In cases where all upper-body joints are blocked in the replanning phase, this method can be extended to a variety of motion. In fact, the inputs for the planner is just initial footsteps and postures, which can be given by a different planner than the one described in section II-B, for example, an RRT planner. The robot can therefore deals with more complexe cases, typically scenarios where the optimisation method fails due to local minima, for example, a long wall is placed between the robot and goal.

C. Control

With the plan (final posture and footsteps) being updated in realtime, it is up to the controller to executed the plan. In this framework the "stack-of-tasks" [START_REF] Mansard | Task sequencing for high-level sensorbased control[END_REF]- [START_REF] Stasse | Real-time (self)-collision avoidance task on a hrp-2 humanoid robot[END_REF] is used. The principle of task-based control is similar to the formulation of optimisation problem in Section II-B.

In this framework the control law qi is written as following:

qi = -λJ + i e i (9)
J + i is the pseudo-inverse of the Jacobian J i [START_REF] Khatib | A unified approach for motion and force control of robot manipulators: The operational space formulation[END_REF]. e i is the difference between desired feature s * i (i.e. a position in operational space, a posture, etc. ) and its current value s i :

e i = s i -s * i (10)
The control law on a set of tasks is written [START_REF] Siciliano | A general framework for managing multiple tasks in highly redundant robotic systems[END_REF]:

qi = qi-1 + λ i J+ i ( ėi -J i qi-1 ), q1 = λ 1 J+ 1 ė1 (
11) when Ji is the projection of J i in the null space of the augmented Jacobian

J A i = [J 1 , J 2 , . . . J i-1 ] T (12) Ji = J i P A i-1 , P A i = I -(J A i ) + J A i ( 13
)
J+ 1 is simply J + 1 .
One recovers ( 9) if there is one task in the stack. This formulation guarantees that the task at ith stage does not disturb the previous tasks, i.e. with higher priority. It allows, for instance, to realize a reaching movement without moving the center of mass, which is required for stability.

1) Application: In the controller perspective, there is no difference between walking and manipulating an object. Each of those stages is just a collection of tasks. Figure 7. depicts the corresponding stack in the two cases.

a) Walking: To ensure the dynamic equilibrium of the robot during walking, a preview control on the Zero Moment Point (ZMP) is used. The principle of this approach is to use an inverted pendulum model [START_REF] Kajita | The 3d linear inverted pendulum mode: a simple modeling for a biped walking pattern generation[END_REF], the mass of the pendulum being that of the robot positioned at the height of the center of mass. The dynamic walking of a humanoid robot is b) Upper body manipulation: Object manipulation is done in a similar manner. In fact, using the stack-of-tasks manipulation and walking are merged in the same framework. Stability in the manipulation phase is ensured by the fact that the task of the center of mass is at highest priority, just like in the locomotion phase.

One last issue is the situations depicted in Figure 8. In these cases, simply adding the grasping task at the same time as posture task, the controller might try to get the hand the fastest possible to the goal and the hand gets stucked behind the body. The remedy here is activating the posture task first, then using a simple heuristic to activate hand task only after sometime at an appropriate time. In practice, placing a threshold on the hand task error and activating the hand task accordingly provides good results.

IV. EXPERIMENTS

Described here are some scenarios with the humanoid robot HRP-2 using the proposed method.

A. Reach and open a door

In this scenario, (Figure 9) the robot has to walk towards a door, reaching for the handle and pull to open the door by walking backwards.

B. Catching a flying balloon

The robot must follow and catch a falling balloon. (Figure 10). No assumption is made about the dynamics of the balloon. The robot simply try to place its hands at certain height at the right position to catch the ball. In simulation, a user alters the wind condition to change the trajectory of the balloon hand changing robot planned motion online.

C. Grasping a moving ball on the ground at distance

This example illustrates probably the best the connection between locomotion and manipulation since precise conditions have to be met for the robot footsteps to make the grasping

V. CONCLUSION REMARKS AND FUTURE WORKS

A generic method for footstep and posture planning and real time replanning has been presented in this paper. Numerous scenarii have demonstrated the applicability of this framework. All demonstrated motion have been tested dynamically with the simulator OpenHRP. On the real robot, the goal dectection and tracking using using CAMShift [START_REF] Bradski | Conputer vision face tracking for use in a perceptual user interface[END_REF] algorithm acts as the perception module. Experiments have been conducted on the robot with HRP-2 following and reaching a ball on the ground, with the goal eventually moved during experiment.

Expansion can be made to this scheme of footsteps replanning in more dynamically intensive cases, e.g˙catching a volleyball instead of a balloon. In this cases, more precise model for the ZMP will have to be investigated to make fast steps possible. Modifications will also need to be done in the feasibility constraints of the virtual kinematic chain.

Fig. 1 .

 1 Fig. 1.Footprints replanning during locomotion in a waling-grasping scenario on HRP2.(Videos available at http://homepages.laas.fr/nddang/humanoids2011)

  Fig. 2. Architecture

Fig. 3 .

 3 Fig. 3. Virtual kinematic chain

Fig. 5 .

 5 Fig. 5. Find the number of steps automatically by the optimizer

Fig. 6 .

 6 Fig.6. Footsteps replanning

Fig. 7 .

 7 Fig. 7. Stack of task during walking (left) and manipulation (right)

Fig. 8 .

 8 Fig. 8. Blocking position due to reaching task

Fig. 9 .

 9 Fig. 9. Reach and open a door

Fig. 10 .

 10 Fig. 10. Catching a flying balloon

  Algorithm 1 Footsteps planning with variable number of steps Require: initial position. Require: manipulation task. Require: obstacle positions. Ensure: footprints and final posture Initialize solver with 0 virtual link. repeat Solve the optimization problem. if Reach local minimum then Add new virtual link end if Check manipulation task error until goal reached