Cyclic Coordinate Descent (CCD)

As I mentioned on previous post. This post will describe more about CCD in relation to Inverse Kinematics and Human Body Animation.

The basic idea of Cyclic Coordinate Descent (CCD) Method is performing iterative heuristic search for each joint angle, so at the end, the end-effector could reach a desired location in space. By doing iterative heuristic search, we try to find the best location of an articulated structure given its joint angles. This would result in the best (closest) distance of the end-effectors and the desired end points. The calculation is done one joint at a time, and in backward fashion, until we reached the parent joint. For calculating the joint angle, we also give certain limitation for the angle, just like the angle of a human. We implement this, so the animation wouldn’t do any strange movement. The first thing to do in CCD method is to determine the desired location of the end-effector (X). After that, we try to minimize the distance (ΔX) between end-effector position (X^) and the desired destination (X) as low as possible. We do this by increasing/decreasing the current joint angle of the end-effector. When the distance of the end-effector is as low as possible, it means that the current joint angle (Θ) has reached its maximum point, given the current position. Then we move backwards to the upper joint, where we then try again to minimize the distance between end-effector and destination point, but this time only altering the current upper joint. We do this until we reached the parent joint. An example can be seen in the following figure.

Cyclic Coordinate Descent Method for: a) Rotational Joint and b) Prismatic Joint

For example, we can imagine when we try to move the whole hand. The first thing that we do is to calculate the minimum distance that could be reached by our hand only using the wrist joint. After that, we then move backwards and try manipulate the elbow joint and again calculate the minimum distance that could be reached by our hand. We do this until the last joint is manipulated, for instance, the shoulder joint, or even our backbone joint. Each human body joint are capable to rotate in one to three different axis (3-Dimension). This ability to rotate is called Degree of Freedom of a joint. So each joint could have 1 to 3 Degree of Freedom (DOF). Using CCD method, we try to find the best joint angle for x-axis, y-axis and z-axis for a joint given the coordinate of the destination point (i.e. the best joint angle of each axis that could make the end-effector closer to the destination point). Suppose a joint cannot move in an axis, the best joint angle for that axis is zero. After calculating both three joint angles for each axis, we then calculate the rotation matrix for each axis, using the following rotation matrix:

Where RotX is the rotation matrix for x-axis, RotY is for y-axis and RotZ is for z-axis. We then combine these rotation matrixes into a single rotation matrix:

R = RotZ*RotY*RotX

Where R matrix is the rotation matrix of a joint. Applying rotation matrix of Joint(i) towards the end-effector will cause all the part from Joint(i) up to the end-effector to rotate. After that, the calculation will move backwards to Joint(i-1) and again we calculate the joint angle for Joint(i-1) and calculate the rotation matrix. In order to move end-effector given the rotation of Joint(i-1), besides rotation matrix of the current joint, we also need rotation matrix of the previous joint and the translation matrix of the previous link. The following is the translation matrix:

Where dX, dY, dZ is the length of the link (i.e. the distance between two joints). For transforming the end-effector given the rotation of Joint(i-1), we need the matrix of R(i-1)*T(i)*R(i), where T(i) is the translation matrix from the current joint to the previous joint (i.e. length of the link) and R(i) is the rotation matrix from the previous joint. Keep in mind that the calculation is done backwards starting from the end-effector towards the parent joint.This calculation will continue until we reached the parent joint where there will be no more joints that could rotate after this joint. After reaching the parent joint, the calculated distance between current end-effector location and the desired location should be as minimum as possible.

Related post

• Human Motion Animation with Inverse Kinematics
  

Read More

Human Motion Animation with Inverse Kinematics

