Lyes Touati
email: lyes.touati@hds.utc.fr

Yacine Challal
email: ychallal@hds.utc.fr

Batch-Based CP-ABE with Attribute Revocation Mechanism for the Internet of Things

Keywords: CP-ABE, Internet of Things, Access Control, Attribute Revocation, Batch-Based

Ciphertext-Policy Attribute-Based Encryption (CP-ABE) is an extremely powerful asymmetric encryption mechanism, it allows to achieve fine-grained access control. However, there is no solution to manage efficiently key/attribute revocation problem in CP-ABE scheme. Key revocation problem is very important in dynamic environment like Internet of Things (IoT), where billions of things are connected together and are cooperating without human intervention. Existing solutions are not efficient due to their overhead (traffic) and complexity (big access trees). Other solutions require the use of powerful semitrusted proxies to re-encrypt data.

The proposed solution in this paper called Batch-Based CP-ABE reduces the complexity and the overhead, and does not require extra nodes in the system. We propose to split time axis into intervals (time slots) and to send only the necessary key parts to allow refreshing the secrets keys. An analysis is conducted on the way to choose the best time slot duration in order to maximize system performances and minimize average waiting time.

I. INTRODUCTION

Internet of things [START_REF] Atzori | The internet of things: A survey[END_REF] is a new paradigm where many objects that surround us are provided with a unique identifier and sensing, actuating, computation and communication capabilities. These objects can be Radio-Frequency IDentification (RFID) tags, sensors, actuators, smart-phones, etc. All these entities will be able to interact with each other and cooperate together to reach common goals. It is expected that more than 50 billion devices will be connected to the Internet by 2020 (sensors, smart-phones, laptops, cars, clothes, wristwatches, etc.). The Internet of Things is an enabling technology for several applications like smart cities, domotic and home automation (smart homes), smart grid, smart healthcare and remote monitoring etc.

In the Internet of Things, all objects communicate between them without human intervention; Therefore, securing IoT communications is a tricky challenge, especially since security protocols developed for the internet, like IPsec or TSL, are not suitable for IoT environments. Indeed, these protocols have a high overhead that cannot be supported by constrained devices in the Internet of Things.

Attribute-based encryption (ABE) is a public key encryption mechanism that allows users to encrypt and decrypt messages based on descriptive user attributes. There are two main versions of ABE: Ciphertext-Policy Attribute-Based Encryption [START_REF] Bethencourt | Ciphertext-policy attributebased encryption[END_REF] and Key-Policy Attribute-Based Encryption [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF]. In KP-ABE, attributes are used to describe the encrypted data and policies are built into user's keys; while in CP-ABE, the attributes are used to describe a user's private key, and an encryptor determines a policy on who can decrypt the data and include it in the encrypted data.

Ciphertext-Policy Attribute-Based Encryption [START_REF] Bethencourt | Ciphertext-policy attributebased encryption[END_REF] is an extremely powerful asymmetric encryption mechanism, it is a promising cryptographic solution to enforce access control in the Internet of Things. Using CP-ABE allows keeping encrypted data confidential even if the storage server is untrusted.

Key revocation, or more generally, attribute revocation is a challenging issue in the CP-ABE scheme since there are many entities that might match the decryption policy.

In this work, we define a batch-based CP-ABE with an efficient attribute revocation mechanism. Our solution reduces the complexity and the overhead comparing to other solutions, and it does not require proxies to re-encrypt messages.

The remainder of this paper is organized as follows. We discuss related works in section II. In section III we present some preliminaries of our work. We define the AMVVI problem in IV. Our solution is presented in V. Section VI presents a study of the impact of time slot duration on system performances. We conclude our paper in section VII.

II. RELATED WORKS

In [START_REF] Pirretti | Secure attribute-based systems[END_REF], authors gave an idea on how attribute revocation could be implemented. The main idea of their proposition is to add expiration date to each attribute. Once this expiration date comes, the attribute authority rename the attribute and send it to all entities in the system, it regenerates all the secret keys to the non-revoked users (the revocation is materialized by not receiving a new secret key including the renamed attribute).

In [START_REF] Bethencourt | Ciphertext-policy attributebased encryption[END_REF], authors propose a way to transform numerical attribute to non-numeric attribute, by this way, they can express conditions on dates and include the revocation condition into the access tree. But this transformation makes access trees bigger than before, thus, the overhead considerably increases.

In [START_REF] Xu | Dynamic user revocation and key refreshing for attribute-based encryption in cloud storage[END_REF], authors addressed user revocation and key refreshing issue for CP-ABE in data-owner-centric environments like those for cloud storage. Their solution named DURKR uses the proxy re-encryption mechanism (PRE [START_REF] Blaze | Divertible protocols and atomic proxy cryptography[END_REF]), it only considers user revocation and requires a cloud storage provider to re-encrypt a data for every user request.

In [START_REF] Cheng | Efficient revocation in ciphertext-policy attribute-based encryption based cryptographic cloud storage[END_REF], authors considered data storage and delivery system. authors proposed a solution that consists on encrypting a data to be shared with symmetric key and splitting it into several slices via an (n,n) secret sharing scheme.

In [START_REF] Yu | Attribute based data sharing with attribute revocation[END_REF], Yu et al. tried to resolve the challenging issue of key revocation in CP-ABE by considering practical scenarios like data sharing in which semi-trustable on-line proxy servers are available. Their solution integrates Proxy Re-Encryption (PRE [START_REF] Blaze | Divertible protocols and atomic proxy cryptography[END_REF]) technique with CP-ABE and enables the authority to revoke user attributes and to delegate laborious tasks to proxy servers. This solution necessitates to regenerate all users secret keys and re-encrypting data after every change occurred in the system.

III. PRELIMINARIES

In this section we review some basic concepts as well as notions related to CP-ABE scheme [START_REF] Bethencourt | Ciphertext-policy attributebased encryption[END_REF].

A. Access Structure

Let {P 1 , P 2 , • • • , P n } be a set of parties. A collection A ⊆ 2 {P1,P2,••• ,Pn} is monotone if ∀B, C : if B ⊆ C then C ∈ A.
an access structure (respectively, monotone access structure) is a collection (respectively, monotone collection) A of nonempty subsets of {P 1 , P 2 , • • • , P n }, i.e., A ⊆ 2 {P1,P2,••• ,Pn} \ {∅}. the sets in A are called the authorized sets, and the sets not in A are called the unauthorized sets.

B. Access tree

Each non-leaf node of the tree represents a threshold gate, described by its children and a threshold value. If num x is the number of children of a node x and k x is its threshold value, then 0 < k x ≤ num x . Each leaf node x of the tree is described by an attribute and a threshold value k x = 1.

Some functions are defined to facilitate working with access trees:

• parent(x): denotes the parent of the node x in the tree.

• att(x): is defined only if x is a leaf node, and denotes the attribute associated with the leaf node x in the tree. • index(x): denotes the order of the node x between its brothers. The nodes are numbered from 1 to num.

Satisfying an access tree. Let T be an access tree with root r. Denote by T x the sub-tree of T rooted at the node x. Hence T is the same as T r . If a set of attributes γ satisfies the access tree T x , we denote it as T x (γ) = 1. We compute T x (γ) recursively as follows. if x is a non-leaf node, evaluate T x ′ (γ) for all children x ′ of node x. T x (γ) returns 1 if and only if at least k x children return 1. if x is a leaf node, then T x (γ) returns 1 if and only if att (x) ∈ γ.

C. Bilinear Maps

Let G 0 and G 1 be two multiplicative cyclic groups of prime order p. Let g be a generator of G 0 and e be a bilinear map, e : G 0 × G 0 → G 1 . the bilinear map e has the following properties:

1) Bilinearity: for all u, v ∈ G 0 and a, b ∈ Z p , we have e g a , g b = e (u, v) ab .

2) Non-degeneracy: e (g, g) = 1.

We say that G 0 is a bilinear group if the group operation in G 0 and the bilinear map e are both efficiently computable. Notice that the map e is symmetric since e g a , g b = e (g, g)

ab = e g b , g a .

D. Lagrange coefficient

Let i be an element in Z p , and S a set of elements in Z p . We define the Lagrange coefficient as:

∆ i,S (x) = j∈S,j =i (x -j) / (i -j) .

E. Revocation in ABE schemes

In Attribute Based Encryption systems, attribute revocation is a challenge issue even more difficult then in Identity-Based Encryption because each attribute is conceivably shared by multiple users. Revocation of any single attribute for a user would affect other users who share that attribute.

IV. AMVVI: ATTRIBUTES MANAGEMENT WITH VARIABLE VALIDITY INTERVALS

A. AMVVI Problem: Definition and Motivation

