CN115454044A - 一种基于骨架图的快速找座方法、系统和芯片 - Google Patents

Abstract

本发明公开了一种基于骨架图的快速找座方法、系统和芯片，本发明所述的方法通过对表示全局地图连通性的骨架图上的空旷点和边界点进行排序，使得移动机器人可以有序地探索地图；通过空旷点进行移动，使得移动机器人避免不必要的碰撞，提高移动效率；通过边界点进行回座信号检测，且同一集合内的边界点不重复检测，使得移动机器人提高了找座效率。

Description

一种基于骨架图的快速找座方法、系统和芯片

技术领域

本发明涉及智能机器人领域，具体涉及一种基于骨架图的快速找座方法、系统和芯片。

背景技术

移动机器人，诸如扫拖机器人、消毒机器人或宠物机器人等都配置有充电电池，在电池电量耗光之前，机器人必须回到充电座进行充电。目前，机器人一般采用自动找座的方法回座，常见的找座方法有随机找座、沿墙找座和RRT（快速扩展随机树算法）找座等。但是，上述找座方法不仅找座速度慢，还容易产生碰撞以及卡死的情况。比如，当通过沿墙方法找座时，机器人需要在整个空间的边沿移动，大大增加了移动距离，而且不可避免地会遇上位于墙边的障碍物。因此，需要对现有的找座方法进行改进。

发明内容

为解决上述问题，本发明提供了一种基于骨架图的快速找座方法、系统和芯片，可以在地图上没有记录充电座的信息，也没有充电座的信号的情况下，有序且快速地探索地图以实现回座。本发明的具体技术方案如下：

一种基于骨架图的快速找座方法，所述方法包括如下步骤：步骤S1，移动机器人生成表示全局地图连通性的骨架图，然后找出骨架图上的边界点和空旷点并生成无向图；其中，移动机器人储存有全局地图步骤S2，基于所述无向图生成多叉树，然后遍历所述多叉树，得到待探索点序列；步骤S3，移动机器人移动到离其最近的空旷点，然后判断与待探索点序列中未探索的第一个边界点是否直线可达，若直线不可达则进入步骤S4，若直线可达则移动到该边界点检测回座信号，如果检测到回座信号则回座，如果没有检测到回座信号则进入步骤S5；步骤S4，移动机器人判断与待探索点序列中未探索的第一个边界点的前一个点是否直线可达，若否则继续对前一个点进行判断直至找到可以直达的点并移动到该点处，然后返回步骤S3；步骤S5，移动机器人将满足预设条件的边界点划分为同一个集和并对该集合中的全部边界点设置已探索标记，然后再次执行步骤S3直至回座或骨架图中所有的边界点都设置有已探索标记。与现有技术相比，本技术方案通过对骨架图上的空旷点和边界点进行排序，使得移动机器人可以有序地探索地图；通过空旷点进行移动，使得移动机器人避免不必要的碰撞，提高移动效率；通过边界点进行回座信号检测，且同一集合内的边界点不重复检测，使得移动机器人提高了找座效率。

进一步地，所述步骤S1中生成表示全局地图连通性的骨架图的方法具体包括：步骤S11，提取全局地图中障碍物的边缘点并进行判断，如果所述边缘点的八邻域内没有其它边缘点，则将该边缘点视为孤立点并删除，保留剩余的边缘点并进入步骤S12；步骤S12，基于步骤S11中剩余的边缘点构建 Delaunay 三角网，然后生成Delaunay 三角网中每个三角形每条边的中垂线；步骤S13，以所述中垂线为边、中垂线的交点为顶点构建泰森多边形，删除Delaunay 三角网后即可得到所述骨架图。删除孤立点，可以使地图变得尽量简单，方便后续找出空旷点和边界点；所述骨架图可以体现连通域信息。

进一步地，所述步骤S1中找出骨架图上的边界点和空旷点并生成无向图的方法具体包括：步骤S14，将所述骨架图叠加到全局地图上，然后依次以骨架图中的像素点为中心，判断作为中心的像素点的八邻域内像素变换次数是否为0，若是则将作为中心的像素点设置为空旷点，若否则将作为中心的像素点设置为边界点；其中，所述空旷点和边界点包含该点的地图坐标信息以及与该点连通的空旷点和/或边界点信息；步骤S15，根据所述空旷点和边界点的连通性进行连线，即可生成所述无向图；其中，所述连线为无向图的边。作为中心的像素点的八邻域内像素变换次数不为0，说明作为中心的像素点靠近障碍物，有可能是充电座，因此将其设置为边界点进行探索。

