Below is my list of publications organized by topics. Papers are released with source code for all but a few unfortunate exceptions. I'm thankful the robotics community is making the move to open archives, putting out preprints of submitted works on repositories like arXiv or HAL. I hope we can take it to the next level by curating our own overlay journals.
Walking stabilization ¶

Biped Stabilization by Linear Feedback of the VariableHeight Inverted Pendulum Model
Stéphane Caron. ICRA 2020, May 2020. (pdf)
The variableheight inverted pendulum (VHIP) model enables a new balancing strategy by height variations of the center of mass, in addition to the wellknown ankle strategy. We propose a biped stabilizer based on linear feedback of the VHIP that is simple to implement, coincides with the stateoftheart for small perturbations and is able to recover from larger perturbations thanks to this new strategy. This solution is based on "besteffort" pole placement of a 4D divergent component of motion for the VHIP under input feasibility and state viability constraints. We complement it with a suitable wholebody admittance control law and test the resulting stabilizer on the HRP4\def\LdG{\dot{L}_G} \def\Ld{\dot{L}} \def\bfA{\boldsymbol{A}} \def\bfB{\boldsymbol{B}} \def\bfC{\boldsymbol{C}} \def\bfD{\boldsymbol{D}} \def\bfE{\boldsymbol{E}} \def\bfF{\boldsymbol{F}} \def\bfG{\boldsymbol{G}} \def\bfH{\boldsymbol{H}} \def\bfI{\boldsymbol{I}} \def\bfJ{\boldsymbol{J}} \def\bfK{\boldsymbol{K}} \def\bfL{\boldsymbol{L}} \def\bfM{\boldsymbol{M}} \def\bfN{\boldsymbol{N}} \def\bfO{\boldsymbol{O}} \def\bfP{\boldsymbol{P}} \def\bfQ{\boldsymbol{Q}} \def\bfR{\boldsymbol{R}} \def\bfS{\boldsymbol{S}} \def\bfT{\boldsymbol{T}} \def\bfU{\boldsymbol{U}} \def\bfV{\boldsymbol{V}} \def\bfW{\boldsymbol{W}} \def\bfX{\boldsymbol{X}} \def\bfY{\boldsymbol{Y}} \def\bfZ{\boldsymbol{Z}} \def\bfalpha{\boldsymbol{\alpha}} \def\bfa{\boldsymbol{a}} \def\bfbeta{\boldsymbol{\beta}} \def\bfb{\boldsymbol{b}} \def\bfcd{\dot{\bfc}} \def\bfchi{\boldsymbol{\chi}} \def\bfc{\boldsymbol{c}} \def\bfd{\boldsymbol{d}} \def\bfe{\boldsymbol{e}} \def\bff{\boldsymbol{f}} \def\bfgamma{\boldsymbol{\gamma}} \def\bfg{\boldsymbol{g}} \def\bfh{\boldsymbol{h}} \def\bfi{\boldsymbol{i}} \def\bfj{\boldsymbol{j}} \def\bfk{\boldsymbol{k}} \def\bflambda{\boldsymbol{\lambda}} \def\bfl{\boldsymbol{l}} \def\bfm{\boldsymbol{m}} \def\bfn{\boldsymbol{n}} \def\bfomega{\boldsymbol{\omega}} \def\bfone{\boldsymbol{1}} \def\bfo{\boldsymbol{o}} \def\bfpdd{\ddot{\bfp}} \def\bfpd{\dot{\bfp}} \def\bfphi{\boldsymbol{\phi}} \def\bfp{\boldsymbol{p}} \def\bfq{\boldsymbol{q}} \def\bfr{\boldsymbol{r}} \def\bfsigma{\boldsymbol{\sigma}} \def\bfs{\boldsymbol{s}} \def\bftau{\boldsymbol{\tau}} \def\bft{\boldsymbol{t}} \def\bfu{\boldsymbol{u}} \def\bfv{\boldsymbol{v}} \def\bfw{\boldsymbol{w}} \def\bfxi{\boldsymbol{\xi}} \def\bfx{\boldsymbol{x}} \def\bfy{\boldsymbol{y}} \def\bfzero{\boldsymbol{0}} \def\bfz{\boldsymbol{z}} \def\calA{\mathcal{A}} \def\calB{\mathcal{B}} \def\calC{\mathcal{C}} \def\calD{\mathcal{D}} \def\calE{\mathcal{E}} \def\calF{\mathcal{F}} \def\calG{\mathcal{G}} \def\calH{\mathcal{H}} \def\calI{\mathcal{I}} \def\calJ{\mathcal{J}} \def\calK{\mathcal{K}} \def\calL{\mathcal{L}} \def\calM{\mathcal{M}} \def\calN{\mathcal{N}} \def\calO{\mathcal{O}} \def\calP{\mathcal{P}} \def\calQ{\mathcal{Q}} \def\calR{\mathcal{R}} \def\calS{\mathcal{S}} \def\calT{\mathcal{T}} \def\calU{\mathcal{U}} \def\calV{\mathcal{V}} \def\calW{\mathcal{W}} \def\calX{\mathcal{X}} \def\calY{\mathcal{Y}} \def\calZ{\mathcal{Z}} \def\d#1{{\rm d}{#1}} \def\defeq{\stackrel{\mathrm{def}}{=}} \def\dim{\rm dim} \def\p{\boldsymbol{p}} \def\qdd{\ddot{\bfq}} \def\qd{\dot{\bfq}} \def\q{\boldsymbol{q}} \def\xdd{\ddot{x}} \def\xd{\dot{x}} \def\ydd{\ddot{y}} \def\yd{\dot{y}} \def\zdd{\ddot{z}} \def\zd{\dot{z}} 44 humanoid robot.

Stair Climbing Stabilization of the HRP4 Humanoid Robot using Wholebody Admittance Control
Stéphane Caron, Abderrahmane Kheddar and Olivier Tempier. ICRA 2019, Montreal, Canada, May 2019. (pdf)
We consider dynamic stair climbing with the HRP4 humanoid robot as part of an Airbus manufacturing usecase demonstrator. We share experimental knowledge gathered so as to achieve this task, which HRP4 had never been challenged to before. In particular, we extend walking stabilization based on linear inverted pendulum tracking by quadratic programmingbased wrench distribution and a wholebody admittance controller that applies both endeffector and CoM strategies. While existing stabilizers tend to use either one or the other, our experience suggests that the combination of these two approaches improves tracking performance. We demonstrate this solution in an onsite experiment where HRP4 climbs an industrial staircase with 18.5 cm high steps, and release our walking controller as open source software.

