Grégoire Jauvion
email: gregoire.jauvion@gmail.com

Nicolas Grislain

Pascal Dkengne Sielenou
email: sielenou_alain@yahoo.fr

Aurélien Garivier
email: aurelien.garivier@math.univ-toulouse.fr

Sébastien Gerchinovitz
email: sebastien.gerchinovitz@math.univ-toulouse.fr

Optimization of a SSP's Header Bidding Strategy using Thompson Sampling

Keywords: Mathematics of computing → Probability and statistics, • Applied computing → Online auctions, Online Learning, Multi-armed Bandit, Thompson Sampling, Bayesian Inference, Particle Filter, Sequential Monte Carlo, Big-Data, Ad-tech, Real-time, Auctions

Over the last decade, digital media (web or app publishers) generalized the use of real time ad auctions to sell their ad spaces. Multiple auction platforms, also called Supply-Side Platforms (SSP), were created. Because of this multiplicity, publishers started to create competition between SSPs. In this setting, there are two successive auctions: a second price auction in each SSP and a secondary, first price auction, called header bidding auction, between SSPs.

In this paper, we consider an SSP competing with other SSPs for ad spaces. The SSP acts as an intermediary between an advertiser wanting to buy ad spaces and a web publisher wanting to sell its ad spaces, and needs to define a bidding strategy to be able to deliver to the advertisers as many ads as possible while spending as little as possible. The revenue optimization of this SSP can be written as a contextual bandit problem, where the context consists of the information available about the ad opportunity, such as properties of the internet user or of the ad placement.

Using classical multi-armed bandit strategies (such as the original versions of UCB and EXP3) is inefficient in this setting and yields a low convergence speed, as the arms are very correlated. In this paper we design and experiment a version of the Thompson Sampling algorithm that easily takes this correlation into account. We combine this bayesian algorithm with a particle filter, which permits to handle non-stationarity by sequentially estimating the distribution of the highest bid to beat in order to win an auction. We apply this methodology on two real auction datasets, and show that it significantly outperforms more classical approaches.

The strategy defined in this paper is being developed to be deployed on thousands of publishers worldwide.

INTRODUCTION

Real-Time Bidding (RTB) is a mechanism widely used by web publishers to sell their ad inventory through auctions happening in real time. Generally, a publisher sells its inventory through different Supply-Side Platforms (SSPs), which are intermediaries who enable advertisers to bid for ad spaces. A SSP generally runs its own auction between advertisers, and submits the result of the auction to the publisher.

There are several ways for the publisher to interact with multiple SSPs. In the typical ad selling mechanism without header bidding, called the waterfall mechanism, the SSPs sit at different priorities and are configured at different floor prices (typically the higher the priority, the higher the floor price). The ad space is sold to the SSP with the highest priority who bids a price greater than its floor price.

With header bidding, all the SSPs are called simultaneously thanks to a piece of code running in the header of the web page. Then, they compete in a first-price auction which is called the header bidding auction thereafter. In this mechanism, a SSP with a lower priority can purchase the ad if it pays more than a SSP with a higher priority. Consequently, a RTB market with header bidding is more efficient than the waterfall mechanism for the publisher.

In this paper, we take the viewpoint of a single SSP buying inventory in a RTB market with header bidding. Based on the result

SSP internal auction

Figure 1: Ad-selling process Typically some digital content will call a Supply-Side Platform (SSP) when loading, that will itself call many advertisers for bids in a real-time auction. To increase competition, some publishers have been calling several SSPs to introduce some competition among them. This setting is called header bidding because the competition among SSPs has typically been happening on the client side, in the header of HTML pages. Header bidding is, in practice, a two-staged process, with several second-price auctions happening in various SSPs, the response of which are aggregated in a final first-price auction. A SSP may be willing to adjust the bid it is responding to adapt to the first price auction context. This can be seen as an adaptative fee.

of the auction it runs internally, it submits a bid in the header bidding auction and competes with the other SSPs. This ad-selling process is summarized on Figure 1. When it wins the header bidding auction, the SSP is paid by the advertiser displaying its ad, and pays to the publisher the closing price of the header bidding auction.

We study the problem of sequentially optimizing the SSP's bids in order to maximize its revenue. Quite importantly we consider a censored setting where the SSP only observes if it has won or lost once the header bidding auction has occurred. The bids of the other SSPs are not observed. This optimization problem is formalized as a stochastic contextual bandit problem. The context is formed by the information available before the header bidding auction happens, including the result of the SSP internal auction. In each context, the highest bid among the other SSPs in the header bidding auction is modeled with a random variable and is updated in a bayesian fashion using a particle filter. Therefore, the reward (i.e., the revenue of the SSP) is stochastic. We design and experiment a version of the Thompson sampling algorithm in order to optimize bids in a sequence of auctions.

The paper is organized as follows. We discuss earlier works in Section 2. In Section 3 we formalize the optimization problem as a stochastic contextual bandit problem. We then describe our version of the Thompson sampling algorithm in Section 4. Finally, in Section 5, we present our experimental results on two real RTB auction datasets, and show that our method outperforms two more traditional bandit algorithms.

RELATED WORK

[31] provides a very clear introduction to the header bidding technology, and how it modifies the ad selling process in a RTB market.

Bid optimization has been much studied in the advertising literature. A lot of papers study the problem of optimizing an advertiser bidding strategy in a RTB market, where the advertiser wants to maximize the number of ads it buys as well as a set of performance goals while keeping its spend below a certain budget (see [START_REF] Wang | Display Advertising with Real-Time Bidding (RTB) and Behavioural Targeting[END_REF] and references therein). [START_REF] Fernandez-Tapia | Optimal Real-Time Bidding Strategies[END_REF] and [START_REF] Lee | Real Time Bid Optimization with Smooth Budget Delivery in Online Advertising[END_REF] state the problem as a control problem and derive methods to optimize the bid online. In [START_REF] Zhang | Optimal Real-time Bidding for Display Advertising[END_REF], the authors define a functional form for the bid (as a function of the impression characteristics) and write the problem as a constrained optimization problem.

The setting of an intermediary buying a good in an auction and selling it to other buyers (which is what the SSP does in our setting) has been widely studied in the auction theory literature. In [START_REF] Roger | Efficient mechanisms for bilateral trading[END_REF], the author uses the tools developed in [START_REF] Roger | Optimal Auction Design[END_REF] (one of the most well-known papers in auction theory) to derive an optimal auction design in this setting, and [START_REF] Feldman | Auctions with Intermediaries: Extended Abstract[END_REF] and [START_REF] Deng | Revenue maximization in a Bayesian double auction market[END_REF] analyze how the intermediary should behave to maximize its revenue.

[17] studies the optimal mechanism a SSP should employ for selling ads and analyzes optimal selling strategies. [START_REF] Qin | Optimizing the Revenue for Ad Exchanges in Header Bidding Advertising Markets[END_REF] analyzes the optimal behaviour of a SSP in a market with header bidding, and validates the approach on randomly generated auctions.

From an algorithmic perspective, the Thompson sampling algorithm was introduced in [START_REF] Thompson | On the Likelihood that one Unknown Probability Exceeds Another in View of the Evidence of Two Samples[END_REF]. The papers [START_REF] Kaufmann | Thompson Sampling: An Asymptotically Optimal Finite Time Analysis[END_REF][START_REF] Korda | Thompson Sampling for 1-Dimensional Exponential Family Bandits[END_REF] studied its theoretical guarantees in parametric environments, while [START_REF] Leike | Thompson Sampling is Asymptotically Optimal in General Environments[END_REF] studied it in non-parametric environments. Besides, a very clear overview of the particle filtering approach to update the posterior distribution is given in [START_REF]Sequential Monte Carlo Methods in Practice[END_REF][START_REF] Murphy | Machine Learning: A Probabilistic Perspective[END_REF].

Bandit algorithms were already designed and studied for repeated auctions, including RTB auctions. For instance, in repeated second-price auctions, [START_REF] Weed | Online learning in repeated auctions[END_REF] construct a bandit algorithm to optimize a given bidder's revenue, while [START_REF] Cesa-Bianchi | Regret minimization for reserve prices in second-price auctions[END_REF] design a bandit algorithm to optimize the seller's reserve price.

In a setting very similar to ours, [START_REF] Heidari | Pricing a low-regret seller[END_REF] study the situation where a given SSP competes with other SSPs in order to buy an ad space. They design an algorithm that provably enables the SSP to win most of the auctions while only paying a little more than the expected highest price of the other SSPs. Though the problem seems similar, our objective is different: we want the SSP to maximize its revenue, and not necessarily to win most auctions with a small extra-payment. In particular we cannot neglect the closing price of the SSP's internal auction in the optimization process.

We finally mention the work of [START_REF] Kleinberg | The value of knowing a demand curve: bounds on regret for on-line posted-price auctions[END_REF] for the online posted-price auction: for each good in a sequence of identical goods, a seller chooses and announces a price to a new buyer, who buys the good provided the price does not exceed their private valuation (see also [START_REF] Mohri | Optimal regret minimization in posted-price auctions with strategic buyers[END_REF][START_REF] Mohri | Revenue optimization against strategic buyers[END_REF] when the seller faces strategic buyers). Though their problem is different, the shape of their reward function is very similar to ours. The authors show that the classical UCB1 and Exp3 bandit algorithms applied to discretized prices are worst-case optimal under several assumptions on the sequence of the buyers' valuations. In our paper we do not tackle the worst case and instead use prior knowledge on the ad auction datasets (i.e., an empiricallyvalidated parametric model) to better optimize the SSP's revenue.

PROBLEM STATEMENT 3.1 RTB market

We represent the RTB market as an infinite sequence D of timeordered impressions 1, . . . , n, . . . happening at times t 1 , . . . , t n , . . .. We note D t the sequence of impressions happening before time t (including t).

