Modular machine assembles copies of itself in minutes.
Rather simple but elegant self assembly of robots. From the movie we can see a tower replicating by picking up pieces at predetermined places and putting them together to form a copy of itself.
It would look a lot cooler to have something like a "cube dispenser". All cubes should be able to communicate with each other. "dead" creatures should return themselves to the cube dispenser unit. "live" creatures all know were to get the cubes from and how to replicate themselves. Some mutations should be possible in order to make more complex creatures. Add some goals like the machine the moves more or the machine that can move some objects is allowed to replicate more.
With these simple type of rules and some more complex body parts they would start to have some very interesting robots.