A Centenary of Turing

One hundred years ago today, June the 23rd, 1912, Alan Turing was born. He is arguably one of the most significant mathematicians born in the 20th century. If you're interested in Turing, I strongly recommend Andrew Hodges biography - Alan Turing: The Enigma

Amongst his many contributions to mathematics, science and cryptography, perhaps the most significant from my perspective relates to the 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem", in which he introduced what is now known as a Turing Machine, the theoretical underpinning of the modern computer. A great summary of the concepts in that work is available in Charles Petzold's book The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine

For me, Turing stands as a reminder of many things:

His work demonstrates the greatness of modern science - in particular how important independent thinking and hard work are, as well as demonstrating how cross-pollination of ideas from math, science and engineering are capable of bringing about remarkable, and in some cases world-changing ideas.

I believe that Turing was, in part, inspired to greatness by his peers, from school and beyond, as well as obviously leaving behind a legacy that has inspired so many. I've been blessed with mentors of my own, both in work and in life. This year, I've taken on the responsibility for mentoring someone, and am sharply reminded how important this role can be.

Turing's story ended in tragedy - he was persecuted by the British authorities of the time for indecency (homosexuality), which ended up with him being punished with chemical castrated. His death two years later was (very strongly) suspected to have been suicide, caused by consumption of a cyanide laced apple. For me, this highlights the need to remain vigilant for unjust prejudices, both around me, and in my own thinking.

Happy birthday Turing, you remain an inspiration

Visualisation of Kuhn Triangulations

One of the things that got briefly referred to in the under-actuated robotics course was the excellent paper "Variable Resolution Discretization in Optimal Control" by Munos & Moore. I'd had a copy of the paper lying around for a while, because it was mentioned in Steven Lavalle's book Planning Algorithms

That paper recommends a more efficient method of interpolation using simplexes rather than hypercubes. The advantage is that simplex interpolation requires (n+1) points rather than 2^n points in n-dimensions.

One of the best things about the Munos & Moore paper is a really great explanation of how interpolation in simplexes using Kuhn triangulation works, as well as a number of really great diagrams. I've attached some (pretty horrible) Mathematica code that I've used to reproduce something similar to one of the explanatory figures from that paper.

(* The m-th cartesian aligned basis vector in an n dimensional space. *)
BasisVector[n_, m_] := Map[If[# == m, 1, 0] &, Range[n]]

(* Takes an ordered list of basis functions which describe the order \
to walk the tetrahedra boundary in *)
SimplexVecs[perm_] := Accumulate[
  Join[
   {ConstantArray[0, Length[perm]]}, 
   Map[BasisVector[Length[perm], #] &, perm]
   ]
  ]

(* Generate all 3d tetrahedra on a unit interval *)
TetrahedraGeom3D[] := Map[
   GraphicsComplex[
     SimplexVecs[#],
     Polygon[Subsets[Range[n + 1], {n}]]
     ] &,
   Permutations[Range[n]]
   ];

SimplexCenter[gc_] := Mean[gc[[1]]]

(* Generate all the geometries *)
gs = TetrahedraGeom3D[];

(* Shift them a little bit away from the cube center*)
gs = Map[
   Translate[#, SimplexCenter[#] - {1/2, 1/2, 1/2}] &,
   gs
   ];

(* Generate a 'nice' list of colors *)
mycolors = {Red, Green, Blue, Cyan, Magenta, Yellow};

(* Compose the graphics together, and render *)
Show[MapThread[
  Graphics3D[{Opacity[0.4], #2, #1}] &,
  {gs, mycolors}
  ]]

Minimum time value iteration solution of the double integrator

I've spent the last week of spare time working of a value iteration problem for the underactuated robotics subject I've been working on. In particular this has involved finding the optimal policy of how to get the undamped double integrator to the origin in minimum time (github gist of code). A MATLAB / Octave solution is available on the OCW site, so I don't feel too bad publishing this here.

This has been something a bit different for me, considering how little vectorised code I've written in the past, but has already had a big impact on some things I'm doing for a number of projects. The performance benefit is substantial, but it makes code hard to read, write, debug and test.

Python simulation of the simple pendulum

Following on from the previous post, I've created some simulations of the simple pendulum without damping or control input. This work was designed more to be a test of my understanding of how to use the scipy integrator module, and to make sure the matplotlib plotting code worked correctly.

I'm pretty pleased with the results, and you can see a plot of the homoclinic orbits of pendulum starting in different initial states, and some videos of what that means, if you don't naturally think in phase space.

Python simulation of the Van der Pol Oscillator

One of the things I'm doing at the moment is watching an excellent series of MIT OCW lectures by Assoc. Prof. Russ Tedrake on underactuated robotics. I've learned a lot watching the videos, which pick up at a point where some parts of my doctoral studies finished.

Just to pick something small that is at least tangentially related to the related to the course, I've attached a python snippet of code for generating the Van der Pol Oscillator. This system is significant in that it exhibits limit cycles, which are an important tool for reasoning about walking robots

import numpy as np
import matplotlib.pyplot as plt
from scipy.integrate import odeint

mu = 0.2

def van_der_pol_oscillator_deriv(x, t):
    nx0 = x[1]
    nx1 = -mu * (x[0] ** 2.0 - 1.0) * x[1] - x[0]
    res = np.array([nx0, nx1])
    return res

ts = np.linspace(0.0, 50.0, 500)

xs = odeint(van_der_pol_oscillator_deriv, [0.2, 0.2], ts)
plt.plot(xs[:,0], xs[:,1])
xs = odeint(van_der_pol_oscillator_deriv, [-3.0, -3.0], ts)
plt.plot(xs[:,0], xs[:,1])
xs = odeint(van_der_pol_oscillator_deriv, [4.0, 4.0], ts)
plt.plot(xs[:,0], xs[:,1])
plt.gca().set_aspect('equal')
plt.savefig('vanderpol_oscillator.png')
plt.show() 

Which when simulated looks something like this:

Hard Real-Time Motion Planning for Autonomous Vehicles online now

It's been a while since I've checked, but Swinburne University have published a low quality copy of my PhD thesis - "Hard Real-Time motion Planning for Autonomous Vehicles" online at their research bank. If you don't want to download the whole thing, you can look at the summary here

During my candidature I had the honour of working with the team developing the Wayamba Unmanned Underwater Vehicle, a three meter long flat-fish form factor research vehicle.

Image Taken from http://www.defence.gov.au/news/navynews/editions/4821/topstories/story08.htm

PyCon - Day 5 (Sprints Day 1)

Today was the first time I've ever sprinted, and I can honestly say it wasn't at all what I expected. I was expecting frantic energy, and I mistakenly assumed that the project maintainers would turn up with a huge number of tickets that would get allocated to anyone who came. I also hoped (expected?) that there would be someone experienced in the project who would help me get started.

Instead it was a cross between a design meeting and a pretty regular work day, and while everyone was friendly and very helpful, they were also busy trying to get their own work done.

It's no-ones fault - I just wasn't anywhere near prepared enough to actually be useful helping on the project that I wanted to work on. In part, I guess that some of that is about trying to break into a community - there needs to be a degree of trust before you get commit rights to a major repository. So I'm happy to watch most of this one out, with the understanding that things will go better at future conferences.

Instead, I've had a good day working on a related topic to my project of interest, which I'm hoping may end up with nice enough results to put in for a PyCon AU talk.

We'll see how it goes.