进一步地，所述步骤S14中判断像素变换次数的方法具体包括：步骤S141，将骨架图叠加到全局地图上后，遍历骨架图中的一个像素点的八邻域上的所有点，其中，遍历起点为任意一个点，遍历终点与遍历起点相同；步骤S142，遍历过程中，如果相邻两个点的颜色不一致则记录一次像素变换，遍历结束后即可得到该像素点像素变换的次数；其中，所述全局地图上使用不同的颜色标记空旷区域和障碍物区域。使用不同的颜色标记可通行区域和障碍物区域，使得不同位置的像素点具有不同的像素变换次数，便于区分和使用。

进一步地，所述步骤S2中基于所述无向图生成多叉树的方法具体包括：将无向图中距离移动机器人最近的空旷点设置为根茎节点，放置于树状结构的最顶层，将与该空旷点直接相连的点放置于树状结构的第二层，将与第二层中的点直接相连的点放置于树状结构的第三层，以此类推，即可生成所述多叉树。将无向图转换成多叉树的形式，方便后续对空旷点和边界点进行排序。

进一步地，所述步骤S2中，移动机器人使用深度优先搜索算法遍历所述多叉树。内存占用少，且能找出多叉树中所有的节点。

进一步地，所述步骤S5中将满足预设条件的边界点划分为同一个集和的方法具体包括：步骤S51，移动机器人以当前所在边界点为中心，找出以预设长度为半径的圆内的边界点；步骤S52，判断所述圆内的边界点与处于中心的边界点是否直线可达，若不存在直线可达的边界点，则将处于中心的边界点单独划分为一个集和，若存在直线可达的边界点则进入步骤S33；步骤S53，判断直线可达的边界点中是否存在属于已有集和的点，若否则将所有直线可达的边界点和处于中心的边界点划分为同一个集和，若是则忽略属于已有集和的点并将剩余的直线可达的边界点和处于中心的边界点划分为同一个集和。将距离较为接近的边界点划分为同一个集和，可以减少移动机器人的移动距离和检测次数，提高找座效率。

进一步地，所述方法还包括：当所述全局地图上存在多个房间和/或区域时，先生成第一个房间或区域的无向图，然后执行所述步骤S2至步骤S5；按顺序依次对剩余的房间或区域执行前述相同的操作直至移动机器人回座或骨架图中所有的边界点都设置有已探索标记；其中，所述房间和/或区域是预先规划好的且具有相应的编号。按房间或区域进行移动和找座，可以大大减少移动机器人的行走距离，提高找座效率，也更符合人的思维。

一种基于骨架图的快速找座系统，包括一个具有检测回座信号的移动机器人和一个具有发射回座信号的充电座，所述系统用于实现所述基于骨架图的快速找座方法，所述移动机器人内部还包括：骨架图生成模块，用于生成表示全局地图连通性的骨架图，以得到空旷点和边界点；无向图生成模块，用于根据骨架图中的空旷点和边界点生成无向图；多叉树生成模块，用于根据无向图生成多叉树，以方便进行深度优先遍历；深度优先遍历模块，用于遍历多叉树，实现空旷点和边界点的排序，以生成待探索点序列；边界点集和生成模块，用于将满足预设条件的边界点划分为同一个集和；回座模块，用于根据待探索点序列的顺序控制移动机器人在所述边界点处检测回座信号以实现回座；其中，移动机器人储存有全局地图。与现有技术相比，本技术方案使用深度优先遍历模块对骨架图上的空旷点和边界点进行排序，使得移动机器人可以有序地探索地图；使用边界点集和生成模块将距离较为接近的边界点划分为同一个集和，移动机器人减少移动距离和检测次数，提高找座效率。

一种芯片，该芯片储存有计算机程序代码，所述计算机程序代码被执行时实现所述基于骨架图的快速找座方法的步骤。与现有技术相比，本技术方案可以使得移动机器人有序且快速地探索地图以实现回座。

