Jonathan Spitz

Karim Bouyarmane

Serena Ivaldi

Jean-Baptiste Mouret

Trial-and-Error Learning of Repulsors for Humanoid QP-based Whole-Body Control

Whole body controllers based on quadratic programming allow humanoid robots to achieve complex motions. However, they rely on the assumption that the model perfectly captures the dynamics of the robot and its environment, whereas even the most accurate models are never perfect. In this paper, we introduce a trial-and-error learning algorithm that allows whole-body controllers to operate in spite of inaccurate models, without needing to update these models. The main idea is to encourage the controller to perform the task differently after each trial by introducing repulsors in the quadratic program cost function. We demonstrate our algorithm on (1) a simple 2D case and (2) a simulated iCub robot for which the model used by the controller and the one used in simulation do not match.

I. INTRODUCTION

Like humans, humanoid robots need to carefully coordinate dozens of degrees of freedom for even the most basic tasks, like standing upright or walking [START_REF] Ivaldi | From humans to humanoids: the optimal control framework[END_REF]. This challenge can be tackled in a principled way with Quadratic Programmingbased Whole-Body Controllers (QB-based WBC) [START_REF] Ivaldi | Special issue on whole-body control of contacts and dynamics for humanoid robots[END_REF]: at each time-step, an optimizer minimizes a cost function that describes the task(s), under constraints that model the dynamics of the robot interacting with its environment [START_REF] Bouyarmane | On the dynamics modeling of free-floating-base articulated mechanisms and applications to humanoid whole-body dynamics and control[END_REF]. This optimization is performed many times per second by casting it as a quadratic program with linear constraints, which can be solved efficiently on modern computers.

The most fundamental assumption of QP-based WBC is that the model accurately captures the dynamics of both the robot and the environment. Unfortunately, no model is ever perfect and thus such controllers often fail when the real world and the model do not match, even when using accurate state estimators and even when assuming perfect state feedback from the robot (which allows for small perturbations to be absorbed to a certain extent). For instance, the robot's dynamics (contact forces, center of mass, friction cones, etc.) is rarely known with precision. Even with a good dynamics model extracted by CAD and refined by dynamics parameters identification [START_REF] Traversaro | Inertial parameter identification including friction and motor dynamics[END_REF], [START_REF] Traversaro | Inertial parameters identification and joint torques estimation with proximal force/torque sensing[END_REF], there are elasticities, nonlinearities and coupled dynamics effects which are impossible to model and measure accurately on a complex platform like a humanoid, especially in presence of multiple contacts [START_REF] Calandra | Learning inverse dynamics models with contacts[END_REF]. Some parts of the environment are also generally unknown, like the exact mass of objects or the friction of the floor, or might not be modeled accurately because of imperfect sensors. Ultimately, the robot may also be damaged [START_REF] Cully | Robots that can adapt like animals[END_REF], or some parts may be worn out. Overall, in practice, setting a QP-based WBC for humanoids almost always involves long hand-tuning sessions of the model and the cost function [START_REF] Modugno | Learning soft task priorities for safe control of humanoid robots with constrained stochastic optimization[END_REF].

The fact that a WBC can fail when its model is imperfect is not a problem per se: humans often fail when they have imperfect information or when their "internal model" is different (e.g., when they move under perturbations [START_REF] Burdet | The central nervous system stabilizes unstable dynamics by learning optimal impedance[END_REF] or after an injury). Humans, however, learn from their mistakes, i.e. they adapt their behavior until they find a way to achieve their objective. By contrast, a QP-based WBC with a fixed model and tasks structure will keep performing the same faulty behaviors.

Ideally, we would like to see humanoid robots that (1) attempt to achieve a whole body task with their WBC, [START_REF] Ivaldi | Special issue on whole-body control of contacts and dynamics for humanoid robots[END_REF] fail (e.g., fall down), and (3) try again until they achieve the desired task. We would also like the learning process to succeed after only a few trials (less than a dozen) and a few minutes [START_REF] Mouret | Micro-data learning: The other end of the spectrum[END_REF], [START_REF] Chatzilygeroudis | Black-box data-efficient policy search for robotics[END_REF], [START_REF] Deisenroth | Gaussian processes for data-efficient learning in robotics and control[END_REF], in particular because of the limited energetic autonomy of robots. The main question here is: "how to incorporate new information from the real world into a QP-based WBC?" Since a QP-based WBC assumes a perfect QP optimizer, only two elements can be updated in such a trial-anderror process: the cost function and the model (i.e., the constraints). The most classic approach is to update the model according to the data acquired during each trial, i.e. perform a classic model identification [START_REF] Hollerbach | Model identification[END_REF]. Nevertheless, identifying the model of a full humanoid is far from being straightforward, as (1) identification can seldom be performed with only proprioceptive sensors [START_REF] Traversaro | Inertial parameter identification including friction and motor dynamics[END_REF], and (2) for a humanoid structure, it might require exciting the system in specific ways which may be unsafe for the robot [START_REF] Yamane | Practical kinematic and dynamic calibration methods for force-controlled humanoid robots[END_REF]. More importantly, some effects cannot be captured by tuning the parameters of classic models. To take an extreme example, a humanoid walking through a flooded room would experience significant viscous forces, which are usually not taken into account in the classical model for the robot moving in an indoor environment.

Our main insight is that even if a model makes inaccurate predictions for some behaviors, this is not necessarily the case for all the behaviors [START_REF] Koos | Fast damage recovery in robotics with the t-resilience algorithm[END_REF], [START_REF] Koos | The transferability approach: Crossing the reality gap in evolutionary robotics[END_REF], [START_REF] Cully | Robots that can adapt like animals[END_REF], [START_REF] Oliveira | Optimization of humanoid walking controller: Crossing the reality gap[END_REF]. In the previous flooded room example, the viscous forces are likely to be negligible if the robot is moving slowly; therefore a learning process could discover that the WBC works fine when the robot moves slowly, without needing to update the model to take viscous forces into account. Similar situations are common when robots perform highly dynamic motions: while a perfect model might be required to move at high speed, a less accurate model might be enough for a lower speed motion. The redundancy of the robot also implies that many tasks can be achieved in different ways with equivalent costs. In case of damage, the redundancy of the robot plays a similar role: the behaviors that do not use the damaged parts (e.g., a blocked joint) will be accurately predicted by the model, whereas those that rely on broken ones will have very different outcomes [START_REF] Koos | Fast damage recovery in robotics with the t-resilience algorithm[END_REF], [START_REF] Cully | Robots that can adapt like animals[END_REF]. In other words, we can use an imperfect model if we know its limits.

In the present paper, we introduce this idea in the QPbased WBC framework for whole-body motion, leading to a novel learning approach. When the robot performs a wholebody movement that, at some point, fails (for example, the robot falls), it should try to avoid repeating the same behavior. This "information" should be added to the QP problem so that the controller takes into account the "failures". The key challenge is that we cannot simply add penalties for failed states because the "bad decision" (i.e., the control command and the state that caused at some point the failure) is very likely to have happened much before the moment when the robot actually "fails" or falls. In essence, this problem is the classic "temporal credit assignment problem" in reinforcement learning [START_REF] Sutton | Reinforcement learning: An introduction[END_REF], which is one of the most important problems of the field. For example, if a humanoid robot falls on the ground, then it reaches a failed state when it hits the ground; but penalizing the failed state would mean repulsing from the ground, which is something that we already know and is already identified as a bad state. Instead, at some point of its trajectory, the robot took a series of decisions that led to the failed state: these are the states that should be avoided. In classic reinforcement learning (e.g. Q-learning, see [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]), we would propagate the knowledge of the failed state to the previous state and start a new episode, but this means a prohibitive number of trials for a complex humanoid robot with many degrees of freedom (thousands in a complex space).

Our main concept is that we can update the cost function of the QP controller after each trial so that the robot tries to solve the task in different ways until it finds one that is satisfying. To do so, we use the state-space trajectory of failed trials to introduce repulsors along the trajectory that push the QP controller away from states that have already been visited, while still attempting to solve the task. Between each episode, a gradient-free optimization algorithm searches for the best repulsors so that the next trial is as different as possible while still "solving" the task. This new episodic, trial-and-error algorithm enables QP-based whole-body controllers to adapt in a few trials to unknown situations, like damage, and to imperfect models of the robot or its environment.

We show the effectiveness of our approach on a toyexample (a particle moving in 2D) and on a simulated iCub humanoid robot for a squatting task, in a situation where the robot model is wrong: the robot's feet are smaller in reality than in the QP model, which causes the QP controller to fail.

II. BACKGROUND

A. Humanoid QP-based whole-body control

Whole-body control for humanoid robots is essentially formulated by prioritized multi-task controllers with strict task priorities [START_REF] Prete | Prioritized motion force control of constrained fully-actuated robots: a task space inverse dynamics[END_REF] or multi-task controllers with soft task priorities (also called weights) [START_REF] Salini | Synthesis of complex humanoid whole-body behavior: A focus on sequencing and tasks transitions[END_REF], [START_REF] Bouyarmane | Using a multi-objective controller to synthesize simulated humanoid robot motion with changing contact configurations[END_REF]. A now well-established classical formulation for the latter is the quadratic programming (QP) formulation, which solves, at every timestep of the control loop, the following QP problem:

min q, f ,τ m ∑ k=1 w k gk -gd k 2 (1) under constraints M q + N = J T f + Sτ (2) J q + J q = 0 (3) f ∈ K (4) q min ≤ q ≤ q max ( 5
)
qmin ≤ q ≤ qmax (6)

τ min ≤ τ ≤ τ max (7) ∀ (i, j) ∈ ColPairs d(B i , B j ) > 0 , ( 8
)
where q is the configuration of the robot (including the 6D position and orientation of the floating-base), q and q are (as an abuse of notation) the configuration-space velocity and acceleration (thus respectively including the angular velocity and angular acceleration of the base, which are not the time derivatives of the base orientation representation), M is the inertia matrix, N the gravity and Coriolis term, J the stacked Jacobian matrices at the contact points, f the vector composed of all the point contact forces, τ the actuator torques, S a selection matrix that maps the dimension of the actuated joints n -6 to the dimension of the configuration space n, K the cross product of the linearized Coulomb friction cones at the contact points, ColPairs the set of collision pairs (i, j), each pair inducing a collision avoidance constraint between the strictly convex bounding volumes of body B i of the robot and body B j of either the robot or the environment, and d is the corresponding distance function between these bounding volumes. Equations ( 5), [START_REF] Calandra | Learning inverse dynamics models with contacts[END_REF], and ( 8) are converted into linear constraints on q by using finite differentiation and velocity dampers [START_REF] Vaillant | Multi-character physical and behavioral interactions controller[END_REF].

