Lluís Godo
email: godo@iiia.csic.es

Enrico Marchioni
email: enrico.marchioni@irit.fr

Logics for Non-Cooperative Games with Expectations

We introduce the logics E(G) for reasoning about probabilistic expectation over classes G of games with discrete polynomial payoff functions represented by finite-valued Lukasiewicz formulas and provide completeness and complexity results. In addition, we introduce a new class of games where players' expected payoff functions are encoded by E(G)-formulas. In these games each player's aim is to randomise her strategic choices in order to affect the other players' expectations over an outcome as well as their own. We offer a logical and computational characterisation of this new class of games.

Introduction

In this work, we introduce the logics E(G) for reasoning about probabilistic expectation over classes G of games with discrete polynomial payoff functions represented by finite-valued Lukasiewicz formulas. This type of games, called Lukasiewicz games [START_REF] Marchioni | Lukasiewicz Games[END_REF], is a generalisation of Boolean games [START_REF] Bonzon | Boolean games revisited[END_REF][START_REF] Harrenstein | Boolean games[END_REF] and involves a finite set of players P = {P 1 , . . . , P n }, each controlling a finite set of propositional variables V i , so that the sets V i are mutually disjoint. Being in control of a set V i of propositional variables means that P i assigns to the variables in V i values from the scale

L k = 0, 1 k , . . . , k -1 k , 1 .
A strategy for a player P i is a function s : V i → L k that corresponds to a valuation of the variables controlled by P i . Strategies can be interpreted as efforts or costs, and each player's strategic choice can be seen as an assignment to each controlled variable carrying an intrinsic cost. Each player is assigned a finite-valued Lukasiewicz formula ϕ i , with propositional variables from n i V i , whose valuation is interpreted as the payoff function for P i and corresponds to the restriction over L k of a continuous piecewise linear polynomial function with integer coefficients. Notice that not all variables in ϕ i might be under P i 's control and, consequently, P i 's payoff from playing a certain strategy (i.e. choosing a certain variable assignment) also depends on the choices made by (some of) the other players.

In this work, we expand Lukasiewicz games by providing an explicit definition of a class G of games, and also defining suitable concepts of a mixed strategy, best response and Nash Equilibrium, adapted to this framework. Then, we define a probabilistic logic E(G) over many-valued formulas (of finite-valued Lukasiewicz logic) to reason about expectations in a class G of Lukasiewicz games. This might be in principle a bit surprising since probabilities are not the same as expectations, but the reason is simple. The generalisation of a classical probability measure on Boolean algebras to the algebraic setting of MV-algebras [START_REF] Cignoli | Algebraic Foundations of Many-alued Reasoning[END_REF] (the algebraic counterpart of Lukasiewicz logics) corresponds to the so-called states [START_REF] Mundici | Averaging the truth-value in Lukasiewicz logic[END_REF], which can be seen as averages of truth-values. Indeed, a state (or finitelyadditive probability) σ over the set of Lukasiewicz logic formulas L (built from a given set of propositional variables V ) is a mapping σ : L → [0, 1] such that:

-σ(1) = 1, -σ(ϕ ⊕ ψ) = σ(ϕ) + σ(ψ), if ¬(ϕ&ψ) is a Lukasiewicz tautology, -σ(ϕ) = σ(ψ), if ϕ ↔ ψ is a Lukasiewicz tautology.
When we consider only finite-valued Lukasiewicz logics L k , as proved in [START_REF] Paris | A note on the Dutch Book method (revised version)[END_REF], a mapping σ : L → [0, 1] is a state on formulas iff there exists a probability distribution π :

Ω k → [0, 1] on the set of L k -valuations Ω k on L such that σ(ϕ) = w∈Ω k p(w) • w(ϕ).
The state σ(ϕ) corresponds to a weighted average of the truth-values of ϕ under all possible valuations, and it can also be regarded as the expected value of the function f ϕ : Ω k → [0, 1], defined as f ϕ (w) = w(ϕ) for all w ∈ Ω k . If we look at Lukasiewicz formulas as a particular class of functions, to reason about the probability of these formulas amounts to reasoning about the expectation of the corresponding functions. This is the view we take in this paper.

Note that a logic, called F P ( L n , L), to reason about the probability of L kformulas was defined and axiomatised in [START_REF] Flaminio | A logic for reasoning about the probability of fuzzy events[END_REF]. The logic E(G) introduced here is a (partially) syntactical and semantic expansion of F P ( L n , L), and its expressive power makes it possible to represent expectations in games where players' payoffs are given by discrete polynomial functions with integer coefficients over L k (encoded by finite-valued Lukasiewicz formulas).

E(G) is built from a set of non-modal formulas ϕ, ψ, . . . that correspond to formulas of the finite-valued Lukasiewicz logic L c k (with additional truth constants for each element c ∈ L k ), and a set of modal formulas Eϕ, Eψ, . . . to represent the expectation associated to each ϕ, ψ, . . . . Modal formulas are combined with the connectives of the LΠ 1 2 -logic [START_REF] Esteva | The LΠ and LΠ 1 2 logics: two complete fuzzy logics joining Lukasiewicz and product logic[END_REF], which makes it possible to express combinations of polynomial equalities and inequalities with rational coefficients.

Based on the logics E(G), we also introduce a new class of games, called Lukasiewicz games with expectations, that generalise Lukasiewicz games. In the situations of strategic interactions modelled in Game Theory, the goal of each player is essentially the maximisation of her own expected payoff. Players, however, often care not only about maximising their own expectation, but also about influencing other players' expected outcomes. Lukasiewicz games with expectations offer a formalisation of these kinds of strategic interactions where each player's aim is to randomise her strategic choices in order to affect the other players' expectations over an outcome as well as their own expectation. Lukasiewicz games with expectations expand Lukasiewicz games by assigning to each player P i a modal formula Φ i of E(G), whose interpretation corresponds to a piecewise rational polynomial function whose variables are interpreted as expected values. The modal formula Φ i assigned to each player is then meant to represent a player's goal concerning the relation between her and other players' expectations.

This work is organised as follows. 1 The next section introduces the basic background notions about Lukasiewicz logics and the LΠ 1 2 -logic. In Section 3, we present the main definition of a Lukasiewicz game, define the concept of a class G of games and build the logics E(G) to represent expectations in each G. We provide both completeness and complexity results for E(G). In Section 4, we introduce games with expectations based on E(G) and offer some examples along with a logical and computational characterisation. We end with some final remarks.

Logical Background

The language of Lukasiewicz logic L (see [START_REF] Cignoli | Algebraic Foundations of Many-alued Reasoning[END_REF]) is built from a countable set of propositional variables {p 1 , p 2 , . . .}, the binary connective → and the truth constant 0 (for falsity). Further connectives are defined as follows:

¬ϕ is ϕ → 0, ϕ ∧ ψ is ϕ&(ϕ → ψ), ϕ&ψ is ¬(ϕ → ¬ψ), ϕ ∨ ψ is ((ϕ → ψ) → ψ), ϕ ⊕ ψ is ¬(¬ϕ&¬ψ), ϕ ↔ ψ is (ϕ → ψ)&(ψ → ϕ), ϕ ⊖ ψ is ϕ&¬ψ, d(ϕ, ψ) is ¬(ϕ ↔ ψ).
Let Form denote the set of Lukasiewicz logic formulas. A valuation e from Form into [0, 1] is a mapping e : Form → [0, 1] assigning to all propositional variables a value from the real unit interval (with e(0) = 0) that can be extended to complex formulas as follows: A valuation e satisfies a formula ϕ if e(ϕ) = 1. As usual, a set of formulas is called a theory. A valuation e satisfies a theory T , if e(ψ) = 1, for every ψ ∈ T .

e(ϕ → ψ) = min
Infinite-valued Lukasiewicz logic has the following axiomatisation:

( L1) ϕ → (ψ → ϕ), ( L2) (ϕ → ψ) → ((ψ → χ) → (ϕ → χ)), ( L3) (¬ϕ → ¬ψ) → (ψ → ϕ), ( L4) ((ϕ → ψ) → ψ) → ((ψ → ϕ) → ϕ).
The only inference rule is modus ponens, i.e.: from ϕ → ψ and ϕ derive ψ.

A proof in L is a sequence ϕ 1 , . . . , ϕ n of formulas such that each ϕ i either is an axiom of L or follows from some preceding ϕ j , ϕ k (j, k < i) by modus ponens. We say that a formula ϕ can be derived from a theory T , denoted as T ⊢ ϕ, if there is a proof of ϕ from a set T ′ ⊆ T . A theory T is said to be consistent if

T ⊢ 0.
Lukasiewicz logic is complete with respect to deductions from finite theories for the given semantics, i.e.: for every finite theory T and every formula ϕ, T ⊢ ϕ iff every valuation e that satisfies T also satisfies ϕ.

For each k ∈ N, the finite-valued Lukasiewicz logic L k is the schematic extension of L with the axiom schemas:

( L5) (n -1)ϕ ↔ nϕ, ( L6) (kϕ k-1 ) n ↔ nϕ k ,
for each integer k = 2, . . . , n -2 that does not divide n -1, and where nϕ is an abbreviation for ϕ ⊕ • • • ⊕ ϕ (n times) and ϕ k is an abbreviation for ϕ& . . . &ϕ, (k times). The notions of valuation and satisfiability for L k are defined as above just replacing [0, 1] by

L k = 0, 1 k , . . . , k -1 k , 1
as set of truth values. Every L k is complete with respect to deductions from finite theories for the given semantics.

It is sometimes useful to introduce constants in addition to 0 that will denote values in the domain L k . Specifically, we will denote by L c k the Lukasiewicz logic obtained by adding constants c for every value c ∈ L k . We assume that valuation functions e interpret such constants in the natural way: e(c) = c.

A McNaughton function [START_REF] Cignoli | Algebraic Foundations of Many-alued Reasoning[END_REF] is a continuous piecewise linear polynomial functions with integer coefficients over the nth-cube [0, 1] n . To each Lukasiewicz formula ϕ(p 1 , . . . , p n ) we can associate a McNaughton function f ϕ so that, for every valuation e f ϕ (e(p 1 ), . . . , e(p n )) = e(ϕ(p 1 , . . . , p n )).

Every L-formula is then said to define a McNaughton function. The converse is also true, i.e. every continuous piecewise linear polynomial function with integer coefficients over [0, 1] n is definable by a formula in Lukasiewicz logic. In the case of finite-valued Lukasiewicz logics, the functions defined by formulas are just the restrictions of McNaughton functions over (L k ) n . In this sense, we can associate to every formula ϕ(p 1 , . . . , p n ) from L k a function f ϕ : (L k ) n → L k . As for each L c k , the functions defined by a formula are combinations of restrictions of McNaughton functions and, in addition, the constant functions for each c ∈ L k . The class of functions definable by L c k -formulas exactly coincides with the class of all functions f : (L k ) n → L k , for every n ≥ 0.

The expressive power of infinite-valued Lukasiewicz logic lies in, and is limited to, the definability of piecewise linear polynomial functions. Expanding L with the connectives ⊙, → Π of Product logic [START_REF] Hájek | Metamathematics of Fuzzy Logic[END_REF], interpreted as the product of reals and as the truncated division, respectively, significantly augments the expressive power of the logic. The LΠ 1 2 logic [START_REF] Esteva | The LΠ and LΠ 1 2 logics: two complete fuzzy logics joining Lukasiewicz and product logic[END_REF] is the result of this expansion, obtained by adding the connectives ⊙, → Π , 1 2 , whose valuations e extend the valuations for L as follows:

