专利名称：一种用于移动平台在未知区域自建地图的覆盖方法
技术领域：
本发明涉及移动平台技术领域，尤其涉及一种用于移动平台在未知区域自建地图的覆盖方法。
背景技术：
移动平台在未知区域的路径规划一直是移动平台领域中重点和难点，由于在未知区域中可能存在障碍，因此移动平台不能对该区域实现全面覆盖。针对上述问题，中国专利ZL02137830. 4公开了一种智能吸尘器的路径规划方法，其通过确定未知区域边界后再对边界内的区域进行覆盖清扫，但其在未知区域内存在障碍时，先对障碍的边界进行确认，再执行清洁动作，算法非常复杂，同时智能吸尘器多次重复已清洁的区域，降低了智能吸尘器的清洁效率；中国专利申请号为201010106562. 6的专利文献中公布了一种基于中国专利ZL02137830.4的技术方案的改进方案，其通过补偿未覆盖区域的方式来达到对整个区域的覆盖，但这种方案不适用于在工作区域内有过多的障碍的情况。

发明内容
本发明提供了一种用于移动平台在未知区域自建地图的覆盖方法，用以解决现有技术算法复杂、覆盖率低的问题，其技术方案如下一种用于移动平台在未知区域自建地图的覆盖方法，预先建立一以起始点为中心、包括多个子区域的虚拟地图，所述方法包括(I)当移动平台进入未知区域时，将移动平台的当前位置与所述虚拟地图的起始点所在的子区域对应；(2)将所述虚拟地图中、与所述移动平台的当前位置对应的子区域标记为已遍历子区域，将所述虚拟地图中的其他子区域标记为未遍历子区域；(3)从与所述已遍历区域相邻的未遍历子区域中确定一目标子区域；(4)将移动平台移动至与所述目标子区域对应的区域中；(5)将所述虚拟地图中、与移动平台当前位置对应的子区域标记为已遍历子区域，并且，从与已遍历区域相邻的未遍历子区域中确定一目标子区域；(6)重复步骤(4)至步骤(5)，直至所述虚拟地图中没有目标子区域。可选的，上述方法还包括移动平台向与所述目标子区域对应的区域中移动的过程中，如果探测到障碍，则将该目标子区域标记为障碍子区域，再返回到步骤(3)。可选的，上述方法还包括如果移动平台无法通过已遍历区域到达某个目标子区域，则将该目标子区域标记为障碍子区域，再返回到步骤(3)。优选的，所述地图存储系统预先建立的虚拟地图中各个子区域的最小覆盖圆的直径小于或等于移动平台在所述虚拟地图中直径的1/2，其中，最小覆盖圆为以子区域边缘相隔最远距离的两个端点为直径的圆形。
优选的，所述预先建立的虚拟地图中各个子区域的形状和大小相同。优选的，所述预先建立的虚拟地图中各个子区域的形状均为正方形。优选的，所述预先建立的虚拟地图中各个子区域的形状是正六边形。本发明与现有技术对比具有以下有益效果本发明将移动平台要覆盖的未知区域划分为已遍历子区域和未遍历子区域，通过在与已遍历区域相邻的子区域中设定目标子区域，使得移动平台覆盖整个未知区域。本方法的算法简单，覆盖率高且可降低移动平台的在未知区域的重复覆盖率，提高了覆盖效率。


