## 3 The Proposed Method
### Generation of the First Constrained Polygonal Space
#### 3.3.6 Ratio of the Connected Obstacles  
In some cases, some obstacles exist that are not directly penetrated with \(\overline{l_{0}}\), but they have connections with the pertinent obstacles (e.g., obstacles directly crossed with \(\overline{l_{0}}\)). These obstacles can escalate the time of path computation and yield unnecessary turns in the path. Hence, while analyzing the CPS complexity, it is paramount to take into account the connected obstacles' effect along with other five complexity parameters. The ratio of the connected obstacles can be found by counting the connected obstacles in the CPS divided by the obstacles' count in the \(S_{1}^{3}\). The count of connected obstacles can be determined using Equation (18):  
\[n^{\prime}=\sum_{j=1}^{n}(O_{j}\cup O_{CON}) \tag{18}\]  
where \(O_{j}\) is the pertinent obstacle, and \(O_{CON}\) denotes the connected obstacle with \(O_{j}\) (e.g., pertinent obstacles). The overall ratio of the connected obstacles (\(r_{co}\)) can be computed using Equation (19):  
\[r_{co}=\frac{n^{\prime}}{n} \tag{19}\]  
where \(n^{\prime}\) represents connected obstacles' strength, and \(n\) shows the number of obstacles in \(E\).  
When all six complexity parameters' values have been calculated, the total complexity \(\chi\) of the \(S_{1}^{3}\) can be quantified using Equation (20):  
\[\chi(S_{1}^{3})=w_{1}\times(1-r_{f})+w_{2}\times C_{p}+w_{3}\times C_{AO}+w_{4 }\times\Pi_{o}+w_{5}\times T_{o}+w_{6}\times r_{co} \tag{20}\]  
In Equation (20), \(1-r_{f}\) denotes the ratio of spaces occupied by obstacles, \(C_{p}\) denotes the deviation in path length from an optimal path, \(C_{AO}\) means the complexity of options while avoiding obstacles, \(\Pi_{o}\) is the occupancy of the obstacles at the distinct region of the CPS, \(T_{o}\) denotes the tendency of obstacles in the CPS in relation to a full map, and \(r_{co}\) denotes the ratio of connected obstacles. The drawing of all six complexity parameters described in prior subsections (e.g., Sections 3.3.1-3.3.6) is given in Figure 5.  
For calculation simplicity, we used complexity parameters values in normalized form; therefore, the \(\chi(S_{1}^{3})\) ranges between 0 and 1. In Equation (20), \(w_{i}\), where \(i=1,2,3,4,5,6\) represents each complexity parameter's weight, and they fulfill two conditions, (i) \(w_{1}+w_{2}+w_{3}+w_{4}+w_{5}+w_{6}=1\), and (ii) \(w_{i}>0\). We adjust each parameter weight by taking into account the significance and influence of every parameter in the CPS complexity analysis. The probability \(\sigma\) of a path \(P\) to be found from the \(S_{1}^{3}\) with good quality is given as follows:  
\[\sigma(P)=\begin{cases}1,&\text{if }0<\chi(S_{1}^{3})<T.\\ 0,&\text{otherwise}.\end{cases} \tag{21}\]  
where \(\chi(S_{1}^{3})\) represents the complexity of the \(S_{1}^{3}\), and \(T\) denotes a threshold. If \(\sigma(P)=1\), no extension of space is required because \(S_{1}^{3}\) is appropriate for low-cost pathfinding. Meanwhile, if \(\sigma(P)=0\), then an additional space will be needed to find good quality paths. The threshold \(T\) value relies on numerous global factors of the \(W\), and local constraints (e.g., related to the UAV). In simulations, we set the threshold value to 0.7 to make a decision about the space expansion. We did substantial experiments to validate the \(T\) value using \(P\)'s length as a main criteria. However, \(T\)'s value can be tuned flexibly based on the UAV's workspace and resources.