Impression i happening at time t i is characterized by a context c i , which summarizes all the information relative to impression i that is available before the header bidding auction starts. It may contain the ad placement (where it is located on the web page), some properties of the internet user (for example its operating system), or the time of the day. An important variable of the context which is specific to our setting is the closing price of the SSP internal auction, which is known before the header bidding auction happens.

We assume that the context is categorical with a finite number of categories C. A continuous variable can be discretized to meet this assumption. Without loss of generality, we assume that the categories are 1, . . . , c, . . . , C. We note D t,c the subsequence of D t containing all impressions i such that c i = c.

Ad selling process with header bidding

We assume that S SSPs: S 1 , . . . , S S compete in the header bidding auctions (possibly bidding 0 if they are not interested in purchasing the ad). We note b i,s the bid of S s in the header bidding auction for impression i. As the header bidding auction is a first-price auction, its closing price is max s (b i,s ).

From now on, we consider the problem from S 1 standpoint. We note q i = b i,1 the bid submitted by S 1 in the header bidding auction, which is the variable to optimize. We also write x i = max(b i,2 , . . . , b i,S ), which is the highest bid among the other SSPs.

In each impression i, we assume that S 1 runs an internal auction between advertisers, whose closing price is denoted p i . p i is the amount paid by the advertiser winning the internal auction to S 1 should S 1 win the header bidding auction. Note that we do not need to know the detailed internal auction mechanism but only its closing price.

Before header-bidding, a SSP would run a second-price auction with an advertiser bidding $10 and closing at p i = $8. Then the SSP would respond q i = p ifees = $6 to the publisher. In this context, the advertiser pays $8, the publisher receives $6 and the SSP gets its fees: $2. In a header bidding context, the SSP is in competition with other SSPs in a first price auction, it may lose an opportunity by taking too much fees or pay too much if it is sure to win and take too little fees.

Revenue function for the SSP S 1

The revenue function R i (.) of S 1 at impression i can be written as R i (q) = 1 q ≥x i (p i -q). Indeed:

• When q ≥ x i , S 1 wins the header bidding auction. It is paid p i by the advertiser winning the internal auction, and it pays q to the publisher. • Otherwise, S 1 does not display any ad and gets no revenue in the auction.

In Figure 2 we plot S 1 's revenue as a function of its bid q, for two sets of values for the closing price p of the internal auction and the highest bid x among the other SSPs.

Note that in the setting described here, we ignore some factors having an impact on S 1 's revenue. Indeed S 1 may charge a fee to the advertiser in addition to the closing price of the internal auction it runs. Also, the cost of running the internal auction may lower S 1 's revenue. These factors would impact the revenue function but the strategy described in this paper would remain applicable.

Optimization problem statement

Before the header bidding auction for impression i happens, the value x i of the highest bid among the other SSPs is unknown and is modeled with the random variable X i . Thus, the revenue optimization problem over n impressions can be expressed as follows:

max q 1 , ...,q n E n i=1 1 q i ≥X i (p i -q i )] = max q 1 , ...,q n C c=1 i ∈D tn ,c E[1 q i ≥X i (p i -q i )] , (1)
where the maximum is over the prices q 1 , . . . , q n that the SSP can choose as a function of the past observations.

It would be tempting to model the variables X i as independent and identically distributed within any context c, with an unknown distribution ϕ c . Under this assumption, the task presented here boils down to a contextual stochastic bandit problem. A closer look at the data, however, shows that there are significant non-stationarities in time. We explain below that our final model does address this issue, by the use of a particle filter within the bandit algorithm.

We emphasize that, after the header bidding auction for impression i has occurred, S 1 does not observe the value of the bid x i , but only observes if it has won or lost the header bidding auction, i.e., 1 q i ≥x i . This censorship issue must be tackled in the optimization methodology.

REVENUE OPTIMIZATION USING THOMPSON SAMPLING

