一种基于改进BIT*的移动机器人全局路径规划方法.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN115903789A(43)申请公布日2023.04.04(21)申请号202211333294.0(22)申请日2022.10.28(71)申请人浙江工业大学地址310014浙江省杭州市拱墅区潮王路18号(72)发明人潘柏松贺帅张科文郑磊(74)专利代理机构杭州浙科专利事务所(普通合伙)33213专利代理师汤明(51)Int.Cl.G05D1/02(2020.01)权利要求书2页说明书6页附图6页(54)发明名称一种基于改进BIT*的移动机器人全局路径规划方法(57)摘要本发明公开了一种基于改进BIT*的移动机器人全局路径规划方法。该方法包括：获取环境地图和移动机器人起始点与目标点；以移动机器人起始点为根节点构建BIT*拓展树；通过改进的BIT*算法进行路径规划，生成一条无碰撞可执行路径。该方法通过四方面对BIT*进行改进：1)基于移动机器人尺寸的地图膨胀化，提高生成路径的安全性；2)引入动态自适应步长，提高算法运行效率；3)增加环境信息因子改进估计成本函数，提高算法采样有效率；4)增加二次逆向剪枝函数，减少路径拐点个数。通过仿真分析,验证基于改进BIT*算法的移动机器人路径规划安全系数更高,路径拐点更少,搜索路径所需时间更短。CN115903789ACN115903789A权利要求书1/2页1.一种基于改进BIT*的移动机器人全局路径规划方法，其特征在于，包括以下步骤：S1：获取环境地图、并基于移动机器人的尺寸对地图中的障碍物进行膨胀化；S2：确定移动机器人的起始点，目标点的位置坐标、基准生长步长r、最大迭代次数并以移动机器人起始点为根节点构建拓展树；S3：判断树边和树节点优先队列是否为空，若为空则执行S4；否则执行S6；S4：根据当前可行路径长度与起始点、目标点的位置坐标，生成采样椭圆域，执行剪枝操作和采样操作并将结果添加到树节点和树边的队列中；S5：根据最小估计成本对树节点和树边的队列进行排序，生成树节点优先队列和树边优先队列；S6：进行最小估计成本判断后获取树节点优先队列中最小估计成本的树节点进行扩展；S7：进行最小估计成本、估计成本、真实成本判断后，获取树边优先队列中最小估计成本的树边作为最优待扩展边进行扩展；S8：判断最优待扩展边的终端点是否在树节点列表中，若是则执行重新布线操作，然后将树边和树节点优先队列全部置空；否则扩展这条边；S9：判断是否达到迭代次数，若是则输出当前路径节点，否则执行S4；S10：对当前路径节点进行二次逆向剪枝，输出可执行路径。2.根据权利要求1所述的一种基于改进BIT*的移动机器人全局路径规划方法，其特征在于，所述S1中地图障碍物膨胀化按照以下方式进行膨胀：Dex＝Erob/αs(Eobs＞0,1＞αs＞0)其中，Dex为障碍物膨胀的距离，Erob为移动机器人边缘到几何中心的最大距离，αs为安全扩展因子。3.根据权利要求1所述的一种基于改进BIT*的移动机器人全局路径规划方法，其特征在于，S5、S6、S7中所述最小估计成本为：其中Vvalue指树节点优先队列中最小估计成本，gT(v)表示从给定当前树的起点到点v的真实成本，即路径长度，TreeQV表示树节点优先队列，TreeQE表示树边优先队列，Evalue指树边优先队列中最小估计成本，calcdist(v,x)为返回欧几里得范数，hestimated(x)表示点x到目标点的估计成本，hestimated(v)表示点v到目标点的估计成本由以下公式确定：hestimated(v)＝calcdist(v,x_goal)+βdestimated(v)式中calcdist(v,x_goal)为返回欧几里得范数，β表示环境信息因子，destimated(v)表示点v与最近障碍物的距离。4.根据权利要求1所述的基于改进BIT*的移动机器人全局路径规划方法，其特征在于，S6中所述获取树节点优先队列，以自适应动态步长为扩展圆半径，获取树节点优先队列中扩展圆范围内的树节点，自适应动态步长由以下公式确定：2CN115903789A权利要求书2/2页其中，r为基础步长，δ为扩展圆距离因子，ε为扩展圆面积因子，scover为以基础步长为半径的扩展圆与障碍物之间重合的面积，sr为基础扩展圆面积。5.根据权利要求1所述的基于改进BIT*的移动机器人全局路径规划方法，其特征在于，S10中所述二次逆向剪枝包括以下步骤：S10.1：获取当前路径节点列表，将目标点赋值给node；S10.2：执行碰撞判断函数：其中，node为当前判断起始节点，nodepar为其父节点，nodegrand为nodepar父节点，若产生碰撞执行S10.2，否则执行S10.3；S10.2：将nodepar赋值给node，将node添加