Human body consists of at least a hundred joint that are connected in some way. When we try to move our hand, there are at least three joint that moves (i.e. shoulder, elbow and wrist joint). Some of human body joints are also capable in moving in 3 dimensions (e.g. shoulder, hip and neck joint). Off course, as a human, we do our movement intuitively, without trying to calculate how can we reach a position (e.g. walking, reaching, looking around, etc). But, in order to animate a human movement using a computer, we have to specify the angle of rotation for each joint in order to perform a movement. The basic procedure to animate a human body movement is to use kinematics. Kinematics is one of the fields of mechanics that evaluates the position changes of an object in a period of time without considering masses or forces of the object itself. The easiest way to apply kinematics in human animation is by using a so-called forward kinematics. Forward kinematics is a low level technique for animating an articulated structure. Using this method, the animator has a great degree of freedom to control the animation, because animator has to define the angle for each body joint. However, it might take a lot of effort to define all the components of the animation for only a single movement.

On the other hand, there is inverse kinematics which could be classified as a high level approach of animating an articulated structure. Instead of defining every transformation of joints, the animator can just define the destination point of end part of the articulated structure (i.e. hand or feet), and use that position to calculate the transformation for each joint, in backward fashion (i.e. calculate the wrist joint transformation first then elbow joint and shoulder joint as the last one).

Using inverse kinematics, it is possible to get several solutions or nothing at all. The drawback of this method is that the complexity of a structure might be very high that would lead to a condition where the calculation becomes too expensive or even impossible. The inverse kinematic could pose a non-linear problem where given a certain position x, there could be multiple solution in order to reach that position.

Inverse Kinematics

By knowing the starting and the ending position of the end-effectors (i.e. hand or feet), we then try to calculate the movement of the whole articulated structure (e.g. hand movement or walking movement). The basic idea of inverse kinematic is to find the appropriate angle of every joint in the articulated structure, given a desired position. Mathematically, inverse kinematics could be expressed as:

Θ = f-1 (x) (1)

Where Θ is the joint angle and x is the end-effector position. Since articulated structures consist of several joints, the equation above would result in a non-linear equation. So for a given end-effector location x, there might be more than one solution for Θ. For solving inverse kinematics, there are three main methods that could be used, which are:

a) Analytical method The most common way to do analytical method is by creating a closed-form equation that is obtained by trigonometric approach. The problem we faced with this method is the difficulty to obtain the trigonometric equation for every joint that are available.

b) Numerical Method We can solve non-linear equation (1) by transforming it into linear equation (linearization). After linearization, the connection between end-effector and joint angles is expressed with the following equation:

dX/dt = J(Θ) . dΘ/dt (2)

where dX/dt is the end-effector velocity, dΘ/dt is the joint velocity, and J relates the changes in the joint variables with the changes in the position of the end-effector in an M x N manner, where M is the joint variables count and N is the dimensions of the end-effector vector.

J = dF(Θ)/dΘ (3)

Where F is total function matrix for the movement of every joint angle.

Inverting equation (2) will result in:

d Θ /dt = J-1(Θ) . dx/dt (4)

And to solve it is by using iterative algorithm. When dealing with this method, we were faced with a very difficult equation in the Jacobian matrix that is hard to solve even using iterative algorithm because of the complexity of the equation.

c) Optimization Method For this method, what we do is try to solve each joint angle by trying to optimize the value of it. One of the examples of Optimization Method is the Cyclic Coordinate Descent Method (CCD) where we try to improve the angle of each joint, step by step, until the articulated structure could reach the desired end location for end-effector.

The next post will cover more about Cyclic Coordinate Descent Method.

Related post

• Cyclic Coordinate Descent
  

Read More

Minimax Pseudocode

Last year I wrote a post about AI in reversi using minimax algorithm with alpha beta pruning. However, it said nothing about the implementation. So, for you guys who already grabbed the idea of minimax but still having some troubles in implementing it, here's a pseudocode that might help you with. It's not something that I wrote by myself, but the idea is somewhat similar.