In this section we present a method to sequentially optimize the bids q i . It combines the Thompson sampling algorithm with a parametric model for the distributions ϕ c (recall that ϕ c is the distribution of the other SSPs' highest bids X i within context c). Note that all the contexts c are modeled independently.

Parametric estimation of ϕ c

We introduce f θ a family of distributions parametrized with θ , and we note F θ the corresponding cumulative density functions. For each context c, we assume that the distribution ϕ c of the other SSPs' highest bids X i belongs to the family f θ ; let θ c be such that

ϕ c = f θ c .
According to the Thompson sampling method, we fix a prior distribution π c,0 (θ ) over θ c . Then, for all t, we consider the posterior distribution π c,t (θ ) given all the observations available at the end of the t-th auction, i.e., the censored observations

1 q i ≥x i for i ∈ D t,c .
The Bayes rule yields the following expression for π c,t :

π c,t (θ ) ∝ π c,0 (θ ) i ∈ D t,c F θ (q i )1 x i ≤q i + (1 -F θ (q i ))1 x i >q i (2)

Overview of the methodology

In our model the Thompson sampling algorithm unfolds as follows: before any impression i,

• Sample a value θ from the posterior distribution π c i ,t i -1 ;

• Compute the bid q i that would maximize the SSP's expected revenue if X i ∼ f θ (see below); • Observe the auction outcome 1 q i ≥x i and update the posterior π c i ,t i . As the particle filter provides a discrete approximation of the posterior distribution, the sampling step is straightforward. The optimization of the bid q i is a one-dimensional optimization problem: when X i ∼ f θ , the maximal SSP expected revenue is max q

(p i -q)F θ (q) .
There is no closed form solution in general, but this problem can be solved numerically for example by using Newton's method.

The difficult step of the algorithm is the update of the posterior, which is explained in the next section.

Updating the posterior distribution

It would be difficult to sample directly from the posterior distribution π c,t , which does not have a simple or tractable form. Even the use of MCMC methods like Metropolis-Hastings would be hazardous, since computing the density of the posterior distribution has a linear cost in the number of past observations which is huge in advertising 1 .

To overcome these difficulties, we approximate the posterior distribution with a particle filter, a powerful sequential Monte-Carlo method for Hidden Markov Models (HMM). For an introduction on HMM and particle filtering, we refer to [START_REF] Cappé | Inference in Hidden Markov Models[END_REF]. The basic idea of a particle filter is to approximate the sequence of posterior distributions by a sequence of discrete probability distributions which are derived from one another by an evolution procedure (which may include a selection step). The posterior distribution π c,t is estimated by a discrete distribution on K points called particles. The particles are denoted by (θ c,1,t , . . . , θ c, K,t ) and their respective weights by (w c,1,t , . . . , w c,K,t ). The evolution procedure and the selection step we use are described below.

A very important strength of the particle filter approach is that it allows to handle non-stationarity: the HMM model encompasses the possibility that the hidden variable (here, the unknown parameter θ ) evolves in time according to a Markovian dynamic of kernel p(θ ′ |θ ), thus forming an unobserved sequence (θ t ) t . We use this possibility by assuming that the parameter θ t is equal to θ t -1 plus a small step in an unknown direction: this permits to handle parameter drift directly inside of the model.

The theory of particle filters for general state space HMM [START_REF] Crisan | Convergence of Sequential Monte Carlo Methods[END_REF][START_REF] Crisan | A Survey of Convergence Results on Particle Filtering Methods for Practitioners[END_REF][START_REF] Douc | Sequential Monte Carlo smoothing for general state space hidden Markov models[END_REF][START_REF]Sequential Monte Carlo Methods in Practice[END_REF] suggests that, in cases such as ours, the particle approximations converge to the true posterior distributions of the parameter θ when the number of particles tends to infinity.

Evolution

: updating the distribution. Recall that we run C independent instances of Thompson Sampling, one for each context c. Next we focus on one context c and recall how to update the particle distribution in the particle filter. To simplify the notation, we write t -1 and t for the times of two consecutive impressions within context c, even if other contexts appeared in between.

The update consists of two steps. First the particles θ c,k,t are sampled from a proposal distribution q(θ c,k,t |θ c,k,t -1 , 1 q t ≥x t ). We then compute new unnormalized weights ŵc,k,t by importance sampling:

ŵc,k,t = ŵc,k,t-1 × F θ c, k, t (q t )1 x t ≤q t + (1 -F θ c,k, t (q t ))1 x t >q t × p(θ c,k,t |θ c,k,t -1 ) q(θ c,k,t |θ c,k,t -1 , 1 q t ≥x t ) , (3)
where p(θ ′ |θ ) is the transition kernel of the hidden process. Here, we may simply take the proposal distribution q(θ c,k,t |θ c,k,t -1 , 1 q t ≥x t ) to be equal to the transition distribution p(θ c,k,t |θ c,k,t -1 ), which yields:

ŵc,k,t = ŵc,k,t-1 × F θ c, k, t (q t )1 x t ≤q t + (1 -F θ c, k, t (q t ))1 x t >q t . (4)
The normalized weights w c,k,t can be computed as:

w c,k,t = ŵc,k,t K k ′ =1 ŵc,k ′ ,t .
4.3.2 Selection: resampling step. The basic update described previously generally fails after a few steps because of a well-known and general problem: weight degeneracy. Indeed, most of the particles soon get a negligible probability, and the discrete approximation becomes very poor. A standard strategy used to tackle this issue is the use of a resampling step when the degree of degeneracy is considered to be too high. We use the following methodology given in [START_REF] Murphy | Machine Learning: A Probabilistic Perspective[END_REF] for resampling:

• Compute S = K k =1 w 2 c,k,t
-1 to quantify the degree of degeneracy of the particle filter • If S < S min (S min is a hyperparameter of the particle filter), resample all the particles by sampling K times with replacement the current set of weighted particles θ c,1,t , . . . , θ c,K,t . The result is an unweighted sample of K particles, so we set the new weights to ŵc,k,t = 1 K . There exist some alternative resampling schemes that could be used: see [START_REF] Douc | Sequential Monte Carlo smoothing for general state space hidden Markov models[END_REF] for a presentation of some of them, and for a discussion on their convergence properties and computation cost.

Time and space complexities. Recall that K is the number of particles and that C is the number of contexts. After each new impression i, since i only falls into one context c, the evolution and selection steps described above need only be carried out for this particular c. This thus only requires O(K) elementary operations per impression (including calls to the cumulative distribution function F θ (x)). As for space complexity, a direct upper bound is O(CK) since we need to store weight vectors for each context c = 1, . . . , C.

Implementation of Thompson sampling

We may now detail our modelling and algorithmic choices for the particle filter within the Thompson sampling algorithm.

Distribution of the highest bids x i . We model the highest bids x i among the other SSPs with a lognormal distribution, a standard choice in econometrics or finance. Lognormal distributions are parametrized by θ = θ (1) , θ (2) , where θ (1) = σ > 0 and θ (2) = µ ∈ R. Here, µ and σ are respectively location and scale parameters for the normally distributed logarithm ln(x i ).

Particle filter. We write θ c for the parameters of the lognormal distribution associated with context c. The particle filter for the posterior distributions works as follows:

(1) In order to handle non-stationarity, we model the parameters θ c by Markov chains θ c,t such that log θ

c,k,t . (3) As explained above, the particles θ c,k evolve at step t according to the same dynamic as the unobserved parameters θ c,t : log θ

(1) c,k,t = log θ (1) c,k,t -1 + N (0, ϵ = 0.005) and θ (2) c,k,t = θ (2)
c,k,t -1 + N (0, ϵ = 0.005). ( 4) We use a uniform distribution as prior π c,k,0 (θ ) for the parameter θ c,0 , and thus uniformly generate the components of the initial particle θ c,k,0 = θ

(1) c,k,0 , θ (2)
c,k,0 . Because of the high number of auctions in each context, the choice of the prior distribution π c,k,0 (θ ) has little impact on the result, as long as its support contains the parameter θ c . (5) Finally, we choose S min = K/2 as a resampling threshold criterion.

EXPERIMENTS ON RTB AUCTIONS DATASETS 5.1 Constrution of the datasets

In practice, the SSPs generally do not share their bids with one another, and we do not have a dataset with the bids from all SSPs in header bidding auctions. The datasets we have used in these experiments give, for two web publishers, the bids as well as the names of the advertisers in RTB auctions run by a particular SSP over one week, in a setting without header bidding.

For these two web publishers, a dataset giving both the bids in S 1 internal auction and the bids from other SSPs in the header bidding auction has been artificially built the following way:

• All the advertisers competing in the RTB auctions (typically a few dozens) have been randomly assigned to one of two groups of advertisers named A and B • In each auction, the bids coming from advertisers in the group A are supposed to be the bids of the internal auction run by the SSP S 1 , and the bids coming from advertisers in the group B are supposed to be the bids coming from the other SSPs in the header bidding auction • Hence, in a given auction i, the closing price of the internal auction p i is given by the second highest bid from advertisers in the group A, and the highest bid among other SSPs x i is given by the highest bid from advertisers in the group B • The auctions where there are less than two bids from advertisers in the group A or less than one bid from advertisers in the group B have been removed from the dataset These two datasets are named P 1 and P 2 thereafter. A brief description is given in Table 1. We give the share of auctions where x i ≤ p i , which is the share of auctions where the SSP S 1 could have won the header bidding auction while generating a positive revenue, by choosing

q i ∈ [x i , p i ].
The experiments have been performed in the two following configurations:

• Stationary environment: the data is shuffled. This configuration is used to evaluate the strategy in a stationary environment • Non-stationary environment: the data is sorted in chronological order. In this case, the data is non-stationary, as the bids highly depend on the time of the day. This configuration is used to evaluate the strategy in a non-stationary environment Note that all the bids have been multiplied by a constant.

Definition of the contexts

In the experiments, we define the context in auction i by the closing price of S 1 internal auction p i . The closing price p i is transformed into a categorical context by discretizing it into C disjoint bins.

The l-th bin contains all auctions where p i ∈ q( l -1 C ), q( l C ) , where q is the empirical quantile function of the closing prices (p i ) estimated on the data. Consequently, each one of the C contexts contains approximately the same number of auctions.

The number of contexts should be chosen carefully. A high number of contexts enables to model more precisely the distribution of the highest bid among other SSPs, which is modeled independently on each context, at the price of a slower convergence. In the experiments, we have chosen C = 100 which yields a good performance on the datasets.

Baseline strategies

We define in this section the baseline strategies used to assess the quality of the Thompson sampling strategy. They correspond to the use of classical multi-armed bandit (MAB) models [START_REF] Cesa | Prediction, Learning, and Games[END_REF]. Each arm j = 1, . . . , J corresponds to a coefficient α (j) = j J applied to the closing price of the internal auction p i to obtain the bid of the SSP S 1 , q i = α (j) • p i . Note that this strategy implies that q i ≤ p i , as the revenue for the SSP S 1 can not be positive when q i > p i .

In each auction i, the SSP S 1 chooses an arm j(i) and bids q i = α j(i) • p i . Then, it receives a reward equal to 1 q i ≥x i (p i -q i ), and the rewards associated to the other arms are unknown.

The goal of the SSP is to maximise their expected cumulative reward. In the MAB literature, this reward maximisation is typically defined via the minimisation of the equivalent measure of cumulative regret. The regret is the difference between the cumulative rewards of the SSP S 1 and the one that could be acquired by a policy assumed to be optimal. In our case, the optimal policy (or the oracle strategy) consists in playing for each auction i the price

q i = x i 1 {x i ≤p i } .
We consider two baseline strategies, corresponding to two distinct state-of-the-art policies:

• the Upper Confidence Bound (UCB) policy [START_REF] Auer | Finite-time Analysis of the Multiarmed Bandit Problem[END_REF][START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF]. Under the assumption that the rewards of each arm are independent, identically distributed, and bounded, the UCB policy achieves an order-optimal upper bound on the cumulative regret; • the Exponential-weight algorithm for Exploration and Exploitation (Exp3) policy [START_REF] Auer | The Nonstochastic Multiarmed Bandit Problem[END_REF][START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF]. Without any assumption on the possibly non-stationary sequence of rewards (except for boundedness), the Exp3 policy achieves a worst-case orderoptimal upper bound on the cumulative regret. The number of arms J has a high impact on the performance of these baseline strategies. A high number of arms makes the discretization of the coefficient applied to the bid p i very precise, but slows the convergence as the average reward for each arm is learnt independently. We have used J = 100 in the experiments.

Evaluation of the Thompson sampling strategy

This section compares the performance of the Thompson sampling strategy (TS) defined in Sections 4 and 4.4 with the performance of the two baseline strategies (UCB and Exp3) introduced in Section 5.3 on the datasets P 1 and P 2 .

The performance of a strategy after n auctions is measured with the average reward:

1 n n i=1 1 q i ≥x i (p i -q i ) .
Figures 3-4 plot the average reward as a function of n on dataset P 1 , in a stationary environment (i.e. on the shuffled dataset) and in a non-stationary environment (i.e. on the ordered dataset). Figures 56plot the same results on dataset P 2 .

The TS strategy clearly outperforms the baseline strategies EXP3 and UCB in both stationary and non-stationary environments. Moreover, one can observe that the convergence of the TS strategy is faster than that of the EXP3 and the UCB strategies. This convergence speed is expressed in terms of the smallest number of auctions needed by the strategy to reach the overall average reward on the whole dataset.

On the dataset P 1 , the average reward with TS strategy is 2.0888 for the stationary case and 2.0937 for the non-stationary case. The corresponding success rates (i.e. the share of auctions won n -1 n i=1 1 q i ≥x i ) are 32.19% and 32.09% respectively. On the dataset P 2 , the average reward with TS strategy is 2.0312 for the stationary case and 2.0342 for the non-stationary case. The corresponding success rates are 29.36% and 29.10% respectively.

Advantages of the Thompson sampling strategy

The main advantage of the Thompson sampling strategy introduced in this paper is that it relies on a random modeling of the highest bid among other SSPs x i , which is the unknown variable. Then, the revenue function of the problem is introduced explicitly to determine an optimal bid in each auction. In the strategies EXP3 and UCB, the rewards corresponding to each arm are learnt independently whereas they are highly correlated because they derive from a common revenue function.

In addition, as argued above, the use of a particle filter within Thompson sampling permits to handle elegantly a parameter drift, a problem which is still under investigation for classical bandit algorithms. We ran experiments using the non-stationary bandits algorithms of [START_REF] Garivier | On Upper-Confidence Bound Policies for Switching Bandit Problems[END_REF], but the results were not better than plain UCB strategies. In contrast, the algorithm proposed above significantly outperforms the classical approaches.

The price for this improvement is an increased computational cost (proportional to the number of particles), and the presence of an additional parameter ϵ which controls the intensity of the drift. It must be chosen so as to reach a good tradeoff between accuracy of the discrete approximation and the adaptation to the parameter drift. Experiments show, however, that even a very rough choice of ϵ does lead to good performance, and that over-estimating the drift intensity has little impact.

Discussion on the parameters of the

Thompson sampling strategy 5.6.1 Choice of the contexts. As precised in Section 5.2, the number of contexts has a high impact on the performance of the strategy and should be chosen carefully.

In the experiments presented in this paper, we have defined the context as the closing price of the internal auction run by the SSP S 1 . This definition of the context is intuitively a good choice, as the result of the internal auction measures the value of the ad space being sold according to the advertisers bidding in this auction. This value is probably highly correlated with the bids of other SSPs for this ad space.

The definition of the contexts could be improved by using characteristics of the ad placement or of the internet user. Experiments show that defining the context as the ad placement does not improve the results. 5.6.2 Choice of the parametric distribution. We chose the lognormal distribution to model the highest bid x i among the other SSPs both because it is frequently used in practice for online auctions and it fitted our datasets reasonably well. However, when the number of other SSPs is sufficiently large, using the generalized extreme value distributions or the generalized Pareto distributions [START_REF] Coles | An introduction to statistical modeling of extreme values[END_REF][START_REF] Embrechts | Modelling Extremal Events for Insurance and Finance[END_REF] might be more relevant.

Some preliminary studies we conducted show that Fréchet distributions fit well the sample maxima of the bids x i within each context. The reason is that such probability distributions are stable and relevant to model and to track the extreme values (sample maxima or peaks over threshold) of independent and identically distributed random variables, whatever the behavior of their tail distributions. In such situations, the associated Thompson sampling strategy could yield even higher cumulative revenues. 5.6.3 Computation time. We have measured the running time (the CPU response time) of the TS strategy using standard computer (µP 2.8GHz, RAM 8GB). Updating the full distribution model and estimating the optimal price q i for an auction i requires about 0.14ms. This running time is below the limit of 1ms at which the optimal price must be decided.

Note that the running time is strongly related to the parametric probability distribution modeling the highest bid among other SSPs x i and to the number of particles K used to approximate the corresponding posterior distributions.

CONCLUSION AND FUTURE WORK

We have formalized the problem of optimizing the sequence of bids of a given SSP as a contextual stochastic bandit problem. This problem is tackled using the Thompson sampling algorithm, which relies on a bayesian parametric estimation of the distribution of the highest bid among other SSPs. The distribution of the highest bid among other SSPs is approximated with a particle filtering approach. It provides a very efficient way to sequentially update the distribution and sample from it to apply the Thompson sampling algorithm.

The results obtained on datasets artificially built from real RTB auctions show that the Thompson sampling strategy outperforms other bandit approaches for this problem. Also, the estimation of the optimal bid for each impression is fast enough and the strategy can be used in real conditions where a bid prediction must be performed in a few milliseconds. This strategy is currently being developed to be deployed on thousands of web publishers worldwide.

The particle filtering models naturally the non-stationarity of the bid distributions through the hypothesis p(θ c,k,t |θ c,k,t -1 ). This hypothesis should be linked to the non-stationarity of the distributions, as decreasing its standard deviation (named ϵ in the paper) enables to forget past observations faster.

In the approach described here, the contexts are modeled independently. The learning speed of the algorithm could be increased by taking into account the correlations between the contexts. In particular, these correlations may be very high when the context is defined by a continuous variable. This point may lead to improvements in the strategy.

Finally, we are planning to explore further how the performance of the strategy depends on the parametric distribution used to model the highest bid among other SSPs x i .

Aknowledgment: This work was partially funded by the French Government under the grant <ANR-13-CORD-0020> (ALICIA Project).

Figure 2 :

 2 Figure 2: S 1 revenue as a function of its bid q

( 2 )

 2 c,t -1 +E 2 , where E 1 , E 2 ∼ N (0, ϵ = 0.005) are independent Gaussian variables with mean 0 and standard deviation ϵ. (2) At each time t, for each context c ∈ {1, . . . , C = 100}, we use K = 100 particles θ c,k,t = θ (1) c,k,t , θ

Figure 3 :

 3 Figure 3: Evolution of the average rewards of TS, UCB, and Exp3 for dataset P1 (stationary environment).

Figure 4 :

 4 Figure 4: Evolution of the average rewards of TS, UCB, and Exp3 for dataset P1 (non-stationary environment).

Figure 5 :

 5 Figure 5: Evolution of the average rewards of TS, UCB, and Exp3 for dataset P2 (stationary environment).

Figure 6 :

 6 Figure 6: Evolution of the average rewards of TS, UCB, and Exp3 for dataset P2 (non-stationary environment)

Table 1 :

 1 Some properties of the datasets P 1 and P 2 .

	P 1	P 2

Indeed, the profile of the payoff function induces a posterior distribution that cannot be simplified. Hence, computing the posterior density exactly, cannot be done better than by computing the product of all bayesian updates, which in practice is intractable and rules-out MCMC sampling.


Artem Melnyk

Alexandre Pitti
email: alexandre.pitti@u-cergy.fr

Synergistic control of a multi-segments vertebral column robot based on tensegrity for postural balance

Keywords: Motor synergies, central pattern generators, tensegrity, vertebral column, postural balance, phase synchronization, soft robotics, feedback resonance, biological robotics

We present a neuronal architecture to control a compliant robotic model of the human vertebral column for postural balance. The robotic structure is designed using the principle of tensegrity that ensures to be lightweight, auto-replicative with multi-degrees of freedom, flexible and also robust to perturbations. We model the central pattern generators of the spinal cords with a network of nonlinear Kuramoto oscillators coupled internally and externally to the structure and error-driven by a proportional derivative (PD) controller using an accelerometer for feedback. This coupling between the two controllers is original and we show it serves to generate controlled rhythmical patterns. We observe for certain coupling parameters some intervals of synchronization and of resonance of the neural units to the tensile structure to permit smooth control and balance. We show that the top-down PD control of the oscillators flexibly absorbs external shocks proportionally to the perturbation and converges to steady state behaviors. We discuss then about our neural architecture to model motor synergies for compliance control and also about tensegrity structures for soft robotics. The 3D printed model is provided as well as a movie at the address https://sites.google.com/site/embodiedai/current-research/tensegrityrobots.

Introduction

Animal's musculoskeletal system is based on a com-Q1 plex network of muscles, bones, nerves, tissues, and soft bodies which are hard to replicate accurately in robots [START_REF] Pfeifer | Self-organization, embodiment, and biologically inspired robotics[END_REF][START_REF] Mcevoy | Materials that couple sensing, actuation, computation, and communication[END_REF]. This dense architecture is however well ordered so that the control done in the nervous system can realize easily exible sensorimotor coordination at a very low energy cost with the dynamical grouping of the muscles known as motor synergies [START_REF] Bernstein | The coordination and regulation of movements[END_REF][START_REF] Todorov | Optimality principles in sensorimotor control[END_REF][START_REF] Bizzi | Modular organization of motor behavior in the frog's spinal cord[END_REF]. Nonetheless, in order to exploit fully the body structure, the nervous system has to organize itself exibly and complementarily [START_REF] Kelso | Dynamic patterns: The self-organization of brain and behavior[END_REF][START_REF] Kelso | Synergetics of brain and behavior. In What is Life? The Next Fifty Years[END_REF][START_REF] Bardy | The dynamics of human postural transitions[END_REF]. For instance, the well distribution of stress and strain throughout the body warranties its ecological control so that when we are exposed to a violent shock, we can still stand or bend our knees or sti en (or soften) our body and joints with a small amount of control, just as a building would absorb an earthquake wave and balance itself, or as a bridge would lean into the wind. In comparison, current robots are still di cult to design and to control in order to achieve robust postural balance under external perturbations and dynamic motion.

In this paper, we propose to take inspiration of both (1) the human musculoskeletal system of the dorsal spine and (2) the neural architecture at the spinal cords level to realize a multi-degrees of freedom vertebral column robot [START_REF] Ly | Bio-inspired vertebral column, compliance and semi-passive dynamics in a lightweight robot[END_REF][START_REF] Nakajima | A soft body as a reservoir: case studies in a dynamic model of octopus-inspired soft robotic arm[END_REF][START_REF] Zhao | Spine as an engine: e ect of spine morphology on spine-driven quadruped locomotion[END_REF][START_REF] Wei | The e ect of spine on the bounding dynamic performance of legged system[END_REF] and its neural controller in order to cope with external perturbations. Our rst contribution is on the one hand on the design of an original neural controller composed of a proportional derivative (PD) controller and nonlinear oscillators in order to generate controlled rhythmical patterns and convergence to steady state behaviors. Our second contribution is on the other hand on the design of a novel vertebral column robot constituted of connected auto-replicative tensegrity elements [START_REF] Flemons | The bones of tensegrity[END_REF] mounted vertically as a multi-segment inverted pendulum with soft links. To our knowledge, this coupling between a PD controller and nonlinear oscillators to control synchronization as a minimization process was never presented before.

We model the central pattern generators (CPGs) of the spinal cords with a network of nonlinear Kuramoto oscillators coupled internally and externally to the structure and error-driven by a PD controller using an accelerometer for feedback. We suggest that our proposed neural controller, although simple, is similar to the role played by the neuromodulators in the spinal cord that modulate the gain of the sensory feedback on the alpha-motor neurons activity to generate the desired synergy [START_REF] Feclarac | Motor systems[END_REF][START_REF] Marder | Principles of rhythmic motor pattern production[END_REF][START_REF] Calabrese | Oscillation in motor pattern-generating networks[END_REF]; which means selecting the most expected resonant modes relative to the perturbation. In line with [START_REF] Bardy | The dynamics of human postural transitions[END_REF][START_REF] Bardy | Postural coordination modes considered as emergent phenomena[END_REF], we consider postural coordination modes as emergent phenomena giving rise to non-linearity properties such as phase transition, multistability and hysteresis [START_REF] Bonnet | A structurally optimal control model for predicting and analyzing human postural coordination[END_REF].

The paper is organized as follows. In Section 2, we present rst our motivation for the design of a tensile structure. In Section 3, we describe then its assembling with replicated 3D printed elements, its motors and sensors used in order to replicate the tendon-driven mechanism and control of the human upper-body. We present the neural oscillators used to model the so-called CPGs and the feedback-driven PD control used to model the neuromodulators. Tested in passive and active conditions, the multi-DOF tensile structure shows a large spectrum of behaviors from very soft dynamics capable to generate rhythmical oscillations to very rigid static postures capable to handle its own weight in every posture.

In Section 4, we propose four experiments to display the capabilities of our framework. In the rst setup, we de ne the dynamics in open-loop control for various modes of coordination by varying the phase and the duration of a pulse-width modulation (PWM) control and by analyzing the resonant frequencies of the system and its rhythmical patterns. In the second experiment, we analyze the system statically from a postural viewpoint and study its robustness in the upward position. In the third experiment, we propose to exploit error feedback for closed-loop control of the structure using CPGs [START_REF] Taga | A model of the neuro-musculo-skeletal system for human locomotion. i. emergence of basic gait[END_REF]. Depending on the values of the internal and external coupling parameters, we can synchronize nonlinear oscillators modeled with Kuramoto units to the resonant modes of the structure and entrain it freely to speci c directions. These privileged modes of synchrony represent the natural motor synergies that are possible to generate and control in the multi-segmented structure [START_REF] Der | Learning to feel the physics of a body[END_REF].

In the fourth experiment, we employ a top-down mechanism, a PD controller, that controls the amplitude level of the oscillators in order to absorb the external perturbations gradually on the vertebral structure so that it can return back to its resting upward posture. Depending on the strength of external perturbation, the controller will set the oscillators to a certain regime producing big oscillations till recovery in order to absorb the shock. In reverse, for tiny perturbations, the controller will set the oscillators to a di erent regime that can dampen the perturbations.

We discuss then the interest of our mechanical design and of our neural network for controlling soft robots as well as the links to human motor synergies.

State of art and motivation

One architectural design that explains well biomechanical compliance is tensegrity structures [START_REF] Fuller | Synergetics: Explorations in the geometry of thinking[END_REF][START_REF] Snelson | Continuous tension, discontinuous compression structures[END_REF]. Tensegrity structures can be seen as physical networks of stress and loads so that they have an inner stress and plasticity in their structure that make them resilient, adaptive and robust to some external loads. In comparison to most robotic designs, they do not follow Newton's law for rigid bodies as they have no joints and no momentum or torque since the motors are not on the axis of articulation. Instead, they follow Hooke's law for elastic bodies. These features make them a promising paradigm for integrating structure and control design [START_REF] Paul | Design and control of tensegrity robots for locomotion[END_REF][START_REF] Bliss | Experimental validation of robust resonance entrainment for cpg-controlled tensegrity structures[END_REF][START_REF] Tietz | Tetraspine: Robust terrain handling on a tensegrity robot using central pattern generators[END_REF]. For instance, we can easily formalize a tensegrity system as a network of tension (muscles and soft tissues) and compression (bones), or as a network of springs and masses [START_REF] Hauser | Towards a theoretical foundation for morphological computation with compliant bodies[END_REF][START_REF] Hauser | The role of feedback in morphological computation with compliant bodies[END_REF]. Therefore, they can be viewed as complex dynamical systems with many degrees of freedom [START_REF] Nakajima | A soft body as a reservoir: case studies in a dynamic model of octopus-inspired soft robotic arm[END_REF][START_REF] Caluwaerts | Design and control of compliant tensegrity robots through simulation and hardware validation[END_REF][START_REF] Pitti | Quanti cation of emergent behaviors induced by feedback resonance of chaos[END_REF], which is a property often seen in biological systems [START_REF] Ingber | Tensegrity, cellular biophysics, and the mechanics of living systems[END_REF][START_REF] Turvey | The medium of haptic perception: a tensegrity hypothesis[END_REF][START_REF] Levin | The tensegrity-truss as a model for spine mechanics: biotensegrity[END_REF].

The redundancy and nonlinearity within such dynamical system might be considered at rst as an obstacle to control, however, the symmetries of the overall structure and the many resonant modes generated can serve to decrease the dimensionality of the control problem. For instance, one way to have an adaptive control is to exploit phase synchronization of these modes similar to coupled chaotic maps [START_REF] Kelso | Synergetics of brain and behavior. In What is Life? The Next Fifty Years[END_REF][START_REF] Strogatz | Sync: the emerging science of spontaneous order[END_REF].

In human control, this work is achieved by the CPGs at the spinal cord level, which are primitives that control the muscle grouping for general motion behaviors [START_REF] Feclarac | Motor systems[END_REF][START_REF] Bizzi | Combining modules for movement[END_REF]. When we are standing upward, for instance, groups of muscles are dynamically selected to contribute to our stability depending on the error perturbation level and the force direction [START_REF] Ting | Dimensional reduction in sensorimotor systems: a framework for understanding muscle coordination of posture[END_REF][START_REF] Allen | Why is neuromechanical modeling of balance and locomotion so hard? Chapter 7[END_REF]. In robotics, such bioinspired control is still di cult to model when we design a compliant body with many degrees of freedom and nonlinearities. In previous works, we have shown how we can control such high degrees-of-freedom system with chaotic controllers that sync dynamically to the resonant frequencies of several robotic devices [START_REF] Pitti | Quanti cation of emergent behaviors induced by feedback resonance of chaos[END_REF][START_REF] Pitti | Exploration of natural dynamics through resonance and chaos[END_REF][START_REF] Pitti | Generating spatiotemporal joint torque patterns from dynamical synchronization of distributed pattern generators[END_REF][START_REF] Pitti | Creating and modulating rhythms by controlling the physics of the body[END_REF] and to human partners [START_REF] Melnyk | Bio-inspired plastic controller for a robot arm to shake hand with human[END_REF]. We believe that this type of control conveys some important features of the human musculoskeletal system control as done in the spinal cord by the CPGs [START_REF] Bizzi | Combining modules for movement[END_REF][START_REF] Nakanishi | Learning attractor landscapes for learning motor primitives[END_REF][START_REF] Ijspeert | Central pattern generators for locomotion control in animals and robots: a review[END_REF].

Material and methods

We present a tensegrity structure based on autoreplicative elements, 3D printed and similar to the ones proposed in [START_REF] Flemons | The bones of tensegrity[END_REF][START_REF] Frumar | Tensegrity structures with 3d compressed components: development, assembly and design[END_REF], see Figure 1(a,b). This particular (a-c) Each element forms a tetrahedron by its four edges, which ensures the whole compliance and tension distribution in the three directions when connected to other elements in line. (d) An Inertial Measurement Unit (IMU) is placed at the end of the structure for position control and acceleration feedback. We provide the design of the replicative element freely at the address [START_REF]Tinkercad[END_REF].

motif reproduces the very stable structure of the tetrahedron (i.e. the pyramids) which can stand easily upward, see Figure 1(c,d). When two structures are assembled as two inverted pyramids, the coupled unit structure can move in two directions and can support small sheer torsions as well in the third direction, which is ideal for modeling the human's rotational joints.

In comparison to other types of tensegrity motives, this one has the advantage to require fewer structures and few junctions part. Each element is connected to others with springs, which confers to the design some viscoelastic properties comparable to pre-stressed structures. The tensile elements possess a stable con guration that returns even after applying some external force pressure (self-stabilisation). The whole structure has 10 elements connected with spherical joints (ping-pong balls), which models well the excentric rotations of bones articulation. The vertebral column measures around 1-meter height; and each element is occupying a volume of 11 centimeters cube. The system can be viewed as a threedimensional version of mass-spring dampers mounted in series. The total weight of the robot vertebrae is under 800 g, counting the weight of the motors (25 g each) and of each element (30 g), which is very light concerning its size.

Conception. We display in Figure 2 the prototyping of the tensegrity model with motors inserted and springs attached. A better understanding of which part of the robot each motor actuates is provided further in the Muscle-Tendon section Figure 3. To show the properties of compliance and postural stability of the structure, we co-contract the motors and set its neutral postural con guration respectively in the horizontal plane and in upward tension, so that the structure has a maximum momentum and tension on its morphology horizontally and has to exploit its physics fully to stand vertically; see resp. Figure 2(a-c). The balanced forces distribution of each motor-driven cables on the whole structure makes it stabilized in every position, even for the less energetical ones as the horizontal plane or the vertical plane, which are also di cult for humans who develop di erent strategies to support their own postural balance [START_REF] Bonnet | A structurally optimal control model for predicting and analyzing human postural coordination[END_REF][START_REF] Turvey | The medium of haptic perception: a tensegrity hypothesis[END_REF][START_REF] Allen | Why is neuromechanical modeling of balance and locomotion so hard? Chapter 7[END_REF][START_REF] Bardy | On perturbation and pattern co-existence in postural coordination dynamics[END_REF].

Sensory acquisition. To perceive the motion, an inertial measurement unit (IMU) is placed at the top of the vertebral column as shown in Figure 1(d). This module possesses one accelerometer and a gyroscope, which permits to measure an angular velocity in rad/s and linear acceleration in rad/s 2 . Since the Gyro drifts slowly from its position and the accelerometer has high-frequency parasites, we can combine the two information to get rid of the slow variations of the gyroscope (high-pass lter) and the fast variations of the accelerometer (lowpass lter). The equation of the complementary lter for the Y angle is: θ IMU = 0.98x(θ + Gy/dt) + 0.02xY a cc. Where Y a cc is the angle of the accelerometer in degree and Gy the variation of the gyroscope. We mount the IMU at the extremity of the structure to have the maximum amplitude variation as the feedback signal. We plot in Figure 1(d) the XY Z coordinate system in which the x-axis is opposite to the gravitational eld and points upward so that the IMU is aligned along the longitudinal axis of the robot, the z-axis is perpendicular to gravity and lies in the horizontal plane of the robot body and the y-axis is aligned in accordance to both the x-and zaxis in order to form a right-hand three-axis coordinate system. The rotations in roll φ, yaw ψ, and pitch θ represent changes in orientation about the x, z and y-axes respectively, see Figure 1(d).

Muscle-tendon model. The structure is actuated by six electrical micro-motors with a gear head and a shaft that reel up a 10 cm tendon-like wire and assembled in opposite sides, two by two, all over the structure and every two segments to have some exibility (under-actuation).

Using the same the nomenclature proposed by Geyer and Herr [START_REF] Geyer | A muscle-re ex model that encodes principles of legged mechanics produces human walking dynamics and muscle activities[END_REF], we propose to model the system dynamics as actuated mass-spring-dampers connected in parallel and in series. formed with an active contractive element (CE) together with elastic series (ES) springs constituting one muscletendon unit (MTU), see Figure 3(a). Each spring has an optimum length l opt in which the global system is in a static con guration. if the CE stretches an ES spring beyond its optimum length (l ES > l opt ), a parallel elasticity (PE) spring engages in the opposite direction so that its length becomes l PE < l opt . Conversely, as each tensile unit possesses two actuators mounted in opposition, the opposite PE prevents the ES of abrupt slack.

We can now put in equation the system's behavior using these elements depending on the action of CE. Knowing the stimulation S(t) of the muscle m and the muscle time delay ( t) and gain G, we have

S(t) = S 0 + G(l CE - l o )(t -t)
where l o is a length o set and S 0 a stimulation o set.

Controllers

We describe in this section the three di erent controllers used to explain our original model to control the soft vertebral robot. In the rst section, we present the error-driven PD controller and how it is implemented to control the structure as a classical invert-pendulum.

In the second section, we present the oscillatory-based Kuramoto network that creates the rhythmical synchronization pattern in open-loop or in closed loop. And in the third section, we present our original approach that combines both approaches, PD+Kuramoto, for rhythmical synchronization and error-based attenuation of oscillations during external perturbation. PD control. One common way to control the structure in its upward position is to use PD controllers to minimize the proportional (P) and derivative errors (D) based on sensory feedback [START_REF] Geyer | A muscle-re ex model that encodes principles of legged mechanics produces human walking dynamics and muscle activities[END_REF]. The variable (e) represents the tracking error, the di erence between the desired input value (R) and the actual output (Y), the angular position computed from the IMU from the vertical axis.

This error signal (e) will be sent to the PD controller, and the controller computes both the derivative of this error signal. The signal (u) just past the controller is now equal to the proportional gain (K P ) times the magnitude of the error plus the derivative gain (K D ) times the derivative of the error: u = K P e + K D ė.

This signal (u) will be sent to the motors fed as a PWM controller, and the new output (Y) will be obtained. This new output (Y) will be sent back to the sensor again to nd the new error signal (e). By convention, the motor units on the left side will receive the command (u) whereas the motors on the right side will receive the command (-u). In the following experiments in Section 4, we will control the tensegrity column in one plane only in the Y -axis using a PD controller on the motor units or the oscillators respectively in Sections 4.3 and 4.5.

Kuramoto oscillators. The PD control presented in the previous section is driven by error feedback and can serve as an adaptive strategy for stabilization if the proper coefcients are found. In comparison, oscillator-based controllers can model rhythmical patterns that can improve the control of speed as well as robustness against noise when the proper feedback-driven coupling is found. We propose to model also this second type of controllers for the balance and postural control of the tensegrity column. We will use for that limit-cycle nonlinear oscillators, which are employed in many robotic experiments to model the spinal cord's CPGs [START_REF] Ijspeert | Central pattern generators for locomotion control in animals and robots: a review[END_REF][START_REF] Nakanishi | An empirical exploration of phase resetting for robust biped locomotion with dynamical movement primitives[END_REF][START_REF] Hoinville | Flexible and multistable pattern generation by evolving constrained plastic neurocontrollers[END_REF].

The archetypal limit-cycle oscillators are the van der Pol or Fitzhugh-Nagumo ; however, we adopt in our experiments the adaptive Kuramoto oscillator for its simplicity to control the motor units. Each oscillator has its intrinsic frequency and can receive interoceptive signals either from other oscillators or descending controllers and exteroceptive signals (in our case from the IMU sensor), see Figure 4 the blue lines. Depending on the Q2 coupling parameters for internal and external feedback, the oscillators can have a phasic adaptation to the robot motion -, which can serve to accelerate it or to damper it concerning the oscillator's own pace,-or an abrupt change to a non-rhythmic behavior.

Each oscillator ϑ has its own intrinsic frequency ω, and each one receives a linear combination from internal and external dynamics. The internal coupling is done by computing the phase di erence between the oscillators. The external coupling is done similarly by computing the phase di erence between the sensory feedback from the IMU unit, θ IMU and the current phase of the oscillator ϑ i . We de ne the three coupling coe cients, KI, KE and JE corresponding, respectively, to the internal coupling among the oscillators, the external coupling of the external signal to the units and the amplitude level of the output signal to the motors. The internal coupling KI synchronizes the oscillators from each other and reduces their variability. The external coupling KE in uences the coupling to external perturbations. Besides, the control of the amplitude signal to the motors JE is used to perturb Colour online, B/W in print and entrain the column. That is, the variable JE changes the amplitude level of sin(ϑ i ) on the motor u i and by doing so modulates the strength of the synchronization level between the oscillators and the multi-articulated structure. The variable JE a ects then the generated resonant modes observed at the body level. Furthermore, in order to take into account the symmetry of the structure, the intrinsic frequency of each co-contracting pair {i, j} are phase-shifted by π so that we have three units controlling the motor activity of six motors: ϑ i = ϑ j + π . We make the note that this e ect is not shown in the equations.

dϑ i dt = ω i + KE sin(θ IMU -ϑ i ) + KI N N j=1 sin(ϑ j -ϑ i ), (1)
u i = JE sin(ϑ i ). ( 2
)
PD control on the Kuramoto oscillators. The parameters {KI, KE, JE} set the oscillators to certain rhythmical regimes, which can be viewed as imposed motor synergies [START_REF] Bizzi | Modular organization of motor behavior in the frog's spinal cord[END_REF]. Therefore, one way to combine the rhythmically based control with the re exive-based control presented before is to put atop of the oscillators a PD controller to modulate the values of the parameters set {KI, KE, JE}. In comparison, the PD controllers atop of the Kuramoto network can modulate its parameters to tune the motor synergies or to repel them from discrete patterns. Therefore, the control of this parameter set {KI, KE, JE} may be seen similar to the descending neuromodulators in the spinal cord that control the activity level of the alphamotor neurons.

This compound controller will drive directly the oscillators toward desired regimes by changing the coupling parameters based on error feedback; the new circuit is plotted in red links in Figure 4. We use for that the dis-Q3 tance to the vertical Y err as a measure of the error e to synchronize the oscillators to the amplitude level of the perturbing force by updating the parameter JE with the PD equations such that JE = K P Y err + K D Ẏerr . Such a strategy may be similar to the task-level commands performed by the neuromodulators in the higher centers of decisions to bypass or to activate the synergistic control at the spinal cord level [START_REF] Todorov | Optimality principles in sensorimotor control[END_REF][START_REF] Bizzi | Modular organization of motor behavior in the frog's spinal cord[END_REF][START_REF] Marder | Principles of rhythmic motor pattern production[END_REF][START_REF] Ting | Dimensional reduction in sensorimotor systems: a framework for understanding muscle coordination of posture[END_REF].

Results

We present in this section the results that characterize our soft robot with perturbations in passive mode in order to retrieve ack its fundamental resonant fre-Q4 quencies (Sections 4.1 and 4.2) and in active mode to control the multi-segments structure for balance and standing upward based on error feedback and oscillations nearby its intrinsic frequencies (Sections 4.3, 4.4 and 4.5).

Dynamic behavior analysis in passive conditions

We make rst a perturbation analysis of the whole structure and present its dynamic behavior when pushed in the frontal plane and when pushed on the transverse plane, respectively (Figure 5(a,b)). Speci cally, we are interested in the passive response under external stresses and the response of the controllers. We display the Fourier diagrams for the two types of perturbations. In Figure 5(a), the horizontal perturbation on the structure produces a pseudo-periodic oscillation with a fundamental mode around 0.5 Hz, whereas in Figure 5(b) a perturbation around its axis of rotation generates an oscillation around 2 Hz. The structure can store and release energy, which is important to develop resonant modes and the motor synergies. The more elements are linked together in the structure; the more resonant modes can be generated.

As the structure is light with spherical joints, it has few frictions except at its xation point and behaves like a pendulum. The number of oscillations till stabilization is very large and above 10 oscillations for 30 seconds momentum for perturbations in the horizontal direction, see Figure 5(b). Therefore, it is reasonable to tune the intrinsic frequencies ω of the oscillators nearby the ones of the structure to ease its motion coordination.

Resonant mode analysis in controlled conditions

We propose to study in this section the control of the different resonant modes and phase delays of the structure with open-loop controllers using PWM controllers. To facilitate the analysis, we group the motors aligned symmetrically in the longitudinal plane forming two clusters of three motors each. We control the phase delay and duration of the PWM between the two motor groups around the fundamental frequency.

If we modulate the duration of the PWM controllers for all the motors as in Figure 6(a-d), respectively, from 50, 100 , 25 and 500 ms, we can observe sensitivity on the oscillatory patterns of the tensegrity structure. As we might expect, large PWM produces large amplitude oscillations whereas small periods of the PWM generate weak perturbations. The resonant mode occurs for 250 ms period square signal with amplitude variation 3 times larger than for PWM of 50 ms. Above this value, in the case of Figure 6(d), new harmonic modes are super-imposed on the speed signal, which corresponds to complex modes of coordination with the apparition also of harmonic waves.

PD control

We perform rst the error-based PD control of the upward structure relative to the Y axis with directly e = Y err , the relative displacement. The PD controller can be written as u = K P Y err + K D Ẏerr . We present a

Colour online, B/W in print The perturbations are represented as strong deviations of the PD error in the middle chart. In this graph, we show that the PD control is capable of stabilizing the Y axis with a short recovery period with respect to external perturbations.

graph in Figure 7 showing the structure Y displacement to the vertical axis, the PD error computed and the motor control on it. It shows that the PD controller rapidly stabilizes its dynamics to the upward posture concerning perturbations, which corresponds more to a re exive bang-bang controller when the K D coe cient is tuned with a small value relative to K P . Although the structure presents a rhythmical pattern, the transitions are abrupt as we do not observe any resonant modes in this conguration (top chart). In this control mode, the motors contribute mostly to shock absorptions, which is less energy-e cient and less compliant. We will study and compare thereinafter other controllers based on oscillators to overcome this problem of smooth control.

Kuramoto oscillators control

Our rst experiment with the Kuramoto oscillators consists in studying the interval range of the external coupling parameter KE and see the impact feedback on the internal dynamics of the oscillators when they are coupled to it. We study rst the Fourier coe cients of Kuramoto's units when the control is done in a closedloop manner when we make to vary KE within the interval range [0; 1]; the motor signal is normalized within the interval range [0, 255] and translated into PWM to the motors. We display the result of the Fourier transform in Figure 8(a) and of the dynamics of one motor in Figure 8 intrinsic frequency ω of the oscillators. In this stage, the tensegrity structure performs a strong rhythmic motion.

At KE = 0.2, an interesting behavior occurs in which the oscillators bifurcate to an attractor point, which is an under-damped postural con guration due to the friction of the ball joints. The friction poises the structure to the vertical position. The structure is slowly entrained by a slight feedback control till its immobilization. This posture is in this plot the upward posture with Y = 0. In this situation, the motors remain in this static posture without any feedback and react to small perturbations: when the structure is slightly pushed, the oscillators act re exively to return back to the static posture. Above this value, say for KE ≥ 0.4, the oscillators start to be entrained actively by the external dynamics with a signal per noise ratio that depends on KE values. In this stage, the feeded back signal generates stable cyclic motion around the upward position in which, the higher the coupling coe cient, the higher the instabilities of the rhythmical pattern.

To understand in more details what is going on between the two regimes found, we plot the dynamics of the oscillator in the interval range KE ∈ [0.15; 0.4], see Figure 8(b). In coherence with the results found in Figure 8(a), we observe a point transition only at KE = 0.25, which corresponds to a bifurcation diagram of the oscillators dynamics when they start to synchronize to the external dynamics of the body structure and start to mutually in uence each other to this particular rhythm. This state corresponds to what is called feedback resonance, a mechanism that drives one system to its resonant frequencies by feedback and for certain coupling strength. This approach is similar to synergistic control [START_REF] Kelso | Dynamic patterns: The self-organization of brain and behavior[END_REF][START_REF] Bardy | The dynamics of human postural transitions[END_REF], nonetheless, we characterized this phenomenon in robotics as a way to control postural coordination in di erent robotic systems [START_REF] Pitti | Quanti cation of emergent behaviors induced by feedback resonance of chaos[END_REF][START_REF] Pitti | Exploration of natural dynamics through resonance and chaos[END_REF][START_REF] Pitti | Generating spatiotemporal joint torque patterns from dynamical synchronization of distributed pattern generators[END_REF][START_REF] Pitti | Creating and modulating rhythms by controlling the physics of the body[END_REF].

We analyze in the next paragraph the three cases found depending on the coupling parameters {KE, KI, JE}.

We display three di erent phase plots for the three behaviors presented earlier with respect to KE ∈ {0.0; 0.2; 0.4}, see Figure 9 resp. (a-c). But to de ne more precisely the behavior of the system, we add two new conditions to compare with when JE = 0.6 and when JE = 1.0 that modulate more or less strongly each motor output. The two left columns of top charts indicate the oscillator's phase over time ϑ(t) given to the motors between [0; +255] and the two left column of bottom charts indicate the vertical displacement over time Y(t) or Y err relative to the vertical axis and normalized between [-100; +100], which corresponds to [-30; +30cm]. The third column in Figure 9(a-c In Figure 9(a), the tensegrity structure is totally open-loop driven and forced to follow the oscillators cycle without any feedback. In contrast, the situation in Figure 9(b) corresponds to an under-damped case for KE = 0.2 where the oscillators go to a point attractor centered on the neutral position of the structure. Besides, when the coupling term KE augments above 0.2 as it is the case in Figure 9(c), the Kuramoto oscillators start to be entrained to the phasic regime of the structure. In line with the Fourier analysis in Figure 8, Figure 9 describes how the coe cient JE a ects synchronization and the system behavior as it is for KE. We will present thereinafter in the next section the top-down control done on the global parameters {KI, KE, JE} for updating the oscillators to the desired regime.

PD control on Kuramoto oscillators

The two methods presented in the previous Sections 4.3 and 4.4 have di erent advantages regarding controllability concerning the desired state (resp. the PD controller) and regarding compliance control concerning the desired rhythm (resp. the oscillators). The association of the two controllers type may permit to combine the advantages of the two worlds for generating one controlled entrainment to resonant modes and robust to perturbations. We propose to study this combined controller for the balance control of the tensegrity column in the upward posture by the amplitude modulation of JE on the oscillators based on error feedback e. We remind the reader that JE is governed by the equation JE = K P Y err + K D Ẏerr where Y err is the horizontal displacement relative to the vertical axis.

We plot in Figure 10 four time series of the structure's stabilization for di erent pushes of gradual strength with the plot of the Y axis deviation in the top chart, and of the PD error over time in the middle chart and of the motor activity in the bottom chart for two motors in the opposite side. In order to better understand the dynamics, a motion sequence is presented in Figure 11 of a recovery after a stroke and a movie are provided at the address https://sites.google.com/site/embodiedai/currentresearch/tensegrityrobots.

The top-down control strategy used to stabilize the structure is based on the modulation of JE concerning the displacement on the Y axis employed as error feedback. Depending on the perturbation force applied on the structure -, that we characterize in percent from 5% to 20% of relative displacement,-various transitory regimes can be observed till stabilization. This 'resynchronization' process has an impact on the temporal period, the phase and the frequency adaptation.

When a small stroke is applied as in Figure 10 (a ,b), the PD controller generates small amplitude variations till convergence of the oscillatory regime of the Kuramoto units with the damping of the structure between 10 and 15 s to its upward posture. The oscillatory regime of the CPGs is similar to an under-damped regime for a spring-mass system with a long lasting transitory regime of a dizain of cycles. For instance, when the perturbation reaches 10% displacement, the PD controller desynchronize several times and takes several trials to re-stabilize the oscillators and the structure.

In the case of a strong perturbation as it is in Figure 10 (c ,d) for 15% and 20% perturbations, the PD controller generates at reverse higher amplitude adaptations of the Kuramoto units till absorption of the shock and damping of the structure. The temporal employed is slightly higher in this forced regime with a longer synchronization stage diminution of the oscillators amplitude and phase di erence. This behavior of the CPGs is similar to an over-damped regime for a spring-mass system with a faster transitory state of several seconds but after the stabilization of the oscillatory, which takes longer times (around 20 cycles).

In all the situations, the oscillatory system nished with a small vibratory mode around the vertical axis due to the tuning of the PD coe cients, till its return back to a static posture with the release of the motors from cocontraction. Our strategy was e cient in all the studied cases, irrespective of the shock level but with some sensitivity of the PD controller to small perturbations due to its coe cients. These small perturbations made the system to slightly reactivate the oscillations as it is displayed in Figure 10(b) at time 48 s. We can understand from this gure that the external dynamics of the vertebral column excites the oscillators and reactivates their dynamics.

The top-down controller performed on the oscillators permits to modulate more adaptively the strength of the motor synergies relative to the task than the PD controller. To compare the two strategies, we plot the error relative to the upward posture for the PD controller and the PD-controlled oscillators, respectively in Figure 12 (a,b). The gure shows that the second strategy (PD control + Kuramoto oscillators) exploits more smoothly the motors with less strength applied on them (with a PWM below 150), which is at the price of a larger error variance. This complementary strategy exploits better the body structure and the motor synergies with unrestricted Colour online, B/W in print Figure 10. Feedback control of the global parameter JE on the Kuramoto oscillators for various external perturbations. When a strong perturbation is imposed on the structure, an oscillatory regime is established by the top-down controller on the vertebral column to absorb the shock with a high amplitude till their attenuation. This transitory regime depends on the amplitude of the shock and of the velocity of the JE to steer the oscillators and the motors till their release when the column is stable enough to return back and stand at its upward posture. The more JE decays slowly, the longer the transition to a stable regime (under-damped oscillations). The more JE decays fastly, the quicker the transition to a stable regime (over-damped oscillations). dynamics and loose error, which makes it better suited to absorb any external shocks.

Discussion

We presented a tensegrity-based model of a vertebral column robot controlled actively with nonlinear oscillators and feedback for rhythmical balance and upward posture. From a control viewpoint, the physics of this complex system requires to adopt a more bio-inspired type of control with loosely and parallely distributed units for adaptation to the body dynamics [START_REF] Caluwaerts | Design and control of compliant tensegrity robots through simulation and hardware validation[END_REF]. In the end, the elastic properties of the tensegrity-based articulated trunk may ease its control [START_REF] Alexander | Walking made simple[END_REF]; i.e. its morphological control [START_REF] Pfeifer | How the body shapes the way we think, a new view of intelligence[END_REF][START_REF] Pfeifer | Morphological computationconnecting brain, body, and environment -creating brain-like intelligence: from basic principles to complex intelligent systems[END_REF][START_REF] Pfeifer | La révolution de l'intelligence du corps[END_REF]. The CPGs in the spinal cord are local neural units that can generate a rhythmical pattern even without any feedback. Their activity, however, is always under the local feedback control of muscle spindle signals and the global feedback control of neuromodulators at the spinal circuits level or at the higher level. These feedback loops make these units embodied in the physics of the structure and contingent to a global coordination at the task level. We use Kuramoto oscillators to entrain the vertebral column to its own rhythms and to synchronize them dynamically to the structure's resonant frequencies thanks to the IMU unit. This phenomenon is known as feedback resonance [START_REF] Pitti | Quanti cation of emergent behaviors induced by feedback resonance of chaos[END_REF][START_REF] Pitti | Exploration of natural dynamics through resonance and chaos[END_REF][START_REF] Fradkov | Exploring nonlinearity by feedback[END_REF][START_REF] Fradkov | Investigation of physical systems by means of feedback[END_REF] and is used as a strategy to control the vertebral column to its resonant frequencies for shock absorption and postural balance. The tensile robot presents interesting damping properties that makes it easy to stabilize at the upward con guration, either passively or actively [START_REF] Iida | Self-stabilization and behavioral diversity of embodied adaptive locomotion. Embodied articial intelligence[END_REF][START_REF] Ikemoto | Advantages of exible musculoskeletal robot structure in sensory acquisition[END_REF]. This is in line with observations found on biological systems and humans on the importance of an actuated head and exible trunk to body balance [START_REF] Bonnet | A structurally optimal control model for predicting and analyzing human postural coordination[END_REF][START_REF] Turvey | The medium of haptic perception: a tensegrity hypothesis[END_REF][START_REF] Bardy | On perturbation and pattern co-existence in postural coordination dynamics[END_REF] and passive walkers [START_REF] Alexander | Walking made simple[END_REF][START_REF] Laumond | The Yoyo-Man[END_REF]. We extended then the oscillator network to adaptive control with the use of feedback error for dynamical synchronization of the structure to the upward posture. This model is in line with other biological models of neurons for robotics that includes reciprocal, inhibitory and oscillatory modes [START_REF] Pitti | Creating and modulating rhythms by controlling the physics of the body[END_REF][START_REF] Melnyk | Bio-inspired plastic controller for a robot arm to shake hand with human[END_REF][START_REF] Amrollah | On the role of sensory feedbacks in Rowat-Selverston cpg to improve robot legged locomotion[END_REF][START_REF] Nassour | Multi-layered multi-pattern CPG for adaptive locomotion of humanoid robots[END_REF]]. However, our neural controller is combining PD control+oscillators in order to produce controlled rhythmical patterns, which is original and appears not used by other teams. Our feedbackdriven oscillatory network controls global parameters for the dynamical entrainment of the resonant frequencies so that it can serve for discrete phase resetting [START_REF] Nakanishi | An empirical exploration of phase resetting for robust biped locomotion with dynamical movement primitives[END_REF] or modulated attenuation/ampli cation; this approach is in line with the proposal by Bizzi of motor synergies [START_REF] Bizzi | Combining modules for movement[END_REF].

