Unmanned Aerial Vehicles (UAVs) have emerged as a versatile technology with significant potential for various applications. Though effective, with further development, UAVs are envisioned to increase their usage particularly in environments that are hazardous or challenging to penetrate for humans, military personnel, and ground robotic systems. The operation of UAVs within confined environments, such as underground installations, mines, and geometrically complex urban spaces (e.g., collapsed buildings) is of specific interest. Such spaces present unique challenges in terms of path planning, exploration/reconnaissance, navigation, and mobility. The ability to navigate within these and other confined spaces efficiently is crucial for applications such as mining ^[1][2][1,2], Urban Search and Rescue (USAR) [3], and military applications ^[4][5][6][4,5,6]. Figure 1 exemplifies applications where such UAV abilities are required in underground mines and sewers, where data collection, repair, and maintenance, for example, are challenging, hazardous, and time-consuming, putting human workers at risk. The complex nature of these environments, characterized by obstacles and openings with non-convex geometrical shapes, and limited space necessitate the development of specialized technologies to ensure safe, collision-free flight.

In recent years, notable advancements in UAV data processing and flight abilities control, as well as future research directions [10], have been achieved in addressing the multifaceted challenges associated with UAV operations within confined environments. Of particular importance is the generation of 3D flight corridors, which establish secure pathways for UAVs to navigate within constrained spaces ^{[11][12][13][14][15]}[11,12,13,14,15]. However, current methodologies cannot be easily applied in confined chaotic spaces where the flight corridor would require the embodiment of a somewhat complex topological framework that incorporates various environmental constraints. This process needs to adequately account for the potentially intricate geometry of the environment and potentially moving obstacles present in it. Consequently, a 3D flight corridor is regarded as a 3D tunnel characterized by varying cross-section profiles. In confined spaces, flight corridors tend to be relatively compact in volume, underscoring the significance of generating a sufficiently voluminous flight corridor while considering the available flight maneuvers that the UAV of interest possesses. An advanced flight corridor generation (10.3390/robotics12050134)  mechanism is proposed that is capable of generating effective geometrically complex tunnels based on the perceived environment, a target goal, and the geometrical physical characteristics of the UAV.

Several methods have been proposed to generate 3D flight corridors for UAVs operating in diverse environments ^{[16][17][18][19][20][21]}[16,17,18,19,20,21]. However, the existing methodologies have limitations in terms of their ability to handle complex non-convex geometries (and thus be applied to complex confined spaces). They cannot handle dynamic obstacles/entities present in the environment (and thus cannot change/morph in real-time, allowing UAVs to replan their flight trajectories in real-time) or search for optimal paths within confined spaces. Furthermore, the existing methods (e.g., ^{[16][17][18][19][20][21]}[16,17,18,19,20,21]) do not consider the preferences and intentions of the UAV operator, which, in some cases, might be considered crucial for effective UAV operations in confined hazardous environments (e.g., buildings on fire [22]).

There are numerous algorithms for obtaining nearly minimal convex decompositions of both 2D and 3D environments focused on creating convex or nearly convex covers. Lien [16] proposed an algorithm for segmenting non-convex polygons with polygonal holes with the goal of minimizing the number of polygons representing the environment. Similarly, Mamou [23] converted a triangulated 3D mesh into a collection of approximately convex pieces by iteratively clustering mesh faces based on the heuristics related to convexity and the aspect ratio. Such an approach, however, can only be applicable to spaces/regions with certain characteristics such as convex geometrical volumes. In contrast, ref. [17] described an approach that is applicable to spaces of arbitrary dimensions that can compute a set of environmental cuts that divide obstacles into approximately convex pieces. These methods are not well-suited for convex optimization within obstacle-free spaces as they require convex regions, which, when applied to any arbitrary environment, might result in regions thought to be empty (obstacle-free) but that do intersect with the obstacle set.

Although effective in geometrically complex spaces meeting certain geometrical criteria, such algorithms are computationally expansive. However, for the past 20 years, new methodologies have been developed with polynomial-time approximations. Eidenbenz et al. [18] described an algorithm that computes a nearly minimal set of overlapping convex pieces for a polygon with holes. Although their approach provides results within a logarithmic error bound relative to the number of vertices in the environment, it requires a high running time of 𝑂(𝑛²⁹𝑙𝑜𝑔𝑛)

, where n represents the number of vertices in the polygon. Feng [19] presented an approach that divides an input polygon with holes into pieces and generates a tree structure of adjacent pieces. While this is a promising approach, their algorithm is limited to 2D cases. There have been convex decompositions that do not aim to find the minimum number of segments. For instance, Sarmiento [24] generates convex polytopic regions in N dimensions by sampling points in free space and checking their visibility from a set of “guard” positions. Unfortunately, this requires a set of samples covering the workspace, which prevents subsequent optimizations from being performed without any consideration for obstacle positions, resulting in a high computational time.

In the context of finding polyhedra, Deits ^[20][21][20,21] introduced the Iterative Regional Inflation by Semi-Definite Programming algorithm (IRIS), which allows users to choose a starting point on a terrain map to identify a maximum-volume ellipsoid contained within a polyhedron defined by hyperplanes. The main drawbacks of IRIS are its high computational effort to find the largest possible ellipsoid in the environment and a deficiency in finding a proper representation of the obstacles present within the environment. Another method employed for generating obstacle-free convex regions in motion planning is Stereographic Projection [25]. This approach relies on spherical projections utilizing convex hull generation and inverse vertex enumeration as subprocedures. One notable limitation of Stereographic Projection is that the selection of the initial point significantly impacts the volume of the resulting polyhedron. In contrast to Stereographic Projection, Zhong et al. [26] employed a technique known as sphere flipping to map original points into a nonlinear space. The algorithm calculates the convex hull of the mapped points and inversely maps the vertices of the hull into the Cartesian space. As with other approaches, this approach is of high computational complexity.