Continuous collision detection for rigid bodies

Contact Methods for Rigid Body Dynamics

Task Matrix for programming humanoid robots

Reaching for humanoid robots

Human and humanoid movement classification

O(n³) convex-optimization-based contact method

---

We have developed a contact method that runs in time O(n³) in the number of contact points. Our method is numerically robust, models Coulomb friction with a true friction cone, and scales to thousands of contact points (using our interior-point QCQP solver.)

This video demonstrates the effectiveness of this method for the problem of a simulated manipulator grasping a ball. This task is notoriously difficult to simulate, and few contact methods are capable of doing so. The video shows a manipulator arm grasping a ball while moving in a sinusoidal trajecory.

Relevant publications:

• Evan Drumwright and Dylan Shell. "Modeling Contact Friction and Joint Friction in Dynamic Robotic Simulation Using the Principle of Maximum Dissipation". Proc. of the Ninth Intl. Workshop on the Algorithmic Foundations of Robotics (WAFR). Singapore, 2010.
• Evan Drumwright and Dylan Shell. "A Robust and Tractable Contact Model for Robotic Simulation". Proc. of the 24th ACM Symp. on Applied Computing (SAC). Honolulu, 2009.

Fast, robust exponential-time contact method

---

Fast and exponential-time are generally contradictory terms in Computer Science. Nevertheless, we have developed an exponential-time algorithm (in the number of contact points) that not only runs in O(n³) time typically, but is even faster than competing O(n³) methods in general. This method produces frictional effects and is energetically consistent.

A holonomic mobile robot simulated using this method.

Relevant publication:

• This work is currently under review.

Advanced penalty method for rigid body simulation

My advanced penalty method works by applying forces over the volume of penetration, rather than applying a force due to only a single, virtual spring and damper at the point of deepest 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.

This video shows the ability of the advanced penalty method to handle a stable pile of objects.

Relevant publication:

• Evan Drumwright. A Fast and Stable Penalty Method for Rigid Body Simulation. IEEE Trans. on Visualization and Computer Graphics. vol. 14, no. 1, pp. 231-240, January/February, 2008.