Our model presents also similar properties with [START_REF] Bardy | The dynamics of human postural transitions[END_REF][START_REF] Bonnet | A structurally optimal control model for predicting and analyzing human postural coordination[END_REF] and provides realistic predictions of postural sway movements during erected head tracking. In our system, bifurcation and nonlinearities emerge from online optimization due to the combination of phase synchronized oscillators and PD control, which is di cult to achieve with o ine models. Adaptation and recovery are possible only when synchronization is done around the frequencies of the body dynamics and found during the test phase. Further versions may examine the online discovery and learning of the structural parameters of the system and of the task, such as ω and the coupling parameter {KE, KI, JE} and Y err , by a top-down neural network or by a pseudo-inverse matrix that store and anticipate these information.

We show that tensile structures present interesting properties for the design of soft and bio-inspired robots with the use of replicative elements to insure a redundancy of the global behavior at the macroscale level and exibility with the many degrees of freedom of each element. These structures are lightweights and pre-tensed, which make them physically robust to shocks even passively as they distribute their tension on all their elements. Furthermore, their sti ness can be linearly controlled with the co-contraction of the motors to switch from a exible behavior to a rigid one. The dimensionality of the system makes it a complex system and the way to control it requires to exploit its passive dynamics and to entrain the controllers to its resonant frequencies for upward balance or rhythmical motion.

