O(n3) exact, robust contact method

I have recently developed (in collaboration with Dylan Shell), an exact, robust contact method that runs in time O(n3) in the number of contact points. Our method is not only asymptotically faster than the O(n4) expected-time LCP-based methods, but is numerically robust, and works with arbitrary articulated body formulations (maximal and reduced-coordinate) and integrators (Euler, Runge-Kutta, Verlet, etc.)

The method has been completed and tested fairly rigorously; details will follow after the method has been accepted for publication. Stay tuned.

Advanced penalty method for rigid body simulation

One of the state-of-the-art methods for rigid body simulation determines the exact contact forces necessary to prevent interpenetration and approximate Coulomb friction using a linear complementarity formulation. However, not only is solving this linear complementarity problem relatively slow, solutions may not exist. I propose an alternative that is based upon the simple penalty method, an approach that applies forces to bodies in contact using virtual springs and dampers.

Rather than applying forces due to only a single spring and damper as is standard, I apply forces at a subset of the volume of penetration. Applying forces at multiple points reduces the oscillation that emerges from the standard approach. Additionally, I use an integrative term to reduce steady-state error, which permits less stiff gain constants to be used for the virtual springs and dampers; the resulting equations of motion are much more stable numerically.


A simple mobile robot simulated using my advanced penalty method.

Relevant publication:

Task Matrix

My dissertation investigated means to program behaviors on humanoid robots. Programming humanoid robots to execute arbitrary tasks is difficult for numerous reasons, including high kinematic redundancy, complex dynamics, and the problems involved with balancing and locomotion. Additionally, once behaviors have been developed, "porting" a program to a robot with even slightly different kinematics or dynamics is generally quite difficult. Consequently, behaviors are typically written anew, thus ignoring one of the key tenets of software development, component reuse.

The Task Matrix (from the definition for matrix as a surrounding medium or structure) framework promotes portability of humanoid behaviors by providing a consistent interface to access robot hardware; in collaboration with Honda Research Institute, USA, I have developed robot-independent behaviors such as pointing, reaching, and fixating.

My dissertation examined how the Task Matrix can be used to perform occupational tasks (i.e., tasks performed in the workplace). I implemented a large subset of the MTM-1 work measurement system's task primitives; MTM-1 is a proven system for decomposing occupational tasks into primitives. Thus, a full implementation of MTM-1 provides some measure of completeness over the space of occupational tasks. The combination of the robot-independence provided by the Task Matrix framework and the approximate completeness offered by the MTM-1 inspired behaviors results in a constantly improving set of behaviors for performing useful tasks.

Please see the videos page for depictions of primitive and complex task programs running on simulated humanoid robots and ASIMO.

Relevant publications:

Reaching for humanoid robots

Reaching (for use with pick-and-place tasks) with humanoid robots in a collision-free manner is difficult for humanoid robots due to the high degree of kinematic redundancy and the PSPACE-complete complexity of motion planning. The papers below examine approaches applicable toward reaching in static environments; the paper by Drumwright, Kallmann, and Mataric' additionally proposes possible methods for reaching in dynamic environments.

Classification of human and humanoid movement

We used models of human movements (which we labeled primitives) to build distributions of movement corresponding to the individual models. A Bayesian classifier was then implemented to categorize observed movement. This method performs very well, and is described in the following two papers: