Gilles Daviet

Florence Bertails-Descoubes

Romain Casati

Fast Cloth Simulation with Implicit Contact and Exact Coulomb Friction

Abstract

Cloth dynamics plays an important role in the visual appearance of moving characters. Properly accounting for frictional contact is of utmost importance to avoid cloth-body penetration and to capture folding behavior due to dry friction. We present here the first method able to account for contact with exact Coulomb friction between a cloth and the underlying character. Our key contribution is to formulate and solve the frictional contact problem merely on velocity variables, by leveraging some tools of convex analysis. Our method is both fast and robust, allowing us to simulate full-size garments with more realistic body-cloth interactions compared to former methods, while maintaining similar computational timings.

Related Work

Simulating cloth dynamics subject to contact and friction is commonly achieved through an iterative velocity filtering process at each time step [START_REF] Bridson | Robust treatment of collisions, contact and friction for cloth animation[END_REF]. Within the main loop, the cloth dynamics Mv + f = 0 are first resolved as if no contact were applied, then each cloth vertex has its velocity sequentially modified so as to satisfy non-penetration and Coulomb frictional constraints locally. Although this method gives a contact-free configuration at the end of each time step, it fails to yield a consistent mechanical state w.r.t. both internal energy and Coulomb constraints. Typically, excessive bending energy may be localized between non-contacting and contacting vertices, and some vertices may be artificially constrained to stick whereas they should be sliding.

In contrast, treating frictional contact implicitly with constraints as

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ Mv + f = J ⊺ r Jv = u (u, r) ∈ C(µ) where C(µ) is the Coulomb law (1)
alleviates such issues, since internal dynamics and frictional contacts are solved simultaneously. The classical way to solve such an implicit formulation is to first eliminate velocities v (primal variables) through the computation of the Delassus operator W = J ⊺ M -1 J, then solve the system in the contact forces r (dual variables), and finally compute v from r. In the case of curvature-based hair models, [START_REF] Daviet | A hybrid iterative solver for robustly capturing Coulomb friction in hair dynamics[END_REF] introduced an efficient solver for the dual problem, able to take exact Coulomb friction into account. For cloth however, where primal variables are 3d velocities, such a method is computationally inefficient. Indeed, the matrix M is costly to invert for large systems and its inverse is dense. * e-mail:{gilles.daviet,romain.casati,florence.descoubes}@inria.fr

A primal formulation with Coulomb friction

We assume body-cloth contacts occur at cloth vertices only, i.e., each contact involves only one vertex. A key observation is that each nonzero block of J related to a vertex i is simply a rotation matrix E i , corresponding to the local contact basis for the vertex i. Our idea is then to build the square block-diagonal matrix G with G i,i equal to E i if i is in contact, and to the 3x3 identity matrix otherwise. G can thus be inverted trivially as G -1 = G ⊺ . Augmenting u and r so that their size matches that of v, we can write (1) as

⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ GMG ⊺ u + G f = r v = G ⊺ u (u i , r i ) ∈ C(µ i ) if i in contact and r i = 0 otherwise.
(2) Denoting Ŵ = GMG ⊺ and b = G f , we obtain a system that is very close to the dual formulation of [START_REF] Daviet | A hybrid iterative solver for robustly capturing Coulomb friction in hair dynamics[END_REF], except that u and r have reversed roles. To retrieve symmetry, we apply De Saxcé's change of variable ũi = u i + s i (u) so that ũi is orthogonal to r i . For a fixed value of s, we identify (2) as the KKT conditions of the convex quadratic optimization problem [START_REF] Acary | A formulation of the linear discrete Coulomb friction problem via convex optimization[END_REF]]

min ũ 1 2 ( ũ) ⊺ Ŵ ũ + (b -Ŵ s) ⊺ ũ ũi ∈ K 1 µ i if i in contact (with Kµ the Coulomb cone),
which can be solved using [START_REF] Daviet | A hybrid iterative solver for robustly capturing Coulomb friction in hair dynamics[END_REF]]'s solver, since this time ũ plays the exact same role as r (replacing K µ i with K 1 µ i

).

