Improved ant colony optimization for robot navigation paper

Question

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:

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

Answer 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.

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....