Let us consider a system where users unpredictably join and leave the system in a completely asynchronous and dynamic way. Users attributes validity periods are then unpredictable. We mean by AMVVI, the problem consisting of managing keys (granting and/or revoking attributes access) that supports variable validity intervals of relating attributes. In order to optimize and significantly reduce the complexity and the number of exchanged messages, a more practical solution is to allow the Attribute Authority (AA) to handle simultaneously a number of attribute-based access policy changes. This can be achieved by splitting time into intervals (referred to as time slots or simply slots) and letting the AA handle all attributebased access policy changes that occur in the same interval at the beginning of the next one.

This solution may cause a delay for entities when joining the system. Indeed, an entity which requests a secret key for some attributes at the middle of a time slot must wait until the beginning of the next time slot to get its own secret key and effectively join the system. System performances closely depend on the choice of the time slot duration: a small time slot forces the Attribute Authority to frequently refresh users' keys and consequently increase the overall system overhead. Conversely, a high time slot increases the delay and reduces users' keys refresh.

The choice of the time slot duration is an important and a critical issue as it directly influences the overall system performances. Generally, the time slot duration depends on the application scenario, it is very common to choose a day or a month as time slot.

Example: Consider a system with three entities (users) i.e. U = {U 1 , U 2 , U 3 }, and a set of three attributes: A = {Att 1 , Att 2 , Att 3 } (Figure 1).

With a color continuous line (red, blue or green) we depict the asked validity period of each attribute for system's users. Below each continuous line, we represented with dotted lines the delivered validity period of the attribute.

We notice here, that an attribute with a validity period starting at the middle of a time slot has its delivered validity period delayed until the beginning of the following time slot, ex. the first attribute (red line) of the first user U 1 in figure 1. Similarly, if the asked validity period of an attribute ends at the middle of a time slot, the delivered validity period ends at the beginning of the following time slot, ex. second attribute (green line) of the fist user U 1 in figure 1.

B. Security requirements

In our solution, we aim to target the following security requirements:

• Backward secrecy: A new user joining the system should not have any access to previous encrypted data. • Forward secrecy: A former user should have no access to current and future ciphertexts. • Collusion free: Collusion resistance is a required property of any ABE system. Even if many users not satisfying the access policy collude, they can obtain no information about the plaintext of the ciphertext. • Data Confidentiality: Unauthorized users who do not have the required attributes satisfying the access policy of a ciphertext must be prevented from accessing the plaintext of the data.

C. Application scenario

The application scenario that motivates our solution is security management of exchanged messages and data in a hospital. In this case, attributes could be administrative grades (Director, Department Chief, Secretary, Employee, ... etc.), Departments (Cardiology Department, Neurology Department, Emergency Department, ... etc.), functional grades (Nurse, Doctor, Trainee, ... etc.).

A trainee who has finished his/her internship in a hospital must see its secret key revoked, more precisely, the system should revoke its "Trainee" attribute. Thus he/she can not use its secret key part related to the attribute "Trainee" to decrypt ciphertexts. Similarly, a nurse who has moved from cardiology department to emergency one must lose her abilities to decrypt ciphertexts destined to cardiology department employee, this is resulting in revoking her "Cardiology Department" attribute.

Attribute revocation is an important task in Attribute Based Encryption systems. This is because systems are generally dynamic and are changing over time, so we cannot consider entities with a predefined and static sets of attributes during throughout the system life.

V. OUR APPROACH

In this section, we present our approach. First, we present our motivations and the concept of our approach. Then, we define assumptions and system model.

A. Concept

Here we describe the basic idea of our solution to implement attribute revocation mechanism in CP-ABE scheme.

As we mentioned in section IV, our approach is a batchbased method, which means that time axis is split into intervals of the same duration called time slots, and policy access changes (granting and/or revoking access) occur only between two successive time slots.

To implement attribute revocation in CP-ABE, our solution is not based on renaming attributes or using access tree to include a policy that considers expiration time for an attribute as proposed in [START_REF] Bethencourt | Ciphertext-policy attributebased encryption[END_REF] and [START_REF] Pirretti | Secure attribute-based systems[END_REF]. In our approach, the Attribute Authority send only the necessary attribute key parts every time slot to allow an entity to refresh its secret key. This technique reduces the overhead and the complexity of the solution comparing to the existing ones.

B. Syntax

Our Batch Based CP-ABE scheme consists of the following primitives:

• Setup. The setup algorithm is run by the Attribute Authority at the bootstrap phase. It takes no input other than the implicit security parameter. It outputs the public parameters P K which is shared with all the entities of the system and a master key M K kept secret. • KeyGen(MK, S). The KeyGen primitive is run by the Attribute Authority for each user joining the system. It takes as input the master key M K, a set of triplet S. Each element of the set S contains three information: an attribute att ∈ D and the validity period materialized by T att begin and T att end1 .

• Encrypt(PK, M, γ, T). The encryption algorithm takes as input the public parameters P K, a message M , an access structure γ over the universe of attributes, and the current time slot number T . The algorithm will encrypt M and produce a ciphertext CT such that only a user that possesses a set of attributes that satisfies the access structure during the T th time slot will be able to decrypt the message. We will assume that the ciphertext implicitly contains γ and T. • Decrypt(PK, CT, SK T ). The decryption algorithm takes as input the public parameters P K, a ciphertext CT , which contains an access policy γ and encryption time slot number T , and a private key SK T , which is a private key for a set S T of valid attributes at the T th time slot.

If the set S T of attributes satisfies the access structure γ then the algorithm will be able to decrypt the ciphertext and return a message M .

C. Our model

Let A denotes the set of all attributes used by the Attribute Authority in the system, and T represents the set of all time slots numbers (we have T ⊂ N). G 0 is a bilinear group of prime order p. The one-way hash function H used in our scheme is defined as follows:

H : A × T -→ G 0 (att, i) -→ H (att, i)
The hash function we use in our approach takes two parameters. The first parameter is an element from the set of all attributes maintained by the Attribute Authority, the second one is an integer that represents a time slot number.

We suppose that the probability of collision existence in the one-way hash function defined above is infinitely small. We mean by collision the existence of two different couples (att i , k) , (att j , l) ∈ A × N (with: (att i , k) = (att j , l)), such that H (att i , k) = H (att j , l). This assumption is described in the following formula:

∀att i , att j ∈ A, ∀k, l ∈ T : (att i , k) = (att j , l) ⇒ P (H (att i , k) = H (att j , l)) ≈ 0 (1)

D. Assumptions

1) Synchronization: We assume that the system is running a synchronization protocol that takes care to ensure synchronization between all entities in the system.

E. CP-ABE with attribute revocation

Let G 0 be a bilinear group of prime order p, and let g be a generator of G 0 . In addition, let e : denote the bilinear map.

Setup. It chooses a bilinear group G 0 of prime order p with generator g. Next it will choose two random exponents α, β ∈ Z p . The public key is published as:

P K = G 0 , g, h = g β , f = g 1/β , e (g, g) α (2)
and the master key is:

M K = (β, g α ) (3)
Note that f is used only for delegation, so we can omit it here as we do not talk about a delegation primitive. For more information we invite the reader to see [START_REF] Bethencourt | Ciphertext-policy attributebased encryption[END_REF].

KeyGen(MK, S).

This KeyGen primitive takes as input the master key M K and a set S which contains a set of attributes and all the corresponding time slot numbers of their validity period. We can write the set S as: S = a, T a begin , T a end , for all attribute a

The Key generation algorithm chooses a random r ∈ Z p , and then random r j ∈ Z p for each attribute j ∈ A. Then it computes the key as

SK = D = g (α+r)/β , ∀j ∈ A, ∀k ∈ T j begin , T j end : D j,k = g r H (j, k) rj , D ′ j = g rj (5)
Note here that the parameter D j,k is related to the attribute j for the time slot k.

Encrypt(PK, M, γ, T).

The encryption primitive encrypts a message M under the tree access γ and the time slot T . The algorithm first chooses a polynomial q x for each node x (including the leaves) in the access tree A. These polynomials are chosen in the following way in a top-down manner, starting from the root R. For each node x in the tree, set the degree d x of the polynomial q x to be one less than the threshold value k x of that node, that is,

d x = k x -1.
Starting with the root node R the algorithm chooses a random s ∈ Z p and sets q R (0) = s. Then, it chooses d R other points of the polynomial q R randomly to define it completely. For any other node x, it sets q x (0) = q parent(x) (index (x)) and chooses d x other points randomly to completely define q x . Let Y be the set of leaf nodes in γ. The ciphertext is then constructed by giving the tree access structure γ, the decryption time slot T and computing:

CT = γ, T, C = M e (g, g) αs , C = h s , ∀y ∈ Y : C y = g qy(0) , C ′ y = H (att (y) , T ) qy(0) (6)
Only users that satisfy the access tree γ during the time slot T can decrypt the ciphertext CT . We notice here that a user encrypting a message during the time slot T 1 can specify a different time slot T 2 for decryption.

Decrypt(CT, SK T ).

The decryption primitive takes the ciphertext CT and a secret key SK T , it is quite similar to the first form proposed in [START_REF] Bethencourt | Ciphertext-policy attributebased encryption[END_REF] with the unique difference in using our one-way hash function H defined in subsection V-C instead of a standard one.

We first define a recursive function DecryptN ode (CT, SK T , x) that takes as input a ciphertext CT = A, T, C, C, ∀y ∈ Y : C y , C ′ y , a secret key SK T = D, ∀j ∈ S T : D j,T , D ′ j , which is associated with a set S T of valid attributes at the time slot T , and a node x from the access tree A.

If the node x is a leaf node then we let i = att (x) and define DecryptN ode as follows: If i ∈ S T , then

DecryptN ode (CT, SK T , x) = e (D i,T , C x ) e (D ′ i , C ′ x) = e g r • H (i, T ) ri , g qx(0)
e g ri , H (i, T )

qx(0)
= e (g, g) rqx(0) .

If i / ∈ S T , then DecryptN ode (CT, SK T , x) = ⊥. Now, we consider the recursive case when x is a nonleaf node. The algorithm DecryptN ode (CT, SK T , x) then proceeds as follows: For all nodes z that are children of x, it calls DecryptN ode (CT, SK T , z) and stores the output as F z . Let S x be an arbitrary k x -sized set of child nodes z such that F z = ⊥. If no such set exists then the node was not satisfied and the function returns ⊥.

Otherwise, we compute αs / e (g, g) s(α+r) /e (g, g) rs = M.

F x = z∈Sx F ∆ i,S ′ x (0) z ; Where: i = index (z) , S ′ x = {index (z) : z ∈ Sx}

VI. PERFORMANCE EVALUATION

In this section, we present a series of simulations that we carried out in order to study the effect of the time slot duration on system performances. We consider two system performance parameters: (i) the Average Number of Time slots in an attribute validity period (ANT). This is because the number of time slots in a validity period determines the number of associated secret key parts to be sent, (ii) the Average Waiting Time that refers to the average delay between access request to an attribute and the beginning of the true validity period for that attribute.

A. Simulation Model

For the sake of simplicity, we considered a group of users which ask gaining the access right to only one attribute. We modeled users' requests, which represent starting dates of attribute validity periods, by Poisson process with the parameter λ. The attribute validity periods durations for all users follow exponential distribution with parameter µ.

B. Average Number of time slots (ANT)

The figure 2 shows the impact of the time slot duration on the system performance i.e. the average number of time slots per user. The figure shows also the impact of the parameter µ on the average number time slots per user. From this figure and figure 3, we can deduce empirically that the average number of time slots AN T is inversely proportional to the chosen time slot duration ∆t:

AN T ≈ 1 µ∆t (7)

C. Average Waiting Time (AWT)

We are also interested on the average waiting time AW T , figure 4 shows the result of a experiment simulating the variation of the overall average waiting time of all users depending on the the time slot duration. We set λ = 0.01. We note that the average waiting time AW T is independent of the Poisson process parameter λ, on the other side it increases linearly with the time slot duration ∆t, we can deduce empirically:

AW T ≈ 1/2 • ∆t (8)

D. ANT vs AWT

We notice here that we are trying to minimize both of the Average Waiting Time AW T and the Average Number of Time slots per user AN T which are two conflicting objectives i.e. minimizing AW T leads to maximizing AN T and vice versa. In real life applications we choose a tradeoff between performance and delay.

From formulas 8 and 7, we can deduce that:

AN T ≈ 1 2µAW T ( 9
)
and this is shown in figure 5.

In real applications we define some conditions and constraints related to the system requirements such as: AW T < α/µ AN T < β/µ α and β are to be determined according to the application requirements. In figure 5, we show in red color the set of solutions that satisfy these conditions where α = 1/10 and β = 1/5.

  Figure 1: Example

  g) r•qx(i)•∆ i,S ′ x (0) = e (g, g) r•qx(0) (Using polynomial interpolation) and return the result. After defining our function DecryptNode, we can now define the decryption algorithm. The algorithm begins by calling the function on the root node R of the tree A. If the tree is satisfied by S T we set A = DecryptN ode (CT, SK T , r) = e (g, g) rqR(0) = e (g, g) rs . The algorithm now decrypts by computing C/ (e (C, D) /A) = C/ e h s , g (α+r)/β /e (g, g) rs = M e (g, g)

Figure 2 :

 2 Figure 2: Average number of time slots

Figure 3 :

 3 Figure 3: Average number of time slots

Figure 4 :

 4 Figure 4: Average waiting time

Figure 5 :

 5 Figure 5: AWT vs ANT

T att begin and T att end are two time slot numbers that represent respectively the first and the last time slot of the validity period of the attribute att.

VIII. ACKNOWLEDGMENT

This work was carried out and funded in the framework of the Labex MS2T. It was supported by the French Government, through the program "Investments for the future" managed by the National Agency for Research (Reference ANR-11-IDEX-0004-02).


Francesco Romano

Andrea Del Prete

Nicolas Mansard
email: nmansard@laas.fr

Francesco Nori

Prioritized Optimal Control: a Hierarchical Differential Dynamic Programming approach

This paper deals with the generation of motion for complex dynamical systems (such as humanoid robots) to achieve several concurrent objectives. Hierarchy of tasks and optimal control are two frameworks commonly used to this aim. The first one specifies control objectives as a number of quadratic functions to be minimized under strict priorities. The second one minimizes an arbitrary user-defined function of the future state of the system, thus considering its evolution in time. Our recent work on prioritized optimal control merges the advantages of both these methods. This paper reformulates the original prioritized optimal control algorithm with the precise goal of improving its computational speed. We extend the dynamic programming method to work with a hierarchy of tasks. We compared our approach in simulation with both our previous algorithm and classical optimal control. The measured computational improvement represents another step towards the application of prioritized optimal control for online model predictive control of humanoid robots. We believe that this could be the key to unlock the (so far unexploited) dynamic capabilities of these mechanical systems.

I. INTRODUCTION

Control of underactuated nonlinear mechanical systems such as humanoids and legged robots is still a main concern for the control community. Given the high number of degrees of freedom (DoFs), it is practical to formulate the control objective in terms of multiple tasks to achieve at the same time. For instance, to make a humanoid robot walk, we can control the trajectory of its center of mass and its swinging foot, the force exerted by its supporting foot and its wholebody posture. If we also add manipulation objectives, it is clear that the number of tasks rapidly grows. In case of conflict between two or more tasks, we might require the most important task to be achieved at the expenses of the others. This approach -known as prioritized or hierarchical control -has been used in robotics and computer animation since the 80's [START_REF] Nakamura | Task-Priority Based Redundancy Control of Robot Manipulators[END_REF]. Researchers have applied prioritized control in different forms. The basic formalism defines a hierarchy among cartesian velocities of multiple points of a robotic structure [START_REF] Nakamura | Task-Priority Based Redundancy Control of Robot Manipulators[END_REF], [START_REF] Siciliano | A general framework for managing multiple tasks in highly redundant robotic systems[END_REF]. The same applies by considering the dynamic model, while imposing a hierarchy among operational references [START_REF] Khatib | A unified approach for motion and force control of robot manipulators: The operational space formulation[END_REF], [START_REF] Sentis | Synthesis and control of whole-body behaviors in humanoid systems[END_REF], thus allowing the control of contact forces, besides cartesian and joint-space motion.

In recent years, new formulations [START_REF] Righetti | Inverse dynamics control of floating-base robots with external constraints: A unified view[END_REF], [START_REF] Mistry | Operational Space Control of Constrained and Underactuated Systems[END_REF] have contributed to improving the computational efficiency of this approach. [START_REF] Saab | Generation of dynamic motion for anthropomorphic systems under prioritized equality and inequality constraints[END_REF], [START_REF] Escande | Hierarchical quadratic programming: Fast online humanoid-robot motion generation[END_REF] have studied efficient ways to include inequalities in the problem formulation, which for instance can model joint limits and torque bounds. Research in computer animation [START_REF] Lasa | Prioritized optimization for taskspace control[END_REF], [START_REF] De Lasa | Feature-based locomotion controllers[END_REF] has followed a similar path, trying to generate artificial motion by solving one or more Quadratic Programs (QP) (i.e. optimization problems with quadratic cost and linear constraints).

On the other hand, another well-known technique is optimal control, which minimizes a function of state and control of the system over a predefined time frame [START_REF] Kirk | Optimal control theory: an introduction[END_REF]. The control law automatically results as the solution of the associated optimization problem. Depending on the problem structure and the resolution method, the control law can be either a feedback control policy or a pure open-loop trajectory. Differently from prioritized control, optimal control takes decisions in accordance to future predictions, but it does not handle properly the multi-task scenario.

