Hostname: page-component-669899f699-7xsfk Total loading time: 0 Render date: 2025-04-26T07:16:39.985Z Has data issue: false hasContentIssue false
  • English
  • Français

Balanced Multi-UAV path planning for persistent monitoring

Published online by Cambridge University Press:  20 November 2024

Xinru Zhan Open the ORCID record for Xinru Zhan [Opens in a new window] ,
Yang Chen Open the ORCID record for Yang Chen [Opens in a new window] ,
Xi Chen  and
Wenhao Zhang
Xinru Zhan
Affiliation:
School of Information Science and Engineering, Wuhan University of Science and Technology, Wuhan, China
Yang Chen*
Affiliation:
School of Information Science and Engineering, Wuhan University of Science and Technology, Wuhan, China
Xi Chen
Affiliation:
School of Information Science and Engineering, Wuhan University of Science and Technology, Wuhan, China
Wenhao Zhang
Affiliation:
Centre for Machine Vision, Bristol Robotics Laboratory, UWE Bristol, UK
*
Corresponding author: Yang Chen; Email: chenyag@wust.edu.cn
Get access Rights & Permissions [Opens in a new window]

Abstract

In scenarios such as environmental data collection and traffic monitoring, timely responses to real-time situations are facilitated by persistently accessing nodes with revisiting constraints using unmanned aerial vehicles (UAVs). However, imbalanced task allocation may pose risks to the safety of UAVs and potentially lead to failures in monitoring tasks. For instance, continuous visits to nodes without replenishment may damage UAV batteries, while delays in recharging could result in missing task deadlines, ultimately causing task failures. Therefore, this study investigates the problem of achieving balanced multi-UAV path planning for persistent monitoring tasks, which has not been previously researched according to the authors’ knowledge. The main contribution of this study is the proposal of two novel indicators to assist in balancing task allocation regarding multi-UAV path planning for persistent monitoring. One of the indicators is namely the waiting factor, which reflects the urgency of a task node waiting to be accessed, and the other is the difficulty level which is introduced to measure the difficulty of tasks undertaken by a UAV. By minimizing differences in difficulty level among UAVs, we can ensure equilibrium in task allocation. For a single UAV, the ant colony initialized genetic algorithm (ACIGA) has been proposed to plan its path and obtain its difficulty level. For multiple UAVs, the K-means clustering algorithm has been improved based on difficulty levels to achieve balanced task allocation. Simulation experiments demonstrated that the difficulty level could effectively reflect the difficulty of tasks and that the proposed algorithms could enable UAVs to achieve balanced task allocation.

Keywords

