一种基于类三维地图的移动机器人全局路径规划方法

摘要

本发明公开了一种基于类三维地图的移动机器人全局路径规划方法，步骤1：将普通栅格地图改造为基于等高线原理的类三维地图；步骤2：初始规划：将移动机器人的起点和终点连成一条直线作为当前路径；步骤3：扫描当前路径穿过的栅格，若未扫描到障碍，则转至步骤6；若扫描到障碍，则根据障碍类型转至步骤4或步骤5；步骤4：处理与边界接触的障碍，更新当前路径，返回步骤3；步骤5：处理不与边界接触的障碍，更新当前路径，返回步骤3；步骤6：输出当前路径，全局路径规划完成。本发明充分发掘障碍物信息，提高程序执行效率、易于实现，满足移动机器人全局路径规划的实时性要求。

主权项

1.一种基于类三维地图的移动机器人全局路径规划方法，其特征在于，包括以下步骤：步骤1：将普通栅格地图改造为基于等高线原理的类三维地图；步骤2：初始规划：将移动机器人的起点和终点连成一条直线作为当前路径；步骤3：扫描当前路径穿过的栅格，若未扫描到障碍，则转至步骤6；若扫描到障碍，则首先确定障碍的类型，障碍的类型包括与边界接触的障碍和不与边界接触的障碍；如果是与边界接触的障碍，转至步骤4，否则转至步骤5；所述的与边界接触的障碍包括只与一侧边界接触的障碍以及与两侧边界接触的障碍；步骤4：处理与边界接触的障碍，更新当前路径，返回步骤3；步骤5：处理不与边界接触的障碍，更新当前路径，返回步骤3；步骤6：输出当前路径，全局路径规划完成；所述的步骤1的具体步骤为：给普通栅格地图建立I、J坐标系，普通栅格地图中的栅格用数组ZG表示；数组ZG的元素ZG[I][J]表示高度值；依据等高线原理建立类三维地图，就是给普通栅格地图中的每一个栅格点都赋予高度值，ZG[I][J]＝H，H∈{0、1、2、3……}，H值越大表示高度越高；普通栅格地图分为两种区域：自由区域与障碍区域，自由区域的高度值H＝0；障碍区域的高度值H＞0，障碍区域分为三种：不与边界接触的障碍区域，只与一侧边界接触的障碍区域，与两侧边界接触的障碍区域；只与一侧边界接触的障碍区域以及与两侧边界接触的障碍区域对应的障碍统称为障碍；以下分三种情况说明障碍区域的类三维地图的创建方法：I、对于不与边界接触的障碍区域：i找出该区域I坐标的最大值Imax、I坐标的最小值Imin、J坐标的最大值Jmax、J坐标的最小值Jmin；ii给该区域的所有I＝Imax和I＝Imin的两列栅格的高度值赋予1，给该区域的所有I＝(Imax-1)和I＝(Imin+1)的两列栅格的高度值赋予2，给该区域的所有I＝(Imax-2)和I＝(Imin+2)的两列栅格的高度值赋予3，依此类推，直到该区域所有的栅格都被赋予一个高度值；iii给该区域的所有J＝Jmax和J＝Jmin的两行栅格的高度值加上1，给该区域的所有J＝(Jmax-1)和J＝(Jmin+1)的两行栅格的高度值加上2，给该区域的所有J＝(Jmax-2)和J＝(Jmin+2)的两行栅格的高度值加上3，依此类推，直到该区域所有的栅格都被加上一个高度值；II、对于只与一侧边界接触的障碍区域：i找出该区域I坐标的最大值Imax、I坐标的最小值Imin、J坐标的最大值Jmax、J坐标的最小值Jmin；ii判断Imax、Imin、Jmax、Jmin四个值中哪个为边界值，即：判断障碍区域与普通栅格地图的上、下、左、右四个边界中的哪个接触，从与普通栅格地图的上、下、左、右四个边界中与障碍区域接触的边界相对的一侧开始给障碍区域赋予高度值；给障碍区域中离该边界最远的一行或一列栅格赋予高度值1，给离该边界第二远的一行或一列栅格赋予高度值2，给离该边界第三远的一行或一列栅格赋予高度值3，依此类推，直到离该边界最近的一行或一列栅格也被赋予高度值；iii然后从另一个方向开始给障碍区域的栅格加上高度值，即：不妨设上一步中是按I坐标方向给栅格赋值，则本步骤中按J坐标方向给栅格加上高度值；给该区域的所有J＝Jmax和J＝Jmin的两行栅格的高度值加上1，给该区域的所有J＝(Jmax-1)和J＝(Jmin+1)的两行栅格的高度值加上2，给该区域的所有J＝(Jmax-2)和J＝(Jmin+2)的两行栅格的高度值加上3，依此类推，直到该区域所有的栅格都被加上一个高度值；III、对于与两侧边界接触的障碍区域：i找出该区域I坐标的最大值Imax、I坐标的最小值Imin、J坐标的最大值Jmax、J坐标的最小值Jmin；ii判断Imax、Imin、Jmax、Jmin四个值中哪两个为边界值，即：判断障碍区域与地图的上、下、左、右四个边界中的哪两个边界接触，然后从两个被接触的边界中任选一个，从与所选的边界相对的一侧开始给障碍区域赋予高度值；不妨设选择行对应的边界为参照，给离该边界最远的一行栅格赋予高度值1，给离该边界第二远的一行栅格赋予高度值2，给离该边界第三远的一行栅格赋予高度值3，依此类推，直到离该边界最近的一行栅格也被赋予高度值；然后从与另一边界相对的一侧开始给障碍区域加上高度值；给离另一边界最远的一列栅格的高度值加上1，给离另一边界第二远的一列栅格的高度值加上2，给离另一边界第三远的一列栅格的高度值加上3，依此类推，直到离另一边界最近的一列栅格也被加上高度值；所述的步骤4中的处理与边界接触的障碍的步骤以及所述的步骤5中的处理不与边界接触的障碍的步骤为：当前路径上每段位于与边界接触的障碍区域的路径段按照下降方向进行基本规划；定义下降方向：若路径穿过了某个障碍区域，则以位于障碍区域内的路径段中高度最大的点为起点，垂直于该路径段且所经过的栅格的高度值降低的方向就是下降方向；定义基本规划：若两点之间的初始规划路径穿过了障碍区域，则找到每段位于障碍区域的路径的下降方向，然后将每段位于障碍区域的路径用沿着障碍区域从下降方向绕过障碍区域的新路径段代替，基本规划就是对初始规划进行修正，基本规划后的路径段称为修正路径段；具体步骤分为以下四步：I、找出当前路径上每段位于与边界接触的障碍区域的路径段的起点与终点，修正路径段上的点(Iy，Jy)需满足以下三个条件：第一个条件：位于下降方向一侧，即，满足下式：$(\mathrm{Jy}-\frac{1}{k}\mathrm{Iy}+\frac{\mathrm{In}}{k}-\mathrm{Jn})\times (\mathrm{Jam}-\frac{1}{k}\mathrm{Iam}+\frac{\mathrm{In}}{k}-\mathrm{Jn})\le 0;$式中：(Im，Jm)为该段穿过了障碍区域的路径段的起点坐标，(In，Jn)为该段穿过了障碍区域的路径段的终点坐标，(Iam，Jam)为该障碍区域的高度值最大的点的坐标；第二个条件：高度值为0，ZG[Iy][Jy]＝0；第三个条件：与对应的障碍区域直接相邻；II、找出被当前路径穿过的每一块与边界接触的障碍区域的犄角点；定义犄角点：在基本规划中，修正路径段上的点中与被修正路径段的距离最大的点就是犄角点；III、找出与当前路径的每一段直线路径段对应的中转点；在所有的位于当前路径同一侧的犄角点中离当前路径最远的点，称为与当前路径对应的中转点；若当前路径为折线，则要找出与折线的每一段直线路径段对应的中转点；IV、将起点、所有中转点以及终点沿当前路径的方向用折线顺次连接起来，将新得到的折线路径作为当前路径；转到步骤3。