e(ϕ ⊙ ψ) = e(ϕ) • e(ψ) e(ϕ → Π ψ) = 1 e(ϕ) ≤ e(ψ) e(ψ) eϕ otherwise e 1 2 = 1 2 e(∆ϕ) = 1 e(ϕ) = 1 0 otherwise
Notice that the presence of the constant 1 2 makes it possible to define constants for all rationals in [0, 1] (see [START_REF] Esteva | The LΠ and LΠ 1 2 logics: two complete fuzzy logics joining Lukasiewicz and product logic[END_REF]). LΠ 1 2 's axioms include the axioms of Lukasiewicz and Product logics (see [START_REF] Hájek | Metamathematics of Fuzzy Logic[END_REF]) as well as the following additional axioms, where ∆ϕ is ¬ϕ → Π 0:

( LΠ1) (ϕ ⊙ ψ) ⊖ (ϕ ⊙ χ) ↔ ϕ ⊙ (ψ ⊖ χ), ( LΠ2) ∆(ϕ → ψ) → (ϕ → Π ψ), ( LΠ3) ∆(ϕ → Π ψ) → (ϕ → ψ), ( LΠ4) 1 2 ↔ ¬ 1 2 .
The deduction rules are modus ponens for & and →, and the necessitation rule for ∆, i.e.: from ϕ derive ∆ϕ. LΠ 1 2 is complete with respect to deductions from finite theories for the given semantics [START_REF] Esteva | The LΠ and LΠ 1 2 logics: two complete fuzzy logics joining Lukasiewicz and product logic[END_REF].

While L is the logic of McNaughton functions, LΠ 1 2 is the logic of piecewise rational functions with integer coefficients over [0, 1] n (see [START_REF] Montagna | Adding structures to MV-algebras[END_REF]). In fact, the function defined by each LΠ 1 2 -formula corresponds to a supremum of rational fractions P (x 1 , . . . , x n ) Q(x 1 , . . . , x n ) over [0, 1] n , where P (x 1 , . . . , x n ), Q(x 1 , . . . , x n ) are polynomials with rational coefficients. Conversely, every piecewise rational function with rational coefficients over the unit cube [0, 1] n can be defined by an LΠ 1 2 -formula.

Logics for Representing Expectation

In this section we first introduce the concept of a Lukasiewicz game on L c k along with the notion of a class G of Lukasiewicz games. Then, we define the logic E(G) to represent expected payoffs for games in G, and provide completeness and complexity results.

Lukasiewicz Games

A Lukasiewicz game G on L c k [START_REF] Marchioni | Lukasiewicz Games[END_REF] is a tuple

G = P, V, {V i }, {S i }, {ϕ i }
where:

1. P = {P 1 , . . . , P n } is a set of players; 2. V = {p 1 , . . . , p m } is a finite set of propositional variables; 3. For each i ∈ {1, . . . , n}, V i ⊆ V is the set of propositional variables under control of player P i , so that the sets V i form a partition of V, |V i | = m i , and

n i=1 m i = m. 4.
For each i ∈ {1, . . . , n}, S i is the strategy set for player P i that includes all valuations s : V i → L k of the propositional variables in V i , i.e.

S i = {s | s : V i → L k }.
5. For each i ∈ {1, . . . , n}, ϕ i (p 1 , . . . , p t ) is an L c k -formula, built from variables in V, whose associated function

f ϕi : (L k ) t → L k
corresponds to the payoff function of P i , and whose value is determined by the valuations in {S 1 , . . . , S n }.

We denote by S = S 1 × • • • × S n the product of the strategy spaces. A tuple s = (s 1 , . . . , s n ) ∈ S of strategies is called a strategy combination. s -i denotes the tuple of strategies (s 1 , . . . , s i-1 , s i+1 , . . . , s n ) not including s i . Aside from s, we use the form (s i , s -i ) do denote a strategy combination. With an abuse of notation, we denote by f ϕi (s i , s -i ) (or, equivalently, f ϕi (s)) the value of the payoff function f ϕi under the valuation corresponding to the strategy combination (s i , s -i ) [or, equivalently, s]. 2Given a game G, let δ : P → {1, . . . , m} be a function assigning to each player P i an integer from {1, . . . , m} that corresponds to the number of variables in V i : i.e.:

δ(P i ) = m i .
δ is called a variable distribution function. Given a game G, the type of G is the triple n, m, δ , where n is the number of players, m is the number of variables in V, and δ is the variable distribution function for G.

Definition 1 (Class). Let G and G ′ be two Lukasiewicz games G and G ′ on L c k of type n, m, δ and n, m, δ ′ , respectively. We say that G and G ′ belong to the same class G if there exists a permutation  of the indices {1, . . . , n} such that, for all P i , δ(P (i) ) = δ ′ (P i ).

Notice that what matters in the definition of a type is not which players are assigned certain variables, but rather their distribution. For instance, take two games G and G ′ all having three players P 1 , P 2 , P 3 and the same variables p 1 , . . . , p 6 . Suppose that, in G, P 1 controls p 1 , P 2 controls p 2 , p 3 , and P 3 controls p 4 , p 5 , p 6 , while in G ′ , P 2 controls p 3 , P 3 controls p 4 , p 5 , and P 1 controls p 1 , p 2 , p 6 . G and G ′ have the same type, since they have the same number of players, the same number of variables, and the permutation , where

1  -→ 2 2  -→ 3 3  -→ 1,
is such that δ P (i) = δ ′ (P i ) for all P i . Given the above definitions, we can adapt some well-known game-theoretic concepts to this settings. We introduce the notion of mixed strategy in order to define the concept of expected payoff along with the notions of best response and equilibrium.

Let G = P, V, {V i }, {S i }, {ϕ i } be a Lukasiewicz game on L c k . A mixed strategy π i for player P i is a probability distribution on the strategy space S i . By π -i , we denote the tuple of mixed strategies (π 1 , . . . , π i-1 , π i+1 , . . . , π n ).

Given a tuple (π 1 , . . . , π n ) of mixed strategies for P 1 , . . . , P n , respectively, the expected payoff for P i of playing π i , when P -i play π -i , is given by

exp ϕi (π i , π -i ) = s=(s1,...,sn)∈S     n j=1 π j (s j )   • f ϕi (s)  
Let Σ i denote the set of mixed strategies of P i . P i 's best response to P -i 's mixed strategy combination π -i is a mixed strategy π i such that, for all strategies

π ′ i ∈ Σ i : exp ϕi (π i , π -i ) ≥ exp ϕi (π ′ i , π -i ).
Definition 2 (Nash Equilibrium). Let G be a Lukasiewicz game on L c k . We call a tuple of mixed strategies (π * 1 , . . . , π * n ) a Nash Equilibrium for G if each player's mixed strategy π * i is a best response to the other players' mixed strategy combination π * -i .

Example: Matching Pennies. The following game is a generalisation of Matching Pennies 3 , a classic example of a zero-sum game without a pure strategy equilibrium. In the original game, two players P 1 and P 2 both have a penny and must secretly choose to turn it to head or tails and reveal their choice at the same time. If their choices agree, P 1 takes both pennies, but if they do not match, P 2 is the one winning both. Now, imagine that both players have a dice with n + 1 faces, they both choose one and reveal it at the same time. P 1 's overall strategy is to be as close as possible to P 2 's choice, who, instead, wants to keep the greater possible distance between the outcomes. Clearly, we can represent each player's strategy space with the set L k . P 1 's payoff function is given by the formula ¬d(p 1 , p 2 ), whose associated function is 1-|e(p 1 )-e(p 2 )|, while P 2 's payoff is defined by the formula d(p 1 , p 2 ), which corresponds to the function |e(p 1 ) -e(p 2 )|. The game is formally defined on L c k as follows:

G = {P1, P2}, {p1, p2}, {p1}1, {p2}2, {s1 : {p1} → L k }, {s2 : {p2} → L k }, {¬d(p1, p2), d(p1, p2)} .
Table 1 shows the payoff matrix for this generalised version of Matching Pennies with k = 5 (the values in each cell correspond to the first and second player payoffs under the valuation to the variables p 1 , p 2 ). By Nash's Theorem [START_REF] Nash | Non-cooperative games[END_REF], we know that an equilibrium with mixed strategies always exists for the generalised version of Matching Pennies.

The Logic E(G)

The aim of this section is to introduce the logic E(G) for reasoning about expected utility in games with Lukasiewicz strategies. Notice that, while sometimes we refer to E(G) as "a logic", we are actually defining a whole family of logics, one for each class G.

Syntax The construction of E(G) mimics the one provided for logics for reasoning about uncertainty in [START_REF] Flaminio | Reasoning about uncertainty of fuzzy events: an overview[END_REF]. The syntax of E(G) is built by taking the m-variable fragment m L c k4 of L c k as inner logic and LΠ 1 2 as outer logic. Its language is defined as follows:

1. The set NModF of non-modal formulas corresponds to the set of m L c kformulas built from the propositional variables p 1 , . . . , p m .

The set ModF of modal formulas is built from the atomic modal formulas

Eϕ, with ϕ ∈ NModF, using the LΠ 1 2 connectives. Eϕ is meant to encode a player's expected payoff from playing a mixed strategy, given the payoff function associated to ϕ. Nested modalities are not allowed.

Semantics Given a class of games G on m L c k , a model M for E(G) is a tuple S, e, {π i } , such that:

1. S is the set of all strategy combinations {s = (s 1 , . . . , s n ) | (s 1 , . . . , s n ) ∈ S 1 × • • • × S n }.
2. e : (NModF × S) → L k is a valuation of non-modal formulas, such that, for

each ϕ ∈ NModF e(ϕ, s) = f ϕ (s),
where f ϕ is the function associated to ϕ and s = (s 1 , . . . , s n ).

3. π i : S i → [0, 1] is a probability distribution, for each P i .

Given a formula Φ, the truth value of Φ in M at the combination s, denoted Φ M,s , is inductively defined as follows:

1. If Φ is a non-modal formula ϕ ∈ NModF, then ϕ M,s = e(ϕ, s),

If Φ is an atomic modal formula Eϕ, then

Eϕ M,s = exp ϕ (π 1 , . . . , π n ) = s=(s1,...,sn)∈S     n j=1 π j (s j )   • e(ϕ, s)   . 5
3. If Φ is a non-atomic modal formula, its truth value is computed by evaluating its atomic modal subformulas and then by using the truth functions associated to the LΠ 1 2 -connectives occurring in Φ.

Since the valuation of a modal formula Φ does not depend on a specific strategy combination but only on the model M, we will often simply write Φ M to denote the valuation of Φ in M. As usual, we say that a formula Φ is satisfiable if there exists a model M such that Φ M = 1. Similarly, a modal theory Γ , i.e. a set of modal formulas, is satisfiable if there exists a model that satisfies each and every one of the formulas contained in Γ . Validity clearly means satisfiability in all models.

Axiomatisation The axioms of E(G) are the following:

1. All the L c k -tautologies for m L c k , i.e.: all the L c k -tautologies in the variables p 1 , . . . , p m , for non-modal formulas.

2. All the LΠ 1 2 -axioms and rules for modal formulas. 3. Probabilistic axioms for E, with ϕ, ψ, r ∈ NModF:

(a) E(¬ϕ) ↔ ¬Eϕ (b) E(ϕ ⊕ ψ) ↔ [(Eϕ → E(ϕ&ψ)) → Eψ] (c) Er ↔ r
4. Independence axioms for E, where p 1i , . . . , p mi is the tuple of variables assigned to P i , for all tuples r 11 , . . . , r m1 , . . . , r 1n , . . . , r mn ∈ (L k ) m : encodes a particular strategy for player P i . In fact, each ∆ (p ji ↔ r ji ) is satisfiable if and only if e(p ji ) = r ji . So, given a tuple r 1i , . . . , r mi , ( †) is satisfiable by a strategy s i if and only if s i (p ji ) -→ r ji , for all p ji .