附图说明

图1为本发明一种实施例所述基于骨架图的快速找座方法流程图。

图2为本发明一种实施例所述骨架图的示意图。

图3为本发明一种实施例所述无向图的示意图。

图4为本发明一种实施例所述像素变换的示意图。

图5为本发明一种实施例所述多叉树的示意图。

图6为本发明一种实施例所述待探索点序列的示意图。

具体实施方式

下面结合附图对本发明的具体实施方式作进一步说明。应该指出，以下详细说明都是示例性的，旨在对本申请提供进一步的说明。除非另有指明，本文使用的所有技术和科学术语具有与本申请所属技术领域的普通技术人员通常理解的相同含义。

需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本申请的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。

在本实施例中，全局地图是该移动机器人第一次使用时，利用其自身携带的各种传感器(例如:加速度传感器、陀螺仪、超声波测距仪、摄像头、单线激光雷达、等等)对每个房间运动区域进行搜索，感应每个房间的位置、形状和大小，以及遇到的障碍物的位置、形状和大小，并据此绘制出一张环境边界地图，通过在室内边行走边记录的方式绘制的整个室内的地图，该地图上包括障碍物区域、空旷区域和未知区域。

本发明一实施例公开一种基于骨架图的快速找座方法，如图1所示，所述方法包括如下步骤：

步骤S1，移动机器人生成表示全局地图连通性的骨架图，然后找出骨架图上的边界点和空旷点并生成无向图；其中，移动机器人储存有全局地图。

在执行步骤S1的过程中，移动机器人生成表示全局地图连通性的骨架图的方法具体包括：

步骤S11，提取全局地图中障碍物的边缘点并进行判断，如果所述边缘点的八邻域内没有其它边缘点，则将该边缘点视为孤立点并删除，保留剩余的边缘点并进入步骤S12，删除孤立点，可以使地图变得尽量简单，方便后续找出待探索目标点；步骤S12，基于步骤S11中剩余的边缘点构建 Delaunay 三角网，然后生成Delaunay 三角网中每个三角形每条边的中垂线；步骤S13，以所述中垂线为边、中垂线的交点为顶点构建泰森多边形，删除Delaunay 三角网后即可得到如图2所示的骨架图，其中，图2左侧为所述骨架图与静态地图的叠加，右侧为单独的骨架图。骨架图可以通过极少的信息量来表达地图的连通域信息，这样能够确保后续提取出的边界点和空旷点之间是相互关联的，而不是随机生成的没有关联性的点。

获得骨架图后，找出骨架图上的边界点和空旷点并生成无向图的方法具体包括：

步骤S14，将所述骨架图叠加到全局地图上，然后依次以骨架图中的像素点为中心，判断作为中心的像素点的八邻域内像素变换次数是否为0，若是则将作为中心的像素点设置为空旷点，若否则将作为中心的像素点设置为边界点；其中，所述空旷点和边界点包含该点的地图坐标信息以及与该点连通的空旷点和/或边界点信息；步骤S15，根据所述空旷点和边界点的连通性进行连线，即可生成如图3所示的无向图；其中，所述连线为无向图的边。

其中，所述步骤S14中判断像素变换次数的方法具体包括：

步骤S141，将骨架图叠加到全局地图上后，遍历骨架图中的一个像素点的八邻域上的所有点，其中，遍历起点为任意一个点，遍历终点与遍历起点相同。参照图4，以像素点0为中心点的八邻域上有1-8八个点，如果遍历起点为像素点1，则遍历顺序为1-2-3-4-5-6-7-8-1。又如，遍历起点为像素点3，则遍历顺序为3-4-5-6-7-8-1-2-3。在本实施例中，设遍历起点为像素点1。步骤S142，遍历过程中，如果相邻两个点的颜色不一致则记录一次像素变换，遍历结束后即可得到该像素点像素变换的次数；其中，所述全局地图上使用不同的颜色标记空旷区域和障碍物区域。