为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。图I为本发明实施例一提供的用于移动平台在未知区域自建地图的覆盖方法的流程示意图；图2是本发明实施例一中的移动平台在未知区域示意图；图3是图2中的移动平台在地图存储系统的虚拟地图中示意图；图4是图3中的移动平台标记相邻子区域的示意图；图5是图3中的移动平台选择目标子区域的示意图；图6是图2中的移动平台进入到目标子区域后的示意图；
图7是图6中的移动平台在地图存储系统的虚拟地图中示意图；图8是图7中的移动平台选择目标子区域的示意图；图9是图7中的移动平台选择另一相邻子区域作为目标子区域的示意图；图10是图2中的移动平台完成未知区域的遍历后的示意图；图11是图10中的移动平台在地图存储系统的虚拟地图中完成遍历后的示意图；图12是本发明实施例2中的移动平台在未知区域示意图；图13是图12中的移动平台在地图存储系统的虚拟地图中示意图；图14是图13中的移动平台标记相邻子区域的示意图；图15是图13中的移动平台选择目标子区域的示意图；图16是图12中的移动平台进入到目标子区域后的示意图；图17是图16中的移动平台在地图存储系统的虚拟地图中示意图；图18是图17中的移动平台选择目标子区域的示意图；图19是图17中的移动平台选择另一相邻子区域作为目标子区域的示意图；图20是图12中的移动平台完成未知区域的遍历后的示意图；图21是图20中的移动平台在地图存储系统的虚拟地图中完成遍历后的示意图；图22是子区域最小覆盖圆直径大于移动平台能通过的最小宽度1//2情况下，移动平台与障碍子区域的示意图；图23是子区域最小覆盖圆直径小于或等于移动平台能通过的最小宽度1//2情况下，移动平台与障碍子区域的示意图24是地图存储系统的虚拟地图中的子区域为正六边形的示意图。
具体实施例方式下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。实现本发明方法的移动平台需要至少包括以下几个功能模块驱动系统用于使移动平台发生位移，可以是如清洁机器人的驱动轮，也可以是如仿生学中的动物(包括人类)的行走机构。障碍探测系统用于探测移动平台周围障碍并在感知到障碍后生成障碍信号传输 给移动平台的控制系统，包括非接触式传感器的如红外传感器、超声波传感器等，以及接触式传感器如电压传感器、机械式开关传感器等。相对定位系统用于确定一段时间后，移动平台在移动后的所在区域相对移动前所在区域的相对位置，包括方向及距离，如可使用惯性导航系统，通过计算移动平台的加速度积分(使用加速度计)、角速度积分(使用陀螺仪)来获得相关信息，或者使用安装在移动平台驱动轮上的编码盘来计算行走轮的移动距离来确定相对位置。地图存储系统建立一个由多个子区域组成的足够大的虚拟地图，并存储各个子区域的信息，可使用应用比较广泛的存储芯片或者内存，用一个字节的数据代表一个子区域的信息用O表示没有遍历过的子区域，用I表示遍历过的子区域，用2表示有障碍的子区域，此外，地图存储系统还可将未遍历子区域的信息由O更改为I (遍历过的子区域)或2(有障碍的子区域)，然后储存并更新虚拟地图。本实施例的信息标记0，1，2仅是为了可以区分表示各子区域的状态，可以使用任意字符或数据代表不同的区域，只要能被地图存储系统识别即可。控制系统用于控制移动平台的整体工作状态包括使移动平台执行预定的动作，根据障碍探测系统反馈的信息控制驱动系统改变移动平台的运动及运动方向等。实施例一本发明实施例一提供了一种用于移动平台在未知区域自建地图的覆盖方法，预先建立一以起始点为中心、包括多个子区域的虚拟地图，图I为该方法的流程示意图，该方法可以包括SlOl :移动平台在进入未知区域时，将移动平台的当前位置与地图存储系统的起始点所在的子区域对应。图2为本实施例中的移动平台M在未知区域的示意图，其中，虚线标记是便于技术人员理解实际区域的划分并将其与虚拟地图中的子区域进行对应，即移动平台M在实际的未知区域中的每个位置都有一个在虚拟地图中的子区域与其对应。其中，图2中的黑色区域表明障碍或边界，白色表明空白区域。S102 :将虚拟地图中、与移动平台当前位置对应的子区域标记为已遍历子区域，将虚拟地图中的其他子区域标记为未遍历子区域。如图3所示，在虚拟地图中，把与移动平台M当前位置对应的子区域(圆圈所在的区域)标记为1，表明该子区域已被移动平台M遍历，而将其他子区域标记为O，表明移动平台M未遍历的子区域，然后更新虚拟地图中的子区域信息并存储。S103 :从与已遍历区域相邻的未遍历子区域中确定一目标子区域。其中，相邻子区域指的是移动平台从已遍历区域不需经过第三子区域而能到达的子区域。如图4所示，由于虚拟地图中的子区域为正方形，与已遍历区域相连的子区域包括4个，因此，把4个子区域作为已遍历区域的相邻子区域，将它们标记为B。其中，相邻子区域指的是移动平台M从已遍历区域不需经过第三子区域而能到达的子区域，也就是说，与已遍历区域具有共同边的子区域，而具有公共顶点的子区域不算为相邻子区域。然后，将这4个标记为B的相邻子区域中的任意一个区域作为目标子区域，如图5所示，将已遍历区域下边的子区域标记为A，即目标子区域。然后更新虚拟地图的子区域信息并存储。S104 :将移动平台从已遍历区域移动至目标子区域。 在虚拟地图标记好目标子区域A后，移动平台M向虚拟地图中标记的目标子区域A运动。S105:在移动平台到达某个目标子区域后，将与移动平台当前位置对应的子区域标记为已遍历子区域，并且，从与已遍历区域相邻的未遍历子区域中确定一目标子区域。图6为移动平台M在实际状况下到达到未知区域的另外一个位置时的示意图，也就是与图5中的虚拟地图中目标子区域A对应的位置。由于图5中的目标子区域A中在实际状况的位置中没有障碍，因此移动平台M可顺利到达与目标子区域A对应的子区域中。在移动平台M到达该子区域后，如图7所示，将该子区域标记为1，即已遍历子区域，将该子区域相邻的未遍历的其他3个子区域标记为B，此时存在6个相邻子区域。如图8所示，在这6个标记为B的相邻子区域中任意选择一个子区域标记为A，即目标子区域。然后更新地图子区域信息并存储。S106 :判断虚拟地图中是否存在目标子区域，如果是，则转入步骤S104，如果否，则结束流程。如图6所示，在图8所示的虚拟地图中的标记为A目标子区域中有障碍物，因此，移动平台M无法进入到该区域，在这种情况下，上述方法还包括如果移动平台在向目标子区域运动的过程中探测到障碍，则将该目标子区域标记为障碍子区域，再返回到步骤S103。实际中的移动平台M在向与图8中标记为A的目标子区域对应的区域运动时，探测到障碍，如图9所示，将该标记为A的目标子区域重新标记为2，即障碍子区域，再从其他6个相邻子区域中任意选择一个标记为A，即作为目标子区域，然后更新地图子区域信息并存储。如此反复，直到已遍历子区域没有目标子区域，图10示出了移动平台M在该未知区域遍历完成后的示意图，图11示出了移动平台M在完成未知区域后在虚拟地图中的示意图。实施例二本发明实施例二提供了一种用于移动平台在未知区域自建地图的覆盖方法，其实现流程与实施例相同，其流程示意图可参见图I。与实施例一不同的是，在实施例一中，如图2所示，虚拟地图中的子区域尺寸与移动平台在虚拟地图中的尺寸基本相同，而在实施例二中，如图12所示，虚拟地图中的子区域尺寸大约是移动平台在虚拟地图中的尺寸的1/2左右。
在下面描述实施例二的具体步骤的过程中，侧重于描述与实施一的不同之处，相同之处可参见实施例一。SlOl :移动平台在进入未知区域时，将移动平台的当前位置与地图存储系统的起始点所在的子区域对应。S102 :将虚拟地图中、与移动平台当前位置对应的子区域标记为已遍历子区域，将其他子区域标记为未遍历子区域。如图13所示，移动平台M在最初占据了 4个子区域，因此将虚拟地图中、与移动平台M占据的区域对应的四个子区域均标记为1，即已遍历子区域。S103:从与已遍历区域相邻的未遍历子区域中确定一目标子区域，其中，相邻子区域指的是移动平台从已遍历区域不需经过第三子区域而能到达的子区域。如图14所示，与已遍历区域相邻的未遍历子区域包括8个，如图14所示，从与已遍历区域相邻的未遍历子 区域中选择一个子区域作为目标子区域，例如，可以将已遍历区域下边右侧的子区域标记为A，即目标子区域。S104 :将移动平台从已遍历区域移动至目标子区域。如图15所示，移动平台M在向与目标子区域A对应的区域中运动的过程中，探测到其运动方向的左侧有障碍，因此，将具有障碍的2个相邻子区域标记为2，即障碍子区域。S105:在移动平台到达某个目标子区域后，将虚拟地图中、与移动平台当前位置对应的区域标记为已遍历区域，并且，从与已遍历区域相邻的未遍历子区域中确定一目标子区域。如图16所示，为移动平台M在实际状况下到达到未知区域的另外一个位置时的示意图，该位置与图15中的虚拟地图中的目标子区域A对应。由于图15中的目标子区域A及其左边的子区域在实际状况的位置中没有障碍，因此，移动平台M可顺利到达该子区域。在移动平台M到达该子区域后，如图17所示，将该子区域和其左边的子区域都标记为1，即已遍历子区域，将该子区域和其左边的子区域相邻的未遍历的其他4个子区域标记为B，此时存在8个相邻子区域(有2个已被标记为障碍子区域)。如图18所示，在这8个标记为B的相邻子区域中任意选择一个子区域标记为A，即目标子区域。然后更新虚拟地图子的区域信息并存储。S106 :判断虚拟地图中是否存在目标子区域，如果是，则转入步骤S 104，否则，结
束流程。如图15所示，在实际状况下，虽然与图17所示的虚拟地图中标记为A的目标子区域对应的区域中没有障碍物，但是，由于移动平台在虚拟地图中的尺寸大约是虚拟地图中的子区域尺寸的2倍，因此，当与目标子区域左边的子区域对应的区域中有障碍物，移动平台M也是无法进入到该区域。上述方法还可以包括如果移动平台在向目标子区域运动过程中探测到障碍，则将该目标子区域标记为障碍子区域，再返回到步骤S103。如图19所示，将目标子区域A左侧的子区域标记为2，即障碍子区域，然后更新地图子区域信息并存储。上述方法还可以包括如果移动平台无法通过已遍历区域到达某个目标子区域，则将该目标子区域标记为障碍子区域，再返回到步骤S 103。
如图19所示，由于移动平台M无法通过已遍历的子区域进入如18中的目标子区域A，因此，也将其标记为2，即障碍区域，然后移动平台M再从剩下的6个相邻子区域中选择一个作为目标子区域，再回到步骤S103。如此反复，直到已遍历子区域没有目标子区域，如图20所示，移动平台M在该未知区域遍历完成后的示意图，如图21所示，为移动平台M在完成未知区域后在虚拟地图中的示意图。如图22所示，虚拟地图中的正方形子区域的边长大约为移动平台M在虚拟地图中的直径的2倍，因此，从理论上说，移动平台M可以从图示中箭头所标记的方向过去而覆盖部分区域，而在实际移动平台的遍历过程中，由于在移动平台在探测到该两个子区域的障碍后，虚拟地图中的这个两个子区域标记为障碍区域，因此移动平台M不会进入与虚拟地图的两个子区域对应的位置，从而存在一些理论上可以覆盖但又不能覆盖的区域，因此子区域的划分不宜太大。如图23所示，虚拟地图中的正方形子区域的边长小于或等于移动平台M在虚拟地 图中的直径的1/2，因此，在图23中，移动平台M从理论上也不能从两个具有障碍的子区域中沿箭头所示的方向穿过，从理论上说，如果存储系统的支持，推荐子区域的大小尽量小，这样移动平台M能尽可能地覆盖未知区域。如果子区域是为不规则图形，移动平台M为非圆形，则可表达为虚拟地图中的子区域的最小覆盖圆的直径小于或等于移动平台在地图存储系统内的能通过的最小宽度的1/2，其中，最小覆盖圆指的是以子区域边缘相隔最远距离的两个端点为直径的圆形，最小宽度指的是移动平台能通过的空间的宽度。如图24所示，是地图存储系统中的虚拟地图中子区域全部为大小相同的正六边形的示意图，其可沿六个方向覆盖整个虚拟地图，其单个子区域的相邻区域有6个，移动平台M在该正六边形的子区域中的覆盖方法及步骤与实施例一和实施例二中的相同，因此不再赘述。实施例三发明实施例三提供了一种用于移动平台在未知区域自建地图的覆盖系统，包括驱动系统、相对定位系统、地图存储系统和控制系统。其中驱动系统，用于驱动移动平台发生位移。相对定位系统，用于确定移动平台在移动后的所在的区域相对移动前所在区域的相对位置。地图存储系统，用于将预存的以起始点为中心、包括多个子区域的虚拟地图中的子区域标记为已遍历区域。控制系统，用于当移动平台进入未知区域时，控制地图存储子系统将预存的虚拟地图的起始点与移动平台的当前位置对应，并控制地图存储子系统将虚拟地图中、与移动平台的当前位置对应的子区域标记为已遍历子区域，将虚拟地图中的其他子区域标记为未遍历子区域，从与已遍历区域相邻的未遍历子区域中确定一目标子区域；利用相对定位子系统确定的位置，控制驱动子系统将移动平台移动至与目标子区域对应的区域中；控制地图存储子系统将虚拟地图中、与移动平台当前位置对应的子区域标记为已遍历子区域，并且，从与已遍历区域相邻的未遍历子区域中确定一目标子区域。控制系统利用相对定位系统控制驱动系统、地图存储系统重复执行上述操作直至虚拟地图中没有目标子区域。
本发明实施例提供的系统还可以包括用于探测故障的故障探测系统。在移动平台向与目标子区域对应的区域中移动的过程中，如果故障探测系统探测到障碍，则控制系统控制地图存储系统将目标子区域标记为障碍子区域。
对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。
权利要求
1.一种用于移动平台在未知区域自建地图的覆盖方法，其特征在于，预先建立一以起始点为中心、包括多个子区域的虚拟地图，所述方法包括 (1)当移动平台进入未知区域时，将移动平台的当前位置与所述虚拟地图的起始点所在的子区域对应； (2)将所述虚拟地图中、与所述移动平台的当前位置对应的子区域标记为已遍历子区域，将所述虚拟地图中的其他子区域标记为未遍历子区域； (3)从与所述已遍历区域相邻的未遍历子区域中确定一目标子区域； (4)将移动平台移动至与所述目标子区域对应的区域中； (5)将所述虚拟地图中、与移动平台当前位置对应的子区域标记为已遍历子区域，并且，从与已遍历区域相邻的未遍历子区域中确定一目标子区域； (6)重复步骤(4)至步骤(5)，直至所述虚拟地图中没有目标子区域。
2.根据权利要求I所述的方法，其特征在于，还包括 在移动平台移动向与所述目标子区域对应的区域中移动的过程中，如果探测到障碍，则将所述目标子区域标记为障碍子区域，再返回到步骤(3)。
3.根据权利要求2所述的方法，其特征在于，还包括 如果移动平台无法通过已遍历区域到达目标子区域，则将该目标子区域标记为障碍子区域，再返回到步骤(3)。
4.根据权利要求I所述的方法，其特征在于，所述预先建立的虚拟地图中各个子区域的最小覆盖圆的直径小于或等于移动平台在所述虚拟地图中直径的1/2，其中，最小覆盖圆为以子区域边缘相隔最远距离的两个端点为直径的圆形。
5.根据权利要求I所述的方法，其特征在于，所述预先建立的虚拟地图中各个子区域的形状和大小相同。
6.根据权利要求I所述的方法，其特征在于，所述预先建立的虚拟地图中各个子区域的形状均为正方形。
7.根据权利要求I所述的方法，其特征在于，所述预先建立的虚拟地图中各个子区域的形状均为正六边形。
全文摘要
本申请提供一种用于移动平台在未知区域自建地图的覆盖方法，预先建立一虚拟地图，该方法包括1)当移动平台进入未知区域时，将移动平台当前位置与虚拟地图起始点所在的子区域对应；2)将与移动平台当前位置对应的子区域标记为已遍历子区域，将其他子区域标记为未遍历子区域；3)将与已遍历区域相邻的未遍历子区域标记为目标子区域；4)将移动平台移动至与目标子区域对应的区域中；5)将与移动平台当前位置对应的子区域标记为已遍历子区域，从与已遍历区域相邻的未遍历子区域标中确定一目标子区域；6)重复步骤4)至5)直至没有目标子区域。本申请提供的方法实现简单，覆盖率高且可降低移动平台在未知区域的重复覆盖率。
文档编号G01C21/34GK102968122SQ20121053550
公开日2013年3月13日 申请日期2012年12月12日 优先权日2012年12月12日
发明者肖双良 申请人:深圳市银星智能科技股份有限公司