# Area Division Using Affinity Propagation for Multi-Robot Coverage Path Planning
## 3 Problem Definition  
The effective division of a given environment into distinct sub-areas for the deployment of multiple robots presents a challenging problem, particularly in the context of ensuring contiguous access within each sub-region. To lay a solid foundation for our investigation, we embarked on a mathematical formulation of this problem, succinctly capturing the essential aspects and constraints involved. This mathematical model serves as an unambiguous representation of the underlying problem, illuminating its core elements and thus guiding the development of algorithmic solutions.  
Our environment is described as a binary matrix representation, defining accessible areas and obstacles. We considered robots that are assigned to different sections of this environment, each section described as a'sub-area'. We also incorporated the distinct nature of the terrain, assigning different types to each cell in the environment. The fundamental goal was to find a valid division of the environment into sub-areas, each assigned to a unique robot, with the sub-areas satisfying a set of constraints related to accessibility and continuity. The mathematical model elucidated below presents a precise description of the problem, facilitating further discussion and solution design.  
Given:  
* An environment \(A\) of size \(X\times Y\) represented as a binary matrix, \(A=\left[a_{i,j}\right]\), where \(a_{i,j}\in\{0,1\}\) for all \(1\leq i\leq X\) and \(1\leq j\leq Y\). In the environment matrix \(A\), \(a_{i,j}=0\) signifies an obstacle, whereas \(a_{i,j}=1\) represents an accessible cell. By definition, robots can only traverse accessible cells.
* A set of robots \(R=\left\{r_{1},r_{2},\ldots,r_{n}\right\}\), where \(n\) is the number of robots.
* A matrix \(T=\left[t_{i,j}\right]\), where, that describes the type of each cell \(a_{i,j}\).
* A matrix \(E=\left[e_{i,j}\right]\), where, that describes the elevation level of each cell \(a_{i,j}\).
* An elevation weight value \(E_{W}\) which represents the elevation weight importance factor, and a floor type \(F_{W}\) which represents the floor type elevation weight importance factor.
* A matrix \(T_{w}=\left[w_{1},w_{2},\ldots,\,w_{n}\right]\) where \(w_{i}\) represents the weight assigned to the \(i\) th floor type. The number of values in \(T_{w}\) is equal to the number of different floor types. Based on this information, we seek:
* A set of sub-areas \(S=\left\{s_{1},s_{2},\ldots,s_{n}\right\}\), where each sub-area \(s_{i}\) is a contiguous partition of \(A\) assigned to robot \(r_{i}\). Formally, we define the following constraints:
* Each sub-area \(s_{i}\) maintains 4-neighbor continuity for all its accessible cells (Figure 1), i.e., for each pair of accessible cells \(c_{m_{1},n_{1}}\) and \(c_{m_{2},n_{2}}\) in \(s_{i}\), there exists a sequence of accessible cells \(c_{m_{k},n_{k}},k=1,\ldots,p\), such that \(c_{m_{1},n_{1}}=c_{m_{1},n_{1}},c_{m_{p},n_{p}}=c_{m_{2},n_{2}}\), and \(c_{m_{k},n_{k}}\) is a 4-neighbor of \(c_{m_{k+1},n_{k+1}}\) for all \(k=1,\ldots,p-1\). The 4-neighbor criterion specifies that connectivity between cells must be either horizontal or vertical--not diagonal. Thus, in essence, every cell in the sequence is horizontally or vertically adjacent to its successor, for all values of k ranging from 1 to \(p-1\).
* This condition ensures a continuity or chain of 4-neighbor connections between any two accessible cells within a given sub-area, thereby preserving the rule of 4-neighbor connectivity throughout the entire grid.
* The environment \(A\) is the union of all sub-areas \(S\), i.e., \(A=\mathrm{U}_{i=1}^{n}s_{i}\).
* The intersection of any two distinct sub-areas \(s_{i}\) and \(s_{j}\) for \(i\
eq j\) is empty, i.e., \(s_{i}\cap s_{j}=\varnothing\) for all \(i\
eq j\).
* The problem is to find a bijective function \(f:R\to S\) such that \(f(r_{i})=s_{i}\) for all \(1\leq i\leq n\), fulfilling the constraints mentioned above.