Roy's Research

Over the years, Roy has contributed to rigid-body dynamics theory and algorithms; to robot kinematics, dynamics and control; and to robot mechanical design and actuation technology.  There is a simple common thread running through all of this, which is

Roy is particularly interested in motions and physical behaviours (like balancing, compliance and legged locomotion) in which the dynamics cannot be ignored.

While Roy was studying Khatib's idea of a dynamically consistent inverse of the Jacobian matrix, which plays a key role in Khatib's oper­ational-space control scheme, it occurred to Roy that this matrix ought to be inde­pendent of load inertia, and that such inde­pen­dence would lead to some useful simplifi­cations and improve­ments to oper­ational-space control.  So he investi­gated, and his hunch turned out to be correct.  The work was published in this journal article.

This was a very short project, but it marked Roy's return to dynamics after many years of focussing mainly on kinematics.

The objective was to create an algorithm that would calculate the forward dynamics of a large system of rigid bodies quickly on a parallel computer—in particular, to do it in O(log(N)) time on a computer with O(N) processors, where N is the number of bodies.

Roy developed an algorithm that solves this problem by a recursive divide-and-conquer technique: the given rigid-body system is cut into two independent subsystems, the dynamics of each is calculated in parallel (by recursive application of the divide-and-conquer algorithm), then they are reconnected, and the motion of the original system is computed from the dynamics of the two subsystems.  The details can be found in this two-part paper: part 1 and part 2.

This algorithm turned out to be the first in a new category of dynamics algorithms, and today you will find many more in this category, invented by other researchers.

One issue that Roy spotted early on is that the numerical accuracy of this type of algorithm is not good.  This issue does not appear to have received much attention.

Having invented the divide-and-conquer dynamics algorithm, Roy needed to generate a variety of test cases in order to test both its correctness and its numerical accuracy.  The solution he came up with was to use fractal robots, which he defined as rigid-body systems in which at least one aspect of their structure or configuration was fractal in nature.  Some definitions and some pretty pictures can be found on this fractal robots page.

The Constraint Force algorithm (CFA) developed by Dr. Fijany et al. was the first published dynamics algorithm to achieve O(log(N)) time complexity for a chain of N rigid bodies on a parallel computer with O(N) processors.  The original version was applicable only to systems in which the bodies were connected together in an unbranched chain, using a restricted set of joint types.  In this project, we developed a new version that overcame these restrictions; and the work was published in this journal article.

Perhaps more important than the algorithm itself, is the technique used to derive it.  Roy called it the change-of-basis technique, but it is really a general method for the mathematical analysis of motion and force constraints in a vector space and its dual.  Roy used it subsequently in the hybrid motion/force control project, which is the next project on this page.

A subsequent collaboration with Dr. Fijany, when he was working at IIT, yielded this follow-on paper.

The aim of this project was to replace the Raibert/­Craig contact model used in hybrid motion/­force control with a more general contact model having the following three properties:

1. it takes into account kinematic constraints within the robot mechanism, such as an end-effector with fewer than 6 degrees of freedom;
2. it models general kinematic constraints between the robot and its environmemt (the Raibert/­Craig model is not general); and
3. it takes into account the instantaneous dynamics of the environment, even if that dynamics is unknown.

One particularly noteworthy property of this model is that it dynamically decouples the force and motion control channels even when the environment's dynamics is unknown.  The new model we developed is theoretically sound, and those parts of it that have been experimentally verified indicate that the model also works in practice.  This project yielded two conference papers (#1, #2) and one journal article.

It is well known that the joint-space inertia matrix (JSIM) of a robot mechanism is a symmetric, positive-definite matrix, and that such matrices are guaranteed to be nonsingular.  However, it is less well known that the condition number of the JSIM can be extremely large, meaning that it can be very close to singular.  So Roy decided to study this effect, to find out if it was a problem.

One of Roy's results shows that for a robot mechanism consisting of an unbranched chain of identical links connected by revolute joints, the JSIM for this mechanism can have a condition number as high as 4N⁴, where N is the number of bodies in the chain.  So, even a chain with only 10 bodies can have a JSIM with a condition number as high as 40,000; and the problem quickly gets worse as N increases.

This is bad news, both for simulation and control.  Simulators suffer a loss of efficiency, accuracy, or both, depending on integration step size, while control systems must cope with a highly sensitive plant in which tiny errors in applied forces can produce large errors in acceleration.

Fortunately, the picture is not this bad for every mechanism.  Unbranched chains appear to be the worst case.  Furthermore, the usual definition of matrix condition number (ratio of largest to smallest singular value) can overestimate the true size of the problem in some cases; and a more accurate measure is the condition number of a scaled version of the JSIM in which the diagonal elements have all been brought to the same value (e.g. 1).  The results of this study appear in this journal article.

This project followed on from the condition-number project above.  Having investigated the numerical properties of the joint-space inertia matrix (JSIM), Roy decided to take a look at the sparsity patterns (patterns of permanently zero-valued elements) in this matrix.

The term kinematic tree describes a rigid-body system in which the bodies are connected to form a topological tree.  (So there are no kinematic loops.)  Branches in the tree produce a pattern of zero-valued elements in the JSIM, so Roy decided to call it branch-induced sparsity.

It turns out that we can exploit this sparsity, using very simple algorithms, in order to reduce both the cost of factorizing the JSIM, and the cost of using the factors to solve dynamics equations.  In addition to cost reduction, these algorithms reduce the computational complexity of factorization from O(n³) to O(nd²), where n is the number of joint variables and d is the depth of the tree, which is the maximum number of joints between any one body and the root body of the tree.

The reduction in computational cost can be dramatic: roughly a factor of 4 for a 30-DoF quadruped, which is enough to bring JSIM-based algorithms back into contention with O(n) algorithms like the articulated-body algorithm.  This work was published in this journal article, and it appears also in Roy's book Rigid Body Dynamics Algorithms.  Implementations of the algorithms can be found in the software package spatial.

After a few years, Roy returned to the topic of branch-induced sparsity in order to investigate whether it could be used to reduce the cost of calculating the operational-space inertia matrix (OSIM).  The answer is 'yes'; and the algorithms he developed achieved even bigger cost reductions than those developed earlier for the joint-space inertia matrix.  For example, they achieved a factor of 6 reduction in the cost of calculating the OSIM for an Asimo next-generation robot (a typical high-end humanoid at the time).  Furthermore, they set a new record by beating the best previously-published algorithms for this computation.  This work was published in this journal article.

Having now investigated both joint-space and operational-space dynamics for the special case of a kinematic tree, the obvious next step is to consider kinematic loops.  Roy has a few ideas on how to do that, but it is a topic for future work.