Rémi Bonnefoi
email: remi.bonnefoi@centralesupelec.fr

Lilian Besson
email: lilian.besson@centralesupelec.fr

Julio Manco-Vasquez
email: juliocesar.mancovasquez@centralesupelec.fr

Christophe Moy
email: christophe.moy@univ-rennes1.fr

Upper-Confidence Bound for Channel Selection in LPWA Networks with Retransmissions

Keywords: Low Power Wide Area, Multi-Armed Bandits, Upper-Confident Bound, retransmissions, Internet of Things

In this paper, we propose and evaluate different learning strategies based on Multi-Arm Bandit (MAB) algorithms. They allow Internet of Things (IoT) devices to improve their access to the network and their autonomy, while taking into account the impact of encountered radio collisions. For that end, several heuristics employing Upper-Confident Bound (UCB) algorithms are examined, to explore the contextual information provided by the number of retransmissions. Our results show that approaches based on UCB obtain a significant improvement in terms of successful transmission probabilities. Furthermore, it also reveals that a pure UCB channel access is as efficient as more sophisticated learning strategies.

I. INTRODUCTION

Nowadays, the Internet of Things (IoT) and in particular the Low Power Wide Area (LPWA) technology is considered a main driver for a vast variety of application that will support the communications among a large number of devices. In fact, network operators are starting to deploy Machine to Machine (M2M) solutions using LPWA networking technologies [START_REF] Raza | Low power wide area networks: An overview[END_REF]. For instance, LoRaWAN and SigFox technologies have been most adopted in the monitoring of large scale systems (e.g., smart cities, metering), where a large number of devices compete for the transmission of their packets in the unlicensed Industrial, Scientific and Medical (ISM) bands.

Nevertheless, this demand to fit a growing number of energy-limited end-devices requires the development of contention-based protocol more tailored for LPWAN technologies. Thus, novel access mechanisms considering collisionavoidance methods need to be addressed to avoid degrading the network performance in these unlicensed bands. In fact, the number of packet collisions increases as more devices without coordination share the same band. Hence, an important concern in the Medium Access (MAC) design is to reduce the Packet Loss Ratio (PLR) due to the interference caused by the collisions among the devices. This publication is supported by the French National Research Agency (ANR), under the projects SOGREEN and EPHYL (grants N ANR-14-CE28-0025-02 and N ANR-16-CE25-0002-03), by Région Bretagne, France, by École Normale Supérieure de Paris-Saclay. by European Union, through the European Regional Development Fund (ERDF), and by Ministry of Higher Education and Research, Brittany and Rennes Mtropole, through the CPER Project SOPHIE / STIC & Ondes.

In this regard, in the context of Cognitive Radio [START_REF] Mitola | Cognitive Radio: making software radios more personal[END_REF], [START_REF] Haykin | Cognitive Radio: Brain-Empowered Wireless Communications[END_REF], Multi-Arm Bandit (MAB) algorithms [START_REF] Auer | Finite-time Analysis of the Multi-armed Bandit Problem[END_REF], [START_REF] Auer | The Non-Stochastic Multi-Armed Bandit Problem[END_REF], [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF] have been recently proposed as a potential solution for channel access in LPWA networks [START_REF] Bonnefoi | Improvement of the LP-WAN AMI backhaul's latency thanks to reinforcement learning algorithms[END_REF], [START_REF] Azari | Self-organized Low-power IoT Networks: A Distributed Learning Approach[END_REF], [START_REF] Bonnefoi | Multi-Armed Bandit Learning in IoT Networks: Learning helps even in nonstationary settings[END_REF]. For instance in [START_REF] Bonnefoi | Multi-Armed Bandit Learning in IoT Networks: Learning helps even in nonstationary settings[END_REF], the impact of non-stationarity on the network performance using MAB algorithms is studied. In this work, low-cost algorithms following two well-known approaches, such as the Upper-Confidence Bound (UCB) [START_REF] Auer | Finite-time Analysis of the Multi-armed Bandit Problem[END_REF], [START_REF] Auer | The Non-Stochastic Multi-Armed Bandit Problem[END_REF], and the Thompson Sampling (TS) algorithms [START_REF] Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF] have reported encouraging results. Other recent directions include theoretical analysis [START_REF] Besson | Multi-Player Bandits Revisited[END_REF], [START_REF] Boursier | SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits[END_REF], and realistic empirical simulations [START_REF] Kumar | Two-stage decision making policy for opportunistic spectrum access and validation on USRP testbed[END_REF], [START_REF] Kumar | Channel Selection for Secondary Users in Decentralized Network of Unknown Size[END_REF], of the application of MAB algorithms for slotted wireless protocols in a decentralized manner, or applications to multi-hoping networks [START_REF] Maskooki | Competition: Channel Exploration/Exploitation Based on a Thompson Sampling Approach in a Radio Cognitive Environment[END_REF], [START_REF] Toldov | A Thompson Sampling Approach To Channel Exploration Exploitation Problem In Multihop Cognitive Radio Networks[END_REF]. None of the above mentioned articles discusses in detail the impact of retransmissions on the performance of MAB learning algorithms as we do in this paper.

The aim of this paper is to assess the performance of MAB algorithms [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF] for channel selection in LPWA networks, while taking into account the impact of retransmissions on the network performance. For this reason, several decision making strategies are applied after a first retransmission (i.e., when a collision occurs). Proposed approach employs contextual information provided by the number of retransmissions, and implemented at each device, so that no coordination among them is needed. Moreover, our UCB-based heuristics show low complexity making them suitable for being embedded in LPWA devices.

The contributions of this paper are summarized as follows:

• Firstly, we provide a close form approximation of the radio collision probability after a first retransmission. By doing this, we highlight the need to develop a learning approach for channel selection upon collision. • Secondly, different heuristics are proposed to cope with retransmissions.

• Lastly, we conduct simulations in order to compare the performance of the proposed heuristics with a naive uniform random approach, and a UCB strategy (i.e., without any learning for the retransmissions).

The rest of the paper is organized as follows. First the system model is introduced in Section II. Our motivations are exposed in Section III, and a formal description of the MAB learning algorithms is given in Section IV. The proposed UCB-based heuristics are presented in Section V, while the corresponding numerical results are shown in Section VI. Finally, some conclusions are drawn in Section VII.

II. SYSTEM MODEL A. LPWA Network

We consider in this paper an LPWA network composed of a gateway and a large number of end-devices that regularly send short data packets, where K channels (K > 1) are available for the transmission of their packets.

We assume that this network is constituted by two types of devices: on one hand, we have static devices that operate in one channel1 in order to communicate with the gateway. On the other hand, there are IoT devices, that possess the additional advantage of being able to select any of the K available channels to perform their transmissions.

Regardless the type of devices, each of them follows a slotted ALOHA protocol [START_REF] Roberts | Aloha packet system with and without slots and capture[END_REF], and has a probability p > 0 to transmit a packet in a time slot. We make the hypothesis that the transmission is successful if the channel is available, otherwise upon radio collision, these devices will attempt to transmit their packet up-to M times, with M ∈ N. Note that, every retransmission is carried out after a random back-off time, uniformly distributed in 0, m-1 , where m ∈ N, m > 0 is the length of the back-off interval.

B. Model of our IoT devices

The aforementioned contention process can be described by a Markov chain model [START_REF] Norris | Markov Chains[END_REF] similar to the one presented in [START_REF] Yang | Performance analysis and parameter optimization of random access backoff algorithm in lte[END_REF], as it is depicted in Fig. 1. A device containing a packet for transmission goes from an idle state to a transmission state, while considering retransmissions due to different collision probabilities, i.e., {p c , p c1 , . . . , p cM -2 }, at each M -1 backoff stage. At each time slot, a transition from an idle state to a transmission state (denoted as Trans.) occurs if a packet transmission is required, while waiting states (denoted as Wait), correspond to a m back-off interval.

A device aims to select a channel with the highest probability of successful transmission, for which it resorts to a reinforcement learning approach. It is formulated as a MAB problem, where each channel (also called arms) is viewed as a gambling machine (bandit), and each bandit has a reward. Then, at every trial, a device chooses a channel that maximizes the sum of the collected rewards. These rewards are the acknowledgment (Ack) signals received after transmitting packets to the gateway. In this way, a successful transmission is considered when an acknowledgment is received, and a learning approach is employed to select the best channel.