(a) E n i=1 mi ji=1i (∆ (p ji ↔ r ji )) ↔ n i=1 E mi ji=1i ∆ (p ji ↔ r ji
The notion of proof in E(G) is defined as usual. For any modal theory Γ and formula ϕ, we write

Γ ⊢ E(G) ϕ to denote that ϕ is a consequence of Γ in E(G).
Completeness Before we prove completeness for E(G) we provide an axiomatic characterisation for the expectation of mixed strategies over m L c k -formulas.

Theorem 1. Let G be a class of Lukasiewicz games on L c k and let m L c k be the m-variable fragment of L c k . The following statements are equivalent:

1. There exists a state

σ : m L c k → [0, 1]
. such that for all tuples r 11 , . . . , r m1 , . . . , r 1n , . . . ,

r mn ∈ (L k ) m σ   n i=1   mi ji=1i (∆ (p ji ↔ r ji ))     = n i=1   σ   mi ji=1i ∆ (p ji ↔ r ji )     ,
where p 1i , . . . , p mi is the tuple of variables assigned to P i . 2. There exists a probability distribution

π i : S i → [0, 1]
for each P i , such that, for all ϕ ∈ m L c k , σ(ϕ) = exp ϕ (π 1 , . . . , π n ), i.e.: σ(ϕ) = s=(s1,...,sn)∈S     n j=1 π j (s j )   • f ϕ (s)   ,
where f ϕ is the function associated to ϕ.

Proof. It is easy to check that (2) implies (1).

To prove the converse, suppose that there exists a state

σ : m L c k → [0, 1]
. As shown by Paris in [18, Appendix 2] there exists a probability distribution π :

S 1 × • • • × S n → [0, 1] such that σ(ϕ) = s∈S π(s) • f ϕ (s), for all ϕ ∈ m L c k . Now, let m i L c
k [p i ] be the m i -variable fragment of L c k in the variables p i = {p 1i , . . . , p mi }, i.e. the variables assigned to P i . Let σ ↓i be the restrictions of σ to

m i L c k [p i ].
It is clear that each σ ↓i is still a probability measure. It follows, again, from [18, Appendix 2] that, for each i, there exists a probability distribution

π i : S i → [0, 1] such that, for all ψ ∈ m i L c k [p i ] σ(ψ) = σ ↓1 (ψ) = si∈Si π i (s i ) • f ψ (s i ).
By assumption, σ satisfies

σ   n i=1   mi ji=1i (∆ (p ji ↔ r ji ))     = n i=1   σ   mi ji=1i ∆ (p ji ↔ r ji )     ,
for all tuples r 11 , . . . , r m1 , . . . , r 1n , . . . , r mn ∈ (L k ) m . It is possible to check that the above condition guarantees the fact that all probability distributions π i are independent, and so for all s ∈ S π(s)

= n i=1 π i (s i ). Therefore σ(ϕ) = s∈S π(s) • f ϕ (s) = s=(s1,...,sn)∈S     n j=1 π j (s j )   • f ϕ (s)   .
We can now proceed to proving the Completeness Theorem.

Theorem 2 (Completeness). Let Γ and Φ be a finite modal theory and a modal formula in E(G). Then, Γ ⊢ E(G) Φ if and only if for every model M such that, for each Ψ ∈ Γ , Ψ M = 1, also Φ M = 1.

Proof. The proof follows from an adaptation of the strategy laid out in [START_REF] Hájek | Metamathematics of Fuzzy Logic[END_REF] and generalised in [START_REF] Flaminio | Reasoning about uncertainty of fuzzy events: an overview[END_REF].

We now study the computational complexity of certain kinds of satisfiability problems for E(G). Let r ∈ Q ∩ [0, 1] and let ♭ ∈ {<, >, ≤, ≥, =}. We call an E(G)-modal formula Φ ♭r-satisfiable if there is a model M such that Φ M ♭r.

Following a strategy similar to the one laid out by Hájek in [START_REF] Hájek | Complexity of fuzzy probability logics II[END_REF] for probability logics, satisfiability of an E(G)-formula Φ can be translated into an existential formula in the theory of the reals whose size is exponential in the number of non-modal propositional variables in Φ. Decidability for the existential theory of the reals Th ∃ (R) was shown by Canny to be in PSPACE [START_REF] Canny | Some algebraic and geometric computations in PSPACE[END_REF]. Therefore, we obtain the following result: Theorem 3. Checking ♭r-satisfiability for E(G) is in EXPSPACE.

Games with Expectations

In this section we introduce a class of games with polynomial constraints over expectations. These games expand Lukasiewicz games by assigning to each player a formula of E(G), which is a piecewise rational polynomial function whose variables correspond to expected values. The idea is that in a situation of strategic interaction players might be interested not only in maximizing their own expectation, but also in influencing others'. The modal formula assigned to each player is then meant to represent a player's goal concerning the relation between her and other players' expectations.

A game with expectations E G on E(G) is a tuple

E G = P, V, {V i }, {S i }, {ϕ i }, {M i }, {Φ i } ,
where:

1. G = P, V, {V i }, {S i }, {ϕ i } is a Lukasiewicz game on L c k , with G ∈ G, 2.
for each i ∈ {1, . . . , n}, M i is the set of all mixed strategies on S i of player P i , 3. for each i ∈ {1, . . . , n}, Φ i is an E(G)-formula such that every atomic modal formula occurring in Φ i has the form Eψ, with ψ ∈ {ϕ 1 , . . . , ϕ n }.

Let E G be a game with expectations on E(G). A model M = S, e, {π i } for E(G) is called a best response model for a player P i whenever, for all models

M ′ = S, e, {π ′ i } with π ′ -i = π -i , Φ i M ′ ≤ Φ i M .
Definition 3 (Equilibrium). A game with expectations E G on E(G) is said to have a Nash Equilibrium, whenever there exists a model M * that is a best response model for each player P i .

Example 1. Let E G be any game with expectations where each P i is simply assigned the formula Φ i := Eϕ i . This game corresponds to the the situation where each player cares only about her own expectation and whose goal is its maximisation. Clearly, by Nash's Theorem [START_REF] Nash | Non-cooperative games[END_REF], every E G of this form admits an Equilibrium, since it offers a formalisation of the classical case where equilibria are given by tuples of mixed strategies over valuations in a Lukasiewicz game.

Example 2. Not every game with expectations has an equilibrium. In fact, consider the following game

E G = P, V, {V i }, {S i }, {ϕ i }, {M i }, {Φ i } ,
with i ∈ {1, 2}, where:

1. ϕ 1 := p 1 and ϕ 2 := p 2 , and 2. Φ 1 := ¬d(E(p 1 ), E(p 2 )) and Φ 2 := d(E(p 1 ), E(p 2 )).

The above game can be regarded as a particular version of Matching Pennies with expectations. In fact, while P 1 aims at matching P 2 's expectation, P 2 's goal is quite the opposite, since she wants their expectations to be as far as possible.

It is easy to see that there is no model M that gives an equilibrium for E G .

Proposition 1. There exist games with expectations on E(G) that do not admit a Nash Equilibrum.

As mentioned above, the satisfiability of every E(G)-formula can be translated into the validity of an existential formula of the theory Th(R) of real closed fields. In a similar way, we can express the existence of an equilibrium in a game with expectations E G through a first-order sentence ξ of Th(R) having exponentially many variables and a fixed alternation of quantifiers. By using the fact that the general decidability problem for Th(R) is singly exponential in the number of variables when the alternation of quantifiers is fixed [START_REF] Grigor'ev | Complexity of deciding Tarski algebra[END_REF], we obtain the following result.

Theorem 4 (Complexity). Checking the existence of a Nash Equilibrium in a game with expectations E G on E(G) is in 2-EXPTIME.

By exploiting the connection between LΠ 1 2 and real closed fields it is also possible to express the existence of an equilibrium through an LΠ 1 2 -formula (see [START_REF] Esteva | Fuzzy logics with enriched language[END_REF]). Therefore, we obtain the following logical characterisation.

Theorem 5. For every game with expectations E G on E(G) there exists an LΠ 1 2formula φ such that E G admits a Nash Equilibrium if and only if φ is satisfiable.

Final Remarks

In this work, we presented a logic E(G) for reasoning about expectations in a class G of Lukasiewicz games. We have also introduced a new class of games based on E(G) that expand Lukasiewicz games. These games capture strategic interactions in which players randomise their choices in order to influence the expectations of the other players as well as their own.

While our approach to representing expectation in games in a logical framework is certainly novel, other works have dealt with similar topics. In [START_REF] Halpern | Characterizing and reasoning about probabilistic and nonprobabilistic expectation[END_REF], Halpern and Pucella introduced a propositional logic for reasoning about probabilistic expectation. Their work, though, is mainly concerned with modelling expectation in general and not in a game-theoretic setting. Certainly closer to our paper is the work by Sack and van der Hoek [START_REF] Sack | A Modal Logic for Mixed Strategies[END_REF], where the authors study a modal logic to reason about mixed strategies in games. Although (each instance of) their logic is based on a fixed game and a fixed set of mixed strategies, it makes it possible to represent the concept of a Nash Equilibrium through logical formulas: a feature that is not possible in our logic.

In our future work, we plan to extend the logical study of expectation for Lukasiewicz games to those situations where payoff formulas are functions defined over the whole unit cube [0, 1] n , and, consequently, players have an infinite strategy space.

  (1 -e(ϕ) + e(ψ), 1) e(¬ϕ) = 1 -e(ϕ) e(ϕ&ψ) = max(0, e(ϕ) + e(ψ) -1) e(ϕ ⊕ ψ) = min(1, e(ϕ) + e(ψ)) e(ϕ ⊖ ψ) = max(0, e(ϕ) -e(ψ)) e(ϕ ∧ ψ) = min(e(ϕ), e(ψ)) e(ϕ ∨ ψ) = max(e(ϕ), e(ψ)) e(d(ϕ, ψ)) = |e(ϕ) -e(ψ)| e(ϕ ↔ ψ) = 1 -|e(ϕ) -e(ψ)|

) 5 .

 5 The following inference rules for E, with ϕ, ψ ∈ NModF: (a) Necessitation: from ϕ derive Eϕ (b) Monotonicity: from ϕ → ψ derive Eϕ → Eψ p ji ↔ r ji ))

Table 1 .

 1 Generalised Matching Pennies.

Notice that the proofs of the main results are either simply sketched or omitted due to space constraints.

fϕ i (si, s-i) can be also seen as the value of e(ϕi), when e coincides with the valuation s.

The idea behind this generalisation comes from[START_REF] Kroupa | Nash Equilibria in a class of constant-sum games represented by McNaughton functions[END_REF].

Notice that the functions definable in m L c k are exactly all the functions f : (L k ) t → L k , where t ≤ m.

Notice that the notation is slightly different from the one used above for the definition of expected payoff but the meaning is the same.

Acknowledgments

Godo acknowledges support from the Spanish projects EdeTRI (TIN2012-39348-C02-01) and AT (CONSOLIDER CSD 2007-0022). Marchioni acknowledges support from the Marie Curie Project NAAMSI (FP7-PEOPLE-2011-IEF).


El Houssein

Chouaib Harik

Student Member, IEEE François Guérin

Frédéric Guinand

Jean-François Brethé

Member, IEEE Hervé Pelvillain

UAV-UGV Cooperation For Objects Transportation In An Industrial Area

We present in this paper a decentralized multirobot (aerial and ground) cooperation scheme for objects transportation. A team of ground mobile robots guided by a drone and a human operator moves in a coordinated way keeping a predefined formation in order to carry objects (tools, gas masks,...) in unsafe industrial areas. One ground mobile robot (leader) navigates among obstacles thanks to the waypoints provided by the drone and the human operator. The other ground mobile robots (followers) use a predictive vision based target tracking controller to keep a certain distance and bearing to the leader.

I. INTRODUCTION

A. Motivation and related works

