摘要
A^(*)算法是机器人路径规划问题中的重要且常用算法之一,在地形复杂的大型地图中,路径点之间的不可视造成A^(*)算法需要大规模节点拓展才能找到可行的优化路径,由此导致算法对存储空间的需求剧增和求解效率的降低.对此,本文针对基于冲突搜索(Conflict-Based Search,CBS)框架下的低层路径规划问题,引入三角剖分方法,给出固定障碍处理方法,融合可视性优化获得相邻点可视的优化路径,在此基础上提出分段策略,令具有动态冲突处理能力的A^(*)算法依相邻可视点进行分段路径规划,最终获得低节点拓展度A^(*)路径规划算法.通过标准地图数据集的仿真实验表明,在复杂地图下本文提出的算法路径长度为A^(*)算法的98.1%~102.2%,节点拓展量降低85.4%,算法求解时间减少58.1%.
A^(*) algorithm is one of the important and commonly used algorithms in path planning of robots.In large map with complex terrain,large-scale node expansion is needed in A^(*) algorithm to find a feasible optimization path in the case of invisibility between path points.This leads to a sharp increase in the demand for storage space and a decrease in running efficiency of the algorithm.To solve low-level path planning problems based on CBS(Conflict-Based Search)framework,an A^(*) path planning algorithm with low node expansion is proposed.Triangulation method and fixed obstacle processing method are introduced to obtain an optimized path that is visible to adjacent points.Moreover,a segmentation strategy is proposed based on integrated visibility optimization to plan the segmented path according to the adjacent visible points with dynamic collision processing ability.Simulation experiments on standard map data sets under complex terrain show that the path length of the proposed algorithm in this paper is 98.1%~102.2%as long as that of A^(*) algorithm,compared with which,the amount of node expansion reduces by 85.4%and the running time of algorithm reduces by 58.1%.
作者
宣志玮
毛剑琳
张凯翔
XUAN Zhi-wei;MAO Jian-lin;ZHANG Kai-xiang(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming,Yunnan 650500,China;Faculty of Mechanical and Electrical Engineering,Kunming University of Science and Technology,Kunming,Yunnan 650500,China)
出处
《电子学报》
EI
CAS
CSCD
北大核心
2022年第8期1943-1950,共8页
Acta Electronica Sinica
基金
云南省重大科技专项计划项目(No.202002AC080001)。
