Wednesday, 6 May 2015

From Deep Blue to Deep Trouble?

On 11th May 1997, Deep Blue, a chess-playing computer developed by IBM, beat the then world champion Gary Kasparov at chess.  It won the six game match with two wins and three draws. Kasparov accused IBM of cheating and demanded a rematch, but IBM refused and dismantled Deep Blue. Kasparov had beaten a previous version of Deep Blue in 1996.

By 2011, IBM had built an even more intelligent computer called Watson – named after IBM founder Thomas Watson. Watson is an artificial intelligence computer system capable of answering questions posed in natural language. As a test of its abilities, Watson competed on the TV quiz show Jeopardy, in the shows only human-versus-machine match to date. Watson managed to beat Brad Rutter and Ken Jennings, the biggest all-time money winner and longest championship streak record holder respectively. Behind the scenes, Watson had access to 200 million pages of structured and unstructured data, consuming four terabytes of disk storage, including the full text of Wikipedia. However, it was not connected to the Internet during the game.

Today, Watson is marketed as a tool for people to explore and use. Watson is not alone, Microsoft have launched Azure ML, their machine learning platform, and everyday new companies are opening for business, promising to provide the answers to humanities toughest problems.

Computer scientists like Geoffrey Hinton, Yann Lecun and Andrew Ng are leading the way with improved machine learning techniques that have recently led to great advances in deep learning systems.

Software advances are being matched in hardware by the unstoppable Moore's law, which is the observation that over the history of computing hardware, the number of transistors on integrated circuits doubles approximately every two years. The law is named after Intel co-founder Gordon Moore, who described the trend in his 1965 paper. His prediction has proven to be most accurate - in part because the law is now used in the semiconductor industry to guide long-term planning and to set targets for research and development. The capabilities of many digital electronic devices are strongly linked to Moore's law: processing speed, memory capacity, sensors and even the number and size of pixels in digital cameras. All of these are improving at exponential rates as well.

Where will it all end? Each stage of technical development and each computerised victory brings us inevitability closer to the day that machines will outsmart humans…

There are those who call themselves Singularitarians who believe that the creation of a super intelligence, the Singularity, will happen in the near future and that deliberate action ought to be taken to ensure that this intelligence benefits humans. Singularitarians are distinguished from other futurists who speculate on a technological singularity by their belief that the Singularity is not only possible, but desirable if guided prudently.

On the flip side, there are some prominent figures, including Elon Musk and Stephen Hawking, who warn against major advances in artificial intelligence. In a recent interview with the BBC Hawking stated:

“The primitive forms of artificial intelligence we already have, have proved very useful. But I think the development of full artificial intelligence could spell the end of the human race. Once humans develop artificial intelligence it would take off on its own and redesign itself at an ever-increasing rate. Humans, who are limited by slow biological evolution, couldn’t compete and would be superseded.”

I’m certainly not up there on the intelligence scales with Stephen Hawking, but I do have a view. We are undoubtedly developing computers that are becoming more intelligent. The problems these computers solve are very useful: self-driving cars and speech recognition – where would I be without Siri?!

However, these computers are in no way sentient – they are merely very good at recognising patterns - they have no personal goals or desires. Animals made this jump with the evolution of the neocortex. In many ways this is what allows mammals to learn new behaviours and for humans to develop conscious thought and language.

To match a human level intelligence, with goals and desires, we must make monumentous advances in learning algorithms and develop fundamentally new approaches. We must learn to create the equivalent of a neocortex that sits over lower level learning algorithms.

That’s not to say we won’t get there one day – I’m certain we will - but we’re a long way from that just yet and have plenty of time to think about necessary safety concerns.

I, for one, welcome our new machine overlords..!

Friday, 27 February 2015

From Neural Networks to Deep Learning

A few years ago, I began blogging about Neural Networks. I have had an interest in this side of machine learning for more time than I can remember. However, even though these amazingly useful constructs have been used to solve many real world problems; they have never really delivered on the dream of a true artificial intelligence – until now. With the advent of Deep Learning algorithms this is all about to change…