Multi-robot cooperation attracts increasingly the attention of researchers, essentially for the numerous advantages that brings the deployment of a multi-robot system to perform a specific task. It brings the problems to a simpler level when the task complexity is too high to be performed by a single-robot to accomplish [START_REF] Parker | Multiple Mobile Robot Systems[END_REF]. Nevertheless, multi-robot cooperation raises different challenges, in particular, the resolution of problems related to perception, decision and action [START_REF] Lacroix | issues in cooperative air/ground robotic systems[END_REF]. We can find in the literature a huge amount of works related to multi-robot systems, surveys can be found in [START_REF] Jiménez-González | Testbeds for ubiquitous robotics: A survey[END_REF], [START_REF] Yan | A survey and analysis of multi-robot coordination[END_REF], and [START_REF] Uny Cao | Cooperative mobile robotics: Antecedents and directions[END_REF].

A distinguished type of multi-robot cooperation is Air-Ground-Cooperation (AGC), where Unmanned Aerial Vehicles (UAVs) and Unmanned Ground Vehicles (UGVs) work in a cooperative way in order to perform a given task. The main advantage that can be drawn from AGC is the complementary skills provided by each type to overcome the specific limitations of the others (payload, perception, velocities, computational abilities, etc...), endowing a complete system to achieve a specific mission with higher efficiency and better delays. Moreover, deploying UAVs and UGVs in a single mission allows to envisage a wide range of applications.

In [START_REF] Michael | Collaborative mapping of an earthquakedamaged building via ground and aerial robots[END_REF], an earthquake-damaged building scenario is used as an experimental field for providing a 3D map of the top three floors using a team of UAVs and UGVs. The main purpose of this work is to provide an insight of the degree of damage inside that building, and the team of robots (one UGV equipped with a laser rangefinder, one UAV also equipped with a laser rangefinder and a RGBD sensor) was able to fulfill the task (to map the three floors) in a relatively short period of time (one afternoon). Similar works using AGC for mapping missions can be found in [START_REF] Forster | Air-ground localization and map augmentation using monocular dense reconstruction[END_REF], [START_REF] Kim | A hierarchical approach to probabilistic pursuit-evasion games with unmanned ground and aerial vehicles[END_REF], [START_REF] Vidal | Pursuit-evasion games with unmanned ground and aerial vehicles[END_REF], [START_REF] Hsieh | Adaptive teams of autonomous aerial and ground robots for situational awareness[END_REF]. Another application of AGC is cooperative navigation, where usually the UAV acts like a remote sensor or a flying eye [START_REF] Stentz | Integrated air/ground vehicle system for semi-autonomous off-road navigation[END_REF]. In this work the authors use a UAV that flies ahead the UGV to provide geo-referenced 3D geometry in order to navigate safely avoiding obstacles (holes and ditches). The experimental results were threefold: the first experimentation consists in using only onboard sensors of the UGV to navigate in the area. In the second experimentation the UGV uses a traversability map that was already captured by the UAV and its onboard sensors. The third experimentation is similar to the second one with difference of adding new obstacle to the environment that has not been mapped before. The main scenario where the UAV flies ahead the UGV was validated through simulations, but some experimentations were carried out with the UAV manually piloted. A follow-up of the previous work can be found in [START_REF] Stentz | Real-time, multi-perspective perception for unmanned ground vehicles[END_REF]. The authors improved mainly their perception system, the UGV is still provided with prior maps taken from the UAV. Another approach can be found in [START_REF] Sofman | Terrain classification from aerial data to support ground vehicle navigation[END_REF] to overcome the UGV sensors limitations to detect negative obstacles (holes, cliffs, etc...). An aerial unmanned helicopter is used to gather data of an area, each point of data has three components: global spacial position, color measurements (RGB), and laser reflectance power measurement. In order to generate the obstacles cost map, a neural network classifier is used to classify the covered area into four classes (road, grass, tree, and building). The processed data is used as an input for a UGV planner to navigate in the covered area. Other related work using AGC for cooperative navigation and state estimation can be found in [START_REF] Faessler | A monocular pose estimation system based on infrared leds[END_REF], [START_REF] Donald | Unmanned ground vehicle state estimation using an unmanned air vehicle[END_REF], [START_REF] Madhavan | Temporal range registration for unmanned ground and aerial vehicles[END_REF], [START_REF] Choi | Collaborative Tracking Control of UAV-UGV[END_REF], [START_REF] Chaimowicz | Experiments in multirobot air-ground coordination[END_REF], [START_REF] Stentz | Integrated air/ground vehicle system for semi-autonomous off-road navigation[END_REF], [START_REF] Vandapel | Unmanned ground vehicle navigation using aerial ladar data[END_REF], [START_REF] Vandapel | Quality assessment of traversability maps from aerial lidar data for an unmanned ground vehicle[END_REF], [START_REF] Vandapel | Experimental results in using aerial ladar data for mobile robot navigation[END_REF].

Extending these ideas, our team proposes a new scenario. We use a UAV to provide a global coverage for a team of UGVs during objects transportation. A human operator is in charge of supervising the team and providing waypoints to navigate safely in the area. For the team of UGVs we use a leader-follower approach. One UGV is designated at all times as a leader, while the other UGVs designated as the followers navigate in the area keeping a predefined distance and bearing to the leader using their embedded vision system. Visualbased formation has already largely been studied ( [START_REF] Couto Gava | Nonlinear control techniques and omnidirectional vision for team formation on cooperative robotics[END_REF], [START_REF] Luca Mariottini | Vision-based localization for leader-follower formation control[END_REF], [START_REF] Roberti | Stable formation control for a team of wheeled mobile robots[END_REF]). The images acquired from an omnidirectional camera mounted on the leader allow to estimate the follower's pose. Thus the leader sends relative angular and linear velocities to the followers in order to maintain the desired formation. An omnidirectional camera offers a wide view, but it also needs important computational resources and complex algorithms (pose estimation). In our work, a pan-tilt colored camera is embedded on each follower, and a vision based tracking controller has been designed [START_REF] Guerin | double exponential smoothing for predictive vision based target tracking of a wheeled mobile robot[END_REF] to extract the distance and the bearing angle to a colored marker mounted on the leader.

B. Contribution and organization

Our contribution is twofold: in the previous related works, a first flight of the drone over the inspected area is always performed before the beginning of the mission. A traversability map is then processed to provide a trajectory to the UGV.

The first contribution of our work consists in providing a real-time navigation scheme. The UAV flies over the area to provide a global coverage, and to assist a UGV in real-time to navigate safely avoiding obstacles. To provide the real-time navigation scheme without the need to have a per-processed map, a human operator is included to select waypoints by monitoring the global and local coverages, making the architecture interactive, and applicable to real scenarios. For numerous reasons, monitoring, surveillance and inspection of industrial sites belonging to Seveso category (highly critical sites) cannot be performed without a constant and careful attention of human experts.

The second contribution concerns the visual-based formation. In the previous works, the leader is always responsible for observing the followers state. It sends the necessary linear and angular velocities of each follower to maintain a predefined configuration. We use in our work a leaderfollower approach, with the difference that each follower is considered as an independent entity. It uses its embedded color vision system to estimate the leader's pose (distance and bearing of the colored marker mounted on the leader) to regulate the linear and angular velocities accordingly. Thus no communication between the team members is required, what makes our proposed architecture does not need significant computational and communication requirements.

This paper is organized as follows: we present in section II the problem statement, and discuss the envisaged scheme. Section III presents the architecture design. We give in section IV some simulation and experimental results, and we conclude in section V the present work and discuss future perspectives.

II. PROBLEM STATEMENT

A UAV (drone) is used to guide among obstacles (Figure 1) a team of UGVs (mobile robots) to perform objects transportation tasks (tools, gas masks,...) in unsafe industrial areas. The video flow is sent continuously to the ground station from the camera mounted on the UAV. It is used in real time to provide localization information to a UGV (that we will designate as a leader) to navigate in the industrial area through the on-the-go waypoints selected by a human operator.

The other UGVs are called followers and are used to carry heavy loads. As the leader navigates to each next waypoint, these followers take the leader as a target and follow it keeping a certain separation distance and bearing in order to form a specific configuration that can be defined prior, or during the mission. In our study, we used two followers, but this number can be extended depending on the mission goals.

III. ARCHITECTURE DESIGN

A. Hardware configuration

We will consider in this work three similar non-holonomic, unicycle-like wheeled mobile robot (UGV) and a quadcopter drone (UAV) equipped with a color camera. The video flow is sent continuously to the ground station where it will be processed to extract the position and the orientation of the leader relative to the next waypoint. These information are then sent to the leader to correct its trajectory in real time using a non-linear kinematic controller.

B. Overall architecture

We can divide our architecture (Figure 2) in two layers: Drone-Leader layer, and Leader-Followers layer. We will explain in the next section the functionality as well as the controllers design of each layer. In the first layer (leader-followers), the followers use their embedded vision system to track the leader keeping a predefined configuration (Figure 3). The embedded vision system is assumed to be located at a distance L from Y F , the y-axis of the UGV coordinate frame (Figure 4). The vision system outputs are the distance (range) z and the orientation (bearing) θ of a follower relative to the moving target (leader). The control objective (Figure 4) consists in regulating the distance z and the bearing angle θ as follows:

z 0 < lim t→∞ z(t) < z 1 lim t→∞ θ(t) = θ 0 (1)
Where z 0 is the predefined separation distance, and θ 0 is the predefined bearing angle. θ 0 is + π 6 for the first follower (right), and -π 6 for the second follower (left) (Figure 3). As the leader moves at unknown velocities, and because of the non-holonomic constraints of the UGVs, the distance z cannot be regulated to z 0 permanently, it has to be bounded with an upper allowable distance z 1 .

1) Design of the non-linear kinematic controller: To fulfill the control objective (1), we consider the following errors e XF and e Y F corresponding to the differences between the initial and the tracking state:

e XF = z.cos(θ) -z 0 .cos(θ 0 ) e Y F = z.sin(θ) -z 0 .sin(θ 0 ) (2)
The time derivatives of e XF and e Y F are given by: ėXF = ż.cos(θ) -z. θ.sin(θ) ėY F = ż.sin(θ) + z. θ.cos(θ)

ėXF and ėY F depends on the UGV's velocities (u,r) and the target's velocities along the X F and Y F axes, denoted as T V XF , T V Y F , thus (3) can be written as follows:

ėXF = T V XF -u ėY F = T V Y F -r.L (4)
r.L is the linear velocity of the point on the UGV at which the embedded vision system is located. The angle θ can vary between -π/2 and +π/2 due to mechanical restrictions. We propose the following stable error dynamic equations:

ėXF = -K.e XF ėY F = -K.e Y F (5)
Where (K > 0) is a proportional gain, substituting ( 2) and (3), this leads to:

T V XF -u = -K.(z.cos(θ) -z 0 .cos(θ 0 )) T V Y F -r.L = -K.(z.sin(θ) -z 0 .sin(θ 0 )) (6)
Since the target's velocities (T V XF , T V Y F ) are unknown, we propose the following non-linear kinematic controller:

u = K.(z.cos(θ) -z 0 .cos(θ 0 )) r = K.(z.sin(θ) -z 0 .sin(θ 0 ))/L (7)
2) Stability analysis: We consider the following Lyapunov candidate function:

V = e XF 2 + e Y F 2 2 (V > 0) (8)
Its time derivative can be written as: 3) DES algorithm: The Double Exponential Smoothing (DES) algorithm [START_REF] Jr | an experiment comparing double exponential smoothing and kalman filter-based predictive tracking algorithms[END_REF] has been implemented to smoothen the uncertain measurement given by the vision system. The DES algorithm runs approximately 135 times faster with equivalent prediction performances and simpler implementations compared to a Kalman filter.

