Ant movement based on pheromone

[AlhaririAnas]

I have thought about the process of how ants decide their next movment based on the pheromones left behind:

Imagine an ant its coordinates (x, y). The ant decides where to go next based on the pheromone levels, around it. The ant can only move a certain number of steps (Ant.step_size) at a time .

Example 1 – Step Size 1: Let's say the ant is at (4, 6). With a step size of 1, it looks at the pheromone levels at nearby spots: (3, 5), (3, 6), (3, 7), (4, 5), (4, 7), (5, 5), (5, 6), and (5, 7). It chooses the spot with the strongest (or weakest, depending on the goal) pheromone level.

Example 2 – Step Size 2: If the ant starts at (4, 6) but can move 2 steps, it checks pheromone levels at spots further away: (2, 4), (2, 6), (2, 8), (4, 4), (4, 8), (6, 4), (6, 6), and (6, 8). It again picks the spot with the strongest (or weakest) pheromone level.

After finding the best spot based on pheromones, an angle α between the ant's current position and its intended destination should be calculated.. This angle helps decide which way the ant should move. For example, if the best spot is at (6, 7), the angle between the ant's current spot (4, 6) and (6, 7) is calculated, and the ant moves in that direction. Ant.move(angle_offset = α)

PS: These are initial thoughts on how this process works. I welcome comments or suggestions for improvement.

[tis22]

For example, if the best spot is at (6, 7), the angle between the ant's current spot (4, 6) and (6, 7) is calculated, and the ant moves in that direction. Ant.move(angle_offset = α)

Can you please explain more detailed which angle should be calculated exactly? (I guess you probably mean in a right-angled triangle)

If the ant starts at (4, 6) but can move 2 steps, it checks pheromone levels at spots further away: (2, 4), (2, 6), (2, 8), (4, 4), (4, 8), (6, 4), (6, 6), and (6, 8).

Moreover in your Example 2 you did not mention the spot (6,7). It's important to know, if we only consider coordinates on the horizontal, vertical and diagonal lines - I guess this is a better approch- or all points after a step size (this would be the outline of a square then).

Please include a picture / drawn diagram! 😄

Examples of the ideas mentioned:

[AlhaririAnas]

For example, if the best spot is at (6, 7), the angle between the ant's current spot (4, 6) and (6, 7) is calculated, and the ant moves in that direction. Ant.move(angle_offset = α)

Oops… I meant of course any index/spot from the ones I listed or from the ones whose pheromone levels were checked. This was a typing error, I meant (6, 4).

Regarding the calculation of the angle. I think it should not be calculated between two vectors as i mentioned, but only from the new position vector, which points in the direction of the highest pheromone level in the vicinity of an ant. See video:

https://github.com/heyitsalina/ant_search_algorithm/assets/147917604/037b0beb-e5ef-43fc-86cd-cd7c9b87aa96

@tis22 Today we can talk more about it at the meeting..

[tis22]

So the angle can be considered as from the origin to the new position - not from the current ant coordinates to the new position?

[tis22]

