## 5 Free Space Extraction
Similar to the preceding approach, [PERSON] and [PERSON] [82] proposed a sequence of spheres to represent free space from the initial position to the final position. To construct the environment, a map was not built; instead, they bypassed map building by constructing a KD-tree-based placeholder [83] to store raw point cloud for the LiDAR. Afterwards, a relative map to the current pose of the MAV was retrieved using nearest neighbour search; RRG [84] combined with A* was used to find a flight corridor or intermediate waypoints. Such intermediate waypoints were connected by overlapping spheres. IRIS [40] is one of the first successful ideas in which obstacle-free spaces are extracted using a convex optimization technique. In this proposed approach, initially, it is required to provide a seeking point and an area with a boundary box where an obstacle-free region is to be searched. Seeking point is defined as a unit ball: \(\varepsilon(C,\mathbf{p}_{0})=\{\mathbf{p}=C\bar{\mathbf{p}}+\mathbf{p}_{0} \mid\|\bar{\mathbf{p}}\|_{2}\leq 1\}\), where \(\mathbf{p}_{0}\) is the center point. The linear constraints, which separate the boundary box into obstacle-free and obstacle-rich regions, are defined as a set of hyper-planes: \(P=\{\mathbf{p}\mid A\mathbf{p}\leq b\}\). Subsequently, finding the optimal representation of \(\varepsilon(C,\mathbf{p}_{0})\) and \(P\) with respect to given obstacles, \(l_{j},j=1,\dots,N\) is solved as an iterative process (38):  
\[ \begin{array}{rl}\min_{C,\mathbf{p}_{0},A,\mathbf{b}}&-log(detC)\\ \text{s.t.}&A_{j}^{T}\mathbf{p}_{k}\geq\mathbf{b}_{j}\quad\forall\mathbf{p}_{ k}\in\mathbf{\iota}_{j},\quad j=1,\dots,N\\ &\sup_{\|\bar{\mathbf{p}}\|}\,A_{i}^{T}(C\bar{\mathbf{p}}+\mathbf{p}_{0})\leq \mathbf{b}_{i}\quad\forall i=1,\dots,N,\end{array}  \tag{38}\]  
where \(A_{i}\) and \(\mathbf{b}_{i}\) correspond to \(i\)th row of \(A\) and \(\mathbf{b}\). The first constraint, i.e., \(A_{j}^{T}\mathbf{p}_{k}\geq\mathbf{b}_{j}\), is imposed to move the obstacle into one side of the plane, \(A_{j}^{T}\mathbf{p}=\mathbf{b}_{j}\), whereas the second constraint, i.e., \(\sup_{\|\bar{\mathbf{p}}\|}\,A_{i}^{T}(C\bar{\mathbf{p}}+\mathbf{p}_{0})\leq \mathbf{b}_{i}\), ensures the ellipsoid lies on the other side of the plane. The researchers proposed to solve the (38) as a two-step process: searching, first, for proper constraints (i.e., \(A_{i}\) and \(\mathbf{b}_{i}\)), and then the maximum volume that satisfies ellipsoid, ensuring preceding constraints. In other words, they attempted to find hyperplanes that separate obstacle regions and free regions. Conceptually, hyperplane separation is completed by finding planes that intersect with obstacle boundaries. Afterwards, the ellipsoid is uniformly expanded until it intersects with obstacle boundaries. Let \(\alpha\) be the scaling factor which defines the expansion. Let \(\varepsilon_{\alpha}=\{C\bar{\mathbf{p}}+\mathbf{p}_{0}\mid\|\bar{\mathbf{p}}\| _{2}\leq\alpha\}\) for \(\alpha\geq 1\) be the expanded ellipsoid. Hence, the optimal \(\alpha^{*}\) can be determined by:  
\[ \begin{array}{rl}\alpha^{*}=\underset{\alpha}{arg\,min}&\\ \text{s.t.}&\varepsilon_{\alpha}\cap l_{j}\
eq\varnothing.\end{array}  \tag{39}\]  
After finding \(\alpha^{*}\), it is possible to define the optimal inscribed ellipsoid (\(\varepsilon^{*}\)), which is the obstacle-free region [40] (Section 3.3). [PERSON] et al. [32] proposed a new approach, quite different from the aforementioned IRIS, for extracting obstacle-free regions as a convex set SFC (Figure 7). SFC searches a set of overlapping polyhedra from the start pose to the goal pose. To obtain intermediate obstacle-free positions, the researchers utilized a graph search technique, namely JPS [55]. The main reason for selecting JPS over sampling-based algorithms (e.g., RRT* and PRM) or search-based techniques such as A* or Dijkstra is due to the nature of JPS; it uses a uniform-cost grid map with uniform voxels. In general, sampling-based techniques are not deterministic though probabilistically complete.