We address the problem of channel selection taking into account the described Markov model for the retransmissions of end-devices. It motivates our present work for which we consider the retransmissions in the analysis of MAB algorithms.

III. MOTIVATIONS FOR THE PROPOSED APPROACH

When a device experiments a collision, it goes in a back-off state to retransmit the same packet on a channel. If all devices remain in the same channel for retransmissions, it could result in a sequence of successive collisions with the same devices' packets that previously collided. Thus, it seems interesting to consider in the decision making policy the possibility for a device to retransmit in a different channel. One of our motivations to develop new MAB algorithms for our problem is this option of using a different communication channels between the first transmission and the next retransmissions.

By considering this possibility, the device will have to learn more, thus, we expect the learning time to be longer, but it could be possible that the final performance gain (i.e., in terms of successful transmission rate) increases too. The next Section VI presents analysis to check this performance gain, for various heuristics based on the UCB algorithm.

Here after, we start by presenting a mathematical derivation that backups this idea. To do so, we study the collision probabilities considering the Markov process depicted in Fig. 1, and foresee the impact of addressing bandit strategies, as well as setting guidelines for the design of heuristic approaches.

A. Probability of collision at the second transmission slot

As it is well known, having a collision during an access time can be overcome by a retransmission procedure (this can take several retransmission attempts). What interest us here, is to obtain a mathematical approximation of the collision probability at the second transmission slot p c1 , as a function of the first collision probability p c .

We consider two hypotheses H 1 and H 2 defined as,

• H 1 : The probability p c1 , is composed by the sum of two probabilities: i) the probability of colliding consecutively twice, i.e., the devices that collide at a given time slot and collide again when retransmitting their packets, and ii) the probability of collision among devices that did not collide in the same previous collision. Moreover, we suppose that the number of devices involved in a collision is small in comparison to the total number of devices.

• H 2 : The total number of the back-off stages at time t is constant, and it is assumed to be large enough to consider that no device will ever be in the last failure state (this case is the one on the right side in Figure 1), after M successive failed retransmissions. Considering one device and a channel, we denote x i t the probability that it is transmitting a packet for the i+1 time in a given time slot t (with i ∈ 0, M -1 ), and let x t = M -1 i=0 x i t be the probability that it transmits a packet. We consider N active devices following the same policy.

We assume to be in the steady state [START_REF] Norris | Markov Chains[END_REF], in our Markov chain model depicted in Figure 1, and thus the probabilities no longer depend on the slot number t (i.e., ∀t, x t = x). Therefore, the probability that this device has a collision at the first transmission is p c , and has the following expression

p c = 1 -(1 -x) N -1 ⇐⇒ x = 1 -(1 -p c ) 1 N -1 . (1)
Moreover, from (1) we define the probability p cp (n) that involves the collision of n packets sent by each IoT device (for any 1 ≤ n ≤ N -1), during the first transmission slot, and is defined by the following equation

p cp (n) = N -1 n x n (1 -x) N -1-n .
As explained above, if an IoT device experiences a collision at the first transmission, it proceeds for the retransmission of its packet after a random back-off interval. We denote p ca the probability to have a collision with a packet involved in the previous collision. Under the H 1 assumption, the number of packets involved in the same previous collision remains very small in comparison to the total number of devices that may transmit during this time. In other words, this collision probability does not depend on previous retransmissions and is equal to p c . So, the probability that the same device's packet experiences again a collision at the second time slot is

p c1 = p ca + (1 -p ca ) p c . (2)
If the device has a collision at the first attempt, we consider p bp (n) the probability that it has a collision with exactly n packets (for any 1 ≤ n ≤ N -1), and that at least one of the n devices involved in this first collision chooses the same back-off interval,

p bp (n) = N -1 n x n (1 -x) N -1-n 1 -1 - 1 m n .
(3) Besides, p ca is the conditional probability of collision with a packet sent by a device involved in the previous collision given that the packet experienced collision at its first transmission. Hence, under hypothesis H 2 , we can use Bayes theorem and the law of total probability to relate p ca with p bp (n), and the different probabilities that a device experienced a collision during the first slot and has the same back-off interval for its retransmission is, Therefore, the expression of p ca is

p ca = 1 p c N -1 n=1 p bp (n). (4)
1 p c N -1 n=1 N -1 n x n (1 -x) N -1-n 1 -1 - 1 m n = 1 - 1 p c N -1 n=1 N -1 n x n (1 -x) N -1-n 1 - 1 m n . (5)
Once again under H 1 , assuming that the number of devices involved in the first collision is small compared to N -1, the first N 0 N -1 terms of the sum in (5) are predominant. We derive,

p ca 1 - 1 p c N0 n=1 N -1 n x n (1 -x) N -1-n 1 - 1 m n . (6
) Moreover, for these terms, n is small compared to N -1, and so N -1 -n can be approximated to N -1. Thus it gives,

p ca 1 - (1 -x) N -1 p c N0 n=1 N -1 n x n 1 - 1 m n . (7)
Assuming H 1 amounts to consider that x 1. As a consequence, the sum in equation ( 7) can be supplemented by negligible terms,

p ca 1 - (1 -x) N -1 p c N -1 n=1 N -1 n x n 1 - 1 m n . (8)
We use the binomial theorem to compute the sum in (8), and we rewrite the expression of p ca as

p ca 1- 1 p c -1 1 + 1 -(1 -p c ) 1 N -1 1 - 1 m N -1 . (9)
Finally, our approximation of p c1 can be obtained by inserting (9) in (2).

B. Behaviour analysis of p c and p c1

In order to assess the proposed approximation, we suppose a unique channel where all the devices follow the same contention Markov process. We simulate an ALOHA protocol with a maximum number of retransmissions M = 10, a maximum back-off interval m = 10, and a transmission probability p = 10 -3 . In Fig. 2, we show the collision probabilities for different number of devices N (from N = 50 up-to N = 400), for both p c and p c1 .

From this simulations, we can verify that our approximation is very precise for lower values p c1 ≤ 30% (i.e., red and orange curves are quite close). Moreover, a significant gap between p c1 and p c , of up-to 10%, can be observed, which suggests us to resort to MAB algorithms for the channel selection for both the first transmission and next retransmissions.

C. Learning is useful for non-congested networks

It is worth to highlight that, if we write (2) as p c1 = p c + p ca (1 -p c ), then it is obvious that p c1 is always larger than p c (as p ca (1 -p c ) > 0). But for large values of p c , p ca (1 -p c ) 0 so the gap gets small, and for small values of p c the gap is significant. Moreover, we can verify (e.g., numerically or by differentiating) that the gap decreases when p c increases (for fixed N and m). This backups mathematically the observation we made from Fig. 2: the smaller p c , the larger is the gap between p c and p c1 .

We interpret this fact in two different situations. On one hand, in a congested network, when devices suffer from a large probability of collision on their first transmission (i.e., p c is not so small), then p c1 p c and so devices cannot really hope to reduce their collision probabilities even if the use a different channel for retransmission. On the other hand, if p c is small enough, i.e., in a network not yet too congested, then our derivation shows that p c1 p c , meaning that the possible gain of retransmitting in a different channel that the one used for the first transmission can be large, in terms of collision probability (e.g., up-to 10% in this experimental setting). In other words, when learning can be useful (small p c ), learning to retransmit in a different channel can have a large impact on the global collision rate, thus justifying our approach.

IV. A WELL-KNOWN MAB ALGORITHM: UCB

Without loss of generality, we have adopted a well-studied stochastic MAB learning algorithm, where the reward distributions are unknown and assumed to be independent and identically distributed (i.i.d). The arms model the channels denoted as C(t) ∈ 1, K , and the players, the dynamic devices, learn the distributions to be able to progressively focus on the best arm, i.e., the arm with largest mean representing the mean availability of a given channel k.

Before presenting our proposed heuristics, we describe a UCB bandit algorithm [START_REF] Auer | Finite-time Analysis of the Multi-armed Bandit Problem[END_REF]. It has reported to be efficient, while featuring a low complexity for its implementation. For this reason, it has been employed for IoT applications [START_REF] Bonnefoi | Multi-Armed Bandit Learning in IoT Networks: Learning helps even in nonstationary settings[END_REF], and we employ this approach to develop our proposals.

A. The UCB algorithm