Following [START_REF] Acary | A formulation of the linear discrete Coulomb friction problem via convex optimization[END_REF], we compute the solution of the full problem (1) by iteratively updating s using a fixed point algorithm.

Unlike the Delassus operator W , our new operator Ŵ is easy to assemble and sparse. Solving our primal problem (2) thus turns out to be orders of magnitude faster compared to the dual problem.

Figure 1 :

 1 Figure 1: Our body-cloth contact solver captures exact Coulomb friction both efficiently and robustly. On this dress example featuring 6000 cloth vertices and 1000 contact points on average, our solver converges at each time step (dt = 1ms) in a few hundred milliseconds.

Acknowledgements

We thank Laurence Boissieux for designing the dress mesh and the body animation. This work was supported by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025-01).


I Sassi

A Gouin

J M Thiriet

A Bayesian network for diagnosis of networked mobile robots

The network of communicating mobile vehicles is a subclass of wireless networked control systems (WNCS) characterized by wireless communications and mobile nodes. The integration of the wireless network into control loop, given the stochastic aspects of wireless communication and mobility of its communicating entities, can lead to problems that affect system performances. In other words, the system quality of control QoC depends on the wireless network quality of service QoS state. A diagnosis method is essential to monitor, diagnose and maintain the system in an operational state. The present paper proposes a modular multi-layer Bayesian network model for diagnosis taking into account the network failures. Results regarding the system performance are presented to illustrate the relevance of the developed Bayesian Network BN to decisions making in order to lead the system to its final goal.

INTRODUCTION

Networked systems have emerged in many fields and in a large number of distributed applications. They are distributed systems where actuators, sensors and controllers are connected through a communication network which is crucial to ensure proper operation. Reducing the installation costs and the simplicity of maintenance and diagnosis of networked control systems prove the advantage of using these systems [START_REF] Simon | Co-design approaches to dependable networked control systems[END_REF]. Networked mobile robots, as wireless networked control systems WNCS, have found applications in transport field, domestic help, military, space, etc. They perform human tasks and they also take over human missions in hostile places, for instance robots that entered to the melted Fukushima reactor [START_REF] Nagatani | Emergency response to the nuclear accident at the fukushima daiichi nuclear power plants using mobile rescue robots[END_REF]. The networked robots receive orders from a controller in order to accomplish their tasks and then they send back information about their state and other observations. For example, for the case of robot Philae, sent to the Tchouri comet to discover the evolution of solar system, researchers need to have a sufficient duration of communications, if it is possible, to receive a feedback from the robot and send him the orders to be executed. However, it is difficult to ensure that the data is transmitted correctly and completely because of the stochastic behavior of wireless network and the mobility of the communicating devices. The integration of wireless network into the control loop introduce problems that affect the system performance and its stability. In fact, the network state in term of quality of service QoS af-fects the system quality of control QoC. This influence is due to delay [START_REF] Simon | Co-design approaches to dependable networked control systems[END_REF], [START_REF] Ghostine | Variable delays and message losses: influence on the reliability of a control loop[END_REF], [START_REF] Tipsuwan | Control methodologies in networked control systems[END_REF], packets loss [START_REF] Mechraoui | Effect of packet loss on the quality of control of a networked mobile robot[END_REF], [START_REF] Lian | Network design consideration for distributed control systems[END_REF], [START_REF] Berbra | Codesign of a safe network control quadrotor[END_REF], jitter [START_REF] Moyne | The emergence of industrial control networks for manufacturing control, diagnostics, and safety data[END_REF], throughput [START_REF] Zhang | Network-induced constraints in networked control systemsa survey. Industrial Informatics[END_REF], [START_REF] Hespanha | A survey of recent results in networked control systems[END_REF]) of the network and the connectivity degradation [START_REF] Mechraoui | A co-design distributed bayesian approach for decision and scheduling of wncs[END_REF]). So, it has been crucial to understand the impact of network failures on the system state and to consider them simultaneously with the control problems which characterize the co-design approach [START_REF] Mechraoui | A co-design distributed bayesian approach for decision and scheduling of wncs[END_REF]. A diagnosis method is essential to identify and localize faults and to make the right decision to improve the system performance. Because of the stochastic behavior of wireless networks, probability theory is used. So, a Bayesian network BN is proposed to model the dependencies between failures and quantify their likelihood. Bayesian methods provide a formalism for reasoning under conditions of uncertainty [START_REF] Pearl | Probabilistic reasoning in intelligent systems: networks of plausible inference[END_REF]. Many Bayesian models have been developed to perform diagnosis [START_REF] Bottone | Failure prediction and diagnosis for satellite monitoring systems using bayesian networks[END_REF], [START_REF] Cheng | Bayesian network based fault diagnosis and maintenance for high-speed train control systems[END_REF], [START_REF] Schumann | Software and system health management for autonomous robotics missions[END_REF]. In this paper, the Bayesian model is inspired from the multi-layer model of [START_REF] Przytula | Reasoning framework for diagnosis and prognosis[END_REF]. The proposed BN is used to identify the cause of QoC degradation of a networked mobile robot , whether it comes from the network as a system component susceptible to malfunctions, or the controller or the internal state of the robot. It is used also to make the decisions to avoid QoS and QoC degradation. [START_REF] Simon | Co-design approaches to dependable networked control systems[END_REF] and [START_REF] Mechraoui | A co-design distributed bayesian approach for decision and scheduling of wncs[END_REF] propose, in the context of the co-design approach, the reconfigu-ration of the network to improve the QoC state or the adaptation of control in the case of QoS degradation. In the present work, a simulated networked mobile robot moving to a target by avoiding obstacles and controlled by a fixed station is considered. It is used to show the effectiveness of the proposed BN to diagnose and to make decisions to improve system performance. The paper is organized as follows. Section 2 is devoted to review basic theories of BNs. Section 3 describes the developed BN for the diagnosis of networked mobile robot. Diagnosis scenario is then presented to illustrate the relevance of BN. Finally, conclusions and perspectives are given in section 5.

