HEJP's Blog

Now on to the algorithm that requires a little mathematical understanding, the Jacobian matrix method. This method approximates the IK problem as a linear problem, which it almost is if you only change the angles of the joints by small amounts. Mathematics of the Method Starting with the vector of angles, We have the forward kinematic function f, i.e the function that return the position of the endpoint, x, given the angles of the joints. Our goal is to find  this can be done be firstly introducing the Jacobian matrix as well as differentiating w.r.t. time resulting in this, Since, Replacing the δ operators with Δ operators to approximate the differentiation, Sets us up for an iterative solution. Outline of the Algorithm

1. Calculate Δx = Goal – f(q) if the size to Δx is small enough exit loop
2. Compute J^-1. J may not be square in which case use the pseudo inverse (J^TJ)^-1J^T
3. Compute Δθ = J^-1Δx
4. θ = θ + Δθ
5. Repeat

Read more: Example, Source and Notes

Inverse Kinematics: Part 1 of 2 Inverse kinematics (IK) is the process of calculating the angles of joints required to reach from a start point to an end point. It has many uses, for example in robotics, 3D animation and computer games. There are a number of algorithms to solve the IK problem; the three that I will describe are an analytic solution, a Cyclic-Coordinate Descent (CCD) solution and a Jacobian matrix iterative solution. Analytic Solution This method uses trigonometry to compute an exact solution to the IK problem. Often there are several solutions but the analytic solution may only give one (depending on the implementation) which could require unnecessary movement compared to another possible solution. Also given more than two joints this method is likely to involve impractical maths, but is perfect if your problem consists of two joints in 2D or an additional swivel point in 3D. Given a situation like this: θ₁, θ₂ can be calculated thusly: Since acos(θ) is not real when θ is outside the range -1 to 1 which occurs when the goal (x,y) is out of reach of the arm you may want to make the arm form a straight line in the direction of (x,y). Read more: Analytic Example, CDD Solution and CCD Example

The method of characteristics is a technique for solving for ‘quasi-linear’ partial differential equations (PDEs), i.e. For example, The Theory The idea is to reduce a PDE to a series of ordinary differentiation equations (ODEs), This is achieved by forcing x, y to be linked by making them functions of one variable, t. Comparing the PDE, To the direction derivative We see that x(t) and y(t) are called the characteristic curves or simply the characteristics. Worked Examples Example 1: Here’s a quite easy example to get things started. Consider the problem described thus, given that Firstly indentify the characteristics, subject to subject to subject to Solve these ODEs to get (1) (2) (3) Substituting (1) into (2) (4) Then substituting (4) into (3) gives us the solution, Example 2: Here’s a little more tricky problem. Consider the problem described thus, given that Firstly indentify the characteristics, subject to subject to subject to Solve these ODEs to get (1) (2) Recall that , so, Which can be solved using the integrating factor technique, (3) Substituting (1) into (2) (4) Then substituting (1) and (4) into (3) gives us the solution, Example 3 Consider the problem described thus, given that Firstly indentify the characteristics, subject to subject to subject to Solve these ODEs to get (1) (2) (3) Substituting (1) into (3) (4) Then substituting (4) into (2) gives us the solution, I hope these examples have covered most of the types of problem you’ll likely be required to solve for an exam. As usual if you have any comments use the comment box below. Here is this post in pdf which is easier to scale.

Evaluating a infix expression (e.g. “3+6^9″) is both a complex and frequently occuring problem in programming projects. Here is a library to evaluate infix expression.

Usage

package test;

import hejp.RPN.*;

public class Test {
	static public void main(String[] args){
		String expression = "tanh(10)";

		try {
			System.out.print(RPN.process(expression).toString() + "\n"); //prints 0.9999999958776927
		} catch (Exception e) {
			if (e.getMessage().equalsIgnoreCase("Malformed Expression")) {
				System.out.print("Malformed Expression");
			}
		}
	}
}

The RPN class only has one method called process this takes an infix expression as a String and returns the result as a Double or throws an Exception whose message is equal to “Malformed Expression”. The method ‘process(String infix)’ is static therefore there is no need to make an instance of the class RPN. So process is called like so RPN.process(infix) rather than like RPN r = new RPN(); r.process(infix).

List of Functions

Read the rest of this entry »

Interpreting and evaluating an infix expression, for example ’3+9*14′, is a frequently occuring problem in computer science. A quick and relatively simple solution to this problem is to first convert the infix expression into a RPN expression. RPN is a notation in which the operands proceed the operators for example ’3 + 5′ = ’3 5 +’ and ’3 + 9 ^ 3 * 5′ = ’3 9 3 ^ 5 * +’. Conversion from infix notation to RPN can be achieved using a shunting yard algorithm although other methods exist, of course. Here is are example implementation of the shunting yard algorithm, in java:

String shunt(String[] _t){
  Stack stack = new Stack();
  Queue queue = new Queue();

  for(int i=0;i<_t.length;i++){

    /* if operand push onto queue */
    if(isDigit(_t[i].charAt(0))){
      queue.push(_t[i]);
    }
    else if(_t[i].length()>=2){/* handles negative numbers */
      if(isDigit(_t[i].charAt(1))){
        stack.push(_t[i]);
      }
    }
    else{
      switch(_t[i].charAt(0)){
      case '+': /* binary associative operations */
      case '*':
        while(!stack.isEmpty() && precidence(_t[i].charAt(0))<=precidence(stack.peek().toString().charAt(0))){
          queue.push(stack.pop());
        }
        stack.push(_t[i].charAt(0));
        break;
      case '-':/* left associative operations */
      case '/':
        while(!stack.isEmpty() && precidence(_t[i].charAt(0))<=precidence(stack.peek().toString().charAt(0))){
          queue.push(stack.pop());
        }
        stack.push(_t[i].charAt(0));
        break;
      case '^':/* right associative operations */
        while(!stack.isEmpty() && precidence(_t[i].charAt(0))<precidence(stack.peek().toString().charAt(0))){
          queue.push(stack.pop());
        }
        stack.push(_t[i].charAt(0));
        break;
      case '(':
        stack.push(_t[i].charAt(0));
        break;
      case ')':
        /* until you find ( pop off stack onto queue */
        while(!stack.isEmpty() && stack.peek().toString().charAt(0)!='('){
          println("Stack: "+stack.toString());
          queue.push(stack.pop());
        }
        if(!stack.isEmpty()){
          stack.pop();
        }
        break;
      default:
        break;
      }
    }
  }
  while(!stack.isEmpty()){
    queue.push(stack.pop());
  }
  String temp = queue.toString();
  temp = temp.substring(1,temp.length()-1);
  temp = temp.replaceAll(",", "");
  return temp;
}

More

RPN Shunting algorithm in detail