Neural Networks began as single layer networks that could be used to solve “linearly separable” classification problems. This type of network was known as the perceptron.

Some very bright people then discovered how to do “back propagation”, which allowed (in theory) multi-layer networks to solve any type of classification problem. The back propagation algorithm is so called, because of the way it works - it compares the output of a network with the desired value and feeds back tiny amounts of the error through the network to modify the weights.

If you wanted to do something useful with a Neural Network, such as perform pattern recognition – identifying images that contain a car - you start by converting raw pixel inputs into feature activations. These feature activations are often hand crafted and are designed to pick out something like an individual wheel or grill. The network would then learn how to weight the feature activations and decide what it’s seeing in the image.

However, using back propagation to solve these problems really did not work for a number of reasons:
  • It’s really hard to hand craft feature detectors
  • It requires pre-classified (labelled) training data - almost all real world data is unlabelled
  • The learning time does not scale well - especially with really large networks
  • The network can often get stuck in “local optima” – it will stop learning before arriving at the correct solution
These serious limitations rendered neural networks as nothing more than a computer scientists plaything for several decades.

But then, with the passage of time, the story slowly changed. The rise of the Internet and Big Data brought with it huge amounts of labelled data. Computers also got a lot faster, especially with the creation of Graphics Processing Units (GPU) - by orders of magnitude. And, most importantly, we learnt new and better techniques to initialise the networks.

The key difference between techniques used in modern deep learning algorithms and the neural networks of old, is that the network creates its own feature detectors – they are not hand crafted. Therefore, the only limitation is computing power – and we have plenty of that!

Deep networks learn one layer at a time, using a generative model of the input (visible) data that connects to a layer of latent (hidden) nodes. The hidden layer is then used to train a second generative model against the next hidden layer, and so on. One technique used to achieve this is a restricted Boltzmann Machine (I’ll post some code next time).

Just like human vision systems, deep learning systems for image recognition process stuff in layers. For example, the first layer may learn correlations between pixels to begin to form tiny edge detectors. By the time you reach the third or forth layer the activations could represent complete wheels, hands, faces, etc.

Fast forward today - Google scientists have developed a computer program capable of learning a wide variety of tasks independently, in what has been hailed as “a significant step towards true artificial intelligence”.

The program learnt to play 49 different retro computer games, and came up with its own strategies for winning. The research was carried out by DeepMind, the British company bought by Google last year for £400m, whose stated aim is to build “smart machines”.

Likewise, Microsoft believes that too much of the world’s Big Data is going to waste and has just launched a new initiative to help organisations process it all, build APIs and finally make some sense out of it. The technology, called Azure Machine Learning (ML), is a new cloud based service that can be accessed via any web browser. It’s simple to use, featuring a simple drag and drop interface that data scientists and developers use. The main aim of ML is to reduce the amount of work that’s needed for organisations to deploy machine learning.

Not to be left behind, a Facebook project known as Deep Face can discern the accuracy of the true identity of any picture of you. The Deep Face AI system is now powerful enough to spot individual users from the 400 million photos uploaded to the social network every single day.

In the future, deep learning systems could be used to power self-driving cars, personal assistants in smartphones or conduct scientific research in fields from climate change to cosmology.

Exciting times..!

Tuesday, 3 February 2015

Biped Hip Replacement


This is a quick post to show the latest updates to my biped development robot.

Since last time I’ve added another degree of freedom to each hip by adding two further Robotis servos. This has had a dramatic effect, allowing me to transition the centre of gravity easily over the desired foot before attempting to stride.

I’ve also moved the battery and main processor off board to reduce weight and allow me to use the full power of my PC. By driving the robot directly from my PC, rather than an Arduino, I’m able to perform real-time diagnostics. This in turn has allowed me to greatly refine the walking gait.

To communicate with my PC I’m using the Robotis USB2Dynamixel adapter. This is a great gadget that has a few of modes of operation – one of which allows me to convert USB signals to TTL used by the Dynamixel AX series and hook in external power for the servos.


