###### Abstract  
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. constrained polygonal space; path length; path planning; obstacles; maps; unmanned aerial vehicles; urban environments; time complexity; extremely sparse waypoint graph +
Footnote †: journal: Applied  
areas [8], forestry applications [9], aerial forest fire detection [10], estimating forest structure [11], traffic monitoring [12], retrieving tree volumes in forests [13], scientific research data collection [14], optical remote sensing [15], disaster assessment and management [16], mountain anti-terrorism combat [17], crust detection on steel bridges [18], vehicle detection in real-time, tracking and speed estimation [19], and ocean exploration assignments [20], among others. Moreover, the UAVs' next generation will offer more unique advancements that may increase their use in military applications around the globe [21; 22]. In the majority of civilian or military applications, a UAV usually needs the ability to search for the target location in a short time while avoiding collisions with obstacles it may face during the mission. However, without human onboard control, UAV use brings many challenges that need robust solutions, and, among those challenges, one is searching for an optimal/quasi-optimal, safe, and time-efficient path between two locations in a 3D map. Due to the large-scale utilization of UAVs in countless sectors, the Path Planning (PP) problem has become a very vibrant research topic. PP is a method of finding a workable path between two locations while safely bypassing obstacles present in the underlying 3D environment map, simultaneously satisfying one or more optimization objectives, such as distance, time, and consumption of energy [23]. PP is regarded as a Non-deterministic Polynomial-time (NP)-hard optimization problem in the robotics field. Generally, there are two types of PP problems: global PP and local PP. In global PP, finding a path that is performed in an environment that is known. However, local PP is relatively complicated because the UAV operating environment can be partially or fully unknown. Taking into account the mission scenarios of UAVs, pathfinding problems can be divided into two categories: single-agent and multi-agent.