参照图3（a），其中白色像素点1、3、6表示空旷区域上的点，黑色像素点2、4、5、7、8表示障碍物区域上的点。类似的，图3（b）中白色像素点2表示空旷区域上的点，黑色像素点1、3、4、5、6、7、8表示障碍物区域上的点。在图3（a）中，从像素点1开始遍历，记录到相邻的像素点1和像素点2之间的颜色不一致，像素点2和像素点3之间的颜色不一致，像素点3和像素点4之间的颜色不一致，以此类推，图3（a）中一共有6对相邻的点颜色不一致，即以像素点0为中心点的八邻域上存在6次像素变换。采用同样的方法，图3（b）中存在2次像素变换。不难看出，以骨架图中的像素点为中心，八邻域内像素变换次数为0的像素点表示的是空旷区域上的点（或者说是不靠近障碍物区域的点），即空旷点，而变换次数不为0的像素点表示的是靠近障碍物区域的点，即边界点。作为中心的像素点靠近障碍物，说明有可能是充电座，因此将其设置为边界点进行探索。

需要说明的是，在构建全局地图时，由于目标区域的环境比较复杂，为了表达目标区域中各个局部区域的特征，可以根据图像中各个物体的情况，给每个栅格配置相应的栅格状态。栅格状态用于表征图像中此处像素点的情况，由于像素点可以属于已探测到的障碍物的像素，也可以属于已探测到的无障碍物的像素，也可以属于不确定此处状态的像素。因此，栅格状态包括无障碍物状态、有障碍物状态及不确定状态。相应的，每个栅格状态都可以被量化表示，在本实施例中，栅格所在的像素点的灰度值为255，其表示无障碍物状态，亦即，已探测且无障碍物的区域中全部栅格都被标记为白色。栅格所在的像素点的灰度值为0，其表示有障碍物状态，亦即，已探测且为障碍物的区域中全部栅格都被标记为黑色。栅格所在的像素点的灰度值为0-225，其表示不确定状态，亦即，不确定的区域中全部栅格都被标记为灰色。为简化地图，将值为0-128的栅格所在的像素点全部标记为0，即用黑色来表示，将值为129-255的栅格所在的像素点全部标记为255，即用白色来表示。

在本实施例中，空旷区域由多个空白像素点组成，障碍物区域由多个黑色像素点组成，空旷区域与所述障碍物区域中像素点的像素特征不同。像素特征可以由任意合适标识符来表示，诸如灰度值或自定义栅格值等，例如，障碍物区域中每个像素点的灰度值为0，空旷区域中每个像素点的灰度值为255。再例如，障碍物区域中每个像素点的栅格值为0，空旷区域中每个像素点的栅格值为1。

步骤S2，基于所述无向图生成多叉树，然后遍历所述多叉树，得到待探索点序列。

为了方便后续进行深度优先搜索，在本实施例中，将所述无向图转换成一棵多叉树，多叉树的示意图可参照图5，生成多叉树的方法具体包括：将无向图中距离移动机器人最近的空旷点设置为根茎节点，放置于树状结构的最顶层，参照图3，假设距离移动机器人“R”最近的空旷点为1，所以将点1放置于树状结构的最顶层。然后依据无向图中点与点之间的连通性，将与该空旷点直接相连的点如图5中的点10、2、3放置于树状结构的第二层，将与第二层中的点直接相连的点如图5中的点8、7、6、5、4放置于树状结构的第三层，以此类推，即可生成所述多叉树。

在执行步骤S2的过程中，使用深度优先搜索算法遍历所述多叉树，得到待探索点序列，其过程可参照图6，图6上侧为深度优先搜索算法的遍历过程，下侧为遍历得到的待探索点序列。深度优先搜索（Depth First Search，DFS）属于图算法的一种，是一个针对图和树的遍历算法。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。如果此时图中存在未被访问的节点，则从下一个未探索的节点开始，重新进行深度优先遍历，直到图中所有节点均被访问过为止。

步骤S3，移动机器人移动到离其最近的空旷点，然后判断与待探索点序列中未探索的第一个边界点是否直线可达，若直线不可达则进入步骤S4，若直线可达则移动到该边界点检测回座信号，如果检测到回座信号则回座，如果没有检测到回座信号则进入步骤S5。

前述内容已经提及，所述空旷点是不靠近障碍物区域的点。因此借助空旷点来进行移动，可以尽可能地减少移动机器人在找座过程中与障碍物产生碰撞，降低出现卡死或导航数据出错的概率，同时也提高了移动效率。需要说明的是，待探索点序列中的空旷点无需探索，因为空旷点不靠近障碍物，也就表明充电座不在空旷点附近。但是，如果在一实施例中，移动机器人处于某一空旷点时检测到充电座的回座信号，移动机器人根据回座信号的指引回座即可。

