改进分层合作A*的无人机交通管理中路径规划  

Improved HCA*Path Planning for UAS Traffic Management

作　　者：陈明 何宁 宏晨 肖明明 景竑元 CHEN Ming;HE Ning;HONG Chen;XIAO Mingming;JING Hongyuan(Beijing Key Laboratory of Information Service Engineering,Beijing Union University,Beijing 100101,China;College of Smart City,Beijing Union University,Beijing 100101,China;College of Robotics,Beijing Union University,Beijing 100101,China)

机构地区：[1]北京联合大学北京市信息服务工程重点实验室,北京100101 [2]北京联合大学智慧城市学院,北京100101 [3]北京联合大学机器人学院,北京100101

出　　处：《计算机工程与应用》2025年第6期361-368,共8页Computer Engineering and Applications

基　　金：国家重点研发计划(2018AAA0100804);国家自然科学基金(61872042,61572077)。

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

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

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]