In [START_REF] Del Prete | Prioritized optimal control[END_REF] we introduced strict task prioritization in the optimal control formulation, which we recall in Sections II. Throughout this paper we will refer to it as POC (Prioritized Optimal Control). The developed algorithm gathers the benefits of prioritized control and optimal control. However, the approach in [START_REF] Del Prete | Prioritized optimal control[END_REF] did not exploit the intrinsic sparsity of the optimal control problem, which can lead to a reduction of the computational complexity from cubic to linear in the number of time steps. This work revisits the original POC algorithm with the main goal of addressing the above-mentioned issue, i.e. exploiting the sparsity. To accomplish this, in Section III we introduce a hierarchical model into the dynamic programming equation. Then in Section IV we presents the corresponding nonlinear heuristics (i.e. regularization and line search). Comparisons with the previous algorithm show the performance improvement in Section V.

II. BACKGROUND

A. Notation

The following notation is used throughout the paper:

• x i ∈ R n is the state variable at the time i. • u i ∈ R m is the control variable at the time i. • X j := (x j , • • • , x N ) and U j := (u j , • • • , u N -1
) are the partial state and control trajectories, respectively, from time j. • X := X 0 and U := U 0 are the entire state and control trajectories.

• ∂ y g is the partial derivative of a multivariable function g(•) with respect to one of its variables y; ∂ yz g is the partial second-order derivative with respect to y and z. • The superscript (•) * denotes the minimum value and the corresponding decision variable for a minimization problem: p * (z * ) := min z p(z). • A † ∈ R m×n is the Moore-Penrose pseudoinverse of the matrix A ∈ R n×m .

B. Problem Formulation

Let us consider a discrete-time nonlinear dynamical system

x i+1 = f (x i , u i ), for i = 0, . . . , N -1, (1)
where f (•) : R n × R m → R n is the dynamics function. Assume that the system has to perform K tasks, with task 1 having the highest priority, and task K the lowest. The k-th task is represented with an arbitrary cost function:

G (k) (X, U ) := N -1 i=0 φ (k) (x i , u i ) + φ (k) N (x N ) , (2)
where φ(•) : R n × R m → R is the running cost and φ N (•) : R n → R is the final cost. The control problem is to find the control input sequence U * and state trajectory X * that solve the following hierarchical optimal control problem, denoted by HOC (k) :

minimize U,X G (k) (X, U ) subject to x i+1 = f (x i , u i ), for i = 0, . . . , N -1 x 0 fixed G (j) (X, U ) = G (j) * ∀j < k , (3)
for k = 1 to K, where G (j) * is the optimum obtained by solving the HOC (j) . We define the hierarchical optimal control problem composed of the K tasks as the solution of the cascade of HOC (k) . This definition of "cascade" follows the construction made in [START_REF] Kanoun | Kinematic control of redundant manipulators: Generalizing the Task-Priority framework to inequality task[END_REF] for hierarchical quadratic problems.

C. Algorithm Outline

Before delving into the mathematical details, let us introduce the principles of the algorithm. Each iteration consists of the following three phases:

1) Problem approximation.

2) Local control computation, or backward pass.

3) System simulation, or forward pass. We start by approximating the dynamics and the cost along an initial nominal state-control trajectory. Then in the backward pass -which is the main contribution of this paperwe compute the local control modification as the solution to a hierarchical optimal control problem for the approximated model. Because this control modification is based on a local model, we have to check how it performs on the real system (i.e. we integrate the dynamics with the new control trajectory and compute the new costs). The so-called linesearch procedure takes care of reducing the magnitude of the control modification to compensate for the mismatch between approximated and real model. Finally we introduce a regularization procedure to solve two issues commonly arising in this class of algorithms: solutions far from the local validity of the model and ill-conditioning due to finiteprecision arithmetic.

III. HDDP ALGORITHM: LINEAR PART

A. Dynamic Programming

We solve the problem (3) by applying the dynamic programming algorithm [START_REF] Kirk | Optimal control theory: an introduction[END_REF]. Let us start by defining the costto-go at step i for task k as:

G (k) i (x i , U i ) := N -1 j=i φ (k) (x j , u j ) + φ (k) N (x N ) .
Note that the total cost corresponds to the cost-to-go at step i = 0. The optimal cost-to-go, or value function, is its minimum value:

V (k) i (x i ) := min Ui G (k) i (x i , U i ) .
By applying Bellman's principle of optimality [START_REF] Bellman | Applied dynamic programming[END_REF] we get the recurrence equation of dynamic programming. This formulation allows you to minimize over a single time step at a time, instead of minimizing over the whole trajectory. The recurrence equation is:

V (k) i (x i ) := min ui φ (k) (x i , u i ) + V (k) i+1 (f (x i , u i )) , (4)
with i = N -1, • • • , 0 initialized with V (k) N (x N ) := φ (k) N (x N ).
To simplify the notation we will use the following definition:

V (k) i (x i , u i ) := φ (k) (x i , u i ) + V (k) i+1 (f (x i , u i )). (5)
Solving the above equation in the nonlinear context is computationally infeasible even for low-dimensional state and control spaces (Bellman's curse of dimensionality). The route followed in this paper, instead, is to iteratively solve local quadratic approximations of the value function.

B. Hierarchical Dynamic Programming

We start by considering a nominal control policy (ū 0 , • • • , ūN-1 ) =: Ū and the corresponding state trajectory (x 1 , • • • , xN ) =: X resulting by applying the former control to the system (1) with initial condition x 0 . We also denote the variation of the control and the state with respect to their nominal values as δu i := u i -ūi and δx i := x i -xi respectively. With these definitions, we approximate (5) with its Taylor's series expansion truncated at the second order:

V (k) i (x i , u i ) ≈ V (k) i (x i , ūi ) + Q (k) x,i δx i + Q (k) u,i δu i + 1 2 δx i Q (k) xx,i δx i + δu i Q (k) uu,i δu i + δx i Q (k) xu,i δu i , (6)
where the coefficients are defined as:

Q (k) x,i = ∂ x φ (k) + ∂ x f ∂ x V (k) i+1 Q (k) u,i = ∂ u φ (k) + ∂ u f ∂ x V (k) i+1 Q (k) xx,i = ∂ xx φ (k) + ∂ x f ∂ xx V (k) i+1 ∂ x f + ∂ x V (k) i+1 ∂ xx f Q (k) uu,i = ∂ uu φ (k) + ∂ u f ∂ xx V (k) i+1 ∂ u f + ∂ x V (k) i+1 ∂ uu f Q (k) xu,i = ∂ xu φ (k) + ∂ x f ∂ xx V (k) i+1 ∂ u f + ∂ x V (k) i+1 ∂ xu f . (7)
All the derivatives are computed for x i = xi and u i = ūi . To speed-up the algorithm, we neglect the terms depending on the second-order derivatives of the dynamics in the last three equations. This is the same approximation that distinguishes the iterative LQR algorithm [START_REF] Todorov | A generalized iterative lqg method for locallyoptimal feedback control of constrained nonlinear stochastic systems[END_REF], [START_REF] Tassa | Synthesis and stabilization of complex behaviors through online trajectory optimization[END_REF] from differential dynamic programming [START_REF] Mayne | A second-order gradient method for determining optimal trajectories of non-linear discrete-time systems[END_REF]. In most scenarios and applications there is a trade-off between computational burden and accuracy of the solution [START_REF] Tassa | Synthesis and stabilization of complex behaviors through online trajectory optimization[END_REF]. Because our final goal is the real-time control of robots, we prefer fast-andapproximate solutions over slow-and-accurate ones.

Now that we have a quadratic model of

V (k) i (x i , u i ),
we can find the optimal control variation analytically:

δu (k) * i = -Q (k) † uu,i Q (k) u,i δ û(k) i -Q (k) † uu,i Q (k) ux,i K (k) i δx i +N (k) i δu (k+1) i (8) where N (k) i is a projector onto N (Q (k) uu,i ) (i.e. the null space of Q (k)
uu,i ) and δu (k+1) i is a free vector that will be chosen to minimize the task k + 1. Typically in robotics the dimension of a task is much smaller than the number of DoFs of the robot, which ensures the existence of the null space.

1) One task resolution: We start by solving the optimal control problem with only one task. In this simplified scenario the optimal control in (8) consists of the first two terms only, i.e. δu (k+1) i ≡ 0 for all i. To obtain the value function at step i we substitute the control (8) into (6), thus obtaining the following quadratic form for the value function:

V i (δx i ) = V s,i + V x,i δx i + 1 2 δx i V xx,i δx i , (9)
where the scalar, linear and quadratic terms are defines as:

V s,i = Q u,i δ ûi + 1 2 δ û i Q uu,i δ ûi V x,i = Q x,i -K i Q u,i -K i Q uu,i δ ûi + Q xu,i δ ûi V xx,i = Q xx,i + K i Q uu,i K i -2Q xu,i K i (10)
Equation ( 9) is solved backward in time starting from i = N -1 to 0 and initialized with the quadratic approximation of φ (k) N (x N ). As expected, for a single task, the solution of hierarchical differential dynamic programming coincides analytically with the solution of DDP [START_REF] Mayne | A second-order gradient method for determining optimal trajectories of non-linear discrete-time systems[END_REF].

2) Multiple-task resolution: When we solve the problem for a task k > 1 the control variable in no longer free. Indeed δ û(j) i and K

