Submitted Successfully!
To reward your contribution, here is a gift for you: A free trial for our video production service.
Thank you for your contribution! You can also upload a video entry or images related to this topic.
Version Summary Created by Modification Content Size Created at Operation
1
Sherif Mohammed Hassan Mostafa
 -- 1148 2023-10-10 08:47:44 |
2 Reference format revised.
Lindsay Dong
Meta information modification 1148 2023-10-16 03:52:08 |

Video Upload Options

Do you have a full video?
Send video materials Upload full video

Confirm

Are you sure to Delete?
Yes No
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
Mostafa, S.; Ramirez-Serrano, A. Three-Dimensional Flight Corridor for Unmanned Aerial Vehicle. Encyclopedia. Available online: https://encyclopedia.pub/entry/50031 (accessed on 20 May 2024).
Mostafa S, Ramirez-Serrano A. Three-Dimensional Flight Corridor for Unmanned Aerial Vehicle. Encyclopedia. Available at: https://encyclopedia.pub/entry/50031. Accessed May 20, 2024.
Mostafa, Sherif, Alejandro Ramirez-Serrano. "Three-Dimensional Flight Corridor for Unmanned Aerial Vehicle" Encyclopedia, https://encyclopedia.pub/entry/50031 (accessed May 20, 2024).
Mostafa, S., & Ramirez-Serrano, A. (2023, October 10). Three-Dimensional Flight Corridor for Unmanned Aerial Vehicle. In Encyclopedia. https://encyclopedia.pub/entry/50031
Mostafa, Sherif and Alejandro Ramirez-Serrano. "Three-Dimensional Flight Corridor for Unmanned Aerial Vehicle." Encyclopedia. Web. 10 October, 2023.
Three-Dimensional Flight Corridor for Unmanned Aerial Vehicle
Edit
This entry is adapted from the peer-reviewed paper 10.3390/robotics12050134

The 3D flight corridor is established as a topological structure based on a hand-crafted path either derived from a computer-generated environment or provided by the human operator, which captures humans’ preferences and desired flight intentions for the given space. This corridor is formulated as a series of interconnected overlapping convex polyhedra bounded by the perceived environmental geometries, which facilitates the generation of suitable 3D flight paths/trajectories that avoid local minima within the corridor boundaries. An occupancy check algorithm is employed to reduce the search space needed to identify 3D obstacle-free spaces in which their constructed polyhedron geometries are replaced with alternate convex polyhedra. 

flight corridor confined spaces indoor environments UAV

1. Introduction

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], Urban Search and Rescue (USAR) [3], and military applications [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.
Robotics 12 00134 g001
Figure 1. Surveying in geometrically complex unstructured spaces [7][8][9]: (a) underground tunnels; (b) collapsed underground installations; (c) mines.
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]. 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.

2. Three-Dimensional Flight Corridor for Unmanned Aerial Vehicle 

Several methods have been proposed to generate 3D flight corridors for UAVs operating in diverse environments [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]) 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 𝑂(𝑛29𝑙𝑜𝑔𝑛), 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] 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.

