## 3 The Proposed Method
### Generation of the First Constrained Polygonal Space
Then, we draw a bottom boundary, \(\Omega_{b}\), around the bottom vertices of the pertinent obstacles, and a top boundary, \(\Omega_{t}\), from minimal height \(h\) with path guarantees  
Figure 3: Results of sketching a straight line (\(\overline{l_{o}}\)) between \(s\) and \(t\) locations. keeping \(s\) and \(t\) as two endpoints. This forms a 3D constrained space where the shape can resemble a 3D polygon, and we call this constrained region the CPS, represented with \(S_{1}^{3}\). This CPS converts the more difficult problem of UAV pathfinding into the relatively easier problem of pathfinding for a 3D point. A visual overview of \(S_{1}^{3}\) is demonstrated in Figure 4. The \(S_{1}^{3}\) can be simply defined as full map \(W\) partitioned into a small space/region where the outline is the same as a 3D polygon, with \(s\) and \(t\) as two endpoints. It is obtained by drawing a boundary around the outermost vertices of the pertinent obstacles in such a way that a path can be found from it regardless of its quality. The process of transforming a full map into \(S_{1}^{3}\) is given in Figure 4a-c. In Figure 4a, environment map \(W\) is shown, which will be converted into \(S_{1}^{3}\). Figure 4b shows the \(\overline{l_{o}}\) drawing, and identifies the corresponding pertinent obstacles (e.g., yellow obstacles) that were crossed by it; these obstacles will be used to subsequently generate \(S_{1}^{3}\). Figure 4c shows the outline of \(S_{1}^{3}\) in 2D form that is obtained by drawing a boundary around obstacles identified in Figure 4b as a consequence of \(\overline{l_{o}}\) penetration. The CPS can enclose the pertinent obstacles--just part of them or as a whole. In some cases, due to complex 3D environments, \(S_{1}^{3}\) can enclose obstacles that do not belong to set \(E\) but that are part of \(S_{1}^{3}\), either partially or completely, and we include such obstacles in \(E\) and utilize them in pathfinding. The essence of \(S_{1}^{3}\) is that it guarantees a flyable path between \(s\) and \(t\). However, \(S_{1}^{3}\) may or may not be an ideal choice for a good-quality path (e.g., optimal or quasi-optimal) due to several complexity parameters (as illustrated in Figure 1) about obstacles. By considering such potential complexity parameters and a probabilistic analysis of optimal paths, we conducted a CPS complexity analysis leveraging six complexity parameters (also known as complexity constraints), prevailing in \(S_{1}^{3}\) that relate to the obstacles' geometries, and a low-cost path tends to lie outside \(S_{1}^{3}\), in most cases, with a significantly higher probability. Figure 4: Overview of transforming a full 3D map \(W\) into a constrained polygonal space (\(S_{1}^{3}\)). Determining and Analyzing the Constrained Polygonal Space Complexity Using a Multicriteria-Based Method  
In order to check whether \(S_{1}^{3}\) is good enough for optimal/quasi-optimal pathfinding or not, we performed a multi-criteria-based complexity analysis of \(S_{1}^{3}\) using multiple complexity parameters before task modeling and pathfinding. We computed the complexity, \(\chi\), of \(S_{1}^{3}\) by leveraging detailed information regarding the obstacles' geometries. We employed six complexity parameters: the proportion of free spaces, the obstacle occupancy in distinct regions of the CPS, the complexity of obstacle-avoidance options, the proportion of connected obstacles, the length deviations from the optimal path, and obstacles' tendency in the CPS that hinders the solution quality. Through extensive simulations and analysis, it is found that there exists a very firm relationship between the complexity parameters of the CPS and path quality. The total \(\chi\) is the weighted sum of six parameters cited above. Brief overviews of those six complexity parameters, with their procedures and equations, are described below.