Saturday 23 June 2012

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

Friday 15 June 2012

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}
  ]]