(j) i have already been chosen for all tasks j < k.

The control variable must then respect the following form:

δu i = [δ û(1) i + • • • + N (1) i • • • N (k-2) i δ û(k-1) i ] -[K (1) i + • • • + N (1) i • • • N (k-2) i K (k-1) i ]δx i + N (1) i N (2) i • • • N (k-1) i δu (k) i := δ ū(k-1) i - K(k-1) i δx i + N (k) i δu (k) i . ( 11
)
Substituting ( 11) into [START_REF] Mistry | Operational Space Control of Constrained and Underactuated Systems[END_REF] we get updated values for the coefficients in [START_REF] Saab | Generation of dynamic motion for anthropomorphic systems under prioritized equality and inequality constraints[END_REF]:

Q(k) x,i = Q (k) x,i - K(k-1) i Q (k) u,i + Q(k) xu,i δ ū(k-1) i Q(k) u,i = Q (k) u,i + Q (k) uu,i δ ū(k-1) i Q(k) xx,i = Q (k) xx,i + K(k-1) i Q (k) uu,i K(k-1) i -2Q (k) xu,i K(k-1) i Q(k) uu,i = N (k-1) i Q (k) uu,i N (k-1) i Q(k) xu,i = Q (k) xu,i - K(k-1) i Q (k) uu,i . ( 12
)
With the above redefinition we can compute the optimal control δu (k) * i using [START_REF] Escande | Hierarchical quadratic programming: Fast online humanoid-robot motion generation[END_REF] with the substitution Q ← Q. Similarly, the value function at step i has the same form as the one in [START_REF] Lasa | Prioritized optimization for taskspace control[END_REF] provided that its coefficients in [START_REF] De Lasa | Feature-based locomotion controllers[END_REF] are computed with Q.

Equations ( 12) and ( 11) already outline the correct procedure to compute the control and the value-function update during the backward pass. It is clear that two sweeps on the task hierarchy are required: 1) from k = 1 to K to compute the feedforward terms, the feedback gain matrices and the null-space projectors; 2) from k = K -1 to 1 to update the value function. Algorithm 1 summarizes the procedure.

Algorithm 1 Hierarchical Linear Solver Initialize V (k) x,N and V (k) xx,N ∀ task k for i = N -1 to 0 do for k = 1 to K do Update δ ū(k-1) i , K(k-1) i and N (k-1) i 5: Compute Q (k) x,i , Q (k) u,i , Q (k) xx,i , Q (k) uu,i and Q (k) xu,i Compute Q(k) x,i , Q(k) u,i , Q(k) xx,i , Q(k) uu,i and Q(k) xu,i δ û(k) i = - Q(k) † uu,i Q(k) u,i K (k) i = Q(k) † uu,i Q(k) ux,i N (k) i ← projector onto N ( Q(k) uu,i ) 10: end for for k = K -1 to 1 do Compute V (k)
x,i and V

(k) xx,i end for δ ûi = δ ū(1) i , K i = K (1)
i 15: end for return {δ ûi , K i , i = 0, . . . , N -1}

C. Computational Cost Analysis

The benefit of the proposed hierarchical dynamic programming approach with respect to the algorithm described in [START_REF] Del Prete | Prioritized optimal control[END_REF] is its computational complexity. We now analyze and compare the computational cost of the two algorithms.

1) HDDP computational complexity analysis: We start by considering a single iteration of the linear part of the algorithm. At each iteration we compute the coefficients Q(k) (•) . This step consists of a series of matrix-matrix multiplications and matrix-vector multiplications (O(r 3 ), where r is the largest dimension of the matrices involved).To compute the pseudoinverse and the null-space projector we have to perform an orthogonal decomposition of the matrix Q(k) uu , e.g. we chose the SVD decomposition. Depending on the algorithm the cost can vary, but it is proportional to O(m 3 ). The value-function update step consists of matrix-matrix and matrix-vector multiplications too. Its cost is still in the order of O(m 3 ). To summarize, the above computations are performed for each of the K tasks and for all the N time steps thus yielding the total cost of O(N K m 3 ).

2) Comparison with POC computational complexity: POC did not take advantage of the intrinsic sparsity of the optimal control problem. Indeed at every iteration a matrix S ∈ R mN ×mN is formed and then decomposed with the SVD algorithm. Its computational cost amounts at O(N 3 m 3 ). The total algorithmic cost is dominated by the above decomposition. We can thus neglect the cost due to matrix multiplications. The total complexity of the linear part of the algorithm is O(N 3 K m 3 ).

Comparing the two costs the difference in complexity is clear: POC cubic in the number of time steps while our algorithm is linear.

IV. HDDP ALGORITHM: NONLINEAR HEURISTIC A. Regularization Procedure

The procedure described in the previous section operates on a local approximation of the original problem (3) and in this context regularization helps attenuating numerical issues arising from the finite-precision arithmetic and the local validity of the approximated model.

We introduce two regularization procedures. The first one, which resembles the Levenberg modification for the nonlinear least-squares problem, penalizes state deviations from the nominal state trajectory. A parameter λ (k) regulates the intensity of the regularization, which is applied in [START_REF] Saab | Generation of dynamic motion for anthropomorphic systems under prioritized equality and inequality constraints[END_REF] to the definitions of

Q (k) uu,i and Q (k) xu,i : Q (k) uu,i = ∂ uu φ (k) + ∂ u f (∂ xx V (k) i+1 + λ (k) I n )∂ u f Q (k) xu,i = ∂ xu φ (k) + ∂ x f (∂ xx V (k) i+1 + λ (k) I n )∂ u f , where I n ∈ R n×n is the identity matrix.
The second regularization consists in damping the pseudoinverses [START_REF] Maciejewski | Dealing with the ill-conditioned equations of motion for articulated figures[END_REF] with a parameter µ (k) . Note that the nullspace projectors must be computed with the undamped pseudoinverses to ensure the proper hierarchy propagation.

B. Line-Search Procedure

Another important feature of the proposed algorithm consists in adopting a custom line-search procedure, which reduces the optimization step computed on the quadratic approximation. More in details, the control-policy update rule (8) consists in a feedback K i (x i -x i ) and a feed forward

δ û(k) i term.
The latter in particular, might significantly degrade the policy optimality and should therefore be carefully chosen by a suitable line-search procedure, complicated by the hierarchical nature of the algorithm.

The line search adopted in our algorithm is the following: a set of constants ν (k) ∈ [0, 1], one for each task, is chosen and the control:

u i = ūi + K k=1 ν (k) δ û(k) i -K i (x i -xi )
is applied to the system (1). The policy for selecting the step size ν (k) consists in initializing ν (k) = 0 for all the tasks. We then start from the highest-priority task traversing the whole hierarchy down to the last task. At a generic task k we set ν (k) = 1 and we progressively decrease it until all the costs decrease in a lexicographic order, i.e. a decrease of the cost for the task k must not lead to an increase of the cost of any tasks j < k.

C. Algorithm Summary

We now summarize the algorithm proposed to solve a cascade of hierarchical optimal control problems. An iteration of the main algorithm is composed of the following phases:

1) Problem approximation.

2) Local control computation, or backward pass.

3) System simulation, or forward pass. Starting from an initial nominal trajectory we approximate the system and the costs and we compute a control modification. In the forward pass, we simulate the system and compute the new cost for every task. In this phase we perform the line-search procedure. In case of no improvements, we increase the regularization parameters and repeat the backward pass. If at least one task has improved, we decrease its regularization parameter and accept the iteration.

Convergence is tested at the end of each iteration. The convergence criteria consists in an absolute criterion and a relative one. We assume that the algorithm has converged if the cost is lower than the absolute tolerance value. Alternatively, the relative improvement between two successive iterations must be smaller than a relative tolerance value.

Algorithm 2 summarizes in pseudo code the hierarchical dynamic programming algorithm.

V. SIMULATION RESULTS

This section presents two sets of simulations. The first tests validate the expected computational improvements of our new formulation with respect to POC [START_REF] Del Prete | Prioritized optimal control[END_REF]. The second tests instead investigate the issues arising when using weights in iLQR to approximate strict priorities.

A. Experimental Setup

All tests have been conducted on a workstation with an Intel Xeon quad core at 3.2GHz with 8GB of RAM. We tested the three algorithms on a customized version of the Compliant huManoid (CoMan) simulator [START_REF] Dallali | Development of a dynamic simulator for a compliant humanoid robot based on a symbolic multibody approach[END_REF]. The base of the robot was fixed because we used only its upper body, which counts 11 DoFs: 4 in each arm and 3 in the torso.

Algorithm 2 Hierarchical Differential Dynamic Programming

Require: Given x 0 and Ū Ensure: decrease λ (k) and µ (k) for improved tasks