V = e XF . ėXF + e Y F . ėY F (9) V = e XF .(T V XF -K.e XF )+e Y F .(T V Y F -K.e Y F ) (10) Thus, V < 0 if |e XF | ≥ | T V XF K | and |e Y F | ≥ | T V Y F K | so that
The DES algorithm at time instant n.T e , where T e is the sampling period and n is the discrete-time index, implemented for both the distance (z) and bearing angle (θ) measurements is given as follows: Equations ( 11) and ( 13) smooth the values of the sequence of measurements by taking into account the trend, whilst ( 12) and ( 14) smooth and update the trend. The m (m > 0) steps ahead forecast of the next position (z) estimation is:

S zn = γ z .z n + (1 -γ z ).(S zn-1 + b zn-1 ) (11
F Zn+m = S Zn + m.b Zn ( 15
)
The initial values given to S zn , S θn , b zn and b θn are:

S z1 = z 1 , S θ1 = θ 1 , b z1 = z 2 -z 1 , b θ1 = θ 2 -θ 1 ( 16
)
Usually, γ (0 ≤ γ ≤ 1) is called the data smoothing factor and λ (0 ≤ λ ≤ 1) is called the trend smoothing factor.

A compromise has to be found for the values of γ and λ.

High values make the DES algorithm follow the trend more accurately whilst small values make it generate smoother results. By using the DES algorithm, the non-linear kinematic controller (7) becomes:

u = K.(S zn .cos(S θn ) -z 0 .cos(θ 0 )) r = K.(S zn .sin(S θn ) -z 0 .sin(θ 0 ))/L (17)
In [START_REF] Choi | Collaborative Tracking Control of UAV-UGV[END_REF], the smoothed values are used instead of the direct noisy measurements of z and θ. F Zn+m the prediction of z in [START_REF] Donald | Unmanned ground vehicle state estimation using an unmanned air vehicle[END_REF] can now be used for the auto-tuning of the proportional gain (K) in the non-linear kinematic controller as follows:

dK dt = β.sign(F Zn+m -z * 0 ) with β > 0 (18)
In discrete time (sampling period T e ), ( 18) can be written as:

K n = K n-1 + T e .β.sign(F Zn -z * 0 ) (19)
The proportional gain K increases or decreases stepwise. This auto-tuning allows to satisfy the control objective (1), since the distance z can never be regulated to z 0 permanently due to the random motion of the target, the non-holonomic restrictions and the dynamic properties of the UGV. The value of z * 0 is chosen according to equation (1) to satisfy the control objective (namely the allowable upper bound specification): z 0 < z * 0 < z 1 .

D. Second layer: Drone-Leader

A UAV equipped with a colored camera is used to provide a global coverage of the industrial area. It assists the UGV (leader) in navigation among obstacles. The UAV flies at a constant altitude, keeping the UGV (leader) in the center of the image plan (visual servoing). Waypoints are assigned in the image plan by a human operator according to the free-space navigation (Figure 5). The UGV (leader) navigates through the selected waypoints, followed continuously by the UAV (this work is under submission). Note that the classical pinhole model [START_REF] Guerin | commande conjuguée d'un robot mobile, modélisation dynamique et vision artificielle[END_REF] is used to estimate the reference values of d and α in the world frame. They were previously extracted in pixels (image processing). Odometry is used to estimate the UGV's current state to its next waypoint.

Let us consider (Figure 5) the following distance errors on X L and Y L axes respectively:

e X L = d.cos(α) -L e Y L = d.sin(α) (20)
The time derivative of the distance errors [START_REF] Vandapel | Quality assessment of traversability maps from aerial lidar data for an unmanned ground vehicle[END_REF], which depends on both the leader's velocities (u, r) and the target's velocities along the X L and Y L axes, denoted as T V X L and T V Y L , are given by:

ėX L = ḋ.cos(α) -d. α.sin(α) = T V X L -u ėY L = ḋ.sin(α) + d. α.cos(α) = T V Y L -rL (21)
Where rL corresponds to the linear velocity of R h (blue marker).

T V X L and T V Y L are null since the leader's target is a waypoint. We propose then the following stable error dynamic equations:

ėX L = -K.e X L = -u ėY L = -K.e Y L = -r.L (22)
Where K > 0 is the proportional gain of the leader's controller. Note that for large values of the distance d, a saturation is implemented to consider the limitations of the electrical drives that control the WMR's wheels.

Starting from [START_REF] Couto Gava | Nonlinear control techniques and omnidirectional vision for team formation on cooperative robotics[END_REF] we propose the following non-linear kinematic controller:

u = K.(d.cos(α) -L) r = K.(d.sin(α))/L (23)
Stability analysis can be studied starting from the same Lyapunov function [START_REF] Kim | A hierarchical approach to probabilistic pursuit-evasion games with unmanned ground and aerial vehicles[END_REF], which shows that the stability of our proposed controller ( 23) is guaranteed.

IV. RESULTS

A. Simulation results

We will present in this section simulation results of the proposed architecture. We simulated a real-like scenario to navigate in the transportation area through the given waypoints. For each UGV (leader and followers), we have used the dynamic model described in [START_REF] Guerin | double exponential smoothing for predictive vision based target tracking of a wheeled mobile robot[END_REF] and [START_REF] Guerin | commande conjuguée d'un robot mobile, modélisation dynamique et vision artificielle[END_REF]. Simulations have been carried out with Matlab-Simulink software (sampling period: 10ms). For the follower's non-linear kinematic controllers, we used the same parameters as in [START_REF] Guerin | double exponential smoothing for predictive vision based target tracking of a wheeled mobile robot[END_REF] except for the bearing angle (θ 0 = ±π/6) and the distance z 0 = 80cm. For the UGV's non-linear kinematic controller we used the following parameters: L = 18cm, K = 0.1. The simulated scenario consists in giving waypoints to navigate in a specific area avoiding obstacles. Figure 6 shows the trajectories of each UGV. The simulation showed the efficiency of the developed architecture and the proposed controllers. The leader is able to follow the given waypoints and the followers are able to navigate using it as a target while keeping a predefined separation distance and bearing angle.

In figures 7,8,9, we notice that the mean distance between the UGVs is around 98cm. It corresponds to the addition of the given distance to be maintained between the UGVs z 0 =80cm and L=18cm, which confirms the efficiency of our developed controller [START_REF] Choi | Collaborative Tracking Control of UAV-UGV[END_REF]. We can see (Figure 6) that the leader's trajectory is discontinuous. It stops at each waypoint to change its direction to the next one, which explains the peaks on figures 7,8,9. They correspond to the moment when the leader changes its direction for a new waypoint, creating a sharp variation in the corresponding distance between him and the followers. Note that maintaining the distance between the three UGVs means the maintain of the desired angle θ 0 .

B. Experimental results

We created a user interface using the development environment Processing [START_REF][END_REF] running on the ground station, where a human operator can supervise in real time the UGVs through a video flow received continuously from the camera mounted beneath the UAV. The human operator can select waypoints in the image by a simple click on the desired position. The program extracts and send the distance d and the orientation α to the leader via ZigBee module (IEEE 802.15.4) at a 50Hz frequency (real time interrupt). Because we do not yet have access to position measurements in the inertial frame (using for example VICON MX system), the results concerning the leader-followers layer are limited to simulations trials only. Figure 10 shows that the UGV, after clicking on the desired waypoint, used the bearing angle α and the distance d received from the ground station, to navigate successfully to that point.

V. CONCLUSION AND FUTURE WORK

We introduced in this paper a control scheme for a multirobot system where a group of UGVs and a UAV work for a transportation task. One UGV is designated at all times to be the leader of a team of UGVs (followers). A UAV is used to provide a global coverage of the area allowing the leader to navigate safely in the transportation area through waypoints selected by a human operator. Each follower is considered as an independent entity. It navigates using a predictive vision based target tracking controller taking the leader as a target, what makes the communication and computational requirements kept at a lower level. The tracking algorithm can be improved by endowing the follower's controllers by the leader's velocity, which will limit the distance errors between the UGVs and thus will improve the proposed architecture for cooperatively transporting a single heavy load.

Fig. 1 .

 1 Fig. 1. Problem statement

Fig. 2 .

 2 Fig. 2. Overall architecture

Fig. 3 .Fig. 4 .

 34 Fig. 3. Leader-follower configuration

  the size of the tracking errors |e XF | and |e Y F | are uniformly ultimately bounded by ( T V XF K ) and ( T V Y F K ) respectively, where (T V XF ) and (T V Y F ) represent bounds on the target's velocity components satisfying |T V XF | < T V XF and |T V Y F | < T V Y F . These tracking errors can never become zero because the target velocities are unknown to the controller. However, large gain K leads to small error bounds. That is why we are going to propose in the next section an automatic tuning of the proportional gain K resting on the use of a predictive double exponential smoothing algorithm.

  )b zn = λ z .(S zn -S zn-1 ) + (1 -λ z ).b zn-1 (12)S θn = γ θ .θ n + (1 -γ θ ).(S θn-1 + b θn-1 )(13) b θn = λ θ .(S θn -S θn-1 ) + (1 -λ θ ).b θn-1 (14) Where: z n , θ n are the values of z and θ at nth sample instant. S zn , S θn are the smoothed values of z and θ. b zn and b θn are the trend values.

Fig. 5 .

 5 Fig. 5. Leader controller

Fig. 6 .

 6 Fig. 6. Waypoints tracking

Fig. 7 .Fig. 8 .

 78 Fig. 7. Distance between the leader and the follower 1

Fig. 9 .

 9 Fig. 9. Distance between the follower 1 and the follower 2

Fig. 10 .

 10 Fig. 10. Waypoint tracking experimentation

LITIS, University of Le Havre.

Rue Philippe Lebon, 76600 Le Havre Cedex (France) -(el-houssein-chouaib.harik,frederic.guinand)@univlehavre.fr 2 GREAH, University of Le Havre. 75, Rue Bellot, 76058 Le Havre Cedex (France) -(francois.guerin,jean-francois.brethe)@univ-lehavre.fr[START_REF] Jiménez-González | Testbeds for ubiquitous robotics: A survey[END_REF] IUT GEII, University of Le Havre. Rue Boris Vian, 76610 Le Havre Cedex (France) -herve.pelvillain@univ-lehavre.fr


Hervé Elettro

Fritz Vollrath

Arnaud Antkowiak

Sébastien Neukirch

Coiling of an elastic beam inside a disk: a model for spider-capture silk

Motivated by recent experimental observations of capillary-induced spooling of bers inside droplets both in spider capture silk and in synthetic systems, we investigate the behavior of a ber packed in a drop. Using a simplied 2D model, we provide analytical predictions for the buckling threshold and the deep post-buckling asymptotic behavior. The threshold for spooling is found to be in particularly good agreement with experimental results. We further solve the Elastica equations for a ber conned in a soft potential, and track the equilibrium paths using numerical continuation techniques. A wealth of dierent paths corresponding to dierent symmetries is uncovered, and their stability is nally discussed.

Introduction

The mechanical properties of spider silk are often presented as outstanding [START_REF] Foelix | Biology of spiders[END_REF][START_REF] Omenetto | New Opportunities for an Ancient Material[END_REF]. An indeed, most silk threads outperform the best man-made bers, such a Kevlar, at least in terms of toughness [START_REF] Vollrath | Liquid crystalline spinning of spider silk[END_REF]. To a large extent, these properties rely on the molecular architecture of the silk. For example, it has been shown that the building blocks of agelliform silk involve molecular nanosprings [START_REF] Becker | Molecular nanosprings in spider capture-silk threads[END_REF]. In 1989 however, a team comprising a zoologist and a physicist reported on coiling and packing of the core lament inside a glue droplet [START_REF] Vollrath | Modulation of the mechanical properties of spider silk by coating with water[END_REF]. This windlass mechanism, as it was called, provided indirect evidence that the glue droplets may as well play a role in the mechanical response of the silk thread. These results have been a subject of debate in the community, and it is only very recently that the mechanism has been observed to be active in a real spider web, see Fig. 1-Left and [START_REF] Elettro | In-drop capillary spooling of spider capture thread inspires highly extensible bres[END_REF]. A natural question that arises in this context is the role played by the molecular structure of the silk and the glue in the observed coiling. An experimental answer to this question is provided in Fig. 1-Right, where a micron-sized articial thread bearing a silicon oil droplet also exhibits the coiling mechanism and packing behavior, therefore demonstrating that capillarity and elasticity are sucient ingredients to explain the mechanism.