在本实施例中，当待探索点序列中未探索的第一个边界点直线可达时，即移动机器人可以通过所在空旷点与该边界点的连线直接到达该边界点时（借助全局地图判断），移动机器人走直线移动到该边界点上。可选地，移动机器人还可以沿着空旷点移动到该边界点上。但是，这种行走方式不流畅，因为每个空旷点都是一个拐点。所以可以先对该路径进行平滑处理，提高移动机器人行走时的流畅性。具体的平滑处理方法为现有技术，不在此赘述。

步骤S4，移动机器人判断与待探索点序列中未探索的第一个边界点的前一个点是否直线可达，若否则继续对前一个点进行判断直至找到可以直达的点并移动到该点处，然后返回步骤S3。

在步骤S3中，移动机器人与待探索点序列中未探索的第一个边界点直线不可达时，先使移动机器人移动到离该边界点最近的直线可达的点上。具体为，取该边界点的前一个点进行判断，如果还是直线不可达，则再往前取一个点进行判断直至找到直线可达的点，然后移动到该点处并再次执行步骤S3。移动方法可参照前述内容。需要说明的是，当移动机器人本身处于空旷点上时，离其最近的空旷点即所处空旷点。

步骤S5，移动机器人将满足预设条件的边界点划分为同一个集和并对该集合中的全部边界点设置已探索标记，然后再次执行步骤S3直至回座或骨架图中所有的边界点都设置有已探索标记。

当执行完步骤S3后，移动机器人没有检测到回座信号，则为已探索的边界点设置已探索标记，避免重复探索。在执行步骤S5的过程中，将满足预设条件的边界点划分为同一个集和的方法具体包括：

步骤S51，移动机器人以当前所在边界点为中心，找出以预设长度为半径的圆内的边界点；步骤S52，判断所述圆内的边界点与处于中心的边界点是否直线可达，若不存在直线可达的边界点，则将处于中心的边界点单独划分为一个集和，若存在直线可达的边界点则进入步骤S33；步骤S53，判断直线可达的边界点中是否存在属于已有集和的点，若否则将所有直线可达的边界点和处于中心的边界点划分为同一个集和，若是则忽略属于已有集和的点并将剩余的直线可达的边界点和处于中心的边界点划分为同一个集和。将距离较为接近的边界点划分为同一个集和，可以减少移动机器人的移动距离和检测次数，提高找座效率。需要说明的是，所述预设长度的最大值不能超过移动机器人检测回座信号的半径与充电座辐射回座信号的半径之和。

作为另一种实施例，当所述全局地图上存在多个房间和/或区域时，先生成第一个房间或区域的无向图，然后执行所述步骤S2至步骤S5；按顺序依次对剩余的房间或区域执行前述相同的操作直至移动机器人回座或骨架图中所有的边界点都设置有已探索标记；其中，所述房间和/或区域是预先规划好的且具有相应的编号。按房间或区域进行移动和找座，可以大大减少移动机器人的行走距离，提高找座效率，也更符合人的思维。

本发明还提供一种基于骨架图的快速找座系统，包括一个具有检测回座信号的移动机器人和一个具有发射回座信号的充电座。优选地，所述回座信号为红外信号或UWB传感器信号。当所述回座信号为红外信号时，该红外信号由充电座上设置的红外发射灯发出，移动机器人上对应设置有检测该红外信号的红外传感器；当所述回座信号为UWB传感器信号时，该UWB传感器信号由设置在充电座上的UWB基站发出，移动机器人上对应设置有检测该UWB传感器信号的UWB标签。至于移动机器人检测到回座信号后如何回座，已为现有技术，不在此赘述。

所述移动机器人内部还包括：

