Revision as of 07:30, 3 August 2010

Project

This page is under construction ...

Introduction

What is my project all about? Well for my honours project I am looking at the performance of iterative inverse kinematic algorithms. Yes there are a few big words in that title so I will break it down and you will see that its not so bad.

My project focuses on the inverse kinematics of simple joint chains such as a robotic arm or the leg of an computer animated character. If we want to position the end of the robotic arm (end-effector) then we need to tell each joint in the arm to move to a particular angle. Once the robot arm has moved each of its joints to the required position the end-effector will (hopefully) be in the desired position. The hard part of this and coincidently that 'inverse' part of the title is finding out what angles you need at each joint so that the end-effector ends up at the correct location. Enter the CCD algorithm ...

The Cyclic Coordinate Descent (CCD) algorithm is an iterative algorithm that operates on a joint chain and works by converging the end-effector to the desired target location. The CCD algorithm is relativity simple to implement and this makes it very popular for use in the fields of robotics and computer animation and computer games.

Below are to images that will help clarify what the CCD algorithm achieves. The first image is the 'before' shot. The joint chain is stretched out straight with the base of the joint chain at the origin. The green circle is the target location and the red circle is the end-effector of the joint chain. The second image is the 'after' shot. In this second image we can see the result of running the CCD algorithm on the joint chain. You will note that the end-effector has moved to the target location. This is a pretty good indication that everything has gone smoothly in the algorithm, it has been able to find the rotation required for each joint in order hit the target.

The joint chain before is has moved to the target.

The joint chain after is has reached its target.

Ok so for each target we have a bunch of information regarding the behaviour of the CCD algorithm, these include the number of iterations done to get the end-effector to the target and others such as the total amount of rotation taken by all the joints. If we now use this information to colour the target and we make as many targets as there are pixels then we get a colourised map of performance of the algorithm with the joint chain. The result can be seen below.

The resulting metric map measuring the number of iterations of the CCD algorithm on a joint chain with 5 links.

Cool eh. Now we can easily see how the CCD algorithm performs using a given set of parameters. We can see that it has trouble reaching around behind itself and we can clearly see the regions of the joint chains workspace that it can reach easily due the simple colouring. Ok now to get onto designing a nice simple object-oriented solution that will make generating various metric maps a snap. But first we need to look at some basic requirements.

Requirements

The program needs to able to render a metric map for a given size joint chain and a given iterative IK algorithm.

Input

• Number of joints in the chain.
• Type of iterative IK algorithm (will be using at least two initially)
• Behaviour parameters for the algorithm, including:
  • Maximum number of iterations to attempt
  • Tolerance distance required for the end-effector to be considered at the target
• Size of the metric map (image dimensions size x size)
• Metric to display on the metric map

Output

• Metric map (size x size) image
• Range of results for the rendered metric map

Internally it does not really matter the structure or the representations as long as the CCD (or any alternative) algorithm works correctly and has access to the joint angles. In saying that lets check out the initial design.

Initial Design

The initial design follows closely to this simple step by step approach to the problem of rendering a metric map. The steps are outlined as follows:

1. Create the required number of joints
2. Create a 2D buffer to hold the results, one element for each pixel/target
3. For each target in the buffer: (see note *)
   1. Reset the joint chain to its default position
   2. Run the algorithm over the joint chain for this target
   3. Save the result to the buffer
4. Loop over the buffer and find the min and max (range) for the required metric
5. Create an image the same size as the buffer
6. For each element in the buffer:
   1. Use the resulting metric range to colourise the result
   2. Store the colour in the corresponding image pixel

* note: This loop can be very computationally expensive, especially with large images and high thresholds. So this loop is targeted for sub division to allow parallel execution.

Description

Structure

First I identified what was going to be changing and the obvious answer is the joint chain. So I designed a Link (joint) class. This class would represent a single link with a static length and dynamic angle. Also included was a origin field that would be the 2D location of the base or origin of the joint.