Figure 1: Experiments on bers bent inside liquid drops. Left: microscopic photograph of spider capture silk. Flagelliform core laments are seen to be coiled and packed inside a (typically 300 µ wide) glue droplet. Right: same mechanism reproduced articially with a 200 µm synthetic droplet and ber (see experimental verication section in section 4). Reproduced from [START_REF] Elettro | In-drop capillary spooling of spider capture thread inspires highly extensible bres[END_REF].

Interestingly, the shape adopted by the lament inside the drop can be as dierent as a perfectly ordered closelypacked annular bundle or a completely disordered tangle. This behavior is reminiscent of the organization of packed Email address: sebastien.neukirch@upmc.fr (Sébastien Neukirch) wires in rigid [START_REF] Stoop | Packing of Elastic Wires in Spherical Cavities[END_REF] and elastic [START_REF] Vetter | Morphogenesis of laments growing in exible connements[END_REF] spherical shells, patterns of folded structures such as plant leaves or crumpled paper [START_REF] Boué | Spiral Patterns in the Packing of Flexible Structures[END_REF][START_REF] Couturier | The lling law: A general framework for leaf folding and its consequences on leaf shape diversity[END_REF], and DNA packing inside capsids [START_REF] Lamarque | Packaging Double-Helical DNA into Viral Capsids[END_REF][START_REF] Klug | Three-dimensional director-eld predictions of viral DNA packing arrangements[END_REF][START_REF] Leforestier | Structure of toroidal DNA collapsed inside the phage capsid[END_REF]. The purpose of the present paper is to explore theoretically in a simplied setting the shape and stability of strongly post-buckled states in order to lay down the basis for a deeper understanding of the windlass mechanism.

The paper is organized as follows. In section 2 we present the problem and the equilibrium equations. In section 3 we perform a linear stability analysis of the straight beam and predict the buckling threshold. Experimental results are confronted to theoretical in section 4 experiments. Finally, we describe the non-linear response of the system in terms of equilibrium solutions and their stability in section 5

Model

T x x

=L Δ A B C s = 0 s = L y s = L / 2 Λ B Λ A R Figure 2:
An elastic beam held in tension at its extremities, and buckling under the action of compressive forces at a disk. The beam is clamped at both ends. The deformation of the beam is described by the angle θ(S) between the tangent to the beam and the x-axis, where S ∈ [0, L] is the arc-length along the beam.

We consider an elastic beam in interaction with a liquid disk and under the action of a tensile end-load. As indicated in Fig. 2, we restrict to planar deformations of the beam, X and Y denoting the horizontal and vertical directions respectively. The beam has length L and a circular cross-section of radius h. We work under the slender (L h) Euler-Bernoulli hypotheses where the beam is considered inextensible and unshearable. Congurations are thus fully described by the position and orientation of the centerline. We use the arc-length S ∈ [0, L] and note θ(S) the angle between the tangent of the beam and the horizontal. The presence of the liquid disk generates capillary forces due to the contrast of surface energy, the interaction energy of the beam with the liquid being smaller than the interaction energy of the beam with the air. Capillary forces are two-fold: (i) meniscus forces applied on the beam at the entrance and exit of the disk, and (ii) barrier forces that prevent the beam from exiting the disk elsewhere than at the meniscus points. We consider that the drop is undeformable and thus remains a disk throughout the experiments. As shown in Appendix A, meniscus forces are pointing toward the center of the disk (see Equations (A.15) and (A.18)) and their intensity is related to the angle between their direction and the tangent to the beam at the meniscus points (see Equation (A.25)). A soft-wall barrier potential [START_REF] Manning | Stability of an elastic rod buckling into a soft wall[END_REF] V

(X, Y ) = V 0 1 + ρ -(1/R) (X -X C ) 2 + (Y -Y C ) 2 (1)
is used to retain the beam inside the disk, centered on (X C , Y C ) and of radius R. The small dimensionless parameter ρ is introduced to avoid the potential to diverge at the meniscus points A and B, where the rod enters and exits the disk. The intensity V 0 of the potential is chosen to be small, the hard-wall limit being V 0 → 0. Kinematics, relating the position (X, Y ) of the rod and the inclination θ of its tangent (cos θ, sin θ) with the horizontal, the bending constitutive relation, relating the curvature θ (S) to the moment M (S), and nally force (N x , N y ) and moment balance are detailed in Appendix A and read

X (S) = cos θ , Y (S) = sin θ (2a) EI θ (S) = M , M (S) = N x sin θ -N y cos θ (2b) N x (S) = χ ∂V ∂X + δ(S -S A ) Λ A X A -X C R + δ(S -S B ) Λ B X B -X C R (2c) N y (S) = χ ∂V ∂Y + δ(S -S A ) Λ A Y A -Y C R + δ(S -S B ) Λ B Y B -Y C R ( 2d
)
where S is the arc-length along the rod, and () = d()/dS. We dene the coordinates of point A as

(X A , Y A ) = (X(S A ), Y (S A )),
-γ SL = γ LV cos α Y ),
and where V A = V B = V 0 /ρ are small compared to F γ . We restrict ourself to cases where the disk is centered on the mid-point of the rod, that is we introduce Σ such that S A = L/2 -Σ and S B = L/2 + Σ. The rod has then 2 Σ of its arc-length spent inside the disk. Finally the external applied tension is noted T = N x (L).

Non-dimensionalization

We use the diameter D = 2R of the disk as unit length, and the buckling load EI/D 2 as unit force. We thus introduce the following dimensionless quantities

s = S D ; σ = Σ D ; = L D ; (x, y) = (X, Y ) D ; n = N D 2 EI ; t = T D 2 EI (3a) f γ = F γ D 2 EI ; m = M D EI ; λ A,B = Λ A,B D 2 EI ; (v, v 0 ) = (V, V 0 ) D 2 EI (3b)
and δ(s) = D δ(S). We then have v(x, y)

= v 0 1 + ρ -2 (x -x C ) 2 + (y -y C ) 2 -1 and
x (s) = cos θ , y (s) = sin θ (4a) θ (s) = m , m (s) = n x sin θ -n y cos θ (4b) n x (s) = χ ∂v ∂x + 2δ(s -s A ) λ A (x A -x C ) + 2δ(s -s B ) λ B (x B -x C ) (4c) n y (s) = χ ∂v ∂y + 2δ(s -s A ) λ A (y A -y C ) + 2δ(s -s B ) λ B (y B -y C ) (4d)
where () = d()/ds, and s A = /2 -σ, s B = /2 + σ.

Boundary-value problem

We consider v 0 , ρ, f γ , and as xed parameters and we look for equilibrium solutions by integrating equations ( 4) with the initial conditions

x(0) = 0 ; y(0) = 0 ; θ(0) = 0 ; m(0) = m 0 ; n x (0) = n x0 ; n y (0) = n y0 (5)
where m 0 , n x0 , and n y0 are unknowns to be accompanied with σ, x C , y C , λ A , and λ B . We therefore have 8 unknowns which are balanced by the following 7 conditions. At the s = end of the rod, clamped boundary conditions read

y( ) = 0 ; θ( ) = 0 (6)
The requirement that points A and B lie on the circle yields the conditions

[x A -x C ] 2 + [y A -y C ] 2 = 1/4 ; [x B -x C ] 2 + [y B -y C ] 2 = 1/4 (7)
and the three force balances related to forces coming from the disk read

n x (s - A ) = n x (s + B ) (8a) n y (s - A ) = n y (s + B ) (8b) -2f γ + v A + v B -2λ A [(x A -x C ) cos θ(s A ) + (y A -y C ) sin θ(s A )] + 2λ B [(x B -x C ) cos θ(s B ) + (y B -y C ) sin θ(s B )] = 0 (8c)
The solution set is thus a 8 -7 = 1 dimensional manifold and we plot in Section 5 dierent solution paths for several values of the parameter f γ .

Buckling threshold

The trivial solution x(s) = s, y(s) = θ(s) = m(s) = n y (s) = 0 to Equations ( 4) with boundary conditions ( 5)-( 8), exists for any value of the load t. Nevertheless, for given values of the parameters v 0 , ρ, f γ , and , there is a threshold value of t under which the trivial solution ceases to be stable and buckling occurs. We look for the rst buckling mode which is symmetrical with respect to the axis joining the center of the disk (x C , y C ) and the beam midpoint (x( /2), y( /2)). We linearize equations (4) for small deections, |y(s)| ∼ , and small slopes, |θ(s)| ∼ , with 0 < 1, see Appendix B for a comprehensive exposition of this perturbation expansion. As in the buckling conguration the rod has virtually no packing interaction with the disk, we set v 0 = 0. The rst four equations of system (4) become x (s) = 1, y (s) = θ(s), θ (s) = m(s), and m (s) = n x (s) θ(s) -n y (s). We then have x C = /2, x A = /2 -σ, and x B = /2 + σ. At order 0 , equation ( 7) yields σ = 1/2. As symmetry imposes y A = y B and θ(s A ) = -θ(s B ), Equation ( 7) at order 2 imposes y C = y A = y B . Then (8c) at order 0 yields 2f γ = λ A + λ B and, as symmetry requires λ A = λ B , we nally obtain f γ = λ A = λ B . Following symmetry we introduce ŝ = s -/2. The three functions y(ŝ), θ(ŝ), and m(ŝ) are then respectively even, odd, and even functions of the variable ŝ. We focus on the right half of the system, ŝ

∈ [0; /2]. Equation (4c) is integrated to yield n x (ŝ) = t -f γ for ŝ ∈ [0; 1/2] and n x (ŝ) = t for ŝ ∈ [1/2; /2]. Equation (4d) shows that n y (ŝ) = const. and from m (ŝ) = n x (ŝ) θ(ŝ) -n y (ŝ)
we see that n y (ŝ) has to be odd, hence zero. We nally arrive at the reduced system

θ = -(f γ -t) θ for ŝ ∈ [0; 1/2] (9)
θ = t θ for ŝ ∈ [1/2; /2] (10)
and we restrict to the f γ > t ≥ 0 case. Integrating these equations and using the boundary conditions θ(ŝ = 0) = 0 = θ(ŝ = /2) and the matching conditions θ(ŝ = 1/2 -) = θ(ŝ = 1/2 + ) and m(ŝ = 1/2 -) = m(ŝ = 1/2 + ), we obtain the buckling condition

f γ -t tanh ( -1) √ t 2 + √ t tan f γ -t 2 = 0 (11)
which is plotted in Figure 3. The two interesting asymptotic limits of the curve dened by [START_REF] Lamarque | Packaging Double-Helical DNA into Viral Capsids[END_REF]

are (i) if t → 0 then f γ → π 2 + 8/ , and (ii) if f γ → +∞ then t → f γ -4π 2 .
Approximations to the buckling load

In the case where 1, we simplify Equation ( 11) and nd

