# Decision trees for solving 2D inverse kinematics?

While experimenting with the OpenCV Machine Learning Library, I tried to make an example to learn the inverse kinematics of a 2D, 2 link arm using decision trees. The forward kinematics code looks like this:

const float Link1 = 1;

CvPoint2D32f forwardKinematics(float alpha, float beta)
{
CvPoint2D32f ret;

// Simple 2D, 2 link kinematic chain

return ret;
}


I generate a random set of 1000 (XY -> alpha) and (XY -> beta) pairs, and then use that data to train two decision tree models in OpenCV (one for alpha, one for beta). Then I use the models to predict joint angles for a given XY position.

It seems like it sometimes gets the right answer, but is wildly inconsistent. I understand that inverse kinematic problems like this have multiple solutions, but some of the answers I get back are just wrong.

Is this a reasonable thing to try to do, or will it never work? Are there other learning algorithms that would be better suited to this kind of problem than decision trees?

I changed the training set generation to uniformly sample the joint space instead of using random samples, and also restricted the range of the second joint to prevent multiple solutions and singularities.

Now the algorithm actually works pretty well, and gives me answers that are reasonably close to the desired position. I'm still not convinced that decision trees are the best algorithm for this problem though.

Thinking about it some more, I think all I've really done here is build a big lookup table in a fancy way (especially when using a uniform training set).

• I was just going to make the observation that DTs would likely work but are probably not the best learning algorithm for this task. I have had really good luck using bilinear interpolation for inverse kinematics. I image it would work well with this problem too. It also seems odd that you are training two trees with one feature each. Generally you would train one tree with multiple features. Finally you will probably see an improvement in performance if you increase the number of samples because you would be creating a better approximation to he real function. – DaemonMaker Nov 28 '12 at 20:10
• The number of samples question is an interesting one, in my current implementation it seems like I actually get more consistent answers with fewer samples. I don't completely understand how OpenCV is building the trees, but it seems like with fewer samples maybe it gets stuck on the wrong node less often? I used two trees because as far as I could tell, the CvDTree implementation uses a single double as the node value, so there isn't a way to store multiple result values. – WildCrustacean Nov 28 '12 at 20:21

The core problem here is that you are using two decision trees. As I understand it you are training two different decision trees on the same data. You then have one tree predict the required angle $\alpha$ and the other predict the required angle $\beta$. The problem is that $\beta$ is dependent on $\alpha$ but the $\beta$ tree has no concept of this fact. What you need to do is train one tree on both feaures (i.e. $\alpha$ and $\beta$).

In OpenCV each DT node uses a double called value to store the splitting value for that node and it uses an integer called class_idx to determine which feature to split on at any given level. When you train the DT you need to supply it with a matrix. Conventionally each row of the matrix is a feature vector and each column is an individual feature. However it appears that this is configurable in the OpenCV implementation by using the tflag (Cool!). Using the conventional method you would need to create an $m{\times}n$ matrix where $m = 1000$ is the number of training samples and $n = 2$.

• I'm still not sure how I would train a single tree to give me both alpha and beta, as far as I can tell the OpenCV DT implementation only supports 1D response vectors. – WildCrustacean Nov 29 '12 at 15:22