MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 added 40 characters in body

Looks easy if you aren't worried about the efficiency of the algorithm. If the bots can agree about which direction is bottom-left, they can start by drawing the smallest bounding square rectangle containing them all, each assigning themselves a unique row-major order in this square rectangle and mapping that to the row-major order in a target square disjoint from the bounding square rectangle but in some predictable position relative to it.

Then the algorithm for i = 1, 2, n is simply for the i-th bot to shuffle towards its target position one step at a time while the remaining bots do nothing until this position has been reached.

Choosing the bots in row-major order, in other words imagining that the rectangle and the target square is are each cut into rows stitched end-to-end as one long strip guarantees that no bot whose turn has started is enclosed by other bots and therefore unable to move to its target position.

show/hide this revision's text 1

Looks easy if you aren't worried about the efficiency of the algorithm. If the bots can agree about which direction is bottom-left, they can start by drawing the smallest bounding square containing them all, each assigning themselves a unique row-major order in this square and mapping that to the row-major order in a target square disjoint from the bounding square but in some predictable position relative to it.

Then the algorithm for i = 1, 2, n is simply for the i-th bot to shuffle towards its target position one step at a time while the remaining bots do nothing until this position has been reached.

Choosing the bots in row-major order, in other words imagining that the square is cut into rows stitched end-to-end as one long strip guarantees that no bot whose turn has started is enclosed by other bots and therefore unable to move to its target position.