Humanoid Robotics: The Math Behind Human Beings
Recent advances are blurring the line between sci-fi and reality
When we were kids, robots meant C-3PO from Star Wars. For the more seasoned among us, maybe Robby the Robot from Forbidden Planet. Ever since Fritz Lang’s landmark film Metropolis introduced us to the first big-screen robot Maria, the notion of the robot with human-like form and articulation has carried through pop culture. Recently, with the aid of some new mathematical techniques and some powerful new computing tools, scientists and engineers are starting to realize a part of this dream.
One of the most remarkable demonstrations of how far engineering has come is the work of the Takanishi Laboratory of Waseda University in Tokyo.1 Dr. Atsuo Takanishi is a leading researcher in the area of humanoid robotics. Unlike the industrial robots with which most engineers are typically familiar, humanoid robotics research aims to emulate human motion and even behavior — anthropomorphic robot.
Professor Takanishi’s achievements include the WABIAN series of robots (short for Waseda bipedal humanoid) noted for its ability to walk in a very human-like way. The Takanishi Lab’s Web site offers a range of photos and videos of WABIAN and its kin. In order to achieve the right gait patterns, natural rhythms and maintain stability on various walking surfaces, the lab’s scientists have developed sophisticated techniques to model and simulate the biomechanics prior to commitment in a physical robot.
According to his research papers, an adequate model of WABIAN requires a minimum eight degrees of freedom (DOF). Typically, the actual number of simultaneous model equations that result from real-world mechanisms operating in three-dimensional space can be significantly higher than the number of DOF. These equations would normally be coupled differential algebraic equations (DAE), ultimately creating a challenge for any modern solver. In sum, there are two major technical challenges: derivation of the model mathematics and the solution of the model equations themselves.
Takanishi has developed a series of specialized techniques to derive and solve these equations — an approach that would literally take months to work out the mathematics and ensure all of the geometric and physical continuities. Historically, advanced modeling cases like these demanded such specialized attention and human-intensive steps. However, more recently, techniques and tools have emerged to provide a systematic framework for dealing with such complexity.
At the recent 2007 Society of Automotive Engineers (SAE) Digital Human Modeling for Design and Engineering conference,2 Professor Asif Mughal of the University of Arkansas presented the results of modeling 3-D bipedal human motion. This research was motivated not so much to design androids of the future, but to handle immediate challenges for prosthetics with active control. The mechanism that Mughal modeled was a complex 12 DOF system with nine joints — comparable complexity to Takanishi’s models. One particular difference between Mughal’s and Takanishi’s projects, however, was the utilization of very recent software technology on Mughal’s part.
Mughal’s model employed a combination of modern symbolic mathematical computation technology and a new technology that automatically generates the fundamental equations of motion for dynamic models of arbitrary 3-D systems. In particular, he used the symbolic capabilities of Maplesoft’s Maple system, and MotionPro’s DynaFlexPro add-on for the model formulation.
Neither symbolic computation nor Maple is new. Indeed, Maple and Mathematica have been around since the early 1980s, but they were preceded by venerable names such as MACSYMA,
click to enlarge
A 3-D bipedal system model definition.
Reduce and ALTRAN, among others. Symbolic mathematics on a computer can manipulate equations and expressions as you would on a piece of paper: they can solve analytically, compute symbolic derivatives, and generally apply the rules of mathematics in an efficient and error-free way. Consequently, for derivations of models, they constitute an ideal platform.
Automatic model generation systems are somewhat less well-known. DynaFlexPro is the brainchild of MotionPro chief scientist John McPhee (also a professor at the University of Waterloo, Canada). The software allows you to specify the general configuration and component parameters of arbitrary 3-D mechanisms. Then, using the symbolic capabilities of the Maple system, it will automatically generate the required model equations. In essence, it automates the traditional modeling tasks requiring reams of paper and shelves full of reference books.
There are some very popular modeling systems that perform similar tasks. For example, there is the famous ADAMS system from MSC and the SimMechanics add-on to MATLAB and Simulink from The MathWorks. These systems provide a comprehensive environment for developing and simulating mechanical models. According to McPhee, Mughal and others, such systems are not efficient for mechanical systems of increasing complexity like the human motion models. For example, the ADAMS mathematical framework can only formulate models in absolute coordinates, which results in massive model equations that are very difficult to manage in the simulation phase. Conversely, Takanishi, tools like DynaFlexPro, and many on the vanguard of this research employ smaller sets of coordinates, often associated with the joints in the system. This one difference can be critical in the feasibility of modeling human motion systems.
Although DynaFlexPro is a relatively new tool, the theory underneath is not. It uses a technique based on linear graph theory and the Graph-Theoretic Method (GTM) for physical systems. Of course, graph theory itself dates back to Euler in the 1700s and is one of the most important mathematical tools applied in the modern world.
McPhee describes GTM as a simple, organized technique for creating mathematical models of discrete physical systems. GTM combines linear graph theory, which derives from topology (the study of how things are interconnected — a branch of the mathematical field of combinatorics), with the physical characteristics of engineering components. The resulting technique is ideally suited for computer creation and solution of the mathematical models of physical systems. More specifically, GTM provides algorithms for automatically generating the differential-algebraic equations governing the dynamic behavior of a wide range of physical systems.GTM was pioneered in the 1960s and 1970s at the University of Waterloo, M.I.T. and Michigan State University. However, it remained a theoretical novelty until technology caught up (in the form of fast symbolic computation). The combination of DynaFlexPro and Maple is the first commercially viable implementation of this method. Outside of biomechanical applications, GTM is gaining popularity within the automotive and aerospace sectors.
The end result of this combination of pure math, scientific creativity and modern computing is generally the reduction of model development time from as high as months to days or even less. In addition to the time savings, another major benefit is emerging from the symbolic computation world. Historically symbolic computation has always taken a back seat to numeric computation when it came to speed. A common Runge-Kutta routine could easily out-compute symbolic differential equation solvers in a head-to-head competition.
Today, the line between symbolic and numeric computation is blurring. For example, in the solution of mechanical simulation models, a symbolic model derived using the kind of techniques described here has been shown to
click to enlarge
Representation of a mechanical system using linear graph theory.
compute up to 10 times faster than those developed using traditional numerical techniques. For example, in the solution of these equations, you need to compute derivatives in order to assemble the Jacobian matrix. Traditional methods must reformulate the entire model and compute the Jacobian at each time step, inducing a major computational burden. Symbolic methods pre-compute the derivatives as symbolic expressions thus avoiding the costly computations later.
Another development emerging from the symbolic world is the treatment of differential algebraic equations (DAEs), which are a general form of differential equation. Unlike systems of regular differential equations, DAEs may include coupled algebraic equations. Any known technique typically attempts to transform the DAE system to equivalent ordinary differential equation (ODE) systems that can then be solved. Unfortunately, this is a nontrivial task and the reliable solution of high-index DAEs remains a major research challenge.
Interestingly, the field of symbolic computation is, again, stepping up to the plate to advance the state-of-the-art in DAE solving. One of the things that symbolic algorithms are very good at are complex substitutions and transformation of mathematical expressions. Consequently, many new techniques have been explored and developed to solve ever-more complex DAEs. McPhee cites Maple’s progress in this field as one of the reasons why he chose this system for his modeling platform. Currently, Maple is one of the few commercial math packages that have specific extensions to handle DAEs.
As scientists and engineers, we work with many things that would seem miraculous to those who preceded us. However, nothing seems more miraculous than something that seems to emulate us. Whether it’s a carnival mechanical fortune teller, or a gorilla who can “read,” or a proper sci-fi android, we chuckle, wonder or worry when we encounter them. With modern advancements in computing and the creative application of genius mathematical concepts, we are now firmly stepping into this sci-fi world. Although the talking, overly-emotional robot of our movies may still be a few years away, a robot that can walk and carry our grand-parents’ groceries may be only a few differential equations away.
Tom Lee is Vice President of Market Development at Maplesoft. He is the chief editor of MaplePrimes.com, a blogging and forum site for mathematical software, and is the host of the biweekly podcast series MapleCast. He may be contacted at editor@ScientificComputing.com.
DAE Differential Algebraic Equation | DOF Degrees of Freedom | GTM Graph-Theoretic Method | ODE Ordinary Differential Equation | SAE Society of Automotive Engineers | WABIAN Waseda Bipedal Humanoid