Like Tree4Likes
  • 2 Post By Matticus
  • 1 Post By nonoob
  • 1 Post By VirtualAce

Smallest binary pattern for ant navigation

This is a discussion on Smallest binary pattern for ant navigation within the General Discussions forums, part of the Community Boards category; We have a virtual ant which uses a chemical scent trail to navigate along a path. As the ant explores ...

  1. #1
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,263

    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,527
    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)?
    Last edited by grumpy; 01-15-2014 at 06:57 PM.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy in reply to you, it is likely you deserve it. Suck it up, sunshine, and read this, this, and this before posting again.

  3. #3
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    1,678
    Quote Originally Posted by brewbuck View Post
    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.
    You don't lay out many constraints, so... perhaps rather than having "different" chemical markers ("A" and "B"), you only need the one but with an orientation attribute. The ant could tell "which way" it was going by how it's orientation aligns with that of the markers'.
    A class that doesn't overload all operators just isn't finished yet. -- SmugCeePlusPlusWeenie
    A year spent in artificial intelligence is enough to make one believe in God. -- Alan J. Perlis

  4. #4
    Registered User
    Join Date
    Jun 2011
    Posts
    2,650
    What a fascinating subject! According to wiki, ants are thought to use a lot more than simply their trails for navigation:
    Ant - Wikipedia, the free encyclopedia

    I don't know if there's a clever way to indicate direction (and potential branches) simply through the usage of trails. Perhaps keeping one chemical singular, and the other increasing in frequency for a few short bursts.

    A-B-A-B-B-A-B-B-B (repeat)

    If the number of B increases by one, it's "north". If the number B decreases by more than one, it's also "north".

    If the number of B decreases by one, it's "south". If the number B increases by more than one, it's also "south".

    That's all I can come up with on the spot.
    stahta01 and oogabooga like this.

  5. #5
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,263
    Quote Originally Posted by grumpy View Post
    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.

    Quote Originally Posted by grumpy View Post
    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...
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  6. #6
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  7. #7
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,629
    Can it drop two blobs side by side?

    not nest
    AB
    AB
    AB
    nest

    If A is on the left, you're heading away from the nest. On the right, heading towards it.

  8. #8
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    A-B-B-A-B-A (repeat)
    Yarin likes this.

  9. #9
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    1,678
    Quote Originally Posted by nonoob View Post
    A-B-B-A-B-A (repeat)
    Nice. A cyclic permutation as mentioned by the OP, but scalable and able to handle forks and joins.
    A class that doesn't overload all operators just isn't finished yet. -- SmugCeePlusPlusWeenie
    A year spent in artificial intelligence is enough to make one believe in God. -- Alan J. Perlis

  10. #10
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    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.
    Last edited by nonoob; 01-17-2014 at 04:29 PM.

  11. #11
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,263
    I also was unable to come up with a sequence shorter than six. I think six is probably the shortest possible.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  12. #12
    Registered User
    Join Date
    Jun 2011
    Posts
    2,650
    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.

  13. #13
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,263
    Quote Originally Posted by Matticus View Post
    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!!!
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  14. #14
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    Quote Originally Posted by brewbuck View Post
    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.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  15. #15
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    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.
    Last edited by VirtualAce; 01-31-2014 at 07:58 PM.
    Hodor likes this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Long integer to binary pattern
    By mark522 in forum C Programming
    Replies: 3
    Last Post: 12-17-2009, 06:03 AM
  2. TabControl Navigation Issue
    By WaterNut in forum C# Programming
    Replies: 0
    Last Post: 02-14-2008, 02:20 PM
  3. Binary Function - Design Pattern Question
    By Raven Arkadon in forum C++ Programming
    Replies: 9
    Last Post: 07-18-2007, 03:39 PM
  4. Searching Binary Files for a Pattern
    By CaptainMorgan in forum C Programming
    Replies: 16
    Last Post: 06-17-2007, 07:04 PM
  5. XML Navigation
    By Khelder in forum C# Programming
    Replies: 2
    Last Post: 05-26-2004, 04:19 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21