A Novel Simulated Annealing Based Strategy for Balanced UAV Task Assignment and Path Planning - PubMed Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2020 Aug 24;20(17):4769.
doi: 10.3390/s20174769.

A Novel Simulated Annealing Based Strategy for Balanced UAV Task Assignment and Path Planning

Lisu Huo  1 , Jianghan Zhu  1 , Guohua Wu  2 , Zhimeng Li  1
Affiliations

A Novel Simulated Annealing Based Strategy for Balanced UAV Task Assignment and Path Planning

Lisu Huo et al. Sensors (Basel). .

Abstract

The unmanned aerial vehicle (UAV) has drawn increasing attention in recent years, especially in executing tasks such as natural disaster rescue and detection, and battlefield cooperative operations. Task assignment and path planning for multiple UAVs in the above scenarios are essential for successful mission execution. But, effectively balancing tasks to better excavate the potential of UAVs remains a challenge, as well as efficiently generating feasible solutions from the current one in constrained explosive solution spaces with the increase in the scale of optimization problems. This paper proposes an efficient approach for task assignment and path planning with the objective of balancing the tasks among UAVs and achieving satisfactory temporal resolutions. To be specific, we add virtual nodes according to the number of UAVs to the original model of the vehicle routing problem (VRP), thus make it easier to form a solution suitable for heuristic algorithms. Besides, the concept of the universal distance matrix is proposed to transform the temporal constraints to spatial constraints and simplify the programming model. Then, a Swap-and-Judge Simulated Annealing (SJSA) algorithm is therefore proposed to improve the efficiency of generating feasible neighboring solutions. Extensive experimental and comparative studies on different scenarios demonstrate the efficiency of the proposed algorithm compared with the exact algorithm and meta-heuristic algorithms. The results also inspire us about the characteristics of a population-based algorithm in solving combinatorial discrete optimization problems.

Keywords: heuristic algorithm; path planning; simulated annealing; unmanned aerial vehicle.

PubMed Disclaimer

Conflict of interest statement

The authors declare no conflict of interest.

Figures

Figure 1
Figure 1
Unmanned aerial vehicle (UAV) task assignment and path planning model in the application scenario.
Figure 2
Figure 2
Convert the multipath problem into a single path problem.
Figure 3
Figure 3
Basic procedure for generating a feasible solution. UAV number M = 3, target nodes number N = 7.
Figure 4
Figure 4
Process of crossover operation of the Modified Genetic Algorithm (MGA).
Figure 5
Figure 5
An example of effective swaps and invalid swaps.
Figure 6
Figure 6
Simulation scenario.
Figure 7
Figure 7
Convergence comparison in scenario C.
Figure 8
Figure 8
Performance comparison among scenarios.
Figure 9
Figure 9
Comparison of optimized results by different methods in scenario C (M = 5, N = 20). (a) Optimized result of DIDE (best/1); (b) optimized result of MGA (Ratem=0.55); (c) optimized result of DISA; (d) optimized result of SJSA.
See this image and copyright information in PMC

Similar articles

See all similar articles

Cited by

See all "Cited by" articles

References

    1. Lundquist E.H. Drone duties: The dull, the dirty, and the dangerous. Nav. Forces. 2003;24:20.
    1. Yang L., Yao H., Wang J., Jiang C., Benslimane A., Liu Y. Multi-UAV Enabled Load-Balance Mobile Edge Computing for IoT Networks. IEEE Internet Things J. 2020;7:6898–6908. doi: 10.1109/JIOT.2020.2971645. - DOI
    1. Chen J., Wei Z., Li S., Cao B. Artificial Intelligence Aided Joint Bit Rate Selection and Radio Resource Allocation for Adaptive Video Streaming over F-RANs. IEEE Wirel. Commun. 2020;27:36–43. doi: 10.1109/MWC.001.1900351. - DOI
    1. Dorling K., Heinrichs J., Messier G.G., Magierowski S. Vehicle Routing Problems for Drone Delivery. IEEE Trans. Syst. Man Cybern. 2017;47:70–85. doi: 10.1109/TSMC.2016.2582745. - DOI
    1. Yongbo C., Yuesong M., Jianqiao Y., Xiaolong S., Nuo X. Three-dimensional unmanned aerial vehicle path planning using modified wolf pack search algorithm. Neurocomputing. 2017;266:445–457. doi: 10.1016/j.neucom.2017.05.059. - DOI

LinkOut - more resources