Balance control using both ZMP and COM height variations: A convex boundedness approach
Stéphane Caron and Bastien Mallein. ICRA 2018, Brisbane, Australia, May 2018. (pdf)
Developments for 3D\def\LdG{\dot{L}_G} \def\Ld{\dot{L}} \def\bfA{\boldsymbol{A}} \def\bfB{\boldsymbol{B}} \def\bfC{\boldsymbol{C}} \def\bfD{\boldsymbol{D}} \def\bfE{\boldsymbol{E}} \def\bfF{\boldsymbol{F}} \def\bfG{\boldsymbol{G}} \def\bfH{\boldsymbol{H}} \def\bfI{\boldsymbol{I}} \def\bfJ{\boldsymbol{J}} \def\bfK{\boldsymbol{K}} \def\bfL{\boldsymbol{L}} \def\bfM{\boldsymbol{M}} \def\bfN{\boldsymbol{N}} \def\bfO{\boldsymbol{O}} \def\bfP{\boldsymbol{P}} \def\bfQ{\boldsymbol{Q}} \def\bfR{\boldsymbol{R}} \def\bfS{\boldsymbol{S}} \def\bfT{\boldsymbol{T}} \def\bfU{\boldsymbol{U}} \def\bfV{\boldsymbol{V}} \def\bfW{\boldsymbol{W}} \def\bfX{\boldsymbol{X}} \def\bfY{\boldsymbol{Y}} \def\bfZ{\boldsymbol{Z}} \def\bfalpha{\boldsymbol{\alpha}} \def\bfa{\boldsymbol{a}} \def\bfbeta{\boldsymbol{\beta}} \def\bfb{\boldsymbol{b}} \def\bfcd{\dot{\bfc}} \def\bfchi{\boldsymbol{\chi}} \def\bfc{\boldsymbol{c}} \def\bfd{\boldsymbol{d}} \def\bfe{\boldsymbol{e}} \def\bff{\boldsymbol{f}} \def\bfgamma{\boldsymbol{\gamma}} \def\bfg{\boldsymbol{g}} \def\bfh{\boldsymbol{h}} \def\bfi{\boldsymbol{i}} \def\bfj{\boldsymbol{j}} \def\bfk{\boldsymbol{k}} \def\bflambda{\boldsymbol{\lambda}} \def\bfl{\boldsymbol{l}} \def\bfm{\boldsymbol{m}} \def\bfn{\boldsymbol{n}} \def\bfomega{\boldsymbol{\omega}} \def\bfone{\boldsymbol{1}} \def\bfo{\boldsymbol{o}} \def\bfpdd{\ddot{\bfp}} \def\bfpd{\dot{\bfp}} \def\bfphi{\boldsymbol{\phi}} \def\bfp{\boldsymbol{p}} \def\bfq{\boldsymbol{q}} \def\bfr{\boldsymbol{r}} \def\bfsigma{\boldsymbol{\sigma}} \def\bfs{\boldsymbol{s}} \def\bftau{\boldsymbol{\tau}} \def\bft{\boldsymbol{t}} \def\bfu{\boldsymbol{u}} \def\bfv{\boldsymbol{v}} \def\bfw{\boldsymbol{w}} \def\bfxi{\boldsymbol{\xi}} \def\bfx{\boldsymbol{x}} \def\bfy{\boldsymbol{y}} \def\bfzero{\boldsymbol{0}} \def\bfz{\boldsymbol{z}} \def\calA{\mathcal{A}} \def\calB{\mathcal{B}} \def\calC{\mathcal{C}} \def\calD{\mathcal{D}} \def\calE{\mathcal{E}} \def\calF{\mathcal{F}} \def\calG{\mathcal{G}} \def\calH{\mathcal{H}} \def\calI{\mathcal{I}} \def\calJ{\mathcal{J}} \def\calK{\mathcal{K}} \def\calL{\mathcal{L}} \def\calM{\mathcal{M}} \def\calN{\mathcal{N}} \def\calO{\mathcal{O}} \def\calP{\mathcal{P}} \def\calQ{\mathcal{Q}} \def\calR{\mathcal{R}} \def\calS{\mathcal{S}} \def\calT{\mathcal{T}} \def\calU{\mathcal{U}} \def\calV{\mathcal{V}} \def\calW{\mathcal{W}} \def\calX{\mathcal{X}} \def\calY{\mathcal{Y}} \def\calZ{\mathcal{Z}} \def\d#1{{\rm d}{#1}} \def\defeq{\stackrel{\mathrm{def}}{=}} \def\dim{\rm dim} \def\p{\boldsymbol{p}} \def\qdd{\ddot{\bfq}} \def\qd{\dot{\bfq}} \def\q{\boldsymbol{q}} \def\xdd{\ddot{x}} \def\xd{\dot{x}} \def\ydd{\ddot{y}} \def\yd{\dot{y}} \def\zdd{\ddot{z}} \def\zd{\dot{z}} \textrm{3D}3D control of the center of mass (CoM) of biped robots are currently located in two local minima: on the one hand, methods that allow CoM height variations but only work in the 2D sagittal plane; on the other hand, nonconvex direct transcriptions of centroidal dynamics that are delicate to handle. This paper presents an alternative that controls the CoM in 3D via an indirect transcription that is both lowdimensional and solvable fast enough for realtime control. The key to this development is the notion of boundedness condition, which quantifies the capturability of 3D CoM trajectories.

Walking on Gravel with Soft Soles using Linear Inverted Pendulum Tracking and Reaction Force Distribution
Adrien Pajon, Stéphane Caron, Giovanni De Magistris, Sylvain Miossec and Abderrahmane Kheddar. Humanoids 2017, Birmingham, United Kingdom, November 2017. (pdf)
Soft soles absorb impacts and cast ground unevenness during locomotion on rough terrains. However, they introduce passive degrees of freedom (deformations under the feet) that complexify the tasks of state estimation and overall robot stabilization. We address this problem by developing a control loop that stabilizes humanoid robots when walking with soft soles on flat and uneven terrain. Our closedloop controller minimizes the errors on the center of mass (COM) and the zero moment point (ZMP) with an admittance control of the feet based on a simple deformation estimator. We demonstrate its effectiveness in real experiments on the HRP4 humanoid.
Contact stability ¶

Feasible Region: an ActuationAware Extension of the Support Region
Romeo Orsolino, Michele Focchi, Stéphane Caron, Gennaro Raiola, Victor Barasuol and Claudio Semini. IEEE Transactions on Robotics. Submitted March 2019. Accepted February 2020. Published August 2020. (pdf)
In legged locomotion the support region is defined as the 2D horizontal convex area where the robot is able to support its own body weight in static conditions. Despite this definition, when the jointtorque limits (actuation limits) are hit, the robot can be unable to carry its own body weight, even when the projection of its Center of Mass (CoM) lies inside the support region. In this manuscript we overcome this inconsistency by defining the Feasible Region, a revisited support region that guarantees both global static stability of the robot and the existence of a set of joint torques that are able to sustain the body weight. Thanks to the usage of an Iterative Projection (IP) algorithm, we show that the Feasible Region can be efficiently employed for online motion planning of locomanipulation tasks for both humanoids and quadrupeds. Unlike the classical support region, the Feasible Region represents a local measure of the robots robustness to external disturbances and it must be recomputed at every configuration change. For this, we also propose a global extension of the Feasible Region that is configuration independent and only needs to be recomputed at every stance change.

ZMP Support Areas for Multicontact Mobility Under Frictional Constraints
Stéphane Caron, QuangCuong Pham and Yoshihiko Nakamura. IEEE Transactions on Robotics. Submitted October 2015. Published December 2016. (pdf)
We propose a method for checking and enforcing multicontact stability based on the Zerotilting Moment Point (ZMP). The key to our development is the generalization of ZMP support areas to take into account (a) frictional constraints and (b) multiple noncoplanar contacts. We introduce and investigate two kinds of ZMP support areas. First, we characterize and provide a fast geometric construction for the support area generated by valid contact forces, with no other constraint on the robot motion. We call this set the full support area. Next, we consider the control of humanoid robots using the Linear Pendulum Mode (LPM). We observe that the constraints stemming from the LPM induce a shrinking of the support area, even for walking on horizontal floors. We propose an algorithm to compute the new area, which we call pendular support area. We show that, in the LPM, having the ZMP in the pendular support area is a necessary and sufficient condition for contact stability. Based on these developments, we implement a wholebody controller and generate feasible multicontact motions where an HRP4 humanoid locomotes in challenging multicontact scenarios.

Leveraging Cone Double Description for Multicontact Stability of Humanoids with Applications to Statics and Dynamics
Stéphane Caron, QuangCuong Pham and Yoshihiko Nakamura. RSS 2015, Roma, Italy, July 2015. (pdf)
We build on previous works advocating the use of the GravitoInertial Wrench Cone (GIWC) as a general contact stability criterion (a "ZMP for noncoplanar contacts"). We show how to compute this wrench cone from the friction cones of contact forces by using an intermediate representation, the surface contact wrench cone, which is the minimal representation of contact stability for each surface contact. The observation that the GIWC needs to be computed only once per stance leads to particularly efficient algorithms, as we illustrate in two important problems for humanoids : "testing robust static equilibrium" and "timeoptimal path parameterization". We show, through theoretical analysis and in physical simulations, that our method is more general and/or outperforms existing ones.

Stability of Surface Contacts for Humanoid Robots ClosedForm Formulae of the Contact Wrench Cone for Rectangular Support Areas
Stéphane Caron, QuangCuong Pham and Yoshihiko Nakamura. ICRA 2015, Seattle, USA, May 2015. (pdf)
Humanoids locomote by making and breaking contacts with their environment. Thus, a crucial question for them is to anticipate whether a contact will hold or break under effort. For rigid surface contacts, existing methods usually consider several pointcontact forces, which has some drawbacks due to the underlying redundancy. We derive a criterion, the Contact Wrench Cone (CWC), which is equivalent to any number of applied forces on the contact surface, and for which we provide a closedform formula.
Walking trajectory generation ¶