Ū , K * i K * i ← 0 X ← FORDWARDDYNAMICS(x 0 , Ū , K * ) G (k) ← COMPUTECOST( X, Ū ) Initialize regularization parameters: λ ← λ 0 , µ ← µ 0 5: loop for k = 1, • • • , K and i = 0, • • • , N do Compute ∂ (•) φ (k) , ∂ x f and ∂ u f end for {δ û(k) i , K i } ← LINEARSOLVER(∂ (•) {φ (k) , f }, µ, λ) 10: {U new , G (k) new } ← LINESEARCH(δ û(k) i , K i ) if all(G (k) new -G (k) > 0) then increase λ
end if Ū ← U new , G (k) ← G (k) new , K * i ← K i if converged then break 20: end if end loop return { Ū , K * i }
Fig. 1: Screenshots of the simulation. On the left the initial configuration of the robot. On the right the final configuration during one test. Colored balls represent the target. In order of priority: yellow, red and green.

All the algorithms and the dynamics computation have been coded in Matlab 2012b.

B. Test Description

We controlled the humanoid robot in order to reach three cartesian points with three different parts of its body, while minimizing the effort (i.e. the joint torques). In order of decreasing priority, we controlled the position of the leftarm end-effector, right-arm end-effector and the top of the torso. Figure 1 shows the test scenario.

We discretized the robot dynamics with a time step of 5ms for a total of 50 steps. In all the tests, we initialized the control trajectory with gravity compensation torques, so that the robot maintained the initial state for the whole time horizon.

C. Comparison with Prioritized Optimal Control

We first tested our algorithm against our previous implementation described in [START_REF] Del Prete | Prioritized optimal control[END_REF]. The reaching cost functions contain only a final cost, i.e. it takes the form G

(k) (X, U ) ≡ φ (k)
N (x N ), being the squared norm of the distance between the end-effector and the target position:

φ (k) N (x N ) = ||h(x N ) -h|| 2 ,
where h(x) : R n → R 3 is the function mapping the state variable x to a cartesian position, and h is its reference value.

We tested three different scenarios: i) two conflicting reaching tasks for the left and right arm end-effectors (Test 1); ii) three conflicting reaching tasks, using both arms and the torso (Test 2); iii) two compatible reaching tasks for the left and right arm end-effectors (Test 3). In all tests we added an effort task at the bottom of the hierarchy, which removes any left redundancy. We repeated the tests 100 times changing the original task targets of a value randomly sampled from a uniform distribution between 0 and 5cm. Table I reports the mean value of the final costs and of the total computation time for the three scenarios.

For both algorithms the absolute and relative tolerance for the stopping criteria have been set to 10 -8 [m 2 ] and 10 -4 , respectively.

Table I shows that, as far as the final error is concerned, HDDP manages to achieve a slightly better performance in all three scenarios. Unexpectedly, in Test 3, in which the tasks are compatible, POC yields some errors, especially in the secondary task, while HDDP manages to achieve almost zero errors.

From the computational standpoint HDDP is faster then POC in every test as we expected. Note that the CPU time is not directly proportional to the number of iterations in the HDDP algorithm. This is mainly due to the line-search procedure: big values of ν (k) mean few forward-dynamics simulations, resulting in faster iterations.

D. Weighted Cost Comparison

This test compares our algorithm with the standard iLQR control in the case of three conflicting reaching tasks (Test 2). To approximate strict priorities we used a weighted sum of the task costs:

G(X, U ) = w 3 g 1 (X, U )+w 2 g 2 (X, U )+wg 3 (X, U )+g e (U ),
where g i (•) is the i th -task cost function, g e (U ) is the effort task and w is a user-defined weight. for different weights from w = 10 to w = 10 6 . We used two different implementations to check that the results did not depend on some implementation details: i) Weighted HDDP is our algorithm with a single weighted task; ii) iLQR is an implementation of [START_REF] Todorov | A generalized iterative lqg method for locallyoptimal feedback control of constrained nonlinear stochastic systems[END_REF]. In both cases the cost has been used both as running cost and as final cost.

For the first two weights, i.e. w = 10 and w = 10 2 , both implementations achieved the same result: the task priorities are not respected and the solutions are suboptimal. By increasing the weights the solutions obtained approach the one from multi-task HDDP. Interestingly, from w = 10 4 the two implementations yield significantly different results. In both cases increasing the weights over a certain value leads to larger errors.

We can conclude that with the appropriate weights iLQR can find a solution that is very similar to the one of HDDP. However, if the weights are not appropriate iLQR can give either suboptimal or meaningless solutions. Moreover, we believe that the complexity of the weight tuning is proportional to the number of tasks, which could easily be higher than 4 when controlling a full humanoid.

VI. CONCLUSIONS AND FUTURE WORKS

In this paper we proposed an efficient way to compute the solution of the prioritized optimal control (POC) problem that we previously introduced in [START_REF] Del Prete | Prioritized optimal control[END_REF]. We reformulated the original POC method, and solved the problem by means of a modified version of dynamic programming, capable of handling strict task priorities. The resulting algorithm is significantly faster than its previous version, while retaining the capability to correctly handle strict priorities.

Our final goal is to apply this method to a real humanoid robot, but before doing so we need to address some issues. Taking into account torques and joint limits is crucial, and it can be accomplished by introducing inequalities constraints into the problem. Since humanoid robots are almost always in contact with the environment, the controller must consider the contact dynamics. Thanks to the generality of our formulation, it should be easy to integrate any smooth contact dynamics [START_REF] Todorov | Mujoco: A physics engine for model-based control[END_REF] inside our algorithm. Finally, the current implementation has been coded in Matlab, which allowed only "relative" comparisons. To properly measure the computational load of the algorithm, an efficient, multithreaded C++ implementation is required.

As humanoid robots become more and more complex, the ability to specify simple and clear tasks through strict priorities -thus avoiding the time-consuming and errorprone weight tuning -could greatly simplify the synthesis of complex behavior for these systems.

TABLE I :

 I Comparison between POC and HDDP. Task errors are in [m 2 ]. Values are average of 100 trials.

		Task 1	Error [m 2 ] Task 2	Task 3	Iter.	CPU Time
	Test 1	POC HDDP 1.87 10 -8 4.07 10 -7	1.59 10 -2 1.22 10 -2	N.A. N.A.	13 139s 411 107s
	Test 2	POC HDDP 1.42 10 -8 5.03 10 -7	1.39 10 -2 1.24 10 -2	2.87 10 -2 2.24 10 -2	28 511s 382 136s
	Test 3	POC HDDP 4.75 10 -9 6.73 10 -7	1.44 10 -5 3.98 10 -9	N.A. N.A.	21 206s 281 187s

  Table II shows the results

TABLE II :

 II Task errors ([m 2 ]) for the three-reaching scenario using a single weighted cost.

		w	Task 1	Error [m 2 ] Task 2	Task 3
	Weighted HDDP	10 10 2 10 3 10 4 10 5 10 6	7.27 10 -4 1.38 10 -6 1.14 10 -8 6.64 10 -10 6.64 10 -10 4.1 10 -4	2.03 10 -2 1.43 10 -2 1.44 10 -2 1.44 10 -2 1.44 10 -2 1.44 10 -2	7.51 10 -2 2.86 10 -2 2.37 10 -2 2.37 10 -2 2.37 10 -2 2.41 10 -2
		10	7.2 10 -4	2.0 10 -2	7.5 10 -2
		10 2	1.3 10 -6	1.43 10 -2	2.78 10 -2
	iLQR	10 3 10 4	9.5 10 -9 7.56 10 -6	1.44 10 -2 1.47 10 -2	2.36 10 -2 2.32 10 -2
		10 5	3.49 10 -6	1.46 10 -2	2.3 10 -2
		10 6	2.37 10 -3	1.33 10 -2	3.33 10 -2