A first approach is to only use an empirical mean estimator of the rewards in every channel, and select the channel with highest estimated mean at every time step; but this greedy approach is known to fail dramatically [START_REF] Auer | The Non-Stochastic Multi-Armed Bandit Problem[END_REF]. Indeed, with this policy, the selection of arms depends too much on the first draws: if the first transmission in one channel fails and the first one on other channels succeeds, the device will never use the first channel again, even if it is the best one (i.e., the most available, in average).

Rather than relying on the empirical mean reward, UCB algorithms instead use a confidence interval on the unknown mean µ k of each arm, which can be viewed as adding a "bonus" exploration to the empirical mean. They follow the "optimism-in-face-of-uncertainty" principle: at each step, they play according to the best model, as the statistically best possible arm (i.e., the highest UCB) is selected.

More formally, for one device, let N k (t) be the number of times the channel k (for k ∈ 1, K ) was selected up-to time t -1, for t ≥ 0 for any t ∈ N,

N k (t) = t-1 τ =0 1(C(τ) = k), ( 10
)
where 1 is an indicator function that is equal to 1, if the IoT device chooses, for its τ -th transmission, the channel k, and 0 otherwise. The empirical mean estimator µ k (t) of channel k is defined as the mean reward obtained up-to time t -1,

µ k (t) = 1 N k (t) t-1 τ =0 r k (τ )1(C(τ ) = k). ( 11
)
where r k (t) is the reward obtained after transmission in channel k at time t (1 for a successful transmission, and 0 otherwise) A confidence term B k (t) is given by [START_REF] Auer | The Non-Stochastic Multi-Armed Bandit Problem[END_REF],

B k (t) = α log(t)/N k (t), (12)
where α refers to an exploration coefficient2 , that we chose equal to 1/2, as suggested in [START_REF] Audibert | Tuning bandit algorithms in stochastic environments[END_REF] and as done in previous works [START_REF] Bonnefoi | Improvement of the LP-WAN AMI backhaul's latency thanks to reinforcement learning algorithms[END_REF], [START_REF] Bonnefoi | Multi-Armed Bandit Learning in IoT Networks: Learning helps even in nonstationary settings[END_REF]. Then, an upper confidence bound in each channel k is defined as

U k (t) = µ k (t) + B k (t). (13)
Finally, the transmission channel at time step t is the one maximizing this UCB index U k (t), as it is the one expected to be the best one at the current time step t,

C(t) = arg max 1≤k≤K U k (t). ( 14
)
The UCB algorithm is implemented independently by each device, and we present it in Algorithm 1. Note that a device using this first approach is only able to select a channel for the first and all the corresponding retransmissions of a packet.

for t = 0, . . . , T do Compute for each channel U k (t) = µ k (t) + B k (t).
following Eqs. ( 10), [START_REF] Besson | Multi-Player Bandits Revisited[END_REF], and ( 12); Transmit in channel C(t) = arg max 1≤k≤K U k (t); Reward r C(t) (t) = 1, if Ack is received, else 0; end Algorithm 1: The UCB algorithm for channel selection.

V. PROPOSED HEURISTICS

A device that implements the UCB algorithm is led to focus is transmissions and retransmissions in the channel which has been identified as the best. As explained in Section III, focusing in one channel increases the collision probability in retransmissions. In this Section, we describe the proposed heuristics for the channel selection in a retransmission. It is carried out taking into account that a device can incorporate a different channel selection strategy while being in a backoff state. Hence, a natural question is to evaluate whether using this additional contextual information can improve the performance of a learning policy.

For that end, all of our heuristics comprise two stages: the first stage is a UCB algorithm employed for the first attempt to transmit, and the second stage is another algorithm used for channel selections for the next retransmissions.

We present below four heuristics for this second stage (short names in "quotes" correspond to the legend on Figures 3,4).

A. Uniform random retransmission ("Random")

In this first proposal, the device uses a random channel selection, following a uniform distribution (in 1, K ). It is described below in Algorithm 2.

B. UCB for retransmission ("Only UCB")

Instead of applying a random channel selection, another heuristic is to use a second UCB algorithm in the second stage. In other words, we expect that this algorithm is able to learn the best channel to retransmit a packet. It is described in Algorithm 3, and it is still a practical approach, since the storage requirements and time complexity remains linear w.r.t. the number of channels K (i.e., of order O(K)).

Note that, we use the superscript ( r ) to denote the variables µ r k (t), B r k (t) and U r k (t), related to the UCB algorithm employed for the retransmission.

C. K different UCBs for retransmission ("K UCB")

Another heuristic is to not use the same algorithm no matter where the collision occurred, but to use K different UCB for t = 0, . . . , T do if First packet transmission then Use first-stage UCB as in Algorithm 1. else // Packet retransmission with UCB r Compute for each channel U r k (t) = µ r k (t) + B r k (t) following Eqs. ( 10), [START_REF] Besson | Multi-Player Bandits Revisited[END_REF], and ( 12

); Transmit in channel C r (t) = arg max 1≤k≤K U r k (t); Reward r r C r (t) (t) = 1, if Ack is received, else 0; end end
Algorithm 3: UCB for retransmission. algorithms. Meaning that after a failed first transmission in channel j, the device relies on the k-th algorithm to decide its retransmission. The corresponding algorithm is depicted in Algorithm 4. Each of these algorithms are denoted using the superscript ( j ), for j ∈ 1, K .

Although, this approach increases the complexity and storage requirements (of order O(K 2 )). For our LPWA networks of interest, such as LoRaWAN, the cost of its implementation is still affordable, since a small number of channels is used. For instance, for K = 4 channels, the memory to store K + 1 = 5 algorithms is of the order of the requirements to storing one.

for t = 0, . . . , T do // At every time step if First packet transmission then Use first-stage UCB as in Algorithm 1. else // Packet retransmission with UCB j j ← last channel selected by first-stage UCB; Compute for each channel U j k (t) = µ k j (t) + B j k (t) following Eqs. [START_REF] Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF], [START_REF] Besson | Multi-Player Bandits Revisited[END_REF], and [START_REF] Boursier | SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits[END_REF]; Transmit in channel C j (t) = arg max 1≤k≤K U j k (t); Reward r j C j (t) (t) = 1 if Ack is received, else 0; end end Algorithm 4: K different UCBs for retransmission.

D. Delayed UCB for retransmission ("Delayed UCB")

This last heuristic is a composite of the random retransmission (Algorithm 2) and the UCB retransmission (Algorithm 3) approaches. Instead of starting the second stage UCB directly from the first retransmission, we introduce a fixed delay ∆ ∈ N, ∆ ≥ 1, and start to rely on the second stage UCB after ∆ transmissions. The selection for the first steps is handled with the random retransmission.

The idea behind this delay is to allow the first stage UCB to start learning the best channel, before starting the second stage UCB (see details in Algorithm 5). The number of transmissions to wait before applying the second algorithm is denoted by ∆, it has to be fixed before-hand.

Note that, we use the superscript ( d ) to denote the variables related to the delayed second-stage UCB algorithm.

VI. SIMULATIONS TO COMPARE OUR HEURISTICS

We simulate our network considering N devices following the contention Markov process described in Section II, and a LoRa standard with K = 4 channels. Each device is set to transmit with a fixed probability p = 10 -3 , i.e., a packet about every 20 minutes for time slots of 1 s.

For the evaluation of the proposed heuristics, a total number of T = 20 × 10 4 time slots is considered, and the results are averaged over 10 3 independent random simulations.

In a first scenario, we consider a total number of N = 1000 IoT devices, with a non-uniform repartition of static devices given by 10%, 30%, 30%, 30% for the four channels. In other words, the channels are occupied 10%, 30%, 30%, and 30% of time, and the contention Markov process considered is given by M = 5, and m = 5. In Fig. 3, we show the successful transmission rate versus the number of slots, for all the proposed heuristics.

A first result is that all the heuristics clearly outperform the non-learning approach that simply use random channel selection for both transmissions and retransmissions (i.e., the no UCB curve). The improvement of the heuristics over the nonlearning approach is evident, and for every heuristic that use a kind of learning mechanism it can be observed a successful transmission rate that increases rapidly (or equivalently an PLR decreasing). Moreover, all of these approaches show a fast convergence making them suitable for the targeted application. It is also worths mentioning that the employment of the same UCB algorithm for retransmissions denoted here as "Only UCB" achieves the best performance, while a "Random" retransmission features a slight degradation. This result can be explained as follows: the loss of performance related to the separation of information for several algorithms is greater than the gain obtained by considering the first transmissions and retransmissions separately.

