## 4 Problem Statement
### Collaborative Target Detection Problem
#### 4.2.2 Single-Source Shortest Path Problem (SSSP)  
After the partitioning of the environment \(E\) into \(P_{E}^{k}\), the next step consists in finding the paths that join a set of targets \(T_{i}\) detected in \(E_{i}\) in a distributed way. Each drone UAV\({}_{i}\) calculates the shortest path to reach a target at the position \(p_{target}\) from its initial position \(p_{init}\in V_{i}\), as shown in Figure 7. It is an algorithmic optimization problem referred to as the Single-Source Shortest Path problem and is well known in operations research and graph theory [59]. It consists in finding an optimal or near-optimal path between two nodes of a directed graph. It is a multi-criteria optimization problem aiming at satisfying the reachability of the final point \(p_{target}\) while minimizing the costs (e.g., distance or time) of the path. There are three variants of the SSSP problem: (1) the dual-path problem, which consists of finding a set of paths leading to a target from several sources; (2) the all-pair problem, which consists in finding the optimal path between all pairs of points; and, finally, (3) the single-source problem, which consists in finding an optimal path from a source that joins all the targets \(T_{i}\) of a sub-environment \(E_{i}\). In our study, we focus on the latter type of problem. Suppose a drone UAV\({}_{i}\) assigned to the sub-environment \(E_{i}=(P_{i},L_{i},W)\) for an exploration mission that consists in finding a set of targets \(T_{i}\) such as the following:  
* \(p_{init}\in P_{i}\): the origin point or current position of the drone UAV\({}_{i}\). * \(p_{target}\in P_{i}\cap T_{i}\): the goal point or position of the target \(t_{i}\in T_{i}\). * \(p_{init}\
eq p_{target}\). * path: the path to reach \(p_{target}\) from \(p_{init}\). We consider the linear program by introducing a binary decision variable \(x_{s,d}\in\{0,1\}\). This variable indicates whether the weight \(w(p_{s},p_{d})\) associated with the line between \(p_{s}\) and \(p_{d}\) minimizes the path cost. It is equal to 1 if the weight minimizes the cost \(w(\mathit{path})\) of the path and 0 in the opposite case:  
Figure 6: Illustration of a bi-partition (\(k=2\)) of an environment for two UAVs with the three partitioning approaches. \[\min w(path)=\sum_{(p_{i},p_{d})\in L_{i}}w(p_{s},p_{d})\times x_{s,d} \tag{4}\]  
Thus, each UAV\({}_{i}\) will seek to determine the minimum weight lines that optimize and favor the progression towards the target \(p_{target}\) position from its initial position \(p_{init}\). This condition is defined as a flow conservation problem [60]; it stipulates that the sum of the flows into a given point must be equal to the sum of the flows out of that point \(p_{i}\), apart from the start \(p_{init}\) and end \(p_{target}\) points. The mathematical formulation of this condition is formulated as follows:  
\[\forall p_{i}\in P_{i}\backslash\{p_{init},p_{target}\},\ \ \ \sum_{(p_{i},p_{j})\in L _{i}}x_{i,j}=\sum_{(p_{j},p_{i})\in L_{i}}x_{j,i} \tag{5}\]  
For each UAV\({}_{i}\), the mathematical model of the problem of reaching the position \(p_{target}\) of a target \(t\in T_{i}\) in its environment \(E_{i}\) is described as follows:  
\[\left\{ \begin{aligned} &\underset{p_{i}\
eq p_{j}\in P_{1}}{ \text{minimize}}&\sum_{(p_{i},p_{j})\in L_{i}}w(p_{i},p_{j}) \times x_{i,j}\\ &\text{subject to:}&\sum_{(p_{i},p_{j})\in L_{i}}x_{i,j }=\sum_{(p_{j},p_{i})\in L_{i}}x_{j,i}\\ & x_{i,j}\in\{0,1\}\\ & p_{i},p_{j}\in P_{i}\backslash\{p_{init},p_{target}\}\end{aligned} \right. \tag{6}\]  
If we set \(d(p_{i})\) as the distance to reach the point \(p_{i}\) from the initial point \(p_{init}\) and if we set \(d(p_{target})=0\), then, for each point \(p_{i}\) to be explored by the UAV\({}_{i}\) in its environment \(E_{i}\), the resulting mathematical model will be written as follows:  
\[\left\{