Legged robots that operate in the real world are inherently subject to stochasticity in their dynamics and uncertainty about the terrain. Owing to limited energy budgets and limited control authority, these “disturbances” cannot always be canceled out with high-gain feedback. Minimally actuated walking machines subject to stochastic disturbances no longer satisfy strict conditions for limit-cycle stability; however, they can still demonstrate impressively long-living periods of continuous walking. Here, we employ tools from stochastic processes to examine the “stochastic stability” of idealized rimless-wheel and compass-gait walking on randomly generated uneven terrain. Furthermore, we employ tools from numerical stochastic optimal control to design a controller for an actuated compass gait model which maximizes a measure of stochastic stability—the mean first-passage time—and compare its performance with a deterministic counterpart. Our results demonstrate that walking is well characterized as a metastable process, and that the stochastic dynamics of walking should be accounted for during control design in order to improve the stability of our machines.
Au, S.K. (2004). Probabilistic failure analysis by importance sampling Markov chain simulation. Journal of Engineering Mechanics , 130:(3) 303-311.
2.
Boone, G. (1997). Minimum-time control of the acrobot. IEEE International Conference on Robotics and Automation (ICRA), Vol. 4, pp. 3281-3287.
3.
Bovier, A. (2004). Metastability and ageing in stochastic dynamics. Dynamics and Randomness II, Maas, A., Martinez, S. and Martin, J. S. (eds). Dodrecht, Kluwer , pp. 17-81.
4.
Bovier, A., Eckhoff, M., Gayrard, V. and Klein, M. (2000). Metastability and small eigenvalues in Markov chains. Journal of Physics A: Mathematical and General, 33(46): L447-L451.
Boyd, S., Diaconis, P. and Xiao, L. (2004). Fastest mixing Markov chain on a graph. SIAM Review, 46(4): 667-689.
7.
Brown, S.C. and Passino, K.M. (1997). Intelligent control for an acrobot. Journal of Intelligent and Robotic Systems, 18: 209-248.
8.
Byl, K. and Tedrake, R. (2006). Stability of passive dynamic walking on uneven terrain. Proceedings of Dynamic Walking II, Kuo, A. (ed.).
9.
Byl, K. and Tedrake, R. (2008a). Approximate optimal control of the compass gait on rough terrain. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA).
10.
Byl, K. and Tedrake, R. (2008b). Control of the compass gait on rough terrain . Proceedings of Dynamic Walking IV, Wisse, M. (ed.).
11.
Byl, K. and Tedrake, R. (2008c). Metastable walking on stochastically rough terrain . Proceedings of Robotics: Science and Systems IV.
12.
Coleman, M.J. (1998). A stability study of a three-dimensional passive-dynamic model of human gait. PhD Thesis, Cornell University.
13.
Coleman, M.J., Chatterjee, A. and Ruina, A. (1997). Motions of a rimless spoked wheel: A simple 3D system with impacts. Dynamics and Stability of Systems, 12(3): 139- 160.
14.
Collins, S.H., Ruina, A., Tedrake, R. and Wisse, M. (2005). Efficient bipedal robots based on passive-dynamic walkers. Science, 307: 1082-1085.
15.
Garcia, M., Chatterjee, A., Ruina, A. and Coleman, M. (1998). The simplest walking model: Stability, complexity, and scaling. Journal of Biomechanical Engineering- Transactions of the ASME, 120(2): 281-288.
16.
Gardiner, C. (2004). Handbook of Stochastic Methods for Physics, Chemistry and the Natural Sciences (3rd edn). Berlin, Springer.
17.
Gaveau, B. and Schulman, L.S. (1998). Theory of non-equilibrium first-order phase transitions for stochastic dynamics. Journal of Mathematical Physics, 39(3): 1517- 1533.
18.
Goswami, A., Espiau, B. and Keramane, A. (1996a). Limit cycles and their stability in a passive bipedal gait. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 246-251.
19.
Goswami, A., Thuilot, B. and Espiau, B. (1996b). Compass-like biped robot part I : Stability and bifurcation of passive gaits. Technical Report RR-2996, INRIA.
20.
Hanggi, P., Talkner, P. and Borkovec, M. (1990). Reaction-rate theory: Fifty years after Kramers . Reviews of Modern Physics, 62(2): 251-342.
21.
Hodgins, J. and Raibert, M. (1991). Adjusting step length for rough terrain locomotion . IEEE Transactions on Robotics and Automation, 7(3): 289-298.
22.
Horenko, I., Dittmer, E., Fischer, A. and Schutte, C. (2006). Automated model reduction for complex systems exhibiting metastability. Multiscale Modeling and Simulation , 5(3): 802-827.
23.
Huisinga, W., Meyn, S. and Schutte, C. (2004). Phase transitions and metastability in Markovian and molecular systems. Annals of Applied Probability, 14(1): 419-458.
24.
Iida, F. and Tedrake, R. (2009). Minimalistic control of a compass gait robot in rough terrain. Proceedings of the IEEE/RAS International Conference on Robotics and Automation (ICRA).
25.
Jain, S. and Jain, R.K. (1994). Problems of estimating meantime system failure . Microelectronics and Reliability, 34(11): 1755-1760.
26.
Kampen, N.V. (2007). Stochastic Processes in Physics and Chemistry (3rd edn). Amsterdam, Elsevier.
27.
Koditschek, D.E. and Buehler, M. (1991). Analysis of a simplified hopping robot. The International Journal of Robotics Research, 10(6): 587-605.
28.
Kuo, A.D., Donelan, J.M. and Ruina, A. (2005). Energetic consequences of walking like an inverted pendulum: Step-to-step transitions. Exercise and Sport Science Reviews, 33(2): 88-97.
29.
Larralde, H. and Leyvraz, F. (2005). Metastability for markov processes with detailed balance. Physical Review Letters, 94(16): 160201.
30.
Manchester, I.R., Mettin, U., Iida, F. and Tedrake, R. (2009). Stable dynamic walking over rough terrain: theory and experiment. To appear in Proceedings of the 14th International Symposium on Robotics Research.
31.
McGeer, T. (1990). Passive dynamic walking. The International Journal of Robotics Research, 9(2): 62-82.
32.
Muller, R., Talkner, P. and Reimann, P. (1997). Rates and mean first passage times. Physica A, 247(247): 338-356.
33.
Munos, R. and Moore, A. (1998). Barycentric Interpolators for Continuous Space and Time Reinforcement Learning, Kearns, M. S., Solla, S. A. and Cohn, D. A. (eds) (Advances in Neural Information Processing Systems, Vol. 11). Cambridge, MA, NIPS/MIT Press.
34.
Munos, R. and Moore, A. (2002). Variable resolution discretization in optimal control. Machine Learning, 49(2/3): 291-323.
35.
Spong, M.W. (1994). Swing up control of the acrobot. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 2356-2361.
36.
Spong, M.W. (1997). Underactuated mechanical systems. Control Problems in Robotics and Automation, Siciliano, B. and Valavanis, K. P. (eds) (Lecture Notes in Control and Information Sciences, Vol. 230). Berlin, Springer.
37.
Spong, M.W. and Bhatia, G. (2003). Further results on control of the compass gait biped. Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), pp. 1933-1938.
38.
Sutton, R.S. and Barto, A.G. (1998). Reinforcement Learning: An Introduction. Cambridge, MA, MIT Press.
39.
Talkner, P., Hanggi, P., Freidkin, E. and Trautmann, D. (1987). Discrete dynamics and metastability: Mean first passage times and escape rates. Journal of Statistical Physics , 48(1/2): 231-254.
40.
Tedrake, R.L. (2004). Applied optimal control for dynamically stable legged locomotion. PhD Thesis, Massachusetts Institute of Technology.
41.
Vijayakumar, S., D'Souza, A. and Schaal, S. (2005). Incremental online learning in high dimensions . Neural Computation, 17: 2602-2634.
42.
Weber, M., Kube, S., Walter, L. and Deuflhard, P. (2006). Stable computation of probability densities for metastable dynamical systems. Technical Report ZIB-Report 06-39, Konrad-Zuse-Zentrum fur Informationstechnik Berlin.