A task g k , with its relative weight w k , is any mapping R n → R n k , where n k is the dimension of the task. A task is characterized by its Jacobian matrix J k = ∂ g k ∂ q and a desired acceleration behaviour gd . A classical behaviour is the attractor behaviour, which is used to bring the task to a desired set-point value g ref k . The attractor behaviour writes:

gd k -α k (g k -g ref k ) -2 √ α k ġk . (9)
It models a critically-damped mass-spring-damper system with unit apparent mass, parameterizable stiffness α k , and critical damping 2 √ α k . This is the most used task in QP controllers. We use it in the examples below to make the humanoid robot perform a squatting motion. The attractor task in this example is on the center-of-mass (CoM) c with reference setpoint that is lowered from the standing up posture CoM c ref,1 to the crouching posture CoM c ref,2 . As opposed to using non-linear contrained optimisation for whole-body trajectory generation [START_REF] Moulard | Roboptim: an optimization framework for robotics[END_REF], a QP can be solved in few milliseconds and thus allows for online control.

B. Learning with humanoid robots

A large part of the work about learning motion controllers for humanoid robots has focused on the optimization of neural networks [START_REF] Hein | Evolution of biped walking using neural oscillators and physical simulation[END_REF], [START_REF] Mordatch | Interactive control of diverse complex characters with neural networks[END_REF] or Central Pattern Generators (CPG) [START_REF] Hein | Evolution of biped walking using neural oscillators and physical simulation[END_REF], [START_REF] Oliveira | Multi-objective parameter cpg optimization for gait generation of a biped robot[END_REF] in simulation, with the hope of transferring the optimized controller to the physical robot; some others rely on more classic reinforcement learning approaches (e.g. Q-learning) and learn discrete policies (e.g., [START_REF] Jeong | Efficient learning of stand-up motion for humanoid robots with bilateral symmetry[END_REF]). However, all these approaches assume that the simulation perfectly captures the dynamics of the robot. The few experiments performed with real robots involve learning very few parameters (typically from 2 to 4) for simple walking patterns [START_REF] Tedrake | Learning to walk in 20 minutes[END_REF], [START_REF] Calandra | Bayesian optimization for learning gaits under uncertainty[END_REF], because only a few dozen of controller evaluations can be reasonably performed with a robot.

While interesting from an artificial intelligence perspective, these learning approaches are far from being competitive with QP-based WBC: they can only generate simple motion for a single task (e.g. walking forward) and are often openloop. In addition, they are not compatible with QP-based WBC, which prevents the two communities to exchange ideas and progress together.

A handful of papers combine QP-based WBC with some form of learning (e.g. [START_REF] Bouyarmane | Brain-machine interfacing control of whole-body humanoid motion[END_REF]). Modugno et al. [START_REF] Modugno | Learning soft task priorities for control of redundant robots[END_REF] exploited a black-box optimizer (CMA-ES [START_REF] Hansen | The cma evolution strategy: a comparing review[END_REF]) to learn the temporal profiles of the task weights of a QP-based controller, using a simulated robot. In [START_REF] Modugno | Learning soft task priorities for safe control of humanoid robots with constrained stochastic optimization[END_REF] they used constrained variants of CMA-ES to learn safe task weights that guarantee that the controller never violates constraints. However, the optimization was still done offline and not on the real robot. Mukovskiy et al. [START_REF] Mukovskiy | Adaptive synthesis of dynamically feasible full-body movements for the humanoid robot HRP-2 by flexible combination of learned dynamic movement primitives[END_REF] learned movement primitives from human motion captures, and combined them with model predictive control and planning to generate whole body motions on the HRP-2 robot. Clever et al. [START_REF] Clever | Cocomopl: A novel approach for humanoid walking generation combining optimal control, movement primitives and learning and its transfer to the real robot HRP-2[END_REF] used motion generated in simulation with a QP-based WBC to learn motion primitives, which can then be employed instead of the QP-based WBC while having a lower computational cost. Overall, these papers use learning in simulation only and aim at making whole body control more reliable and less computationally demanding. Contrary to the present paper, they do not aim at incorporating data from failed executions into the controller itself. Although not tested on a physical robot (to our knowledge), the approach proposed by Lober et al. [START_REF] Lober | Efficient reinforcement learning for humanoid whole-body control[END_REF] is probably the closest to the present work. In this work, the authors used Bayesian Optimization (BO) [START_REF] Cully | Robots that can adapt like animals[END_REF], which is a model-based black-box optimization algorithm, to move an intermediate waypoint for a QP-based WBC. However, as noted by the author, BO does not scale besides a few parameters (about 5 to 10 parameters to optimize).

The same observation was done by Antonova et al. [START_REF] Antonova | Sample efficient optimization for learning controllers for bipedal locomotion[END_REF] that used BO and CMA-ES to optimize the 16 parameters of a walking controller for a simulated planar robot.

Finally, in a study related to the present paper, but not directly related to learning, Gori et al. used force fields as attractors and repulsors to model targets and obstacles inside a reaching/tracking controller for the upper-body of iCub [START_REF] Gori | Dforc: a real-time method for reaching, tracking and obstacle avoidance in humanoid robots[END_REF]. The authors, however, only applied their approach to the upper-body of the robot on a fixed base, and relied on real-time perception of visual targets and obstacles. In other words, they did not attempt to learn, that is, to improve performance after several trials; instead, they only adapted the current controller to the environment.

C. Transferability in robot learning

It is well documented that optimizers overfit simulators most of the time, which leads to behaviors that are highperforming in simulation, but low-performing in reality. This issue is commonly called the "reality gap" [START_REF] Jakobi | Noise and the reality gap: The use of simulation in evolutionary robotics[END_REF], [START_REF] Koos | The transferability approach: Crossing the reality gap in evolutionary robotics[END_REF], [START_REF] Mouret | Crossing the reality gap: a short introduction to the transferability approach[END_REF].

Many ideas have been explored to cross this "reality gap", especially in evolutionary robotics. The proposed solutions range from adding noise to the simulation [START_REF] Jakobi | Noise and the reality gap: The use of simulation in evolutionary robotics[END_REF], [START_REF] Del Prete | Robustness to joint-torque-tracking errors in task-space inverse dynamics[END_REF] to automatically improving simulators [START_REF] Moeckel | Gait optimization for roombots modular robotsmatching simulation and reality[END_REF], [START_REF] Chatzilygeroudis | Black-box data-efficient policy search for robotics[END_REF]. One of the most successful approaches is the "transferability approach" [START_REF] Koos | The transferability approach: Crossing the reality gap in evolutionary robotics[END_REF], [START_REF] Koos | Fast damage recovery in robotics with the t-resilience algorithm[END_REF], [START_REF] Mouret | Crossing the reality gap: a short introduction to the transferability approach[END_REF]: instead of attempting to correct the simulator, the transferability approach hypothesizes that the simulator is accurate for some behaviors and not others; it is therefore possible to (1) learn the limits of the simulation, which is a supervised learning problem, and (2) encourage the learning process to select behaviors that are within these limits.

This idea was recently used to learn new walking policies for a damaged 6-legged robot in less than 2 minutes / a dozen trials [START_REF] Cully | Robots that can adapt like animals[END_REF]. In these experiments, the robot can find a working policy because some behaviors from the simulated, intact robot perform the same on the damaged, real robot (typically because they do not rely on the damaged part). Put differently, the algorithm finds the subset of high-performing solutions that work similarly in the simulated, intact robot and the physical, damaged robot. However, this algorithm does not fit the QP-based WBC framework, since it is designed to learn parametrized policies (e.g. CPGs or neural networks). In the present work, we exploit the same concept of transferability, but we formulate it in a way that leverages the benefits of modern WBC.

III. REPULSOR LEARNING

A. Repulsor behavior with the QP controller

When the robot executes a QP-controlled motion that leads to a failure (e.g. the robot falling down, the QP failing to find a solution, etc.), we want to instruct the controller to avoid that motion. Let t → q fail (t) be the trajectory in the configuration space, corresponding to such an ultimately failing motion. The trajectory is discretized in a number n r of repulsor configurations (q fail 1 , . . . , q fail n r ). In order to write a QP-compatible repulsor task from a repulsor configuration q fail j , we take inspiration from the behavior of the Coulomb's inverse-square law between electrically charged point particles. Considering the current configuration q and the the repulsor configuration q fail j as two positive electric charges, the desired behavior writes:

min q q - ∆ ∆ 3 2 , ∆ β q -q fail j , ( 10
)
where β is a diagonal matrix with non-negative, and at least one positive, elements. Changing the elements in β affects the repulsion strength along each coordinate, which can also be set to zero. Let us denote the desired acceleration of the repulsor behavior from q fail j as:

qrep (q fail i ) ∆ ∆ 3 . ( 11
)
Adding the set of repulsors from the failed motion to the QP (1) with respective weights (w rep 1 , . . . , w rep n r ), the latter becomes:

min q, f ,τ m ∑ k=1 w k gk -gd k 2 + n r ∑ j=1 w rep j q -qrep (q fail j ) 2 ( 12
)
under constraints (2) to (8).

As described in Section II-A, a classical QP task behavior is to attract the task to a desired set-point, using springdamper dynamics [START_REF] Burdet | The central nervous system stabilizes unstable dynamics by learning optimal impedance[END_REF]. When there is a mismatch between the QP model and reality, this behaviour can cause the robot to fail. Our insight is that using the data from failed attempts to add repulsor tasks will cause the QP to explore away from previously visited states, while still trying to complete the task. The individual joint gains (β ) determine how much each joint is repulsed by the repulsor, while the task weights (w rep j ) determine the strength of each repulsor. Fig. 1 illustrates this behaviour in a simple twodimensional state-space where there is a mismatch between the QP model and the real world. In example A, the hatched area represents the mismatch between the real world robot and its simulated model (i.e., the model used to compute the controls) which drives the state "downwards" preventing the QP to reach the task's goal. Adding repulsors on the failed trajectory causes the QP to explore away from the hatched area and complete the task (A.2). In the second case (B.1 and B.2), we reach a failed state when entering the hatched area. Adding the repulsors (red triangles) effectively changes the path followed by the QP in B.2, which approaches the goal from another configuration.

B. Optimizing the repulsors