minimax(in game board, in best_opposing_score, out score chosen_score, out move chosen_move)
begin
best_score = -infinity;
Gt_generate_moves(current_mimx_data,moves_list);
for (i = 0 to moves_list.num_moves-1) do
new_board = board;
Gt_move(board, moves_list[i],the_unmove);
minimax(board, the_score,the_move);
Gt_unmove(board,the_unmove);
if (the_score > best_score) then
best_score = the_score;
best_move = moves_list[i];
if (best_score > best_opposing_score) then
cut;/* the opponent will not allow you to reach this node*/
endif
endif
enddo
chosen_move = best_move;
Gt_evaluate(current_mimx_data,chosen_score,best_score);
end.

Related post

• http://www.cs.caltech.edu/~petrovic/games/archex/othellodir/node2.html (external)

Read More

Modeling a Tree using L-System

An L-system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar (a set of rules and symbols), most famously used to model the growth processes of plant development, but also able to model the morphology of a variety of organisms. [wikipedia]

When using this model, we have to define a set of grammar rules that will be used to describe the growth of the branches of a tree. The rules that we define will later be implemented as the growth of the tree in an iterative fashion. In this system, we define these following alphabets that will be used in the production rules:

f : create branch
l : create leaf
[ and ] : define a set of local area/branch. The definitions of the area are put inside the [ and ]
+ and - : rotate the branch right/left in x-axis
^ and v : rotate the branch up/down in y-axis
<> : twist the branch left/right in z-axis

By using the symbols above, we can begin to create a tree with our system. But before that, we also have to define several properties that are also important in generating the tree, which are:

• The number of production rules iterations, for determining the level of the branches,
• The angle, for determining branch curves, and
• The radius of the branches and the decreasing value of it, in an iterative way The length of the branches

The following are several examples of the production rules that are used using the system:

Tree A

Angle : 25
# Iterations: 6
Branch radius: 0.02
Branch radius reduction: 0.0015
Branch length (height): 0.15
Initial value : fffffA
Production rules : A = f[++Al][--Al]>>>A



Tree B

Angle : 30
# Iterations: 10
Branch radius: 0.01
Branch radius reduction: 0.001
Branch length (height): 0.16
Initial value : fA
Production rules : A = f[^Bl]>>[^Bl]>>A, B = f[-Bl]B


Tree C

Angle : 15
# Iterations: 13
Branch radius: 0.02
Branch radius reduction: 0.0015
Branch length (height): 0.15
Initial value : fA
Production rules : A = ^fB>>>B>>>>>B, B = [^^f>>>>>>A]

Read More

Firefox Add-ons: Snaplinks and Linkification

Two reccommended add-ons for your Firefox!

Snap Links allows users to easily open multiple links in new tabs by drawing a box around them. Links can also be opened in new windows, new tabs on a new window, copied to clipboard, bookmarked or downloaded. I mostly use it to (lazily) open multiple links into new tabs or as a replacement for a standard procedure: right click - open link in New Tab.

snap links screen shot

Linkification on the other hand, is a very simple yet useful add-ons. It converts text links into a genuine, clickable links. No more copy and paste to the address bar! I found it works perfectly with snap links...

Open this (Snap Links) and this (Linkification) if you are interested.

Read More

A Negotiation Agent

Introduction

Sometimes there will be a problem between two parties where everyone has a different self-interest regarding the issues that they are arguing. In order to solve the problem, both parties (and maybe even more) have to sit and discuss about the issues that they are arguing and decide which issues that is best for them all. This is what negotiation is all about.

Each party will have its own utility value for every issue and every item in it. These values determine the importance of each issue for them. Off course, the best result is to get everything on our side and perhaps zero for the opponent. But in a negotiation, that is highly impossible because each party wants something for themselves. So the best thing to do is to reach an agreement for both parties of what issue that they will keep for themselves and will give to the other.

An Italian economist named Vilfredo Pareto (1848-1923) once introduced a concept called Pareto Efficiency. Pareto Efficiency is the outcome of a negotiation when there are no other outcomes where both parties will do better, but rather one party will do better, but the other will do worse. In a negotiation, there could be more than one outcome where the outcome is Pareto optimal. These outcomes are located in a Pareto frontier which is the boundaries between available and unavailable outcomes.