BACKGROUND

Bayesian network BN

BNs, also called beliefs networks, are probabilistic graphical model representing dependencies between events with their likelihood. They are the results of research work of Judea Pearl in the 80s [START_REF] Pearl | Probabilistic reasoning in intelligent systems: networks of plausible inference[END_REF]. BNs have been used in many applications such as decisions making problem in autonomous vehicles, risk modeling and especially diagnosis which is the objective of this work. One of the advantage of this model is to gather and merge different types of data [START_REF] Naïm | Les réseaux bayésiens[END_REF]. BNs are directed acyclic graphs in which the nodes represent variables (discrete or continuous) and the arcs represent direct causal influences between the connected variables. These influences, which represent the dependencies between the variables, are expressed by forward conditional probabilities. Finally, a BN is defined as follows:

• a directed acyclic graph G=(V,E) where V is the set of nodes and E is the set of directed edges;

• a probability space (Ω,Z,P);

• a set of random variables associated to the graph nodes such as

P (V 1 , V 2 , ..., V n ) = n i=1 P (V i |C(V i )) (1)
where C(V i ) is the set of V i parents. The exact inference in belief network is NP-hard.

Distributed Bayesian Network

Distributed BNs have been introduced in many works [START_REF] Sayed | Distributed bayesian diagnosis for modular assembly systemsa case study[END_REF], [START_REF] Xiang | Justifying multiply sectioned bayesian networks[END_REF], [START_REF] Bloemeke | Agent-encapsulated bayesian networks and the rumor problem[END_REF], [START_REF] Langevin | Knowledge representation, communica-tion, and update in probability-based multiagent systems[END_REF], [START_REF] Hwang | Modular bayesian networks for inferring landmarks on mobile daily life[END_REF], [START_REF] Hwang | Landmark detection from mobile life log using a modular bayesian network model[END_REF] to shorten inference time, to reduce load on the calculations server and to infer information from different environments. In fact, the information coming from remote and smart devices should be preprocessed and inferred locally [START_REF] Frank | Segmenting bayesian networks for intelligent information dissemination in collaborative, context-aware environments with bayeslets[END_REF]. The local inference results coming from different modules are then gathered for final inference. Three types of distributed BN have been studied. Multi Sectioned Bayesian Networks MSBN [START_REF] Xiang | Justifying multiply sectioned bayesian networks[END_REF] is a knowledge representation formalism that divides a large BN into sub-networks to enable multi-agent probabilistic reasoning. It is used to model a domain using a set of Bayesian subnet that are each assigned to a subset of the domain. The d-separation is used to section the global BN and all subnets are organized in a hyper tree structure. Besides, there is only one probability distribution for the set of all random variables of all local BNs. The constraints of MSBN limit the autonomy of the agents that must be tightly coupled.

Regarding Agent Encapsulated Bayesian Networks [START_REF] Bloemeke | Agent-encapsulated bayesian networks and the rumor problem[END_REF], [START_REF] Langevin | Knowledge representation, communica-tion, and update in probability-based multiagent systems[END_REF], each agent implements its internal knowledge as a local BN which has its own probability distribution. It uses its local BN for its own reasoning. These type of BNs modeling deals with problems where the information and the actors are distributed. The agents are organized in a publisher-subscriber hierarchy and communicate by passing messages through shared variables.

The subscriber updates its beliefs based on its own observations and on the publisher beliefs because the publishing agent are more knowledgeable about the variables they produce, i.e. the subscribing agent replaces its current view of the shared variables with the publishers one. Another distributed Bayesian approach is developed by Hwang andCho (2006, 2009). The BNs, in their approach, are modularized according to their separated sub-domains. The inference consists of two stages considering the co-causality of the modularized BN. Every Bayesian module infers in first given the available hard evidence. The first stage output of Bayesian modules that are connected as parents is introduced as soft evidence in the second stage by virtual linking.

In this work, Modular BN based on two-stage inference of Hwang and Cho is proposed to achieve the objective of diagnosis. A detailed description is introduced in section 3.

Bayesian network for diagnosis

System diagnosis is the identification of failures in order to make decisions to return the system to its normal state. It consists in determining whether a com-ponent is failing or not i.e. localizing the origin of the failures from observations. A failure is defined as a deviation, outside an acceptable range, of an observed variable. The diagnosis task is divided into 3 subtasks (Patton and Chen 1999):

• failure detection which consists in observing system malfunction;

• failure localization to determine the failing component;

• failure identification which lies in the determination of the failure form and its amplitude.

CONSTRUCTING THE BN MODEL

The global system consists of a robot equipped with actuators and sensors and communicating to a remote station where the controller is implemented. The mobile robot has limitations such as insufficient memory capacity, lower CPU power and limited battery lifetime. The defaults that have an impact on the system QoC have been studied. In this work, the QoC measures the capacity of the controller to bring the robot to its steady position via wireless network. The QoC is affected by the state of the network, as a system component, and more specifically, its QoS. Besides, the robot state has an impact on the QoC because in the case of actuators degradation, the robot won't be able to execute the station orders. The global system is divided into 3 sub-systems which are the network sub-system, the operative sub-system (robot actuators and sensors) and the control sub-system. For each sub-system, a BN is modeled to represent the dependencies between failures of each sub-domain. Consequently, a modular BN for diagnosis is constructed in order to identify the QoC degradation cause whether it is network failure, or a robot failure or a controller 2007) model to provide more accurate and broad coverage context specially the components level, the intermediate one, which represents relationships between component failures. The first layer represents the usage of the system and the conditions in which it is running. There is also another intermediate layer which is the subsystem layer representing the state of each subsystem of the global one. Finally, observations layer is used to monitor the state of components or components failures. The operative Bayesian module is implemented on the robot while the other two modules are on the station side.

Operative Module

The robot is equipped with sensors and motors (actuators) which represent the operative subsystem of the WNCS. For this subsystem, a subsystem node is defined as robot state to indicate the state of this part of the system as shown in figure 2. The components (components node) of this subsystem are the left and right motor and the obstacles sensors of the robot. For each component node, an observation node measures and monitors its health state. The sensors are considered failing if they are not able to detect the presence of obstacles or the transmitted values are constant or incorrect. For the actuators, a motor failure is monitored by observing the reference error of the angular velocity. This velocity error must decrease over time and does not exceed a threshold, otherwise, the motor (left or right) is failing. A usage node battery level is used to describe the robot battery usage, it represents the conditions in which the robot components are operating.

Network module

