A Simulated Annealing Algorithm and Grid Map-Based UAV Coverage Path Planning Method for 3D Reconstruction

3D trajectory planning based on the Rapidly-exploring Random Tree–Connect and artificial potential fields method for unmanned aerial vehicles

This research proposes a multifaceted approach of three-dimensional trajectory planning based on the combination of Rapidly-exploring Random Tree–Connect algorithm and artificial potential field method to improve the path search ability and dynamic obstacles avoidance capability of unmanned aerial vehicles. Firstly, an improved method of the target gravity is developed by controlling the sampling range to reduce invalid sampling and speed up the convergence speed of the algorithm so as to lessen the restriction of low efficiency and random sampling of the Rapidly-exploring Random Tree–Connect algorithm. Moreover, the regulation factor is introduced into the artificial potential field method to deal with the problem of target unreachable in the trajectory planning. Then the improved Rapidly-exploring Random Tree–Connect algorithm is implemented to plan the global path in a complex environment. This step is carried out via selecting the local target point on the global path found in the global plan, dividing the complex environment into simple environment and utilizing the artificial potential field method to achieve the effect of avoiding unknown dynamic obstacles in the simple environment. Finally, cubic B-spline is employed to smoothing of the planned trajectory. The simulation results demonstrate that the combination of two improved algorithms improves the path search ability and dynamic barrier avoidance capability of the unmanned aerial vehicles.

Research on smooth path planning method based on improved ant colony algorithm optimized by Floyd algorithm

Aiming at the problems of slow convergence and easy fall into local optimal solution of the classic ant colony algorithm in path planning, an improved ant colony algorithm is proposed. Firstly, the Floyd algorithm is introduced to generate the guiding path, and increase the pheromone content on the guiding path. Through the difference in initial pheromone, the ant colony is guided to quickly find the target node. Secondly, the fallback strategy is applied to reduce the number of ants who die due to falling into the trap to increase the probability of ants finding the target node. Thirdly, the gravity concept in the artificial potential field method and the concept of distance from the optional node to the target node are introduced to improve the heuristic function to make up for the fallback strategy on the convergence speed of the algorithm. Fourthly, a multi-objective optimization function is proposed, which comprehensively considers the three indexes of path length, security, and energy consumption and combines the dynamic optimization idea to optimize the pheromone update method, to avoid the algorithm falling into the local optimal solution and improve the comprehensive quality of the path. Finally, according to the connectivity principle and quadratic B-spline curve optimization method, the path nodes are optimized to shorten the path length effectively.

Grid-Based coverage path planning with NFZ avoidance for UAV using parallel self-adaptive ant colony optimization algorithm in cloud IoT

In recent years, with the development of Unmanned Aerial Vehicle (UAV) and Cloud Internet-of-Things (Cloud IoT) technology, data collection using UAVs has become a new technology hotspot for many Cloud IoT applications. Due to constraints such as the limited power life, weak computing power of UAV and no-fly zones restrictions in the environment, it is necessary to use cloud server with powerful computing power in the Internet of Things to plan the path for UAV. This paper proposes a coverage path planning algorithm called Parallel Self-Adaptive Ant Colony Optimization Algorithm (PSAACO). In the proposed algorithm, we apply grid technique to map the area, adopt inversion and insertion operators to modify paths, use self-adaptive parameter setting to tune the pattern, and employ parallel computing to improve performance. This work also addresses an additional challenge of using the dynamic Floyd algorithm to avoid no-fly zones. The proposal is extensively evaluated. Some experiments show that the performance of the PSAACO algorithm is significantly improved by using parallel computing and self-adaptive parameter configuration. Especially, the algorithm has greater advantages when the areas are large or the no-fly zones are complex. Other experiments, in comparison with other algorithms and existing works, show that the path planned by PSAACO has the least energy consumption and the shortest completion time.

Systemic Performance Analysis on Zoning for Unmanned Aerial Vehicle-Based Service Delivery