3D biped locomotion control including seamless transition between walking and running via 3D ZMP manipulation
Tomomichi Sugihara, Kenta Imanishi, Takanobu Yamamoto and Stéphane Caron. IEEE International Conference on Robotics and Automation, May 2021.
A novel control scheme for biped robots to manipulate the ZMP threedimensionally apart from the actual ground profile is presented. It is shown that the linear invertedpendulumlike dynamics with this scheme can represent a wider class of movements including variation of the body height. Moreover, this can also represent the motion in aerial phase. Based on this, the footguided controller proposed by the authors is enhanced to enable the robots to locomote on highly uneven terrains and also to seamlessly transition between walking and running without preplanning the overall motion reference. The controller guarantees the capturability at landing and defines the motion by a timevariant state feedback, which is analytically derived from a model predictive optimization. It is verified through some computer simulations.

ZMPの3次元的操作による可捕性規範凹凸地面上二脚運動制御
Tomomichi Sugihara and Stéphane Caron. RSJ 2020, Japan, October 2020. (pdf)
二脚ロボットを実用する上で，高低差のある地形を移動する機能は必須である．限られた足場で着地点を選び，転倒を避けながら重心を制御する方法が求められる．梶田ら [1] はその先駆的な研究において，凹凸地形に合わせて上下動を伴う重心の運動と支持足の切り替えを適切に連動させる歩行制御法を提案した．その際，重心運動を直線上に拘束することで導かれた線形な倒立振子様の力学系を用いて，議論を簡明にした．

Lower body control of a semiautonomous avatar in Virtual Reality: Balance and Locomotion of a 3D Bipedal Model
Vincent Thomasset, Stéphane Caron and Vincent Weistroffer. ACM Symposium on Virtual Reality Software and Technology, Parramatta, Australia, November 2019. (pdf)
Animated virtual humans may rely on fullbody tracking system to reproduce user motions. In this paper, we reduce tracking to the upperbody and reconstruct the lower body to follow autonomously its upper counterpart. Doing so reduces the number of sensors required, making the application of virtual humans simpler and cheaper. It also enable deployment in cluttered scenes where the lower body is often hidden. The contribution here is the inversion of the wellknown capture problem for bipedal walking. It determines footsteps rather than centerofmass motions and yet can be solved with an offtheshelf capture problem solver. The quality of our method is assessed in realtime tracking experiments on a wide variety of movements.

Capturabilitybased Pattern Generation for Walking with Variable Height
Stéphane Caron, Adrien Escande, Leonardo Lanari and Bastien Mallein. IEEE Transactions on Robotics. Submitted January 2018. Accepted May 2019. Published April 2020. (pdf)
Capturability analysis of the linear inverted pendulum (LIP) model enabled walking with constrained height based on the capture point. We generalize this analysis to the variableheight inverted pendulum (VHIP) and show how it enables 3D walking over uneven terrains based on capture inputs. Thanks to a tailored optimization scheme, we can compute these inputs fast enough for realtime model predictive control. We implement this approach as opensource software and demonstrate it in dynamic simulations.

When to make a step? Tackling the timing problem in multicontact locomotion by TOPPMPC
Stéphane Caron and QuangCuong Pham. Humanoids 2017, Birmingham, United Kingdom, November 2017. (pdf)
We present a model predictive controller (MPC) for multicontact locomotion where predictive optimizations are realized by timeoptimal path parameterization (TOPP). A key feature of this solution is that, contrary to existing planners where step timings are provided as inputs, here the timing between contact switches is computed as output of a fast nonlinear optimization. This is appealing to multicontact locomotion, where proper timings depend on terrain topology and suitable heuristics are unknown. We show how to formulate legged locomotion as a TOPP problem and demonstrate the behavior of the resulting TOPPMPC controller in simulations with a model of the HRP4 humanoid robot.