Starting from this tensegrity-based vertebral column robot, it is natural then to think to design other body parts based on tensegrity [START_REF] Flemons | The bones of tensegrity[END_REF][START_REF] Fujita | Environmental and structural e ects on physical reservoir computing with tensegrity[END_REF]. We will attempt to go further in that direction with a more complex body and behaviors such as postural coordination and walking [START_REF] Pitti | Generating spatiotemporal joint torque patterns from dynamical synchronization of distributed pattern generators[END_REF]. At now, we have employed only one IMU unit in the top vertebral column to allow head-centered coordinated movements [START_REF] Bonnet | A structurally optimal control model for predicting and analyzing human postural coordination[END_REF] as it is known that the vestibular system, perceiving rotational velocities and linear accelerations, uses this information to generate a uni ed inertial reference frame, centered in the head that allows whole-body coordinated movements and head-oriented locomotion [START_REF] Berthoz | The brain's sense of movement[END_REF][START_REF] Falotico | Head stabilization based on a feedback error learning in a humanoid robot[END_REF]. In future works, we will employ more IMU units for each segment to have proprioception at the body level.

Finally, as an educational tool, the scalability of tensegrity structures ful lls the requirements for testing ideas with low-cost and multi-disciplinary platforms at the community level for exploration and experimentation in robotics for Research, as well as in Art and Education. For instance, tensile structures can be 3D printed and can be highly replicable, which can be interesting for the Do-It-Yourself community. In the complement of this paper, we provide a website of the project with links for downloading freely the tensegrity modules for building it and to inspire and iterate on the project to one's own. Their overall robustness and lightweight can be put forward in comparison to most robots, which are still fragile and expensive products to design and repair. The ecology of the body morphology changes also the way control in force and precision is done and requires to understand biological control and to rethink it for robots.

