## 5 Free Space Extraction  
Obstacle region identification is of utmost importance for optimal trajectory planning in real time. In a cluttered environment, the way the trajectory planning problem formulated matters for fast reaction. Such trajectory planning approaches can be designed as QP mainly due to less computation power required for such tasks. Hence, forming obstacle-free regions in the form of convex has more advantages in terms of reducing the computation power, simplicity, and fast convergence. [PERSON] [74] attempted to define free space as a series of cubes between the start and goal pose. Thenceforth, OctoMap [81] was used for constructing the map surrounding the quadrotor, where regions with no obstacles are considered free spaces. After obtaining the free space information, obstacle constraints are enforced into (15) to generate optimal trajectory. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**Type**} & \multicolumn{4}{c}{**Velocity**} & \multicolumn{4}{c}{**Acceleration**} \\ \cline{2-9}  & **Mean** & **Std** & **Min** & **Max** & **Mean** & **Std** & **Min** & **Max** \\ \hline Poly-traj, d: 8. mc 2 & 0.0058 & 1.0154 & \(-\)1.4545 & 3.9179 & 0.0056 & 0.9051 & \(-\)2.835 & 3.6449 \\ \hline Poly-traj, d: 8. mc 6 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ \hline Poly-traj, d: 6, mc 4 & 0.006 & 1.0708 & \(-\)1.7716 & 3.7864 & 0.0043 & 0.9307 & \(-\)2.7987 & 3.6032 \\ \hline Poly-traj, d: 8. mc 4 & 0.0059 & 1.0299 & \(-\)1.4728 & 3.934 & 0.0053 & 0.9131 & \(-\)2.9157 & 3.5214 \\ \hline Poly-traj, d: 10, mc 4 & 0.0058 & 1.0057 & \(-\)1.4428 & 3.9213 & 0.0052 & 0.8918 & \(-\)2.7541 & 3.631 \\ \hline Minimum-snap, d: 8, mc 2 & 0.1258 & 1.2154 & \(-\)1.4345 & 3.1259 & 0.0676 & 0.1259 & \(-\)2.2874 & 3.3278 \\ \hline Minimum-snap, d: 8, mc: 6 & 0.0045 & 0.0094 & \(-\)0.07 & 0.019 & 0.09 & 0.0097 & \(-\)0.0098 & 0.0014 \\ \hline Minimum-snap, d: 6, mc 4 & 0.0689 & 1.0009 & \(-\)1.3416 & 3.2388 & 0.0012 & 0.4584 & \(-\)2.3189 & 3.2185 \\ \hline Minimum-snap, d: 8, mc 4 & 0.0015 & 1.0412 & \(-\)1.3215 & 3.7543 & 0.0075 & 0.8763 & \(-\)2.5487 & 3.3215 \\ \hline Minimum-snap, d: 10, mc 4 & 0.0036 & 1.0006 & \(-\)1.3428 & 3.7832 & 0.0099 & 0.4378 & \(-\)2.4548 & 3.4893 \\ \hline CHOMP; pd: 3 & 0.0068 & 0.6421 & \(-\)0.9522 & 1.7255 & 0.0045 & 0.3876 & \(-\)1.131 & 1.476 \\ \hline CHOMP; pd: 5 & 0.0065 & 0.644 & \(-\)0.9634 & 1.7161 & 0.0044 & 0.3909 & \(-\)1.1082 & 1.4418 \\ \hline CHOMP; pd: 7 & 0.0064 & 0.6443 & \(-\)0.966 & 1.7105 & 0.0043 & 0.3916 & \(-\)1.0951 & 1.4205 \\ \hline Type & \multicolumn{4}{c}{Jerk} & \multicolumn{4}{c}{Sapap} \\ \hline Poly-traj, d: 8, mc 2 & 0.007 & 1.2544 & \(-\)4.8056 & 3.9318 & \(-\)0.0151 & 2.3178 & \(-\)9.8029 & 6.9483 \\ \hline Poly-traj, d: 8, mc 6 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ \hline Poly-traj, d: 6, mc 4 & 0.0117 & 1.568 & \(-\)5.5746 & 5  
Let \(C=[c_{1}^{m},c_{2}^{m},\dots]\) be a set of consecutive grids within the OctoMap and corresponding free space regions be \(C_{free}=[c_{1}^{f},c_{2}^{f},\dots]\). Both \(c_{i}^{m}\) and \(c_{i}^{f}\) were defined as cubes, each of which is described by:  
\[c_{i}^{m}=[\underbrace{c_{i_{x_{0}}}^{m},c_{i_{y_{0}}}^{m},c_{i_{y_{0}}}^{m},c_{ i_{x_{1}}}^{m},c_{i_{y_{1}}}^{m},c_{i_{x_{1}}}^{m}}_{n_{i_{x}}^{m}}],\quad c_{i}^{f}=[c_{ i_{x_{0}}}^{f},c_{i_{y_{0}}}^{f},c_{i_{x_{1}}}^{f},c_{i_{y_{1}}}^{f},c_{i_{x_{1}}}^{f} ]. \tag{37}\]  
Once \(C_{free}\) was obtained, free space regions can be considered as a set of inequality constraints that can be added into the piece-wise-polynomials trajectory generation as \(l_{f}^{i}\leq\Gamma_{T}(t_{i})\leq u_{f}^{i}\), where \(i=1,\dots,m_{d}-1\) and \(\Gamma_{T}\) was defined in (13). In such a trajectory, additional boundary constraints should be introduced if the extrema of \(d\)th-order polynomial violates the boundary constraints corresponding to each axis, i.e., x, y, and z, in each segment [74] (Equation (10)).