We also consider in our analysis the case where M = 5, and m = 10 using ALOHA protocol, a statistic distribution of the devices about 40%, 30%, 20%, 10% for the four channels, and N = 2000 IoT devices. The corresponding results are depicted in Fig. 4. In this case the successful transmission rate is degraded compared with achieved results in Fig. 3, this can be explained with the fact that we are considering in our network more devices that increase the collision probability. It is important to highlight, that the "Random" retransmission heuristic shows a poor performance in comparison to the other heuristics, and it can be attributed to the fact that the number of retransmission is increased, and consequently a learning approach is able to take advantage of it. Furthermore, the "UCB", "K UCB" and "Delayed UCB" heuristics behave similarly than "Only UCB", after a similar convergence time. The conclusions we can draw from depicted results are twofold. First, MAB learning algorithms are very useful to reduce the collision rate in LPWA networks, a gain of upto 30% of successful transmission rate is observed after convergence. A second conclusion that can be highlighted is that, using learning mechanisms for retransmissions can be an interesting way to reduce collisions in networks with massive deployments of IoT as this can be checked in Fig. 4, where the random retransmission heuristic is not very advantageous in front of the UCB-based approaches that use learning for channel selection during the retransmission procedure.

VII. CONCLUSIONS

In this paper, we presented a retransmission model of LPWA networks based on an ALOHA protocol, slotted both in time and frequency, in which dynamic IoT devices can use machine learning algorithms, to improve their PLR when accessing the network. The main novelty of this model is to address the packet retransmissions upon radio collision, by using a Multi-Armed Bandit framework. We presented and evaluated several learning heuristic that try to learn how to transmit and retransmit in a smarter way, by using the UCB algorithm for channel selection for first transmission, and different proposals based on UCB for the retransmissions upon collisions.

We showed that incorporating learning for the transmission is needed to achieve optimal performance, with significant gain in terms of successful transmission rate in networks with a large number of devices (up-to 30% in the example network). Our empirical simulations show that each of our proposed heuristic outperforms a naive random access scheme. Surprisingly, the main take-away message is that a simple UCB learning approach, that retransmit in the same channel, turns out to perform as well as more complicated heuristics.

Future works

The utility and impact of the proposed approaches for LPWA networks motivates us to address several subjects as future works. Among them, the non-stationarity of the channel occupancy caused by the learning policy employed by the IoT devices. For that end, modifications of MAB algorithms have been proposed, such as Sliding-Window-UCB or Discounted-UCB [START_REF] Garivier | On upper-confidence bound policies for switching bandit problems[END_REF] or more recently M-UCB [START_REF] Cao | Nearly Optimal Adaptive Procedure for Piecewise-Stationary Bandit: a Change-Point Detection Approach[END_REF], that nevertheless have not been explored for the targeted problem.

In order to validate our results in a realistic experimental setting and not only with simulations, future works include a hardware implementation of the analyzed models to complete our recent works [START_REF] Darak | Spectrum Utilization and Reconfiguration Cost Comparison of Various Decision Making Policies for Opportunistic Spectrum Access Using Real Radio Signals[END_REF], [START_REF] Besson | MALIN: an Implementation of Multi-Armed Bandits Learning Schemes for Internet-of-things Networks[END_REF]. A hardware demonstrator could be also benefit to study other settings by removing some hypotheses, for instance by studying a similar model in nonslotted time.

Note on the simulation code

Fig. 1 .

 1 Fig. 1. All devices in the network follow the same Markov behavior.

Fig. 2 .

 2 Fig. 2. Our proposed approximation for the probability of collision at the second transmission. It is more precise for smaller values of N .

Algorithm 2 :

 2 for t = 0, . . . , T do if First packet transmission then Use first-stage UCB as in Algorithm 1. else // Random retransmission Transmit in channel C(t) ∼ U(1, . . . , K); end end Uniform random retransmission.

  for t = 0, . . . , T do // At every time step if First packet transmission then Use first-stage UCB as in Algorithm 1. else if t ≤ ∆ then // Random selection with UCB d Transmit randomly in a channel C(t) ∼ U (1, . . . , K).

	else	// Delayed UCB
		Compute for each channel U d k (t) = µ d k (t) + B d k (t)
		following Eqs. (10), (11), and (12);
		Transmit in channel C d (t) = arg max 1≤k≤K U d k (t);
		Reward r d C d (t) (t) = 1 if Ack is received, else 0;
	end
	end
	Algorithm 5: Delayed UCB for retransmission.

  Comparison among the exposed heuristics for the retransmission: Only UCB, Random, UCB, K UCB, and Delayed UCB. First scenario: learning helps but learning to retransmit smartly is not needed, as we observe that the random retransmission heuristic achieves similar performance than the others.

		0.88
		0.86
		0.84
	Successful transmission rate	0.72 0.74 0.76 0.78 0.8 0.82								Only UCB Random UCB
										K UCB
		0.7								Delayed UCB no UCB
		0.68
		0	2	4	6	8	10	12	14	16	18	20
						Number of slots (unit is 10000 slots)
	Fig. 3.

Note that, for unlicensed bands, this definition also encompasses any device following a different standard or trying to establish communication with gateways of other networks.

In fact, the larger this coefficient is, the longer the exploration, while the UCB algorithm is proven to be order optimal for α > 0.5[START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF], and has reported a good performance for lower values of α > 0.

The source code (MATLAB or Octave) used for the simulations and the figures is open-sourced under the MIT License, at Bitbucket.org/scee_ietr/ucb_smart_retrans.


Torque-Based Balancing for a Humanoid Robot Performing High-Force Interaction Tasks

Firas Abi-Farraj 1 , Bernd Henze 2 , Christian Ott 2 , Paolo Robuffo Giordano 1 , and Máximo A. Roa 2

Abstract-Balancing is a critical feature for a robot interacting with an unstructured environment. The balancing control should account for unknown perturbation forces that might destabilize the robot when performing the intended tasks. In the case of humanoid robots this challenge is higher due to the inherent difficulties of balancing a robot on two legs, resulting in a rather small footprint. Approaches for enabling a good balancing behavior on humanoid robots traditionally rely on whole-body balancing approaches. This paper extends a passivity-based whole-body balancing framework to guarantee the equilibrium of a humanoid robot while performing different interaction tasks where the (high) task forces acting on the robot are difficult to foresee. Instead of controlling the center of mass, the proposed controller directly uses information from the Gravito-Inertial Wrench Cone to guarantee the feasibility of the balancing forces. The performance of the approach is validated in a number of successful experimental tests.

Index Terms-Humanoid Robots, Force Control

I. INTRODUCTION

H UMANOID robots offer an embodiment that could allow them to enter environments made for humans and utilize standard tools and devices, in order to support and replace humans in dangerous and physically demanding tasks. One example of such expectations on humanoid robots was staged during the DARPA Robotics Challenge (DRC), where robots were required to perform simple tasks in disaster-like scenarios such as driving a car, opening doors, walking on rough terrains, and using simple tools. However, real-life disaster scenarios are even more demanding; one would expect the robot to be capable of moving heavy objects (rocks, debris), operating heavy machinery, and employing tools and devices that require both skill and strength, such as hydraulic rescue tools. Performing such tasks requires suitable control frameworks for dealing with the interaction forces generated during the execution of the task, while still accounting for the balance of the robotic platform.

