search

liorwirt / AntsGroup

Ants Group Site
GNU General Public License v3.0
0 stars 1 forks source link

Algorithmic Thoughts #1

Closed dngreenst closed 5 years ago

dngreenst commented 5 years ago

Some thoughts regarding the algorithmic framework below. This still feels half-baked, so I'll appreciate your comments.

If we have enough ants to cover the whole cave/building with the ant's sensors while maintaining data connection to the outside, then mapping the cave is sufficient to detect movement from the cave/building's entries:

Once we have mapped the whole cave and covered the topology of the cave with the ant's sensors, we can detect any entry and exit to the cave/building.

Additionally, we can detect changes in topology (for example - a door being opened from a room that was previously unreachable).

I think we can map the cave assuming 2 sorts of ant signals and 2 ant roles:

Ant signals: a. Reached a dead end - do not head in this direction b. Direction is valid (did not reach a dead end - keep moving in this direction)

Ant roles: a. Transmission ant - transfers data and the direction it came from ("pheromones") to nearby ants (of both types). Rules for data transmission will be elaborated later. Transmission ants do not move. b. Scouting ant - Keeps moving in directions suggested by the pheromones (probability based). Transfers data only to transmission ants.

Algorithm for a scouting ant:

  1. While distance(nearest transmission ant) < R: 1.1. Transmit the directions that are physically blocked to the transmission ant 1.2. If all the legal directions around you are marked with dead end pheromones: 1.2.1. next_location=current_location 1.2.2 continue
    1.3. Choose a random direction among the legal directions that are not dead ends
  2. Attempt to become a transmission ant, based on exponential backoff 2.1. If successful, go to algorithm for transmission ant 2.2. Otherwise, there is a new transmission ant nearby - go to 1.

Algorithm for the transmission ant - Transmit pheromones according to the following rulebase:

  1. If there are no reachable transmission ants in direction d: 1.1. If there are no reachable scouting ants in direction d: 1.1.1. Transmit that direction d is still valid (not a dead end) 1.2. If there are reachable scouting ants in direction d: 1.2.1. If all (??) scouting ants in direction d have found a physical dead end 1.2.1.1. Transmit that direction d is a dead end 1.2.2. Else: 1.2.2.1. Transmit that direction d is valid
  2. If all (??) transmission ants in direction d mark it as a dead end: 2.1. Transmit that direction d is a dead end
  3. Else: 3.1. Transmit that direction d is valid
dngreenst commented 5 years ago

Two problems with this algorithm framework that come to mind:

  1. We might have a faster way to detect openings - mapping the whole building/cave might be a bit of an overkill
  2. Having enough ants to map the whole building and leave them there to detect changes in topology requires much more ants - this might be an even greater overkill

Additionally, the section regarding the transmission ants rulebase feels off.

hartmaneyal commented 5 years ago

Was looking for something more "antsy" and came up with the following (less than half-baked I'm afraid):

Assumptions:

Abbreviations: TA = transmission Ant distance(Nearest(TA),x) - distance to nearest transmission Ant from location x R = transmission Range Radius AP(x) = Number of available paths around location x PT(x) = "Pheromone trails" around point x - set of points known to the transmission ant around location x containing AP(y)|y denotes locations around x. NA = a value given by AP(x) to an uncharted location (no pheromone trail or visible obstacle) NA is an integer with a value we will determine later (higher number = exploration)

Optional: decay of "pheromone trail" to encourage re-exploration to see if something changed Optional: find a way to recalculate AP(x) based on all trails it leads to (so that dead ends will be identified early)

Algorithm: While distance(Nearest(TA),x) < R: --Scan surrounding and set AP(x) --Save AP(x) to internal AP array --Transmit AP(x) --If AP(x) > 0: ----Get PT(x) where any uncharted location gets NA and blocked paths gets 0 ----if Sum(PT(x)) = 0: ------Move to Previous location ------if AP(Previous location) = 0 [need some recursion here] --------Exit and return home (?) ------loop ----else ------From PT(x) where AP(x)>0 select location y randomly ------------- [giving higher chance to locations with higher AP(x)] (?) ------if R < distance(Nearest(TA),y) --------Exit loop ------else --------Move to y --------loop --else ----Move to Previous location... Become TA

hartmaneyal commented 5 years ago

One more thing I was thinking about is adding a function to call for re-enforcement - similar to what ants do, we can start with a minimal number of ants and as they reach junctions \ transform to a transmission ant more ants will be called from the "nest".