Optimal Motion Generation

Interpolation Methods based on Learned Movements

Of all the remarkable physical abilities of humans, motor control is the skill that is most often taken for granted, as it seems to require the least conscious effort on our part. Only when a particular motor skill is impaired or lost do we then begin to appreciate the difficulty of the motor control and learning process. It comes as no surprise that these exact same difficulties are encountered when attempting to endow robots with motor learning skills like that of humans.

Dancing motions generated for the KIBO humanoid robot
Although we perform everyday motions quite effortlessly, it is all too easy to forget that some of these motor skills are acquired only after considerable effort, in some cases after years of practice. From a child learning to throw a ball or swing a bat, to an adult perfecting her golf swing or practicing calligraphy, or a gymnast mastering a new tumbling routine, these seemingly quite distinct motor skills become a part of our motion vocabulary only after years of practice.

Yet we can can still infer some common sequence of events in the motor learning process. Upon first learning the skill, the resulting motion is usually crude and awkward, lacking grace and fluidity. Initially it appears as if only a few degrees of freedom are deliberately controlled, with the remaining degrees of freedom either frozen in place or ``pulled along'' by mechanical and other constraints. Then, as the motion is practiced, the once-locked degrees of freedom now seemingly begin to unlock, and move in coordination with the primary degrees of freedom. As the motion is perfected, all the degrees of freedom work synchronously to create a fluid and natural looking motion. In most cases the resulting motion is optimized in some sense with respect to some physical criterion.

There is another common feature to the motor learning process: the diminishing reliance on feedback as learning takes place. Initially the motion will be guided and corrected by some form of sensory feedback, e.g., visual or tactile. With practice, the resulting motion appears more and more as if a preloaded motor program is being played. In control theory terminology, this transition can be described as moving from a closed-loop to an open-loop control structure.

Clearly motor learning encompasses a much broader set of issues than the ones touched upon above. There is, for example, the complex interplay between the different modalities of perception and action, as well as higher levels of ``physical" intelligence, and the synthesis of ``balancing" and ``task" movement primitives. Our current work in this area focuses on both optimal movement generation and interpolation methods based on learned movements, as well as how elements of both methods can be merged within a unified framework.



Optimal Movement Generation

There is ample biological evidence to justify an optimization-based approach to motor control and learning. Indeed, in the literature one can find many optimal control-based studies of various human motions, e.g., maximum-height jumping, voluntary arm movements, maintaining postural balance, minimum-time running and swimming, even wheelchair propelling. Besides some of the more obvious optimization criteria like minimum energy or control effort, strategies that involve minimizing the jerk, as well as muscle or metabolic energy costs, have also been examined in the context of specific arm motions.

Models for human motor learning and control that take into account both the muscle dynamics and features of the neural system have been proposed, and extensive studies of the cerebellum and its role in motor learning and control have also been performed. The most predominant models adopt a cybernetic metaphor, in which the body is treated as a machine that receives sensory inputs and generates motor outputs. Proponents of the equilibrium point hypothesis argue that motions are generated according to a potential field determined by the endpoints of the movement. Still others have argued that the nervous system performs inverse dynamics to generate the motor commands, with recent research suggesting that it is possible to identify accurate internal models from movement data, and that such strategies can be successfully implemented in robots. More recent is the evidence suggesting that inverse dynamics-based feedforward computations are also an integral part of human movement planning, particularly for fast movements.

From an engineering perspective an optimization-based approach to motion generation usually comes to mind as the first reasonable thing to try. Past approaches have usually failed, however, because the complexity of the governing equations of motion usually led to intractable optimization problems. Indeed, the intractability of the optimization seems at least partly (if not largely) responsible for the recent flurry of attention given to, e.g., neural networks, genetic algorithms, and other evolutionary optimization approaches to motor learning.

One of the arguments that we put forth is that, like the view of the cerebellum as a computational engine for dynamics, model-based motor learning based on classical descent-type optimization methods is indeed a computationally feasible paradigm. Aside from the complexity of the nonlinear dynamics, another reason classical descent methods, despite their reliability (indeed, in many cases these algorithms are the only ones that can guarantee local optimality and convergence), are bypassed in most motor learning schemes is their reliance on gradient and Hessian information. Although in principle one can numerically approximate these quantities, for problems involving even moderately complex multibody systems, approximated gradients and Hessians more often than not lead to ill-conditioning, instability, and poor convergence behavior, not to mention a significant increase in the computational burden.

What we have discovered in our research is that by appealing to techniques from the theory of Lie groups, it is possible to formulate the equations of motion of even complicated antagonistic multibody systems like the human body in such a way as to render the optimization problem tractable. In many cases the solutions can even be obtained quite efficiently and in a numerically robust way. We can, for example, pose the active balancing problem as a second-order cone programming problem, for which efficient interior point optimization algorithms are available. Human motions that minimize muscle metabolic energy can also be reliably generated.

