# Area Division Using Affinity Propagation for Multi-Robot Coverage Path Planning
## 1 Introduction  
Over the past few decades, we have witnessed an exponential advancement in technology that has fundamentally reshaped the global landscape [1]. With a broad gamut ranging from telecommunications and computing to artificial intelligence and robotics, these technological breakthroughs have drastically altered the ways in which humans operate and perform tasks [1, 2, 3]. Once labor-intensive or monotonous tasks are now executed with unparalleled speed, precision, and efficiency, largely due to automation and the advent of intelligent systems. A predominant player in this transformational journey has been the field of robotics. Robots, once confined to the realms of science fiction, now pervade numerous sectors, such as manufacturing [4], healthcare [5], agriculture [6, 7, 8], and logistics [9], serving as invaluable tools for enhancing productivity and improving the quality of services. In disaster management, robots have been instrumental in executing search-and-rescue missions in environments too hazardous for human intervention [10, 11]. In agriculture, robotic systems are leveraged for tasks ranging from seeding to harvesting, contributing significantly to precision farming. However, as with any emergent technology, the rapid rise of robotics has posed a unique set of challenges, requiring innovative solutions. A prominent challenge in the domain of robotics is Coverage Path Planning (CPP). In essence, CPP is the process ofdeveloping a route or path that allows a robot to cover an entire operational area in an efficient manner [12; 13]. A vital aspect of numerous applications, CPP is integral to tasks such as field inspection in agriculture [14; 15; 16], where a robotic system needs to cover a farm field to assess crop health. The complexity of CPP intensifies when we move from single-robot systems to multi-robot systems. Multi-robot CPP involves devising paths for multiple robots to ensure comprehensive and efficient coverage of a larger or more complex area [17; 18; 19; 20; 21; 22; 23; 24; 25; 26]. A pressing issue in multi-robot CPP is the division of the operational area among the robots, a problem known as the 'area division problem'. For example, consider a team of drones deployed for large-scale environmental monitoring or a fleet of autonomous vehicles performing a search-and-rescue mission in a disaster-stricken area. The optimal allocation of specific regions to individual robots can drastically enhance the coverage efficiency and operational coordination, reducing redundancies and saving valuable time. Addressing the area division problem effectively is paramount for the successful deployment of multi-robot systems across a range of real-world applications. As such, it remains a vibrant area of research, inviting novel solutions and methodologies that can meet the evolving demands of modern robotic systems. Several researchers have proposed models to resolve the multi-robot CPP problem, yet they often encounter significant limitations. A prevalent limitation of multi-robot CPP algorithms lies in the arbitrary selection of the number of robots and their starting locations. Both these factors yield substantial influence over the efficacy of the algorithm. For example, an inadequate number of robots may yield incomplete coverage, resulting in overlooked regions. Conversely, deploying an excessive number of robots can render the task inefficient and unnecessarily complicated, thus elevating the cost and computational burden. Likewise, the robots' initial placement crucially impacts the effectiveness of the algorithm, dictating the distribution of robots and the thoroughness of area coverage. Another major constraint is the limited scalability of the algorithms, referring to the capability of an algorithm to perform optimally as the number of inputs or variables increases. In the context of multi-robot CPP, scalability pertains to the algorithm's ability to manage expansive environments and multiple robots cooperating to execute a task.