骨架图生成模块，用于生成表示全局地图连通性的骨架图，以得到空旷点和边界点；无向图生成模块，用于根据骨架图中的空旷点和边界点生成无向图；多叉树生成模块，用于根据无向图生成多叉树，以方便进行深度优先遍历；深度优先遍历模块，用于遍历多叉树，实现空旷点和边界点的排序，以生成待探索点序列；边界点集和生成模块，用于将满足预设条件的边界点划分为同一个集和，以避免重复探索，提高探索效率；回座模块，用于根据待探索点序列的顺序控制移动机器人在所述边界点处检测回座信号以实现回座；其中，移动机器人储存有全局地图。与现有技术相比，所述移动机器人使用深度优先遍历模块对骨架图上的空旷点和边界点进行排序，使得移动机器人可以有序地探索地图；使用边界点集和生成模块将距离较为接近的边界点划分为同一个集和，移动机器人减少移动距离和检测次数，提高找座效率。

本发明还公开一种芯片，该芯片用于存储计算机程序代码，并可以设置在前述的移动机器人内，所述计算机程序代码被执行时实现前述基于骨架图的快速找座方法的步骤。或者，所述芯片执行所述计算机程序代码时实现上述移动机器人实施例中各个模块的功能。示例性的，所述计算机程序代码可以被分割成一个或多个模块/单元，所述一个或者多个模块/单元被存储在所述芯片中，并由所述芯片执行，以完成本申请。所述一个或多个模块/单元可以是能够完成特定功能的一系列计算机程序指令段，该指令段用于描述所述计算机程序代码在所述移动机器人中的执行过程。例如，所述计算机程序代码可以被分割成：前述移动机器人实施例内的骨架图生成模块、无向图生成模块、多叉树生成模块、深度优先遍历模块、边界点集和生成模块和回座模块。与现有技术相比，所述芯片可以使得移动机器人有序且快速地探索地图以实现回座。

显然，上述的实施例仅仅是本发明一部分实施例，而不是全部的实施例，各个实施例之间的技术方案可以相互结合。此外，如果实施例中出现“中心”、“上”、“下”、“左”、“右”、“竖直”、“水平”、“内”、“外”等术语，其指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位或以特定的方位构造和操作，因此不能理解为对本发明的限制。如果实施例中出现“第一”、“第二”、“第三”等术语，是为了便于相关特征的区分，不能理解为指示或暗示其相对重要性、次序的先后或者技术特征的数量。

所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备（可为个人计算机、服务器或者网络设备等）执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、只读存储器（ROM，Read-Only Memory）、随机存取存储器（RAM，Random Access Memory）、移动硬盘、磁碟或者光盘等各种可以存储程序代码的介质。

最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。

Claims (10)

1.一种基于骨架图的快速找座方法，其特征在于，所述方法包括如下步骤：

步骤S1，移动机器人生成表示全局地图连通性的骨架图，然后找出骨架图上的边界点和空旷点并生成无向图；其中，移动机器人储存有全局地图；

步骤S2，基于所述无向图生成多叉树，然后遍历所述多叉树，得到待探索点序列；

步骤S3，移动机器人移动到离其最近的空旷点，然后判断与待探索点序列中未探索的第一个边界点是否直线可达，若直线不可达则进入步骤S4，若直线可达则移动到该边界点检测回座信号，如果检测到回座信号则回座，如果没有检测到回座信号则进入步骤S5；

步骤S4，移动机器人判断与待探索点序列中未探索的第一个边界点的前一个点是否直线可达，若否则继续对前一个点进行判断直至找到可以直达的点并移动到该点处，然后返回步骤S3；

步骤S5，移动机器人将满足预设条件的边界点划分为同一个集和并对该集合中的全部边界点设置已探索标记，然后再次执行步骤S3直至回座或骨架图中所有的边界点都设置有已探索标记。

2.根据权利要求1所述的一种基于骨架图的快速找座方法，其特征在于，所述步骤S1中生成表示全局地图连通性的骨架图的方法具体包括：

步骤S11，提取全局地图中障碍物的边缘点并进行判断，如果所述边缘点的八邻域内没有其它边缘点，则将该边缘点视为孤立点并删除，保留剩余的边缘点并进入步骤S12；

步骤S12，基于步骤S11中剩余的边缘点构建 Delaunay 三角网，然后生成Delaunay 三角网中每个三角形每条边的中垂线；

步骤S13，以所述中垂线为边、中垂线的交点为顶点构建泰森多边形，删除Delaunay 三角网后即可得到所述骨架图。