One of the keys lies in the ability to recursively evaluate the nonlinear dynamics, and also to recursively compute exact analytic gradients and Hessians without resorting to numerical approximations. The resulting algorithms, while still computation-intensive, are O(n) with respect to the number of rigid bodies comprising the system.

  Balancing on a sliding floor   Balancing on a spinning floor
  Minimum torque parallel bar motion   Minimm torque rowing
  Minimum metabolic energy pedaling   Minimum metabolic energy walking

Related Publications

J.E. Bobrow, F.C. Park, and Athanasios Sideris, ``Progress on the Algorithmic Optimization of Robot Motion," in Fast Motions in Biomechanics and Robotics: Optimization and Feedback Control, Diehl, Moritz; Mombaur, Katja (Eds.) , Lecture Notes in Control and Information Sciences , Vol. 340, Springer-Verlag, October 2006.

Juyong Park, Jaeyoung Han, and F.C. Park, ``Convex optimization algorithms for active balancing of humanoid robots," IEEE Transactions on Robotics, Vol. 23, No. 4, pp. 817-822, August 2007.

Sunghee Lee, Junggon Kim, F.C. Park, Munsang Kim and J.E. Bobrow, ``Newton-type algorithms for dynamics-based robot movement optimization," IEEE Trans. Robotics Vol. 21, No. 4, pp. 657-667, August 2005.

J. E. Bobrow, B. Martin, G. Sohl, E. C. Wang, Junggon Kim and F. C. Park, ``Optimal robot motions for physical criteria," J. Robotic Systems, Vol. 18, No. 12, pp. 785-795, Dec 2001.

Albro, J.V., Sohl, G.A., Bobrow, J.E. and Park, F.C., ``On the computation of optimal high dives," Proc. IEEE Conference on Robotics and Automation, San Francisco, 2000.


Interpolation Methods Based on Learned Movements

By now there is general agreement that humans learn a great variety of movements, and that these movements are stored in some form in our memories. What still remains unresolved is the exact nature of these building blocks, or modules, for generating movements, and how these modules are used to generate new movements. The idea that inverse dyanamics-based trajectories are stored in table form for every possible movement has by now been dispelled on computational arguments. On the other hand it has also become clear that the human movement generation paradigm is fundamentally driven by the central nervous system's remarkable capacity for storage and retrieval of large amounts of data.

Our main motivation is to develop a method for generating natural motions in an efficient manner: we seek to overcome the two main disadvantages of dynamics-based motion optimization, i.e., the heavy computational burden, and the lack of modularity and reusability. The innovative features of our approach are (i) to select and classify a set of movement primitives, and to store these as a family of basis functions; (ii) to extract these basis functions from a factorization analysis of observed human movements, and (iii) to perform higher-level processing (e.g., dynamics-based motion optimization, construct Hidden Markov model representations) using these basis functions to generate natural motions in real-time.


Movement generation framework

In the block diagram describing our movement generation framework, given a high-level description of a desired task, the task parser interprets this description and generates a corresponding sequence of desired movements. The movement compiler then takes this sequence as input and, drawing upon the database of movement primitives, constructs an appropriate movement sequence plan consisting of feedforward and feedback terms to be applied over given epochs. The movement compiler performs a combination of local optimization and learning, motion interpolation, and motion blending and smoothing, all the while ensuring that any physical and user-specified motion constraints are satisfied.

The movement primitives are stored as a family of basis functions, which are extracted from a factorization analysis (e.g., principal component analysis, independent component analysis, or nonnegative matrix factorization) of movement data. For example, arm motions can be classified into reaching, swinging, lifting objects, and various grasping and fine manipulation movements. Arbitrary movements are then generated as linear combinations of the basis functions such that they satisfy boundary conditions and other feasibility criteria.



HMM designed and trained using human motion capture data to represent the specific arm motion.
The optimized arm motion that maximizes the probability for the trained HMM. In the optimization, we use the motion basis elements extracted from the PCA of motion capture joint angle trajectories.


HMM-optimized motion(left) versus torque-minimized motion(right). Both hand-raising motions are generated with the same boundary condition and motion basis elements(principal components). Note that the HMM-optimized motion appears more human-like.

Related Publications

F.C. Park and Gyusang Jo, ;Movement primitives and principal component analysis," Advances in Robot Kinematics (J. Lenarcic and C. Galletti, Eds.), Kluwer, Dordrecht, 2004

Bokman Lim, Syungkwon Ra, and F.C. Park, "Movement primitives, principal component analysis, and the efficient generation of natural motions" , in Proc. IEEE Conference on Robotics and Automation, Barcelona, 2005

Junghyun Kwon and F. C. Park, "Using hidden Markov models to generate natural humanoid movement," in Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, Beijing, 2006