Figure 1 .

 1 Figure 1. Multi-joint vertebral column model based on autoreplicative tensile elements for soft robotics. (a-c) Each element forms a tetrahedron by its four edges, which ensures the whole compliance and tension distribution in the three directions when connected to other elements in line. (d) An Inertial Measurement Unit (IMU) is placed at the end of the structure for position control and acceleration feedback. We provide the design of the replicative element freely at the address [44].

Figure 2 .Figure 3 .

 23 Figure 2. Robustness in co-contraction in horizontal and upward postural configuration. Static postures demand to set the contraction of all the motors to specific lengths. In these situations, the motors act as rigid tendons and loads are distributed overall the structure. Maximal efforts are delivered on the structure when set at the horizontal in (a), in the vertical plane with different directions in (b), and upward at the vertical in (c).

Figure 4 .

 4 Figure 4. Hierarchical control based on top-down PD controllers and bottom-up oscillators. The whole control of the motor synergies is based on the coupling parameters set {KE, KI, JE}. The Kuramoto oscillators are coupled internally to each other based on the parameter KI. The external coupling is done by the parameter KE, which sets the influence of the IMU sensor on the internal dynamics. The parameter JE acts on the amplitude of the Kuramoto units. The rhythmical patterns produced by the oscillators can be controlled by a higher center of decision that selects the global parameters for a desired postural control. This hierarchical control corresponds to a dimensionality reduction of the controller on the robot dynamics to generate a feedback-based closed loop control on oscillatory movements.

