Radio Map Enabled Path Planning for Multiple Cellular-Connected Unmanned Aerial Vehicles
-
摘要: 针对多网联无人机协同作业场景中，因冲突规避引发的个体服务质量不均衡问题，提出一种基于无线电地图辅助的协同路径规划方案。该方案以最小化所有无人机中最大任务完成时间与通信断联时间加权和为目标，构建了多无人机路径规划模型，并设计了一种改进的冲突搜索(ICBS)算法进行求解。该算法采用分层搜索架构：高层结构通过引入邻近冲突检测以确保满足安全距离约束，并利用重构的代价函数引导以公平性为导向的冲突消解与路径选择；低层结构则采用基于双向A*的最优路径算法，通过双向并行搜索机制提升寻优效率。仿真结果表明，相较于基准方案，所提方案能够有效降低所有无人机中最大加权时间，显著提升多无人机协同的公平性与整体性能。Abstract:
Objective In collaborative operation scenarios of cellular-connected Unmanned Aerial Vehicles (UAVs), conflict avoidance strategies often result in unbalanced service quality. Traditional schemes typically focus on minimizing the total task completion time, failing to ensure service fairness. To address this, a radio map-assisted cooperative path planning scheme is proposed. The primary objective is to minimize the maximum weighted sum of task completion time and communication disconnection time across all UAVs, thereby ensuring balanced service quality in multi-UAV scenarios. Methods A Signal-to-Interference-Plus-Noise Ratio (SINR) map is constructed to evaluate communication quality. The 2D airspace is discretized into grids, and link gain maps are generated via ray-tracing and Axis-Aligned Bounding Box detection to determine Line-of-Sight (LoS) or Non-Line-of-Sight (NLoS) link conditions. The SINR map is then derived by selecting the base station with the maximum expected SINR for each grid. To solve the optimization problem, an Improved Conflict-Based Search (ICBS) algorithm with a hierarchical structure is developed. At the high-level stage, proximity conflicts are managed to maintain safety distances, and the cost function is reconstructed to prioritize fairness by minimizing the maximum weighted time. The low-level stage employs a bidirectional A* algorithm for single UAV path planning, utilizing parallel search mechanisms to accelerate the process while adhering to the constraints from the high-level stage. Results and Discussions The effectiveness of the proposed scheme is verified through simulations across various scenarios. The building height and position distribution are illustrated, where base station locations are marked by red stars and building heights are represented by color gradients from light to dark indicating increasing height ( Fig.2 ). The complex wireless propagation environment between UAVs and ground base stations is revealed by the constructed SINR map at an altitude of 60 m (Fig.3 ), showing significant SINR degradation in specific areas caused by building blockage and co-channel interference, which leads to the formation of communication blind zones. Trajectory planning results for four UAVs at an altitude of 60 m with a SINR threshold of 2 dB demonstrate that all UAVs effectively avoid signal blind zones and complete tasks without collision risks under the proposed scheme (Fig.4 ). A trade-off between task completion time and communication disconnection time is demonstrated by the weight coefficient (Fig.5 ). A monotonically increasing trend is observed in the maximum weighted time as the weight coefficient increases, whereas the maximum disconnection time decreases significantly. Superior computational efficiency is exhibited by the bidirectional A* algorithm compared to Dijkstra’s and traditional A* algorithms, while optimal solution quality is maintained (Table 1 ). Identical weighted times are achieved by all three algorithms, confirming the optimality of the bidirectional A* approach, yet the runtime is significantly reduced due to the bidirectional parallel search mechanism. The proposed scheme is compared with three different benchmark schemes, achieving the lowest maximum weighted time across various SINR thresholds (Fig.6 ). Performance analysis across different UAV altitudes indicates that a stable maximum weighted time is maintained by the proposed scheme below 75 m, while sharp increases are observed above this height due to intensified interference from non-serving base stations (Fig.7 ). Furthermore, the scalability analysis demonstrates significant improvements of the proposed scheme over benchmark schemes, particularly when conflicts become more frequent (Fig.8 ).Conclusions To address the fairness issue in cellular-connected multi-UAV systems, a radio map-assisted path planning scheme is proposed to minimize the maximum weighted time. Based on a constructed discretized SINR map, an Improved Conflict-Based Search (ICBS) algorithm is developed. At the high-level stage, proximity conflicts and a reconstructed cost function are introduced to ensure safety and fairness, while a bidirectional A* algorithm is employed at the low-level stage to accelerate search efficiency. Simulation results indicate that the proposed scheme effectively reduces the maximum weighted time compared to benchmark schemes, significantly enhancing the fairness and overall performance of multi-UAV collaboration. -
Key words:
- Cellular-connected UAV /
- Radio map /
- Path planning /
- Conflict-based search algorithm
-
1 ICBS算法
输入： $ K $架无人机的起点集合$ \left\{{\boldsymbol{u}}_{k,I}\right\} $，终点集合$ \left\{{\boldsymbol{u}}_{k,F}\right\} $，SINR地图$ {[\boldsymbol{R}]}_{i,j} $，SINR阈值$ {\gamma }_{\text{th}} $，安全距离$ {d}_{\text{s}} $ 输出： 无冲突的最优路径集合$ \left\{{\boldsymbol{U}}_{k}\right\} $ (1) 初始化：优先队列$ \text{OPEN}\leftarrow \varnothing $，创建根节点$ {\text{CT}}_{\text{root}} $，设置其约束集$ {\text{CT}}_{\text{root}}.\boldsymbol{C}\leftarrow \varnothing $，并调用双向A*算法规划初始路径作为$ {\text{CT}}_{\text{root}} $的路
径集合及根据公式(21)计算代价$ {\text{CT}}_{\text{root}}.\text{cost} $，将$ {\text{CT}}_{\text{root}} $插入OPEN(2) while $ \text{OPEN}\neq \varnothing $ do (3) 当前节点$ {\text{CT}}_{\text{curr}}\leftarrow \arg {\min }_{\text{CT}\in \text{OPEN}}\text{CT.cost} $，检测$ {\text{CT}}_{\text{curr}} $路径集合中的邻近冲突 (4) if 路径无冲突 then (5) return $ {\text{CT}}_{\text{curr}} $的路径集合$ \left\{{\boldsymbol{U}}_{k}\right\} $ (6) end if (7) for参与冲突的两架无人机 do (8) 创建子节点$ {\text{CT}}_{\text{child}} $，$ {\text{CT}}_{\text{child}}.\boldsymbol{C} $继承$ {\text{CT}}_{\text{curr}} $的约束集并添加新冲突约束 (9) 调用双向A*规划算法重新规划路径作为$ {\text{CT}}_{\text{child}} $的路径集合并计算$ {\text{CT}}_{\text{child}}.\text{cost} $，然后将$ {\text{CT}}_{\text{child}} $插入OPEN (10) end for (11) end while 
下载: 导出CSV
表 1 低层路径规划算法的性能对比
任务编号 加权时间成本(s) 算法运行耗时(s) Dijkstra A* 双向A* 任务1 51.3 0.35 0.13 0.10 任务2 106.0 0.84 0.60 0.35 任务3 136.7 1.31 0.74 0.59
下载: 导出CSV
-
[1] PAN Yan, CHEN Qianwu, ZHANG Nan, et al. Extending delivery range and decelerating battery aging of logistics UAVs using public buses[J]. IEEE Transactions on Mobile Computing, 2023, 22(9): 5280–5295. doi: 10.1109/TMC.2022.3167040. [2] 高思华, 刘宝煜, 惠康华, 等. 信息年龄约束下的无人机数据采集能耗优化路径规划算法[J]. 电子与信息学报, 2024, 46(10): 4024–4034. doi: 10.11999/JEIT240075.GAO Sihua, LIU Baoyu, HUI Kanghua, et al. Energy-efficient UAV trajectory planning algorithm for AoI-constrained data collection[J]. Journal of Electronics & Information Technology, 2024, 46(10): 4024–4034. doi: 10.11999/JEIT240075. [3] SHAO Xiang and WANG Wei. Truthful double auction for multiple secondary operator spectrum sharing with flexible bidding[J]. IEEE Internet of Things Journal, 2025, 12(15): 31813–31823. doi: 10.1109/JIOT.2025.3574306. [4] 陆音, 刘金志, 张珉. 一种模型辅助的联邦强化学习多无人机路径规划方法[J]. 电子与信息学报, 2025, 47(5): 1368–1380. doi: 10.11999/JEIT241055.LU Yin, LIU Jinzhi, and ZHANG Min. A model-assisted federated reinforcement learning method for multi-UAV path planning[J]. Journal of Electronics & Information Technology, 2025, 47(5): 1368–1380. doi: 10.11999/JEIT241055. [5] LI Zuguang, WANG Wei, GUO Jia, et al. Blockchain-empowered dynamic spectrum management for space-air-ground integrated network[J]. Chinese Journal of Electronics, 2022, 31(3): 456–466. doi: 10.1049/cje.2021.00.275. [6] 王威, 佘丁辰, 王加琪, 等. 多模型融合的无人机异常航迹校正方法[J]. 电子与信息学报, 2025, 47(5): 1332–1344. doi: 10.11999/JEIT241026.WANG Wei, SHE Dingchen, WANG Jiaqi, et al. Multi-model fusion-based abnormal trajectory correction method for unmanned aerial vehicles[J]. Journal of Electronics & Information Technology, 2025, 47(5): 1332–1344. doi: 10.11999/JEIT241026. [7] SHAO Xiang, WANG Wei, ZHOU Bo, et al. Joint bandwidth and spectrum usage zones flexible allocation for coexisting multiple UAV networks: An interference graph approach[J]. IEEE Internet of Things Journal, 2025, 12(15): 31141–31153. doi: 10.1109/JIOT.2025.3572085. [8] ZHAN Cheng, HU Han, LIU Zhi, et al. Interference-aware online optimization for cellular-connected multiple UAV networks with energy constraints[J]. IEEE Transactions on Mobile Computing, 2024, 23(12): 13804–13820. doi: 10.1109/TMC.2024.3438759. [9] MEER I A, OZGER M, SCHUPKE D A, et al. Mobility management for cellular-connected UAVs: Model-based versus learning-based approaches for service availability[J]. IEEE Transactions on Network and Service Management, 2024, 21(2): 2125–2139. doi: 10.1109/TNSM.2024.3353677. [10] CHEN Guqiao, CHENG Changjun, XU Xiaoli, et al. Minimizing the age of information for data collection by cellular-connected UAV[J]. IEEE Transactions on Vehicular Technology, 2023, 72(7): 9631–9635. doi: 10.1109/TVT.2023.3249747. [11] GUO Hongzhi, ZHOU Xiaoyi, WANG Jiadai, et al. Intelligent task offloading and resource allocation in digital twin based aerial computing networks[J]. IEEE Journal on Selected Areas in Communications, 2023, 41(10): 3095–3110. doi: 10.1109/JSAC.2023.3310067. [12] 陈可欣, 王威, 肖江浩, 等. 速率公平的分布式无人机资源分配方法[J]. 西安电子科技大学学报, 2025, 52(3): 48–60. doi: 10.19665/j.issn1001-2400.20250506.CHEN Kexin, WANG Wei, XIAO Jianghao, et al. Rate fairness oriented distributed resource allocation for UAVs[J]. Journal of Xidian University, 2025, 52(3): 48–60. doi: 10.19665/j.issn1001-2400.20250506. [13] ZENG Yong, XU Xiaoli, JIN Shi, et al. Simultaneous navigation and radio mapping for cellular-connected UAV with deep reinforcement learning[J]. IEEE Transactions on Wireless Communications, 2021, 20(7): 4205–4220. doi: 10.1109/TWC.2021.3056573. [14] ZHANG Shuowen and ZHANG Rui. Trajectory design for cellular-connected UAV under outage duration constraint[C]. 2019 IEEE International Conference on Communications (ICC), Shanghai, China, 2019: 1–6. doi: 10.1109/ICC.2019.8761259. [15] KHAMIDEHI B and SOUSA E S. Power efficient trajectory optimization for the cellular-connected aerial vehicles[C]. 2019 IEEE 30th Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), Istanbul, Turkey, 2019: 1–6. doi: 10.1109/PIMRC.2019.8904357. [16] AL-HOURANI A, KANDEEPAN S, and LARDNER S. Optimal LAP altitude for maximum coverage[J]. IEEE Wireless Communications Letters, 2014, 3(6): 569–572. doi: 10.1109/LWC.2014.2342736. [17] BI Suzhi, LYU Jiangbin, DING Zhi, et al. Engineering radio maps for wireless resource management[J]. IEEE Wireless Communications, 2019, 26(2): 133–141. doi: 10.1109/MWC.2019.1800146. [18] ZHANG Shuowen and ZHANG Rui. Radio map-based 3D path planning for cellular-connected UAV[J]. IEEE Transactions on Wireless Communications, 2021, 20(3): 1975–1989. doi: 10.1109/TWC.2020.3037916. [19] ZHAN Cheng and ZENG Yong. Energy minimization for cellular-connected UAV: From optimization to deep reinforcement learning[J]. IEEE Transactions on Wireless Communications, 2022, 21(7): 5541–5555. doi: 10.1109/TWC.2022.3142018. [20] GONG Qiuhu, WU Fahui, YANG Dingcheng, et al. 3D radio map reconstruction and trajectory optimization for cellular-connected UAVs[J]. Journal of Communications and Information Networks, 2023, 8(4): 357–368. doi: 10.23919/JCIN.2023.10387267. [21] CHEN Yujing, YANG Dingcheng, XIAO Lin, et al. Optimal trajectory design for unmanned aerial vehicle cargo pickup and delivery system based on radio map[J]. IEEE Transactions on Vehicular Technology, 2024, 73(8): 11706–11718. doi: 10.1109/TVT.2024.3382170. [22] CHEN Yujia and HUANG Dayu. Joint trajectory design and BS association for cellular-connected UAV: An imitation-augmented deep reinforcement learning approach[J]. IEEE Internet of Things Journal, 2022, 9(4): 2843–2858. doi: 10.1109/JIOT.2021.3093116. [23] 李安, 余传鑫, 陈成. 面向多网联无人机的MADRL协同路径规划算法[J]. 西安电子科技大学学报, 2025, 52(3): 163–175. doi: 10.19665/j.issn1001-2400.20250102.LI An, YU Chuanxin, and CHEN Cheng. Multi-agent deep reinforcement learning assisted cooperative path planning for the multi-cellular-connected unmanned aerial vehicle[J]. Journal of Xidian University, 2025, 52(3): 163–175. doi: 10.19665/j.issn1001-2400.20250102. [24] WU Di, CAO Zhuang, LIN Xudong, et al. A learning-based cooperative navigation approach for multi-UAV systems under communication coverage[J]. IEEE Transactions on Network Science and Engineering, 2025, 12(2): 763–773. doi: 10.1109/TNSE.2024.3517872. [25] XU Xiaoli and ZENG Yong. Cellular-connected UAV: Performance analysis with 3D antenna modelling[C]. 2019 IEEE International Conference on Communications Workshops (ICC Workshops), Shanghai, China, 2019: 1–6. doi: 10.1109/ICCW.2019.8756719. [26] SHARON G, STERN R, FELNER A, et al. Conflict-based search for optimal multi-agent pathfinding[J]. Artificial Intelligence, 2015, 219: 40–66. doi: 10.1016/j.artint.2014.11.006. [27] 3GPP. TR 36.777 Enhanced LTE support for aerial vehicles[S]. Sophia Antipolis: 3GPP, 2017. (查阅网上资料, 未找到本条文献出版地信息, 请确认). -
图(8) / 表(2)
计量
- 文章访问数: 48
- HTML全文浏览量: 23
- PDF下载量: 7
- 被引次数: 0
下载:
