Improved HCA* Path Planning for UAS Traffic Management

doi:10.3778/j.issn.1002-8331.2309-0333

Abstract

Abstract: Aiming at the pre?flight conflict detection and resolution (CDR) problem in unmanned aerial vehicle traffic management (UTM), it is represented as a new version of multi-agent path finding (MAPF) model, a continuous-time hierarchical cooperative A*(CHCA*) algorithm is proposed. Firstly, agents continuously move between positions in the metric space at maximum speed in a continuous search space. Secondly, the size and shape of the agent are considered to determine conflicts based on whether their shapes overlap. Finally, the search heuristic value calculation is optimized. Experiments have shown that the success rate of CHCA* is higher than continuous-time conflict-based search (CCBS) on one-shot path planning, CHCA* is suitable for solving large-scale problems. The simulation experiment on a consultancy study of predicted UAV traffic for delivery services in Sendai, Japan, 2030, shows that for 32?887 random requests in a day, the success rate of CHCA* approaches up to 96%.

Key words: multi-agent path finding (MAPF), unmanned aircraft system traffic management (UTM), continuous-time hierarchical cooperative A*(CHCA*) algorithm, conflict detection, conflict resolution, continuous time

摘要： 针对无人机交通管理中飞行前冲突探测与解脱问题，表示为一种新的多智能体路径规划扩展模型，提出一种连续时间分层合作A*（continuous-time hierarchical cooperative A*，CHCA*）算法。面向连续时间，智能体在度量空间中的位置之间以最大速度持续移动；考虑智能体的大小形状，以空间是否覆盖判定智能体冲突；优化搜索启发值计算。实验表明，CHCA*单次路径规划成功率高于CCBS，适合大规模智能体路径规划求解；在日本仙台2030无人机空运预测模型上仿真实验表明，对于一天内32?887个随机请求，CHCA*算法规划成功率可达96%。

关键词: 多智能体路径规划（MAPF）, 无人机交通管理（UTM）, 改进分层合作A*算法, 冲突探测, 冲突解脱, 连续时间

CHEN Ming, HE Ning, HONG Chen, XIAO Mingming, JING Hongyuan. Improved HCA* Path Planning for UAS Traffic Management[J]. Computer Engineering and Applications, 2025, 61(6): 361-368.

陈明, 何宁, 宏晨, 肖明明, 景竑元. 改进分层合作A*的无人机交通管理中路径规划[J]. 计算机工程与应用, 2025, 61(6): 361-368.

References