f γ -t + √ t tan f γ -t 2 = 0 (12)
This formula has the same large f γ limit as [START_REF] Lamarque | Packaging Double-Helical DNA into Viral Capsids[END_REF] and in fact as → +∞, the curve dened by [START_REF] Lamarque | Packaging Double-Helical DNA into Viral Capsids[END_REF] tends to the curve dened by [START_REF] Klug | Three-dimensional director-eld predictions of viral DNA packing arrangements[END_REF] everywhere but in a boundary layer around (f γ , t) = (π 2 , 0). Indeed even if is large, for small t the tanh term cannot be approximated by 1 if t ∼ 1/ 2 . It is convenient to have an explicit formula t = t(f γ ) for buckling and we introduce the approximation

t b (f γ ) = f γ -4π 2 - 108π 4 3π 4 -40π 2 + (3π 2 -28) f γ + (32π -6π 3 ) f γ ( 13
)
This last formula has the same behavior as ( 12) at low t: we have t b (f γ = π 2 ) = 0, and t b (f γ = π 2 ) = 0. Moreover (13) also shares the large f γ limit of ( 11) and ( 12): t b = -4π 2 + f γ + . . .. We see in Figure 3 that the curves dened by ( 12) and ( 13) are in fact hard to distinguish.

Π 2 2 Π 2 4 Π 2 6 Π 2 F Γ D 2 EI

Experimental verication

