## 3 The Proposed Method
### Extremely Sparse Waypoint Graph Generation from the Selected CPS  
Waypoint graph (WG) is one of the approaches for task modeling and pathfinding, respectively. The WG constructs an indirect and compact graph connecting \(s\) with \(t\) by catching the connectivity of the \(\zeta_{free}\) to form a multiple paths' network. However, generating a WG is very expensive in terms of computation. The overall time complexity of generating a WG with \(n\) nodes is \(O(n^{3})\). Many studies that have focused on lowering the complexity of the WG generation have been reported by joining adjacent obstacles, altering obstacles' shape, and ignoring small obstacles. More recent research [60] highlights that WG's time complexity in the 3D environments can be decreased to the \(O(n^{2})\) by only considering the obstacles crossed by the \(\overline{l_{o}}\). To expedite the time complexity reduction of the WG, this paper suggests a new concept of an ESVG construction method which does not compose a dense WG. This method forms an ESVG from the CPS like a roadmap with connectivity between \(s\) and \(t\) through intermediate nodes. An ESVG is a double-edge type graph \(G\) of reachable and mutually-visible locations, mathematically expressed as: \(G=\{X,Y\}\). To construct a \(G\) from the 3D CPS, two steps are generally applied: making a nodes' set \(X\) and generating an edge set \(Y\). The initial step is about creating nodes set \(X\). We utilized three vertices of obstacles, bottom, top, and mid to make an ESWG for the first time. Both bottom and top vertices' geometry values are known, and mid vertices can be found leveraging the midpoint formula on top and bottom axis values. Every obstacle has total eight vertices (e.g., four bottom and four top). An \(ith\) obstacle's vertices and their respective values can be expressed mathematically in a matrix as demonstrated in Equation (22). The height of bottom four vertices of each obstacles are transformed to the \(h_{min}\) and top vertices of the obstacles have the same height as of the CPS height (e.g., \(h\)). In below metrics, the value of \(z_{min}\) is zero but after adjustment becomes \(h_{min}=z_{min}\):  
\[O_{i}= \begin{bmatrix}x_{min}&y_{min}&z_{max};x_{min}&y_{min}&z_{min}\\ x_{min}&y_{max}&z_{max};x_{min}&y_{max}&z_{min}\\ x_{max}&y_{min}&z_{max};x_{max}&y_{min}&z_{min}\\ x_{max}&y_{max}&z_{max};x_{max}&y_{max}&z_{min}\end{bmatrix} = \begin{bmatrix}1131 &1632&241;1131&1632&23\\ 1131&1703&241;1131&1703&23\\ 1209&1632&241;1209&1632&23\\ 1209&1703&241;1209&1703&23\end{bmatrix}  \tag{22}\]  
For example, an \(O\) whose original \(z_{max}\) is greater than the CPS height, and the bottom and top vertices are fully known, the pair of mid-points' two side faces denoted with \(f_{1}\) and \(f_{2}\) can be determined using Equations (23) and (24), respectively:  
\[f_{1}=\{\frac{x_{max}+x_{min}}{2},y_{min},z_{min}\},\{\frac{x_{max}+x_{min}}{ 2},y_{max},z_{min}\} \tag{23}\]  
\[f_{2}=\{\frac{x_{max}+x_{min}}{2},y_{min},z_{max}\},\{\frac{x_{max}+x_{min}}{ 2},y_{max},z_{max}\} \tag{24}\]  
A similar procedure can be utilized to find the pair of vertices around all obstacles. After computing set \(X\) from the pertinent obstacles, we add both \(s\) and \(t\) in a set \(X\) and  
Figure 6: Overview of constrained polygonal space (\(\xi_{1}^{3}\)) and its expansion to the next level (\(\xi_{2}^{3}\)). generate set \(Y\) of edges through two novel strategies and visibility-checks. Any two nodes \(u\) and \(v\) in \(X\) are inter-visible if a \(\overline{uv}\) segment of line connecting them is collision free. A function named-line-of-sight (LOS) determines the visible segments among pairs of nodes through visibility analysis. The time complexity of this mechanism heavily relies on the function of LOS checking, and number of nodes. Meanwhile, in our work, we incorporate two additional strategies of far-reachability (FR) and direction-guidance (DG), thereby time complexity is significantly reduced.