*This work was supported by the FP7 EU projects CoDyCo (No. 600716 ICT 2011.2.


Ala Atrash
email: ala-aldin.atrash@utc.fr

Marie-Hélène Abel
email: marie-helene.abel@utc.fr

Claude Moulin
email: claude.moulin@utc.fr

Supporting Organizational Learning with Collaborative Annotation

Keywords: Collaboration, Organizational Learning, Semantic Modeling, Ontology, Annotation, Collaborative Annotation

INTRODUCTION

In this current uncertain economical situation, organizations should do their best to stay competitive. [START_REF] Alavi | Exploring the relation between organizational learning and knowledge management for improving performance[END_REF] affirms that organizations which learn can have a good competitive situation. [START_REF] Huber | Organizational learning: The contributing processes and the literatures[END_REF] argues that organizational learning consists of four points: knowledge acquisition, knowledge sharing, knowledge interpretation and knowledge storage. Facilitating the knowledge sharing is done by organizing the knowledge in order to be communicable and integrable [START_REF] Duncan | Organizational learning: Implications for organizational design[END_REF]. This means that the knowledge should be represented in a comprehensible and distributable manner and should be saved in an accessible and consistent organizational memory. Many research studies pointed out the usefulness of collaborative annotation for facilitating learning within organizations. Current annotation taking platforms do not take into consideration the aspects of organizational learning. A common limitation of these platforms is the restricted ability to share / retrieve annotations [START_REF] Su | A web 2.0-based collaborative annotation system for enhancing knowledge sharing in collaborative learning environments[END_REF]. This is because the annotations in these platforms are disconnected from the information system and they are only accessible in the annotation system. As a result, the annotations could not be indexed as any other information resources (e.g., a document). This means that the annotations are not accessible / visible like other resources. In order to overcome these limitations, we propose to consider the annotation as being an information resource in its own right. This would facilitate the sharing, indexing, retrieving of the annotations which in turns facilitates the implementing of the collaborative annotation. As a consequence, the collaborative annotation promotes knowledge circulation within organizations. This leads to the applying of the four points presented by [START_REF] Huber | Organizational learning: The contributing processes and the literatures[END_REF]: knowledge acquisition, sharing, interpretation and storage. As a result, the organizational learning is supported by implementing the collaborative annotation within organizations.

In this paper, we define the collaborative annotation and we justify the role it plays for enhancing organizational learning section 2. Current collaborative annotation tools are presented in section 3. We present MEMORAe-core 2 model and MEMORAe web platform in section 4. A use case example is presented in section 5. We discuss the advantages of this web platform over other collaborative annotation platforms in section 6. Conclusion and future work are in section 7.

COLLABORATIVE ANNOTATION

2.1 Annotation Definition [START_REF] Oren | What are semantic annotations? Technical report[END_REF] defines the annotation as being a relation between the annotated data and the annotating data, this relation has a type and is done in a particular context. [START_REF] Bringay | A specific tool of annotations for the electronic health record[END_REF] defines the annotation as: "A particular note linked to a target. The target can be an other annotation, a collection of documents, a document or a document segment (a paragraph, a phrase, an image, a part of an image, etc.)". [START_REF] Slimani | Semantic annotation: The mainstay of semantic web[END_REF] precises four domains on which the annotation could be applied:

• Document annotation: It is the annotation of documents or part of them. Users can take notes, comments, remarks, etc. and share them with others.

• Wiki annotation: Wikis are collaborative authoring of a particular content. Authors could contribute by adding, modifying or deleting the content. Authors could add annotations to describe the wiki. Annotations are added on page level to describe the whole wiki page.

• Blog annotation: A blog is a website or online journal owned by an individual who regularly writes posts which are presented in reverse chronological order. Contributors to a blog could write comments to a particular post. An annotation in a blog is a statement about a post. For example, posts are classified with simple categories "sport", "research", "teaching", etc. (Slimani, 2013) considers that blog posts are annotated with these categories.

• Tagging: Tags are descriptive terms (e.g., keywords). For example, Flickr allows a tagging to a particular image to describe its content (e.g., "car" for a car image). [START_REF] Slimani | Semantic annotation: The mainstay of semantic web[END_REF] considers that tags express some unspecified relation between the resource and whatever the term refers to.

The annotation granularity and form are terms used in the annotation definition. So we need to define these terms

• Annotation granularity (also called "scope" ) [START_REF] Sazedj | Time to evaluate: Targeting annotation tools[END_REF] indicates if the annotated data is a whole resource (e.g., a document) or part of a it (e.g., a section inside a document, a sentence, etc.). When the granularity is high, the annotation could be done to any part of the resource.

• The form of the annotation [START_REF] Euzenat | Eight questions about semantic web annotations[END_REF] indicates the type of annotation, a textual object or a structured object. Textual annotation has a plain text form. Structured annotation could be a link to a structured object (e.g., html page, xml, rdf, etc.)

According to us, the annotation is an information resource in its own right. We define an annotation as the "transcription of an idea that have a particular target and a body which is somehow about the target". We consider that the annotation could have a high granularity [START_REF] Sazedj | Time to evaluate: Targeting annotation tools[END_REF]. This means that it would be possible to annotate the resource itself or any part of it.

Collaborative Annotation Definition

Collaborative annotation is the process of annotating a particular resource by several users within a collaborative environment [START_REF] Petasis | The sync3 collaborative annotation tool[END_REF]. Within "Palimpsest1 " project, the collaborative annotation is the process of adding a comment to a shared space (e.g., a document), this comment is either a note, an explanation or a criticism attached to a particular text. In collaborative annotation, the users have access to the shared resource on which they could add their annotation. Users also have access to other annotations of the shared resource.

According to us, the collaborative annotation takes place when the annotation itself is shared between individuals who have access to the annotated resource. In this case, the annotations could have an impact on individuals who view it. This annotation could be written by a single author or multi authors. The annotation becomes collaborative when its content is shared between the collaborators. The annotation "Body" could have different forms [START_REF] Euzenat | Eight questions about semantic web annotations[END_REF]: plain text, a document, a chat, etc. When the annotation "Body" is a chat, a wiki or a forum, the annotation is necessarily written by multi authors.

The Role of Collaborative Annotation in the Organizational Learning Process

As mentioned earlier, the organizational learning is done by supporting knowledge sharing and retrieval within an organization. The fact that collaborative annotations are shared between users promotes the organizational learning. The annotations within a collaborative environment reflects the opinions of the annotators about a particular resource. An already annotated resource allows a better understanding of it.

Many research studies illustrated the usefulness of collaborative annotation for facilitating learning within organizations. For example [START_REF] Nokelainen | Evaluating the role of a shared document-based annotation tool in learner-centered collaborative learning[END_REF] affirms that collaborative annotation motivates the individuals ability to learn which in turns enhances the organizational learning process. [START_REF] Marshall | Exploring the relationship between personal and public annotations[END_REF] indicates that collaborative annotation provides an opportunity to facilitate making individual knowledge a public one. As a consequence, the annotations' knowledge value is accumulated when these annotations are shared. The experiment of [START_REF] Su | A web 2.0-based collaborative annotation system for enhancing knowledge sharing in collaborative learning environments[END_REF] shows us how a collaborative annotation web platform facilitates knowledge circulation and retrieval between individuals within a collaborative environment. As a result, sharing the annotations by a collaborative annotation platform within an organization plays an important role in the organizational learning process.

CURRENT COLLABORATIVE ANNOTATION TOOLS

Most of the collaborative annotation tools are web based applications (e.g PAMS 2.0 [START_REF] Su | A web 2.0-based collaborative annotation system for enhancing knowledge sharing in collaborative learning environments[END_REF]) and few of them are desktop ones [START_REF] Petasis | The sync3 collaborative annotation tool[END_REF]) (e.g., SYNC32 ). For example, Annotea [START_REF] Kahan | Annotea: An open rdf infrastructure for shared web annotations[END_REF], Bounce3 , Diigo4 , iComment5 and MyStickies6 are extensions that could be added to a web browser in order to annotate web resources (e.g., HTML pages, images). These extensions run inside the browser along with a centralized server (to store the annotations). Usually, these annotations are text fields where users can type anything they wish. The user of these tools can be part of one or more groups whose members have access to the annotations of this user [START_REF] Petasis | The sync3 collaborative annotation tool[END_REF]. Some tools allow the annotation to collaborative environments (e.g., wikis, blogs).

Taking wiki annotations, we can mention WikSAR [START_REF] Aumueller | Semantic authoring and retrieval within a wiki[END_REF], IkeWiki [START_REF] Schaffert | Ikewiki: A semantic wiki for collaborative knowledge management[END_REF] and SemperWiki [START_REF] Oren | Semperwiki: a semantic personal wiki[END_REF]. Most of wiki annotations tools allow annotations only to a whole wiki page. This is the same case in blog annotation tools where annotations are done to the blog posts. For blog annotations, we can mention semiBlog [START_REF] Möller | semiblogsemantic publishing of desktop data[END_REF], HP Semantic Blogging demonstrator [START_REF] Cayzer | Semantic blogging and decentralized knowledge management[END_REF].

None of the presented annotation tools consider the annotation as an information resource in its own right. The annotation in these tools is an integral part of the annotated resource. As a result, the annotation itself is not indexed and in order to find it is necessary to search the annotated resource. In addition, none of these tools support the annotation that has a structured object like a chat, a forum or a wiki. The only annotation form [START_REF] Euzenat | Eight questions about semantic web annotations[END_REF] supported is the textual annotation. In order to solve the annotation indexing problem, we consider the annotation as information resource in its own right. So the annotation could itself be indexed, shared, retrieved, etc. the same way we do to index, share, retrieve, etc. a particular resource (e.g., a document). We also offer a new way to create collaborative annotation. This is done by supporting annotations that have structured form like chat, wiki or forum pages.

COLLABORATIVE ANNOTATION WITHIN MEMORAE APPROACH

The main objective of MEMORAe approach is to manage heterogeneous information resources within organizations. The approach is comprised of a semantic model (called MEMORAe-core 2) and a web platform (called MEMORAe) which is based on the semantic model. The model and the platform make together a support to enhance the process of organizational learning. The details are in the following sections.

The Annotation Within

MEMORAe-core 2 Model

Describing MEMORAe-core 2 Model