[1] KOPARDEKAR P, RIOS J, PREVOT T, et al. Unmanned aircraft system traffic management (UTM) concept of operations[C]//Proceedings of AIAA Aviation Technology, Integration, and Operations Conference, 2016.
[2] 张洪海, 邹依原, 张启钱, 等. 未来城市空中交通管理研究综述[J]. 航空学报, 2021, 42(7): 82-106.
ZHANG H H, ZOU Y Y, ZHANG Q Q, et al. Future urban air mobility management: review[J]. Acta Aeronautica et Astronautica Sinica, 2021, 42(7): 82-106.
[3] JENIE Y I, KAMPEN E, ELLERBROEK J, et al. Taxonomy of conflict detection and resolution approaches for unmanned aerial vehicle in an integrated airspace[J]. IEEE Transactions on Intelligent Transportation Systems, 2016, 18(3): 558-567.
[4] 刘继新, 蒋伶潇, 刘禹汐, 等. 无人机冲突探测与解脱技术研究概述[J]. 科学技术与工程, 2023, 23(26): 11081-11089.
LIU J X, JIANG L X, LIU Y X, et al. Research on UAV conflict detection and resolution technology[J]. Science Technology and Engineering, 2023, 23(26): 11081-11089.
[5] HO F, SALTA A, GERALDES R, et al. Multi-agent path finding for UAV traffic management[C]//Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019: 131-139.
[6] 刘志飞, 曹雷, 赖俊, 等. 多智能体路径规划综述[J]. 计算机工程与应用, 2022, 58(20): 43-64.
LIU Z F, CAO L, LAI J, et al. Overview of multi-agent path finding[J]. Computer Engineering and Applications, 2022, 58(20): 43-64.
[7] STERN R, STURTEVANT N, FELNER A, et al. Multi-agent pathfinding: definitions, variants, and benchmarks[C]//Proceedings of the Twelfth Annual Symposium on Combinatorial Search, 2019.
[8] WALKER T T, STURTEVANT N R, FELNER A. Extended increasing cost tree search for non-unit cost domains[C]//Proceedings of the Twenty Seventh International Joint Conference on Artificial Intelligence, 2018: 534-540.
[9] LI J, TINKA A, KIESEL S, et al. Lifelong multi-agent path finding in large-scale warehouses[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2021: 11272-11281.
[10] SILVER D. Cooperative pathfinding[C]//Proceedings of the First Artificial Intelligence and Interactive Digital Entertainment Conference, 2005: 117-122.
[11] SHARON G, STERN R, FELNER A, et al. Conflict-based search for optimal multi-agent pathfinding[J]. Artificial Intelligence, 2015, 219(2): 40-66.
[12] BARER M, SHARON G, STERN R, et al. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem[C]//Proceedings of the Seventh Annual Symposium on Combinatorial Search, 2014.
[13] JONES M, DJAHEL S, WELSH K. Path-planning for unmanned aerial vehicles with environment complexity considerations: a survey[J]. ACM Computing Surveys, 2022, 55(11): 1-39.
[14] HO F, GONCALVES A, RIGAULT B, et al. Multi-agent path finding in unmanned aircraft system traffic management with scheduling and speed variation[J]. IEEE Intelligent Transportation Systems Magazine, 2022, 14(5): 8-21.
[15] AI B, JIANG J C, YU S S, et al. Multi-agent path finding with heterogeneous edges and roundtrips[J]. Knowledge-Based Systems, 2021, 234(5): 107554.
[16] HE X Y, HE F, LI L S, et al. A route network planning method for urban air delivery[J]. Transportation Research Part E: Logistics and Transportation Review, 2022, 166: 102872.
[17] GUGAN G, HAQUE A. Path planning for autonomous drones: challenges and future directions[J]. Drones, 2023, 7(3): 169.
[18] P?TTER NETO C A, DE CARVALHO BERTOLI G, SAOTOME O. 2D and 3D A* algorithm comparison for UAS traffic management systems[C]//Proceedings of the 2020 International Conference on Unmanned Aircraft Systems (ICUAS), Athens, Greece, 2020: 72-76.
[19] ZAMMIT C, VAN KAMPEN E. Comparison between A* and RRT algorithms for UAV path planning[C]//Proceedings of the 2018 AIAA Guidance, Navigation, and Control Conference, 2018.
[20] 徐伟华, 聊士超, 张根瑞, 等. 改进Theta*算法的物流无人机城域三维路径规划[J]. 计算机工程与应用, 2023, 59(17): 334-340.
XU W H, LIAO S C, ZHANG G R, et al. 3D path planning of logistics UAV based on improved Theta* algorithm in metropolitan area[J]. Computer Engineering and Applications, 2023, 59(17): 334-340.
[21] CANNY J, REIF J. New lower bound techniques for robot motion planning problems[C]//Proceedings of the 28th Annual Symposium on Foundations of Computer Science (SFCS 1987), Los Angeles, CA, USA, 1987: 49-60.
[22] 甄然, 王攀, 武晓晶, 等. 基于量子遗传算法的无人机冲突解脱方法[J]. 科学技术与工程, 2020, 20(17): 6963-6969.
ZHEN R, WANG P, WU X J, et al. A method of UAVs conflict resolution based on quantum genetic algorithm[J]. Science Technology and Engineering, 2020, 20(17): 6963-6969.
[23] OOSEDO A, HATTORI H, YASUI I, et al. Unmanned aircraft system traffic management (UTM) simulation of drone delivery models in 2030 Japan[J]. Journal of Robotics and Mechatronics, 2021, 33(2): 348-362.
[24] JIANG T, GELLER J, NI D, et al. Unmanned aircraft system traffic management: concept of operation and system architecture[J]. International Journal of Transportation Science and Technology, 2016, 5(3): 123-135.
[25] LAPPAS V, ZOUMPONOS G, KOSTOPOULOS V, et al. EuroDRONE, a European UTM testbed for U-Space[C]//Proceedings of the 2020 International Conference on Unmanned Aircraft Systems (ICUAS), Athens, Greece, 2020: 1766-1774.
[26] XU C C, LIAO X H, TAN J M, et al. Recent research progress of unmanned aerial vehicle regulation policies and technologies in urban low altitude[J]. IEEE Access, 2020, 8: 74175-74194.
[27] MOHAMED B, CHI W C, WANG Z K, et al. Preliminary concept of adaptive urban airspace management for unmanned aircraft operations[C]//Proceedings of the 2018 AIAA Information Systems-AIAA Infotech, 2018.
[28] JUNG K, KIM S, JUNG B, et al. UTM Architecture and flight demonstration in Korea[J]. Aerospace, 2022, 9(11): 650.
[29] XUE M, RIOS J, SILVA J, et al. Fe3: an evaluation tool for low-altitude air traffic operations[C]//Proceedings of the 2018 Aviation Technology, Integration, and Operations Conference, Atlanta, Georgia, 2018.
[30] MILLAN-ROMERA J A, ACEVEDO J J, CASTA?O á R, et al. A UTM simulator based on ROS and Gazebo[C]//Proceedings of the 2019 Workshop on Research, Education and Development of Unmanned Aerial Systems (RED UAS), Cranfield, UK, 2019: 132-141.
[31] RIVERA N, HERNáNDEZ C, HORMAZáBAL N, et al. The 2k neighborhoods for grid path planning[J]. Journal of Artificial Intelligence Research, 2020, 67: 81-113.
[32] GUY S, KARAMOUZAS I. Guide to anticipatory collision avoidance[M]//Game AI Pro 2: collected wisdom of game AI professionals.[S.l.]: CRC Press, 2019: 195-208.
[33] ANDREYCHUK A, YAKOVLEV K, ATZMON D, et al. Multi-agent pathfinding with continuous time[C]//Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19), 2019: 39-45.
[34] ANDREYCHUK A, YAKOVLEV K, BOYARSKI E, et al. Improving continuous-time conflict based search[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2021: 11220-11227.