References

  1. Shahmoradi, J.; Talebi, E.; Roghanchi, P.; Hassanalian, M. A comprehensive review of applications of drone technology in the mining industry. Drones 2020, 4, 34.
  2. Ren, H.; Zhao, Y.; Xiao, W.; Hu, Z. A review of UAV monitoring in mining areas: Current status and future perspectives. Int. J. Coal Sci. Technol. 2019, 6, 320–333.
  3. Półka, M.; Ptak, S.; Kuziora, Ł. The use of UAV’s for search and rescue operations. Procedia Eng. 2017, 192, 748–752.
  4. Neubauer, M.; Günther, G.; Füllhas, K. Structural Design Aspects and Criteria for Military UAV; Technical Report; European Aeronautic Defence and Space (EADS): Munich, Germany, 2007.
  5. Gupta, S.G.; Ghonge, D.M.; Jawandhiya, P.M. Review of unmanned aircraft system (UAS). Int. J. Adv. Res. Comput. Eng. Technol. (IJARCET) 2013, 2, 1646–1658.
  6. Innocente, M.S.; Grasso, P. Self-organising swarms of firefighting drones: Harnessing the power of collective intelligence in decentralised multi-robot systems. J. Comput. Sci. 2019, 34, 80–101.
  7. CSIRO Head Office; Westwick-Farrow Pty Ltd. Researchers Deploy Autonomous Drone to Improve Operations for Mining Industry. November 2017. Available online: https://www.processonline.com.au/content/business/news/researchers-deploy-autonomous-drone-to-improve-operations-for-mining-industry-1267356273 (accessed on 24 September 2023).
  8. Coldewey, D. Subterranean Drone Mapping Startup Emesent Raises $2.5 M to Autonomously Delve the Deep. TechCrunch; November 2018. Available online: https://techcrunch.com/2018/11/05/subterranean-drone-mapping-startup-emesent-raises-2-5m-to-autonomously-delve-the-deep/ (accessed on 24 September 2023).
  9. Reporter, S. Mapping the Underground with Drones, Legged Robots. Aspermont Media Ltd. October 2018. Available online: https://www.miningmagazine.com/innovation/news/1347934/mapping-the-underground-with-drones-legged-robots (accessed on 24 September 2023).
  10. Liang, H.; Lee, S.C.; Bae, W.; Kim, J.; Seo, S. Towards UAVs in Construction: Advancements, Challenges, and Future Directions for Monitoring and Inspection. Drones 2023, 7, 202.
  11. Liu, S.; Watterson, M.; Mohta, K.; Sun, K.; Bhattacharya, S.; Taylor, C.J.; Kumar, V. Planning dynamically feasible trajectories for quadrotors using safe flight corridors in 3-d complex environments. IEEE Robot. Autom. Lett. 2017, 2, 1688–1695.
  12. Zinage, V.; Arul, S.H.; Manocha, D.; Ghosh, S. 3D-Online Generalized Sensed Shape Expansion: A Probabilistically Complete Motion Planner in Obstacle-Cluttered Unknown Environments. IEEE Robot. Autom. Lett. 2023, 8, 3334–3341.
  13. Chen, J.; Liu, T.; Shen, S. Online generation of collision-free trajectories for quadrotor flight in unknown cluttered environments. In Proceedings of the 2016 IEEE International Conference on Robotics and Automation (ICRA), Stockholm, Sweden, 16–21 May 2016; pp. 1476–1483.
  14. Gao, F.; Wang, L.; Zhou, B.; Zhou, X.; Pan, J.; Shen, S. Teach-repeat-replan: A complete and robust system for aggressive flight in complex environments. IEEE Trans. Robot. 2020, 36, 1526–1545.
  15. Gao, F.; Wang, L.; Wang, K.; Wu, W.; Zhou, B.; Han, L.; Shen, S. Optimal trajectory generation for quadrotor teach-and-repeat. IEEE Robot. Autom. Lett. 2019, 4, 1493–1500.
  16. Lien, J.M.; Amato, N.M. Approximate convex decomposition of polygons. In Proceedings of the Twentieth Annual Symposium on Computational Geometry, Brooklyn, NY, USA, 9–11 June 2004; pp. 17–26.
  17. Liu, H.; Liu, W.; Latecki, L.J. Convex shape decomposition. In Proceedings of the 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Francisco, CA, USA, 13–18 June 2010; pp. 97–104.
  18. Eidenbenz, S.J.; Widmayer, P. An approximation algorithm for minimum convex cover with logarithmic performance guarantee. SIAM J. Comput. 2003, 32, 654–670.
  19. Feng, H.Y.; Pavlidis, T. Decomposition of polygons into simpler components: Feature generation for syntactic pattern recognition. IEEE Trans. Comput. 1975, 100, 636–650.
  20. Deits, R.; Tedrake, R. Computing large convex regions of obstacle-free space through semidefinite programming. In Proceedings of the Algorithmic Foundations of Robotics XI: Selected Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics, Istanbul, Turkey, 3–5 August 2015; pp. 109–124.
  21. Deits, R.; Tedrake, R. Efficient mixed-integer planning for UAVs in cluttered environments. In Proceedings of the 2015 IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, USA, 26–30 May 2015; pp. 42–49.
  22. Tan, L.; Hu, M.; Lin, H. Agent-based simulation of building evacuation: Combining human behavior with predictable spatial accessibility in a fire emergency. Inf. Sci. 2015, 295, 53–66.
  23. Mamou, K.; Ghorbel, F. A simple and efficient approach for 3D mesh approximate convex decomposition. In Proceedings of the 2009 16th IEEE International Conference on Image Processing (ICIP), Cairo, Egypt, 7–10 November 2009; pp. 3501–3504.
  24. Sarmientoy, A.; Murrieta-Cidz, R.; Hutchinsony, S. A sample-based convex cover for rapidly finding an object in a 3-D environment. In Proceedings of the 2005 IEEE International Conference on Robotics and Automation, Barcelona, Spain, 18–22 April 2005; pp. 3486–3491.
  25. Savin, S. An algorithm for generating convex obstacle-free regions based on stereographic projection. In Proceedings of the 2017 International Siberian Conference on Control and Communications (SIBCON), Astana, Kazakhstan, 29–30 June 2017; pp. 1–6.
  26. Zhong, X.; Wu, Y.; Wang, D.; Wang, Q.; Xu, C.; Gao, F. Generating large convex polytopes directly on point clouds. arXiv 2020, arXiv:2010.08744.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
Upload a video for this entry
Information
Subjects: Robotics
Contributors MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
Sherif Mostafa
,
Alejandro Ramirez-Serrano
View Times: 197
Revisions: 2 times (View History)
Update Date: 16 Oct 2023
Table of Contents
    1000/1000
    Hot Most Recent
    Video Production Service
    Feedback