MEMORAe-core 2 semantic model (Fig. 1) contains the concepts that describe "how we collaborate". MEMORAe-core 2 is built using owl (Web Ontology Language). The model focuses on information resources shared between individuals and groups of individuals within an organization. There are two main aspects in MEMORAe-core 2 :

• Modeling the individuals and groups of individuals: The organization in MEMORAe-core 2 model is a set of members. These members are potential users of the MEMORAe web platform.

Modeling the Annotation

The modeling of the annotation concept in MEMORAe-core 2 model is based on the Open Annotation7 standard of W3C. The annotation concept is added to MEMORAe-core 2 model as an information resource in its own right so it is a subclass of "mc2:Resource" concept. Each annotation has an author, a type, an index, a "Target" and a "Body". It is the annotation itself that links the annotation "Target" (the annotated data) with the annotation "Body" (the annotating data). The annotation is created by a "mc2:User". The type of the annotation indicates its nature (a comment, an explanation, a reference, a question, a discussion). The annotation "Target" (filler of the "mc2:hasTarget" object property) could be any concept in the model. This means that the "Target" could be an agent, a document, a forum post, a chat session file, a wiki page or any "Thing" in MEMORAe-core 2 model. The annotation "Body" is somehow "about" the "Target" of the annotation.

The "Body" of the annotation could be any resource "mc2:Resource" of the model. The annotation (as any other resource) is indexed by an index key "mc2:IndexKey" which is visible for a sharing space

The Annotation within MEMORAe Web Platform

Describing MEMORAe Web Platform

MEMORAe is a prototype web platform which is developed using web 2.0 technologies and based on MEMORAe-core 2 model. The platform aims to facilitate knowledge sharing within organizations. All types of resources are indexed by one or more concepts of a semantic map (Fig. 2) which is shared among all users. The semantic map is the graphical representation of an ontology that represents the specific terms of an organization. This semantic map is built by importing the ontology file (which could be generated by an ontology editor e.g., protégé) into the platform. This ontology describes "about what we collaborate" and it differs from one organization to another. In order to retrieve the resources indexed by a particular concept, the user choses the desired indexing concept from the semantic map. This concept is then placed in the middle of the screen and its color changes indicating that this is the "focus con-cept". If the user shares a particular resource, by default the resource is indexed by the "focus concept".

The users could also add other indexing concepts of the resource. The sharing spaces of the user could be viewed in parallel while navigating through the semantic map. This parallel view of sharing spaces is advantageous because the user can view in parallel the resources shared between different sharing spaces (different groups) but indexed by the same concept (the "focus concept"). This parallel view also permits the user to easily transfer a resource from one sharing space to another by means of "drag and drop". In this case, the resource is not physically duplicated in the hosting server. It only becomes visible / accessible by both sharing spaces.

Taking Annotation in MEMORAe Web Platform

The user of the platform can annotate information resources including documents, parts of them, notes, other annotations, etc. There are two ways to access the annotations, either when opening the annotated resource or directly through the resources list of the the sharing space. An example of the first way to access the annotation is when the user opens a document, he/she could retrieve all the annotations of this doc- ument which are shared in a sharing space to which he/she has access (cf.1 in Fig. 3). In order to create a new annotation, the user choses the text that he/she wants to annotate, precises the annotation type, the indexing concept(s) (Fig. 3). The user should also choose a sharing space to which he/she has access and in which the document is shared. The user then writes the content of the annotation and adds it. The selected text is the annotation "Target" and the content of the annotation is its "Body". The user can not only add annotations, but also filter the annotations of the document thanks to the search tool (cf.2 in Fig. 3) which is integrated to the document viewer. With such a tool, it is possible to filter the annotations of the document by type, date, author, indexing concept, sharing space (to which the user has access), etc. The second way to access the annotation is through its related sharing space. This is because the annotation is modeled as an information resource in its own right so it is accessible in the related sharing spaces when the "focus concept" is the annotation's indexing concept. When the user clicks on an annotation which is visible in the sharing space, the annotation is opened within its annotated resource. This means that the resource is being accessible by its annotations which are indexed by the concepts of the semantic map.

A USE CASE WITHIN "TOUR EQUIPEMENT" ENTERPRISE

"Tour Equipement" is a small enterprise (14 employed persons) which is specialized in the mechanical production with 50 years of experience. The enterprise is situated in the Picardy region in France. The enterprise hierarchy is composed of: owner-manager, technical manager, production manager, commercial manager and administrative manger. In addition, there are 9 blue-collar workers in the workshop. The process of organizational learning is highly affected by the size of the organization. So this process is specific and needs a none traditional approach in SMEs [START_REF] Atrash | A semantic model for small and medium-sized enterprises to support organizational learning[END_REF]. This is due to the significant relative "weight" of each member in SMEs (Mahe. [START_REF] De Boislandelle | L'effet de grossissement chez le dirigeant de pme: ses incidences au plan du management des hommes et de la grh. communication au Illème CIFPME[END_REF]. As a consequence, one member could play multiple roles at the same time. This multitasking is a fundamental aspect that have an impact on the organizational learning in SMEs. In addition, there are very few hierarchical levels with direct supervision and coordination between the members. As a result, employees and the owner-manager have direct interaction and this coordination is usually more made in the action than based on prescriptions and codified rules [START_REF] Tsai | Learning in small and medium enterprises (smes) -take taiwanese smes as examples[END_REF]. Two interview sessions with "Tour Equipement" employees have re-cently took place in order to identify the special need for managing its knowledge. The first session focused on the main task held by each employee. The second session concentrated to retrieve their daily practices. This field study illustrated that the employees tend to take a lot of annotations during their daily work. As mentioned in section 2.3, sharing the annotations between the members of an organization supports the process of organizational learning within this organization. As a consequence, MEMORAe web platform with its collaborative annotation functionalities and its semantic model seemed an adequate solution which is dedicated to "Tour Equipement" need. MEMORAe web platform allows "Tour Equipement" employees not only to annotate documents (invoices, plans, images of the designed products), but also to share these annotations among each other. To take a concrete example of using MEMORAe web platform within "Tour Equipement" enterprise, let's suppose that following scenario: 1. The technical manager belongs to the "workshop" group. He/she shares a document that describes a particular order of a product. 2. The technical manager indexes the document by the "jaw chuck" concept of the semantic map (supposing that the "jaw chuck" is the ordered product). 3. While the production manager (who is also a member of the "workshop" group) is reading the document shared by technical manger, he/she finds a sentence that also corresponds to another type of chucks called "collet chuck". 4. The production manager decides to annotate the document by a commentary saying "This is also applicable for the collet chucks". 5. The production manager choses the sentence and adds his/her annotation. By considering this annotation as an information resource, the production manager could share his annotation with others. The annotation could be shared only in the sharing space of the containing document ("workshop" group in this case). 6. The production manager choses to index his annotation by the "collet chuck" concept of the semantic map. 7. Now this annotation is visible / accessible by the members of "workshop" group when the "focus concept" is "collet chucks" (Fig. 4). The members of the "workshop" group could see the sentence chosen by the production manager with his/her commentary ("This is also applicable for the collet chucks"). The members could also open the containing document if they want.

DISCUSSION

Taking back the "Tour Equipement" use case, we recognize that considering the annotation as an information resource enabled the production manager to share and index his/her annotation in order to be accessible by others. The members of "workshop" sharing space were able to access the document by the annotation of the production manager. With other collaborative learning platforms, the annotation of the production manager is considered to be as an integral or complementary part of the document. As a result, the indexing and sharing of the annotation is not possible and the only way to access the annotations is to open the annotated document itself. Our platform has overcome this limitation of annotation sharing by modeling this latter as an information resource in its own right. The annotation itself is accessible as being an information resource in the sharing space.

CONCLUSION AND FUTURE WORK

This paper presented an original semantic model that models the annotation as an information resource in its own right. This enables to share and index the annotation separately from the annotated resource. The model allows to create annotations that have a chat, a forum or a wiki "Body". We presented MEMORAe web platform for collaboration that uses MEMORAecore 2 model as a base. We illustrated how this platform implements and facilitates the collaborative annotation. This would support the circulation of ideas which in turns enhances the process of organizational learning. Future work could be done by applying the work of [START_REF] Li | Facilitating experience sharing in groups -collaborative trace reuse and exploitation[END_REF] to capitalize the traces of annotation-taking activities that took place within the enterprise.

Figure 1 :

 1 Figure 1: MEMORAe-core 2 model

Figure 2 :

 2 Figure 2: MEMORAe web platform

Figure 3 :

 3 Figure 3: Annotations in a document

Figure 4 :

 4 Figure 4: The annotation visible as an information resource in its sharing space.

http://www.programhouse.com/pal/

http://www.sync3.eu

http://www.bounceapp.com/

http://www.diigo.com/

http://www.icomment.com/

http://www.mystickies.com/

http://www.w3.org/ns/oa

ACKNOWLEDGEMENTS

We would like to thank the Picardy region for financing this project.