The network is considered as a WNCS component which can be failing like the other system components. When the network cannot ensure the required QoS, it is considered failing. The network state is represented by the node QoS which is a subsystem node as shown in figure 3. The network parameters that have an impact on the QoS are packets loss rate, delay, jitter and throughput. Failures which are associated to this observable parameters are defined to describe the degradation of the QoS state. There are 3 types of failure mode in the network when some communicating device are mobile: channel failure, transmission failure and connectivity failure. For the communication channel failure which limits the network availability, a component node channel state is defined because when the channel is saturated, there is no guarantee that the message will be transmitted. To monitor the channel state, an observation node throughput measures the rate of transmitted packets in the network. Regarding the connectivity failure, when the mobile robot moves away from the station coverage area, it loses its connectivity to the station so the messages are dropped. To observe the state of connectivity node, the received signal strength indicator RSSI is used to measure the quality of the received signal. The nodes deadline respect and data loss are devoted to transmission failure description. The jitter and delay measurement monitors the reception on time of the transmitted packets and the packet loss observes the rate of dropped packet in the network. A set of nodes in the usage layer define the use conditions of the network. Number of communicating nodes define the number of mobile communicating entities in the network. If this number increases, the collision probability increases so the throughput decreases, the delay and packet loss rate increase. The node network load represents the network limited resources offered to the application. If the network is overloaded, its performances degrades, the delay and packet loss increase and the channel is saturated. The closed loop sampling period has also an impact on the network state because if its value is under a certain threshold, the network will be overloaded and packets will consequently be dropped [START_REF] Simon | Co-design approaches to dependable networked control systems[END_REF]). The connectivity state depends on the environment in which the robot is moving, where there are obstacles (obstacle node)and a risk of signal fading or absorption. It depends also on the distance between the station and the robot to define the coverage area where the connection persists.

Control module

The QoC node, which represents the control subsystem, indicates the performance and the state of the control application, i.e. it indicates whether the robot is controlled via wireless network or not. The QoC is influenced by the robot state (state of operative subsystem), the QoS state (state of the network subsystem) and the state of the controller as shown in figure 4. If the robot actuators don't receive on time the control data or they are not able to execute the control laws, the robot cannot be well controlled therefore the QoC state degrades. Observations node are defined to monitor the QoC state. The stability node controls the system stability along the trajectory using Lyapunov theory. The position error node monitors the distance between the target and the robot (navigation mission) which must decrease over time. The distance robotobstacle node monitors the distance between the robot and an obstacle (if it exists in the robot trajectory) because the robot must reach the target position while avoiding obstacles. The controller node, which is a component node, has an impact on the QoC state. If the controller has limited calculations capacity or its CPU is overloaded, the QoC degrades. Two usage nodes are defined for the controller to precise its type and its CPU load. The embedded controller (implemented on the robot) has degraded performance while the remote controller (station) is efficient.

Diagnosis reasoning

The Bayesian modules are used to perform networked mobile robot diagnosis in order to maintain it in a good state and lead it to its target. In this model, the control subnet shares with the network and operative subnets the QoS node and the robot state node respectively. In the first inference stage, hard evidence are applied in 3 modules. Secondly, the result of the inference in the control subnet is transferred to the other two subnets as soft evidence on the Qos node and robot state node. In the next section, diagnosis scenarios are described to prove the relevance of these method using a simulated networked robot controlled by a remote station. 5 where it moves in the station coverage zone and in good network conditions. The robot reaches its target after 60s when the linear velocity becomes zero.