3.根据权利要求1所述的一种基于骨架图的快速找座方法，其特征在于，所述步骤S1中找出骨架图上的边界点和空旷点并生成无向图的方法具体包括：

步骤S14，将所述骨架图叠加到全局地图上，然后依次以骨架图中的像素点为中心，判断作为中心的像素点的八邻域内像素变换次数是否为0，若是则将作为中心的像素点设置为空旷点，若否则将作为中心的像素点设置为边界点；其中，所述空旷点和边界点包含该点的地图坐标信息以及与该点连通的空旷点和/或边界点信息；

步骤S15，根据所述空旷点和边界点的连通性进行连线，即可生成所述无向图；其中，所述连线为无向图的边。

4.根据权利要求3所述的一种基于骨架图的快速找座方法，其特征在于，所述步骤S14中判断像素变换次数的方法具体包括：

步骤S141，将骨架图叠加到全局地图上后，遍历骨架图中的一个像素点的八邻域上的所有点，其中，遍历起点为任意一个点，遍历终点与遍历起点相同；

步骤S142，遍历过程中，如果相邻两个点的颜色不一致则记录一次像素变换，遍历结束后即可得到该像素点像素变换的次数；其中，所述全局地图上使用不同的颜色标记空旷区域和障碍物区域。

5.根据权利要求3所述的一种基于骨架图的快速找座方法，其特征在于，所述步骤S2中基于所述无向图生成多叉树的方法具体包括：

将无向图中距离移动机器人最近的空旷点设置为根茎节点，放置于树状结构的最顶层，

将与该空旷点直接相连的点放置于树状结构的第二层，

将与第二层中的点直接相连的点放置于树状结构的第三层，以此类推，即可生成所述多叉树。

6.根据权利要求5所述的一种基于骨架图的快速找座方法，其特征在于，所述步骤S2中，移动机器人使用深度优先搜索算法遍历所述多叉树。

7.根据权利要求1所述的一种基于骨架图的快速找座方法，其特征在于，所述步骤S5中将满足预设条件的边界点划分为同一个集和的方法具体包括：

步骤S51，移动机器人以当前所在边界点为中心，找出以预设长度为半径的圆内的边界点；

步骤S52，判断所述圆内的边界点与处于中心的边界点是否直线可达，若不存在直线可达的边界点，则将处于中心的边界点单独划分为一个集和，若存在直线可达的边界点则进入步骤S33；

步骤S53，判断直线可达的边界点中是否存在属于已有集和的点，若否则将所有直线可达的边界点和处于中心的边界点划分为同一个集和，若是则忽略属于已有集和的点并将剩余的直线可达的边界点和处于中心的边界点划分为同一个集和。

8.根据权利要求1所述的一种基于骨架图的快速找座方法，其特征在于，所述方法还包括：

当所述全局地图上存在多个房间和/或区域时，先生成第一个房间或区域的无向图，然后执行所述步骤S2至步骤S5；按顺序依次对剩余的房间或区域执行前述相同的操作直至移动机器人回座或骨架图中所有的边界点都设置有已探索标记；其中，所述房间和/或区域是预先规划好的且具有相应的编号。

9.一种基于骨架图的快速找座系统，包括一个具有检测回座信号的移动机器人和一个具有发射回座信号的充电座，其特征在于，所述系统用于实现权利要求1-8任一项所述基于骨架图的快速找座方法，所述移动机器人内部还包括：

骨架图生成模块，用于生成表示全局地图连通性的骨架图，以得到空旷点和边界点；

无向图生成模块，用于根据骨架图中的空旷点和边界点生成无向图；

多叉树生成模块，用于根据无向图生成多叉树，以方便进行深度优先遍历；

深度优先遍历模块，用于遍历多叉树，实现空旷点和边界点的排序，以生成待探索点序列；

边界点集和生成模块，用于将满足预设条件的边界点划分为同一个集和；

回座模块，用于根据待探索点序列的顺序控制移动机器人在所述边界点处检测回座信号以实现回座；

其中，移动机器人储存有全局地图。

10.一种芯片，该芯片储存有计算机程序代码，其特征在于，所述计算机程序代码被执行时实现权利要求1-8任一项所述基于骨架图的快速找座方法的步骤。

Images