Accounting for interaction forces of the robot with the environment can be achieved mainly in two different ways. A straightforward approach is to separate interaction and balancing tasks, which usually translates into considering two independent controllers for the lower and upper body of the robot [START_REF] Ibanez | Unified preview control for humanoid postural stability and upper-limb interaction adaptation[END_REF], [START_REF] Ott | Kinesthetic teaching of humanoid motion based on whole-body compliance control with interaction-aware balancing[END_REF]. Forces coming from interactions with the environment using the upper body are considered as a disturbance input by the underlying balancing control, which guarantees the robot balance using only the joints in the lower body. The consideration of force distribution between lower and upper body at the same time can also be achieved through wholebody control frameworks, which exploit the capabilities of redundant robots to deal with multiple tasks [3]- [START_REF] Henze | Multi-contact balancing of humanoid robots in confined spaces: Utilizing knee contacts[END_REF]. Different whole-body balancing controllers have been proposed based mainly on two approaches: solving the inverse kinematics or dynamics of the robot [START_REF] Sentis | Compliant control of whole-body multi-contact behaviors in humanoid robots[END_REF], [START_REF] Stephens | Push recovery by stepping for humanoid robots with force controlled joints[END_REF]- [START_REF] Mistry | Inverse dynamics control of floating base systems using orthogonal decomposition[END_REF], or using passivity-based approaches [START_REF] Henze | Passivity-based whole-body balancing for torque-controlled humanoid robots in multi-contact scenarios[END_REF], [START_REF] Hyon | Full-body compliant human-humanoid interaction: Balancing in the presence of unknown external forces[END_REF], [START_REF] Ott | Posture and balance control for biped robots based on contact force optimization[END_REF]. A subset of the whole-body control frameworks feature a hierarchical architecture that allows for multiple control objectives [START_REF] Sentis | Compliant control of whole-body multi-contact behaviors in humanoid robots[END_REF], [START_REF] Henze | An approach to combine balancing with hierarchical whole-body control for legged humanoid robots[END_REF], [START_REF] Escande | Hierarchical quadratic programming: Fast online humanoid-robot motion generation[END_REF]. In [START_REF] Henze | Multi-contact balancing of humanoid robots in confined spaces: Utilizing knee contacts[END_REF], a hierarchical approach was used to balance on contacts scattered over the whole body of the robot.

When it is foreseen that high forces could arise in the interaction of the robot with the environment, the robot can plan in advance the best posture and force distribution required to deal with the task [START_REF] Murooka | Wholebody pushing manipulation with contact posture planning of large and heavy object for humanoid robot[END_REF]. The planning has to consider several factors such as kinematic limitations, actuator constraints, or characteristics of the supporting contacts. A recent method to account for the contact properties is based on the computation of the so-called Gravito-Inertial Wrench Cone (GIWC), which provides the maximum perturbations that the robot can resist at a given configuration, and/or the maximum interaction force that the robot can generate at a given posture [START_REF] Caron | Multi-contact walking pattern generation based on model preview control of 3D COM accelerations[END_REF]- [START_REF] Prete | Fast algorithms to test robust static equilibrium for legged robots[END_REF]. However, this polyhedron has been so far used for (offline) planning and not for instantaneous control of the robot posture. In this context, the main goal of this paper is to leverage the concept of the GIWC and apply it to instantaneous control of the robot posture. A whole-body controller usually requires an explicit goal provided for the center of mass (CoM) trajectory. This paper does not specify an explicit location for the CoM; instead, the CoM is moved such that the contact wrenches required for balancing the interaction force are feasible for each contact configuration. In that way, the polyhedron of feasible balancing wrenches or GIWC is used to ensure the online stability of the humanoid (with respect to the contact properties) while interacting with an unknown environment.

II. PRELIMINARIES AND BACKGROUND A. Dynamic Model

In the field of legged humanoid robotics it is common to use dynamic models with a free-floating base, as they provide a higher flexibility regarding contact changes compared to dynamic models with a fixed base. In general, a central body within the kinematic structure of the robot is chosen as base link, e.g. the hip or the trunk. Some works also employ the center of mass (CoM) as base, since it represents an essential point for balancing. Here, we will follow [START_REF] Henze | Passivity-based whole-body balancing for torque-controlled humanoid robots in multi-contact scenarios[END_REF] by defining a CoM frame C, which is located at the CoM and has the same orientation of the hip. Let x c ∈ R3 and R c ∈ SO(3) denote the position and orientation of the frame C with respect to the world frame W. The corresponding translational and rotational velocities are given by ẋc and ω c , respectively. Considering the n joint angles q ∈ R n and v c = ( ẋT c , ω T c ) T , the dynamics of the humanoid robot is given by

M vc q ν +C v c q ν + mg 0 0 g = 0 τ + τ ext . (1)
Herein, M ∈ R (6+n)×(6+n) and C ∈ R (6+n)×(6+n) represent the inertia and Coriolis/centrifugal matrix, respectively. The gravitational torques are given by g ∈ R 6+n , with m denoting the total mass of the robot and g 0 ∈ R 6 the gravitational acceleration 1 . The joint torques are denoted by τ ∈ R n . The influence of external wrenches acting on the robot is taken into account by the generalized torque vector τ ext ∈ R 6+n . Let us divide the Ψ end-effectors into two subgroups as in [START_REF] Henze | Passivity-based whole-body balancing for torque-controlled humanoid robots in multi-contact scenarios[END_REF]: the first group is referred to as "balancing end-effectors" (bal) and contains the ψ end-effectors that are used by the robot to support itself (usually the feet). The remaining endeffectors are called "interaction end-effectors" (int), because they can still be used for a manipulation or interaction task (usually the hands). With this distinction, the Cartesian velocities of the end-effectors v ∈ R 6Ψ are given by

v = v bal v int = J bal J int ν = J ν (2)
with the Jacobian matrix J ∈ R 6Ψ×(6+n) and 6+n) . If all external disturbances act solely at the end-effectors, τ ext simplifies to

