# Area Division Using Affinity Propagation for Multi-Robot Coverage Path Planning
## 5 Experimental Results  
In this section, we present the findings obtained from our in-depth analysis of the proposed algorithm. The experimental results validate the efficiency and adaptability of our algorithm in effectively decomposing the environment into suitable sub-areas. The  
Figure 5: The initial environment as depicted in (**a**) contains two layer types (denoted by green and gray cells). The output of the algorithm in (**b**) shows the two clusters (blue and yellow), as they were generated by the algorithm. It is worth mentioning that different values of the importance value \(T_{w}\) may result in slightly different clusters. evaluation metrics employed primarily centered on the criteria of computational time and the quality of the generated clusters. In terms of comparison with existing algorithms, it is important to highlight that our proposed AP-based algorithm addresses a unique problem in the field of multi-robot CPP. In the literature, many algorithms attempt to solve the issue of dividing an initial area into multiple sub-areas for each robot. However, the identical problem that our algorithm solves, without arbitrarily pre-determining the number of robots and their initial positions, is lacking in the current literature. Nevertheless, we embarked on an indirect comparative analysis, contrasting our algorithm's performance with traditional algorithms for area division in CPP, which rely on pre-specified robot counts and locations. The comparative study primarily emphasized the improvements in efficiency, flexibility, and adaptability introduced by the proposed algorithm. Despite the inherent differences in the problem contexts, the comparative analysis provided a clear demonstration of the strides made by the AP-based approach, particularly in situations where the initial robot positions are in close proximity. The conducted simulations predominantly operated in two meticulously constructed environments of distinct sizes, each featuring distinct characteristics. Both environments were generated using a pseudo-random process, offering a unique combination of accessible areas and obstacles along with varying environmental types, ensuring the robustness of the simulated scenarios. The smaller 24 \(\times\) 24 environment served as an essential proving ground for our proposed algorithm, presenting a grid with a variety of unique parameters and diverse characteristics. The total area consisted of 576 cells, with approximately 80% of the grid being accessible and approximately 20% assigned as obstacles. These obstacles were evenly scattered throughout the grid to simulate potential hindrances that robots might encounter in real-world scenarios. Beyond mere accessibility, cells in the environment were characterized by two distinct terrain types--grass and asphalt. The grass cells accounted for roughly 60% of the accessible area, while the asphalt cells constituted the remaining 40%. This bifurcation of terrain types aimed to emulate real-world environments where robots might encounter varied terrains requiring different path planning strategies and navigation capabilities. To augment the realism of the simulation, cells were assigned varying elevation levels. The elevations ranged from 0 to 10 units, with a standard deviation of three units to ensure a substantial variation in elevation across the grid. An elevation weight factor of 0.1 was applied to indicate the importance of elevation. Similarly, the type of terrain also had an associated weight factor to indicate the importance of terrain type. Subsequently, a second, larger, and more complex environment was introduced for a more in-depth simulation. The dimensions of this environment are 100 \(\times\) 100. The rest of the parameters were the same as those of the previous smaller environment. Due to its substantial size, detailed visualization was rendered impractical. Nevertheless, we present empirical data and statistics to illustrate the algorithm's performance.