4

I am trying to understand this paper and do a live implementation of improved ant colony optimization for robot navigation paper. While I was trying to implement, I was having a few questions that strikes my head:

  1. The author introduced negative pheromone depositing(mentioned in page 2 second column of the above paper). But I didn't understood what it is or where it is used! Inside the paper, it doesn't talk about it as well googled about it. What is it and where would we use it? We are already doing pheromone deposition and evaporation.

  2. In the goal seeking algorithm (in page 2), the Pheromone deposition is done after all the ants are moved to the next position as well as after the evaporation is carried out. So, at that time, the depositing of the pheromones is carried out by iterating through all the ants and updating the pheromone concentration in their current location, isn't it?

  3. In that goal seeking algorithm (in page 2), the author talks about Check if termination criteria met. So, does that mean check whether the ant had reached the goal(ie. destination location)? If so, the execution should be terminated. Isn't it?

  4. Apart from that, I didn't understood what he meant by these three lines in the goal seeking algorithm in page 2:

    • Control ant distance from wall

    • Prevent backtracking

    • Prevent 4 square looping

I have included the screenshot of the relevant part from the above paper:

enter image description here

I would really appreciate if you could clear my above questions.

EDIT

Since there was no response to this, I have asked another question here: https://softwareengineering.stackexchange.com/questions/238639/ant-colony-optimization-movement-of-ants

Community
  • 1
  • 1
Vpp Man
  • 2,384
  • 8
  • 43
  • 74
  • I don't think this is strictly off topic for [so], but I think [cs.se] is slightly more appropriate for this question (just [don't cross-post it](http://meta.stackexchange.com/questions/64068/is-cross-posting-a-question-on-multiple-stack-exchange-sites-permitted-if-the-qu)) (or perhaps even [cstheory.se], but I'm not at all sure about that). – Bernhard Barker May 09 '14 at 22:32
  • Please feel free to move to the respective section if you finds it's more appropriate. Thank you – Vpp Man May 09 '14 at 22:34
  • Please check this: http://programmers.stackexchange.com/questions/238639/ant-colony-optimization-movement-of-ants – Vpp Man May 10 '14 at 16:38
  • Yes, this question would fit on cs.stack, but it is a good thing to boycott this seperation because every question on stackoverflow is either a) algorithmic -> cs b) opinion-based (which to use) and thus off topic or c) code specific -> code-review.stack... – example May 26 '14 at 18:15

1 Answers1

3

The author introduced negative pheromone depositing(mentioned in page 2 second column of the above paper). But I didn't understood what it is or where it is used! Inside the paper, it doesn't talk about it as well googled about it. What is it and where would we use it? We are already doing pheromone deposition and evaporation.

Only skimming the paper you have provided I cannot tell you how exactly they implemented the negative pheromone. There are several approaches, probably the most common general purpose approach is to choose the worst paths generated and give all of their tiles a negative pheromone instead of the regular positive one. There is still a design choice in choosing a function that calculates the movement-likelihood based on the levels of the two different pheromones though...

In the given paper it sounds like they took a similar approach and substracted pheromone from the corresponding tiles instead of adding a second negative pheromone. Thus they don't need to change the function that determined the likelihood of movement to neighbouring tiles.

In the goal seeking algorithm (in page 2), the Pheromone deposition is done after all the ants are moved to the next position as well as after the evaporation is carried out. So, at that time, the depositing of the pheromones is carried out by iterating through all the ants and updating the pheromone concentration in their current location, isn't it?

In that goal seeking algorithm (in page 2), the author talks about Check if termination criteria met. So, does that mean check whether the ant had reached the goal(ie. destination location)? If so, the execution should be terminated. Isn't it?

All ants are moved until they have all reached the goal - or some other termination criterion is met. Eg. you might decide to only wait till at least 90% of the ants have reached the goal or you might include a maximum number of steps.

Evaporate the pheromones on each tile according to (5).

Now consider the paths that all the ants have taken to get to the goal. Add pheromone to all used tiles according to the given function (3) or (4) depending on whether you want to encourage this particular path or not (eg. all ants that did not reach the goal are good candidates for negative pheromones).

Apart from that, I didn't understood what he meant by these three lines in the goal seeking algorithm in page 2:

    Control ant distance from wall
    Prevent backtracking
    Prevent 4 square looping

When choosing the next tile to move to, they restrict the choices somewhat. They want to keep a minimum distance from all walls, so they neglect choices directly neighbouring walls (or some other distance from them, no idea why they decided to include this at this point in the algorithm...). They also forbid an ant from only walking back and forth, so the previous tile is forbidden - as well as 4-square looping (ie loops that consist of four tiles).

EDIT One possible implementation of the algorithm could do the following (where I have chosen the stoping criterion and choice of negative pheromones for you)

initialize all cells pheromone levels to some constant > 0

repeat
    set all ants to start location and erase their history
    repeat
        for every ant do
            if this ant is at the goal skip it
            make list of all neighbouring cells that are
                1. not too close to a wall
                2. not equal to the previous cell
                3. not equal to the cell that was visited 3 moves before
            calculate probability for all cells in this list
            choose next cell according to these probabilities
            update current position and history
        end for
    until 80% of all ants have reached the goal
    
    evaporate pheromones
    
    for every ant do
        if it reached the goal
            add pheromones to all cells in this ants history according to (3)
        else
            substract pheromones accoring to (4)
    end for
until length of shortest path has not changed for M iterations

hope this clears things up a bit. I would change the conditions 2. and 3. in the choice of neighbours to exclude any cell that was already visited by this ant - but that it personal preference....

Community
  • 1
  • 1
example
  • 3,349
  • 1
  • 20
  • 29
  • You did not mention why you want to implement this algorithm. If you have a choice and need something practical let me know and I will add my two cents why this is a bad choice... – example May 26 '14 at 18:06
  • Thanks for the response. This paper when I had chosen first, was looking simple and that's why I decided to try implementing it. As you can see this how it looks now: http://stackoverflow.com/questions/23584460/ant-colony-optimization-movement-of-ants. I am all confused at the moment. The pseudocode in that question is what I have done so far. – Vpp Man May 26 '14 at 18:14
  • @VppMan note that after the loop over all ants you need to add pheromones to the full path the ants took and not just their current positions. after that destroy the ants and start with new ones. – example May 26 '14 at 18:20
  • Means after the inner loop(in the psuedocode of mine), the pheromones are deposited to the whole path that the ant took? So we have to store the paths(or cells) that the ants goes one too. Isn't it? Didn't understood what you meant by "destroy and start with new ones". – Vpp Man May 26 '14 at 18:23
  • Yes, you have to remember the full path that the ant walks exactly for this reason. With the "destroy" part I meant to reset all ants to the start and erase their path-histories before starting the inner loop again. – example May 26 '14 at 18:25
  • Did you really mean to do that? Then the ants won't be moving any cells other than it's first one! Or am I interpreting it in the wrong way? The inner loop just considers each ant and moves one cell. This is done for the whole ants and at the end of that loop(ie. executed for TOTAL_NUM_OF_ANTS times), if we try to reset the ants back, then there is no improvement in the movement! – Vpp Man May 26 '14 at 18:29
  • @VppMan indeed, in your pseudo code it is. But in the paper it says something else `while there are ants moving`. – example May 26 '14 at 18:30
  • Can you please tell me what the author meant by that? – Vpp Man May 26 '14 at 18:33
  • @VppMan repeat until all ants have reached the goal - or some other criterion is fulfilled like "1000 steps have passed" or "90% of all ants have reached the goal" – example May 26 '14 at 18:36
  • That's what I was trying to do with the outer loop. Looks like I have messed up the ideas that I got after reading the algorithm. – Vpp Man May 26 '14 at 18:38
  • Am really sorry to ask this, but could you be able to provide a little more easy to understand pseudocode of the algorithm? I would be very gladful and I will double the bounty(EDIT: Not sure how to edit the bounty!). – Vpp Man May 26 '14 at 18:41
  • @VppMan I have posted my interpretation of the goal seeking pseudocode. – example May 26 '14 at 20:20