Dynamic Walking over Rough Terrains by Nonlinear Predictive Control of the Floatingbase Inverted Pendulum
Stéphane Caron and Abderrahmane Kheddar. IROS 2017, Vancouver, Canada, September 2017. (pdf)
We present a realtime roughterrain dynamic walking pattern generator. Our method automatically finds step durations, which is a critical issue over rough terrains where they depend on terrain topology. To achieve this level of generality, we introduce the Floatingbase Inverted Pendulum (FIP) model where the center of mass can translate freely and the zerotilting moment point is allowed to leave the contact surface. We show that this model is equivalent to the linearinverted pendulum mode with variable center of mass height, aside from the fact that its equations of motion remain linear. Our design then follows three steps: (i\def\LdG{\dot{L}_G} \def\Ld{\dot{L}} \def\bfA{\boldsymbol{A}} \def\bfB{\boldsymbol{B}} \def\bfC{\boldsymbol{C}} \def\bfD{\boldsymbol{D}} \def\bfE{\boldsymbol{E}} \def\bfF{\boldsymbol{F}} \def\bfG{\boldsymbol{G}} \def\bfH{\boldsymbol{H}} \def\bfI{\boldsymbol{I}} \def\bfJ{\boldsymbol{J}} \def\bfK{\boldsymbol{K}} \def\bfL{\boldsymbol{L}} \def\bfM{\boldsymbol{M}} \def\bfN{\boldsymbol{N}} \def\bfO{\boldsymbol{O}} \def\bfP{\boldsymbol{P}} \def\bfQ{\boldsymbol{Q}} \def\bfR{\boldsymbol{R}} \def\bfS{\boldsymbol{S}} \def\bfT{\boldsymbol{T}} \def\bfU{\boldsymbol{U}} \def\bfV{\boldsymbol{V}} \def\bfW{\boldsymbol{W}} \def\bfX{\boldsymbol{X}} \def\bfY{\boldsymbol{Y}} \def\bfZ{\boldsymbol{Z}} \def\bfalpha{\boldsymbol{\alpha}} \def\bfa{\boldsymbol{a}} \def\bfbeta{\boldsymbol{\beta}} \def\bfb{\boldsymbol{b}} \def\bfcd{\dot{\bfc}} \def\bfchi{\boldsymbol{\chi}} \def\bfc{\boldsymbol{c}} \def\bfd{\boldsymbol{d}} \def\bfe{\boldsymbol{e}} \def\bff{\boldsymbol{f}} \def\bfgamma{\boldsymbol{\gamma}} \def\bfg{\boldsymbol{g}} \def\bfh{\boldsymbol{h}} \def\bfi{\boldsymbol{i}} \def\bfj{\boldsymbol{j}} \def\bfk{\boldsymbol{k}} \def\bflambda{\boldsymbol{\lambda}} \def\bfl{\boldsymbol{l}} \def\bfm{\boldsymbol{m}} \def\bfn{\boldsymbol{n}} \def\bfomega{\boldsymbol{\omega}} \def\bfone{\boldsymbol{1}} \def\bfo{\boldsymbol{o}} \def\bfpdd{\ddot{\bfp}} \def\bfpd{\dot{\bfp}} \def\bfphi{\boldsymbol{\phi}} \def\bfp{\boldsymbol{p}} \def\bfq{\boldsymbol{q}} \def\bfr{\boldsymbol{r}} \def\bfsigma{\boldsymbol{\sigma}} \def\bfs{\boldsymbol{s}} \def\bftau{\boldsymbol{\tau}} \def\bft{\boldsymbol{t}} \def\bfu{\boldsymbol{u}} \def\bfv{\boldsymbol{v}} \def\bfw{\boldsymbol{w}} \def\bfxi{\boldsymbol{\xi}} \def\bfx{\boldsymbol{x}} \def\bfy{\boldsymbol{y}} \def\bfzero{\boldsymbol{0}} \def\bfz{\boldsymbol{z}} \def\calA{\mathcal{A}} \def\calB{\mathcal{B}} \def\calC{\mathcal{C}} \def\calD{\mathcal{D}} \def\calE{\mathcal{E}} \def\calF{\mathcal{F}} \def\calG{\mathcal{G}} \def\calH{\mathcal{H}} \def\calI{\mathcal{I}} \def\calJ{\mathcal{J}} \def\calK{\mathcal{K}} \def\calL{\mathcal{L}} \def\calM{\mathcal{M}} \def\calN{\mathcal{N}} \def\calO{\mathcal{O}} \def\calP{\mathcal{P}} \def\calQ{\mathcal{Q}} \def\calR{\mathcal{R}} \def\calS{\mathcal{S}} \def\calT{\mathcal{T}} \def\calU{\mathcal{U}} \def\calV{\mathcal{V}} \def\calW{\mathcal{W}} \def\calX{\mathcal{X}} \def\calY{\mathcal{Y}} \def\calZ{\mathcal{Z}} \def\d#1{{\rm d}{#1}} \def\defeq{\stackrel{\mathrm{def}}{=}} \def\dim{\rm dim} \def\p{\boldsymbol{p}} \def\qdd{\ddot{\bfq}} \def\qd{\dot{\bfq}} \def\q{\boldsymbol{q}} \def\xdd{\ddot{x}} \def\xd{\dot{x}} \def\ydd{\ddot{y}} \def\yd{\dot{y}} \def\zdd{\ddot{z}} \def\zd{\dot{z}} ii) we characterize the FIP contactstability condition; (ii\def\LdG{\dot{L}_G} \def\Ld{\dot{L}} \def\bfA{\boldsymbol{A}} \def\bfB{\boldsymbol{B}} \def\bfC{\boldsymbol{C}} \def\bfD{\boldsymbol{D}} \def\bfE{\boldsymbol{E}} \def\bfF{\boldsymbol{F}} \def\bfG{\boldsymbol{G}} \def\bfH{\boldsymbol{H}} \def\bfI{\boldsymbol{I}} \def\bfJ{\boldsymbol{J}} \def\bfK{\boldsymbol{K}} \def\bfL{\boldsymbol{L}} \def\bfM{\boldsymbol{M}} \def\bfN{\boldsymbol{N}} \def\bfO{\boldsymbol{O}} \def\bfP{\boldsymbol{P}} \def\bfQ{\boldsymbol{Q}} \def\bfR{\boldsymbol{R}} \def\bfS{\boldsymbol{S}} \def\bfT{\boldsymbol{T}} \def\bfU{\boldsymbol{U}} \def\bfV{\boldsymbol{V}} \def\bfW{\boldsymbol{W}} \def\bfX{\boldsymbol{X}} \def\bfY{\boldsymbol{Y}} \def\bfZ{\boldsymbol{Z}} \def\bfalpha{\boldsymbol{\alpha}} \def\bfa{\boldsymbol{a}} \def\bfbeta{\boldsymbol{\beta}} \def\bfb{\boldsymbol{b}} \def\bfcd{\dot{\bfc}} \def\bfchi{\boldsymbol{\chi}} \def\bfc{\boldsymbol{c}} \def\bfd{\boldsymbol{d}} \def\bfe{\boldsymbol{e}} \def\bff{\boldsymbol{f}} \def\bfgamma{\boldsymbol{\gamma}} \def\bfg{\boldsymbol{g}} \def\bfh{\boldsymbol{h}} \def\bfi{\boldsymbol{i}} \def\bfj{\boldsymbol{j}} \def\bfk{\boldsymbol{k}} \def\bflambda{\boldsymbol{\lambda}} \def\bfl{\boldsymbol{l}} \def\bfm{\boldsymbol{m}} \def\bfn{\boldsymbol{n}} \def\bfomega{\boldsymbol{\omega}} \def\bfone{\boldsymbol{1}} \def\bfo{\boldsymbol{o}} \def\bfpdd{\ddot{\bfp}} \def\bfpd{\dot{\bfp}} \def\bfphi{\boldsymbol{\phi}} \def\bfp{\boldsymbol{p}} \def\bfq{\boldsymbol{q}} \def\bfr{\boldsymbol{r}} \def\bfsigma{\boldsymbol{\sigma}} \def\bfs{\boldsymbol{s}} \def\bftau{\boldsymbol{\tau}} \def\bft{\boldsymbol{t}} \def\bfu{\boldsymbol{u}} \def\bfv{\boldsymbol{v}} \def\bfw{\boldsymbol{w}} \def\bfxi{\boldsymbol{\xi}} \def\bfx{\boldsymbol{x}} \def\bfy{\boldsymbol{y}} \def\bfzero{\boldsymbol{0}} \def\bfz{\boldsymbol{z}} \def\calA{\mathcal{A}} \def\calB{\mathcal{B}} \def\calC{\mathcal{C}} \def\calD{\mathcal{D}} \def\calE{\mathcal{E}} \def\calF{\mathcal{F}} \def\calG{\mathcal{G}} \def\calH{\mathcal{H}} \def\calI{\mathcal{I}} \def\calJ{\mathcal{J}} \def\calK{\mathcal{K}} \def\calL{\mathcal{L}} \def\calM{\mathcal{M}} \def\calN{\mathcal{N}} \def\calO{\mathcal{O}} \def\calP{\mathcal{P}} \def\calQ{\mathcal{Q}} \def\calR{\mathcal{R}} \def\calS{\mathcal{S}} \def\calT{\mathcal{T}} \def\calU{\mathcal{U}} \def\calV{\mathcal{V}} \def\calW{\mathcal{W}} \def\calX{\mathcal{X}} \def\calY{\mathcal{Y}} \def\calZ{\mathcal{Z}} \def\d#1{{\rm d}{#1}} \def\defeq{\stackrel{\mathrm{def}}{=}} \def\dim{\rm dim} \def\p{\boldsymbol{p}} \def\qdd{\ddot{\bfq}} \def\qd{\dot{\bfq}} \def\q{\boldsymbol{q}} \def\xdd{\ddot{x}} \def\xd{\dot{x}} \def\ydd{\ddot{y}} \def\yd{\dot{y}} \def\zdd{\ddot{z}} \def\zd{\dot{z}} iiii) we compute feedforward controls by solving a nonlinear optimization over recedinghorizon FIP trajectories. Despite running at 30 Hz in a modelpredictive fashion, simulations show that the latter is too slow to stabilize dynamic motions. To remedy this, we (iii\def\LdG{\dot{L}_G} \def\Ld{\dot{L}} \def\bfA{\boldsymbol{A}} \def\bfB{\boldsymbol{B}} \def\bfC{\boldsymbol{C}} \def\bfD{\boldsymbol{D}} \def\bfE{\boldsymbol{E}} \def\bfF{\boldsymbol{F}} \def\bfG{\boldsymbol{G}} \def\bfH{\boldsymbol{H}} \def\bfI{\boldsymbol{I}} \def\bfJ{\boldsymbol{J}} \def\bfK{\boldsymbol{K}} \def\bfL{\boldsymbol{L}} \def\bfM{\boldsymbol{M}} \def\bfN{\boldsymbol{N}} \def\bfO{\boldsymbol{O}} \def\bfP{\boldsymbol{P}} \def\bfQ{\boldsymbol{Q}} \def\bfR{\boldsymbol{R}} \def\bfS{\boldsymbol{S}} \def\bfT{\boldsymbol{T}} \def\bfU{\boldsymbol{U}} \def\bfV{\boldsymbol{V}} \def\bfW{\boldsymbol{W}} \def\bfX{\boldsymbol{X}} \def\bfY{\boldsymbol{Y}} \def\bfZ{\boldsymbol{Z}} \def\bfalpha{\boldsymbol{\alpha}} \def\bfa{\boldsymbol{a}} \def\bfbeta{\boldsymbol{\beta}} \def\bfb{\boldsymbol{b}} \def\bfcd{\dot{\bfc}} \def\bfchi{\boldsymbol{\chi}} \def\bfc{\boldsymbol{c}} \def\bfd{\boldsymbol{d}} \def\bfe{\boldsymbol{e}} \def\bff{\boldsymbol{f}} \def\bfgamma{\boldsymbol{\gamma}} \def\bfg{\boldsymbol{g}} \def\bfh{\boldsymbol{h}} \def\bfi{\boldsymbol{i}} \def\bfj{\boldsymbol{j}} \def\bfk{\boldsymbol{k}} \def\bflambda{\boldsymbol{\lambda}} \def\bfl{\boldsymbol{l}} \def\bfm{\boldsymbol{m}} \def\bfn{\boldsymbol{n}} \def\bfomega{\boldsymbol{\omega}} \def\bfone{\boldsymbol{1}} \def\bfo{\boldsymbol{o}} \def\bfpdd{\ddot{\bfp}} \def\bfpd{\dot{\bfp}} \def\bfphi{\boldsymbol{\phi}} \def\bfp{\boldsymbol{p}} \def\bfq{\boldsymbol{q}} \def\bfr{\boldsymbol{r}} \def\bfsigma{\boldsymbol{\sigma}} \def\bfs{\boldsymbol{s}} \def\bftau{\boldsymbol{\tau}} \def\bft{\boldsymbol{t}} \def\bfu{\boldsymbol{u}} \def\bfv{\boldsymbol{v}} \def\bfw{\boldsymbol{w}} \def\bfxi{\boldsymbol{\xi}} \def\bfx{\boldsymbol{x}} \def\bfy{\boldsymbol{y}} \def\bfzero{\boldsymbol{0}} \def\bfz{\boldsymbol{z}} \def\calA{\mathcal{A}} \def\calB{\mathcal{B}} \def\calC{\mathcal{C}} \def\calD{\mathcal{D}} \def\calE{\mathcal{E}} \def\calF{\mathcal{F}} \def\calG{\mathcal{G}} \def\calH{\mathcal{H}} \def\calI{\mathcal{I}} \def\calJ{\mathcal{J}} \def\calK{\mathcal{K}} \def\calL{\mathcal{L}} \def\calM{\mathcal{M}} \def\calN{\mathcal{N}} \def\calO{\mathcal{O}} \def\calP{\mathcal{P}} \def\calQ{\mathcal{Q}} \def\calR{\mathcal{R}} \def\calS{\mathcal{S}} \def\calT{\mathcal{T}} \def\calU{\mathcal{U}} \def\calV{\mathcal{V}} \def\calW{\mathcal{W}} \def\calX{\mathcal{X}} \def\calY{\mathcal{Y}} \def\calZ{\mathcal{Z}} \def\d#1{{\rm d}{#1}} \def\defeq{\stackrel{\mathrm{def}}{=}} \def\dim{\rm dim} \def\p{\boldsymbol{p}} \def\qdd{\ddot{\bfq}} \def\qd{\dot{\bfq}} \def\q{\boldsymbol{q}} \def\xdd{\ddot{x}} \def\xd{\dot{x}} \def\ydd{\ddot{y}} \def\yd{\dot{y}} \def\zdd{\ddot{z}} \def\zd{\dot{z}} iiiiii) linearize FIP feedback control computations into a quadratic program, resulting in a constrained linearquadratic regulator that runs at 300 Hz. We finally demonstrate our solution in simulations with a model of the HRP4 humanoid robot, including noise and delays over both state estimation and foot force control.

Multicontact Walking Pattern Generation based on Model Preview Control of 3D COM Accelerations
Stéphane Caron and Abderrahmane Kheddar. Humanoids 2016, Cancún, Mexico, November 2016. (pdf)
We present a multicontact walking pattern generator based on previewcontrol of the 3D acceleration of the center of mass (COM). A key point in the design of our algorithm is the calculation of contactstability constraints. Thanks to a mathematical observation on the algebraic nature of the frictional wrench cone, we show that the 3D volume of feasible COM accelerations is a always an upwardpointing cone. We reduce its computation to a convex hull of (dual) 2D points, for which optimal O(nlogn)\def\LdG{\dot{L}_G} \def\Ld{\dot{L}} \def\bfA{\boldsymbol{A}} \def\bfB{\boldsymbol{B}} \def\bfC{\boldsymbol{C}} \def\bfD{\boldsymbol{D}} \def\bfE{\boldsymbol{E}} \def\bfF{\boldsymbol{F}} \def\bfG{\boldsymbol{G}} \def\bfH{\boldsymbol{H}} \def\bfI{\boldsymbol{I}} \def\bfJ{\boldsymbol{J}} \def\bfK{\boldsymbol{K}} \def\bfL{\boldsymbol{L}} \def\bfM{\boldsymbol{M}} \def\bfN{\boldsymbol{N}} \def\bfO{\boldsymbol{O}} \def\bfP{\boldsymbol{P}} \def\bfQ{\boldsymbol{Q}} \def\bfR{\boldsymbol{R}} \def\bfS{\boldsymbol{S}} \def\bfT{\boldsymbol{T}} \def\bfU{\boldsymbol{U}} \def\bfV{\boldsymbol{V}} \def\bfW{\boldsymbol{W}} \def\bfX{\boldsymbol{X}} \def\bfY{\boldsymbol{Y}} \def\bfZ{\boldsymbol{Z}} \def\bfalpha{\boldsymbol{\alpha}} \def\bfa{\boldsymbol{a}} \def\bfbeta{\boldsymbol{\beta}} \def\bfb{\boldsymbol{b}} \def\bfcd{\dot{\bfc}} \def\bfchi{\boldsymbol{\chi}} \def\bfc{\boldsymbol{c}} \def\bfd{\boldsymbol{d}} \def\bfe{\boldsymbol{e}} \def\bff{\boldsymbol{f}} \def\bfgamma{\boldsymbol{\gamma}} \def\bfg{\boldsymbol{g}} \def\bfh{\boldsymbol{h}} \def\bfi{\boldsymbol{i}} \def\bfj{\boldsymbol{j}} \def\bfk{\boldsymbol{k}} \def\bflambda{\boldsymbol{\lambda}} \def\bfl{\boldsymbol{l}} \def\bfm{\boldsymbol{m}} \def\bfn{\boldsymbol{n}} \def\bfomega{\boldsymbol{\omega}} \def\bfone{\boldsymbol{1}} \def\bfo{\boldsymbol{o}} \def\bfpdd{\ddot{\bfp}} \def\bfpd{\dot{\bfp}} \def\bfphi{\boldsymbol{\phi}} \def\bfp{\boldsymbol{p}} \def\bfq{\boldsymbol{q}} \def\bfr{\boldsymbol{r}} \def\bfsigma{\boldsymbol{\sigma}} \def\bfs{\boldsymbol{s}} \def\bftau{\boldsymbol{\tau}} \def\bft{\boldsymbol{t}} \def\bfu{\boldsymbol{u}} \def\bfv{\boldsymbol{v}} \def\bfw{\boldsymbol{w}} \def\bfxi{\boldsymbol{\xi}} \def\bfx{\boldsymbol{x}} \def\bfy{\boldsymbol{y}} \def\bfzero{\boldsymbol{0}} \def\bfz{\boldsymbol{z}} \def\calA{\mathcal{A}} \def\calB{\mathcal{B}} \def\calC{\mathcal{C}} \def\calD{\mathcal{D}} \def\calE{\mathcal{E}} \def\calF{\mathcal{F}} \def\calG{\mathcal{G}} \def\calH{\mathcal{H}} \def\calI{\mathcal{I}} \def\calJ{\mathcal{J}} \def\calK{\mathcal{K}} \def\calL{\mathcal{L}} \def\calM{\mathcal{M}} \def\calN{\mathcal{N}} \def\calO{\mathcal{O}} \def\calP{\mathcal{P}} \def\calQ{\mathcal{Q}} \def\calR{\mathcal{R}} \def\calS{\mathcal{S}} \def\calT{\mathcal{T}} \def\calU{\mathcal{U}} \def\calV{\mathcal{V}} \def\calW{\mathcal{W}} \def\calX{\mathcal{X}} \def\calY{\mathcal{Y}} \def\calZ{\mathcal{Z}} \def\d#1{{\rm d}{#1}} \def\defeq{\stackrel{\mathrm{def}}{=}} \def\dim{\rm dim} \def\p{\boldsymbol{p}} \def\qdd{\ddot{\bfq}} \def\qd{\dot{\bfq}} \def\q{\boldsymbol{q}} \def\xdd{\ddot{x}} \def\xd{\dot{x}} \def\ydd{\ddot{y}} \def\yd{\dot{y}} \def\zdd{\ddot{z}} \def\zd{\dot{z}} \calO(n \log n)O(nlogn) algorithms are readily available. This reformulation brings a significant speedup compared to previous methods, which allows us to compute timevarying contactstability criteria fast enough for the control loop. Next, we propose a conservative trajectorywide contactstability criterion, which can be derived from COMacceleration volumes at marginal cost and directly applied in a modelpredictive controller. We finally implement this pipeline and exemplify it with the HRP4 humanoid model in multicontact dynamically walking scenarios.
Multicontact motion control ¶

Humanoid Control Under Interchangeable Fixed and Sliding Unilateral Contacts
Saeid Samadi, Julien Roux, Arnaud Tanguy, Stéphane Caron and Abderrahmane Kheddar. Robotics and Automation Letters. April 2021. (pdf)
In this letter, we propose a wholebody control strategy for humanoid robots in multicontact settings that enables switching between fixed and sliding contacts under active balance. We compute, in realtime, a safe centerofmass position and wrench distribution of the contact points based on the Chebyshev center. Our solution is formulated as a quadratic programming problem without a priori computation of balance regions. We assess our approach with experiments highlighting switches between fixed and sliding contact modes in multicontact configurations. A humanoid robot demonstrates such contact interchanges from fullyfixed to multisliding and also shuffling of the foot. The scenarios illustrate the performance of our control scheme in achieving the desired forces, CoM position attractor, and planned trajectories while actively maintaining balance.

Humanoid Robots in Aircraft Manufacturing: The Airbus Use Cases
Abderrahmane Kheddar, Stéphane Caron, Pierre Gergondet, Andrew Comport, Arnaud Tanguy, Christian Ott, Bernd Henze, George Mesesan, Johannes Englsberger, Máximo A. Roa, PierreBrice Wieber, François Chaumette, Fabien Spindler, Giuseppe Oriolo, Leonardo Lanari, Adrien Escande, Kevin Chappellet, Fumio Kanehiro and Patrice Rabaté. IEEE Robotics and Automation Magazine. December 2019. Best Paper Award. (pdf)
We report results from a collaborative project that investigated the deployment of humanoid robotic solutions in aircraft manufacturing for some assembly operations where access is not possible for wheeled or railported robotic platforms. Recent developments in multicontact planning and control, bipedal walking, embedded SLAM, wholebody multisensory task space optimization control, and contact detection and safety, suggest that humanoids could be a plausible solution for automation given the specific requirements in such largescale manufacturing sites. The main challenge is to integrate these scientific and technological advances into two existing humanoid platforms: the position controlled HRP4 and the torque controlled TORO. This integration effort was demonstrated in a bracket assembly operation inside a 1:1 scale A350 mockup of the front part of the fuselage at the Airbus SaintNazaire site. We present and discuss the main results that have been achieved in this project and provide recommendations for future work.

Balance of Humanoid Robots in a Mix of Fixed and Sliding MultiContact Scenarios
Saeid Samadi, Stéphane Caron, Arnaud Tanguy and Abderrahmane Kheddar. ICRA 2020, May 2020. (pdf)
This study deals with the balance of humanoid or multilegged robots in a multicontact setting where a chosen subset of contacts is undergoing desired slidingtask motions. One method to keep balance is to hold the centerofmass (CoM) within an admissible convex area. This area is calculated based on the contact positions and forces. We introduce a methodology to compute this CoM support area (CSA) for multiple fixed and intentionally sliding contacts. To select the most appropriate CoM position within CSA, we account for (i) constraints of multiple fixed and sliding contacts, (ii) desired wrench distribution for contacts, and (iii) desired CoM position (eventually dictated by other tasks). These are formulated as a quadratic programming (QP) optimization problems. We illustrate our approach with pushing against a wall and wiping, and conducted experiments using the HRP4 humanoid robot.

PostImpact Adaptive Compliance for Humanoid Falls Using Predictive Control of a Reduced Model
Vincent Samy, Stéphane Caron, Karim Bouyarmane and Abderrahmane Kheddar. Humanoids 2017, Birmingham, United Kingdom, November 2017. (pdf)
We consider control of a humanoid robot in active compliance just after the impact consecutive to a fall. The goal of this postimpact braking is to absorb undesired linear momentum accumulated during the fall, using a limited supply of time and actuation power. The gist of our method is an optimal distribution of undesired momentum between the robot's hand and foot contact points, followed by the parallel resolution of Linear Model Predictive Control (LMPC) at each contact. This distribution is made possible thanks to emph{torquelimited friction polytopes}, an extension of friction cones that takes actuation limits into account. Individual LMPC results are finally combined back into a feasible CoM trajectory sent to the robot's wholebody controller. We validate the solution in fullbody dynamics simulation of an HRP4 humanoid falling on a wall.

MultiContact Motion Planning and Control
Karim Bouyarmane, Stéphane Caron, Adrien Escande and Abderrahmane Kheddar. Humanoid Robotics: a Reference. Edited by Ambarish Goswami and Prahlad Vadakkepat. Springer. Submitted 2017. Published 2019. (pdf)
The essence of humanoid robots is their ability to reproduce human skills in locomotion and manipulation. Early efforts in humanoid research were dedicated to bipedal walking, first on flat terrains and recently on uneven ones, while the manipulation capabilities inherit from the literature in bimanual and dexteroushand manipulation. In practice, the two problems interact largely. Locomotion in cluttered spaces benefits from extra contacts between any part of the robot and the environment, such as when grippers grasp a handrail during stair climbing, while legs can conversely enhance manipulation capabilities, such as when arching the wholebody to augment contact pressure at an endeffector. The two problems share the same background: they are governed by nonsmooth dynamics (friction and impacts at contacts) under viability constraints including dynamic stability. Consequently, they are now solved jointly. This chapter highlights the stateoftheart techniques used for this purpose in multicontact planning and control.

Supervoxel Plane Segmentation and MultiContact Motion Generation for Humanoid Stair Climbing
Tianwei Zhang, Stéphane Caron and Yoshihiko Nakamura. International Journal of Humanoid Robotics. Submitted August 2016. Published March 2017. (pdf)
Stair climbing is still a challenging task for humanoid robots, especially in unknown environments. In this paper, we address this problem from perception to execution. Our first contribution is a realtime plane segment estimation method using unorganized lidar data without prior models of the staircase. We then integrate this solution with humanoid motion planning. Our second contribution is a stair climbing motion generator where estimated plane segments are used to compute footholds and stability polygons. We evaluate our method on various staircases. We also demonstrate the feasibility of the generated trajectories in a reallife experiment with the humanoid robot HRP4.

Teleoperation System Design of Valve Turning Motions in Degraded Communication Conditions
Stéphane Caron and Yoshihiko Nakamura. RSJ 2015, Tokyo, Japan, September 2015. (pdf)
During the DARPA Robotics Challenge (DRC), robots were expected to solve a number of tasks under teleoperation by a human operator. Limits in execution time and teleoperation bandwidth required teams to implement some level of autonomy on their robots, yet meaningful input could still be provided by the operator on a regular basis via the team’s Operator Control System (OCS). The purpose of the present paper is to report on the development of Team Hydra’s OCS for the DRC in the context of the valveturning task. We describe the design of the system as well as the technical choices made, meanwhile pointing out the underlying research questions and directions for future work.
Further topics ¶
Force sensing

MultiContact Interaction Force Sensing from WholeBody Motion Capture
TuHoa Pham, Stéphane Caron and Abderrahmane Kheddar. IEEE Transactions on Industrial Informatics. Submitted November 2016. Published October 2017. (pdf)
We present a novel technique that unobtrusively estimates forces exerted by human participants in multicontact interaction with rigid environments. Our method uses motion capture only, thus circumventing the need to setup cumbersome force transducers at all potential contacts between the human body and the environment. This problem is particularly challenging, as the knowledge of a given motion only characterizes the resultant force, which can generally be caused by an infinity of force distributions over individual contacts. We collect and release a largescale dataset on how humans instinctively regulate interaction forces on diverse multicontact tasks and motions. The force estimation framework we propose leverages physicsbased optimization and neural networks to reconstruct force distributions that are physically realistic and compatible with real interaction force patterns. We show the effectiveness of our approach on various locomotion and multicontact scenarios.

WholeBody Contact Force Sensing From Motion Capture
TuHoa Pham, Adrien Bufort, Stéphane Caron and Abderrahmane Kheddar. SII 2016, Sapporo, Japan, December 2016. Best Paper Award. (pdf)
In this paper, we challenge the estimation of contact forces backed with groundtruth sensing in human wholebody interaction with the environment, from motion capture only. Our novel method makes it possible to get rid of cumbersome force sensors in monitoring multicontact motion together with force data. This problem is very challenging. Indeed, while a given force distribution uniquely determines the resulting kinematics, the converse is generally not true in multicontact. In such scenarios, physicsbased optimization alone may only capture force distributions that are physically compatible with a given motion rather than the actual forces being applied. We address this indeterminacy by collecting a largescale dataset on wholebody motion and contact forces humans apply in multicontact scenarios. We then train recurrent neural networks on real human force distribution patterns and complement them with a secondorder cone program ensuring the physical validity of the predictions. Extensive validation on challenging dynamic and multicontact scenarios shows that the method we propose can outperform physical force sensing both in terms of accuracy and usability.
Machine learning

Mixing bandits A recipe for improved coldstart recommendations in a social network
Stéphane Caron and Smriti Bhagat. SNAKDD 2013. (pdf)
Recommending items to new or “coldstart” users is a challenging problem for recommender systems. Collaborative filtering approaches fail when the preference history of users is not available. A promising direction that has been explored recently [12] is to utilize the information in the social networks of users to improve the quality of coldstart recommendations. That is, given that users are part of a social network, a new user shows up in the network with no preference history and limited social links, the recommender system tries to learn the user’s tastes as fast as possible. In this work, we model the learning of preferences of coldstart users using multiarmed bandits [5] embedded in a social network. We propose two novel strategies leveraging neighborhood estimates to improve the learning rate of bandits for coldstart users. Our first strategy, MixPair, combines estimates from pairs of neighboring bandits. It extends the wellknown UCB1 algorithm [5] and inherits its asymptotically optimal guarantees. Although our second strategy, MixNeigh, is a heuristic based on consensus in the neighborhood of a user, it performed the best among the evaluated strategies. Our experiments on a dataset from Last.fm show that our strategies yield significant improvements, learning 2 to 5 times faster than our baseline, UCB1.

Leveraging Side Observations in Stochastic Bandits
Stéphane Caron, Branislav Kveton, Marc Lelarge and Smriti Bhagat. UAI 2012. (pdf)
This paper considers stochastic bandits with side observations, a model that accounts for both the exploration/exploitation dilemma and relationships between arms. In this setting, after pulling an arm i, the decision maker also observes the rewards for some other actions related to i. We will see that this model is suited to content recommendation in social networks, where users' reactions may be endorsed or not by their friends. We provide efficient algorithms based on upper confidence bounds (UCBs) to leverage this additional information and derive new bounds improving on standard regret guarantees. We also evaluate these policies in the context of movie recommendation in social networks: experiments on real datasets show substantial learning rate speedups ranging from 2.2x to 14x on dense networks.
Motion planning

Completeness of Randomized Kinodynamic Planners with Statebased Steering
Stéphane Caron, QuangCuong Pham and Yoshihiko Nakamura. Robotics and Autonomous Systems. Submitted November 2015. Published December 2016. (pdf)
Probabilistic completeness is an important property in motion planning. Although it has been established with clear assumptions for geometric planners, the panorama of completeness results for kinodynamic planners is still incomplete, as most existing proofs rely on strong assumptions that are difficult, if not impossible, to verify on practical systems. In this paper, we focus on an important class of kinodynamic planners, namely those that interpolate trajectories in the state space. We provide a proof of probabilistic completeness for these planners under assumptions that can be readily verified from the system’s equations of motion and the userdefined interpolation function. Our proof relies crucially on a property of interpolated trajectories, termed secondorder continuity (SOC), which we show is tightly related to the ability of a planner to benefit from denser sampling. We analyze the impact of this property in simulations on a lowtorque pendulum. Our results show that a simple RRT using a secondorder continuous interpolation swiftly finds solution, while it is impossible for the same planner using standard Bezier curves (which are not SOC) to find any solution

Admissible Velocity Propagation: Beyond QuasiStatic Path Planning for HighDimensional Robots
QuangCuong Pham, Stéphane Caron, Puttichai Lertkultanon and Yoshihiko Nakamura. International Journal of Robotics Research. Submitted November 2014. Published November 2016. (pdf)
Pathvelocity decomposition is an intuitive yet powerful approach to address the complexity of kinodynamic motion planning. The difficult trajectory planning problem is solved in two separate adn simpler steps: first, find a path in the configuration space that satisfies the geometric constraints (path planning), and second, find a timeparameterization of that path satisfying the kinodynamic constraints. A fundamental requirement is that the path found in the first step should be timeparameterizable. Most existing works fulfill this requirement by enforcing quasistatic constraints in the path planning step, resulting in an important loss in completeness. We propose a method that enables pathvelocity decomposition to discover truly dynamic motions, i.e. motions that are not quasistatically executable. At the heart of the proposed method is a new algorithm — Admissible Velocity Propagation — which, given a path and an interval of reachable velocities at the beginning of that path, computes exactly and efficiently the interval of all the velocities the system can reach after traversing the path while respecting the system kinodynamic constraints. Combining this algorithm with usual samplingbased planners then gives rise to a family of new trajectory planners that can appropriately handle kinodynamic constraints while retaining the advantages associated with pathvelocity decomposition. We demonstrate the efficiency of the proposed method on some difficult kinodynamic planning problems, where, in particular, quasistatic methods are guaranteed to fail.

Computational Foundation for PlannerintheLoop MultiContact WholeBody Control of Humanoid Robots 運動計画をフィードバックループに含むヒューマノイドロボットの多点接触全身制御のための計算基盤
Stéphane Caron. PhD thesis. Defended on January 25, 2016 at the University of Tokyo (東京大学). (pdf)
In this thesis, we explore the questions of motion planning and control for humanoid robots with the aim to integrate motion planning in a fast control loop. Our contributions towards this goal revolve around three axes: kinodynamic decoupling, forcespace curtailment, and dimensional reduction of the control space. In the first one, we decouple the kinematic and dynamic components of the planning problem by an original integration with timeoptimal control methods. This approach allows us to keep planning in a geometric space, the benefits of which we demonstrate both empirically and through theoretical proofs. In the second axis, we focus on the contact aspects of planning. To avoid slippage or other contact losses, planners usually consider a large number of contact forces and their associated Coulomb friction cones. We show how this redundant representation can be reduced to contact wrenches, unique to each contacting articulation, and propose the first analytical derivation of the associated frictional wrench cone for rectangular contact surfaces. We then connect these developments to the gravitoinertial wrench for wholebody motion planning. However, we note that using wrenches for planning leads to challenging open questions such as the interpolation of the nonholonomic angular momentum. We attack this problem with a paradigm shift: rather than controlling wrenches, we generalize the notion of ZMP (point where the tangential component of the gravitoinertial moment vanishes) to that of "ZMP of a wrench". We then propose efficient algorithms to compute the associated support areas, and show how to use these tools to generate locomoting trajectories from simplified dynamics model such as the Linear Pendulum, even in arbitrary multicontact scenarios. This reduction of the control space rounds the third and last axis of the computational foundations advanced by this thesis. We demonstrate the applicability of each by simulations and empirical experiments on the HRP4 humanoid robot.

Planning with the CenterofMass rather than Stances for Humanoids Walking on Uneven Terrains
Stéphane Caron and Yoshihiko Nakamura. IFToMM 2015, Taipei, Taiwan, October 2015. (pdf)
In the current literature for nongaited humanoid motion planning, stances (i.e., contact locations) are usually planned in a first step, after which jointangle trajectories are interpolated or planned themselves. In this paper, we propose an alternative where planning is driven by centerofmass motions rather than stances. Our approach uses a randomized motion planner as its first layer to explore the space of horizontal CoM coordinates. At a lower level, we propose a custom method to extend stances based on a desired CoM position. We evaluate the ability of the resulting planner in a rubblefield 3D environment with a model of the HYDRA humanoid robot.

Kinodynamic Motion Retiming for Humanoid Robots
Stéphane Caron, QuangCuong Pham and Yoshihiko Nakamura. RSJ 2014, Fukuoka, Japan, September 2014. (pdf)
In this paper, we advocate the use of TimeOptimal Path Parameterization (TOPP) to enable planning of dynamic motions for humanoid robots. We extend the existing formulation of ZMP constraints to arbitrary polygonal areas and provide an original approach to incorporate frictional contact constraints in TOPP. We evaluate our algorithm experimentally with the HRP4 robot performing a stepping motion. Given a slow and quasistatic input motion, our method automatically produces a 2xfaster dynamic motion successfully executed on the real robot (4x faster in simulation).

Completeness of Randomized Kinodynamic Planners with Statebased Steering
Stéphane Caron, QuangCuong Pham and Yoshihiko Nakamura. ICRA 2014, HongKong, China, June 2014. (pdf)
The panorama of probabilistic completeness results for kinodynamic planners is still confusing. Most existing completeness proofs require strong assumptions that are difficult, if not impossible, to verify in practice. To make completeness results more useful, it is thus sensible to estabish a classification of the various types of constraints and planning methods, and then attack each class with specific proofs and hypotheses that can be verified in practice. We propose such a classification, and provide a proof of probabilistic completeness for an important class of planners, namely those whose steering method is based on the interpolation of system trajectories in the state space. We also provide design guidelines for the interpolation function and discuss two criteria arising from our analysis: local boundedness and acceleration compliance.

Kinodynamic Motion Planners based on Velocity Interval Propagation
Stéphane Caron, Yoshihiko Nakamura and QuangCuong Pham. RSJ 2013, Tokyo, Japan, September 2013. (pdf)
Humanoid robotics has spawned several fields of active research. When it comes to dynamic motion control, three lines of work stand out: reduced models (combined with inverse kinematics), local controllers and global planning. In the present paper, we present and further develop a motion planning approach recently proposed in [10], which allows planning with dynamics constraints while staying in the configuration space; thus avoiding the complexity explosion mentioned above. We briefly discuss how this approach can be extended to handle ZMP constraints, which may give rise to a new family of efficient motion planners for humanoid robots.

Kinodynamic planning in the configuration space via Admissible Velocity Propagation
QuangCuong Pham, Stéphane Caron and Yoshihiko Nakamura. RSS 2013, Berlin, Germany, June 2013. (pdf)
We propose a method that enables kinodynamic planning in the configuration space (of dimension n) instead of the state space (of dimension 2n), thereby potentially cutting down the complexity of usual kinodynamic planning algorithms by an exponential factor. At the heart of this method is a new technique – called Velocity Interval Propagation – which, given a path in the configuration space and an interval of reachable velocities at the beginning of that path, computes exactly and efficiently the interval of all the velocities the system can reach after traversing the path while respecting the system kinodynamic constraints. Combining this technique with usual samplingbased methods gives rise to a family of new motion planners that can appropriately handle kinodynamic constraints while avoiding the complexity explosion and, to some extent, the conceptual difficulties associated with a move to the state space
P2P storage systems

P2P Storage Systems: Study of Different Placement Policies
Stéphane Caron, Frédéric Giroire, Dorian Mazauric, Julian Monteiro and Stéphane Pérennes. PeertoPeer Networking and Applications, Springer, March 2013. (pdf)
In a P2P storage system using erasure codes, a data block is encoded in many redundancy fragments. These fragments are then sent to distinct peers of the network. In this work, we study the impact of different placement policies of these fragments on the performance of storage systems. Several practical factors (easier control, software reuse, latency) tend to favor data placement strategies that preserve some degree of locality. We compare three policies: two of them are local, in which the data are stored in logical neighbors, and the other one, global, in which the data are spread randomly in the whole system. We focus on the study of the probability to lose a data block and the bandwidth consumption to maintain such redundancy. We use simulations to show that, without resource constraints, the average values are the same no matter which placement policy is used. However, the variations in the use of bandwidth are much more bursty under the local policies. When the bandwidth is limited, these bursty variations induce longer maintenance time and henceforth a higher risk of data loss. We then show that a suitable degree of locality could be introduced in order to combine the efficiency of the global policy with the practical advantages of a local placement. Additionally, we propose a new external reconstruction strategy that greatly improves the performance of local placement strategies. Finally, we give analytical methods to estimate the mean time to the occurrence of data loss for the three policies.

Data Life Time for Different Placement Policies in P2P Storage Systems
Stéphane Caron, Frédéric Giroire, Dorian Mazauric, Julian Monteiro and Stéphane Pérennes. Globe 2010. (pdf)
Peertopeer systems are foreseen as an efficient solution to achieve reliable data storage at low cost. To deal with common P2P problems such as peer failures or churn, such systems encode the user data into redundant fragments and distribute them among peers. The way they distribute it, known as placement policy, has a significant impact on their behavior and reliability. In this paper, we study the impact of different placement policies on the data life time. More precisely, we describe methods to compute and approximate the mean time before the system loses data (Mean Time to Data Loss). We compare this metric for three placement policies: two of them local, in which the data is stored in logical peer neighborhoods, and one of them global in which fragments are parted uniformly at random among the different peers.

P2P Storage Systems Data Life Time for Different Placement Policies
Stéphane Caron, Frédéric Giroire, Dorian Mazauric, Julian Monteiro and Stéphane Pérennes. AlgoTel 2010. (pdf)
Peertopeer systems are foreseen as an efficient solution to achieve reliable data storage at low cost. To deal with common P2P problems such as peer failures or churn, such systems encode the user data into redundant fragments and distribute them among peers. The way they distribute it, known as placement policy, has a significant impact on their behavior and reliability. In this report, after a brief stateoftheart of the technology used in P2P storage systems, we compare three different placement policies: two of them local, in which the data is stored in logical peer neighborhoods, and on of them global in which fragments are parted at random among the different peers. For each policy, we give either Markov Chain Models to efficiently compute the Mean Time To Data Loss (which is closely related to the probability to lose data) or approximations of this quantity under certain assumptions. We also attempt to give lower bounds on P2P storage systems introducing the BIG system, in which we consider information globally. We propose various ways to compute a bound on the probability to lose data, in relation with parameters such as the peer failure rate of the peer bandwidth.
Signal processing

Parametric recurrence quantification analysis of autoregressive processes for pattern recognition in multichannel electroencephalographic data
Sofiane Ramdani, Anthony Boyer, Stéphane Caron, François Bonnetblanc, Frédéric Bouchara, HuguesDuffau and Annick Lesne. Pattern Recognition. Submitted July 2019. Accepted August 2020. To appear in January 2021.
Recurrence quantification analysis (RQA) is an acknowledged method for the characterization of experimental time series. We propose a parametric version of RQA, pRQA, allowing a fast processing of spatial arrays of time series, once each is modeled by an autoregressive stochastic process. This method relies on the analytical derivation of asymptotic expressions for five current RQA measures as a function of the model parameters. By avoiding the construction of the recurrence plot of the time series, pRQA is computationally efficient. As a proof of principle, we apply pRQA to pattern recognition in multichannel electroencephalographic (EEG) data from a patient with a brain tumor.
Smart grid energy management

Incentivebased Energy Consumption Scheduling Algorithms for the Smart Grid
Stéphane Caron and George Kesidis. IEEE SmartGridComm 2010. (pdf)
In this paper, we study Demand Response (DR) problematics for different levels of information sharing in a smart grid. We propose a dynamic pricing scheme incentivizing consumers to achieve an aggregate load profile suitable for utilities, and study how close they can get to an ideal flat profile depending on how much information they share. When customers can share all their load profiles, we provide a distributed algorithm, set up as a cooperative game between consumers, which significantly reduces the total cost and peaktoaverage ratio (PAR) of the system. In the absence of full information sharing (for reasons of privacy), when users have only access to the instantaneous total load on the grid, we provide distributed stochastic strategies that successfully exploit this information to improve the overall load profile. Simulation results confirm that these solutions efficiently benefit from information sharing within the grid and reduce both the total cost and PAR.