CBS框架下面向复杂地图的低拓展度A^(*)算法

作     者：宣志玮 毛剑琳 张凯翔 XUAN Zhi-wei;MAO Jian-lin;ZHANG Kai-xiang

作者机构：昆明理工大学信息工程与自动化学院云南昆明650500 昆明理工大学机电工程学院云南昆明650500 

出 版 物：《电子学报》 (Acta Electronica Sinica)

年 卷 期：2022年第50卷第8期

页      面：1943-1950页

核心收录：

学科分类：080202[工学-机械电子工程] 08[工学] 0804[工学-仪器科学与技术] 0802[工学-机械工程] 

基　　金：云南省重大科技专项计划项目(No.202002AC080001) 

主　　题：A^(*)算法 路径规划 Delaunay三角剖分 移动机器人 冲突消解 

摘      要：A^(*)算法是机器人路径规划问题中的重要且常用算法之一,在地形复杂的大型地图中,路径点之间的不可视造成A^(*)算法需要大规模节点拓展才能找到可行的优化路径,由此导致算法对存储空间的需求剧增和求解效率的降低.对此,本文针对基于冲突搜索(Conflict-Based Search,CBS)框架下的低层路径规划问题,引入三角剖分方法,给出固定障碍处理方法,融合可视性优化获得相邻点可视的优化路径,在此基础上提出分段策略,令具有动态冲突处理能力的A^(*)算法依相邻可视点进行分段路径规划,最终获得低节点拓展度A^(*)路径规划算法.通过标准地图数据集的仿真实验表明,在复杂地图下本文提出的算法路径长度为A^(*)算法的98.1%~102.2%,节点拓展量降低85.4%,算法求解时间减少58.1%.