Hero (or Heron) of Alexandria is one of the first well-documented automaton-makers in history. He designed many ingenious devices. The folks over at The New Scientist have made a working model of a self-propelled, programmable cart that was used on stage. Very cool.
I learned of the video first from BoingBoing.net.