Multi-UAV Coverage through Two-Step Auction in Dynamic Environments
Abstract
:1. Introduction
1.1. Related Work
1.2. Contributions
- We design the comprehensive MCTA framework for area coverage with multiple energy-limited UAVs in dynamic environments.
- We propose the two-step auction mechanism to select the optimal next action and avoid dynamic obstacles.
- We develop a reverse auction mechanism to avoid conflicts and balance workloads between UAVs.
2. Problem Formulation
3. MCTA Framework
3.1. Two-Step Auction
Algorithm 1 Two-step Auction. |
Input: UAV position p, orientation o Output: Four models sorted by bidding price and orientation o 1: for to 4 do 2: ; 3: Assume that the UAV is in module ; 4: Based on module , calculate ; 5: ; 6: end for 7: ; 8: return |
3.2. Obstacle Avoidance and Multi-UAV Conflict Resolution
3.3. Energy Constraint and Loop-Check
3.4. MCTA Framework
Algorithm 2 MCTA. |
Input:, , , 1: Two-step Auction (); 2: ; 3: for to 4 do 4: if module m corresponding to is reachable then 5: direction of module m; 6: ; 7: break 8: end if 9: end for 10: if then 11: Judge if there is a multi-UAV conflict; 12: if no conflict occurs or win the conflict then 13: Check the remaining energy and the loop; 14: if and not in the loop then 15: Choose a suitable way to reach module m; 16: the position of module m; 17: else 18: ; 19: end if 20: else 21: Stay in place for next step; 22: end if 23: else 24: ; 25: end if |
4. Experiments and Analysis
4.1. Qualitative Evaluation
4.2. Quantitative Evaluation
- Coverage rate: The coverage rate is defined as the ratio between the area of covered modules and the area of the entire environment:
- Repeated coverage rate: The repeated coverage rate is defined as:
- Average flight deviation: To investigate the degree of deviation of the flight path of each UAV from its average path, the average flight deviation is defined as follows:
5. Conclusions
Author Contributions
Funding
Institutional Review Board Statement
Informed Consent Statement
Data Availability Statement
Acknowledgments
Conflicts of Interest
References
- Liu, Z.; Wang, X.; Shen, L.; Zhao, S.; Cong, Y.; Li, J.; Yin, D.; Jia, S.; Xiang, X. Mission-oriented miniature fixed-wing UAV swarms: A multilayered and distributed architecture. IEEE Trans. Syst. Man Cybern. Syst. 2020, 52, 1588–1602. [Google Scholar] [CrossRef]
- Yan, C.; Xiang, X.; Wang, C. Towards real-time path planning through deep reinforcement learning for a UAV in dynamic environments. J. Intell. Robot. Syst. 2020, 98, 297–309. [Google Scholar] [CrossRef]
- Ball, Z.; Odonkor, P.; Chowdhury, S. A swarm-intelligence approach to oil spill mapping using unmanned aerial vehicles. In Proceedings of the AIAA Information Systems-AIAA Infotech@ Aerospace, Grapevine, TX, USA, 9–13 January 2017; p. 1157. [Google Scholar]
- Pannozzi, P.; Valavanis, K.P.; Rutherford, M.J.; Guglieri, G.; Scanavino, M.; Quagliotti, F. Urban monitoring of smart communities using UAS. In Proceedings of the 2019 International Conference on Unmanned Aircraft Systems (ICUAS), Atlanta, GA, USA, 11–14 June 2019; pp. 866–873. [Google Scholar]
- Alevizos, E.; Oikonomou, D.; Argyriou, A.V.; Alexakis, D.D. Fusion of Drone-Based RGB and Multi-Spectral Imagery for Shallow Water Bathymetry Inversion. Remote Sens. 2022, 14, 1127. [Google Scholar] [CrossRef]
- Bandini, F.; Lopez-Tamayo, A.; Merediz-Alonso, G.; Olesen, D.; Jakobsen, J.; Wang, S.; Garcia, M.; Bauer-Gottwein, P. Unmanned aerial vehicle observations of water surface elevation and bathymetry in the cenotes and lagoons of the Yucatan Peninsula, Mexico. Hydrogeol. J. 2018, 26, 2213–2228. [Google Scholar] [CrossRef] [Green Version]
- Specht, M.; Stateczny, A.; Specht, C.; Widźgowski, S.; Lewicka, O.; Wiśniewska, M. Concept of an Innovative Autonomous Unmanned System for Bathymetric Monitoring of Shallow Waterbodies (INNOBAT System). Energies 2021, 14, 5370. [Google Scholar] [CrossRef]
- Stateczny, A.; Specht, C.; Specht, M.; Brčić, D.; Jugović, A.; Widźgowski, S.; Wiśniewska, M.; Lewicka, O. Study on the Positioning Accuracy of GNSS/INS Systems Supported by DGPS and RTK Receivers for Hydrographic Surveys. Energies 2021, 14, 7413. [Google Scholar] [CrossRef]
- Wang, D.; Xing, S.; He, Y.; Yu, J.; Xu, Q.; Li, P. Evaluation of a New Lightweight UAV-Borne Topo-Bathymetric LiDAR for Shallow Water Bathymetry and Object Detection. Sensors 2022, 22, 1379. [Google Scholar] [CrossRef] [PubMed]
- Lin, L.; Goodrich, M.A. UAV intelligent path planning for wilderness search and rescue. In Proceedings of the 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, St. Louis, MO, USA, 10–15 October 2009; pp. 709–714. [Google Scholar]
- Kohlbrecher, S.; Kunz, F.; Koert, D.; Rose, C.; Manns, P.; Daun, K.; Schubert, J.; Stumpf, A.; von Stryk, O. Towards highly reliable autonomy for urban search and rescue robots. In Proceedings of the Robot Soccer World Cup; Springer: Berlin/Heidelberg, Germany, 2014; pp. 118–129. [Google Scholar]
- Galceran, E.; Carreras, M. A survey on coverage path planning for robotics. Robot. Auton. Syst. 2013, 61, 1258–1276. [Google Scholar] [CrossRef] [Green Version]
- Gao, G.Q.; Xin, B. A-STC: Auction-based spanning tree coverage algorithm formotion planning of cooperative robots. Front. Inf. Technol. Electron. Eng. 2019, 20, 18–31. [Google Scholar] [CrossRef]
- Viet, H.H.; Dang, V.H.; Laskar, M.N.U.; Chung, T. BA*: An online complete coverage algorithm for cleaning robots. Appl. Intell. 2013, 39, 217–235. [Google Scholar] [CrossRef]
- Khamis, A.; Hussein, A.; Elmogy, A. Multi-robot task allocation: A review of the state-of-the-art. Coop. Robot. Sens. Netw. 2015, 2015, 31–51. [Google Scholar]
- Khan, A.S.; Chen, G.; Rahulamathavan, Y.; Zheng, G.; Assadhan, B.; Lambotharan, S. Trusted UAV Network Coverage Using Blockchain, Machine Learning, and Auction Mechanisms. IEEE Access 2020, 8, 118219–118234. [Google Scholar] [CrossRef]
- Gabriely, Y.; Rimon, E. Spiral-STC: An on-line coverage algorithm of grid environments by a mobile robot. In Proceedings of the 2002 IEEE International Conference on Robotics and Automation (Cat. No. 02CH37292), Washington, DC, USA, 11–15 May 2002; Volume 1, pp. 954–960. [Google Scholar]
- Sonti, S.; Virani, N.; Jha, D.K.; Mukherjee, K.; Ray, A. Language measure-theoretic path planning in the presence of dynamic obstacles. In Proceedings of the 2013 American Control Conference, Washington, DC, USA, 17–19 June 2013; pp. 5110–5115. [Google Scholar]
- Gorbenko, A.; Popov, V. The multi-robot forest coverage for weighted terrain1. J. Ambient. Intell. Smart Environ. 2015, 7, 835–847. [Google Scholar] [CrossRef]
- Yehoshua, R.; Agmon, N.; Kaminka, G.A. Robotic adversarial coverage of known environments. Int. J. Robot. Res. 2016, 35, 1419–1444. [Google Scholar] [CrossRef]
- Shnaps, I.; Rimon, E. Online coverage of planar environments by a battery powered autonomous mobile robot. IEEE Trans. Autom. Sci. Eng. 2016, 13, 425–436. [Google Scholar] [CrossRef]
- Wei, M.; Isler, V. Coverage path planning under the energy constraint. In Proceedings of the 2018 IEEE International Conference on Robotics and Automation (ICRA), Brisbane, Australia, 21–25 May 2018; pp. 368–373. [Google Scholar]
- Wu, C.; Dai, C.; Gong, X.; Liu, Y.J.; Wang, J.; Gu, X.D.; Wang, C.C. Energy-efficient coverage path planning for general terrain surfaces. IEEE Robot. Autom. Lett. 2019, 4, 2584–2591. [Google Scholar] [CrossRef]
- Modares, J.; Ghanei, F.; Mastronarde, N.; Dantu, K. Ub-anc planner: Energy efficient coverage path planning with multiple drones. In Proceedings of the 2017 IEEE International Conference on Robotics and Automation (ICRA), Singapore, 29 May–3 June 2017; pp. 6182–6189. [Google Scholar]
- Jensen-Nau, K.R.; Hermans, T.; Leang, K.K. Near-Optimal Area-Coverage Path Planning of Energy-Constrained Aerial Robots with Application in Autonomous Environmental Monitoring. IEEE Trans. Autom. Sci. Eng. 2020, 18, 1453–1468. [Google Scholar] [CrossRef]
- Strimel, G.P.; Veloso, M.M. Coverage planning with finite resources. In Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, Chicago, IL, USA, 14–18 September 2014; pp. 2950–2956. [Google Scholar]
- Dutta, A.; Sharma, G. A Constant-Factor Approximation Algorithm for Online Coverage Path Planning with Energy Constraint. arXiv 2019, arXiv:1906.11750. [Google Scholar]
- Torres, M.; Pelta, D.A.; Verdegay, J.L.; Torres, J.C. Coverage path planning with unmanned aerial vehicles for 3D terrain reconstruction. Expert Syst. Appl. 2016, 55, 441–451. [Google Scholar] [CrossRef]
1 | |||||
a | 4 | 3 | 2 | 1 | 0 (obstacles cannot move) |
Environment | Size | v | Static | Dynamic | ||||
---|---|---|---|---|---|---|---|---|
free | 20 × 20 | 1 | 93.54% | 15.66% | 0 | 93.06% | 14.87% | 0 |
4 | 92.18% | 23.37% | 1.34 | 91.98% | 23.32% | 1.44 | ||
8 | 88.14% | 25.11% | 1.41 | 88.52% | 24.66% | 1.44 | ||
40 × 40 | 1 | 91.06% | 19.30% | 0 | 91.74% | 19.75% | 0 | |
4 | 91.09% | 23.39% | 2.26 | 91.08% | 23.92% | 2.41 | ||
convex | 20 × 20 | 1 | 96.34% | 30.32% | 0 | 96.52% | 31.40% | 0 |
4 | 95.59% | 38.91% | 1.58 | 96.28% | 40.17% | 1.6 | ||
12 | 92.42% | 49.06% | 1.4 | 92.70% | 48.36% | 1.36 | ||
40 × 40 | 1 | 94.58% | 33.51% | 0 | 94.73% | 32.47% | 0 | |
8 | 95.39% | 43.23% | 3.9 | 95.40% | 43.24% | 3.86 | ||
12 | 95.08% | 45.48% | 2.74 | 95.20% | 45.78% | 2.74 | ||
maze | 20 × 20 | 8 | 81.89% | 33.32% | 3.42 | 80.53% | 35.26% | 3.4 |
12 | 82.36% | 38.42% | 2.64 | 82.67% | 41.01% | 2.43 | ||
40 × 40 | 1 | 79.47% | 29.80% | 0 | 79.75% | 29.97% | 0 | |
12 | 87.07% | 45.11% | 9.13 | 87.67% | 45.29% | 8.93 | ||
ring | 20 × 20 | 1 | 83.02% | 22.78% | 0 | 83.44% | 24.26% | 0 |
12 | 86.82% | 46.64% | 1.35 | 86.43% | 47.05% | 1.43 | ||
40 × 40 | 1 | 81.27% | 33.76% | 0 | 80.81% | 32.32% | 0 | |
12 | 89.09% | 49.53% | 2.95 | 88.42% | 50.27% | 2.97 | ||
honeycomb | 20 × 20 | 1 | 75.74% | 36.19% | 0 | 75.75% | 35.62% | 0 |
8 | 80.75% | 37.57% | 3.27 | 80.45% | 37.95% | 3.33 | ||
strip | 20 × 20 | 1 | 92.07% | 28.82% | 0 | 93.15% | 29.16% | 0 |
4 | 93.31% | 39.58% | 3.26 | 93.70% | 39.52% | 2.96 | ||
8 | 93.30% | 45.57% | 1.82 | 92.89% | 44.94% | 1.85 | ||
40 × 40 | 1 | 87.42% | 28.94% | 0 | 87.86% | 30.27% | 0 | |
12 | 92.13% | 46.28% | 4.83 | 92.61% | 45.93% | 4.88 |
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. |
© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Sun, Y.; Tan, Q.; Yan, C.; Chang, Y.; Xiang, X.; Zhou, H. Multi-UAV Coverage through Two-Step Auction in Dynamic Environments. Drones 2022, 6, 153. https://0-doi-org.brum.beds.ac.uk/10.3390/drones6060153
Sun Y, Tan Q, Yan C, Chang Y, Xiang X, Zhou H. Multi-UAV Coverage through Two-Step Auction in Dynamic Environments. Drones. 2022; 6(6):153. https://0-doi-org.brum.beds.ac.uk/10.3390/drones6060153
Chicago/Turabian StyleSun, Yihao, Qin Tan, Chao Yan, Yuan Chang, Xiaojia Xiang, and Han Zhou. 2022. "Multi-UAV Coverage through Two-Step Auction in Dynamic Environments" Drones 6, no. 6: 153. https://0-doi-org.brum.beds.ac.uk/10.3390/drones6060153