In our todays meeting we decided that we need a mapping-method to map the current coordinates of the ant to the associated position in the pheromones-array (see #87).

the horizontal, vertical and diagonal lines - I guess this is a better approch-

We will use that approch.
For the search of the strongest or weakest (depending on the goal) pheromones a new method find_pheromone_target is needed. This method examines which value in the array is the strongest or weakest in a range of a given step size. If all values within this step size are of one value (f.e. 0 or 1 or -1) a random direction will be picked. In the next epoch the find_pheromone_target-method will examine the pheromones within the stepsize again and look for a max or min value / decide for a random direction again.

After the direction array-element is found, the direction will be updated. Therefor an angle is calculated by the array-indices(?) of the element with the min/max-value (see video above).

Question @AlhaririAnas:

• Don't I need the mapped coordinates for this calculation?
• If I use the coordinates will the ant-movement headed to the center or the top left corner? (maybe if f.e. for the x-axis the mapping calculated an width of 3 the center must be 1.5) - I guess the center would be the best idea.
  The red dots are the two possible new positions of the ant after the movement:

After all the angle is returned to the ant.move-method to do the movement.

[AlhaririAnas]

@tis22:

Don't I need the mapped coordinates for this calculation?

No, we only need the mapped coordinates to determine where the ant is located, i.e. which pheromone index (cell) it belongs to.

---

If I use the coordinates will the ant-movement headed to the center or the top left corner? (maybe if f.e. for the x-axis the mapping calculated an width of 3 the center must be 1.5) - I guess the center would be the best idea.

The pheromone index should correspond to the center position, that makes the implementation easier and more understandable. I agree with you, therefore.

---

If anything is still unclear, please let me know.

[tis22]

If the code does the calculation for the angle by using the indices of the pheromones-array this would not be the center, as far as I can tell. I guess this would be the top left corner then.

If we want to use the center I need to know how the mapping was or is performed:

(maybe if f.e. for the x-axis the mapping calculated an width of 3 the center must be 1.5)

Because of this I think I do need the mapping informations.

[tis22]

Do we really want/need a step_size > 1?

Until now we have not discussed this in the meeting. Since we update the peromones every epoch it could be useful that the ants can move only on step at each epoch also.

I've got a solution for step_size > 1 but it makes the code more complicated and errors could occur easier.

[AlhaririAnas]

@tis22

The step_size is now implemented in our code, and it is being used. I don't think we can do without it, so the step_size should not be hardcoded to always be 1.

[tis22]

Please answer the previously written comment.

[AlhaririAnas]

Here is a calculation for the center of the pheromone spot with the highest pheromone level:

I hope this could help you further.

[AlhaririAnas]

Do we really want/need a step_size > 1?

Until now we have not discussed this in the meeting. Since we update the peromones every epoch it could be useful that the ants can move only on step at each epoch also.

I've got a solution for step_size > 1 but it makes the code more complicated and errors could occur easier.

I now have a better understanding of what you mean. I suggest we initially assume that the step size is 1. This means we should only consider and compare the immediate surrounding pheromone spots. It's possible that we might not need to take the step size into account at all. I will think about it and leave a comment once it becomes clearer to me

[tis22]

I made a commit of my current working state, please refer to it (39ed330). The step_size is already implemented and works now.

The part highlighted in blue: These indices will be given to the new find_pheromone_target-method.

The part highlighted in yellow: These indices will be determined by the find_pheromone_target-method. The method returns – as you intended – the arctan, not the target-indices.

The part circled in red: This has to be part of the mapping-method OR the return of the find_pheromone_target-method has to be changed to the (not mapped) indices of the target-spot.

This is what I already questioned you above and in Issue_87.

[tis22]

Furthermore:

The calculation of the angle is implemented as you suggested.
Following problems occour:

Example 1:

F.e. assume this array (note the 40):

pheromones = np.array([[ 1, 40,  3,  4,  5],
                       [11, 12, 13, 14, 15],
                       [16, 17, 18, 19, 20],
                       [21, 22, 23, 24, 25],
                       [26, 27, 28, 29, 30]])

ant_position = (0, 0)
pheromone_level = 1
step_size = 1

The method found that the spot with coordinates (0, 1) has the highest pheromone-concentration with a value of 40.

Calculating the arctan: $\tan^{-1}(\frac{0}{1}) = 0.0° $

This value will be given to the ant.move-method. There it is implemented if the angle_offset = 0 the moving-direction of the ant will be determined randomly.

==> This makes no sense because the ant should move to the position with the highest pheromone-level and not randomly.

Example 2:

F.e. assume this array (note the 40):

pheromones = np.array([[ 1,  2,  3,  4,  5],
                       [11, 12, 13, 14, 15],
                       [16, 17, 18, 19, 20],
                       [21, 22, 23, 24, 25],
                       [40, 27, 28, 29, 30]])

ant_position = (0, 0)
pheromone_level = 1
step_size = 1

In this case the method found that the spot with coordinates (0, 4) has the highest pheromone-concentration with a value of 40.

Calculating the arctan: $\tan^{-1}(\frac{4}{0}) = ERROR $

The angle can not be determined because you cannot divide by 0.

==> This makes no sense because the ant should move to the position with the highest pheromone-level. Like this it is not possible.

[tis22]

@AlhaririAnas Refer to the comments above.

Please delve deeper into the problems with your original idea. It's best if you also understand my commit.

[AlhaririAnas]

Regarding my approach, it may not necessarily be correct, and there's a chance I might have made mistakes. That's why I mentioned: 'PS: These are initial thoughts on how this process works. I welcome comments or suggestions for improvement.' So, if you disagree with my approach, feel free to think about and apply a different method. The most important thing is to accomplish the task.

I carefully reviewed your code with the commit (39ed330) and had difficulties understanding everything. It's possible that the code is too complex for me.

I'm trying here once again to articulate what needs to be done with this issue and request a recoding.

Objective: Develop a method named find_pheromone_target_idx in the Pheromone class. This method aims to identify the index of the strongest or weakest pheromone in the immediate vicinity of an ant, depending on the pheromone's state.

Parameters:

1. idx_ant_pos: The index of the current position of the ant in pheromone_array.
2. pheromone_status: The state of the pheromone, indicating whether to search for the highest or lowest value.

Functionality:

• The method should scan the neighboring cells around the ant's current position.
• It reads the pheromone value of each cell and decides, based on pheromone_status, whether to search for the highest or lowest value.
• The method returns the index (x, y) of the cell with the targeted pheromone value. If all surrounding cells have the same pheromone value, return None.

Pseudocode:

Method find_pheromone_target_idx(idx_ant_pos, pheromone_status):
Set target_pheromone_value to 0
Set idx_target_pheromone_value to (0, 0)

Get n_rows and n_cols from the shape of pheromone_array
Initialize unique_pheromone_values as an empty set

Set depth to 1
If pheromone_status is -1, set depth to 0

For i from idx_ant_pos[0] - 1 to idx_ant_pos[0] + 2:
    For j from idx_ant_pos[1] - 1 to idx_ant_pos[1] + 2:
        If i is within 0 and n_rows and j is within 0 and n_cols and (i, j) is not idx_ant_pos:
            Add pheromone_array[depth, i, j] to unique_pheromone_values

            If pheromone_status is 1 and pheromone_array[depth, i, j] > target_pheromone_value:
                Update target_pheromone_value
                Update idx_target_pheromone_value

            Else if pheromone_status is -1 and pheromone_array[depth, i, j] < target_pheromone_value:
                Update target_pheromone_value
                Update idx_target_pheromone_value

If unique_pheromone_values has only one value, return None

Return idx_target_pheromone_value

Step size and the calculation of the angle can be ignored for now!

[tis22]

As stated above my commit already does what was asked for in this issue.

I haven't come up with a new idea yet, which is why I asked you for your other ideas and wanted to discuss them with you. I think you again don't understand the problems I described.

I'll repeat my points here so that you can understand them better:

• Step size is fully implemented.

• Function to search the field with the highest level of pheromones is implemented.

• If all fields (within the step size) have the same value (f.e. all have pheromone-level 20; or all have pheromone-level 0) the return is movement_angle = 0 currently, as this leads to a random selection of the field/new position in the ant.move-method.

• If only two fields (within the step size) have the same value, the choice between the two will be random.

• The angle to the field with the highest pheromone-level movement_angle is returned in all cases at the moment.

Since this approach is apparently (somehow) faulty, I pointed this out to you and said that we can change the return to the index of the field with the highest pheromone level, as you also mentioned in your last comment.

Note: The return is only the index of the field in the pheromone array. In order for the ant to walk to the center of the field, this coordinates must then be mapped to the center using the mapping method. This (direction of the mapping) still needs to be added to the mapping method.

Summary:

In summary, you only have to tell me whether I should change the current implementation so that the function returns the indices of the field with the highest pheromone-level.

As I said, you will (very likely) have to change your mapping method then so that the ants move to the middle of the field if given this coordinates. This mapping should not be done in the find_pheromone_target-method as it depends on the mapping of the mapping-method.

[AlhaririAnas]

Yes, please modify the implementation so that the method returns the relevant indices.

With these indices, a new method I've coded, called "calculate_pheromone_target_pos()", will be integrated into the simulation. It will compute and return the central position of the field with the highest or lowest pheromone level.

For the time being, disregard the use of Step_size. The reason is that when pheromone fields cover a large area, such as a board size of 480x720 with a grid_shape of 50x50, an ant can take multiple steps within a single field. Hence, employing Step_size in this scenario does not provide an advantage.

[heyitsalina]

DEADLINE FOR THIS ISSUE: 14.02.