Decision trees for solving 2D inverse kinematics?

Question

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;
const float Link2 = 2;

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

    // Simple 2D, 2 link kinematic chain
    ret.x = Link1 * std::cos(alpha) + Link2 * std::cos(alpha - beta);
    ret.y = Link1 * std::sin(alpha) + Link2 * std::sin(alpha - beta);

    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?

Answer 1

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).

Answer 2

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$.