A network fault occurs, the network delay is greater than the sampling period of the control loop which is equal to 0.4s, the application performance is degraded and the QoC state becomes bad because of the degradation of the QoS. No actions are taken in the case of figure 6 which shows that the robot cannot be sta- In this article, a diagnosis method for wireless networked mobile robot based on modular BN is proposed in order to maintain the controlled system operational and lead it to its target. This approach takes into consideration both QoS and QoC states to solve a co-design problem. The developed method is then tested on a simulated networked mobile robot. Probabilities given by the BN, describing the actual situation, generate an order to maintain the communication between the robot and the station or to make controllers switching decision. This strategy gives first satisfying result in term of application performance because the robot reaches its target after switching to embedded controller. In this work, decisions have been made based on QoS and QoC states. In further work, the intermediate layer of each BN will be used to make more efficient decisions based on each type of network failure, on the controller state or on each robot component state. The developed Bayesian method will be implemented on a real mobile robot. The prognostic aspect will be also integrated in this work to avoid QoC and QoS degradation before its occurrence.

  BNs for diagnosis have been used in many fields. As probabilistic models, they evaluate the state of systems that have random dynamic and represent the dependencies between failures. They model the causal links that relate errors to symptoms based on human experts and engineering knowledge about the system. The inference algorithm is used to infer error causes from observed symptoms.[START_REF] Bottone | Failure prediction and diagnosis for satellite monitoring systems using bayesian networks[END_REF] proposed a Bayesian model for satellite diagnosis. Their system consists of 4 types of component susceptible to failures. The model is composed of 2 main nodes types: a measurable node which corresponds to the state of a measurable parameter and a non measurable node defined as failure node which represents a component failure or a system failure. The failure node had 2 states: fail state for component failure and no fail state for operational component. The diagnosis procedure in this model determine the maximum likelihood of non measurable nodes given the state of measurable nodes and consequently the cause of system dysfunction.[START_REF] Cheng | Bayesian network based fault diagnosis and maintenance for high-speed train control systems[END_REF] developed a dynamic BN for the maintenance of Automatic Train Protection Control Unit ATPCU and for the diagnosis of the cause of train stop. In their model, a monitor node supervise the system and when it detects a failure, it pass the information to maintenance node. Consequently, the maintenance probability increases until a defined value that triggers the maintenance operation to upgrade the ATPCU state. A stop node gives the state of the train. If the train is stopped, the ATPCU is in degraded mode. A system condition node describes the conditions and the environment in which the system is operating. Another BN is used in NASA as Software Health Management for the diagnosis of software and hardware failures.[START_REF] Schumann | Software and system health management for autonomous robotics missions[END_REF] developed a modular, hierarchical and reusable Bayesian model which consists of discrete nodes. The command node C presents, as an observable node and an input to the BN, a ground truth, a command, an action or a specific operating mode. The sensor node S, which is also an observable node and an input to the BN, gives measures about the software and hardware monitoring. A non observable node which is the Health node H is the result of diagnosis of the component state. The state of this node is thus

Figure 1 :

 1 Figure 1: Multi-layer Bayesian network for diagnosis

Figure 2 :

 2 Figure 2: Operative Bayesian module

  Figure 3: Network Bayesian Module

  Figure 5: Robot navigation in good network conditions

Figure 6 :Figure 7 :

 67 Figure 6: Robot navigation in degraded network conditions

  Decision Making Algorithm P 1 = P (QoC = good|observations) P 2 = P (QoC = degraded|observations) P 3 = P (QoC = bad|observations) P 1 = P (QoS = good|observations) P 2 = P (QoS = degraded|observations) P 3 = P (QoS = bad|observations) if [P 1 > max(P 2 , P 3 )] || [P 2 > max(P 1 , P 3 )]

	order=0
	else
	if P 3 > max(P 2 , P 1 )
	order=1
	end if
	end if
	mote station whose position is (1,1) and BNT toolbox
	(Murphy et al. 2001) is used to implement the BN.
	The robot starts from its initial position (x0, y0)=(0,0)
	to the target one (xd, yd)= (15,1) as shown in the fig-
	ure
	controller type	CPU load
		controller
	QoS
		QoC
	robot
	state
	distance robot-obstacle	stability	position error
	Figure 4: Control Bayesian Module
	4 DIAGNOSIS SCENARIO
	A diagnosis scenario is presented below to verify
	the efficiency of the developed approach to decisions
	making. Based on the QoC state in the one hand and

on the QoS state on the other hand, the remote station orders the robot to switch to its embedded controller if it is necessary. Algorithm 1 is used as a strategy to control the robot in distance using the Bayesian diagnosis results after entering observations on the BN. Truetime toolbox (2.0 version)

[START_REF] Cervin | Truetime 2.0 betareference manual[END_REF]

) is used to co-simulate (network and control cosimulation) the networked robot controlled by a re-Algorithm 1