The position of the added repulsors is determined by the trajectories previously explored by the QP-based WBC. However, the individual joint gains (β ) and the weight of each repulsor task (w rep j ) need to be tuned: if they are too high, the QP-based WBC will not solve the task (the repulsors will dominate the cost function of the quadratic program); if they are too small, then the next behavior is likely to be very close to the current failed ones, and therefore likely to fail as well. As a consequence, we need to optimize the gains and the weights so that the QP-based WBC solves Fig. 1. Intuition of the repulsors approach, shown in a 2D state-space for simplicity. Each panel shows the path followed by the state from the start (blue, filled) to the task goal (green, hollow). Hatched areas show a mismatch between the QP model and the real world. Repulsors are shown with red triangles. the task as best as possible, while being as far as possible from the previous failed attempts.

These two objectives can be evaluated for a vector of individual joint gains diag(β ) and a set of i • n r repulsor weights W = [w rep 1 , . . . , w rep i×n r ] by running the QP controller (Eq. 12) for T time-steps without interacting with the physical robot, that is, by simulating the robot with the same model as the QP controller, and computing the two following cost functions: (1) the average distance of the QP-generated trajectory from each repulsor (c E ) and ( 2) the tracking error of the QP task (c T ). More formally, we compute:

c E (β ,W ) 1 i • n r T 0 i•n r ∑ j=1 exp -q -q fail j 2 (13) c T (β ,W ) T 0 m ∑ k=1 w k g k -g d k 2 dt , ( 14
)
where i is the current episode number and T is the duration of each episode. We normalize c E and c T using a Monte Carlo estimate of the bounds for each cost. More specifically, we run the QP controller K times (e.g., K = 100) with random values for β and W ; we estimate [c E , c T ] for each run; then, we normalize c E and c T using the 5 th and 95 th percentiles (to avoid potential outliers):

C E (β ,W ) c E (β ,W ) -I 5% (c E ) I 95% (c E ) -I 5% (c E ) (15)
C T (β ,W ) c T (β ,W ) -I 5% (c T ) I 95% (c T ) -I 5% (c T ) (16)
where I 5% (x) denotes the 5 th percentile of x and I 95% (x) the 95 th percentile. Lastly, we combine C E and C T in a single cost function C:

C(β ,W ) λ •C E (β ,W ) + (1 -λ ) •C T (β ,W ) + P(t) (17)
where λ is a user-defined parameter that represents the tradeoff between the two cost functions, i.e. between exploration and exploitation. A penalty P(t) is added to the cost if a failed state is reached before the end of the allotted episode time:

P(t) = 2 t T allotted ( 18
)
C(β ,W ) is not differentiable since it involves solving a QP program at every time-step. We therefore consider it as a black-box function that we optimize with CMA-ES 1 [START_REF] Hansen | The cma evolution strategy: a comparing review[END_REF], a state-of-the-art global optimizer for non-linear, stochastic, black-box global optimization. This optimization typically requires hundreds of calls to the cost function, which makes the overall optimization computationally demanding (at least several minutes for a humanoid using a modern computer). Nevertheless, our aim is primarily to reduce the interaction time, that is, the time spent trying controllers on the real robot, because we assume that computers will be faster and faster in the future. In addition, CMA-ES can take full advantage of multi-core computers and clusters to speed up the computation. It is also important to highlight that the optimization becomes harder after each episode, since we increase the number of parameters to optimize after each episode on the physical robot. Our approach is therefore not likely to work with more than a dozen of episodes; it still fits our use case well because we aim at performing at most a dozen of learning episode with the physical robot.

C. Episodic learning

The learning algorithm searches for high-performing, alternative control strategies until it has exhausted its budget of episodes (or until a satisfying solution is found). Algorithm 1 details the full learning loop, which is based on three main steps:

1) attempt to complete the task using the QP controller in the real world (with the physical robot); record the trajectory and the tracking cost c T (β ,W ) (line 6); 2) add new repulsors R using the state-space trajectory q (i) of the last episode (line 11); 3) optimize the parameters of the repulsors (β ,W ) with CMA-ES and the QP controller, using the model of the controller as a simulator (line 12). After each episode, the robot is reset to its initial position. The output of the algorithm is the set of repulsors, joint gains, and repulsor weights that correspond to the best tracking cost in the real world. 1 We use the implementation of the libcmaes library: https:// github.com/beniz/libcmaes β * ,W * ← 0, 0 best parameters 5:

for i from 1 to N do for each episode 6:

q (i) ← Run episode in real world using QP controller with R(β ,W ) and compute c T (β ,W ) (Eq. 14 for j from 1 to n r do add new repulsors

12: R ← R ∪ q (i) (t j ), t j = j-1 n r -1 T 13: β ,W ← argmin(SIMEPISODE(R)) CMA-ES 14: return R * , β * ,W * 15: procedure SIMEPISODE(R) 16:
Run episode using QP model, controlled by QP with R(β ,W ) (Eq. 12)

17:

Calculate exploration cost, C E , using (Eq. [START_REF] Hollerbach | Model identification[END_REF][START_REF] Koos | Fast damage recovery in robotics with the t-resilience algorithm[END_REF] 18:

Calculate task cost, C T , using (Eq. [START_REF] Yamane | Practical kinematic and dynamic calibration methods for force-controlled humanoid robots[END_REF][START_REF] Koos | The transferability approach: Crossing the reality gap in evolutionary robotics[END_REF] 19:

return C(β ,W ) (Eq. 17)

IV. EXPERIMENTAL RESULTS

A. 2D particle

Our first objective is to validate the concept of repulsor learning on a simple and visual example (Fig. 2). To do so, we implemented our algorithm for a simple two-dimensional particle of mass 1 kg that has to start from state (1, 0) and reach state (-1, 0). At each time-step, the QP controller chooses the magnitude of a 2D force, which is applied on the particle with the standard equation of dynamics. To introduce a mismatch between the QP model and the "real world", we placed a circular obstacle of radius 0.3 around (0, 0) which is unknown to the QP controller. Hitting the obstacle puts the particle in a "failed state", which halts the controller. In higher-dimensional spate spaces, the equivalent of this obstacle would be a zone in which the robot fails, for instance, a zone of the state-space in which a humanoid robot fails to maintain its balance. After each episode, we add 6 repulsors, resulting in 8 to 32 parameters to optimize2 , depending on the episode number. Since the optimization procedure is stochastic, we replicate each experiment 20 times to gather statistics. To optimize the cost, CMA-ES is given a budget of 500 calls to the cost function.

The results show that three episodes are enough to reach the target state (Fig. 2A). In a typical run (Fig. 2B), the particle first hits the obstacle (for which there is a mismatch between the model and the "reality"), which is expected since the controller has no knowledge of the obstacle. Repulsors are then added, but the second episode is often too close to the obstacle. At the third episode, the particle usually reaches the target state. After this episode, the algorithm explores more complex trajectories, but the resulting trajectories often have a high tracking error because they have to be different from the "good" trajectory that was found at the third episode.

B. iCub squatting with a mismatch in feet geometry

We then evaluate our approach with a QP-based WBC for the iCub robot, with a mismatch between the internal model of the QP controller and the model simulated in Gazebo 3 . iCub is a 53-DOF full humanoid robot, with 7- 3 In this case, the simulated robot in Gazebo is the "real world" robot. DOF arms, 3-DOF torso and 6-DOF legs. It is fully opensource in both mechanics and software [START_REF] Natale | The iCub Platform: A Tool for Studying Intrinsically Motivated Learning[END_REF]. Its dynamics model, represented in a URDF format, is used by a software abstraction layer to control the simulated robot in Gazebo as if it was the real one [START_REF] Romano | A whole-body software abstraction layer for control design of free-floating mechanical systems[END_REF]. Wrenches, contact forces and center of mass are computed for both the real and simulated robot by open-source libraries for dynamics estimation [START_REF] Fumagalli | Force feedback exploiting tactile and proximal force/torque sensing[END_REF]. To optimize the cost, CMA-ES is given a budget of 500 calls to the cost function.

We created a QP-based WBC for iCub using the MC-RTC framework [START_REF] Bouyarmane | On the dynamics modeling of free-floating-base articulated mechanisms and applications to humanoid whole-body dynamics and control[END_REF]. The controller is composed of a position task for the robot's center of mass (CoM), the left hand and the right hand. Each position task switches its set-point position every t period seconds, taking iCub from a standing to a crouching configuration and back. When both the QP controller and Gazebo, i.e., the "real world", have the exact same model, iCub is able to perform the squatting task with the "classic" QP controller with three tasks (and no repulsors). However, we introduce a mismatch to the QP model that causes iCub to fail when performing the task. Specifically, we provide iCub with a different (smaller) pair of feet, as shown in Figure 3, which is a common occurrence in this platform as different variations of it are used in labs around the world. The model in the QP controller no longer reflects the real world robot: as expected, the "classic" QP controller with the three tasks fails, and the robot falls.

Therefore, we start learning the repulsors as described in Section III. The controlled robot has 53DOF, which would result in a 53-dimensional repulsor if all the joints would be considered (more if the full state would be considered, including velocities and accelerations). However, most of the joints of iCub are not "critical" for balancing (e.g., 9 DOF in each hand). For this reason, and for keeping the number of parameters to optimize as low as possible, we designed a repulsor state of 8-DOF, with the following joints: ["torso pitch", "torso roll", "torso yaw", "neck pitch", "l hip pitch", "r hip pitch", "l knee", "r knee"].

We run the learning algorithm for 6 episodes, adding 6 new repulsors after each episode and optimizing their parameters before making a new attempt at fulfilling the task with the "real robot". The number of parameters to optimize is therefore dim(β ) + dim(W ) × i = 8 + 6 × i, ranging from 14 (i = 1, first episode) to 38 (i = 5, last episode).

There is a clear improvement in the task performance when using repulsors, as seen in Fig. 4. As more trials are performed and new repulsors are added, the performance increases further. Although the robot is not able to perform the same squatting motion as expected by the QP-based WBC (because the QP controller is using a wrong model), it is still able to perform a comparable squatting motion without falling down (see the Supplementary Video). The CoM trajectories from one learning process are shown in Fig. 5. Here we can see that the original trajectory, i.e. without repulsors (shown in blue), is not able to make the robot stand up after performing the squat (the robot falls). In three of the following trials iCub performed a smaller squat (see the Supplementary video) and was able to go back to a standing position.

V. CONCLUSION AND DISCUSSION

Learning repulsors is a novel and promising approach to mix QP-based WBC with trial-and-error learning. It enables applying QP controller to real world robots, despite the inevitable model errors, and without requiring to identify or improve the robot model used by the QP controller. In the two experimental setups of this paper, only 3 to 5 episodes are required to find a controller that works in spite of an important mismatch between the model used in the controller and the real world. This low number of episodes makes it easy to use our approach on physical humanoids robot and significantly lowers the risk of breaking them.

Nevertheless, the way we learn repulsors is only a first "proof of concept" of the idea and we believe the concept can be improved in several ways. First, the trade-off between solving the task and exploring needs to be well-tuned to obtain satisfying results. In future work, we will explore the use of stack-based formulations of the whole-body problem [START_REF] Prete | Prioritized motion force control of constrained fully-actuated robots: a task space inverse dynamics[END_REF] (instead of the weight-based approach followed here), which would change the way we combine the repulsors with the main task.

A second direction of improvement is to accelerate (and potentially improve) the optimization of the repulsors by using a more data-efficient optimization algorithm. For instance, Bayesian optimization [START_REF] Cully | Robots that can adapt like animals[END_REF], [START_REF] Calandra | Bayesian optimization for learning gaits under uncertainty[END_REF] with an appropriate prior could require fewer calls to the cost function to find high-performing solutions. In addition, the proposed algorithm does not use all the available information. For instance, the score achieved in the real world is currently ignored by the algorithm, whereas it could be used to guide the search for the best repulsors.

Overall, learning repulsors offers a new view of humanoid robot learning that bridges the gap between modern whole body control and reinforcement learning. We believe it opens many new research avenues to make humanoids robot that Fig. 5. Center of mass trajectories of the iCub robot for 5 episodes of a typical learning process in the "real world" (here the Gazebo simulation with small feet). The original trajectory, i.e. without repulsors, is shown in blue. Episodes 2, 4 and 5 led to satisfying behaviors (not falling, squatting movement). See the supplementary Video for a a visualization of the behaviors.

  )

Fig. 2 .

 2 Fig.2. Tracking cost for the particle task (20 replicates). A: Median of the best tracking cost since the beginning of the learning process and 25 th -75 th percentiles. The task is solved after only 3 to 4 seconds of interaction time (3 to 4 episodes). B: Behavior of a typical controller. The first two episodes (trajectories 1 and 2) hit the obstacle; the third tested trajectory solves the task and obtains the best tracking cost; the fourth trajectory is very different from the third trajectory, but it obtains a higher cost. The selected controller is the third one.

Fig. 3 .

 3 Fig.3. The mismatch between the "real world" iCub (left, small feet) and its internal model in the QP controller (right, large feet) causes the iCub robot to fail in the real world, even though the QP-based WBC generates a feasible joints trajectory. The "real world" here is in Gazebo.

Fig. 4 .

 4 Fig.[START_REF] Traversaro | Inertial parameter identification including friction and motor dynamics[END_REF]. Tracking cost for the iCub squatting task (13 replicates). Median of the best tracking cost since the beginning of the learning process and 25 th -75 th percentiles. The task performance increases (lower cost) on average as more trials are performed, with the major improvement between the first and second trials.

The particle has a 2-dimensional state. The number of parameters is 2 + 6 × i, where 6 is the number of repulsors and i the learning episode.

can both benefit from sophisticated control methods and adapt to unexpected situations.

VI. ACKNOWLEDGMENT

The authors would like to thank Brice Clement for the engineering support; the IDH team for their help with the QP controller (https://github.com/ jrl-umi3218/Tasks); Gabriele Nava and Silvio Traversaro for their help with the iCub's URDF.

This work received funding from the Grand Est region (project "LocoLearn"), Inria (project "wbCub"), the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (GA no. 637972, project "ResiBots"), and the European Commission (GA no. 731540, H2020 project "An.Dy").


Daniel Gonçalves
email: daniel.goncalves@lirmm.fr

Lucas Isenmann
email: lucas.isenmann@lirmm.fr

Claire Pennarun
email: claire.pennarun@labri.fr

Planar Graphs as L-intersection or L-contact graphs *

The -intersection graphs are the graphs that have a representation as intersection graphs of axis parallel shapes in the plane. A subfamily of these graphs are { , |, -}-contact graphs which are the contact graphs of axis parallel , |, andshapes in the plane. We prove here two results that were conjectured by Chaplick and Ueckerdt in 2013. We show that planar graphs are -intersection graphs, and that triangle-free planar graphs are { , |, -}-contact graphs. These results are obtained by a new and simple decomposition technique for 4-connected triangulations. Our results also provide a much simpler proof of the known fact that planar graphs are segment intersection graphs.

Introduction

The representation of graphs by contact or intersection of predefined shapes in the plane is a broad subject of research since the work of Koebe on the representation of planar graphs by contacts of circles [START_REF] Koebe | Kontaktprobleme der konformen Abbildung[END_REF]. In particular, the class of planar graphs has been widely studied in this context.

More formally, assigning a shape X of the plane for each vertex of a graph G, we say that G is a X-intersection graph if there is a representation of G such that every vertex is assigned to a shape X, and two shapes X 1 , X 2 intersect if and only if the vertices they are assigned to are adjacent in G. In the case where the shape X is homeomorphic to segments (resp. discs), a X-contact system is a collection of X shapes such that if an intersection occurs between two shapes, then it occurs at one of their endpoints (resp. on their border). We say that a graph G is a X-contact graph if it is the intersection graph of a X-contact system. This definition can be easily generalized if the representation of each vertex is chosen among a family of shapes.

The case of shapes that are homeomorphic to a disc has been widely studied; see for example the literature for triangles [START_REF] De Fraysseix | On Triangle Contact Graphs[END_REF][START_REF] Gonçalves | Triangle contact representations and duality[END_REF], homothetic triangles [START_REF] Kaufmann | Maxtolerance graphs as intersection graphs: Cliques, cycles and recognition[END_REF][START_REF] Schrezenmaier | Homothetic triangle contact representations[END_REF], axis parallel rectangles [START_REF] Thomassen | Plane representations of graphs[END_REF], squares [START_REF] Kenyon | Dimers, tilings and trees[END_REF][START_REF] Schramm | Square tilings with prescribed combinatorics[END_REF], hexagons [START_REF] Gansner | Optimal Polygonal Representation of Planar Graphs[END_REF], or convex bodies [START_REF] Schramm | Combinatorically Prescribed Packings and Applications to Conformal and Quasiconformal Maps[END_REF]. We here focus on the representation of planar graphs as contact or intersection graphs, where the assigned shapes are segments or polylines in the plane. The simplest definition of representation of graphs by intersection of curves is the so-called string-representation: each vertex is represented by a curve, and two curves intersect if and only if the vertices they represent are adjacent in the graph. It is known that every planar graph has a string-representation [START_REF] Ehrlich | Intersection graphs of curves in the plane[END_REF]. However, this representation may contain pairs of curves that cross any number of times. One may thus take an additional parameter into account, namely the maximal number of crossings of any two of the curves: a 1-string representation of a graph is a string representation where every two curves intersect at most once. The question of finding a 1-string representation of planar graphs has been solved by Chalopin et al. in the positive [START_REF] Chalopin | Planar graphs have 1-string representations[END_REF], and additional parameters are now studied, like order-preserving representations [START_REF] Biedl | Order-preserving 1-string representations of planar graphs[END_REF].

Segment intersection graphs are in turn a specialization of the class of 1string graphs. It is known that bipartite planar graphs are {|, -}-contact graphs [START_REF] Ben-Arroyo Hartman | On grid intersection graphs[END_REF][START_REF] De Fraysseix | Representation of planar graphs by segments[END_REF] (i.e. segment contact graphs with vertical or horizontal segments). De Castro et al. [START_REF] Castro | Triangle-free planar graphs as segment intersection graphs[END_REF] showed that triangle-free planar graphs are segment contact graphs with only three different slopes. De Fraysseix and Ossona de Mendez [START_REF] De Fraysseix | Representations by contact and intersection of segments[END_REF] then proved that a larger class of planar graphs are segment intersection graphs. Finally, Chalopin and the first author extended this result to general planar graphs [START_REF] Chalopin | Every planar graph is the intersection graph of segments in the plane[END_REF], which was conjectured by Scheinerman in his PhD thesis [START_REF] Scheinerman | Intersection Classes and Multiple Intersection Parameters of Graphs[END_REF].

A graph is said to be a VPG-graph (Vertex-Path-Grid) if it has a contact or intersection representation in which each vertex is a path of vertical and horizontal segments (see [START_REF] Aerts | Vertex Contact Representations of Paths on a Grid[END_REF][START_REF] Cohen | Posets and VPG Graphs[END_REF]). Asinowski et al. [START_REF] Asinowski | Vertex intersection graphs of paths on a grid[END_REF] showed that the class of VPGgraphs is equivalent to the class of graphs admitting a string-representation. They also defined the class B k -VPG, which contains all VPG-graphs for which each vertex is represented by a path with at most k bends (see [START_REF] Felsner | Intersection graphs of L-shapes and segments in the plane[END_REF] for the determination of the value of k for some classes of graphs). It is known that B k -VPG ⊆ B k+1 -VPG, and that the recognition of graphs of B k -VPG is an NP-complete problem [START_REF] Chaplick | Bend-bounded path intersection graphs: Sausages, noodles, and waffles on a grill[END_REF]. These classes have interesting algorithmic properties (see for example [START_REF] Mehrabi | Approximation Algorithms for Independence and Domination on B 1 -VPG and B 1 -EPG Graphs[END_REF] for approximation algorithms for independence and domination problems in B 1 -VPG graphs), but most of the literature studies their combinatorial properties.

Chaplick et al. [START_REF] Chaplick | Planar Graphs as VPG-Graphs[END_REF] proved that planar graphs are B 2 -VPG graphs. This result was recently improved by Biedl and Derka [START_REF] Biedl | 1-string B 2 -VPG representation of planar graphs[END_REF], as they showed that planar graphs have a 1-string B 2 -VPG representation.

Various classes of graphs have been showed to have 1-string B 1 -VPG representations, such as planar partial 3-trees [START_REF] Biedl | 1-String B1-VPG Representations of Planar Partial 3-Trees and Some Subclasses[END_REF] and Halin graphs [START_REF] Francis | VPG and EPG bend-numbers of Halin graphs[END_REF]. Interestingly, it has been showed that the class of segment contact graphs is equivalent to the one of B 1 -VPG contact graphs [START_REF] Kobourov | Combinatorial and geometric properties of planar Laman graphs[END_REF]. This implies in particular that trianglefree planar graphs are B 1 -VPG contact graphs. This has been improved by Chaplick et al. [START_REF] Chaplick | Planar Graphs as VPG-Graphs[END_REF] as they showed that triangle-free planar graphs are in fact { , , |, -}-contact graphs (that is without using the shapes and ).

The restriction of B 1 -VPG to -intersection or -contact graphs has been much studied (see for example [START_REF] Felsner | Intersection graphs of L-shapes and segments in the plane[END_REF]) and it has been shown that they are in relation with other structures such as Schnyder realizers, canonical orders or edge labelings [START_REF] Chaplick | Equilateral L-contact graphs[END_REF]. The same authors also proved that the recognition ofcontact graphs can be done in quadratic time, and that this class is equivalent to the one restricted to equilateral shapes. Finally, the monotone (or linear) -contact graphs have been recently studied further, for example in relation with MPT (Max-Point Tolerance) graphs [START_REF] Ahmed | L-Graphs and Monotone L-Graphs[END_REF][START_REF] Catanzaro | Max point-tolerance graphs[END_REF].

Our contributions

The two main results of this paper are the following:

Theorem 1 Every triangle-free planar graph is a { , |, -}-contact graph.
Theorem 2 Every planar graph is a -intersection graph.

Both results were conjectured in [START_REF] Chaplick | Planar Graphs as VPG-Graphs[END_REF]. Theorem 1 is optimal in the sense that a { , |, -}-contact graph with n vertices has at most 2n -3 edges, while triangle-free planar graphs may have up to 2n -4 edges. However, up to our knowledge, the question of whether every triangle-free planar graph is a { , |}contact graph is open1 . Theorem 2 implies that planar graphs are in B 1 -VPG, improving the results of Biedl and Derka [START_REF] Biedl | 1-string B 2 -VPG representation of planar graphs[END_REF] stating that planar graphs are in B 2 -VPG. Since a -intersection representation can be turned into a segment intersection representation [START_REF] Middendorf | The max clique problem in classes of stringgraphs[END_REF], this also directly provides a rather simple proof of the fact that planar graphs are segment intersection graphs [START_REF] Chalopin | Every planar graph is the intersection graph of segments in the plane[END_REF]. Note that a simple modification of our method can be used to prove that 4-connected planar graphs have a B 3 -EPG representation [START_REF] Biedl | 4-connected graphs are in B 3 -EPG[END_REF], where vertices are represented by paths on a rectangular grid with at most 3 bends, and adjacency is shown by sharing an edge of the grid.

The common ingredient of the two results is what we call 2-sided neartriangulations. In Section 2, we present the 2-sided near-triangulations, allowing us to provide a new decomposition of planar 4-connected triangulations (see [START_REF] Biedl | The (3,1)-ordering for 4-connected planar triangulations[END_REF] and [START_REF] Whitney | A theorem on graphs[END_REF] for other decompositions of 4-connected triangulations). This decomposition is simpler than the one provided by Whitney [START_REF] Whitney | A theorem on graphs[END_REF] that is used in [START_REF] Chalopin | Every planar graph is the intersection graph of segments in the plane[END_REF]. In Section 3, we define thick -contact systems, (i.e., -contact representations in which the shapes have some thickness ε) with specific properties. We then show that every 2-sided near-triangulation can be represented by such a system. This result is used in Section 4 to prove Theorem 1. Then in Section 5 we use 2-sided near-triangulations to prove Theorem 2.

2-sided near-triangulations

In this paper we consider plane graphs without loops nor multiple edges. In a plane graph there is an infinite face, called the outer face, and the other faces are called inner faces. A near-triangulation is a plane graph such that every inner face is a triangle. In a plane graph G, a chord is an edge not incident to the outer face but that links two vertices of the outer face. A separating triangle of G is a cycle of length three such that both regions delimited by this cycle (the inner and the outer region) contain some vertices. It is well known that a triangulation is 4-connected if and only if it contains no separating triangle. Given a vertex v on the outer face, the inner-neighbors of v are the neighbors of v that are not on the outer face. We define here 2-sided near-triangulations (see Figure 1) whose structure will be useful in the inductions of the proofs of Theorem 2, and Theorem 7.

Definition 3 A 2-sided near-triangulation is a 2-connected near-triangulation T without separating triangle and such that going clockwise on its outer face, the vertices are denoted a 1 , a 2 , . . . , a p , b q , . . . , b 2 , b 1 , with p ≥ 1 and q ≥ 1, and such that there is no chord a i a j or b i b j (that is an edge (a p -removal) This operation applies if p > 1, if a p has no neighbor b i with i < q, and if none of the inner-neighbors of a p has a neighbor b i with i < q. This operation consists in removing a p from T , and in denoting b q+1 , . . . , b q+r in anti-clockwise order the new vertices on the outer face, if any. This yields a 2-sided near-triangulation T (see Figure 2a). (b q -removal) This operation applies if q > 1, if b q has no neighbor a i with i < p, and if none of the inner-neighbors of b q has a neighbor a i with i < p. This operation consists in removing b q from T , and in denoting a p+1 , . . . , a p+r in clockwise order the new vertices on the outer face, if any. This yields a 2-sided near-triangulation T . This operation is strictly symmetric to the previous one.

a i a j or b i b j such that |i -j| > 1). b 1 b 2 b 3 a 1 a 2 a 3
1 b 2 b q a p b q+r a p-1 b q-1 a 2 a 1 T (a) b 1 b q a p a p-1 b q-1 a 1 T b j a i T b T a x (b)
(cutting) This operation applies if p > 1 and q > 1, and if the unique common neighbor of a p and b q , denoted x, has a neighbor a i with i < p, and a neighbor b j with j < q. If x has several such neighbors, i and j correspond to the smaller possible values. This operation consists in cutting T into three 2-sided near-triangulations T , T a and T b (see Figure 2b):

-T is the 2-sided near-triangulation contained in the cycle formed by vertices (a 1 , . . . , a i , x, b j , . . . , b 1 ), and the vertex x is renamed a i+1 .

-T a (resp. T b ) is the 2-sided near-triangulation contained in the cycle (a i , . . . , a p , x) (resp. (x, b q , . . . , b j )), where the vertex x is denoted b 1 (resp. a 1 ).

Proof.

Suppose that a p has no neighbor b i with i < q and none of the inner-neighbors of a p has a neighbor b i with i < q. We denote b q+1 , . . . , b q+r the inner-neighbors of a p in anti-clockwise order such that b j is connected to b j+1 for every q ≤ j ≤ r. Let T be the graph obtained by removing a p and its adjacent edges from T . It is clear that T is a near-triangulation, and that it has no separating triangle (otherwise T would have one too). Furthermore, as there is no chord incident to a p , and as T has at least three vertices its outer face is bounded by a cycle, and T is thus 2-connected. As T is a 2-sided near-triangulation, T has no chord a i a j , with i, j < p, or b i b j with i, j ≤ q. By hypothesis, the inner-neighbors of a p have no neighbors b k with k < q, thus there is no chord b i b j with i ≤ q and q < j. There is no chord b i b j in T with q ≤ i < j. Otherwise the vertices a p , b i , and b j would form a triangle with at least one vertex inside, b i+1 , and at least one vertex outside, a p-1 : it would be a separating triangle, a contradiction. Therefore T is a 2-sided near-triangulation.

The proof for the b q -removal operation is analogous to the previous case. Suppose that we are not in the first case nor in the second one. Let us first show that p > 1 and q > 1. Towards a contradiction, consider that p = 1. Then as T is 2-connected, it has at least three vertices on the outer face and q ≥ 2. In such a case one can always perform the b q -removal operation, a contradiction.

Let us now show that a p is not adjacent to a vertex b i with i < q. Towards a contradiction, consider that a p is adjacent to a vertex b i with i < q. Then by planarity, b q (with q > 1) has no neighbor a i with i < p, and has no innerneighbor adjacent to a vertex a i with i < p. In such a case one can always perform the b q -removal operation, a contradiction. Symmetrically, we deduce that b q is not adjacent to a vertex a i with i < p.

Vertices a p and b q have one common neighbor x such that xa p b q is an inner face. Note that as there is no chord incident to a p or b q , then x is not on the outer face. They have no other common neighbor y, otherwise there would be a separating triangle ya p b q (separating x from both vertices a 1 and b 1 ).

As we are not in the first case nor in the second case, we have that a p (resp. b q ) has (at least) one inner-neighbor adjacent to a vertex b i with i < q (resp. a i with i < p). By planarity, x is the only inner-neighbor of a p (resp. b q ) adjacent to a vertex b i with i < q (resp. a i with i < p). We can thus apply the cutting operation.

We now show that T , T a and T b are 2-sided near-triangulations. Consider first T . It is clear that it is a near-triangulation without separating triangles. It remains to show that there are no chords a i a j or b i b j . By definition of T , the only chord possible would have x = a i+1 as an endpoint, but the existence of an edge xa k with k < i would contradict the minimality of i. Thus T is a 2-sided near-triangulation.

By definition, T a is also a near-triangulation containing no separating triangles. Moreover, there is no chord a k a l with i ≤ k ≤ l -2 as there are no such chords in T . Therefore T a is a 2-sided near-triangulation. We show in the same way that T b is a 2-sided near-triangulation. 2

3 Thick { }-contact system

A thick is a shape where the two segments are turned into ε-thick rectangles (see Figure 3a). Going clockwise around a thick from the bottom-right corner, we call its sides bottom, left, top, vertical interior, horizontal interior, and right.

A thick is described by four coordinates a, b, c, d such that a + ε < b and c + ε < d. It is thus the union of two boxes:

([a, a + ε] × [c, d]) ∪ ([a, b] × [c, c + ε]).
If not specified, the corner of a thick denotes its bottom-left corner (with coordinate (a, c)). In the rest of the paper, all the thick shapes have the same thickness ε.

Definition 5 Given a thick -contact system, a thick is said left if its horizontal interior is free (i.e., does not touch another ) and its left side is not contained in the side of another thick (see Figure 3b). Similarly, a thick is said bottom if its vertical interior is free and its bottom side is not contained in the side of another thick (see Figure 3c). Definition 6 A convenient thick -contact system (CTLCS) is a contact system with thick shapes (which implies that the thick shapes interiors are disjoint) with a few properties:

• Two thick shapes intersect either on exactly one segment or on a point (Figure 4 lists the allowed ways two shapes can intersect). If the intersection is a segment, then it must be exactly one side of a thick . If the intersection is a point, then it is the bottom right corner of one thick and the top left corner of the other one.

• Every thick is bottom or left.

Remark that the removal of any thick still leads to a CTLCS. This definition implies that in a CTLCS there is no three shapes intersecting as in Figure 5.

We now make a link between CTLCS and 2-sided near-triangulations (See Figure 6 for an illustration).

Theorem 7 Every 2-sided near-triangulation can be represented by a CTLCS with the following properties:

• every thick is included in the quadrant {(x, y) : x ≥ 0, y ≥ 0},

• a 1 has the rightmost corner and b 1 has the up-most corner, • every vertex a i is represented by a bottom thick whose corner has coordinates (x, 0), with x > 0, and

• every vertex b i is represented by a left thick whose corner has coordinates (0, y), with y > 0. Proof. We proceed by induction on the number of vertices. The theorem clearly holds for the 2-sided near-triangulation with three vertices. Let T be a 2-sided near-triangulation; it can thus be decomposed using one of the three operations described in Lemma 4. We go through the three operations successively.

a 1 b 1 a 2 a 3 b 2 b 3 x b 1 b 2 b 3 x a 1 a 2 a 3
b 1 b q b q+1 b q+r b 2 a 1 a 2 a p-1 (a) CTLCS of T b 1 b q b q+1 b q+r b 2 a 1 a 2 a p-1 a p (b) CTLCS of T
(a p -removal) Let T be the 2-sided near-triangulation resulting from an a premoval operation on T . By the induction hypothesis, T has a CTLCS with the required properties (see Figure 7a). We can now modify this CTLCS slightly in order to obtain a CTLCS of T (thus adding a thick corresponding to vertex a p ). Move the corners of the thick corresponding to vertices b q+1 , . . . , b q+r slightly to the right. Since these are left thick shapes, one can do this without modifying the rest of the system. Then one can add the thick of a p such that it touches the thick of vertices b q and a p-1 (as depicted in Figure 7b). One can easily check that the obtained system is a CTLCS of T and satisfies all the requirements.

(b q -removal) This case is strictly symmetric to the previous one.

(cutting) Let T , T a and T b be the three 2-sided near-triangulations resulting from the cutting operation described in Lemma 4. By induction hypothesis, each of them has a CTLCS satisfying the requirements of Theorem 7. Consider the CTLCS of T (see Figure 8). Move the corner of x = a i+1 slightly upward. Since x = a i+1 is a bottom vertex, one can do this without modifying the rest of the system. Then one can add the CTLCS of T a below vertex x and the one of T b on its left (see Figure 8, bottom). One can easily check that the obtained system satisfies all the requirements.

2 b 1 b 2 b j-1 b j b j+1 b q-1 b q x a p a p-1 a i+1 a i a 2 a 1 b j b j+1 b q-1 b q x x a p a p-1 a i+1 a i b 1 b 2 b j-1 b j x a i a 2 a 1

{ , |, -}-contact systems for triangle-free planar graphs

We can now use the CTLCS systems to prove Theorem 1. Recall that a { , |, -}contact system is a contact system with some , some vertical segments |, and some horizontal segments -, such that if an intersection occurs between two of these objects, then the intersection is an endpoint of one of the two objects. We need the following lemma as a tool (it is proved in appendix).

Lemma 8 For any plane triangle-free graph G, there exists a 4-connected triangulation T containing G as an induced subgraph.

We can now prove Theorem 1, which asserts that every triangle-free planar graph has a { , |, -}-contact system.

Proof. Consider a triangle-free planar graph G. According to Lemma 8, there exists a 4-connected triangulation T containing G as an induced subgraph. As the exterior face of T is a triangle, T is a 2-sided near-triangulation (denoting a 1 , b 2 , b 1 the three exterior vertices in clockwise order). By Theorem 7, T has a CTLCS and removing every thick corresponding to a vertex of T \ G leads to a CTLCS of G.

If a thick x has its bottom side included in the horizontal interior side of another thick y, then x is bottom, and so does not intersect anyone on its horizontal interior side. Furthermore, x does not intersect anyone on its right side nor on its bottom right corner. Indeed, if there was such an intersection with a thick z, then y and z would also intersect, contradicting the fact that G is triangle-free (see Figure 9). One can thus replace the thick of x by a thick |. Similarly, if a thick x has its left side included in the vertical interior side of a thick y, we can replace the thick of x by a thick -.

Note that now the intersections are on small segments, or on a point, between the bottom right corner of a thick or -, and the top left corner of a thick or |. Then, we replace each thick , |, andby thin ones as depicted in Figure 10. It is clear that we obtain a { , |, -}-contact system whose contact graph is G. This concludes the proof. An example of the process is shown in Figure 11. Figure 11: Given a CTLCS of a triangle-free graph G, we first replace some thick by thick | and thick -, and then replace every thick shape by a thin one according to Figure 10.

2 ε/2 ε/2 ε/2 ε/2 ε/2 ε/2

The -intersection systems

An -intersection system (LIS) is an intersection system of shapes where every two shapes intersect on at most one point. Using Theorem 7, one could prove that that every 4-connected triangulation has a LIS. To allow us to work on every triangulation (not only the 4-connected ones) we need to enrich our LISs with the following notion that was introduced in [START_REF] Felsner | Intersection graphs of L-shapes and segments in the plane[END_REF] under the name of private region.

An anchor can be seen as a union of three segments, or as the union of two . It has two corners, which correspond to the shapes corners. There are two types of anchors. A horizontal anchor is a set

[x 1 , x 3 ] × y 1 ∪ x 1 × [y 1 , y 2 ] ∪ x 2 × [y 1 , y 2 ]
where x 1 < x 2 < x 3 and y 1 < y 2 (see Figure 12a). The middle corner of such a horizontal anchor is defined as the point (x 2 , y 1 ). A vertical anchor is a set

x 1 × [y 1 , y 3 ] ∪ [x 1 , x 2 ] × y 1 ∪ [x 1 , x 2 ]
× y 2 where x 1 < x 2 and y 1 < y 2 < y 3 (see Figure 12b). The middle corner of such a vertical anchor is defined as the point (x 1 , y 2 ). Consider a near-triangulation T , and any inner face abc of T . Given a LIS of T , an anchor of abc is an anchor crossing the shapes of a b and c and no other , and such that the middle corner is in the square described by a, b and c as depicted in Figure 12. Figure 12: The two types of anchors (horizontal and vertical), and the two possible anchors for the 's of a triangle abc.

Definition 9 A full -intersection system (FLIS) of a near-triangulation T is a LIS of T with an anchor for every (triangular) inner face of T , such that the anchors are pairwise non-intersecting.

Let us now prove that every 2-sided near-triangulation admits a FLIS.

Proposition 10 Every 2-sided near-triangulation has a FLIS such that among the corners of the shapes and the anchors:

• from left to right, the first corners are those of vertices b 1 , b 2 , . . . b q and the last one is the corner of vertex a 1 , and As the of a i and a i+1 (resp. b i and b i+1 ) intersect, the FLIS is rather constrained. This is illustrated in Figure 14, where the grey region contains the corners of the inner vertices, and the corners of the anchors.

•
1 b 2 b 3 b q a p a 3 a 2 a 1 b 1 a p a 3 a 2 a 1 a p-1 b 1 b 2 b 3 b q a 1 b q-1
Figure 14: Illustration of Proposition 10 when p > 1 and q > 1, when p = 1 and q > 1, and when p > 1 and q = 1.

Proof. We proceed by induction on the number of vertices. The result clearly holds for the 2-sided near-triangulation with three vertices, whatever p = 1 and q = 2, or p = 2 and q = 1. Let T be a 2-sided neartriangulation with at least four vertices. By Lemma 4 we consider one of the following operations on T :

(a p -removal) Consider the FLIS of T obtained by induction and see in Figure 15 how one can add a for a p and an anchor for each inner face a p b j b j+1 with q ≤ j < q + r and for the inner face a p a p-1 b q+r . One can easily check that the obtained system verifies all the requirements of Proposition 10.

(b q -removal) This case is symmetric to the previous one.

(cutting) Consider the FLISs of T , T a and T b . Figure 16 depicts how to combine them, and how to add an anchor for xa p b q , in order to get the FLIS of T . One can easily check that the obtained system verifies all the requirements of Proposition 10.

2

We now prove Theorem 2 which asserts that every planar graph is aintersection graph. It is well known that every planar graph is an induced sub- graph of some triangulation (see [START_REF] Chalopin | Planar graphs have 1-string representations[END_REF] for a proof similar to the one of Lemma 8). Thus, given a planar graph G, one can build a triangulation T whose G is an induced subgraph. If one can create a FLIS of T , then it remains to remove the shapes assigned to vertices of T \ G along with the anchors in order to get a -representation of G. In order to prove Theorem 2, we thus only need to show that every triangulation admits a FLIS. Proposition 11 Every triangulation T with outer-vertices x, y, z has a FLIS such that among the corners of the shapes and the anchors:

b j-1 b q b q-1 x a i a i-1 a p a p-1 a 1 b j b q b q-1 x x a i a p a p-1 b 1 b j b j-1 x a i a i-1 a 1
• the corner of x is the upmost and leftmost,

• the corner of y is the second leftmost, and

• the corner of z is the bottom-most and rightmost.

Note that in this proposition there is no constraint on x, y, z, so by renaming the outer vertices, other FLISs can be obtained. Another way to obtain more FLISs is by applying a reflection with respect to a line of slope 1. In such FLIS (see Figure 17) among the corners of the shapes and the anchors:

• the corner of x is the bottom-most and rightmost,

• the corner of y is the second bottom-most, and

• the corner of z is the upmost and leftmost.

Proof. We proceed by induction on the number of vertices in T . Let T be a triangulation with outer vertices x, y, z.

If T is 4-connected, then it is also a 2-sided near-triangulation. By Proposition 10 and by renaming the outer-vertices x to b 1 , y to b 2 and z to a 1 , T has a FLIS with the required properties.

If T is not 4-connected, then it has a separating triangle formed by vertices a, b and c. We note T in and T out the triangulations obtained from T by removing the vertices outside and inside abc respectively.

By the induction hypothesis, T out has a FLIS verifying Proposition 11 (considering the outer vertices to be x, y, z in the same order). Without loss of generality we can suppose that the shapes of a, b and c appear in the following order: the upmost and leftmost is b, the second leftmost is c and the bottom-most is a. There are two cases according to the type of the anchor of the inner face abc.

If the anchor of abc in the FLIS of T out is vertical (see Figure 18a), then applying the induction hypothesis on T in with b, c, a as outer vertices considered in that order, T in has a FLIS as depicted on the Figure 18b. Figure 18c depicts how to include the FLIS of T in \ {a, b, c} in the close neighborhood of the anchor of abc. As abc is not a face of T , the close neighborhood of its anchor is indeed available for this operation. Now suppose that the anchor of abc in the FLIS of T out is horizontal (see Figure 19a). By application of the induction hypothesis on T in with a, c, b as outer vertices considered in that order, then T in has a FLIS as depicted on the Figure 19b. By a reflection of slope 1, T in has a FLIS such that b is the up-most and left-most, c is the second left-most and a is bottom-most (see Figure 19c). Similarly to the previous case, we include this last FLIS of T in \ {a, b, c} in the one from T out (see Figure 19d). As T in and T out cover T , and intersect only on the triangle abc, and as every inner face of T is an inner face in T in or in T out , these constructions clearly verify Proposition 11. This concludes the proof of the proposition. 2

A From triangle-free planar graphs to 4-connected triangulations

We here prove Lemma 8.

Proof. The main idea of the construction of T is to insert vertices and edges in every face of G (even for the exterior face).

For the sake of clarity, vertices of G are said black and vertices of T \ G are said red. The new graph T contains G as an induced subgraph, along with other vertices and edges. More precisely, for every face of G, let P = {v 0 , e 0 , v 1 , e 1 , . . .} be the list of vertices and edges along the face boundary (see Figure 20), where e i is the edge between vertices v i and v i+1 ; there can be repetitions of vertices or edges. For each face of G, given the list P , the graph T contains a vertex v i for each vertex v i , a vertex e i for each edge e i , and an additionnal vertex t. Each vertex v i is connected to e i and e i+1 (with subscripts addition done modulo the size of the face), each vertex v i is connected to v i , e i-1 and e i , and the vertex t is connected to all vertices v i and e i (see Figures 20 and21 for examples).

The new graph T is a triangulation, and we now show that it is 4-connected, i.e., has no separating triangle. Suppose that there is a separating triangle in the new graph. There are four cases depending on the colors of the edges of this triangle:

• The separating triangle contains three black edges. It is impossible since G is triangle-free.

• The separating triangle contains exactly one red edge. One of its endpoints must be a red vertex. But a red vertex is adjacent to only red edges, a contradiction.

• The separating triangle contains exactly two red edges. Then their common endpoint is a red vertex, and the triangle is made of two vertices v i and v i+1 , together with the vertex e i . All these triangles are faces, a contradiction.

• The separating triangle contains three red edges. Since for each face, the red vertices (vertices v i , e i and t) induce a wheel graph centered on t, with at least 8 peripheral vertices (vertices v i and e i ), this separating triangle has at least one black vertex. As two adjacent black vertices are linked by a black edge, this separating triangle has exactly one black vertex. As the two red vertices are two adjacent v i or e j vertices, we have that those are v i and e j , for some i and for j = i or for j = i + 1. Such a triangle is not separating, a contradiction.

This concludes the proof of the lemma.

2 v i v i+1 e i e i+1 v i+2 e i+2 v i+3 v i e i v i+1

Figure 1 :Lemma 4

 14 Figure 1: Example of a 2-sided near-triangulation

  b

Figure 2 :

 2 Figure 2: Illustrations of (a) the a p -removal operation and (b) the cutting operation.

  The thick shape representing vertex x is bottom but not left. y (c) The thick shape representing vertex y is left but not bottom.

Figure 3 :

 3 Figure 3: Left and bottom thick shapes.

Figure 4 :Figure 5 :

 45 Figure 4: Allowed intersections in a CTLCS. From left to right: the intersection is the top, right, bottom, left side of a thick , and the intersection is a point at the bottom right corner of a thick and at the top left corner of a thick .

Figure 6 :

 6 Figure 6: A 2-sided near-triangulation and (one of) its CTLCS.

Figure 7 :

 7 Figure 7: The (a p -removal) operation for a CTLCS. Here, the grey region contains the corners of the inner vertices.

Figure 8 :

 8 Figure 8: The (cutting) operation for a CTLCS.

Figure 9 :

 9 Figure9: If a thick x has its bottom side included in the horizontal interior of a thick y, then x has no intersection with a thick z on its right side and on its bottom right corner.

Figure 10 :

 10 Figure 10: Replacing thick , |, andby thin ones.

Figure 13 :

 13 Figure 13: Example of a triangulation and a corresponding FLIS

  b

Figure 15 :

 15 Figure 15: The (a p -removal) operation.

Figure 16 :

 16 Figure 16: The (cutting) operation.

Figure 17 :

 17 Figure 17: Illustration of Proposition 11, and the FLIS obtained after reflection with respect to a line of slope 1.

  The vertical anchor of abc in the FLIS of Tout The inclusion of the FLIS of Tin in the FLIS of Tout

Figure 18 :

 18 Figure 18: FLIS inclusion in the case of a vertical anchor

  The inclusion of the FLIS of Tin in the FLIS of Tout

Figure 19 :Figure 20 :

 1920 Figure 19: FLIS inclusion in the case of a horizontal anchor

Figure 21 :

 21 Figure 21: Zoom on the new

In fact, it has been proven in the Masters thesis (in German) of Björn Kapelle in

[START_REF] Kapelle | Kontact-und Schnittdarstellungen planarer Graphen[END_REF] Sec. 3.3], but never published.

* This research is partially supported by the ANR GATO, under contract ANR-16-CE40-0009.


Stephan Reiff-Marganiec

Noor J Rajper

Modelling Virtual Organisations: Structure and Reconfigurations

Keywords: Virtual Organisations, Structural Model, Reconfigurations

Organisations have to adapt rapidly to survive in today's diverse and rapidly changing environments. The idea of virtual organisations emerged as an answer. There is a strong need to understand virtual organisations (VOs) in a formal way: changes can have side effects and hence one might wish to understand precisely what consequences a change might have. The Virtual Organisation Modelling Language (VOML) consists of sub-languages to model different aspects of VOs such as their structure or operational models: VO-S deals with structural aspects while VO-R addresses reconfigurations. The concepts are exemplified through a travel booking VO that needs to cope with extra demands imposed by a large event such as the Olympic games.

Introduction

Changing business environments and a diversity of emerging requirements make entities' (organizations, individuals, etc.) survival and success dependant on their ability to adapt dynamically to changing operating conditions [START_REF] Camarinha-Matos | Towards a framework for creation of dynamic virtual organisations[END_REF][START_REF] Cummings | Beyond being there: A blueprint for advancing the design, development, and evaluation of virtual organizations[END_REF][START_REF] Foster | The anatomy of the grid: Enabling scalable virtual organizations[END_REF]. VOs provide a solution when it is impossible for any single organization (particularly small or medium size enterprises; SMEs) to keep up with the speed of change in the environment and the diversity of demands prevailing in the market. Adaptability and diversity are some of the main defining characteristics of VOs -adaptability allows to cope with changing demands while diversity is multidimensional (e.g. the range of involved stakeholders, the offerings made, cultural and geographic positioning, etc.).

A VO is a loosely bound consortium of organisations that together address a specific demand that none of them can (at the given time) address alone -once the demand has been satisfied the VO might disband. A VO is created in the context of a VO Breeding Environment (VBE), which is a more stable grouping of business partners, but without a specific current goal [START_REF] Camarinha-Matos | Towards a framework for creation of dynamic virtual organisations[END_REF]. Some VOs persist over longer time, but adapt to realign themselves to address changes in demand.

A VO has a structure that defines the tasks it is conducting to achieve its goals as well as defining which partners are involved. There is a need to rigorously define this structure, as it is the foundation to describing and analysing the reconfigurations of the VO [START_REF] Bryans | Formal modelling of dynamic coalitions, with an application in chemical engineering[END_REF], which are the way in which a VO adapts to changing demands.

In this paper we present VOML (the VO Modelling Language) focusing on two aspects: the modelling of the structure of a VBE/VO and the description of reconfigurations. For the former we present a new language that captures the key aspects of the VO at a level of abstraction meaningful to business users by making key concepts first class citizens of the language but still concrete enough to be mapped into more rigorous languages for operational models and rigorous reasoning and analysis. For the latter we introduce VO-R, the VO reconfiguration language. VOs can adapt in two fundamental ways: The ultimate goal of the VO might change, i.e. the VO should address a demand unrelated to its original purpose, in which case a new VO should be formed, possibly including current members. However, often the VO needs to adapt in more subtle ways to deal with fluctuations in capacity demands or alternative ways of achieving a task -it is this aspect which is addressed by VO-R.

The paper is organized as follows: Section 2 presents an overview of the VOML approach for modelling VOs, sections 3 and 4 introduce the structural and reconfiguration languages. The paper is rounded off with a discussion, related work and some concluding remarks and future directions in the final sections.

Overview of Approach

The Virtual Organization Modelling Language (VOML) is dedicated to VO development. VOML operates in the context of a VO Breeding Environment; VOs are formed dynamically to provide high-level functionalities by sharing a number of resources in a distributed way. The VOML approach [START_REF] Bocchi | Structure and behaviour of virtual organisation breeding environments[END_REF] supports the definition of a structural and behavioural model of a fixed VBE based on three different levels of representation: (1) the definition of the persistent functionalities of the VBE; (2) the definition of the transient functionalities of the VOs that are offered by the VBE at a specific moment in time (a business configuration of the VBE) and (3) the ensemble of components (instances) and connectors that, at that time, deliver the services offered by the VOs present in the business configuration (a state configuration). Very briefly, structural models present the general structure of the VO (or VBE); these are mapped semi-automatically (semi as some refinement is required) into operational models. The operational models are quite close to respective execution frameworks (such as agent based systems or service oriented systems) and can be mapped to these. The execution framework is monitored and any changes are reported back to the model levels where policies are activated to refine the VOs and ensure that they remain competitive. Reconfiguration rules are checked for consistency and furthermore any VO-model should be correct by construction (that is it should be a true refinement of the respective structural model) -however this is further ensured by consistency checks. Figure 1 depicts this overview in a graphical manner.

Structural Models: VO-S

The VO Structural Modelling Language (VO-S) defines the basic structure of the VO, its constituent elements, abstract process, and other details which define the essential structure of the VO and provide the basis for its operational models. The VO structural model consists of five basic elements: (1) Members, (2) Process, (3) Tasks, (4) VBEResource and ( 5) Data-Flow. Of these, Members, Tasks and VBEResources are elements that can occur in VBE specifications, too.

Members can be of one of three types: Partners are permanent members of the VBE, Associates are transient members of the VBE who have joined temporarily based on demands of some VO which requires some capability for which there is currently no member available in the VBE and finally extEntity which are transient members of a VO and are discovered for each VO instance and leave the VO when the instance finishes its life. For the travel booking VO, the hotel provider is a partner, while FlightBooking is an extEntity.

Process describes the workflow which leads to meeting the requirements of the customer of a VO at the highest level of abstraction. It lists only those tasks that contribute directly towards achieving the goals of the VO.

Task specifications define the competencies required by the VO from its members. They help in deciding the kind of restructuring that a task and hence a VO can undergo, having effects ranging from VO topology to member relationships. Tasks are complex and we will here only show some key features. Attributes exist in the TaskScope (where they provide a domain of discourse for configurations) and in the ConfScope (where they describe the current configuration). E.g. the performedBy attribute in the TaskScope might specify that the task can be performed by Associates and Members, the ConfScope would make precise who is performing the task in the current configuration. Also, each tasks specifies the competencies required for performing it: which capability does a performing partner need and what capacity is needed (e.g. a partner needs to provide accommodation, and 50 rooms are needed).

Reasons for forming virtual organizations are (a) an entity (organization) lacks some capabilities to take on a job; and (b) an entity has all the capabilities required but lacks the required capacity (often the case with Small and Medium organizations (SMEs) competing for large jobs). VO-S addresses this by offering three types of tasks: AtomicTask (tasks to be performed by only one member), ReplicableTask (tasks that can be shared to gain extra capacity) and ComposableTask (tasks that can be shared to address capability issues). Members can compete or cooperate ReplicableTasks. VBEResource are resources that are owned by the VBE and made available to all VOs that stem out of the respective VBE. The VBE will have rules on their usage.

Data-Flow specifies the relationship between data items to assist with realizing concrete orchestrations, transitions and wires in operational model. It expresses which data items are expected from the customer and partners and their flow between tasks. The TravelBK VO (Fig. 2) specifies a VO that is concerned with offering trip itineraries that include transport via air, accommodation and local excursions. There are two members in the VO (the AccomProvider1 is a VBE member, the TourAg is an associate). Air transport is provided by suitable external entities. All three tasks are atomic meaning each is performed by a single member.

Reconfigurations: VO-R

Policy languages have been successfully used for dynamically adapting systems. In this work we are particularly interested in policies which allow to reconfigure (adapt) a VO to cope with the changes that it is subjected to. We require and wish to model replication of tasks so that a number of members can combine capacity (either jointly or in competition) and decomposing complex tasks into smaller ones, so that several members can combine their skills. Additionally we like to be able to change the membership of the VO by adding or removing members.

While policies provide a feasible approach towards reconfiguration, a special policy language is required which provides explicit constructs suitable for the domain of VO reconfigurations. Typically a policy language can be completely domain specific or a more generic ECA (event-condition-action) language can be adapted to new domains by providing appropriate actions, triggers and conditions. We adapt the APPEL [START_REF] Blair | APPEL: The ACCENT Policy Environment/Language[END_REF] language -APPEL had been developed with a clear separation of domain and core language. APPEL has a style closer to natural language as it was aimed at non-technical end users, rather than developers or system administrators, something clearly of benefit the users of VO modelling languages. APPEL was originally aimed at call control, but has since been specialised for e.g. sensor networks or elderly care.

Policy rules are the basic building block of APPEL. Each rule consists of an optional trigger, optional condition and an action. A rule is applicable when its trigger has occurred (if one is defined) and its conditions (on the state and possibly trigger parameters) are satisfied (with the empty condition being trivially satisfied). Actions have an effect on the system to which the policies are applied. Policy rules can be grouped into larger policies. A typical APPEL policy looks as follows: policy policy-name appliesTo task-id/member-id/VO-id when [trigger(s)] if [condition(s)] do action(s)

For VO-R we have to add a number of triggers, conditions and actions. We also need to consider the meaning of the localisation: appliesTo allows to 'locate' a policy. In distributed settings this would allow to specify the location of a policy, for VOs this allows to express which task(s), member(s) or VO(s) a policy applies to. The specialization of APPEL to Virtual organizations forms the Virtual Organisations Reconfiguration language VO-R. There are several triggers (Table 1) and actions (Table 2) specific to the domain, some of which are shown below -we do at this stage not claim that this list is complete and ongoing investigation studies this aspect.

Trigger Description NoMemberWithRequiredC apacityFound

Arises when no existing VBE member is found to provide suitable capacity (either because they are not willing to provide more resources to the VO or because they cannot).

CapacityDeficit

The VO has all required capabilities, but is lacking capacity to satisfy current demand by a task. The task could be conducted, but with limitations.

CapabilityDeficit

The VO lacks a required capability. A capability deficit means that certain tasks cannot be conducted.

Table 2. Sample actions for VO Reconfigurations.

Action Description MakeTaskReplicable

Changes the type of a task so that it can be shared between (task-id, allowedMembers, relationship)

members. The resulting type will be a ReplicableTask that can be shared between at most allowedMembers members who compete or cooperate (depending on relationship). AssignTask(member-id, task-id) Assigns a member to a task. If the task is atomic or was unassigned this member will be the one conducting the task; if the task is replicable or composable this member will perform some part of the task. AddNewMember(memberid)

Adds a new members to the VO.

Let us now consider two examples based on the TravelBK VO, which was presented earlier in detail. Specifically the VBE management has decided that TravelBK has a big role to play during a big upcoming event, such as the Olympic games, but needs to adapt to cope with the demands. Scenario 1: More hotel beds are needed than the current provider can provide. The Olympic games will bring an influx of people who require accommodation. The current member responsible for the HotelProvision task has limited capacity and no other member can individually meet the expected demand, but each provider could contribute to the demand. The following reconfiguration policy makes the HotelProvision task shareable between up to 3 members; the allocation will be given to the cheapest one.

policy MoreBeds appliesTo HotelProvision when NoMemberWithRequiredCapacityFound do MakeTaskReplicable(HotelProvision,3,[competition,cheapest]) Scenario 2: One of the hotel partners has had a fire and had to withdraw their commitment. Sadly one of the hotels had a fire and cannot provide the promised accommodation. This is a kind of contract violation in the eyes of the VBE -clearly in business cases this happens and the VO is prepared to react to it as it has the following rule (this rule assumes that memberX is only involved in TaskY). Before a member can be removed the tasks assigned to that member need to be removed. The application of the rule might lead to a follow-on problem of a capacity or capability deficit (a capacity deficit was shown in Scenario 1 and capability deficits are similar).

policy MemberQuits appliesTo memberX do UnAssignTask(memberX, TaskY)

andthen RemoveMember(memberX)

Related Work

VO's have been modelled using a number of generic modelling frameworks, such as UML, ERP or PetriNets. For example, in [START_REF] Bryans | Formal modelling of dynamic coalitions, with an application in chemical engineering[END_REF] a VO is modelled using the Vienna Development Method in five dimensions: membership, information representation, provenance, time and trust. The formal model allows for analysis and verification. Our modelling language raises the level of abstraction to a point where it is possible to directly support notions and concepts that are paramount in the domain of VO such as members and resources. The use of UML stereotypes to achieve the same could be investigated, and indeed would be interesting to enhance our work with a graphical syntax -VO-R could then be expressed through graph transformation rules. Like our proposal, [START_REF] Norman | Agent-based formation of virtual organisations[END_REF] allows tasks to be shared, however they only allow sharing of a task based on capacity whereas we allow sharing based on capabilities as well. Additionally we cover the effects of such sharing on the members and on the process model. Besides, [START_REF] Norman | Agent-based formation of virtual organisations[END_REF] is based on Agent Technology whereas our work is at a higher level of abstraction than a platform or technology specific solution.

The field of dynamic adaptability in general [START_REF] Marzo Serugendo | A metadatabased architectural model for dynamically resilient systems[END_REF] is relevant. ASSL [START_REF] Vassev | ASSL: A software engineering approach to autonomic computing[END_REF] in particular focuses on flexibility by providing a modelling language for autonomous systems. ASSL abstracts away from business level requirements of the system, however these are at the heart of VO modelling. More in the domain of VOs, the Arcon framework provides a reference model at an abstract level, while we attempt to make precise more of the structural and operational aspects of the VO and its reconfigurations.

In many areas of computing policy languages have become widely accepted as a way of reconfiguring systems to cope with changes in the environment [START_REF] Vassev | ASSL: A software engineering approach to autonomic computing[END_REF]. Often policy languages describe security or low level system management aspects [START_REF] Lupu | Conflicts in policy-based distributed systems management[END_REF]; at higher levels of abstraction the APPEL [START_REF] Blair | APPEL: The ACCENT Policy Environment/Language[END_REF] policy language has been adapted for workflows, where it allows to insert and delete tasks [START_REF] Gorton | StPowla: SOA, policies and workflows[END_REF]. For VO's no such language currently exists but the presented reconfiguration language is a variant of APPEL.

Conclusions and Future Work

VOs capture organizations that are formed as relatively short lived consortia from other organizations. The ability to dynamically adapt to diversity in demands extends the lifespan and profit of VOs. In this paper we put forward a novel language to allow for modelling the structure and reconfigurations of VOs. VO-S allows to describe the structure of a VBE or a VO in terms of the key elements such as tasks or partners, while VO-R allows to specify rules that describe how a VO should adapt if asked to do by the VBE or if events occur from the VO's environment that need to be addressed. The VBE might stipulate changes when it sees them as beneficial to the business; the environment might raise triggers e.g. a capability or capacity shortage.

As reconfigurations are a core aspect of VOs, other approaches provide attempts at dealing with similar issues. Our approach is quite close to how real organisations behave in that we are providing a flexibility by allowing reconfiguration of tasks into a different task type by replication or decomposition. It is crucial to understand the changes as they can range from the VO architecture (its structure) to relationship between members and further more to changes in control and data flow. Existing work often focuses on replication of resources rather than on the members, however it is usual that new capacity or capability comes from new partners.

Our modelling and reconfiguration is close to the business requirements as shown in the reconfiguration scenarios and the respective policies -the policy language is intuitive and staff with business knowledge can write the required policies (actually the previous uses of APPEL in telecommunications were targeted at lay end-users).

Finally, we have clearly separated changes that change the tasks and hence can have an affect on the goal of the VO from those that make it more competitive in its environment. Changes to goals are achieved by new VOs being created from the VBE, while the presented reconfigurations allow for adaptations that maintain the overall goal. This distinction is critical, as it allows specification of properties that the VO needs to achieve or preserve and ensure that these are indeed adhered to.

In future work we will analyse whether VO-R can be lifted to the VBE level, to see if 'changes' to the structure that occur during the creation of new VOs can described in the same way (e.g. rules on selection of VO partners). Initial analysis shows that this is feasible, but will require further domain specific actions and triggers in VO-R. We will also consider performance modelling based on variants of VO-S models to understand the affect of VO-R rules on adaptability of the VO and more formal detection of conflicting rules, based on the formal semantics of APPEL [START_REF] Montangero | Logic-based conflict detection for distributed policies[END_REF]. These types of analysis will lead to an understanding that is useful for any VO.

Fig. 1 :

 1 Fig. 1: Overview of Framework

Fig. 2 :

 2 Fig. 2: VO-S Structural Model of the TravelBK VO

Table 1 .

 1 Sample triggers for VO Reconfigurations.