技术摘要：
本发明公开了一种基于双层图的大尺度已知环境地图创建方法，包括以下步骤：S1，使用九宫格方法对平面栅格地图进行分割；S2，构建第一层图模型；S3，构建第二层图模型。本发明针对大尺度已知环境下的轨迹规划问题，提前构建地图中的凸安全节点，从而构建双层图模型，避  全部
背景技术：
目前，环境地图是移动机器人在当前环境下实现自主导航的关键部分，机器人地 图创建问题，在结构化、静态、小尺度环境下已经取得很多研究成果，但对于大尺度环境下 的研究还不够成熟，在移动机器人领域最常见的地图是栅格地图，但是当栅格地图的尺寸 和分辨率提高时，将会大大降低路径搜索的效率，传统的基于切线图和Voronoi图轨迹规划 方法虽然能够解决这些问题，但是传统方法对障碍物的边缘和顶点比较敏感，当障碍物的 边缘是曲线或者无顶点时，切线图和Voronoi图方法均难以应用，并且传统方法生成的小车 轨迹质量不高等诸多问题。
技术实现要素：
本发明的主要目的在于提供一种基于双层图的大尺度已知环境地图创建方法。 本发明采用的技术方案是：一种基于双层图的大尺度已知环境地图创建方法，包 括以下步骤： S1，使用九宫格方法对平面栅格地图进行分割； S2，构建第一层图模型； S3，构建第二层图模型。 进一步地，所述步骤S1包括： S11，读取平面栅格地图，其中黑色部分表示经过膨胀的障碍物，白色部分表示移动小 车的可行通道； S12，将步骤S11中的地图划分为9个大小相同的方块； S13，对方块4和方块5进一步分割； S14，重复步骤S13，一直分割到地图中的格子分为两类，第一类是完全不包含障碍物的 格子，第二类是完全包含障碍物的格子； S15，对格子的面积设置一个最小阈值，当分割的格子面积小于这个阈值时则不再分 割，具体阈值设置为多少需要根据地图中障碍物的复杂度和需要的精度进行设置； S16，步骤S15中设置阈值的方法会产生大量的第三类格子，这类格子只包含部分障碍 物，将这类格子当作第二类格子。 更进一步地，所述步骤S2包括： S21，创建第一层节点； S22，创建第一层边。 更进一步地，所述步骤S21包括： S211，创建存储所有节点的空结构体nodes； 4 CN 111599009 A 说　明　书 2/6 页 S212，取出其中一个第一类格子，创建该第一类格子对应的新节点； S213，设置第一类格子的节点id； S214，计算第一类格子的中心坐标并存储在当前节点中； S215，计算第一类格子的长和宽并存储在当前节点中； S216，计算左下角坐标、右上角坐标等，存储到当前节点中； S217，将该节点放入存储所有节点的结构体nodes中； S218，重复以上步骤S212到步骤S217，直到所有第一类格子都转化为节点。 更进一步地，所述步骤S22包括： 遍历每个节点，并且对节点进行一个像素的膨胀，如果有其它节点与之重叠则存在相 邻关系，具体步骤为： S221，创建一个二维的结构体edges，第一维表示当前节点的id，第二维表示当前节点 的相邻节点； S222，在第一层节点集中取出一个未遍历过的节点node； S223，将节点node的四条边进行膨胀，得到膨胀后的边缘； S224，判断膨胀后边缘与哪些节点有重叠关系； S225，遍历每一个有重叠关系的节点，计算当前节点和相邻节点中心的欧式距离； S226，根据当前节点的索引id、相邻节点的索引id和欧式距离等信息创建一个新的边； S227，将新的边加入到结构体edges中； S228，重复上述步骤5到步骤7，直到当前节点与所有相邻节点的边相邻关系都加入到 结构体edges中； S229，重复上述步骤S222到步骤S228，直到第一层中的所有节点都已经遍历过为止。 更进一步地，所述步骤S3包括： S31，创建第二层节点； S32，创建第二层边。 更进一步地，所述步骤S31包括： 重复使用第一层中的节点即可，创建第二层中第二类节点；将未被包含的第一层节点 进行最大膨胀得到所有可能存在的凸安全节点； 创建凸安全节点的具体步骤为： S311，创建第二层图模型中凸安全节点的结构体； S312，从第一层图模型中取出一个未遍历过并且未被包含的节点； S313，将该节点的边缘进行膨胀，当某一个方向碰到障碍物时则立即停止该方向的膨 胀，并且继续其余方向的膨胀，直到所有方向都碰到障碍时，得到一个凸安全节点的形状和 大小； S314，判断当前凸安全节点都包含了第一层图模型中的哪些节点，并且将这些节点标 记为已遍历过的节点，下次进行步骤S312时不再遍历； S315，设置该凸安全节点的索引id，计算左下角坐标和右上角坐标； S316，将步骤S315中的信息和步骤S314中包含的第一层节点id都保存到当前凸安全节 点中，并且将该凸安全节点插入到第二层图模型中； S317，重复上述步骤S312到步骤S316，直到第一层图模型中的所有节点都被包含为止， 5 CN 111599009 A 说　明　书 3/6 页 此时地图中所有不重复的凸安全节点均以创建完成。 更进一步地，所述步骤S32包括： 遍历第一层节点加入对应凸安全节点的id，具体步骤如下： S321，遍历所有凸安全节点，取出其中一个凸安全节点node_expand； S322，遍历当前凸安全节点包含的所有第一层节点，并且取出其中一个节点node； S323，将当前凸安全节点node_expand的id信息保存到当前节点node中； 重复步骤S321到步骤S323。 本发明的优点： 本发明针对大尺度已知环境下的轨迹规划问题，提前构建地图中的凸安全节点，从而 构建双层图模型，避免了在实时规划过程中重复生成凸安全区域造成的效率降低问题，进 一步提升了大尺度已知环境下轨迹规划的速度，无需在实时的规划中重新生成凸安全节 点，减少了机器人在实时规划中的计算量。与传统的基于切线图和Voronoi图轨迹规划方法 相比，本专利的方法在第二层图模型中凸安全节点上生成轨迹的质量更高。 除了上面所描述的目的、特征和优点之外，本发明还有其它的目的、特征和优点。 下面将参照图，对本发明作进一步详细的说明。 附图说明 构成本申请的一部分的附图用来提供对本发明的进一步理解，本发明的示意性实 施例及其说明用于解释本发明，并不构成对本发明的不当限定。 图1是本发明的平面栅格地图示意图； 图2是本发明的第一次九宫格划分图； 图3是本发明的第二次九宫格划分图； 图4是本发明的九宫格分割效果图； 图5是本发明的节点膨胀过程示意图（a为节点膨胀方向图，b为当某一方向碰障碍物时 的图）； 图6是本发明的简单的平面栅格地图； 图7是本发明的九宫格分割图； 图8是本发明的第一层图模型图； 图9是本发明的凸安全节点示意图； 图10是本发明的第二层图模型图。