Designing a Negotiation Agent

We constructed an agent that is capable of negotiating problems with the other agent in order to achieve a result that is acceptable enough for both agents. The following diagram is the flowchart of our agent.

The basic procedure of how our agent works is that first, it always generates an offer that consists of the issues that is most important for the agent. It does this because it wants to tell to the opponent, at the first time, which issues are the most important for the agent. After sending the offer, the agent will later on receive a message from the opponent as a reaction. The opponent could accepts our offer, breaks the negotiations or proposes a counter offer. Both acceptance and breaking off from the opponent will result in ending the negotiations, but if the message is a counter offer, then our agent will try to calculate the next offer that it will give to the opponent

Since the agent doesn’t know any information regarding the opponent’s preferences, it has to try to create a model of opponent utility values in order to make an offer that is acceptable to the opponent, while still maintaining the agent acceptance value. An acceptance value is the value where the agent limits itself for which offer that it could accept. This value will decrease in time, since there is a limited time in negotiation. But the acceptance value will never be less than the agent’s reservation value.

The reservation value is the lowest utility value where the agent still possibly accept the offer from the opponent, but it will accept it only if both agent still haven’t decide anything while approaching the end of the negotiation time. Our reservation value is decided without any formalization. We just choose from the scale 0-100 and choose which one that seems reasonable. The following formula is the connection between acceptance value and reservation value.

The decision algorithm whether the agent will receive the offer from the opponent or not is quite simple:

As has been previously mentioned, the agent has to create a model of opponent utility values to calculate the offer that is acceptable for both parties. This model is evaluated every time the opponent gives an offer to our agent. In order to model the utility values of the opponent, our agent use a Bayesian learning method. First, our agent will form two matrices for every issue in the negotiation:

Where matrix A is the weight hypothesis and matrix B is the probability of the weight hypothesis. The values inside the matrix A are constant, where it ranges from 0-9 (in default, it could be easily change though) for each column and the values will be the same for each row.

The values inside the matrix B will be always in total of 1 for each column. At the initial condition, we will assume that the value for each column element is the same which is 1/n. The value m represent the number of choices in every issue and the value n represents the number of hypothesis that we use in this agent which is 10. Every time the opponent proposes an offer, the value of matrix B will also change. To calculate the values inside matrix B, we use the Bayesian learning equation:

From these two matrices, the agent will then try to model the opponent utility values for every issue by finding the product of matrix A and B. the result will be the model of opponent utility values for every choice in every issues. This production will always be calculated ever time the opponent gives an offer.

The matrix C will also changes every time the opponent gives an offer to the agent and each time our agent get an offer from the opponent, this model will update the values of matrix C in order to get a better representation of the opponent utility values.

After modeling the opponent’s utility values, our agent will try to calculate the best offer that it could give to the opponent. By using its utility values and the model of opponent’s utility values, the agent will try to come up with an offer which has a good utility value for the opponent while still trying to maintain the utility values for the agent itself which is greater than the acceptance value.

For calculating the offer will be given to the opponent, it is allowed to choose one of two methods available in the agent. The first method is a random method where the agent calculate every possible offer configurations that it could come up (for this assignment, we limit it for 500 configurations). The agent will compare the first offer that it come up with the next offer and keep the one that has highest utility value and it is not less than the acceptance value, and it will do this every time until the 500^th offer. For the second method, the agent will try to calculate the Pareto frontier outcomes based on both utility values (the agent’s and the opponent’s model) and later on, the agent will choose the outcome that has the highest utility for the opponent and later will propose that offer to the opponent.

The default setting for the agent is using the random method. There are several reasons why we choose the random method. It is not because the second method generate worse offer than the first but because the second method tends to give the same offer in several message exchanging. The consequence of this behavior is that the opponent has less opportunity to learn about our agent and therefore reduce the effectiveness of the negotiation.

Read More

Funny Computer Jokes

Tech support: What kind of computer do you have?
Female customer: A white one…