Path planningpersistent monitoringtask balancingK-means clustering
Type
Research Article
Information
Robotica , First View , pp. 1 - 18
Copyright
© The Author(s), 2024. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Messaoudi, K., Oubbati, O. S., Rachedi, A. and Bendouma, T., “UAV-UGV-based system for AOI minimization in IOT networks,” ICC 2023-IEEE International Conference on Communications, Rome, Italy, IEEE (2023), 2023-May, pp. 4743–4748. Google Scholar
Xu, C., Li, Q., Zhou, Q., Zhang, S., Yu, D. and Ma, Y., “Power line-guided automatic electric transmission line inspection system,” IEEE Trans. Instrum. Meas. 71, 1–18 (2022).Google Scholar
Bailon-Ruiz, R. and Lacroix, S., “Wildfire remote sensing with UAVs: A review from the autonomy point of view,” 2020 International Conference on Unmanned Aircraft Systems (ICUAS), IEEE (2020) pp. 412–420.Google Scholar
Zhang, C., Zhou, W., Qin, W. and Tang, W., “A novel UAV path planning approach: Heuristic crossing search and rescue optimization algorithm,” Expert Syst. Appl. 215, 119243 (2023).CrossRefGoogle Scholar
Messaoudi, K., Oubbati, O. S., Rachedi, A., Lakas, A., Bendouma, T. and Chaib, N., “A survey of UAV-based data collection: Challenges, solutions and future perspectives,” J. Netw. Comput. Appl. 216, 103670 (2023).CrossRefGoogle Scholar
Alzahrani, B., Oubbati, O. S., Barnawi, A., Atiquzzaman, M. and Alghazzawi, D., “UAV assistance paradigm: State-of-the-art in applications and challenges,” J. Netw. Comput. Appl. 166, 102706 (2020).CrossRefGoogle Scholar
Yu, B., Fan, S., Cui, W., Xia, K. and Wang, L., “A multi-UAV cooperative mission planning method based on SA-WOA algorithm for three-dimensional space atmospheric environment detection,” Robotica 42(7), 2243–2280 (2024).CrossRefGoogle Scholar
Chen, Y., Ren, S., Chen, Z., Chen, M. and Wu, H., “Path planning for vehicle-borne system consisting of multi air–ground robots,” Robotica 38(3), 493–511 (2020).CrossRefGoogle Scholar
Asghar, A. B., Sundaram, S. and Smith, S. L., Multi-robot persistent monitoring: minimizing latency and number of robots with recharging constraints, arXiv preprint arXiv:2303.08935 (2023).Google Scholar
Sharma, M. and Voruganti, H. K., “Multi-objective optimization approach for coverage path planning of mobile robot,” Robotica 42(7), 2125–2149 (2024).CrossRefGoogle Scholar
Hari, S. K. K., Rathinam, S., Darbha, S., Manyam, S. G., Kalyanam, K. and Casbeer, D., “Bounds on optimal revisit times in persistent monitoring missions with a distinct and remote service station,” IEEE T. Robot. 39(2), 1070–1086 (2022).CrossRefGoogle Scholar
Scott, D., Manyam, S. G., Casbeer, D. W. and Kumar, M., “A lagrangian algorithm for multiple depot traveling salesman problem with revisit period constraints,” IEEE T. Autom. Sci. Eng. 20(1), 690–702 (2022).CrossRefGoogle Scholar
Lin, X., Yazıcıoğlu, Y. and Aksaray, D., “Robust planning for persistent surveillance with energy-constrained UAVs and mobile charging stations,” IEEE Robot. Autom. Lett. 7(2), 4157–4164 (2022).CrossRefGoogle Scholar
Shu, Y., Chen, Y., Hu, M., Wu, H. and Zhao, X., “UAV path planning based on simultaneous optimization of monitoring frequency and security,” 2022 34th Chinese Control and Decision Conference (CCDC), Piscataway, NJ, IEEE (2022) pp. 3808–3814. Google Scholar
Feng, L. and Katupitiya, J., “UAV-based persistent full area coverage with dynamic priorities,” Robot. Auton. Syst. 157, 104244 (2022).CrossRefGoogle Scholar
Lien, J.-M., Rodriguez, S. and Morales, M., “Persistent covering with latency and energy constraints,” IEEE Robot. Autom. Lett. 6(2), 998–1003 (2021).CrossRefGoogle Scholar
Wang, L., Zhang, X., Deng, P., Kang, J., Gao, Z., Liu, L., “An energy-balanced path planning algorithm for multiple ferrying UAVs based on GA,” Int. J. Aerospace Eng. 2020, 3516149 (2020).CrossRefGoogle Scholar
Huo, L., Zhu, J., Wu, G. and Li, Z., “A novel simulated annealing based strategy for balanced UAV task assignment and path planning,” Sensors 20(17), 4769 (2020).CrossRefGoogle ScholarPubMed
Lee, S., “A multi-robot balanced coverage path planning strategy for patrol missions,” 2021 21st International Conference on Control, Automation and Systems (ICCAS), Jeju, Korea, IEEE (2021) pp. 1567–1569. Google Scholar
You, J., Jia, J., Pang, X., Wen, J., Shi, Y. and Zeng, J., “A novel multi-robot task assignment scheme based on a multi-angle k-means clustering algorithm and a two-stage load-balancing strategy,” Electronics 12(18), 3842 (2023).CrossRefGoogle Scholar
Guo, Q., Peng, J., Xu, W., Liang, W., Jia, X., Xu, Z., Yang, Y. and Wang, M., “Minimizing the longest tour time among a fleet of UAVs for disaster area surveillance,” IEEE T. Mobile Comput. 21(7), 2451–2465 (2020).CrossRefGoogle Scholar
Tang, Y., Zhou, R., Sun, G., Di, B. and Xiong, R., “A novel cooperative path planning for multirobot persistent coverage in complex environments,” IEEE Sens. J. 20(8), 4485–4495 (2020).CrossRefGoogle Scholar
Yu, X., Jin, S., Shi, D., Li, L., Kang, Y. and Zou, J., “Balanced multi-region coverage path planning for unmanned aerial vehicles,” IEEE International Conference on Systems, Man, and Cybernetics (SMC), Piscataway, NJ, IEEE (2020) pp. 3499–3506. Google Scholar
Hari, S., Rathinam, S., Darbha, S., Kalyanam, K., Manyam, S. and Casbeer, D., “Optimal UAV route planning for persistent monitoring missions,” IEEE T. Robot. 37(2), 550–566 (2020).CrossRefGoogle Scholar
Xia, L., “Risk-sensitive markov decision processes with combined metrics of mean and variance,” Prod. Oper. Manag. 29(12), 2808–2827 (2020).CrossRefGoogle Scholar
Tan, J. S., Gao, J., Wang, H., Zhang, H. and Zhang, Y., “Multi-UAV path planning based on IB-ABC with restricted planned arrival sequence,” Robotica 41(4), 1244–1257 (2023).CrossRefGoogle Scholar