Robots On A Sphere

So, the blog seems to be reverting to a semi-weekly thing (where semi-weekly means every other week, not twice a week, which is apparently semi-standard english (where semi-standard means half standard, not twice standard, at least I'm consistent)). Anyway, I first found this puzzle on the xkcd forums:

Two robots are being sent to a planet, and you will have to write an algorithm for the robots to find eachother. The planet is a perfect, featureless sphere of known radius, and the robots are of a size epsilon (epsilon is small compared to the size of the planet). The robots each have a single flag that they can place anytime at their location that cannot be moved once placed. The robots have no sight range and can only find something by bumping into it, but they can tell the difference between their own flag, the other robots flag, and the other robot. Each robot must be given the exact same deterministic program, the robots will land somewhere randomly on the planet and will them just follow their program. Find an algorithm that guarantees that the robots can find eachother.

The hardest part is dealing with the fact that both robots must be given the same program. You may assume for simplicity that the robots already have a simple program for searching out an area (were you able to keep one robot stationary while the other moves, this problem would be trivial, as it is easy to search the entire planet surface given its radius and the robots size) so you don't need to write out such an algorithm explicitly.