Publications

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 pre-prints 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

Contact stability

Walking trajectory generation

Multi-contact motion control

Further topics

Force sensing
  • Multi-Contact Interaction Force Sensing from Whole-Body Motion Capture
    Tu-Hoa 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 multi-contact 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 large-scale dataset on how humans instinctively regulate interaction forces on diverse multi-contact tasks and motions. The force estimation framework we propose leverages physics-based 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 multi-contact scenarios.

  • Whole-Body Contact Force Sensing From Motion Capture
    Tu-Hoa 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 ground-truth sensing in human whole-body interaction with the environment, from motion capture only. Our novel method makes it possible to get rid of cumbersome force sensors in monitoring multi-contact 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 multi-contact. In such scenarios, physics-based 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 large-scale dataset on whole-body motion and contact forces humans apply in multi-contact scenarios. We then train recurrent neural networks on real human force distribution patterns and complement them with a second-order cone program ensuring the physical validity of the predictions. Extensive validation on challenging dynamic and multi-contact 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 cold-start recommendations in a social network
    Stéphane Caron and Smriti Bhagat. SNAKDD 2013. (pdf)

    Recommending items to new or “cold-start” 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 cold-start 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 cold-start users using multi-armed bandits [5] embedded in a social network. We propose two novel strategies leveraging neighborhood estimates to improve the learning rate of bandits for cold-start users. Our first strategy, MixPair, combines estimates from pairs of neighboring bandits. It extends the well-known 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 State-based Steering
    Stéphane Caron, Quang-Cuong 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 user-defined interpolation function. Our proof relies crucially on a property of interpolated trajectories, termed second-order 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 low-torque pendulum. Our results show that a simple RRT using a second-order 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 Quasi-Static Path Planning for High-Dimensional Robots
    Quang-Cuong Pham, Stéphane Caron, Puttichai Lertkultanon and Yoshihiko Nakamura. International Journal of Robotics Research. Submitted November 2014. Published November 2016. (pdf)

    Path-velocity 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 time-parameterization of that path satisfying the kinodynamic constraints. A fundamental requirement is that the path found in the first step should be time-parameterizable. Most existing works fulfill this requirement by enforcing quasi-static constraints in the path planning step, resulting in an important loss in completeness. We propose a method that enables path-velocity decomposition to discover truly dynamic motions, i.e. motions that are not quasi-statically 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 sampling-based planners then gives rise to a family of new trajectory planners that can appropriately handle kinodynamic constraints while retaining the advantages associated with path-velocity decomposition. We demonstrate the efficiency of the proposed method on some difficult kinodynamic planning problems, where, in particular, quasi-static methods are guaranteed to fail.

  • Computational Foundation for Planner-in-the-Loop Multi-Contact Whole-Body 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, force-space 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 time-optimal 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 gravito-inertial wrench for whole-body motion planning. However, we note that using wrenches for planning leads to challenging open questions such as the interpolation of the non-holonomic 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 gravito-inertial 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 multi-contact 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 HRP-4 humanoid robot.

  • Planning with the Center-of-Mass 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 non-gaited humanoid motion planning, stances (i.e., contact locations) are usually planned in a first step, after which joint-angle trajectories are interpolated or planned themselves. In this paper, we propose an alternative where planning is driven by center-of-mass 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 rubble-field 3D environment with a model of the HYDRA humanoid robot.

  • Kinodynamic Motion Retiming for Humanoid Robots
    Stéphane Caron, Quang-Cuong Pham and Yoshihiko Nakamura. RSJ 2014, Fukuoka, Japan, September 2014. (pdf)

    In this paper, we advocate the use of Time-Optimal 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 HRP-4 robot performing a stepping motion. Given a slow and quasi-static input motion, our method automatically produces a 2x-faster dynamic motion successfully executed on the real robot (4x faster in simulation).

  • Completeness of Randomized Kinodynamic Planners with State-based Steering
    Stéphane Caron, Quang-Cuong Pham and Yoshihiko Nakamura. ICRA 2014, Hong-Kong, 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 Quang-Cuong 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
    Quang-Cuong 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 sampling-based 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. Peer-to-Peer 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)

    Peer-to-peer 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)

    Peer-to-peer 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 state-of-the-art 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
  • Incentive-based 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 peak-to-average 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.