A zoning approach that divides an area of interest into multiple sub-areas can be a systemic and strategic solution to safely deploy a fleet of unmanned aerial vehicles (UAVs) for package delivery services. Following the zoning approach, a UAV can be assigned to one of the sub-areas, taking sole ownership and responsibility of the sub-area. As a result, the need for collision avoidance between units and the complexity of relevant operational activities can be minimized, ensuring both safe and reliable execution of the tasks. Given that the zoning approach involves the demand-server allocation decision, the service quality to customers can also be improved by performing the zoning properly. To illuminate the benefits of the zoning approach to UAV operations from a systemic perspective, this study applies clustering techniques to derive zoning solutions under different scenarios and examines the performance of the solutions using a simulation model. The simulation results demonstrate that the zoning approach can improve the safety of UAV operations, as well as the quality of service to demands.

A Multi-Objective Coverage Path Planning Algorithm for UAVs to Cover Spatially Distributed Regions in Urban Environments

This paper presents a multi-objective coverage flight path planning algorithm that finds minimum length, collision-free, and flyable paths for unmanned aerial vehicles (UAV) in three-dimensional (3D) urban environments inhabiting multiple obstacles for covering spatially distributed regions. In many practical applications, UAVs are often required to fully cover multiple spatially distributed regions located in the 3D urban environments while avoiding obstacles. This problem is relatively complex since it requires the optimization of both inter (e.g., traveling from one region/city to another) and intra-regional (e.g., within a region/city) paths. To solve this complex problem, we find the traversal order of each area of interest (AOI) in the form of a coarse tour (i.e., graph) with the help of an ant colony optimization (ACO) algorithm by formulating it as a traveling salesman problem (TSP) from the center of each AOI, which is subsequently optimized. The intra-regional path finding problem is solved with the integration of fitting sensors’ footprints sweeps (SFS) and sparse waypoint graphs (SWG) in the AOI. To find a path that covers all accessible points of an AOI, we fit fewer, longest, and smooth SFSs in such a way that most parts of an AOI can be covered with fewer sweeps. Furthermore, the low-cost traversal order of each SFS is computed, and SWG is constructed by connecting the SFSs while respecting the global and local constraints. It finds a global solution (i.e., inter + intra-regional path) without sacrificing the guarantees on computing time, number of turning maneuvers, perfect coverage, path overlapping, and path length. The results obtained from various representative scenarios show that proposed algorithm is able to compute low-cost coverage paths for UAV navigation in urban environments.

Model-based analysis of multi-UAV path planning for surveying postdisaster building damage

Emergency responders require accurate and comprehensive data to make informed decisions. Moreover, the data should be acquired and analyzed swiftly to ensure an efficient response. One of the tasks at hand post-disaster is damage assessment within the impacted areas. In particular, building damage should be assessed to account for possible casualties, and displaced populations, to estimate long-term shelter capacities, and to assess the damage to services that depend on essential infrastructure (e.g. hospitals, schools, etc.). Remote sensing techniques, including satellite imagery, can be used to gathering such information so that the overall damage can be assessed. However, specific points of interest among the damaged buildings need higher resolution images and detailed information to assess the damage situation. These areas can be further assessed through unmanned aerial vehicles and 3D model reconstruction. This paper presents a multi-UAV coverage path planning method for the 3D reconstruction of postdisaster damaged buildings. The methodology has been implemented in NetLogo3D, a multi-agent model environment, and tested in a virtual built environment in Unity3D. The proposed method generates camera location points surrounding targeted damaged buildings. These camera location points are filtered to avoid collision and then sorted using the K-means or the Fuzzy C-means methods. After clustering camera location points and allocating these to each UAV unit, a route optimization process is conducted as a multiple traveling salesman problem. Final corrections are made to paths to avoid obstacles and give a resulting path for each UAV that balances the flight distance and time. The paper presents the details of the model and methodologies, and an examination of the texture resolution obtained from the proposed method and the conventional overhead flight with the nadir-looking method used in 3D mappings. The algorithm outperforms the conventional method in terms of the quality of the generated 3D model.