Thread: Smallest binary pattern for ant navigation

We have a virtual ant which uses a chemical scent trail to navigate along a path. As the ant explores in new directions it lays down chemical blobs at regular intervals. The presence and pattern of these blobs helps the ant navigate back to the nest and other ants navigate to where the pioneer ant is located.

Since the blobs are placed regularly, it seems more than one chemical marker is necessary, because a string of "A A A A A..." doesn't help the ant determine which direction is toward the nest and which is away from it.

So if you had two chemical markers A and B and had to lay them in a regular pattern, so that an ant traversing the pattern could tell WHICH WAY they were going, how small would the smallest such pattern be?

For example, "A A B" doesn't work, because the reverse, "B A A" is a cyclic permutation of "A A B" and thus the ant would not be able to tell which way it was headed. So you're looking for the smallest string of A's and B's whose reversal is not a cyclic permutation of itself.

Why does the ant need to know its heading?

I would suggest all it needs to know is what to do when it encounters a particular marker, based on goal (heading to food, heading to nest) and maybe some time history. So its movements would be relative to its existing motion, with changes (keep going, bear left, bear right, go back) based on the marker [or a limited history] and what it is trying to do (e.g. the responses for an ant heading to food from the nest would differ from the responses of an ant carrying food to the nest).

Would an ant be able to make sense of colocated markers (for example, respond differently to A on top of B versus B on top of A versus A only versus B only)?

Originally Posted by grumpy

Why does the ant need to know its heading?

Not the heading, just whether it's heading toward the nest or away from it. If the ant leaves the trail and intersects it again it needs to know which way the nest is.

Originally Posted by grumpy

I would suggest all it needs to know is what to do when it encounters a particular marker, based on goal (heading to food, heading to nest) and maybe some time history. So its movements would be relative to its existing motion, with changes (keep going, bear left, bear right, go back) based on the marker [or a limited history] and what it is trying to do (e.g. the responses for an ant heading to food from the nest would differ from the responses of an ant carrying food to the nest).

If the ant always stays on an existing trail that all makes sense, because it can orient relative to the way it already knows it is going. But if it encounters some other trail...

Would an ant be able to make sense of colocated markers (for example, respond differently to A on top of B versus B on top of A versus A only versus B only)?

Maybe. If it could map out the blobs in two dimensions it might be able to tell which mark was on top of the other and thus the sequence of marks at that spot over time. This reminds me of how they (supposedly) can recover data from magnetic storage even after it has been overwritten...

I had essentially the same idea as Maticcus, but with increasing distances between a single chemical:

Code:

A A  A   A    A A  A   A    A A  A   A    A
               *

If the ant encounters a radical distance change (such as at the asterisk), it ignores it, but small changes are either increasing or decreasing, which determines the direction.

I should have rotated it slightly to show a nicer pattern: A-B-AA-BB
This is equivalent to the earlier one.

I wonder if ants or snails have sophisticated enough mechanics to generate chemical blobs in this manner. It is nothing more than two differing chemicals (or concentrations), deposited alternating A followed by B in small portions followed by larger deposits AA followed by BB.
I have thought about this problem years ago - and I wondered whether the creature uses an even simpler direction-encoding in its path: one chemical but deposited in an increasing (or decreasing) wedge - similar to triangles or arrows. This is actually similar to the "binary" sequence above except that now we are allowing a 'width' dimension instead of 2 chemicals. In other words the varying amount deposited is coded as a width rather than as a duration.

I also was unable to come up with a sequence shorter than six. I think six is probably the shortest possible.

Originally Posted by Matticus

If the constraints are simply an alternating pattern with no clever tricks allowed (e.g. the "side by side" method proposed by anduril462, or the varying distance method proposed by oogabooga), then it appears that six is minimum sequence length needed to meet your goal.

This is based on the results of a small program I wrote to test all permutations of sequences from lengths of one through six. The only time the pattern differs between the forward and reverse of such a string is when the length of that string is at least six.

Interesting. Where is this number six coming from?

If you had three markers or more, the problem becomes boring! Because if you have A, B, and C you just mark "A B C" and this distinguishes the two directions. But for the case of two markers you get this minimum sequence length of six. Fascinating.

EDIT: Ants have six legs. So they can put down one marker of the sequence for each leg. Coincidence? I think not!!!

Originally Posted by brewbuck

Interesting. Where is this number six coming from?

If you had three markers or more, the problem becomes boring! Because if you have A, B, and C you just mark "A B C" and this distinguishes the two directions. But for the case of two markers you get this minimum sequence length of six. Fascinating.

Well, you could use two markers and make "C" be a matter of spacing. E.g.:

AB--AB--AB--AB

On the other hand, nature actually didn't solve the problem. Ants lay continuous pheromone trails and if their own trail intersects another ant's, it randomly picks a direction and goes. Maybe it ends up back at the nest, maybe it ends up somewhere else. When ants find food, they strengthen the pheromone trail and make it more likely that other ants will use that trail too.

Not the heading, just whether it's heading toward the nest or away from it. If the ant leaves the trail and intersects it again it needs to know which way the nest is.

I think your representation of trails is off a bit. Use vectors.
When the ant leaves the trail then make it pick back up where it left. One simple vector would guide the ant back.

However as to the question of direction this can be done with vectors and the dot product. If each trail is a set of nodes connected by vectors to the next node and all vectors always point to the nest then it is a simple operation to figure out which way to go. You must set your navigation trails up so that all vectors point in the direction of the nest or to the next node(s) that will eventually lead to the nest. It does not matter how many curves and patterns there are in the trail so long as if you traverse it linearily from node to node always moving the direction of the to vector to the next node...you will end up at the nest.

This approach would also allow you to leave any trail at any time and pick back up on any other trail at any time and instantly know which direction to go to head to the nest.

If you do not have preset trails then every so often lay down a 'node'. Create a vector from that node to the previously laid down node. You can have the nodes time out if you want to simulate trails disappearing, etc.

This problem is 2D so you need 2D nodes and 2D vectors.