# Area Division Using Affinity Propagation for Multi-Robot Coverage Path Planning
## 4 The Proposed Algorithm
### Calculating Normalized Distance  
In this process, each cell within the initial environment is mapped onto a data point in a two-dimensional coordinate system. To discern the relationship between data points, we define a similarity function. In many standard applications of AP, similarity is gauged by the negative of Euclidean distance. This inversely proportional relationship implies a smaller similarity for larger absolute distances between data points.  
Figure 3: The initial environment (**a**) consists of obstacles (black cells), cells of type grass (green cells), and cells of type asphalt (gray cells). In order to divide the environment into multiple sub-areas, we first have to convert the environment into a set of data points. (**b**) depicts the data points in a X, Y Cartesian coordinate system.  
Figure 2: The initialization step prepares the data, converts the grid to a set of data points, and calculates the similarity matrix \(S\). Then, the responsibility matrix \(R\) is updated. The responsibility matrix reflects how well suited a data point is to serve as the exemplar for the other data points. Next, the Availability matrix is updated. This matrix reflects how suitable an exemplar is for each data point to serve as its exemplar. Finally, the algorithm iterates until the maximum number of iterations set, or until there are no changes from the last iteration.  
However, the application of Euclidean distance to our context of CPP within a two-dimensional grid, where we aim to preserve each cluster's continuity and its cell's 4-neighbor relationship, is not fitting. This metric fails to account for obstacles that may disrupt the path between two locations. This discrepancy between Euclidean distances and actual traversable distances can lead to significant errors, with the disparity being exacerbated by the presence of numerous obstacles.  
Understanding the inherent constraints of the traditional approach, we adapted our similarity function to include a more tailored and nuanced model (Algorithm 1).  
```
1. Input: Binary matrix \(A\) with dimensions \(X\) by \(Y\), starting point \((x_{1},y_{1})\), and target point \((x_{2},y_{2})\)
2. Output: minimum distance \(D\) between the starting and target points
3. Function 4_neighbor_actual_distance\((A,\ x_{1},y_{1},\ x_{2},\ y_{2})\):
4. Step 1: Initialize a distance matrix \(D\) with dimensions \(X\) by \(Y\), set all elements to infinity
5. Step 2: Initialize a queue \(Q\)
6. Step 3: Set \(D\)\([x_{1},y_{1}]=0\) and add \((x_{1},y_{1})\) to \(Q\)
7. Step 4: While \(Q\) is not empty:
8. Step 4.1: Dequeue a point \((x,y)\) from \(Q\)
9. Step 4.2: Loop through each of its four neighbors \((x_{n},\ y_{n})\) in the environment \(A\):
10. Step 4.2: If \((x_{n},\ y_{n})\) is an obstacle \((A[x_{n},\ y_{n}]=0)\), skip this neighbor
11. Step 4.2: If \(D[x_{n},\ y_{n}]>D[x,\ y]+1\):
12. Step 4.2.2: Update \(D[x_{n},\ y_{n}]=D[x,\ y]+1\)
13. Step 4.2.2: Add \((x_{n},\ y_{n})\) to \(Q\)
14. Step 5: Return \(D[x_{2},\ y_{2}]\) as the minimum distance \(D\) between the starting and target points
15. End Function
```  
**Algorithm 1**Calculating the normalized 4-neighbor distance between two points  
Our novel algorithm not only calculates the minimum 4-neighbor distance between cells, similar to a BFS approach, but also takes into account the type of floor and elevation of each cell, thereby capturing crucial information about the landscape's unique characteristics. It thereby ensures a more accurate and practical representation of the environment's traversability. Incorporating these parameters directly into the similarity function provides a more realistic framework for area division in 2D grid environments. This ultimately leads to enhanced efficiency and effectiveness in our CPP solutions, as it ensures more prudent and strategic allocation of sub-areas to robots, factoring in complex grid conditions that could impact their performance.