基于改进高斯采样PRM算法和狭窄通道识别的路径规划方法.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN115061467A(43)申请公布日2022.09.16(21)申请号202210730956.1(22)申请日2022.06.24(71)申请人合肥工业大学地址230009安徽省合肥市包河区屯溪路193号(72)发明人黄云志徐玉全韩亮牛平安汪辉柴冲(74)专利代理机构合肥和瑞知识产权代理事务所(普通合伙)34118专利代理师王挺(51)Int.Cl.G05D1/02(2020.01)权利要求书1页说明书4页附图6页(54)发明名称基于改进高斯采样PRM算法和狭窄通道识别的路径规划方法(57)摘要本发明公开了基于改进高斯采样PRM算法和狭窄通道识别的路径规划方法，通过改进高斯采样增大狭窄通道内的采样点数以保证机器人在含有狭窄通道的地图中规划的实施效率，属于路径规划的技术领域。所述方法首先对路况的地图进行栅格化处理，得到栅格地图模型，设置规划的起始点和目标点；改进高斯采样应用于栅格地图狭窄通道的局部采样，增加狭窄通道的路标点数量；对局部路标点进行聚类识别处理，识别出狭窄通道；接着利用PRM算法根据路标点生成无向图；最后在无向图中根据要求查询最优路径。本发明改进PRM算法的采样策略，实现狭窄通道环境中的路径规划，增加了PRM算法在狭窄通道环境中采样点数，提高了PRM算法在狭窄通道下路径搜索的效率。CN115061467ACN115061467A权利要求书1/1页1.基于改进高斯采样PRM算法和狭窄通道识别的路径规划方法，其特征在于，在高斯采样阶段限制其采样点分布的位置，增加PRM算法在狭窄通道的采样点数量；提出基于密度的聚类识别狭窄通道的方法，将环境中的狭窄通道准确的识别出来。2.根据权利要求1所述的基于改进高斯采样PRM算法和狭窄通道识别的路径规划方法，其特征在于，根据狭窄通道的几何特征，对于高斯采样算法中的每一采样点，通过在障碍物空间的采样点A(x1,y1)和自由空间的采样点B(x2,y2)的有向线段的延长线上选取一点C(x3,y3)，若点C位于障碍物空间上，则自由空间的采样点B同时位于狭窄通道；点C的计算如下：假设点A(x1,y1)和点B(x2,y2)分别位于障碍物空间和自由空间，如果点B位于狭窄通道，则的斜率Kab：若点C位于障碍物空间，存在参数α使得在有向线段延长线上存在一点C，C(x3,y3)坐标为：狭窄通道采样点的获取方式如下所示：S1，首先根据高斯采样原理得到障碍物空间的采样点A和自由空间的采样点B，在此基础上计算点A到点B的有向线段的斜率Kab，以此计算出点A和点B的直线方程；S2，根据步骤S1的直线方程和参数α得到点C，判断C的位置，如果C位于障碍物空间，则将点B作为狭窄通道采样点加入狭窄通道样本集，否则更新点A和点B进行下一次的选择；S3，按照以下步骤循环：更新点A和点B，并通过更新的点A和点B重复进行步骤S1～S2；S4，当所述狭窄通道内的采样点个数达到预先设定的狭窄通道采样点阈值时，停止检测。3.根据权利要求1或2所述的基于改进高斯采样PRM算法和狭窄通道识别的路径规划方法，其特征在于，S5，使用基于密度的聚类算法DBSCAN对狭窄通道样本集中的采样点进行识别处理，设置聚类算法中的密度区域ξ和区域样本个数minPts，区分出噪声点，识别出狭窄通道；S6，得到狭窄通道处理后的样本集。4.根据权利要求1或2所述的基于改进高斯采样PRM算法和狭窄通道识别的路径规划方法，其特征在于，在非狭窄通道进行均匀采样，得到非狭窄通道样本集，狭窄通道的样本集和均匀采样得到的样本集添加到总样本集中，根据总样本集生成连通图，在连通图中进行PRM路径规划。2CN115061467A说明书1/4页基于改进高斯采样PRM算法和狭窄通道识别的路径规划方法技术领域[0001]本发明涉及机器人路径规划技术领域，尤其是基于改进高斯采样PRM算法和狭窄通道识别的路径规划方法。背景技术[0002]PRM算法是一种基于随机概率图的路径规划方法，当环境中存在诸如狭窄通道环境时，PRM算法的性能急剧下降，虽然可以通过大量采样进行弥补狭窄通道采样概率低的问题，但是这增加了离线学习阶段构建高连通性路线图的计算时间，导致PRM算法的效率低下。为了提高路线图狭窄通道环境的实施效率，学者们提出了许多针对PRM算法的改进。中国专利CN110411454A提出一种改进随机路径图法的移动机器人路径规划方法，使用自适应采样和高斯采样相结合的方法提高在狭窄通道的采样点数量，从而提高机器人在含有困难区域(如狭窄通道)地图路径规划的实时效率，该方法利用地图环境中的障碍物密度进行自适应采样，虽然提高了狭窄通道内的采样点密度，但是在障碍物周围也会存在大量的采样点，降低算法性能。中国专利CN109683630A提出了