# Area Division Using Affinity Propagation for Multi-Robot Coverage Path Planning
## 2 Literature Review  
This section will delve into research endeavors in the literature that confront the multi-robot coverage path planning problem, particularly emphasizing area division and allocation. The objective of this section is to furnish a comprehensive review of extant algorithms and methodologies employed to mitigate the problem of multi-robot coverage. An analysis, comparison, and critical evaluation of related works were conducted to highlight their respective merits and demerits, thereby establishing a foundation for assessing the scientific contribution and novelty of the model proposed in this paper and identifying lacunae in the prevailing state-of-the-art. A widely recognized offline multi-robot CPP algorithm is the one proposed by [PERSON] et al. [21] using the MSTC\({}^{*}\) framework. This algorithm primarily aims to generate coverage paths for multiple robots while considering realistic physical constraints such as obstacles and communication paths among robots. The MST technique, employed to divide the target environment into smaller sub-regions, forms the backbone of the algorithm. Robots are then allocated to these sub-areas according to their capabilities and workload requirements. This algorithm possesses the advantage of addressing physical constraints, a pivotal aspect in real-world scenarios where robots need to maneuver through complex and dynamic environments. However, the algorithm does not consider environmental uncertainties, leading to sub-optimal performance in volatile and dynamic situations. Further, it predetermines the number of robots, thereby deciding the number of sub-areas. It is notable that [PERSON] et al. 's problem formulation aligns with the problem formulated in this paper in terms of area division and allocation, although the specific problem details the authors address are distinct. Another noteworthy offline multi-robot CPP algorithm is the one developed by [PERSON] et al. [24] for autonomous radiation mapping using a mobile robot. The primary objective of this algorithm is to create coverage paths that a single robot can traverse to conduct radiation mapping in a designated area. The method draws from a genetic algorithm, utilized to generate a multitude of potential coverage paths, and, subsequently, the optimal path is selected based on criteria such as coverage efficiency and path length. The flexibility of this algorithm lies in its adaptability; it can be modified to cater to varying radiation mapping scenarios. Moreover, the algorithm's computational efficiency makes it suitable for extensive application. However, it uses the K-means clustering technique to partition the overall space into smaller sub-spaces, implying that the algorithm necessitates a completely arbitrary selection of the number of robots. The DARP algorithm [18] represents a notable approach in the domain of multi-robot coverage path planning. It offers a systematic solution by dividing the total environment into distinct sub-areas, each allocated to a specific robot. The primary objective of DARP is to minimize the total coverage time, accomplished by intelligently dividing the environment based on its characteristics and the robotic fleet's capabilities. However, the algorithm makes predetermined assumptions about the number of robots and their initial positions, leading to potential limitations in more complex environments. An interesting approach was proposed by [PERSON] et al. [19], who suggested a multi-robot CPP algorithm based on the DARP algorithm. The authors sought to tackle the problem of weight allocation for multi-robot coverage using a weighted approach. The algorithm employs a grid-based representation of the environment and segregates the environment into a collection of cells necessitating coverage. The robots are assigned weights and the DARP algorithm is utilized to distribute these weights among the robots and determine their coverage paths.