In order to verify experimentally and quantitatively the mechanics of the windlass, we place a drop on a ber and test whether the bre coils in the drop. The bre is made of BASF Thermoplastic PolyUrethan (TPU) that is melt-spinned. This process involves melting down the TPU, then applying a large extension rate to the liquid lament while it cools down rapidly in the ambient air. It results in reproducible, meter-long micronic bres (1-20 µm in radius) with portions away from the edges having small perturbations in radius (typically <5% every 1000 radii). Calipers are used to further manipulate the samples. Clamping is achieved with cured Loctite R glue. The system size is measured optically with a Leica macroscope (VZ85RC) mounted on a micro-step motor and a 3 megapixels Leica DFC-295 camera (400× magnication, 334nm/pixel picture resolution) with a Phlox 50x50 mm backlight, at 60000 lux or alternatively an optical bre with LED lamp (Moritex MHF-M1002) with circular polarizer. The bre radius is then extracted by image analysis, using imageJ (http://imagej.nih.gov/ij/). For the droplet, we select silicone oil Rhodorsil 47V1000, the gure 1000 referring to its viscosity compared to water. High viscosity was chosen in order to be able to deposit drops on the bre by brushing, and for its slow evaporation properties. Using the condition that meniscus forces have to support the weight of the droplet and be strong enough to buckle the beam, we nd that to be bendable, a TPU bre must be below 7.2 µm in radius, with E TPU = 17 ± 3 MPa, γ silicone-oil/air = 21.1mN/m, α Y, silicone-oil/TPU = 27 ± 5 degrees and ρ silicone-oil = 960 kg/m 3 the silicone oil density.

We deposit a drop on a bre with a known radius and we slowly bring the caliper forks closer to impose compression on the bre. If the drop is able to coil the bre, the macroscopic consequences are easily visible to the naked eye. If at rst try the drop does not coil, the sample is tested again with a random compression and a slight shake to overcome any possible metastability. The couple drop/ber is given an activity index of 1 if coiling is achieved and 0 otherwise (see gure 4). The experimental results show that coiling is present whenever f γ > π 2 , with a error of margin of 3%, consistent with equation (11).

Nonlinear post-buckling computations Equilibrium paths

We now analyze the post-buckling regime by numerically solving the non-linear system of equilibrium equations. We use a shooting method to solve the boundary-value problem (4)-( 8) and a pseudo-arc-length continuation algorithm to follow the solution as parameters are varied, both of these routines being implemented in Mathematica. For large f γ values, typically f γ > 15, numerical diculties arise and we thankfully switch to the AUTO package [START_REF] Doedel | Numerical Analysis And Control of Bifurcation Problems (II): Bifurcation In Innite Dimensions[END_REF]. We x

E D EI C 1 C 2 C 3 C 4 C 5 C 6 A x P t L 1 L 2
Figure 5: Post-buckling paths: (Left) Force-displacement curves for fγ = 20, where t is the applied tension and δ the end-shortening, and (Right) Energy Ê as function of δ. Solid lines represents both Ax congurations, where the beam shape is symmetric with respect to the axis joining the center of the disk (x C , y C ) and the beam midpoint (x( /2), y( /2)), and P t congurations, where the beam shape is symmetric with respect to the beam midpoint P t. Dashed lines correspond to L 1 and L 2 congurations. = 10, v 0 = 0.02, ρ = 0.2, and we compute force-extension bifurcation diagrams for several values of f γ . We show in Figure 5 such a diagram for f γ = 20 where the tension t is plotted as function of the end-shortening δ = -x( ). The diagram comprises four dierent equilibrium paths: (i) path Ax where congurations are symmetric with respect to the axis joining the center of the disk (x C , y C ) and the beam midpoint (x( /2), y( /2)), (ii) path P t where congurations are symmetric with respect to the beam midpoint, (iii) path L 1 where congurations are looping once inside the disk, and (iv) path L 2 where congurations are looping twice inside the disk. Few of these congurations are shown in Figure 6. In a typical experiment the system is rst completely straight, held by a large tension t. This situation corresponds to a point on the vertical axis of Figure 5, above the buckling threshold. As t is decreased the systems reaches the start of the Ax path, and the beam buckles. For f γ = 20, the numerically found value of the buckling tension t 3.66 is to be compared to t b (20) 3.76 given by ( 13), and t 3.73 given by [START_REF] Lamarque | Packaging Double-Helical DNA into Viral Capsids[END_REF]. As the system branches on the Ax path, tension goes up again we have a subcritical bifurcation. The slope of the Ax path is calculated analytically in Appendix B and is plotted in Figure B.8 for comparison. As the beam enters deeper in the postbuckling regime, bending localizes inside the disk and the tails remain approximatively straight. The path eventually reaches a plateau, see formula [START_REF] Manning | Stability of an elastic rod buckling into a soft wall[END_REF], where the beam coils in a circular way inside the disk and the bending energy in the beam can then be approximated by (1/2) EI/R 2 [L -X(L)]. We also plot the t > 0 part of the path P t. This path also reaches the same plateau as the beam coils in the same circular way inside the disk. In addition we plot Figure 6: Post-buckling congurations. Top row shows Ax congurations, symmetric with respect to the axis joining the center of the disk (x C , y C ) and the beam midpoint (x( /2), y( /2)). Middle row shows P t congurations, symmetric with respect to the beam midpoint P t. Bottom row represents L 1 and L 2 congurations. The circles have center (x C , y C ) and radius

(1 + ρ)/2.
paths along which the beam adopts congurations with one (path L 1 ) or two (path L 2 ) loops. The relevance of these paths could be questioned for two reasons: (i) conguration on path L 1 do not have the same topology as far as twist is considered: a full turn of twist would be necessary to connect congurations on path Ax or P t with congurations on path L 1 , see [START_REF] Van Der Heijden | Instability and self-contact phenomena in the writhing of clamped rods[END_REF][START_REF] Goss | Experiments on Snap Buckling, Hysteresis and Loop Formation in Twisted Rods[END_REF], and (ii) these paths are not connected to the vertical axis δ = 0. We plot in Figure 5-Right the energy Ê = E κ + E w + E γ -P γ SV L + F γ (∆ + D) as a function of the end-shortening δ and we see that, for some range of the end-shortening δ, congurations on paths L 1 or L 2 have a lower energy than congurations on paths Ax or P t. These remarks call for a stability analysis of the equilibrium congurations, as well as a study of congurations deformed in 3D, where twist, link, and writhe would be computed [START_REF] Elettro | Equilibrium and stability of a twisted rod conned in a liquid drop[END_REF].

Approximate analytical model for the plateau regime

As explained in [START_REF] Elettro | In-drop capillary spooling of spider capture thread inspires highly extensible bres[END_REF], in the regime where the end-shortening δ = -x( ) is large, that is when several coils of the beam are present in the disk, the external tension t reaches a plateau and no longer varies as more coils are added. The plateau value of the tension is calculated by a balance of energy as a beam length ∆S enters the disk. The work done by the tension T is -T ∆S, the work done by the meniscus force F γ is +F γ ∆S, and the energy spent to bend the beam in coils is -(1/2) (EI/R 2 ) ∆S. The sum of these energies is zero on the plateau, which yields

t = f γ -2 (14)
in dimensionless quantities. In Figure 7 we plot Ax and P t equilibrium paths for f γ = 10, 20, . . . , 50 with the vertical axis rescaled according to [START_REF] Manning | Stability of an elastic rod buckling into a soft wall[END_REF]. The collapse of the curves for δ 4 conrms relation [START_REF] Manning | Stability of an elastic rod buckling into a soft wall[END_REF].

Conclusion

This paper presents a rst venture into the complex equilibria adopted by a ber buckled, coiled, and packed by a droplet. Using a simple 2D model and numerical continuation techniques, we have uncovered several equilibrium paths characterized by dierent symmetries (point-symmetric, axis-symmetric, single or double-looped) and provided clues for the bifurcations between these dierent states. Analytical predictions for the buckling threshold, as well as the asymptotic behavior (plateau regime) for the deep post-buckling regime have been derived. The agreement between experiments and theory for the windlass activation threshold is certainly promising, and calls for an extension of the present model to 3D (including twist and writhe), and a deeper comparison between the experimentally observed ordered and disordered packing modes and the theoretical prediction. Finally the deformation of the drop on its own, considered rigid throughout this study, and its interplay with the shape adopted by the ber also deserves a dedicated investigation. Equation (A.4a) imposes that the capturing disk is centered on the mid-point of the rod. We introduce Σ such that S A = L/2 -Σ and S B = L/2 + Σ. The rod has then 2 Σ of its arc-length spent in the disk. As the variables X(S), Y (S), κ(S) and θ(S) all appear in the formulation, we have to consider the continuous constraints relating them: X (S) = cos θ(S), Y (S) = sin θ(S), θ (S) = κ(S) (A.5)

We consequently write the Lagrangian:

L(X,Y, θ, κ 1 , κ 2 , κ 3 , X C , Y C , Σ) = -T X(L)+ L/2-Σ 0 EI 2 κ 2 1 + P γ SV + ν 1 (S) [X -cos θ] + µ 1 (S) [Y -sin θ] + η 1 (S) [θ -κ 1 ] dS+ L/2+Σ L/2-Σ EI 2 κ 2 2 + P γ SL + ν 2 (S) [X -cos θ] + µ 2 (S) [Y -sin θ] + η 2 (S) [θ -κ 2 ] + V (X, Y, X C , Y C ) dS+ L L/2+Σ EI 2 κ 2 3 + P γ SV + ν 3 (S) [X -cos θ] + µ 3 (S) [Y -sin θ] + η 3 (S) [θ -κ 3 ] dS+ Λ A 2R [X (L/2 -Σ) -X C ] 2 + [Y (L/2 -Σ) -Y C ] 2 -R 2 + Λ B 2R [X (L/2 + Σ) -X C ] 2 + [Y (L/2 + Σ) -Y C ] 2 -R 2 (A.6a)
The rod is clamped as both extremities, boundary conditions reads:

X(0) = 0, Y (0) = 0, θ(0) = 0, Y (L) = 0, θ(L) = 0 (A.7)
First variation

We note U = (X, Y, θ, κ 1 , κ 2 , κ 3 , X C , Y C , Σ) and we consider the conditions for the state U e to minimize the energy E. Calculus of variations shows that a necessary condition is

L (U e ) Ū = d d L(U e + Ū ) =0 = 0 (A.8)
where Ū = ( X, Ȳ , θ, κ1 , κ2 , κ3 , XC , ȲC , Σ). The bar ¯sign represents a small perturbation of the variable. Moreover boundary conditions (A.7) imply that X(0) = 0, Ȳ (0) = 0, θ(0) = 0, Ȳ (L) = 0, θ(L) = 0 (A.9)

Noting that

A+ Ā 0 f (x)dx = A 0 f (x)dx + Āf (A) + O( 2 )
we evaluate the rst variation (A.8)

L (U e )( Ū ) = -T X(L) -2F γ Σ + V A Σ + V B Σ+ L/2-Σ 0 EI κ1 κ 1 + ν 1 (S) X + θ sin θ + µ 1 (S) Ȳ -θ cos θ + η 1 (S) θ -κ1 dS+ L/2+Σ L/2-Σ EI κ2 κ 2 + ν 2 (S) X + θ sin θ + µ 2 (S) Ȳ -θ cos θ + η 2 (S) θ -κ2 + V dS L L/2+Σ EI κ3 κ 3 + ν 3 (S) X + θ sin θ + µ 3 (S) Ȳ -θ cos θ + η 3 (S) θ -κ3 dS+ Λ A R [X (L/2 -Σ) -X C ] X (L/2 -Σ) -Σ X (L/2 -Σ) -XC + Λ A R [Y (L/2 -Σ) -Y C ] Ȳ (L/2 -Σ) -Σ Y (L/2 -Σ) -ȲC + Λ B R [X (L/2 + Σ) -X C ] X (L/2 + Σ) + Σ X (L/2 + Σ) -XC + Λ B R [Y (L/2 + Σ) -Y C ] Ȳ (L/2 + Σ) + Σ Y (L/2 + Σ) -ȲC (A.10a)
The variable n y (ŝ), an odd function of ŝ, has also to verify (A.24), which reads n y (ŝ = -σ) = n y (ŝ = σ). Consequently n y (±σ) = 0 and, as n y (ŝ) is constant for |ŝ| > σ, we have that n y (ŝ) ≡ 0, ∀|ŝ| > σ. Moreover, in the limit where the barrier potential tends to zero, v 0 → 01 , n y (ŝ) ≡ 0 inside the disk. Being an odd function, n y (ŝ) is then such that

n y (ŝ) ≡ 0 ∀ŝ (B.2)
The consequence is that the force jumps (A.18) for n y (ŝ) at the entry ŝ = -σ and exit ŝ = +σ of the disk are zero:

λ A [y A -y C ] = 0 = λ B [y B -y C ].
We discard the cases λ A = 0 and λ B = 0 for which there would not be any meniscus force at all, and conclude

y A = y C = y B (B.3)
Conditions (A.4b) and (A.4c) now read (x A -x C ) 2 = 1/4 and (x B -x C ) 2 = 1/4 which yields

x A = x C -1/2 and x B = x C + 1/2 (B.4) As n x (-ŝ) = n x (ŝ), the force jumps (A.15) imply that λ A [x A -x C ] + λ B [x B -x C ] = 0. Using (B.4), we conclude that λ A = λ B (B.5)
Finally, using the global force balance (A.25), (B.3), (B.4), and (B.5), and still in the limit v 0 → 0, we obtain

f γ = λ B cos θ B (B.6)
Taking advantage of the symmetries (B.1), we now rewrite the boundary-value problem (4), ( 5), ( 6) for the interval ŝ ∈ [0, /2]. Using the external tension t, we write the x-component of the force as n x (ŝ) ≡ t, ∀ŝ ∈ [σ, /2] and using the jumps at ŝ = σ we obtain n x (ŝ) ≡ t -λ < 0, ∀ŝ ∈ (0, σ) where we note λ = λ A = λ B . We therefore have to solve

dx in /dŝ = cos θ in , dθ in /dŝ = m in , dm in /dŝ = -(λ -t) sin θ in for ŝ ∈ [0, σ] (B.7a) dx out /dŝ = cos θ out , dθ out /dŝ = m out , dm out /dŝ = -(λ -t) sin θ out for ŝ ∈ [σ, /2] (B.7b)
These are 6 dierential equations with 2 unknowns parameters λ and σ. Boundary conditions are

x in (0) = x C , θ in (0) = 0 , x in (σ) = x C + 1/2 , f γ = λ cos θ in (σ) , θ out ( /2) = 0 (B.8)
and matching conditions are

x out (σ) = x in (σ) , θ out (σ) = θ in (σ) , m out (σ) = m in (σ) (B.9)
Hence, for each given value of t, f γ , , the 8 boundary and matching conditions dene a well-posed problem for equations (B.7). For simplicity reasons, we replace the last condition in (B.8) by θ out (+∞) = 0, that is we work in the large limit. We look for a small amplitude solution to this boundary-value problem, that is we develop each variable in power of , where is a small parameter. As buckling happens through a pitchfork bifurcation, two symmetric ( > 0, where the beam is buckled upward, and < 0, where the beam is buckled downward) branches emerge from the = 0 buckling point. Taking advantage of this symmetry we introduce the following series and that t 0 is solution to the equation

f -t 0 cos √ f -t 0 2 + √ t 0 sin √ f -t 0 2 = 0 (B.18)
which is [START_REF] Klug | Three-dimensional director-eld predictions of viral DNA packing arrangements[END_REF]. At order 2 , we nd

λ 2 = 1 2 f γ sin 2 √ f -t 0 2 (B.19) σ 2 = √ f -t 0 -sin √ f -t 0 8 √ f 0 (B.20) x in 2 (ŝ) = sin 2ŝ √ f -t 0 -2 ŝ √ f -t 0 8 √ f -t 0 (B.21) x out 2 (ŝ) = sin √ f -t 0 8 √ f -t 0 - 1 8 + sin 2 √ f -t0 2 e (1-2ŝ) √ t0 -1 4 √ t 0 (B.22)
At order 3 , we nd θ in 3 (ŝ), m in 3 (ŝ), θ out (ŝ), and m out (ŝ) and from their matching conditions (B.9), we obtain

t 2 = f 2 γ (4 + 5 √ t 0 ) -f γ t 0 (2 + 3 √ t 0 ) + 2t 2 0 -2f γ f γ ( √ t 0 -2) + 4t 0 cos( √ f -t 0 ) 8f γ (2 + √ t 0 ) (B.

Figure 3 :

 3 Figure 3: Buckling curve for = 5. (Left) Curves dened by Equations (11) (12) (13). At this scale the three curves are almost indistinguishable. The asymptote t = fγ -4π 2 is shown dashed. (Right) Zoom corresponding to the rectangle shown on the Left. The approximations (12) (13) are still hard to distinguish, but are seen to deviate from the exact curve[START_REF] Lamarque | Packaging Double-Helical DNA into Viral Capsids[END_REF], shown continuous and black.

2 Figure 4 :

 24 Figure 4: Experimental verication of the windlass activation as function of the parameter fγ . The windlass mechanism is active as soon as the meniscus force fγ is greater than π 2 .

2 Figure 7 :

 27 Figure 7: Equilibrium paths for fγ = 10, 20, . . . , 50 with the vertical axis rescaled according to Equation (14). (Left) Axis-symmetric (Ax) congurations and (Right) Point-symmetric (P t) congurations. Direction of increasing fγ is indicated with the arrows.

x 1 (ŝ) + 3 θ in,out 3 ( 1 (ŝ) + 3 m in,out 3 (Figure B. 8 :

 13138 Figure B.8: Paths Ax for fγ = 20, 30, 40 and 50 with their slope at the origin given by (B.25)

  )

t = t 0 + 2 t 2 = t 0 + t 2 δ 2 δ

 22 23) We now compute the end-shortening δ = -x(s = ) = -2 [x out (ŝ = /2) -x C ], still in the limit where → +∞. Using (B.10) and (B.22) we nd δ = 2 δ 2 with (B.25) We plot in Figure B.8 paths Ax for f γ = 20, 30, 40 and 50 and the straight lines given by (B.25).

  same for point B. Note that the potential V has the dimension of an energy per unit of arc-length of the beam. For S ∈ [S A ; S B ] the rod lies inside the disk and we have χ = 1, otherwise χ = 0. The Dirac distribution δ(S) localizes meniscus forces at points A and B. The rod material has Young's modulus E and the second moment of area I = π h 4 /4. The intensities Λ A and Λ B of the meniscus forces are unknown but related to surface tension γ LV through Equation (A.25), where F γ = 2πh γ LV cos α Y with α Y being the Young-Dupré wetting angle (γ SV

the repulsion from the disk is only important for congurations in the deep post-buckling regime

Acknowledgments

The present work was supported by ANR grant ANR-09-JCJC-0022-01, ANR-14-CE07-0023-01, and ANR-13-JS09-0009. Financial support from `La Ville de Paris -Programme Émergence' is also gratefully acknowledged, along with travel support from the Royal Society, through the International Exchanges Scheme (grant IE130506) and support from the CNRS, through a PEPS-PTI grant. We thank Christine Rollard (MNHN) for helpful discussions.

Appendix A. Variational derivation of the equilibrium equations

To prevent the beam from exiting the disk elsewhere than at the meniscus points, we use a (soft wall) barrier potential [START_REF] Manning | Stability of an elastic rod buckling into a soft wall[END_REF] V (X, Y ) = V 0

where the disk has center (X C , Y C ) and radius R. The small dimensionless parameter ρ is introduced to avoid the potential to diverge at the meniscus points A and B, where the rod enters and exits the disk. The internal energy of the system comprises the bending energy E b of the rod, the barrier energy E w of the circle, and surface energy E γ :

where P = 2π h is the perimeter of the cross-section of the rod, and V 0 has the dimension of an energy per unit length. The curvatures κ i (S) are dened in each region of the rod. We add the work done by the external load T e x and obtain the potential energy of the system:

We minimize this energy under the following constraints

where

)), and V = (∂V /∂X) X + (∂V /∂Y ) Ȳ + (∂V /∂X C ) XC +(∂V /∂Y C ) ȲC . Note also that we have used (A.5) at S = L/2±Σ to eliminate several terms. Requiring (A.10) to vanish for all κi , i = 1, 2, 3, we obtain

and hence identify the Lagrange multipliers η i (S) with the bending moment M (S) in the beam. Requiring (A.10) to vanish for all θ yields, after integration by parts:

Due to the boundary conditions (A.9), part of the boundary terms vanish. Nevertheless, arbitrariness of

: the bending moment is continuous at the entry and the exit of the disk. Moreover, from the requirement that (A.12) vanishes for all θ(S), we obtain the equations for the equilibrium of the bending moment

Requiring (A.10) to vanish for all X yields, after integration by parts:

Boundary conditions (A.9) cancel part of the boundary terms, but arbitrariness of X at S = L/2 ± Σ implies

Equation (A.16) enable us to identify ν 3 and therefore ν 1 and ν 2 with the x-component, N x , of the resultant force in the beam. By extension the µ i are identied to the y-component, N y , of this force. Equations (A.15) are then seen as jumps in the x-component of the internal force due to the external force coming from the disk. Moreover, from the requirement that (A.14) vanishes for all X(S), we obtain the equilibrium equations for the x-component of the resultant force in the beam

The same procedure for the variable Y yields Equations (A.18) are then seen as jumps in the y-component of the internal force due to the external force coming from the disk, and equations (A.19) are the equilibrium equations for the y-component of the resultant force in the beam. Requiring (A.10) to vanish for all XC yields

We use the identity ∂V ∂X C = -∂V ∂X and (A.17) to obtain

The same procedure for the variable Y C yields

Considering (A.21), (A.22), (A.15), and (A.18) together yields

which means that the internal force in the beam at the entrance of the disk is equal to the internal force at the exit of the disk. We therefore have that the total external force applied on the beam by the disk is zero. Finally requiring that (A.10) vanishes for all Σ yields

In summary the equilibrium of the beam is governed by the system

Appendix B. Incipient post-buckling regime

We here focus on congurations on path Ax. With regard to the shifted arc-length variable ŝ = s -/2, introduced in Section 3, the variables have the following symmetries: