Omniscient bots gathering on $\mathbb{Z}^2$

Question

There are $N=n^2$ "bots" on distinct integer lattice points in the plane. Each knows the positions $p_i$ of all bots, and each has unlimited (private) memory. Each executes the same algorithm $\cal{A}$: at time $t=0,1,2,\ldots$, bot $i = (t \bmod N)$ executes $\cal{A}$, which (possibly) examines the bot positions and consults its memory, resulting in it either remaining at $p_i$, or moving 1 unit in one of the four compass directions to an unoccupied lattice point.

Q1. Is there an algorithm $\cal{A}$ which, starting from an arbitrary configuration of $N$ bots, terminates with all bots arranged in an $n \times n$ square?

          

          _{(This question is inspired by (but not mentioned in) arXiv:1111.2259.)}

I believe the answer to Q1 is Yes, say by gathering toward the lowerleftmost bot, but I don't see it in clear detail. If this is right, then suppose omniscience is blocked by opacity:

Q2. Is there an algorithm as before, but now with each bot $p_i$ knowing the position of $p_j$ only if the line segment $p_i p_j$ does not share a point interior to a unit square centered on any other $p_k$.

My guess here is: No.

Answer 1

An idea for Q2: the bots can determine if they are the ``lowerleftmost'' bot (the most left bot on the lowest row with bots).

Then this bot moves to a position low and left enough, away from the others (far enough so it won't block lines of sight).

The other bots who decided that they are not the lowerleftmost stay put, and track if they see some other bot move. If they see a bot halting at a certain position (and see every other bot halting), they can decide if they are the lowerleftmost of the ones not in the horizontal line of bots where the previous one just stopped moving. If this is the case they join this horizontal line on the right hand side (by the shortest path) and do nothing till they see something moving below them.

Repeating this algorithm gives you all the bots on this line. Bots can determine if they were the last one to join this line. Then this last one moves below the other ones in a certain pattern to initiate an ``endgame'' forming the square.

There is one last problem you'd need to add to the algorithm: the horizontal line where you build on might be too full to be far away enough from the others. The block which wishes to join should then go straight down enough to be in sight of all other blocks in the horizontal line and then return. The blocks already in the horizontal line should be programmed to move the line one spot to the left if they see this occuring below them. This move should be orchestrated such that the bot wishing to join stops last.

I hope this helps, I might be missing something still however.

Answer 2

An explicit algorithm for Q1: (I think?)

Let $p$ be a prime larger than $2^n$. Assume the lower left bot is at $(0,0)$ and weight each bot at $(i,j)$ with $p^i2^{-j}$ (hence all bots have distinct weights and the weighting favours bots to the left and at the top).

Group the bots with the $n$ lowest weights into a set $A_1$, the next $n$ into $A_2$, and so on. Each bot in $A_i$ then performs the following algorithm:

1) Are all the bots in $A_j$ for $j < i$ lined up so that the bots in $A_j$ are on the $(j-1)$ file? If not, don't do anything.

2) Otherwise, are you on $A_i$? If so, don't do anything.

3) Otherwise, is there a bot in $A_i$ with lower weighting on your file? If so, don't do anything.

4) Otherwise, is there a bot immediately to your left? If so, move up one.

5) Otherwise, move one to your left.

Running this enough times hence ensures that all bots in $A_i$ are on the file $(i-1)$. Note that this algorithm preserves the relative ordering of all bots according to the weighting.

Now we just switch to the algorithm which shuffles each file down to make an $n\times n$ square:

1) Is there a bot immediately below you? If so, don't do anything.

2) Otherwise, move down one, unless you are already on rank 0. Then don't do anything.

Roughly: shuffle all the bots until they're on the right file, then shuffle them down to lie on top of one another.

This fails Q2, however, since each bot needs to know the positions of all other bots before it does anything.

EDIT: Not quite as stated; see my comments below for an initial spreading algorithm. In particular, memory is needed, since each bot needs to know if it's been spread already (otherwise the same bot just keeps being flung further and further to the right).

Answer 3

This should formalize Koen S's answer: which fully answers Q2.

Stage 1: Every bot scans to see if they are the "lowerleftmost" bot; the bot which satisfies that condition calls itself Alice. Of the remaining bots, each bot on the left end of its row calls itself Bill, and if a bot is not the left-most one on its row it calls itself Carl.

Stage 2: Alice moves down once, and then left until there are no bots to her left, nor directly above. Alice moves left once more for good measure. (Note: If there was another bot on the same initial row as Alice, the left-most one changes its name from Carl to Bill.)

Stage 3: Whenever Alice is on an empty row, she moves up one row (unless there are no bots on rows above her). If Bill sees Alice move onto his row, he moves down once on the next turn. If Carl sees the bot directly to his left (on the same row) move down, he moves down on the next turn.

This allows Alice to count how many bots there are, on each row, and in which positions. Each bot, one by one, simply moves down one square.

Stage 4: If Alice is on a row with no other bots (but at least one bot on a row below her) she moves down. If she is on a row with other bots, she communicates with the left-most bot. She does this by left-right movements (which allow her to encode the information in binary). She communicates where that bot should move into a square (far above the original configuration). After she tells the bot where to go, she waits until that bot will have gotten into position, and then communicates with the next bot on the row, moves down, or (at the very end) takes her own position in the final square.

Answer 4

Here's a three-stage Q2 procedure at the end of which all the bots are lined up in a single horizontal row, with each bot assigned a number according to its position in the row, say from left to right. From there it's straightforward to create a square: The first $n$ bots stay where they are, the next $n$ move up 1 and over $n$ (taking as many rounds as needed), the next $n$ up 2 and over $2n$, etc.

In Stage 1, the bots will space themselves out so that each bot is in a separate column. During this stage, each bot will move to the right (whenever it can on its turn) if it sees another bot immediately on its left or if it sees a bot anywhere below it in its column. This should only take about $N^2$ rounds at worst, but to be on the safe side let's assign a total of $10^N$ rounds for it, during most of which most bots will simply sit idle during their turn, just counting down until the stage is over. (Edit made 1/24/12 in response to a comment of Pace Nielsen.)

Stage 2 will last exactly $N$ rounds. Each time it's bot b's turn during this stage, bot b will move one space down if it thinks it might be in the bottommost row, otherwise it will stay put. Note that during each round, at least one bot will move down and, more important, at least one bot will stay put. (If the bots don't all start on a single row, there is certainly at least one bot that can see there are bots below it; if they do all start on a single row, then the first bot to move down serves as a signal for at least one bot to its left or right that it's no longer on the bottom row.) As in Stage 1, most of the bots wind up doing nothing during Stage 2 but counting down until the stage is over. At the end of this stage, all the bots know there is exactly one bot in the bottommost row, and they know it will regard itself as bot #1. Or should we say the "alpha" bot?

Stage 3 will take as long as it takes, but the bots will all know when it's over. During this stage, each "beta" bot will do nothing until it's been "tickled from below" by a string of bots moving from left to right on the row just below it. It counts these bots as they pass by and then drops down to join them, knowing it's own number in the left-to-right string. Once it's in the string, it will basically follow the bot ahead of it. The string, of course, is headed by the alpha bot. The alpha bot begins this stage by taking a couple of steps down (so as not to tickle anyone until it's ready) and then doing an ever-expanding back-and-forth search until it's seen all the other bots, which Stage 1 had so kindly put in separate columns. Once the alpha bot knows where all the other bots are, it heads for the rightmost bot on the bottommost row above it and begins creating the string. Each time it reaches the leftmost bot in a row, it swings down and loops back around to the right, to get started on the next row, with the ever-growing string trailing behind. And so forth.

Note that during the initial phase of Stage 3, while the alpha bot is doing it's widening search, the beta bots will be able to spot it as well (when it passes directly beneath them, at the very least). So alternatively one could do the roundup by letting each beta bot begin dropping toward the alpha bot's row as soon as it sees it, stopping say two rows above the alpha bot's pacing. The alpha will know when everyone's in place. It can then come up from below and "teach" each beta bot its number, say by touching it and then moving $k$ spaces down before going to the next bot. Once each bot knows its number they can crowd together in a single string.

Added 1/21/12: Here's an alternative approach, inspired by the answers of John Ramsden and John Wiltshire-Gordon.

The process begins with a predetermined number of rounds in which the bots get themselves spread out, so that each one will have room to do a little "waggle dance" without bumping into anyone.

When the spreading-out stage is complete, each bot will make a mental list of the x and y coordinates (in binary) of all the bots whose current position it knows, using its current position as the origin. At first this list will consist only of those bots it can see (plus perhaps a few it may have noticed while the bots were spreading themselves out). The point is, these lists are going to grow as the bots observe each other's waggle dances, until each bot has a complete list of all the other bots' coordinates.

The waggle dance takes the following form:

"I know where a bot is..." -- one step up from its initial position.

"Its x coordinate (of its initial position, relative to my initial position) is..." -- another step up.

"1" -- a step to the right followed by a step back to the left

"0" -- a step to the left followed by a step back to the right

[It repeats these 0's and 1's until it's communicated the entire binary sequence. The reason each bit uses two steps is so that the bot doesn't wind up wandering away from its initial position.]

"Its y coordinate (relative to my position) is..." -- another step up, followed by the right/left's and left/right's of the y coordinates 1's and 0's.

"And that's where that bot is!" -- three steps down, back to the initial position.

While each bot does its own dances, it's watching the dances of the bots it can see, and every time it sees a completed dance, it converts the transmitted information to its own coordinate system. If that results in actual new information, it adds it to its mental list and schedules it for a dance of its own. The point is, eventually every bot will know the initial position of every other bot, even for the ones it can't see, because each bot is in the line of sight of a bot that's in the line of sight of a bot that's in the lines of sight, etc.

The waggle dance might also transmit information that identifies the "number" of each bot. I'm not sure that's necessary, but it probably wouldn't hurt.

Once a bot knows where all the other bots' initial positions are, it can compute the "center of mass" of all the bots, rounded to the nearest lattice point (with appropriate tie-breaking conventions). It can then transform all its knowledge to a coordinate system with the center of mass as the origin, determine based on its own number where it belongs in a square whose lower left hand corner, say, is at the origin, and start heading toward its destination. One potential glitch in this is that bots might get in each other's way -- you might, for example, have all the perimeter bots arrive first, blocking the interior bots from getting inside -- so it might make sense for bot $k$ to wait until bots 1 through $k-1$ have had time to get into position: Once a bot knows the initial positions of all the other bots, it can compute what those bots currently know, when they'll have complete information, and what they'll do with it. In particular, each bot can linger in its initial position until it knows all the other bots have complete information. If the bots notice that some of their brethren are occupying positions within the target square, they can run a predetermined algorithm to move them out of the way and then start taking turns assembling the square.

All this, of course, is highly inefficient. I'm just trying to outline approaches that will clearly and (I hope) correctly work.

Answer 5

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 rectangle containing them all, each assigning themselves a unique row-major order in this rectangle and mapping that to the row-major order in a target square disjoint from the bounding 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 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.

Answer 6

Here is an easy answer to Q2:

First each bot determines if it is in the bottom occupied row. These bots call themselves "home row bots". Each home row bot takes a step downwards. The bots which are not in home row begin to march right.

Each bot in the next occupied row above home row sees every bot below it move down one. These bots now call themselves "next row bots". Note that every next row bot can now see every home row bot (and vice versa).

The leftmost bot of home row (who will act as the leader of home row) takes a step down to check the positions of the other bots in his row, and then returns to his place.

The leader now performs a left-right waggle dance for the benefit of the next row. He transmits the number of squares the next row needs to march until every bot of the next row is to the right of every bot of home row.

Each bot in the next row, observing the waggle dance, continues marching until it has taken the prescribed number of steps. The next row then walks down to get in line behind the current home row.

The bots above the old next row observe this downward motion and infer that they are the new "next row bots". The leader of home row performs another waggle dance, and these bots join home row as well.

This process continues until all the bots are in home row.

Now the bots play follow-the-leader. The leader walks up n, then right n, then down (n-1), then left (n-1), then up (n-1), etc., spiraling inwards. As the other bots follow, the leader leads them into a box shape.

Answer 7

Maybe you can do Q2 by deterministically spreading out until all bot positions are common knowledge, reducing to Q1. Or maybe a stranger bot would first need to say that one of them has blue eyes.

Edit: In more detail, I think you can do it in three phases as follows. Initially the bots spread out deterministically. The first time that the bot sees that every bot sees every other bot (the trick would be proving that this will happen), it declines to move for a single round. On the round following this pause, the bot begins acting according to the Q1 strategy, following it until the solid square has been formed. To an observer, the bots would appear to spread out, then pause for a single round, then collapse into a square.