JACIII Vol.28 No.3 pp. 475-483
doi: 10.20965/jaciii.2024.p0475

Research Paper:

Research on the Messenger UAV Mission Planning Based on Sampling Transformation Algorithm

Benxiang Wang*, Bin Xin*,†, Yulong Ding**, and Yang Li***

*School of Automation, Beijing Institute of Technology
5 South Zhongguancun Street, Haidian District, Beijing 100081, China

Corresponding author

**Peng Cheng Laboratory
Shibi Long Park Phase I, Shenzhen 518000, China

***Beijing Institute of Electronic Engineering
Yongding Road, Haidian District, Beijing 102206, China

March 17, 2023
August 4, 2023
May 20, 2024
urban environment, path planning, messenger mechanism, TSP

In recent years, there has been a significant development in unmanned platform technologies, specifically unmanned ground vehicles (UGVs) and unmanned aerial vehicles (UAVs). As a result, their application scenarios have expanded considerably. Unmanned platforms are considered integral components of the Internet of Things system. However, certain challenges arise when dealing with specialized tasks, such as navigating complex urban low-altitude terrain with multiple obstacles and limited communication capabilities. These challenges can greatly impact the efficiency of the system due to information isolation. To address this issue, a messenger drone mechanism is introduced in this paper, which utilizes air superiority to facilitate indirect communication between unmanned platforms. Additionally, a task sequence planning algorithm based on sampling transformation is designed. This algorithm efficiently assigns the drone to mobile UGVs by discretely sampling their paths and considering the UAV-UGV motion relationship. By transforming the problem into an asymmetric traveler problem, it allows for a fast solution. Finally, the effectiveness of the algorithm is verified through comparative analysis in different scenarios.

Cite this article as:
B. Wang, B. Xin, Y. Ding, and Y. Li, “Research on the Messenger UAV Mission Planning Based on Sampling Transformation Algorithm,” J. Adv. Comput. Intell. Intell. Inform., Vol.28 No.3, pp. 475-483, 2024.
Data files:
  1. [1] N. L. Fantana, T. Riedel, J. Schlick, S. Ferber, J. Hupp, S. Miles, F. Michahelles, and S. Svensson, “IoT Application - Value Creation for Industry,” O. Vermesan and P. Friess (Eds.), “Internet of Things Converging Technologies for Smart Environments and Integrated Ecosystems,” River Publishers, 2013.
  2. [2] H. Zhang, B. Xin, and Y. L. Ding, “Online Path Planning of Messenger UAV in Air-Ground Collaborative System,” 2019 Chinese Control Conf. (CCC), pp. 5875-5880, 2019.
  3. [3] C. A. Thiels, J. M. Aho, S. P. Zietlow, and D. H. Jenkins, “Use of Unmanned Aerial Vehicles for Medical Product Transport,” J. of Air Medical Transport, Vol.34, No.2, pp. 104-108, 2015.
  4. [4] B. Jung and G. Sukhatme, “Cooperative Multi-Robot Target Tracking,” Distributed Autonomous Robotic Systems 7, pp. 81-90, 2006.
  5. [5] D. F. Hu, J. L. Vincent, T. Wang, and L. Ma, “Multi-Agent Robotic System (MARS) for UAV-UGV Path Planning and Automatic Sensory Data Collection in Cluttered Environments,” Building and Environment, Vol.221, 2022.
  6. [6] M. Saska, V. Vonásek, T. Krajník, and L. Přeučil, “Coordination and Navigation of Heterogeneous MAV-UGV Formations Localized by a ‘Hawk-Eye’-Like Approach Under a Model Predictive Control Scheme,” Int. J. of Robotics Research, Vol.33, Issue 10, pp. 1393-1412, 2014.
  7. [7] H. Yu, K. Meier, M. Argyle, and R. W. Beard, “Cooperative Path Planning for Target Tracking in Urban Environments Using Unmanned Air and Ground Vehicles,” IEEE/ASME Trans. on Mechatronics, pp. 541-552, 2015.
  8. [8] Y. Ding, B. Xin, J. Chen, F. Hao, Y. Zhu, G. Gao, and L. Dou, “Path Planning of Messenger UAV in Air-Ground Coordination,” IFAC-PapersOnLine, Vol.50, Issue 1, pp. 8045-8051, 2017.
  9. [9] Q. Q. Wu, Y. Zeng, and R. Zhang, “Joint Trajectory and Communication Design for Multi-UAV Enabled Wireless Networks,” IEEE Trans. on Wireless Communications, Vol.17, No.3, pp. 2109-2121, 2018.
  10. [10] E. E. Yurek and H. C. Ozmutlu, “A Decomposition-Based Iterative Optimization Algorithm for Traveling Salesman Problem with Drone,” Transportation Research Part C: Emerging Technologies, Vol.91, pp. 249-262, 2018.
  11. [11] A. ul Husnain, N. Mokhtar, N. M. Shah, M. Dahari, and M. Iwahashi, “A Systematic Literature Review (SLR) on Autonomous Path Planning of Unmanned Aerial Vehicles,” Drones, Vol.7, No.2, 2023.
  12. [12] J. Chen, X. Zhang, and B. Xin, “Coordination Between Unmanned Aerial and Ground Vehicles: A Taxonomy and Optimization Perspective,” IEEE Trans. on Cybernetics, Vol.46, Issue 4, pp. 959-972, 2017.
  13. [13] H. C. Sung, A. Bhawesh, and J. K. Lee, “Optimization for Drone and Drone-Truck Combined Operations: A Review of the State of the Art and Future Directions,” Computers and Operations Research, Vol.123, Article No.105004, 2020.
  14. [14] B. X. Wang, B. Xin, Y. L. Ding, and Y. Li, “Sampling Transformation Based Path Planning for Messenger UAV in Urban Environment Messenger,” The 10th Int. Symp. on Computational Intelligence and Industrial Applications (ISCIIA2022), 2022.
  15. [15] N. Cao, K. H. Low, and J. M. Dolan, “Multi-Robot Informative Path Planning for Active Sensing of Environmental Phenomena: A Tale of Two Algorithms,” Proc. of 2013 Int. Conf. on Autonomous Agents and Multi-Agent Systems, pp. 7-14, 2013.
  16. [16] C. C. Murray and R. Raj, “The Multiple Flying Sidekicks Traveling Salesman Problem: Parcel Delivery with Multiple Drones,” Transportation Research Part C: Emerging Technologies, Vol.110, pp. 369-398, 2020.
  17. [17] S. Kim and I. Moon, “Traveling Salesman Problem with a Drone Station,” IEEE Trans. on Systems, Man, and Cybernetics: Systems, Vol.49, Issue 1, pp. 42-52, 2019.
  18. [18] Y. L. Ding, B. Xin, and J. Chen, “Precedence-Constrained Path Planning of Messenger UAV for Air-Ground Coordination,” Control Theory Tech., Vol.17, pp. 13-23, 2019.
  19. [19] C. E. Noon and J. C. Bean, “An Efficient Transformation of the Generalized Traveling Salesman Problem,” INFOR: Information Systems and Operational Research, Vol.31, No.1, pp. 39-44, 1993.
  20. [20] K. Helsgaun, “An Effective Implementation of the Lin–Kernighan Traveling Salesman Heuristic,” European J. of Operational Research, Vol.126, No.1, pp. 106-130, 2000.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Jul. 12, 2024