===============
Customer: Hi, this is Celine. I can’t get my diskette out.
Tech support: Have you tried pushing the Button?
Customer: Yes, sure, it’s really stuck.
Tech support: That doesn’t sound good; I’ll make a note.
Customer: No, wait a minute… I hadn’t inserted it yet… it’s still on my desk… sorry….

===============

Tech support: Click on the ‘my computer’ icon on to the left of the screen.
Customer: Your left or my left?

===============

Tech support: Good day. How may I help you?
Male customer: Hello… I can’t print.
Tech support: Would you click on “start” for me and…
Customer: Listen pal; don’t start getting technical on me! I’m not Bill Gates.

===============

Customer: Hi, good afternoon, this is Martha, I can’t print. Every time I try, it says ‘Can’t find printer’. I’ve even lifted the printer and placed it in front of the monitor, but the computer still says he can’t find it…

===============

Customer: I have problems printing in red…
Tech support: Do you have a color printer?
Customer: Aaaah………………..thank you.

===============

Tech support: What’s on your monitor now, ma’am?
Customer: A teddy bear my boyfriend bought for me at the 7-11.

===============

Customer: My keyboard is not working anymore.
Tech support: Are you sure it’s plugged into the computer?
Customer: No. I can’t get behind the computer.
Tech support: Pick up your keyboard and walk 10 paces back
Customer:! OK
Tech support: Did the keyboard come with you?
Customer: Yes
Tech support: That means the keyboard is not plugged in. Is there another keyboard?
Customer: Yes, there’s another one here. Ah…that one does work…

===============

Tech support: Your password is the small letter “a” as in apple, a capital letter V as in Victor, the number 7.
Customer: Is that 7 in capital letters?

===============

Customer: can’t get on the Internet.
Tech support: Are you sure you used the right password?
Customer: Yes, I’m sure. I saw my colleague do it.
Tech support: Can you tell me what the password was?
Customer: Five stars.

===============

Tech support: What anti-virus program do you use?
Customer: Netscape.
Tech support: That’s not an anti-virus program.
Customer: Oh, sorry…Internet Explorer.

===============

Customer: I have a huge problem. A friend has placed a screen saver on my computer, but every time I move the mouse, it disappears.

===============

Tech support: How may I help you?
Customer: I’m writing my first e-mail.
Tech support: OK, and what seems to be the problem?
Customer: Well, I have the letter ‘a’ in the address, but how do I get the circle around it?

===============

A woman customer called the Canon help desk with a problem with her printer.
Tech support: Are you running it under windows?
Customer: “No, my desk is next to the door, but that is a good point. The man sitting in the cubicle next to me is under a window, and his printer is working fine.”

===============

And last but not least…

Tech support: “Okay Bob, let’s press the control and escape keys at the same time. That brings up a task list in the middle of the screen. Now type the letter “P” to bring up the Program Manager”
Customer: I don’t have a P.
Tech support: On your keyboard, Bob.
Customer: What do you mean?
Tech support: “P”…..on your keyboard, Bob.
Customer: I’M NOT GOING TO DO THAT!

taken from http://funnylah.com/2006/10/31/funny-computer-jokes-tech-support/

Read More

OpenGL and Java

While some programmers might still don't like this idea, developing a OpenGL-based 3D application using Java is possible. One option is to use the OpenGL implementation of Java3D, and the other is using an external library. JOGL (Java Binding for OpenGL) belongs to the latter category.

So, if you are a programmer who like to make a 3D application using OpenGL and also still want to take the advantage of Java's windowing system (AWT and Swing), JOGL is a great solution. JOGL allows access to most features available to C programming language programmers, obviously excluding GLUT. A quick example about how to work with JOGL could be found on wiki. For more detailed tutorial (my favourite) you can always visit NeHe. Though the sources related to the tutorial originally written in C++ but the Java version is also provided by other users.

Happy coding!

Read More

Windows Vista - Source Code

source: http://privatebrian.wordpress.com/

Read More