In order to represent a joint chain I would simply use an array of links. This way it naturally enforced an order and length, so therefore would work perfectly as a joint chain.

Algorithm

Next I needed a Solver that would take a joint chain and modify the angles of the joints until the end-effector was at a given target location. Knowing that I wanted to be able to test different algorithms, I made this class abstract and then implemented a concrete CCD class from it.

Now that I had the ability to represent and solve a IK problem on a simple joint chain I needed a way to record what happened to the joint chain during the solve routine. So I created a Result class that kept the results of various metrics and made is the return value for the Solver.Solve() method. By doing this I let the implementation of the Solver take care about filling in the various metric values.

Plot

So far I think that I was off to a good start. I had simple classes to represent joint, solver and result. Now I need to take these and apply them to each pixel in an image and render the result using colours. Firstly I decided that I need to collect all the data. So next up I designed a Plotter class. This class would have the responsibility of creating a 2D array of results, each result representing a point in a square grid that would then be mapped onto a pixel in a square image (metric map). The plotter class turned out to only have a single method and did not need to contain any state between calls so this class was defined as a static class with a single static method. Through this method you could pass all the required information the plotter needed to produce a 2D array of results. I thought this was a nice solution as it kept all the behaviour of the solver in a single call and would allow me to break the problem up further into chunks that I could process simultaneously over multiple threads. So that's exactly what I did. (Note: PlotThreaded() and the internal Job class).

Summarise

Great now we only need to loop over all the results in the results buffer (2D array) and compute a colour value for each result, saving the computed colour to a cosponsoring image pixel. But how do I know what metric we want to show and what is the range of that metric in our result buffer? An into the fray I designed the Statistics class. This class would simply loop through the results buffer and compile a series of ranges for each metric in the result class. In this case I decided that I did not want it doing all that work in the constructor so I made the default constructor private and instead created a static method that when called would create and return the class with all the field filled in. In this way only the static method creates the and has write access to the classes field. What's returned is effectively a 'read-only' class.

Render

For the final step I needed a way to colourise each result. Because the bulk of this operation would be the same no matter what metric we wanted to measure I decided to design a Renderer class. This would do all the grunt work of looping over results and then I would use a simple delegate method Colourise, passed to the renderer, do the simple job of selecting the appropriate metric and using the metrics range define a colour value.

UML Diagram

Discussion

Ok now we have finished the initial design we can put on our OO hat and take a closer look.

The first thing we may notice is that there is not a lot of OO going on here. Sure we have used classes to implement a "separation of concerns" but a lot of those classes appear to have no state. Should this be a concern? What about the use of an abstract Solver class that does not have any implemented methods? What's with all the static methods in Link? And what's with the private constructor in the Statistics class? Well it seems that we have a few good questions to start with so we will now attempt to address them one at a time.

Properties, getters and setters

Starting with the humble Link class we can examine the use of getters and setters (properties in C#). Logically, for this project, we only want the angle of the joint to change not the length. And in saying this we may not want the link to just blindly rotate to a given angle as there may be constraints to the amount of rotation required. An attempt to fix this in the initial design looks to have been attempted with the inclusion of the Rotate() method that takes a requested change in angle and returns the actual change made. This is a good attempt as it hides the details of the link but by leaving all those public setters it does not go all the way. The Length, Angle and Origin are needed in processing a link but altering the state of the Link class should be limited to the Rotate() method only.

Abstract class vs Interface

The abstract Solver class defines only a single method and no state. This looks like it would be the perfect candidate to be an interface instead of an abstract class. In this situation (only abstract methods and no state) the only reason that we may want to keep this as an abstract class is if we only want our subclasses to inherit from a single class (itself).

Comments

Please leave any comments that you have regarding this project or even the writing of this wiki page in this comments section.

- Thanks Mr Robinson, I see now that my UML diagram is missing almost all of its associations. Fixed now.