In total, this biped now has 10 degrees of freedom: two in each hip; one in each knee; two in each ankle. To make turning easier, I could add another degree of freedom to each hip or ankle, which would enable rotation on the transverse plane. But for now, I’m happy the way it is.

It’s a pretty agile little beast now – check out the video below…

video

Tuesday, 2 December 2014

Using Inverse Kinematics to Develop a Biped Robot Walking Gait (C#)

When I created the eight degree of freedom (8 DOF) biped robot in my last blog post, I wrote a C# application to calculate servo positions, which in turn generated a smooth, life-like, walking gait. In this post I will walk through the application logic in more detail. The application generates a motion plan, runs the inverse kinematics calculations and allows me to visualise the results as rendered a stick man. The complete source code is below.

According to Wikipedia, “Inverse kinematics refers to the use of the kinematics equations of a robot to determine the joint parameters that provide a desired position of the end-effector. Specification of the movement of a robot so that its end-effector achieves a desired task is known as motion planning. Inverse kinematics transforms the motion plan into joint actuator trajectories for the robot.”

Starting with the motion plan and using the two rules established in my previous post (#1 static hip height and #2 clipped sinusoidal foot motion), I knew roughly what I wanted each joint to do. Next I had to model that mathematically. Hip height was easy, as it’s constant. Left and right feet follow the pattern illustrated below.

Biped Robot Hip & Foot Height Against Time

I created a system of triangles to represent each of the robot joints and could now begin to calculate the relative angles between them for each time interval. To preserve symmetry, I decided that the feet would always remain parallel with the body (and floor) and that the horizontal plane would always bisect the knee angle. These principles helped determine many of the joint angles using some simple trigonometry.



Biped Robot Limb Angles
All that remained was to solve any outstanding angles using the law of cosines. The law of cosines can be used in a number of ways - such as calculating the third side of a triangle when two sides and their enclosed angle are known, or to determine the angles of a triangle if all three sides are known. Once the angles are known, these can be translated into servo positions, with the appropriate amount of offset and direction applied.

This could now be implemented in code – the motion plan (determining foot geometry), the inverse kinematics (determining servo angle) calculation and the joint visualisation. I won’t walk through every step as the source code is pretty easy to decipher.

Note about the code: I separate the code into a few classes to keep key objects and values partitioned (legs, hip, etc). In this post I’ve compressed everything into a single file, which will execute - just paste the entire block into a new Windows Form project. However, if you want to modify the code, for maintainability, it would be best to break out again into discrete class files.

I hope you find this useful.

Code Snippet
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Drawing;
  4. using System.IO;
  5. using System.Threading;
  6. using System.Windows.Forms;
  7.  
  8. namespace Biped
  9. {
  10.     public class Canvass : Form
  11.     {
  12.         private List<int[]> _patterns = new List<int[]>();
  13.         private Hip _hip = new Hip();
  14.         private int _p = 0;
  15.  
  16.         [STAThread]
  17.         static void Main()
  18.         {
  19.             Application.Run(new Canvass());
  20.         }
  21.  
  22.         public Canvass()
  23.         {
  24.             this.Paint += Render;
  25.             this.Height = 300;
  26.             this.Width = 250;
  27.             CalcFeetCoordinates();
  28.         }
  29.  
  30.         private void CalcFeetCoordinates()
  31.         {
  32.             // Move left leg forward.
  33.             for (int i = 0; i < 20; i++)
  34.             {
  35.                 double x = (i - 10) * (Leg.StrideLength / 20.0);
  36.                 double y = Leg.HipHeight;
  37.                 AddStridePosition(x, y, -45);
  38.             }
  39.  
  40.             // Move left leg backward.
  41.             for (int i = 0; i < 20; i++)
  42.             {
  43.                 double x = (10 - i) * (Leg.StrideLength / 20.0);
  44.                 double y = FootHeight(x);
  45.                 AddStridePosition(x, y, 45);
  46.             }
  47.  
  48.             // Build right leg from phase shift clone of left.
  49.             for (int i = 0; i < 40; i++)
  50.                 for (int j = 0; j < 4; j++)
  51.                     _patterns[i][j + 4] = -_patterns[(i + 20) % 40][j];
  52.  
  53.             // Roll ankles on transition.
  54.             RollAnkle(19, 20, 6);
  55.             RollAnkle(45, 0, 6);
  56.  
  57.             // Write servo positions to file.
  58.             DumpToFile();
  59.         }
  60.  
  61.         private double FootHeight(double x)
  62.         {
  63.             return Leg.HipHeight - Leg.FootLift * Math.Cos(Math.Abs(x * Math.PI / Leg.StrideLength));
  64.         }
  65.  
  66.         private void AddStridePosition(double x, double y, int tilt)
  67.         {
  68.             // Cosine rule: cos A = (b^2 + c^2 - a^2) / 2bc
  69.             int[] pos = new int[8];
  70.             double hypSqrd = Math.Pow(x, 2) + Math.Pow(y, 2);
  71.             double hyp = Math.Sqrt(hypSqrd);
  72.             pos[0] = 0 - RadToStep(Math.Acos(hyp / (2 * Leg.Bone)) - Math.Atan2(x, y));
  73.             pos[1] = RadToStep(Math.Acos((2 * Leg.BoneSqrd - hypSqrd) / (2 * Leg.BoneSqrd))) - 512;
  74.             pos[2] = pos[0] - pos[1];
  75.             pos[3] = tilt;
  76.             _patterns.Add(pos);
  77.         }
  78.  
  79.         private void RollAnkle(int r1, int r2, int steps)
  80.         {
  81.             int[] row1 = _patterns[r1];
  82.             int[] row2 = _patterns[r2];
  83.             for (int i = 0; i < steps; i++)
  84.             {
  85.                 int[] pos = new int[8];
  86.                 for (int j = 0; j < 8; j++)
  87.                     pos[j] = row1[j] - ((row1[j] - row2[j]) * (i + 1)) / (steps + 1);
  88.                 _patterns.Insert(r1 + 1 + i, pos);
  89.             }
  90.         }
  91.  
  92.         private void Render(object sender, PaintEventArgs e)
  93.         {
  94.             _hip.Render(_patterns[_p++], e.Graphics);
  95.             if (_p == _patterns.Count) _p = 0;
  96.             this.Invalidate();
  97.             Thread.Sleep(100);
  98.         }
  99.  
  100.         private int RadToStep(double rads)
  101.         {
  102.             return (int)(rads * 512 / Math.PI);
  103.         }
  104.  
  105.         private void DumpToFile()
  106.         {
  107.             using (TextWriter tw = new StreamWriter("biped.csv", false))
  108.             {
  109.                 foreach (int[] pos in _patterns)
  110.                     tw.WriteLine("{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}",
  111.                         pos[0], pos[1], pos[2], pos[3], pos[4], pos[5], pos[6], pos[7]);
  112.                 tw.Close();
  113.             }
  114.         }
  115.     }
  116.  
  117.     public class Hip
  118.     {
  119.         private Leg _leftLeg = new Leg();
  120.         private Leg _rightLeg = new Leg();
  121.  
  122.         public void Render(int[] steps, Graphics graph)
  123.         {
  124.             _leftLeg.SetServos(steps[0], steps[1], steps[2], -1);
  125.             _leftLeg.Render(graph, Pens.Black);
  126.  
  127.             _rightLeg.SetServos(steps[4], steps[5], steps[6], 1);
  128.             _rightLeg.Render(graph, Pens.Blue);
  129.         }
  130.     }
  131.  
  132.     public class Leg
  133.     {
  134.         public static int Bone = 100;
  135.         public static int BoneSqrd = Bone * Bone;
  136.         public static int HipHeight = 180;
  137.         public static int StrideLength = 60;
  138.         public static int FootLift = 20;
  139.  
  140.         private static int _foot = Bone / 5;
  141.         private double[] _joints = new double[3];
  142.  
  143.         public void SetServos(int hip, int knee, int ankle, int direction)
  144.         {
  145.             _joints[0] = StepToRad(hip * direction);
  146.             _joints[1] = StepToRad(-knee * direction);
  147.             _joints[2] = StepToRad(-ankle * direction + 256);
  148.         }
  149.  
  150.         public void Render(Graphics g, Pen pen)
  151.         {
  152.             Point[] points = new Point[4];
  153.             points[0] = new Point(100, 40);
  154.  
  155.             points[1] = new Point();
  156.             points[1].X = points[0].X + (int)(Math.Sin(_joints[0]) * Bone);
  157.             points[1].Y = points[0].Y + (int)(Math.Cos(_joints[0]) * Bone);
  158.  
  159.             points[2] = new Point();
  160.             points[2].X = points[1].X + (int)(Math.Sin(_joints[0] + _joints[1]) * Bone);
  161.             points[2].Y = points[1].Y + (int)(Math.Cos(_joints[0] + _joints[1]) * Bone);
  162.  
  163.             points[3] = new Point();
  164.             points[3].X = points[2].X + (int)(Math.Sin(_joints[0] + _joints[1] + _joints[2]) * _foot);
  165.             points[3].Y = points[2].Y + (int)(Math.Cos(_joints[0] + _joints[1] + _joints[2]) * _foot);
  166.  
  167.             for (int i = 0; i < 3; i++)
  168.                 g.DrawLine(pen, points[i], points[i + 1]);
  169.         }
  170.  
  171.         private double StepToRad(int steps)
  172.         {
  173.             return Math.PI * steps / 512.0;
  174.         }
  175.     }
  176. }

Sunday, 30 November 2014

8 DOF Biped Robot using Dynamixel AX-12A Servos and Arduino

Buoyed by the success of my 6 DOF biped I decide to take the next step (no pun intended).

I purchased another Dynamixel AX-12A servo for each leg to give me eight degrees of freedom (DOF) in total. The hope was that this would result in a much more life like walking gait. Whilst ordering the servos, I also bought some more Robotis plastic frames to ease bolting this lot together.

The new servos and frames were fixed together similar to the previous design, but now with an enhanced ankle joint. With 8 DOF, I could no longer work out joint ankles in my head. It was time to break out some inverse kinematics!

Designing a walking gait from scratch is not that simple. I started by watching how people walk and tried to establish some simple rules I could emulate in code. My first observation was that humans have a really efficient walking gait. Our bodies carry a large mass above the waistline and we tend to keep that fairly stable whilst walking.

Rule #1: The robot’s hip height should remain constant.

Secondly, we raise and lower our feet very smoothly, just enough to achieve forward movement, which peaks in the middle of our stride.

Rule #2: The robot’s feet should follow clipped sine wave.

With these two rules established I could now generate a system of triangles to calculate all servo positions at each point of the stride. I could solve any missing angles using the law of cosines. To help me with this job I wrote a C# application to crunch the numbers and visualise the task. The result was a [52, 8] matrix of servo positions that I could paste into a very small Arduino program.

I will walk through the C# application in detail in my next post.

The resulting Arduino code is posted below. Like before, the program refers to my Dynamixel class created in a previous post.

I’m really pleased with the results. Here is a video of my new 8 DOF biped walking across a glass table - it looks and sounds pretty sinister…

video


Code Snippet
  1. #include "Dynamixel.h"
  2. #include "Wire.h"
  3.  
  4. #define WALK_SWITCH  8
  5.  
  6. Dynamixel servo;
  7.  
  8. int pos[52][8] = {
  9. {-95, -138, 43, -45, 41, 138, -97, -45},
  10. {-93, -140, 47, -45, 50, 151, -101, -45},
  11. {-92, -141, 49, -45, 59, 164, -105, -45},
  12. {-90, -143, 53, -45, 67, 174, -107, -45},
  13. {-88, -144, 56, -45, 74, 184, -110, -45},
  14. {-85, -145, 60, -45, 80, 192, -112, -45},
  15. {-83, -146, 63, -45, 87, 198, -111, -45},
  16. {-81, -147, 66, -45, 92, 204, -112, -45},
  17. {-78, -147, 69, -45, 97, 207, -110, -45},
  18. {-76, -147, 71, -45, 101, 210, -109, -45},
  19. {-73, -148, 75, -45, 104, 210, -106, -45},
  20. {-70, -147, 77, -45, 107, 210, -103, -45},
  21. {-67, -147, 80, -45, 109, 207, -98, -45},
  22. {-64, -147, 83, -45, 110, 204, -94, -45},
  23. {-61, -146, 85, -45, 110, 198, -88, -45},
  24. {-58, -145, 87, -45, 110, 192, -82, -45},
  25. {-55, -144, 89, -45, 109, 184, -75, -45},
  26. {-52, -143, 91, -45, 106, 174, -68, -45},
  27. {-48, -141, 93, -45, 103, 164, -61, -45},
  28. {-45, -140, 95, -45, 100, 151, -51, -45},
  29. {-45, -140, 95, -33, 100, 150, -50, -33},
  30. {-44, -140, 95, -20, 99, 148, -49, -20},
  31. {-44, -140, 95, -7, 98, 146, -48, -7},
  32. {-43, -139, 96, 6, 98, 144, -47, 6},
  33. {-43, -139, 96, 19, 97, 142, -46, 19},
  34. {-42, -139, 96, 32, 96, 140, -45, 32},
  35. {-41, -138, 97, 45, 95, 138, -43, 45},
  36. {-50, -151, 101, 45, 93, 140, -47, 45},
  37. {-59, -164, 105, 45, 92, 141, -49, 45},
  38. {-67, -174, 107, 45, 90, 143, -53, 45},
  39. {-74, -184, 110, 45, 88, 144, -56, 45},
  40. {-80, -192, 112, 45, 85, 145, -60, 45},
  41. {-87, -198, 111, 45, 83, 146, -63, 45},
  42. {-92, -204, 112, 45, 81, 147, -66, 45},
  43. {-97, -207, 110, 45, 78, 147, -69, 45},
  44. {-101, -210, 109, 45, 76, 147, -71, 45},
  45. {-104, -210, 106, 45, 73, 148, -75, 45},
  46. {-107, -210, 103, 45, 70, 147, -77, 45},
  47. {-109, -207, 98, 45, 67, 147, -80, 45},
  48. {-110, -204, 94, 45, 64, 147, -83, 45},
  49. {-110, -198, 88, 45, 61, 146, -85, 45},
  50. {-110, -192, 82, 45, 58, 145, -87, 45},
  51. {-109, -184, 75, 45, 55, 144, -89, 45},
  52. {-106, -174, 68, 45, 52, 143, -91, 45},
  53. {-103, -164, 61, 45, 48, 141, -93, 45},
  54. {-100, -151, 51, 45, 45, 140, -95, 45},
  55. {-100, -150, 50, 33, 45, 140, -95, 33},
  56. {-99, -148, 49, 20, 44, 140, -95, 20},
  57. {-98, -146, 48, 7, 44, 140, -95, 7},
  58. {-98, -144, 47, -6, 43, 139, -96, -6},
  59. {-97, -142, 46, -19, 43, 139, -96, -19},
  60. {-96, -140, 45, -32, 42, 139, -96, -32}
  61. };
  62.  
  63. int centre = 512;
  64. byte p = 0;
  65.  
  66. void setup() {
  67.   pinMode(WALK_SWITCH, INPUT);
  68.   Serial.begin(1000000);
  69. }
  70.  
  71. void loop() {
  72.   if (digitalRead(WALK_SWITCH)) {
  73.     update(p++);
  74.     delay(38);
  75.     if (p > 51) p = 0;
  76.   }
  77. }
  78.  
  79. void update(byte p) {
  80.   int fix = 0;
  81.   for (byte i = 0; i < 8; i++)
  82.   {
  83.     if (i==0) fix = -120;
  84.     else if (i==4) fix = 120;
  85.     else fix = 0;
  86.     servo.setPos(i + 1, centre + pos[p][i] + fix, 0);
  87.   }
  88. }