Path Planning Method for UAVs Based on Constrained Polygonal Space and an Extremely Sparse Waypoint Graph
Finding an optimal/quasi-optimal path for Unmanned Aerial Vehicles (UAVs) utilizing full map information yields time performance degradation in large and complex three-dimensional (3D) urban environments populated by various obstacles. A major portion of the computing time is usually wasted on model...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-06-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/11/12/5340 |
| _version_ | 1797530863274033152 |
|---|---|
| author | Abdul Majeed Seong Oun Hwang |
| author_facet | Abdul Majeed Seong Oun Hwang |
| author_sort | Abdul Majeed |
| collection | DOAJ |
| description | Finding an optimal/quasi-optimal path for Unmanned Aerial Vehicles (UAVs) utilizing full map information yields time performance degradation in large and complex three-dimensional (3D) urban environments populated by various obstacles. A major portion of the computing time is usually wasted on modeling and exploration of spaces that have a very low possibility of providing optimal/sub-optimal paths. However, computing time can be significantly reduced by searching for paths solely in the spaces that have the highest priority of providing an optimal/sub-optimal path. Many Path Planning (PP) techniques have been proposed, but a majority of the existing techniques equally evaluate many spaces of the maps, including unlikely ones, thereby creating time performance issues. Ignoring high-probability spaces and instead exploring too many spaces on maps while searching for a path yields extensive computing-time overhead. This paper presents a new PP method that finds optimal/quasi-optimal and safe (e.g., collision-free) working paths for UAVs in a 3D urban environment encompassing substantial obstacles. By using Constrained Polygonal Space (CPS) and an Extremely Sparse Waypoint Graph (ESWG) while searching for a path, the proposed PP method significantly lowers pathfinding time complexity without degrading the length of the path by much. We suggest an intelligent method exploiting obstacle geometry information to constrain the search space in a 3D polygon form from which a quasi-optimal flyable path can be found quickly. Furthermore, we perform task modeling with an ESWG using as few nodes and edges from the CPS as possible, and we find an abstract path that is subsequently improved. The results achieved from extensive experiments, and comparison with prior methods certify the efficacy of the proposed method and verify the above assertions. |
| first_indexed | 2024-03-10T10:36:02Z |
| format | Article |
| id | doaj.art-4f8968ca0c1b45aba2051a607b60199a |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T10:36:02Z |
| publishDate | 2021-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-4f8968ca0c1b45aba2051a607b60199a2023-11-21T23:18:17ZengMDPI AGApplied Sciences2076-34172021-06-011112534010.3390/app11125340Path Planning Method for UAVs Based on Constrained Polygonal Space and an Extremely Sparse Waypoint GraphAbdul Majeed0Seong Oun Hwang1Department of Computer Engineering, Gachon University, Seongnam 13120, KoreaDepartment of Computer Engineering, Gachon University, Seongnam 13120, KoreaFinding an optimal/quasi-optimal path for Unmanned Aerial Vehicles (UAVs) utilizing full map information yields time performance degradation in large and complex three-dimensional (3D) urban environments populated by various obstacles. A major portion of the computing time is usually wasted on modeling and exploration of spaces that have a very low possibility of providing optimal/sub-optimal paths. However, computing time can be significantly reduced by searching for paths solely in the spaces that have the highest priority of providing an optimal/sub-optimal path. Many Path Planning (PP) techniques have been proposed, but a majority of the existing techniques equally evaluate many spaces of the maps, including unlikely ones, thereby creating time performance issues. Ignoring high-probability spaces and instead exploring too many spaces on maps while searching for a path yields extensive computing-time overhead. This paper presents a new PP method that finds optimal/quasi-optimal and safe (e.g., collision-free) working paths for UAVs in a 3D urban environment encompassing substantial obstacles. By using Constrained Polygonal Space (CPS) and an Extremely Sparse Waypoint Graph (ESWG) while searching for a path, the proposed PP method significantly lowers pathfinding time complexity without degrading the length of the path by much. We suggest an intelligent method exploiting obstacle geometry information to constrain the search space in a 3D polygon form from which a quasi-optimal flyable path can be found quickly. Furthermore, we perform task modeling with an ESWG using as few nodes and edges from the CPS as possible, and we find an abstract path that is subsequently improved. The results achieved from extensive experiments, and comparison with prior methods certify the efficacy of the proposed method and verify the above assertions.https://www.mdpi.com/2076-3417/11/12/5340constrained polygonal spacepath lengthpath planningobstaclesmapsunmanned aerial vehicles |
| spellingShingle | Abdul Majeed Seong Oun Hwang Path Planning Method for UAVs Based on Constrained Polygonal Space and an Extremely Sparse Waypoint Graph Applied Sciences constrained polygonal space path length path planning obstacles maps unmanned aerial vehicles |
| title | Path Planning Method for UAVs Based on Constrained Polygonal Space and an Extremely Sparse Waypoint Graph |
| title_full | Path Planning Method for UAVs Based on Constrained Polygonal Space and an Extremely Sparse Waypoint Graph |
| title_fullStr | Path Planning Method for UAVs Based on Constrained Polygonal Space and an Extremely Sparse Waypoint Graph |
| title_full_unstemmed | Path Planning Method for UAVs Based on Constrained Polygonal Space and an Extremely Sparse Waypoint Graph |
| title_short | Path Planning Method for UAVs Based on Constrained Polygonal Space and an Extremely Sparse Waypoint Graph |
| title_sort | path planning method for uavs based on constrained polygonal space and an extremely sparse waypoint graph |
| topic | constrained polygonal space path length path planning obstacles maps unmanned aerial vehicles |
| url | https://www.mdpi.com/2076-3417/11/12/5340 |
| work_keys_str_mv | AT abdulmajeed pathplanningmethodforuavsbasedonconstrainedpolygonalspaceandanextremelysparsewaypointgraph AT seongounhwang pathplanningmethodforuavsbasedonconstrainedpolygonalspaceandanextremelysparsewaypointgraph |