v bal ∈ R 6ψ , v int ∈ R 6(Ψ-ψ) , J bal ∈ R 6ψ×(6+n) , J int ∈ R 6(Ψ-ψ)×(
τ ext = J T F ext . (3)

B. Overview of the Compliant Balancing Controller

This section provides a brief summary of our balancing controller, presented in detail in [START_REF] Henze | Passivity-based whole-body balancing for torque-controlled humanoid robots in multi-contact scenarios[END_REF]. The controller stabilizes the CoM by a Cartesian compliance, which generates a wrench F c ∈ R 6 at the CoM frame C. Each one of the interaction end-effectors is stabilized by another Cartesian compliance, with the resulting wrenches stacked into F int ∈ R 6(Ψ-ψ) . In order to support the robot, the control algorithm computes a suitable set of balancing wrenches F opt bal ∈ R 6Ψ by minimizing the following quadratic optimization problem

F opt bal = argmin F bal F bal -F def bal T Q F bal -F def bal ( 4
)
with respect to

Ad T bal F bal + Ad T int F int = mg 0 -F c (5)
and

f k,z ≥ f min k,z , δ min k,x/y ≤ δ k,x/y ≤ δ max k,x/y , f k,x/y ≤ μk f k,z . (6)
The cost function (4) minimizes the deviation of F bal from a default wrench distribution2 F def bal based on the positive definite weighting matrix Q ∈ R 6ψ×6ψ . The equality constraint [START_REF] Henze | Passivity-based whole-body balancing for torque-controlled humanoid robots in multi-contact scenarios[END_REF] represents the underactuation of the base by demanding that the influence of all commanded end-effector wrenches (F bal , F int ) on the CoM must sum up to the compliance wrench F c plus gravity. For this, the Jacobian matrices J bal = [ Adbal Jbal ] and J int = [ Adint Jint ] are divided into Ad bal ∈ R 6ψ×6 , Ad int ∈ R 6(Ψ-ψ)×6 , J bal ∈ R 6ψ×n , and J int ∈ R 6(Ψ-ψ)×n . The first two are the stacked adjoint matrices of each endeffector, which relate a motion of the CoM frame C with a motion of the end-effectors. The matrices J bal and J int map a motion of the joints to a motion of the end-effectors. The inequality constraints ( 6) describe the contact model to which F bal is subjected to in order to account for unilaterality, location of the Center of Pressure (CoP), and friction of the balancing contacts. For each end-effector wrench within F bal , the force perpendicular to the contact surface has a lower bound given as a minimum contact force f min k,z in order to prevent the end-effector from lifting off 3 . Slippage is prevented by constraining the tangential forces f k,x/y to the friction cone given by μk . The CoP δ k is constrained to the interior of the contact surface via δ min/max k,x/y to prevent the end-effector from tilting.

After computing a suitable wrench distribution F opt bal , the end-effector wrenches are mapped to joint space via

τ = -J T bal J T int F opt bal F int . (7)
III. CONTROLLER DESIGN

In the architecture described in [START_REF] Henze | Passivity-based whole-body balancing for torque-controlled humanoid robots in multi-contact scenarios[END_REF], a Cartesian compliance defines the wrench F c to be applied at the CoM in order to stabilize it at a desired configuration. This approach proved efficient for balancing, and showed significant robustness to noise and external disturbances. However, the amount of force and torque the robot can apply with the interaction endeffectors is limited because the balancing contacts must provide an appropriate counter-force constrained by the contact model [START_REF] Henze | An approach to combine balancing with hierarchical whole-body control for legged humanoid robots[END_REF]. With that in mind, a new approach for controlling the wrench F c on the CoM while accounting for the interaction forces between the robot and the environment is proposed in this paper. The proposed architecture is based on the controller presented in [START_REF] Henze | Passivity-based whole-body balancing for torque-controlled humanoid robots in multi-contact scenarios[END_REF] and aims at ensuring the feasibility of the needed balancing wrenches as a function of the contact configuration of the balancing end-effectors by moving the CoM accordingly. The control is based on the polyhedron of feasible balancing wrenches calculated from the current contact configuration, with no need for calculating the support polygon. The actuator limitations are not considered in the described controller, but their inclusion is an interesting direction for future exploration.

A. Force Polyhedron and Support Polygon

The support polygon of a humanoid robot is the region in which the vertical projection of the CoM must lie so that the balancing end-effectors can carry statically the robot's weight. In case that the humanoid is moving on a horizontal plane, the support polygon S is the convex hull of the contact areas with the ground, mainly corresponding to the feet of the humanoid (Fig. 2). However, in a multi-contact scenario where other parts of the humanoid's body are used for balancing (e.g. the hands), the calculation of the support polygon gets more complicated [START_REF] Hirukawa | A universal stability criterion of the foot contact of legged robots -adios ZMP[END_REF]. The same holds in the case of non-horizontal or non-planar contact surfaces (e.g. rough terrain). The support polygon can be calculated from the GIWC, which is the set of wrenches that the balancing end-effectors can apply at a particular contact configuration. The contact configuration, referred to hereafter by Υ, is the pose of the end-effectors used for balancing in the world frame. It is dependent on the contact configuration itself and the contact model (see eq. ( 6)) specifying the maximum load that each end-effector can carry. The contact model can be re-written into a polyhedron ξ i = {F bal,i :

A i F bal,i ≤ b i } representing
the set of feasible wrenches for each balancing end-effector, where F bal,i ∈ R 6 (see [START_REF] Caron | Leveraging cone double description for multi-contact stability of humanoids with applications to statics and dynamics[END_REF] for details). The GIWC can be calculated via the Minkowski-Sum of ξ i , resulting in the wrench polyhedron ξ defined as

ξ = { w F bal,t : A w F bal,t ≤ b} (8)
where A = [ A1 ... An ] T ∈ R m×6 is a constant matrix and b = ( b1 ... bm ) T ∈ R m a constant vector. The total wrench w F bal,t ∈ R 6 is defined in the world frame W and is related to F bal,i via w F bal,t = Ad T c Ad T bal F bal . The adjoint matrix Ad c maps the total wrench from the CoM frame to the world frame. Note that the resulting matrix w Ad bal = Ad bal Ad c is constant, as the balancing contacts are stationary with respect to the world frame W. Any wrench w F satisfying ( 8) is feasible and can be applied by the balancing end-effectors in the current contact configuration Υ. If Υ changes, ξ can be re-computed accordingly. We refer the reader to [START_REF] Caron | Leveraging cone double description for multi-contact stability of humanoids with applications to statics and dynamics[END_REF] for more details on the calculation of the GIWC.

𝑤 𝑭 𝑏𝑎𝑙,𝑡

𝑨 𝑤 𝑭 𝑏𝑎𝑙,𝒕 ≤ 𝒃 The support polygon is calculated at a particular pre-defined point by projecting ξ on a certain plane of interest [START_REF] Caron | ZMP support areas for multicontact mobility under frictional constraints[END_REF]. For instance, in the case of a robot standing on horizontal ground, ξ is projected on the horizontal plane at a point located on the ground to retrieve the support polygon. This solution is, however, clearly suboptimal since ξ corresponds to a whole polyhedron (8), and is not just restricted to a planar projection. Therefore in this paper we propose to define a control law at the level of the balancing wrench itself, without the need of calculating the support polygon.

B. Proposed Controller

Assuming a quasi-static scenario (F c ≈ 0) and that all external forces/torques act only at the end-effectors, eq. ( 5) describing the forces at the CoM and defined at the origin of the world frame W can then be written as Note that F int represents the commanded wrenches of the compliances arising from the interaction task. The adjoint matrices w Ad c and w Ad int are a function of the CoM location x c and of the position x int,i of each interaction end-effector, respectively. From the definition of ξ in (8), the balancing wrenches are feasible if

w F bal,t + w Ad T int F int + w Ad T c mg 0 = 0. ( 9
)
A w F bal,t ≤ b, (10)
as detailed in [START_REF] Caron | Leveraging cone double description for multi-contact stability of humanoids with applications to statics and dynamics[END_REF].

Assuming that the robot starts from a feasible configuration, we define a "distance" measure d i from the current balancing wrench w F bal,t to the i th face of the polyhedron ξ given by {F bal,i :

A i F bal,i = b i }, such that d i ( w F bal,t ) = b i -A i w F bal,t ||A i || . ( 11
)
While there are infinite ways of expressing the GIWC, the measure d i is unique and scale invariant. We however assume that there are no duplicate surfaces in [START_REF] Mistry | Inverse dynamics control of floating base systems using orthogonal decomposition[END_REF].

On the other hand, from [START_REF] Righetti | Optimal distribution of contact forces with inverse dynamics control[END_REF] we know that

w F bal,t = -w Ad T int F int -w Ad T c mg 0 = -w Ad T int F int - I 3×3 0 3×3 [x c ] x I 3×3 mg 0 = -w Ad T int F int - mg 0,x 0 3×3 + 0 3×3 [mg 0,x ] x x c = -w Ad T int F int - mg 0,x 0 3×3 + mg     0 3×2 0 -1 1 0 0 1×3     x c y c , (12)
where [•] x denotes the skew-symmetric operator, and

g 0,x ∈ R 3 is the linear component of g 0 = ( g T 0,x 03 ) T , with g T 0,x = [0 0 -g] T .
As no previous knowledge of the environment is assumed, F int in the above equation is unknown, which leaves x c and y c as the only controllable variables.

The balancing end-effectors can apply the required balancing wrench w F bal,t if and only if d i > 0 ∀i. We then define a potential H to encode the proximity of the balancing wrench to the limits of ξ. H needs to be a monotone function that grows infinite as d → 0, in order to reflect the loss of balance in such a case. Among the many ways to design such a potential, we empirically choose H to be

H(x c , y c ) = i 1 d i (x c , y c ) . (13)
To simplify the notation, H(x c , y c ) and d i (x c , y c ) are respectively referred to by H and d i in the rest of the paper. Since ξ is convex, the balance of the humanoid robot can be ensured by defining a gradient-descent control law on H (Fig. 4). The gradient of H with respect to [x c , y c ] T can be written as

∂H ∂[x c , y c ] T = mg i A i d 2 i ||A i ||     0 3×2 0 -1 1 0 0 1×3     (14)
As the only CoM parameters impacting H are x c and y c , the control wrench F c to be applied at the CoM (eq. ( 5)) can be divided into two parts

F c = [F c,b F c,i ] T , where F c,b = [F c,x F c,y ] T ∈ R 2 ensures
the balance of the robot by acting on the x and y components of x c , while

F c,i = [F c,z F c,ω ] T ∈ R 4 commands
F c,b = -k b ∂H ∂[x c y c ] T T -D c,b ẋc ẏc , (15)
where D c,b ∈ R 2×2 is a damping matrix, and k b is a control gain. Note that while the interaction forces, F int , cannot be predicted, they are accounted for in the term

1/d 2 i in ∂H/∂[x c y c ] T .
It is also important to indicate that F int actually corresponds to the commanded forces on the interacting end-effectors (which are controlled in compliance), and it is not retrieved from the measured torques. On the other hand, F c,i is defined as an impedance-based control task to allow the control of z c and R c as described in section II-B.

C. Contact Switching

While a humanoid can balance on its feet, different contact configurations may be required in cases where, for example, the ground is not planar or where the robot needs to use its feet to interact with the environment. Switching from a particular contact configuration to another one requires shifting the supporting forces from some end-effectors to others, depending on the given contact configuration. In this section, we describe an autonomous contact-switching algorithm that handles this "weight shifting" process in the wrench space when the endeffectors are already in position. A typical situation happens when the two feet of the robot are on the ground and one hand is in contact with a wall. The robot can switch contacts to balance using any possible combination of the three endeffectors, i.e. the two feet, the two feet and the hand, or one foot and the hand. The three end-effectors are assumed to be static during the switching process. In order to handle cases where the balancing end-effectors should be moved (e.g. for stepping), this algorithm needs to be topped with a suitable planner.

Assume the robot is balancing on a particular contact configuration Υ 1 , with ψ 1 end-effectors, and needs to switch to a different contact configuration Υ 2 , with ψ 2 end-effectors. Two GIWC, ξ 1 and ξ 2 , can be defined corresponding to contact configurations Υ 1 and Υ 2 respectively. The goal of the contact switch is to 'move' w F bal,t from polyhedron ξ 1 to polyhedron ξ 2 . To this end, we retrieve the optimal CoM position, [x c , y c ] opt,x , corresponding to each polyhedron ξ x by solving min

[xc,yc] H ξ x , (16)
where H ξ x is the potential in ( 13) calculated for the GIWC ξ x . [x c , y c ] opt,x can then be substituted in [START_REF] Ott | Posture and balance control for biped robots based on contact force optimization[END_REF] to retrieve the optimal balancing wrench w F opt,x corresponding to ξ x . Note that when the robot is in contact configuration ξ x , the gradient descent controller defined in section II-B maintains w F bal,t at w F opt,x , which ensures a smooth back and forth switch between the two controllers.

The contact-switching controller aims then to drive w F bal,t from w F opt,1 to w F opt,2 (i.e. from polyhedron ξ 1 to polyhedron ξ 2 ). To this end, we define a quadratic contact-switch potential H cs as

H cs = ( w F bal,d (t) -w F bal ) T ( w F bal,d (t) -w F bal ) (17)
where w F bal,d = (1 -α) w F opt,1 + α w F opt,2 is the desired balancing wrench that shifts smoothly from w F opt,1 to w F opt,2 as α : 0 → 1. Since the contacts corresponding to both ξ 1 and ξ 2 are established during the switch, and as all the computed wrench polyhedrons are convex, w F bal,d necessarily lies within the Minkowski-Sum of ξ 1 and ξ 2 , which ensures its feasibility. Finally, and similarly to section II-B, the wrench F c,cs to be applied at the CoM is defined as

F c,cs = -k cs ∂H cs ∂[x c y c ] T T -D c,b ẋc ẏc , (18)
where k cs is a control gain. The resulting overall algorithm is detailed in Alg. 1. For this algorithm, α and Hcs are control variables to be tuned.

IV. EXPERIMENTS AND RESULTS

A. Experimental Setup

The proposed approach was implemented on TORO, the torque-controlled humanoid robot developed at DLR [START_REF] Englsberger | Overview of the torque-controlled humanoid robot TORO[END_REF]. The robot has 27 DoF (plus 12 DoF at the hands), a total height of 1.74 m and a weight of 76.4 kg. 25 of the joints, located at the arms, legs and hip, are based on the DLR-KUKA LBR (Lightweight robot arm), and allow for both position and torque control modes. Besides position and torque sensing at the LBR-based joints, TORO has an IMU at the trunk and a 6-DoF Force-Torque sensor at each foot.

B. Experimental results

Several experiments were performed to validate the proposed approach. They are demonstrated in the attached video (available also at https://youtu.be/TBl49-XvnRE). In this section, we discuss four experiments that demonstrate the applicability of the proposed architecture for balancing while interacting with the environment, and for automatic contact switching.

1) Experiment 1. Carrying a heavy box: The experiment consists of a person passing to the robot a box weighing 25 kg (nearly one third of the robot's weight), and then taking it back. The hands of the robot are controlled in impedance mode and are subject to the Cartesian end-effector compliance described in section II-B. No feed-forward forces were fed to the arms to counteract the weight of the box, which is totally unknown to the controller. Figure 5 shows the results of the experiment. The two dashed lines denote the instances when the robot takes the box from the human (t=6.5 s) and when it gives it back (t=19.5 s). Figures 5a and5b show the commanded linear compliance forces on the right and left hand respectively, which reach a maximum of 142 N on the right and 134 N on the left hand. Figure 5c shows the x and y coordinates of the CoM, which is autonomously shifted backwards due to [START_REF] Caron | Multi-contact walking pattern generation based on model preview control of 3D COM accelerations[END_REF] to compensate for the weight of the box. This is also reflected in Fig. 5d where the ZMP, measured from sensors on the feet of the robot, is rapidly stabilized after the disruptions during the application and the release of the weight. The sensors used for measuring the ZMP position are relatively noisy, and this is visible in the initial (t < 3 s) and final (t > 20 s) stages of the experiment. The estimation of the CoM position (calculated from joint encoders as in [START_REF] Henze | Passivity-based whole-body balancing for torque-controlled humanoid robots in multi-contact scenarios[END_REF]) is, on the other hand, more smooth and accurate. The trajectories of both ZMP and CoM throughout the experiment are visualized in Fig. 5e over the support polygon. Note that the ZMP remains in the support area throughout the whole experiment. Despite the disruptions during the box handover, the ZMP remains almost stationary while the CoM is shifted to the back in order to compensate for the weight of the box. It is worth noting here that the maximum weight of the box was limited by the maximum torques that the joints can deliver (in particular, the limit of 40 Nm at the elbow was critical). In the attached video, it is visible that the elbows were stretched when carrying the mass of 25 kg. 2) Experiment 2. Table Pushing: In the second experiment, the robot is placed in front of a table and is required to push it forward. The weight of the table and the friction parameters with the ground are unknown (as it is usually the case in such situations), the push-forward motion is planned as a forward Cartesian trajectory for the two hands with no feedforward forces. Figures 6a and6b show the commanded linear compliance forces, which reach an overall magnitude of 79.5 N and 60.8 N on the right and left hands, respectively. Figure 6c shows the x and y coordinates of the CoM, which shifts significantly forward to compensate for the forces applied by the interacting end-effectors. In fact, the CoM leaves the ground support area toward the front, which would result in an immediate fall without the interaction forces. This is reflected in Fig. 6d and Fig. 6e, which depict the trajectory of the ZMP. Note that the contact configuration, and therefore the ZMP support area, is different with respect to the first experiment. Figure 6e shows that the ZMP is significantly far from the boundaries of its support area throughout the experiment. It is slightly shifted from the center due to noisy measurements and minor uncertainties in the model of the robot.

3) Experiment 3. Interacting with the Right Foot: The robot in this experiment is balancing using its left foot and right hand, while the right foot and the left hand are free endeffectors available for interaction. The robot uses its right foot to push an object (a fire extinguisher of mass 19.8 kg). Again, the environment and its properties are unknown to the controller, and the motion of the foot is simply planned in Cartesian space. Figure 7 describes the results of the performed experiments. Figure 7a shows the commanded compliance forces on the right foot, which increase in magnitude up to 70.3 N. The different phases of the experiment are clearly distinguishable on the graph as the foot establishes contact with the object (force starts to increase), starts pushing it (the force is at its maximum) and finally retreats back to its initial position (the force goes back to zero). Figure 7b shows the forces applied by the right hand, which is used for balancing. Note that the applied force maintains a stable behavior as the right foot pushes and releases the object. The threshold for the maximum balancing forces to be applied on the right hand is 100N; this threshold is never reached during the experiment. The motion of the CoM as it counteracts the force applied on the foot by moving slightly to the right is depicted in Fig. 7c and Fig. 7e. The latter shows the trajectory of the CoM over the support area, which is calculated from the contact configuration of the balancing end-effectors (the left foot and the right hand in this case). The left foot, which maintains contact with the ground, is shown in gray. As there is no information about the forces applied on the right hand (no force/pressure sensors available), the ZMP trajectory plotted in Fig. 7e corresponds to the of the left foot (measured with the force-torque sensor in the foot). The mentioned ZMP keeps a relatively constant position throughout the experiment, regardless of the forces applied by the right foot. 4) Experiment 4. Automatic Contact Switching: The fourth experiment aims at validating the automatic contact switching algorithm described in section III-C. Before the beginning of the experiment, the robot (standing on its feet) establishes contact with the structure using its right hand. All three endeffectors (the right hand and both feet) remain in contact throughout the experiment (Fig. 8). At t=0 s, the robot balances on its two feet with no load on its right hand. It then incorporates its right hand as a balancing end-effector and shifts its weight to balance on its feet and its right hand (t=7 s). Finally, it shifts its weight again to balance on its right hand and its left foot, with no load on its right foot (t=15 s). Figure 8a shows the change in the CoM position as the robot shifts from one balancing configuration to another one. The three contact configurations are respectively referred to by Υ f f for balancing on two feet, Υ f f h for balancing on both feet and the right hand, and Υ f h for balancing on the left foot and the right hand. Since a different GIWC exists for each contact configuration, the value of the cost function H, depicting the stability of the robot, is different depending on which GIWC is considered, even if the state of the robot did not change. For example, the robot would be more stable when using all three end-effectors for balancing rather than using only two (with the third being in contact but carrying no weight). This is reflected in Fig. 8b-8d, where the evolution of the potential H for each configuration is shown. The three figures depict H for contact configurations Υ f f , Υ f f h and Υ f h respectively. Note that a lower H reflects a better stability. The regions shaded in gray represent the phases during which the balance switch takes place. During the first phase (t=1→4.4 s) the robot, which was balancing on its two feet with no load on its right hand, incorporates that hand as an additional balancing end-effector. During the second phase (t=7.3→12 s) the robot shifts from balancing on its two feet and its right hand to balancing on its left foot and its right hand, removing all load from the right foot (which can now be lifted if needed).