Figure 5 .

 5 Figure 5. Perturbation analysis on the vertical and axial plans of rotation, resp. top chart and bottom chart in (a) and (b). The Fourier transforms in (c) show the resonant frequencies of the structure. Two different fundamental resonant frequencies are found for the two axis, respectively 0.5Hz and 2Hz.

Figure 6 .

 6 Figure 6. Phase duration characterization in controlled condition with PWM. A PWM signal controls the tensegrity structure in the vertical axis with motors aligned along the vertical axis. Modulating the phase duration of the motors, from small durations 50 ms (resp (a), 100 ms (resp (b), 250 ms (resp (c) up to 500 ms (resp. (d), affects the level of global synchrony and the apparition of complex modes of resonance.

Figure 7 .

 7 Figure 7. PD control with respect to external perturbations. The top chart presents the displacement of the structure on the Y axis, the middle chart displays the PD error and the bottom chart corresponds to the motor output taken from two units in opposite side.The perturbations are represented as strong deviations of the PD error in the middle chart. In this graph, we show that the PD control is capable of stabilizing the Y axis with a short recovery period with respect to external perturbations.

Figure 8 .Figure 9 .

 89 Figure 8. Influence of the external coupling parameter KE on the resonant modes of the tensegrity structure. In (a), we plot the Fourier coefficients with respect to the quantity of feeded back signal injected into the oscillators within the interval range KE ∈ [0.0, 1.0] from open-loop control to stable closed-loop entrainment. In (b), we plot the details of the dynamics of one oscillator with respect to KE in the interval range [0.15, 0.40] when the system bifurcates from an under-damped state to a rhythmical regime with the resonant frequencies of the tensile structure.

  ) corresponds to the phase plot of the two variables Y and ϑ, respectively in the AND A. PITTI x and y axis, which describes the temporal dependence of the two variables. These graphs show the plots during 10 s of the internal CPGs dynamics and of the position at the tip of the structure oscillating around the Y axis for JE ∈ [0.6; 1.0].

Figure 11 .

 11 Figure 11. Motion sequence of postural balance after a stroke. A complete movie is provided at the address https://sites.google.com/site/ embodiedai/current-research/tensegrityrobots.

Figure 12 .

 12 Figure12. Motor contribution with respect to the control strategy and perturbation. Comparison of motor dynamics between the PD controller in (a) and the PD controller on the Kuramoto oscillators in (b). In (a), the motors are strongly solicited to minimize error drastically from any perturbation. In (b), the motors are less strongly exploited; which has in consequence the loose error. The second strategy permits to exploit better the body structure and its passivity in order to have a more compliant and energy-efficient control on the body structure.

Acknowledgments

We would like to dedicate this manuscript in memory of Stephane Garnier, our collaborator at ENSEA, who started to work with us on this project and passed away. We would like to thank Ihor Kuras for his help on this project.

Disclosure statement

No potential con ict of interest was reported by the authors. Q5 1436 1441 1446 1451 1456 1461 1466 1471 1476 1481 1546 1551 1556 1561 1566 1571 1576 1581 1586 1591

Funding

This research project was partially funded by chaire d'Excellence CNRS-UCP, the project Labex MME-DII (ANR11-LBX-0023-Q6 01) and EQUIPEX-ROBOTEX (CNRS).