Finding myself today on a long flight overseas without access to the internet, I started wondering what it would take to make a robot that moved like a millipede. My thought was that a robot millipede could move not merely forward and back, but in any direction.
The first thing I came up with works like the following, when seen in profile:

If you click on the above image you can play with the interactive applet. The basic idea is that as the surface undulates, the little “hairs” on the bottom spread out and come back together in such a way that they grip the floor and pull the robot along.
I was thinking that these “waves” of undulation could go in any direction, so at any moment the robot can move itself along the floor in any direction. One possibility is to put a regular arrangement of up/down actuators on the underside of the robot, like this:

Then it occurred to me that rather than make this a vehicle, one could cover an entire floor or table with this kind of thing. Then any object you put on the surface could be moved along under computer control. This is reminiscent of some wonderful work done by Dan Resnick a while back, in which he cleverly vibrated a table to make it move multiple objects at the same time. One problem with Dan’s approach was that the more objects you wanted to control, the slower everything moved. The millipede surface wouldn’t have that problem.
Of course it will come down to questions like “How cheap can you make an actuator that just moves slightly up and down?” Should you use solenoids, memory metals, piezoelectrics, or something else entirely? The whole thing can be scaled down to very small sizes and still work, so the answer might just come down to finding a mechanism that comes in a really low cost per unit area when the actuators are at some optimal scale.
Perhaps eventually there will be a nano-tech solution, and these things will become as cheap as wallpaper. Imagine the desk that can arrange your papers or bring you your coffee cup — or a floor that could rearrange your furniture for you. That would be very cool.