The results of the experiment showed several interesting characteristics of the architecture and of the proposed potential function H. First, note that the average value of H is lowest for contact configuration Υ f f h at ≈ 3.8e-3 (Fig. 8b). It is higher for contact configuration Υ f f , where it ranges between 4.8e-3 and 5.5e-3 (Fig. 8a), and it is highest for contact configuration Υ f h , where H reaches a maximum of 7.8e-3 (Fig. 8c). Recalling from the definition of H in eq. ( 13) that the lower the potential the better the balance, the results go inline with the intuition that the robot is best balanced using all three end-effectors, and least balanced when balancing on one foot and a hand only. On the other hand, the contact switch is reflected as the robot shifts from configuration Υ f f to Υ f f h , where the potential corresponding to Υ f f increases while that of Υ f f h decreases to its minimum. A similar behavior is observed when switching from Υ f f h to Υ f h , where the potential corresponding to the former increases while that of the latter decreases to its minimum. On the other hand, the degree of variation of each potential reflects as well the of each configuration. We notice that balancing on one foot and one hand is quite sensitive to changes in the posture of the robot, whereas balancing on both feet and the hand is altogether a much more robust posture.

V. CONCLUSIONS In this paper, we have presented a controller for maintaining the balance of torque-controlled humanoid robots in the presence of unknown (and high) external forces. The controller acts at the wrench level to ensure that the needed balancing forces lie within the Gravito-Inertial Wrench Cone (GIWC). The same approach is applied to allow for automatic switching between different contact configurations by acting on the GIWC itself. The efficiency and robustness of the approach was demonstrated by several experiments that tested the robot hardware with forces up to the order of 250 N (≈ 1/3 of the robot's weight). The robot interacted with and manipulated the environment using one hand, both hands and even one foot, while the controller was handling the different force directions and contact configurations.

An extension of the present work is the consideration of the tracking case in order to ensure balance of the robot in highly dynamic scenarios. Actuator limits could be included into the GIWC following the ideas in [START_REF] Orsolino | Application of wrench based feasibility analysis to the online trajectory optimization of legged robots[END_REF]. Moreover, it is interesting to couple the controller with a higher-level planner to allow for complicated tasks like opening spring-loaded doors. A more exhaustive analysis of passivity and stability of the proposed architecture is a future work.

Fig. 1 .

 1 Fig. 1. TORO pushing a table with a weight of 50 kg on top.

Fig. 2 .

 2 Fig. 2. Illustration of the support polygon for a robot standing on horizontal ground.

Fig. 3 .

 3 Fig. 3. TORO balancing with its right hand and left foot while interacting with the environment using its right foot. The two balancing end-effectors can exert a set of forces estimated by the polyhedron A w F bal,t ≤ b.

  the z component of x c and the orientation R c of the CoM frame C. Consequently, we define F c,b as

Algorithm 1 9 :

 19 Contact-Switching algorithm.1: w F bal,d = w F opt,1 2: Switch from controller[START_REF] Caron | Multi-contact walking pattern generation based on model preview control of 3D COM accelerations[END_REF] to controller[START_REF] Prete | Fast algorithms to test robust static equilibrium for legged robots[END_REF] (F c = F c,cs ) 3: while H cs > Hcs do 4:F c = F c,cs ( w F bal,d ) 5: end while 6: α = 0 7: while α < 1 do 8: w F bal,d = (1 -α) w F opt,1 + α w F opt,2 F c = F c,cs ( w F bal,d) 10: α = α + α 11: end while 12: w F bal,d = w F opt,2 13: while H cs > Hcs do 14: F c = F c,cs ( w F bal,d ) 15: end while 16: Switch back from controller (18) to controller (15) (F c = F c,b )

Fig. 5 .

 5 Fig. 5. Results for experiment 1: lifting a box of 25 kg. (a) Force on the right hand. (b) Force on the left hand. (c) CoM position. (d) ZMP position. (e) CoM and ZMP over the support polygon. (f) Experimental setup.

Fig. 6 .

 6 Fig. 6. Results for experiment 2: pushing a table weighing 50 kg. (a) Force on the right hand. (b) Force on the left hand. (c) CoM position. (d) ZMP position. (e) CoM and ZMP over the support polygon. (f) Experimental setup.

Fig. 7 .

 7 Fig. 7. Results for experiment 3: using the right foot to move a heavy fire extinguisher (19.8 kg). (a) Force on the right hand. (b) Force on the left hand. (c) CoM position. (d) ZMP position. (e) CoM over the support area (orange) and ZMP of the left foot. (f) Experimental setup.

Fig. 8 .

 8 Fig. 8. Results for experiment 4: The robot shifts its balance autonomously between the three end-effectors that are in contact. It switches between contact configuration Υ f f (only the two feet used for balancing), contact configuration Υ f f h (the two feet and the right hand all used for balancing), and contact configuration Υ f h (only the left foot and the right hand used for balancing).Figure (a) shows the change in position for the CoM. Figures (bd) show the cost function H corresponding to contact configurations Υ f f , Υ f f h and Υ f h respectively. A lower value of H reflects a better balance of the robot.

  Fig. 8. Results for experiment 4: The robot shifts its balance autonomously between the three end-effectors that are in contact. It switches between contact configuration Υ f f (only the two feet used for balancing), contact configuration Υ f f h (the two feet and the right hand all used for balancing), and contact configuration Υ f h (only the left foot and the right hand used for balancing).Figure (a) shows the change in position for the CoM. Figures (bd) show the cost function H corresponding to contact configurations Υ f f , Υ f f h and Υ f h respectively. A lower value of H reflects a better balance of the robot.

  𝒙 𝑖𝑛𝑡 , 𝑹 𝑖𝑛𝑡 , 𝑹 𝑐 , 𝑧 𝑐 𝒙 𝑐 , 𝑹 𝑐 , 𝒗 𝑐 , 𝒙 𝑖𝑛𝑡 , 𝑹 𝑖𝑛𝑡 , 𝒗 𝑖𝑛𝑡

	𝑚𝒈 0
	𝐻	𝜕𝐻 𝑥 𝑐 , 𝑦 𝑐	𝑇	-𝑘 𝑏	𝑭 𝑐,𝑏	Wrench
		[ ሶ 𝑥 𝑐 , ሶ 𝑦 𝑐 ]	-𝑫		Distribution 𝑭 𝑜𝑝𝑡
					𝑭 𝑐,𝑖	Wrench
	𝒙 𝑖𝑛𝑡 𝑑 , 𝑹 𝑖𝑛𝑡 𝑑 , 𝑹 𝑐 𝑑 , 𝑧 𝑐 𝑑	Cartesian Compliances	𝑭 𝑖𝑛𝑡	Mapping 𝝉
						Robot
	Planner
	Fig. 4. Overview of the control architecture.

Note that g 0 is a six-dimensional vector, containing three translational and three rotational DoFs of the CoM frame C.

The default distribution F def bal is a tunable parameter, which can be set for instance to 50% of the weight of the robot per foot if the posture is symmetric.

For the conducted experiments (section IV), f min k,z was set to 50 N in order to account for the effect of joint friction.

This paper was recommended for publication by Editor Nikos Tsagarakis upon evaluation of the Associate Editor and Reviewers' comments. This work was supported by the European Union Horizon 2020 Research and Innovation programme under grant agreement No. 645582 (RoMaNS), and H2020-ICT-645097 (COMANOID)