CN116466694A - 基于激光点的最优碰撞点搜索方法、芯片及机器人 - Google Patents

Abstract

本发明公开基于激光点的最优碰撞点搜索方法、芯片及机器人，该最优碰撞点搜索方法包括，在预配置地图内搜索出满足预设连通条件的栅格，再将该满足预设连通条件的栅格的坐标标记为最优碰撞点在预配置地图内的坐标，并确定满足预设连通条件的栅格对应的激光点所反映的物理位置是最优碰撞点。本发明能够在距离机器人机体最近的连续型障碍物中搜索出最优碰撞点，克服现有技术中采集的激光数据（包括激光点的坐标、探测角度及激光距离）存在噪声或地图不稳定的问题。

Description

基于激光点的最优碰撞点搜索方法、芯片及机器人

技术领域

本发明涉及激光导航定位的技术领域，尤其涉及基于激光点的最优碰撞点搜索方法、芯片及机器人。

背景技术

目前具备激光导航定位功能的清洁机器人在执行清扫工作时，清洁机器人在一个室内房间区域内进行清扫作业之前，需要找到一个沿着室内房间的墙体边界进行沿边行走的起点位置，从这个起点位置开始沿边行走，沿完该室内房间区域的墙体边界，再开始对该室内房间区域进行清扫。

清洁机器人的激光传感器获取的点云数据具备数据量大以及离散程度较高的特征，导致构建地图的激光数据会携带有噪声；机器人预先构建的激光点云地图所使用的激光帧的帧数较少，使得激光点云地图较为模糊。所以，即便将清洁机器人放置在同一地点，机器人也是同时寻找到多个障碍物碰撞位置，使得清洁机器人会导航到不同障碍物碰撞位置处并与相应位置处的障碍物发生碰撞，再开始沿边行走（可以是沿着墙面作沿边行走），从而造成清洁机器人的导航结果不稳定且沿边行走模式不稳定。

发明内容

为了解决上述技术问题，本发明搜索激光帧的每个激光点，并根据其在地图上的落点所在的连通域的像素数量特征来搜索出一个最优碰撞点，以便于机器人从一个稳定的位置处开始沿着距离最近的最大的连续型障碍物作沿边行走。具体的技术方案包括：

基于激光点的最优碰撞点搜索方法，该最优碰撞点搜索方法包括在预配置地图内搜索出满足预设连通条件的栅格，再将该满足预设连通条件的栅格的坐标标记为最优碰撞点在预配置地图内的坐标，并确定满足预设连通条件的栅格对应的激光点所反映的物理位置是最优碰撞点。

进一步地，在预配置地图内搜索满足预设连通条件的栅格，再将该满足预设连通条件的栅格的坐标标记为最优碰撞点的坐标的方法包括当在预配置地图内搜索出满足第一预设连通条件的栅格时，将该满足第一预设连通条件的栅格的坐标标记为最优碰撞点在预配置地图内的坐标；在预配置地图内搜索不出满足第一预设连通条件的栅格后，则在预配置地图内搜索出满足第二预设连通条件的栅格，再将该满足第二预设连通条件的栅格的坐标标记为最优碰撞点在预配置地图内的坐标；其中，所述预设连通条件包括第一预设连通条件或第二预设连通条件。

进一步地，当搜索不出满足第一预设连通条件的栅格，且搜索不出满足第二预设连通条件的栅格时，在激光帧内搜索出激光距离最小的激光点，再将该激光点对应的栅格的坐标标记为最优碰撞点在预配置地图内的坐标；其中，机器人所搜索到的激光点都是来源于机器人采集到的激光帧；一个激光点对应一个激光距离。

进一步地，激光点是用于表征机器人的激光传感器发射的激光在障碍物上的反射位置，激光点是来源于机器人采集到的激光帧；其中，激光点是位于激光传感器的有效探测角度范围内，并映射到所述预配置地图的对应栅格中；在有效探测角度范围内，一个激光点对应一个单位探测角度，一个激光点对应一个栅格，一个激光点对应一个激光距离，激光距离用于反映所探测的障碍物与机器人所安装的激光传感器之间的距离。

进一步地，满足第一预设连通条件的栅格是：在预配置地图内，最佳邻域连通像素数量大于预设像素数量阈值、最佳邻域连通像素数量最大且激光距离最小的第一有效激光点对应的栅格；其中，一个第一有效激光点对应的栅格的预设范围覆盖到该第一有效激光点对应的栅格；其中，一个第一有效激光点的最佳邻域连通像素数量是该第一有效激光点对应的栅格的预设范围与预配置地图的重叠区域内，所有栅格的连通像素数量当中的最大值；一个栅格对应一个连通像素数量；其中，第一有效激光点是激光距离处于预设探测距离范围内的激光点。

进一步地，所述在预配置地图内搜索出满足第一预设连通条件的栅格的方法包括每当搜索完一个第一有效激光点对应的栅格的预设范围内所有栅格，则将最佳邻域连通像素数量大于预设像素数量阈值的第一有效激光点标记为第一一目标激光点；当搜索完每个第一有效激光点对应的栅格的预设范围内所有栅格时，若判断到只存在一个第一二目标激光点，则将第一二目标激光点对应的栅格标记为满足第一预设连通条件的栅格，并将第一二目标激光点对应的栅格的坐标标记为最优碰撞点在所述预配置地图内的坐标，并确定第一二目标激光点所在的物理位置点是最优碰撞点；当搜索完每个第一有效激光点对应的栅格的预设范围内所有栅格时，若判断到存在至少两个第一二目标激光点，则将激光距离最小的第一二目标激光点对应的栅格标记为满足第一预设连通条件的栅格，并将激光距离最小的第一二目标激光点对应的栅格的坐标标记为最优碰撞点在所述预配置地图内的坐标，并确定第一二目标激光点所在的物理位置点是最优碰撞点；其中，第一二目标激光点是在预配置地图内，最佳邻域连通像素数量最大的第一一目标激光点。

进一步地，在搜索完每个第一有效激光点对应的栅格的预设范围内所有栅格后，若在预配置地图内搜索不出连通像素数量大于预设像素数量阈值的栅格，则确定在预配置地图内搜索不出满足第一预设连通条件的栅格，然后开始在所述预配置地图内搜索所述满足第二预设连通条件的栅格；其中，连通像素数量用于反映障碍物的尺寸，以使得满足第一预设连通条件的栅格或满足第二预设连通条件的栅格被配置为所述连续型障碍物所占用的栅格。

进一步地，满足第二预设连通条件的栅格是：在预配置地图内，最佳邻域连通像素数量大于预设像素数量阈值且激光距离最小的第二有效激光点对应的栅格；其中，一个第二有效激光点对应的栅格的预设范围都覆盖到该第二有效激光点对应的栅格；其中，一个第二有效激光点的最佳邻域连通像素数量是该第二有效激光点对应的栅格的预设范围与预配置地图的重叠区域内，所有栅格的连通像素数量当中的最大值；其中，第二有效激光点是激光距离与机身尺寸相关联的激光点；第二有效激光点在预配置地图内的分布范围大于第一有效激光点在预配置地图内的分布范围。

进一步地，所述在预配置地图内搜索出满足第二预设连通条件的栅格的方法包括每当搜索完一个第二有效激光点对应的栅格的预设范围内所有栅格，则在检测到最佳邻域连通像素数量大于预设像素数量阈值的第二有效激光点时，将该第二有效激光点标记为第二一目标激光点；当搜索完每个第二有效激光点对应的栅格的预设范围内所有栅格时，将激光距离最小的第二一目标激光点对应的栅格标记为满足第二预设连通条件的栅格，并将第二一目标激光点对应的栅格的坐标标记为最优碰撞点在预配置地图内的坐标，并确定第二一目标激光点所在的物理位置是最优碰撞点。

进一步地，当搜索完每个第二有效激光点对应的栅格的预设范围内所有栅格后，若在预配置地图内搜索不出连通像素的数量大于预设像素数量阈值的栅格，则确定在预配置地图内搜索不出满足第二预设连通条件的栅格，然后在所述激光帧内搜索激光距离最小的激光点，再将激光点对应的栅格的坐标标记为最优碰撞点在预配置地图内的坐标，并确定该激光点所在的物理位置是最优碰撞点。

进一步地，激光点对应的栅格的坐标的来源包括：以激光点的激光距离的三角函数换算结果为坐标偏移量，对该激光点进行坐标偏移，再按照预设比率将经过坐标偏移的激光点的坐标换算为栅格坐标，实现将该激光点转换到所述预配置地图的坐标系内。

进一步地，激光传感器的有效探测角度范围是0度至360度，激光帧中存在360个激光点，分别对应360个不同的激光距离；其中，激光点的激光距离跟随该激光点所处的单位探测角度的变化而变化，该激光点所处的单位探测角度是处于激光传感器的有效探测角度范围内。

进一步地，激光点对应的栅格的预设范围是该激光点对应的栅格的邻域栅格范围，包括该激光点对应的栅格。

进一步地，所述激光点对应的栅格的预设范围是该激光点对应的栅格的四邻域，包括以该激光点对应的栅格、以及以该激光点对应的栅格为中心的上下左右的相邻栅格，以减少坐标的计算量。

进一步地，每个激光点对应的栅格在所述预配置地图内使用像素点表示，每个像素点使用栅格表示；所述预配置地图是属于机器人的激光传感器采集的激光点所映射出的特定尺寸的图像；其中，在所述预配置地图内，每个障碍物都是由像素值相同且相邻接的像素点组成，使得每个障碍物在所述预配置地图内由相邻接的栅格组合成。

进一步地，一个栅格的连通像素数量是该栅格所处的连通域内所包含的栅格的数量，使得一个激光点对应的栅格与一个连通域相对应；其中，连通域是由像素值相同且位置相邻的像素点组成的图像区域、或由具有相同像素值的相邻栅格组成的栅格集合，同一个连通域内的每个栅格或每个像素点都有相同的连通像素数量。

进一步地，在所述预配置地图内搜索出满足预设连通条件的栅格之前，先对所述预配置地图进行闭操作，使得所述预配置地图中标记的障碍物的轮廓线得到完整的描述，其中，所述闭操作用于连接所述预配置地图中的连通域；其中，所述预配置地图是属于机器人构建出的用于描述激光点的位置特征的特定尺寸的图像。

进一步地，所述闭操作包括在将所述预配置地图二值化处理后，获得二值化地图；然后对二值化地图进行图像膨胀处理，再对经过图像膨胀处理后的二值化地图进行图像腐蚀处理，使得部分表示非障碍物的像素点被配置为表示障碍物的像素点；其中，二值化地图中，表示障碍物的像素点的像素值和表示非障碍物的像素点的像素值不同。

一种芯片，内置控制程序，所述控制程序用于控制机器人执行所述的最优碰撞点搜索方法。

.一种机器人，该机器人装配有支持360度探测的激光传感器，该机器人内置所述的芯片。

与现有技术相比，本发明在一个预配置地图内，先在分布范围较小的激光点对应的栅格的预设范围内搜索满足第一预设连通条件的栅格，再将该满足第一预设连通条件的栅格的坐标标记为最优碰撞点的坐标；若在分布范围较小的激光点对应的栅格的预设范围内搜索不出满足第一预设连通条件的栅格，则在分布范围较大的激光点对应的栅格的预设范围内搜索出满足第二预设连通条件的栅格，再将该满足第二预设连通条件的栅格的坐标标记为最优碰撞点的坐标，从而，本发明能够在距离机器人机体最近的尺寸最大的连续型障碍物中搜索出一个最优碰撞点，克服现有技术中采集的激光数据（包括激光点的坐标、探测角度及激光距离）存在噪声或地图不稳定的问题，过滤所述预配置地图对应的图像区域中的噪声信息，减少选择孤立障碍物与机器人相碰撞的位置作为所述最优碰撞点的概率，进而减少机器人优先选择孤立障碍物作沿边行走的概率；也减少选择实际物理环境中无法与障碍物相碰撞的位置或无法检测到障碍物的位置作为机器人沿边行走的起点的概率，增强搜索出的所述最优碰撞点的环境适应性。

附图说明

图1是本发明的一种实施例公开的基于激光点的最优碰撞点搜索方法的流程图。

图2是本发明的另一种实施例公开的搜索满足第一预设连通条件的栅格的方法的流程图。

图3是本发明的又一种实施例公开的搜索满足第二预设连通条件的栅格的方法的流程图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行详细描述。为进一步说明各实施例，本发明提供有附图。这些附图为本发明揭露内容的一部分，其主要用以说明实施例，并可配合说明书的相关描述来解释实施例的运作原理。配合参考这些内容，本领域普通技术人员应能理解其他可能的实施方式以及本发明的优点。作为流程图描绘的处理或方法。虽然流程图将各步骤描述成顺序的处理，但是其中的许多步骤可以被并行地、并发地或者同时实施。此外，各步骤的顺序可以被重新安排。当其操作完成时所述处理可以被终止，但是还可以具有未包括在附图中的附加步骤。所述处理可以对应于方法、函数、规程、子例程、子程序等等。

作为一种实施例，本发明实施例提供的一种基于激光点的最优碰撞点搜索方法，该最优碰撞点搜索方法可由激光点云数据处理装置执行，该激光点云数据处理装置可以由软件和/或硬件实现，一般可集成在激光导航机器人中，则该激光导航机器人可以作为方法的执行主体，这个激光导航机器人上可以设置激光传感器，该激光传感器可以检测障碍物，该激光传感器发射的激光束扫描到机器人的机身周边物体表面反射回的数据形成周边物体的点云数据，则可以将机身周边物体识别为障碍物并标记在地图中，其中，点云数据包括激光传感器的激光光束扫描到的障碍物表面的位置信息，即扫描到的障碍物表面相对于激光传感器的纵向距离、横向偏移量及探测角度，点云可以视为激光点的集合，在构建地图时使用激光帧对激光点进行划分，激光帧是激光传感器360度扫描的激光点的集合，即一帧点云。一个激光点的数据表示激光传感器的一个探测角度方向上发射的激光光束所扫描到的障碍物表面的位置信息（包括激光距离）。一般场景下，激光导航机器人在室内移动过程中，可以通过设置在该激光导航机器人上的激光传感器检测周围是否存在障碍物并即时标记在地图上，此时需要使用到最新产生的激光帧，激光帧中包括多个激光点，可视为激光点的集合，激光帧数据包括激光点的数据，在往地图中标记障碍物信息时需要使用到激光帧所包括的激光点，从而基于SLAM技术对所述激光导航机器人的周围环境构建二维点云模型，可以由预先获得的激光帧构建出预配置地图；以下将激光导航机器人简称为机器人。所述预配置地图是未经过所述最优碰撞点搜索方法处理过的地图，是预先构建出的机器人的第一个工作区域的地图，可以标记有机器人所在的房间区域中的距离最远的障碍物，以使得机器人在第一个工作区域内存在足够大的可通行区域，其中，机器人的第一个工作区域的面积小于机器人所在的房间区域的面积。优选地，所述预配置地图是矩形地图区域，矩形地图区域的长度和宽度都是预先根据实际工作环境的尺寸进行适应性的配置或根据障碍物的分布特征进行适应性的配置。

具体地，机器人内部的控制器实时读取激光传感器采集到的激光点云数据或包括激光点云数据的深度图像，构建起点云模型以创建点云地图，通过将激光雷达坐标系或像素坐标转换为世界坐标，将点云地图投影并转换为可用于导航的二维栅格地图，即预配置地图，作为二维点云地图，反映机器人在行进平面所探测的环境信息，该预配置地图视为地图图像，并随之转换出与所述预配置地图（二维点云地图）的点云位置一一对应的二维的路标信息，以便于在所述预配置地图内进行相关的图像处理操作。在所述预配置地图的地图坐标系中，即前述二维栅格坐标系中，所述预配置地图的地图坐标系的原点可定义在机器人的驱动轮、激光传感器的装配位置或机体中心位置，在此不作限制。在所述预配置地图中，每个栅格的坐标是该栅格的左下角点的坐标、该栅格的左上角点的坐标或该栅格的右下角点的坐标，在一些实施场景下，使用栅格的中心位置表示被扫描区域的真实地理位置，每个栅格的坐标会使用该栅格的中心位置的坐标表示。其中，该栅格的相关边角点及中心位置的坐标还可以表示该栅格在预配置地图中的行序号和列序号，横坐标等于列序号，纵坐标等于行序号，在本实施例中，激光点对应的栅格的坐标是激光点转换到所述预配置地图中坐标，也称之为激光点的地图坐标，相应地，激光点对应的栅格是对应为或直接理解为激光点对应的地图坐标点；激光点对应的栅格的坐标是直接理解为激光点的地图坐标。

在预配置地图的一些实施例中，从左到右遍历栅格，列序号逐步递增；从下到上遍历栅格，行序号逐步递增。从而保证所述预配置地图内逐个栅格连接生成的路径是连续的。优选地，所述预配置地图或所述预配置地图所在的全局栅格地图由行单元格和列单元格组成，由单元格左上角起始，行方向作为y坐标，列方向作为x坐标，每个单元格的坐标由其行列位置定义，每个单元格是所述栅格。一个激光点对应的栅格使用单个单元格代表，然后用一系列相邻单元格代表线，邻接单元格的集合可以代表区域，每个单元格有一个值，，用于表示类别数据，如标记的环境信息类型、障碍物的类型。

在本实施例中，机器人的激光传感器采集的每个激光点对应的栅格在所述预配置地图内使用像素点表示，每个像素点使用特定尺寸的栅格表示，这里的特定尺寸的栅格是前述二维栅格地图中的每个栅格，像素点作为所述预配置地图中单元像素，当然，栅格作为所述预配置地图中的单位栅格，使得一个激光点对应一个栅格；优选地，所述预配置地图将像素点配置为栅格的地图配置条件下，机器人将一个像素点配置为5厘米乘以5厘米的单元格，作为填充所述预配置地图的栅格，此时，栅格等效于5厘米乘以5厘米的单元格，且一个激光点对应一个栅格，因此，在本实施例中，针对一个所述预配置地图或该预配置地图中的局部地图，一个栅格也只对应一个连通域，这个连通域的大小就是相连通的像素点的个数，也称为连通数，可以选择存储于相应的栅格内。其中，组成连通域的像素点的数量能反映障碍物的尺寸。

在沿边导航场景中，一般先控制机器人搜索出最近的墙体障碍物，在导航到该最近的墙体障碍物后与其表面发生触碰后，机器人将这个相碰触的位置设置为沿边起点，则机器人从这个相碰触的沿边起点开始，调整机器人的前进方向，使得机器人沿着墙面开始执行沿边行走，机器人也可以在相同的碰撞场景下沿着一定区域范围内连续性的障碍物边界（同一房间内的四面墙壁，四面墙壁是连续的、一体的，不属于孤立障碍物）执行沿边行走，需要补充的是，墙体障碍物包括贴住墙体的障碍物、墙体及其附属的物体，即本发明将靠墙物分布并贴住墙体的物体视为墙体。此时，机器人与该最近的墙体障碍物中的一个障碍物碰撞点发生碰触，本发明需要搜索出一个最合适的障碍物碰撞点，同时也确定出这个障碍物碰撞点存在合适的便于机器人沿边行走的连续型障碍物，以便于机器人导航至与这个障碍物碰撞点相碰触的位置或相碰撞的位置，然后机器人在未开始移动之前将这个位置配置为机器人沿边起点，则为了开始进入沿边工作模式，机器人优先导航至这个机器人沿边起点并机体上与所述最合适的障碍物碰撞点相接触。然后，机器人只有沿完外轮廓，才会开始正常工作；但是，由于机器人只能通过激光点的数据去感知环境，而激光帧的数据（一帧点云数据、一帧激光点的数据或一帧激光数据）只有360度的激光点的数据，所以识别墙体一类的连续型障碍物的准确度不高，再加上采集的激光点不稳定，一帧激光数据（激光点的数据）容易存在噪声，导致预配置地图中标记出的墙壁边界出现缺口，或导致机器人将孤岛的障碍物（突起且不可跨越且不可推动的障碍物）识别为墙体以使其优先绕着柱子沿边行走。

本发明实施例通过执行所述最优碰撞点搜索方法，来找到离机器人的机体距离最短的有效的墙体位置点，即相应的墙体在地面的投影位置点，配置为所述最优碰撞点。所述最优碰撞点搜索方法的基本构思包括：机器人在所述预配置地图内搜索出满足预设连通条件的栅格，再将该满足预设连通条件的栅格的坐标标记为最优碰撞点在预配置地图内的坐标，并确定满足预设连通条件的栅格对应的激光点所反映的物理位置是最优碰撞点，其中，预设连通条件可以是多个用于识别出墙体等具备连续型障碍物边界一类的障碍物的不同的连通条件，包括像素点个数的数量特征的连通条件，则满足任一个连通条件的栅格对应的激光点都可以配置出最优碰撞点，满足任一个连通条件的栅格对应的激光点的坐标作为最优碰撞点在实际物理环境中的坐标，该激光点对应的栅格的坐标作为最优碰撞点在预配置地图中的坐标，并确定所述最优碰撞点处存在连续型障碍物，所述最优碰撞点处存在的连续型障碍物是在所述预配置地图内所搜索到的尺寸最大的连续型障碍物，同时，所述最优碰撞点是所搜索到的尺寸最大的连续型障碍物中距离机器人的机体最近的一个位置点。需要说明的是，机器人采集的激光点与所述预配置地图中的栅格相对应，机器人当前采集的激光数据，都能够转换至机器人构建的地图的栅格上，以便于计算处理相连通的栅格，但是激光点对应的栅格的邻域可能超出预配置地图的边界。可选地，在执行所述最优碰撞点搜索方法之前，机器人当前采集的激光数据已经实时地转换到所述预配置地图中，可能以不稳定的状态标记出障碍物信息。因此，本发明实施例需要根据采集到的激光点在地图上的落点的特定连通条件，搜索出墙体一类的连续型障碍物，进而确定最优碰撞点，减少搜索出的最优碰撞点处没有障碍物的现象的发生机率，克服机器人最新采集的激光数据不稳定而带来的误判问题。

需要说明的是，启动机器人开始在所述预配置地图限定的区域沿边行走时，最优碰撞点所属的障碍物是机器人所沿的第一个障碍物，此时机器人的沿边起点不是最优碰撞点，而是最优碰撞点附近的允许机器人接触最优碰撞点所属的障碍物的位置点，此时机器人可以确定第一个导航目标位置处能接触到最优碰撞点所属的障碍物。

在一种实施的方式中，机器人实时探测到的墙体后，本实施例等效于将墙体的实时探测数据投影于所述预配置地图内，形成墙体所在的地面区域；然后通过区域连通域算法(Connected Components With Stats) 将所述墙体构建为所述预配置地图的二维平面边界，使得所述墙体的探测数据被机器人转换为墙体所在的地面区域，可以是理解为实际探测到的属于墙体的轮廓边界线段投影于地面的线段，即将本实施例公开的连续型障碍物在所述预配置地图中的表示形式，可以作为机器人的第一个工作区域的边界线。

需要说明的是，机器人从房间内任意位置出发寻找墙体障碍物（连续型障碍物），检测到墙体时或与墙体碰撞时，触发机器人进入沿边行走的工作模式，则在沿边行走的工作模式下，机器人调整其前进方向平行于墙面轮廓线或墙体在地面投影出的边界线，即实现沿边；同时设置一个适用于机器人的沿边起点，属于一种导航目标点，这个沿边起点也可以是机器人与障碍物相碰撞的位置点，但不是前述的最优碰撞点，可以在最优碰撞点对应栅格的邻域中或在最优碰撞点的预设距离范围内，且不被障碍物所占据；然后机器人沿着当前前进方向行走，保持当前前进方向与墙面轮廓线或墙体在地面投影出的边界线相平行，即实现沿边行走。

另外，在机器人实时构建的地图（可以等效于所述预配置地图）中记录此时机器人的坐标以及机器人前进的角度（机器人前进方向相对于地图坐标系的X轴方向的角度或机器人前进方向相对于地图坐标系的Y轴方向的角度），再从这个沿边起点开始保持平行于墙面作沿边行走（沿墙行走），其中，机器人前进方向被调整为与墙面延伸方向平行。

作为一种实施例，如图1所示，.基于激光点的最优碰撞点搜索方法包括：步骤S1、获取预配置地图，并获取激光帧；具体地，机器人获取到已经标记有障碍物信息的预配置地图，同时获取激光传感器当前采集的激光帧，包括当前采集的一帧激光点的数据（360度的有效探测角度范围内的采集的激光数据），以便于处理激光帧所包括的激光点的数据在预配置地图中的连通关系。然后进入步骤S2。

步骤S2、判断在所述预配置地图内是否搜索出满足第一预设连通条件的栅格，是则进入步骤S4，否则进入步骤S3。其中，前述实施例所述的预设连通条件包括第一预设连通条件或第二预设连通条件；在本实施例中，机器人在所述预配置地图内搜索的栅格可以是对应到采集到的一个激光点，这个激光点对应的栅格可以是作为一个种子栅格；需要说明的是，一个激光点落入所述预配置地图对应的一个栅格中，对应该激光点的坐标转换为所述预配置地图的一个栅格的坐标，但是一个栅格可以允许落入多个激光点，即不受限于同一激光帧的前提下，多个不同的激光点的坐标可以转换为同一个栅格的坐标；当前采集的激光点不一定落入该栅格的邻域栅格区域内。

步骤S3、判断在预配置地图内是否搜索出满足第二预设连通条件的栅格，是则进入步骤S5，否则进入步骤S6。机器人判断到其在预配置地图内搜索不出满足第一预设连通条件的栅格后，转而判断在预配置地图内是否搜索出满足第二预设连通条件的栅格。其中，本实施例对满足第一预设连通条件的栅格和满足第二预设连通条件的栅格所适用的地图区域范围不同；可选地，满足第一预设连通条件的栅格适用的地图区域范围小于满足第二预设连通条件的栅格适用的地图区域范围，激光点在两种地图区域范围内分布的密集程度不同。在一些实施例中，机器人在激光帧中所包含的每个激光点对应的栅格的预设范围内搜索出满足第一预设连通条件的栅格时，执行步骤S4，否则执行步骤S3。

步骤S4、将满足第一预设连通条件的栅格的坐标标记为最优碰撞点在所述预配置地图内的坐标，即最优碰撞点在相应的地图坐标系内的坐标。机器人在所述预配置地图中搜索出满足第一预设连通条件的栅格后，获取满足第一预设连通条件的栅格的坐标，被配置为最优碰撞点在预配置地图的坐标系中的坐标，相应地，机器人可以获取到该栅格对应的激光点的坐标，作为最优碰撞点在实际物理环境内（激光雷达坐标系中）的定位坐标。

步骤S5、将满足第二预设连通条件的栅格的坐标标记为最优碰撞点在所述预配置地图内的坐标，即最优碰撞点在相应的地图坐标系内的坐标。机器人在所述预配置地图中搜索出满足第二预设连通条件的栅格后，获取满足第二预设连通条件的栅格的坐标，被配置为最优碰撞点在预配置地图的坐标系中的坐标，相应地，机器人可以获取到该栅格对应的激光点的坐标，作为最优碰撞点在实际物理环境内（激光雷达坐标系中）的定位坐标。

步骤S6、在激光帧内搜索出激光距离最小的激光点，再将该激光点对应的栅格的坐标标记为最优碰撞点在预配置地图内的坐标。在该步骤S6中，机器人搜索不出满足第一预设连通条件的栅格，且机器人搜索不出满足第二预设连通条件的栅格后，机器人在当前采集好的激光帧内，将激光距离最小的激光点配置为最优碰撞点，并将该激光点的坐标标记为最优碰撞点在激光雷达坐标系中的坐标。其中，机器人当前在所述预配置地图内所搜索到的栅格对应的激光点都是来源于机器人当前采集到的激光帧；一个激光点对应一个激光距离。

前述步骤S1至S6所述最优碰撞点搜索方法，根据激光点的数据在预配置地图内满足连通条件的情况，求得所述最优碰撞点，实现通过枚举激光点的方式来过滤预配置地图中的杂点，对于不稳定地图及不稳定激光数据有一定的适应性，避免机器人开始沿边行走的位置附近没有障碍物。

在前述实施例中，该激光传感器发射的激光束扫描到机器人的机身周边物体表面反射回的数据形成周边物体的点云数，激光点是用于表征机器人的激光传感器发射的激光在障碍物上的反射位置，激光点是来源于机器人采集到的激光帧，激光帧是激光传感器360度扫描的激光点的集合，即一帧点云；最优碰撞点是位于连续型障碍物占据的一个位置，比如墙体的一个边界点、或缺口位置；其中，激光点是位于激光传感器的有效探测角度范围内，并映射到所述预配置地图的对应栅格中，具体是激光数据由激光雷达坐标系转换到地图坐标系，能够将激光距离转换为使用栅格表示。在有效探测角度范围内，一个激光点对应一个单位探测角度（激光传感器发射的激光束的扫描角度），一个激光点对应一个栅格，一个激光点对应一个激光距离，激光距离用于反映所探测的障碍物与机器人所安装的激光传感器之间的距离大小，激光距离可以是障碍物的反射位置与机器人的机体中心的距离，可以根据地图坐标系的设置方式而调整，所述预配置地图的地图坐标系的原点可定义在机器人的驱动轮、激光传感器的装配位置或机体中心位置，在此不作限制。在本实施例中，激光传感器的有效探测角度范围是0度至360度，激光帧中存在360个激光点，分别对应360个不同的激光距离，则在相应的栅格空间中，存在0度的单位探测角度处的激光距离是1米，存在1度的单位探测角度处的激光距离是1.1米；因而，本实施例每个单位探测角度内存在一个激光点并匹配一个激光距离，对应激光帧，不同激光点的激光距离不相等。从而便于将激光传感器采集具有数据量大且离散性较高的激光点统一转换至所述预配置地图的地图坐标上，既使获得的离散激光点的数据能够在同一坐标系中进行描述，也便于在同一坐标系中对属于同一连通域内的坐标信息和栅格数量进行识别整理。

在上述实施例的基础上，满足第一预设连通条件的栅格是：在预配置地图内，最佳邻域连通像素数量大于预设像素数量阈值、最佳邻域连通像素数量最大且激光距离最小的第一有效激光点对应的栅格。在本实施例中，满足第一预设连通条件的栅格的来源包括在落入所述预配置地图的激光点中，以第一有效激光点对应的栅格为中心栅格（种子栅格），在该中心栅格及其邻域栅格中的每个栅格对应的连通像素数量中筛选出数值最大的连通像素数量，作为第一有效激光点对应的栅格的最佳邻域连通像素数量，参与落入（转换至）所述预配置地图中的每个第一有效激光点的最佳邻域连通像素数量的比较，则可以实现在预配置地图内，最佳邻域连通像素数量大于预设像素数量阈值、最佳邻域连通像素数量最大且激光距离最小的第一有效激光点对应的栅格，作为满足第一预设连通条件的栅格。可选地，每个第一有效激光点对应的栅格的预设范围内所有栅格不一定都是位于预配置地图内，第一有效激光点对应的栅格不一定都是在预配置地图内，激光距离处于预设探测距离范围内的激光点。优选地，预设探测距离范围是大于机器人的机身半径（机器人是外壳为圆形的扫地机器人时），但小于1.5米，则处于预设探测距离范围内的激光距离的激光点都是第一有效激光点，使用第一有效激光点的连通像素数量的特征去搜索满足要求的栅格，能够在连通区域较大的区域范围内搜索出有效的连续型障碍物的轮廓点，排除更多的孤立障碍物反射回的激光点的数据信息的干扰，减少将不可忽略的长度的孤立障碍物线段拟合为物理墙体的概率，减小轮廓线段误判为墙体的影响。

在本实施例中，一个第一有效激光点对应的栅格的预设范围覆盖到该第一有效激光点对应的栅格，具体地，所述第一有效激光点对应的栅格的预设范围是该第一有效激光点对应的栅格的邻域栅格范围，包括该第一有效激光点对应的栅格；本实施例中对第一有效激光点配置预设范围是考虑到第一有效激光点或第一有效激光点对应的栅格会存在噪声因素，需以第一有效激光点对应的栅格为中心栅格朝着预设扩展方向向外围扩展一个栅格，再在扩展后的栅格区域内进行搜索。一个第一有效激光点的最佳邻域连通像素数量是该第一有效激光点对应的栅格的预设范围与所述预配置地图的重叠区域内，所有栅格的连通像素数量当中的最大值，通过枚举比较前述重叠区域内的每个栅格的连通像素数量，可获得连通像素数量最大的一个栅格，此时将该第一有效激光点的预设范围内的数值最大的连通像素数量配置为第一有效激光点的最佳邻域连通像素数量，因为最佳邻域连通像素数量是以第一有效激光点对应的栅格为中心栅格扩展出的栅格区域内的搜索结果，有利于搜索出尺寸较大的连续型障碍物，比如墙体；从而排除非连续型的障碍物（木条、柱子等孤立的不可跨越的突起障碍物）直线的干扰作用，提高机器人区分墙体与非墙体障碍物的准确性和智能化水平。

需要说明的是，一个栅格对应一个连通像素数量，而在一些实施例中，一个第一有效激光点对应的栅格的预设范围内的所有栅格可能是相互连通，形成一个独立的连通域，则一个第一有效激光点对应的栅格的预设范围内的所有栅格的连通像素数量都相等。

值得注意的是，一个激光点落入所述预配置地图对应的一个栅格中，对应该激光点的坐标转换为所述预配置地图的一个栅格的坐标，但是对应不同激光帧，一个栅格可以允许落入多个激光点，多个不同的激光点的坐标可以转换为同一个栅格的坐标；在一些实施例中，一个栅格的预设范围包括该栅格自身及其邻域栅格区域，但其邻域栅格区域不一定落入相应的激光点，可能在该预设范围内，只有该栅格处落入激光点。

作为一种实施例，如图2所示，所述在预配置地图内搜索出满足第一预设连通条件的栅格的方法包括：

步骤S201、每当搜索完一个第一有效激光点对应的栅格的预设范围内所有栅格，则将最佳邻域连通像素数量大于预设像素数量阈值的第一有效激光点标记为第一一目标激光点；然后进入步骤S202。具体地，机器人在一个第一有效激光点对应的栅格的预设范围内搜索栅格的过程中，会对预配置地图内的每个栅格的连通像素数量进行排序和比较，获取最大的连通像素数量，再将最大的连通像素数量配置为第一有效激光点的最佳邻域连通像素数量，当最佳邻域连通像素数量大于预设像素数量阈值时，该第一有效激光点标记为第一一目标激光点。优选地，预设像素数量阈值是配置为16，同时，第一有效激光点对应的栅格的预设范围是第一有效激光点对应的栅格的四邻域，有利于过滤无效激光数据；一个激光点的最佳邻域连通像素数量能够反映该激光点所在的障碍物的尺寸特征，当所需搜索的障碍物的尺寸越大，障碍物的连续性的轮廓线越长，则对应的最佳邻域连通像素数量越大，则需要将预设像素数量阈值配置得越大，可以用于识别墙。

需要说明的是，每个栅格的连通像素数量是预先获得的，并按照该栅格在所述预配置地图中的坐标信息存储在机器人内部的相关联的索引地址中，该栅格的坐标相对于地图坐标系的原点的坐标偏移量与该索引地址相关联，在一些实施例中，可以将该栅格相对于原点的纵坐标偏移量乘上所述预配置地图在横轴方向上的长度再加上该栅格相对于原点的横坐标偏移量，获得结果作为该栅格的连通像素数量的索引地址，优选地，该栅格在所处的连通域信息也存储在该索引地址中。

具体地，在所述步骤S201中，每当在第一有效激光点对应的栅格的预设范围与所述预配置地图内搜索到连通像素数量最大的栅格后，等效于在所述预配置地图内的第一有效激光点对应的栅格的预设范围搜索到连通像素数量最大的栅格后，若判断到该栅格的连通像素数量大于预设像素数量阈值，则将该第一有效激光点标记为第一一目标激光点，将该栅格的连通像素数量标记为第一一目标激光点对应的最佳邻域连通像素数量，并将该第一有效激光点的激光距离标记为第一一目标激光点的激光距离，同时记录下第一一目标激光点的激光距离和最佳邻域连通像素数量，便于在与后续搜索出相同类型的信息进行比较，以获得更大数值的最佳邻域连通像素数量，实现连续型障碍物的准确识别。

步骤S202、搜索完每个第一有效激光点对应的栅格的预设范围内所有栅格时，判断是否只存在一个第一二目标激光点，是则进入步骤S203，否则进入步骤S204。在本实施例中，机器人先后在各个第一有效激光点对应的栅格的预设范围内完成每个栅格的连通像素数量的枚举和比较后，获得第一二目标激光点，至此，机器人完成落入预设探测距离范围内的所有激光点的遍历，且完成预设探测距离范围内的所有栅格或邻域栅格的搜索，即在大于一个机身半径，且小于1.5米或其余受限制的有效探测距离内完成栅格的连通像素数量的搜索。

需要说明的是，每当在所述预配置地图限定的区域内搜索完所有第一有效激光点对应的栅格的预设范围内的栅格，则将连通像素数量最大的第一一目标激光点标记为第一二目标激光点；则第一二目标激光点是在预配置地图内，最佳邻域连通像素数量最大的第一一目标激光点。

步骤S203、确定检测到只存在一个第一二目标激光点，则将第一二目标激光点对应的栅格标记为满足第一预设连通条件的栅格，并将第一二目标激光点对应的栅格的坐标标记为最优碰撞点在所述预配置地图内的坐标，并确定第一二目标激光点所在的物理位置点是最优碰撞点，并确定第一二目标激光点对应的栅格处存在所述连续型障碍物，即机器人识别出墙体类型的连续型障碍物以供机器人进行沿边行走。

步骤S204、确定检测到存在至少两个第一二目标激光点，则将激光距离最小的第一二目标激光点对应的栅格标记为满足第一预设连通条件的栅格，并将激光距离最小的第一二目标激光点对应的栅格的坐标标记为最优碰撞点在所述预配置地图内的坐标，并确定第一二目标激光点所在的物理位置是最优碰撞点，并确定第一二目标激光点对应的栅格被所述连续型障碍物占据，即机器人识别出墙体类型的连续型障碍物，以供机器人进行沿边行走。

综上，步骤S201至步骤S204在分布范围受限的激光点对应的栅格的预设范围内搜索满足第一预设连通条件的栅格，再将该满足第一预设连通条件的栅格的坐标标记为最优碰撞点的坐标，从而在较为靠近的机器人的机身的区域搜索出有效的连续型障碍物的边界点，即通过搜索数值最大的连通像素数量来获得满足第一预设连通条件的栅格，以此栅格对应的激光点作为最优碰撞点，实现在较小地图区域内通过枚举激光点的方式，来在连通区域较大的栅格区域内搜索出最优碰撞点对应的栅格。后续，机器人导航至与最优碰撞点处的障碍物接触后开始启动沿边行走，具体是沿着所接触的障碍物的轮廓边缘进行行走，其前进方向与障碍物的轮廓线保持平行。

需要补充的是，在机器人工作的室内环境中，缺口左右端点两侧的障碍物边界是指在一定区域范围内具有连续性的障碍物边界，通常包含多个边界点，而不是只有一个边界点。如，缺口可以是房间的门洞，门洞两侧的障碍物是同一房间内的四面墙壁，四面墙壁是连续的、一体的，不属于孤立障碍物。因此，本实施例可以通过前述步骤S201至步骤S204区分出墙体障碍物和孤岛的障碍物（突起且不可跨越且不可推动的障碍物），克服机器人仅通过激光帧所包含的激光数据不能准确识别出墙体的问题，比如，避免靠近一个木条而将木条中距离机器人最近的位置点判断为所述最优碰撞点，使得机器人沿着该木条进行沿边行走。

在上述实施例的基础上，在搜索完每个第一有效激光点对应的栅格的预设范围内所有栅格后，若在预配置地图内搜索不出连通像素数量大于预设像素数量阈值的栅格，则确定在预配置地图内搜索不出满足第一预设连通条件的栅格，然后机器人由执行步骤S2转而执行步骤S3，开始在在所述预配置地图内搜索所述满足第二预设连通条件的栅格，实现在新的范围区域内激光点对应的栅格中搜索所述满足第二预设连通条件的栅格。对应地，在所述预配置地图内，机器人在所有第一有效激光点对应的栅格的预设范围内所有栅格中搜索不出连通像素数量大于预设像素数量阈值的栅格时，确定不能将第一有效激光点对应的栅格标记为满足第一预设连通条件的栅格，机器人搜索出的每个第一有效激光点对应的栅格的预设范围内的栅格的连通像素数量都比较小，不足以用来描述墙体等连续型的障碍物；需要说明的是，连通像素数量用于反映障碍物的尺寸以使得满足第一预设连通条件的栅格或满足第二预设连通条件的栅格被配置为所述连续型障碍物所占用的栅格。

作为一种实施例，满足第二预设连通条件的栅格是：在预配置地图内，最佳邻域连通像素数量大于预设像素数量阈值且激光距离最小的第二有效激光点对应的栅格。在本实施例中，机器人在落入所述预配置地图的激光点中，以第二有效激光点对应的栅格为中心栅格（种子栅格），在该中心栅格及其邻域栅格中的每个栅格对应的连通像素数量中筛选出数值最大的连通像素数量，作为第二有效激光点对应的栅格的最佳邻域连通像素数量，再进一步筛选出最佳邻域连通像素数量大于预设像素数量阈值且激光距离最小的第二有效激光点对应的栅格，作为满足第二预设连通条件的栅格，相比于满足第一预设连通条件的栅格，不追求最佳邻域连通像素数量是最大值，降低对障碍物的轮廓线连续程度的要求，转而追求距离最近的激光点，此时所搜索的地图区域内落入的激光点的分布密集度较高。可选地，每个第二有效激光点对应的栅格的预设范围内的栅格不一定位于预配置地图内，一个第二有效激光点对应的栅格的预设范围都覆盖到该第二有效激光点对应的栅格；其中，第二有效激光点是激光距离与机身尺寸相关联的激光点。优选地，激光距离大于机器人的机身半径（机器人是外壳为圆形的扫地机器人时），以避免机器人的激光传感器在扫描探测的过程中碰撞到障碍物，则在落入所述预配置地图的激光点中，激光距离大于机器人的机身半径的激光点都是第二有效激光点；因此，第二有效激光点在预配置地图内的分布范围大于第一有效激光点在预配置地图内的分布范围，且落入或转换至预配置地图内的第二有效激光点的数量大于第一有效激光点的数量。在本实施例中，机器人使用第二有效激光点的连通像素数量的特征去搜索满足要求的栅格，能够在较近距离范围内搜索出有效的连续型障碍物边界，排除近距离处的孤立障碍物反射回的激光点的数据信息的干扰，减少机体周围的障碍物轮廓线段被误判为墙体的现象的发生。从而在覆盖面较大的地图区域内的激光点分布较为密集（被搜索的第二有效激光点的数量较多）的栅格区域搜索出所述满足第二预设连通条件的栅格。

在本实施例中，一个第二有效激光点对应的栅格的预设范围覆盖到该第二有效激光点对应的栅格，具体地，所述第二有效激光点对应的栅格的预设范围是该第二有效激光点对应的栅格的邻域栅格范围，包括该第二有效激光点对应的栅格；本实施例中对第二有效激光点配置预设范围是考虑到第二有效激光点或第二有效激光点对应的栅格会存在噪声因素，需以第二有效激光点对应的栅格为中心栅格朝着预设扩展方向向外围扩展一个栅格，再在扩展后的栅格区域内进行搜索。一个第二有效激光点的最佳邻域连通像素数量是该第二有效激光点对应的栅格的预设范围与所述预配置地图的重叠区域内，所有栅格的连通像素数量当中的最大值，通过枚举比较一个第二有效激光点对应的栅格的预设范围内的每个栅格的连通像素数量，可获得连通像素数量最大的一个栅格，此时将该第二有效激光点的预设范围内的数值最大的连通像素数量配置为第二有效激光点的最佳邻域连通像素数量，因为最佳邻域连通像素数量是以第二有效激光点对应的栅格为中心栅格扩展出的栅格区域内的搜索结果。从而在距离机器人的机身较近的区域内排除非连续型的障碍物（木条、柱子等孤立的不可跨越的突起障碍物）轮廓线的干扰作用，提高机器人区分近距离的墙体与非墙体障碍物的准确性和智能化水平，加快机器人开始执行沿边行走的速度。

作为一种实施例，如图3所示，所述在预配置地图内搜索出满足第二预设连通条件的栅格的方法包括：

步骤S301、每当搜索完一个第二有效激光点对应的栅格的预设范围内所有栅格，则在检测到最佳邻域连通像素数量大于预设像素数量阈值的第二有效激光点时，可以是检测到最佳邻域连通像素数量大于预设像素数量阈值的栅格对应的第二有效激光点时，将该第二有效激光点标记为第二一目标激光点；然后进入步骤S302。

具体地，机器人在一个第二有效激光点对应的栅格的预设范围内搜索栅格的过程中，会对预配置地图内的每个相关联的栅格的连通像素数量进行枚举和比较，获取最大的连通像素数量，再将最大的连通像素数量配置为第二有效激光点的最佳邻域连通像素数量，当最佳邻域连通像素数量大于预设像素数量阈值时，该第二有效激光点标记为第二一目标激光点。优选地，预设像素数量阈值是配置为16，同时，第二有效激光点对应的栅格的预设范围是第二有效激光点对应的栅格的四邻域，有利于过滤较近区域内的无效激光数据；一个激光点的最佳邻域连通像素数量能够反映该激光点所在的障碍物的尺寸特征，当所需搜索的障碍物越大，障碍物的连续性的水平轮廓越长，则对应的最佳邻域连通像素数量越大，则需要将预设像素数量阈值配置得越大，比如识别墙。

具体地，在所述步骤S301中，每当在第二有效激光点对应的栅格的预设范围内搜索到连通像素数量最大的栅格后，若判断到该栅格的连通像素数量大于预设像素数量阈值，则将该第二有效激光点标记为第二一目标激光点，并将该栅格的连通像素数量标记为第二一目标激光点对应的最佳邻域连通像素数量，并将该第二有效激光点的激光距离标记为第二一目标激光点的激光距离，同时记录下第一一目标激光点的激光距离，便于在与后续搜索出相同类型的信息进行比较，获得更小数值的激光距离，实现更近距离的连续型障碍物的准确识别。

步骤S302、当搜索完每个第二有效激光点对应的栅格的预设范围内所有栅格时，将激光距离最小的第二一目标激光点对应的栅格标记为满足第二预设连通条件的栅格，并将第二一目标激光点对应的栅格的坐标标记为最优碰撞点在预配置地图内的坐标，并确定第二一目标激光点所在的物理位置是最优碰撞点，并确定第二一目标激光点对应的栅格处存在所述连续型障碍物，比如识别到距离机器人较近的墙面中的位置点，表示为所述最优碰撞点，然后机器人可以花费更短的距离导航到所述最优碰撞点，再开始沿着该连续型障碍物进行沿边行走。

在本实施例中，机器人先后在各个第二有效激光点对应的栅格的预设范围内完成第二一目标激光点的激光距离的比较后，获得激光距离最小的第二一目标激光点，由于对于激光帧，每个激光点的激光距离都不同，所以激光帧落入所述预配置地图的激光点中，激光距离最小的激光点只有一个，则获得一个激光距离最小的第二一目标激光点，至此，机器人完成落入预设探测距离范围内的所有第二有效激光点的遍历，且完成大于机器人的机身半径的范围内的所有栅格的搜索，并实现在大于一个机身半径的较为全面的距离区域内完成激光距离的比较。因此，在分布范围较小的激光点对应的栅格的预设范围内搜索不出满足第一预设连通条件的栅格的基础上，在分布范围较大的激光点对应的栅格的预设范围内搜索出满足第二预设连通条件的栅格，再将该满足第二预设连通条件的栅格的坐标标记为最优碰撞点的坐标。

在上述实施例的基础上，当搜索完每个第二有效激光点对应的栅格的预设范围内所有栅格后，若在预配置地图内搜索不出连通像素的数量大于预设像素数量阈值的栅格，则确定在预配置地图内搜索不出满足第二预设连通条件的栅格，然后机器人由执行步骤S3转而执行步骤S6，实现在当前采集到激光帧内所有激光点对应的栅格中搜索激光距离最小的激光点，再将该激光点对应的栅格的坐标标记为最优碰撞点在预配置地图内的坐标，并确定该激光点所在的物理位置是最优碰撞点，并确定该激光点对应的栅格处存在所述连续型障碍物。相应地，机器人在所述预配置地图内既搜索不出满足第一预设连通条件的栅格，机器人在所述预配置地图内也搜索不出满足第二预设连通条件的栅格，则机器人按照所述有效探测角度范围内的每个单位探测角度搜索激光点，遍历并比较每个激光点的激光距离，从中获取激光距离最小的激光点，再将激光距离最小的激光点标记为最优碰撞点，并将激光距离最小的激光点对应的栅格的坐标标记为最优碰撞点对应的栅格的坐标，从而在不判断连通的栅格的前提下，让机器人在最近的墙面处获得一个最优碰撞点。

综上，本发明能够在距离机器人机体最近的连续型障碍物中获取一个最优碰撞点，克服现有技术中存在的激光数据（包括激光点的坐标、探测角度及激光距离）不稳定或噪声造成结果不稳定的问题，过滤预配置地图对应的图像区域中的噪声信息，减少选择孤立障碍物的轮廓处的位置作为最优碰撞点的概率，也减少选择实际物理环境中不存在障碍物的位置作为最优碰撞点的概率，机器人导航至与最优碰撞点处的障碍物接触后开始启动沿边行走，具体是沿着所接触的障碍物的轮廓边缘进行行走，其前进方向与障碍物的轮廓线保持平行，增强机器人沿边行走的环境适应性。

作为一种实施例，激光点对应的栅格的坐标的来源包括：在所述在预配置地图内，以该激光点的激光距离的三角函数换算结果为坐标偏移量，包括横轴坐标偏移量和纵轴坐标偏移量；可选地，该激光点的激光距离的三角函数换算结果中，横轴坐标偏移量是由一个参考横坐标加上该激光点的激光距离的余弦函数值获得；纵轴坐标偏移量是由一个参考纵坐标加上该激光点的激光距离的正弦函数值获得；实现将激光点的激光距离换算为坐标。然后，按照横轴坐标偏移量和纵轴坐标偏移量，控制该激光点进行坐标偏移，即按照横轴坐标偏移量和纵轴坐标偏移量控制激光点在激光雷达坐标系中的坐标进行坐标偏移计算；再按照预设比率将经过坐标偏移的激光点的坐标换算为栅格坐标，该栅格坐标是整数形式的栅格数，实现将该激光点转换到所述预配置地图的坐标系内，进而实现激光点在统一的坐标系内完成栅格化处理，让机器人获得的离散点云数据能够在同一个地图坐标系中进行描述。

在一些实施例中，前述坐标偏移计算的过程中需要考虑转换前后的坐标系的坐标轴方向；一般地，坐标偏移计算方式与转换前后的两个坐标系的横坐标轴的方向相关，当转换前后的两个坐标系的横坐标轴的正方向相同，则控制激光点在激光雷达坐标系中的横坐标减去横轴坐标偏移量，获得经过坐标偏移的激光点的横坐标；否则控制横轴坐标偏移量减去激光点在激光雷达坐标系中的横坐标，获得经过坐标偏移的激光点的横坐标。同理地，坐标偏移计算的方式与转换前后的两个坐标系的纵坐标轴的方向相关，当转换前后的两个坐标系的纵坐标轴的正方向相同，则控制激光点在激光雷达坐标系中的纵坐标减去纵轴坐标偏移量，获得经过坐标偏移的激光点的纵坐标；否则控制纵轴坐标偏移量减去激光点在激光雷达坐标系中的纵坐标，获得经过坐标偏移的激光点的纵坐标。

在一些实施例中，激光点的激光距离跟随激光点所处的探测角度的变化而变化，该激光点所处的探测角度是处于激光传感器的有效探测角度范围内，其中，每个激光点落入一个单位探测角度，每个激光点对应一个激光距离，每个激光距离对应一个单位探测角度。优选地，激光传感器的有效探测角度范围是0度至360度，则在激光帧中获取360个激光点，分别对应360个不同的激光距离，当单位探测角度是1度时，划分出360个区域，激光帧中每个激光点分别落入一个区域；对于激光帧，每个区域内的激光点的激光距离是不同的，且每个区域都属于栅格区域。其中，有效探测角度范围内包括有多个单位探测角度，一个有效探测角度范围内存在的单位探测角度的数量等于一帧点云（激光帧）内包括的激光点的数量。

在前述实施例中，激光点对应的栅格的预设范围是该激光点对应的栅格的邻域栅格范围，包括该激光点对应的栅格，其中，所述激光点包括第一有效激光点和第二有效激光点。该激光点对应的栅格的邻域栅格范围包括但不限于以该激光点对应的栅格为中心栅格的4邻域、8邻域、12邻域或圆形区域等，这些邻域都可以使用栅格表示。本实施例中设置预设范围是考虑到采集到的激光点会存在噪声因素，需以激光点对应的栅格为中心栅格朝着预设扩展方向向外围扩展一个邻域栅格，再在扩展后的栅格区域内进行搜索，才能减少中心栅格所携带的噪声因素带来的误差，同时在扩展后的栅格区域内更容易搜索出所述连续型障碍物，这也是基于区域的连通性考量的结果。

优选地，所述激光点对应的栅格的预设范围是该激光点对应的栅格的四邻域，包括以该激光点对应的栅格、以及以该激光点对应的栅格为中心的上下左右的相邻栅格，相对于八邻域的栅格区域或圆域，搜索的栅格数量更少，进而减少坐标的计算量。

在一些实施例中，每个激光点对应的栅格在所述预配置地图内使用像素点表示，每个像素点使用特定尺寸的栅格表示，使得一个激光点对应一个栅格；优选地，所述预配置地图将像素点配置为栅格，将一个像素点配置为5厘米乘以5厘米的单元格，作为填充所述预配置地图的栅格，一个激光点对应一个栅格，但一个栅格也只对应一个连通域，这个连通域的大小就是相连通的像素点的个数。其中，组成连通域的像素点的数量能反映障碍物的尺寸。

在一些实施例中，所述预配置地图是属于机器人的激光传感器采集的激光点所映射出的特定尺寸的图像，以像素点为单位组成元素，每个像素点都可以视为栅格（特定尺寸的单位格）；其中，在所述预配置地图内，每个障碍物都是由像素值相同且相邻接的像素点组成，使得每个障碍物在所述预配置地图内由相邻接的栅格组合成，具体地，使用现有技术公开的连通域分析对所述预配置地图进行处理，能够将不同位置处的障碍物标记为由不同像素值的像素点组成，且不同位置处的障碍物是由不同颜色的像素点组成，比如，在机器人工作的室内环境中，缺口左右端点两侧的障碍物边界是不连通时，缺口左右端点两侧的障碍物边界分别被标记为不同颜色的像素点；其中，缺口左端点一侧的障碍物边界是由蓝色连通区的像素点组成，并由46个相连通的像素点组成，则蓝色连通区内的任一个像素点的连通像素数量都为46；缺口右端点一侧的障碍物边界是由绿色连通区的像素点组成，并由92个相连通的像素点组成，则绿色连通区内的任一个像素点的连通像素数量都为92。缺口左右端点两侧的障碍物边界是指在一定区域范围内具有连续性的障碍物边界时，比如缺口可以是房间的门洞，门洞两侧的障碍物是同一房间内的四面墙壁，四面墙壁是连续的、一体的，不属于孤立障碍物，则缺口左右端点两侧的障碍物都被标记为相同颜色的像素点，此时获得的连通像素数量比较大。

在一些实施例中，所述预设像素数量阈值是在所述预配置地图中，用于表示连续型障碍物的相邻接的栅格的数量的判断阈值，使得在判断到相应栅格的连通像素数量大于所述预设像素数量阈值，机器人将相应栅格所在位置识别为存在连续型障碍物，或将相应栅格的连通像素数量大于所述预设像素数量阈值者确定为相应栅格存在连续型障碍物的必要技术特征之一。有利于搜索出连通像素数量更大的栅格及其相连通的栅格组成的障碍物。

需要说明的是，一个栅格的连通像素数量是该栅格所处的连通域内所包含的栅格的数量，使得一个激光点对应的栅格与一个连通域相对应；其中，连通域是由像素值相等且位置相邻的像素点组成的图像区域，当本实施例将每个激光点对应的栅格在所述预配置地图内使用像素点表示时，连通域则是由具有相同像素值的相邻栅格组成的栅格集合；则同一个连通域内的每个栅格或每个像素点都有相同的连通像素数量。

至于连通域分析（Connected Component Analysis，Connected ComponentLabeling）是指将所述预配置地图所属的图像中的各个连通区域找出并标记，以实现标记出各个位置占据的障碍物。一般地，在连通域分析的过程中，会先选取一个前景像素点作为种子，然后根据连通区域的两个基本条件（像素值相同、位置相邻）将与种子相邻的前景像素合并到同一个像素集合中，最后得到的该像素集合则为一个连通区域。运用于本实施例的预配置地图中，相关的连通条件为，在种子栅格的邻域栅格区域内与种子栅格有相邻位置且像素值相等的目标栅格，则可进行连通，种子栅格的邻域栅格区域可以为种子栅格的上下左右相邻栅格的范围，即当种子栅格上下左右任一相邻栅格为像素值相等的目标栅格时，将种子栅格与目标栅格进行连通，并赋予新的标记值且计数下相连通的栅格的数量，并将赋予新的标记值的栅格配置为连通栅格，判断连通栅格的邻域栅格区域内是否包含像素值相等的目标栅格，若有，则继续连通，直至最终的连通栅格的邻域栅格区域内无像素值相等的目标栅格时，即最终连通栅格的邻域栅格区域内的栅格均为非目标栅格，连通结束，则可得到当前连通过程中目标栅格包含点云数据对应的一个连通域，此时计数出的相连通的栅格的数量为该连通域的连通像素数量，也是该连通域内任一栅格的连通像素数量。

在前述实施例的基础上，一个激光点对应的栅格的预设范围内的栅格至少匹配一种连通像素数量，包括0，其中，每一种连通像素数量表示一种连通域，进而表示激光点的一种聚类结果；则一个激光点对应的栅格的预设范围内的所有栅格当中，存在连通像素数量最大的一个栅格，使得该栅格的连通像素数量被配置为第一有效激光点的最佳邻域连通像素数量、或第二有效激光点的最佳邻域连通像素数量。

因而，本实施例通过枚举激光帧的每个激光点，判断其在地图上的落点，根据落点是否障碍物，来计算最终的沿边起点；通过枚举激光点，可以有效过滤地图上的杂点，避免机器人在沿边行走的起点位置附近没有需要沿边的障碍物；综上，机器人可以根据激光帧中的激光点在所述预配置地图中对应栅格的连通情况，求得所述最优碰撞点；当找到比较大的障碍物且激光距离最小时，比如距离较近的墙时，可以在所述预配置地图中确定出最优碰撞点对应的栅格或像素点。

作为一种关于预配置地图的实施例，在所述预配置地图内搜索出满足预设连通条件的栅格之前，相应地在执行前述步骤S1之前，机器人先对所述预配置地图进行闭操作，使得所述预配置地图中标记的障碍物的轮廓线得到完整的描述，其中，所述闭操作用于连接连通域，以便于筛选出最新采集的激光点对应的准确栅格位置，属于对所述预配置地图中标记的像素点进行图像形态学意义上的修复，特别是对标记的障碍物的轮廓边界线进行平滑处理。这样后续执行的步骤S1中获取的地图信息、步骤S2和步骤S3中参与判断的栅格信息的准确性得到提高，减少步骤S1获取的激光帧中所携带的噪声信息的影响。

需要说明的是，所述预配置地图是属于机器人构建出的用于描述激光点的位置特征的特定尺寸的图像，以适应实际障碍物分布特征，也是机器人在步骤S1中获取当前激光帧之前，根据在先采集的激光帧构建出的地图。所述预配置地图限定的区域可以是4m*4m的方形区域。

具体地，所述闭操作包括：在将机器人预先构建的地图中的特定尺寸的地图图像区域二值化处理后，获得二值化地图；然后对二值化地图进行图像膨胀处理，再对经过图像膨胀处理后的二值化地图进行图像腐蚀处理，使得部分表示非障碍物的像素点被配置为表示障碍物的像素点，以将未经过图像膨胀处理和图像腐蚀处理的二值化地图中障碍物的轮廓线中的缺口得到填充；其中，二值化地图中，表示障碍物的像素点的像素值和表示非障碍物的像素点的像素值不同，一般地，像素值为255的像素点被配置为组成障碍物，像素值为0的像素点被配置为组成非障碍物。由于二值化后的地图，本来连接在一起的同一个障碍物可能被分为多段，原因可能是机器人预先构建的地图不稳定，或者激光数据不稳定，导致地图不能反映实际；则本实施例通过前述闭操作修复同一障碍物间缺失的部分。

在流程图中表示或在此以其他方式描述的逻辑和/或步骤，例如，可以被认为是用于实现逻辑功能的可执行指令的定序列表，可以具体实现在任何计算机可读介质中，以供指令执行系统、装置或设备(如基于计算机的系统、包括处理器的系统或其他可以从指令执行系统、装置或设备取指令并执行指令的系统)使用，或结合这些指令执行系统、装置或设备而使用。就本说明书而言，“计算机可读介质”可以是任何可以包含、存储、通信、传播或传输程序以供指令执行系统、装置或设备或结合这些指令执行系统、装置或设备而使用的装置。计算机可读介质的更具体的示例(非穷尽性列表)包括以下：具有一个或多个布线的电连接部(电子装置)，便携式计算机盘盒(磁装置)，随机存取存储器(RAM)，只读存储器(ROM)，可擦除可编辑只读存储器(EPROM或闪速存储器)，光纤装置，以及便携式光盘只读存储器(CDROM)。另外，计算机可读介质甚至可以是可在其上打印所述程序的纸或其他合适的介质，因为可以例如通过对纸或其他介质进行光学扫描，接着进行编辑、解译或必要时以其他合适方式进行处理来以电子方式获得所述程序，然后将其存储在计算机存储器中。

在上述实施例中，以可执行扫地任务的机器人(简称为扫地机器人)为例对本申请技术方案进行了示例性说明，但并不限于扫地机器人。本申请各实施例中的机器人泛指任何能够在其所在环境中高度自主地进行空间移动的机械设备，例如，可以是扫地机器人、陪护机器人或引导机器人等，也可以是净化器、无人驾驶车辆等。当然，对于不同机器人形态，其所执行的工作任务也会有所不同，对此不做限定。

本发明另一实施例还公开一种芯片，内置控制程序，所述控制程序用于控制移动机器人执行前述实施例所述的最优碰撞点搜索方法。所述芯片在所述预配置地图内标记出一个最优碰撞点对应的栅格，克服现有技术中存在的激光数据（包括激光点的坐标、探测角度及激光距离）不稳定或噪声造成结果不稳定的问题，过滤预配置地图对应的图像区域中的噪声信息，减少选择孤立障碍物的轮廓处的位置作为障碍物碰撞点的概率，也减少选择实际物理环境中不存在障碍物的位置作为障碍物碰撞点的概率，增强所述最优碰撞点的坐标的环境适应性。

要理解本文所述的最优碰撞点搜索方法对应的实施例可以由硬件、软件、固件、中间件、微代码或其任意组合来实现。对于硬件实现方式，处理单元可以在一个或多个专用集成电路(ASIC) 、数字信号处理器(DSP) 、数字信号处理器件(DSPD) 、可编程逻辑器件(PLD) 、现场可编程门阵列(FPGA) 、处理器、控制器、微控制器、微处理器、被设计以执行本文所述功能的其他电子单元、或其组合内实现。当以软件、固件、中间件或微代码、程序代码或代码段来实现实施例时，可以将它们存储在诸如存储组件的机器可读介质中。

本发明另一实施例还公开一种机器人，该机器人装配有支持360度探测的激光传感器，该机器人内置上述实施例所述的芯片，用于控制机器人在距离机体最近的连续型障碍物中获取最优碰撞点，再控制机器人导航至该最优碰撞点，以开始沿该最优碰撞点所属的墙体障碍物作沿边行走。一般地，根据沿边导航的实现需求，机器人装配的激光雷达可以为多个，设置在不同位置，以达到获得机身周边障碍物点云数据的目的。其中，激光传感器支持实时扫描构建激光地图，并存储到机器人内置所述的芯片中。

上述实施例只为说明本发明的技术构思及特点，其目的是让熟悉该技术领域的技术人员能够了解本发明的内容并据以实施，并不能以此来限制本发明的保护范围。凡根据本发明精神实质所作出的等同变换或修饰，都应涵盖在本发明的保护范围之内。

Claims (20)

1.基于激光点的最优碰撞点搜索方法，其特征在于，该最优碰撞点搜索方法包括：

在预配置地图内搜索出满足预设连通条件的栅格，再将该满足预设连通条件的栅格的坐标标记为最优碰撞点在预配置地图内的坐标，并确定满足预设连通条件的栅格对应的激光点所反映的物理位置是最优碰撞点。

2.根据权利要求1所述最优碰撞点搜索方法，其特征在于，在预配置地图内搜索满足预设连通条件的栅格，再将该满足预设连通条件的栅格的坐标标记为最优碰撞点的坐标的方法包括：

当在预配置地图内搜索出满足第一预设连通条件的栅格时，将该满足第一预设连通条件的栅格的坐标标记为最优碰撞点在预配置地图内的坐标；

在预配置地图内搜索不出满足第一预设连通条件的栅格后，则在预配置地图内搜索出满足第二预设连通条件的栅格，再将该满足第二预设连通条件的栅格的坐标标记为最优碰撞点在预配置地图内的坐标；

其中，所述预设连通条件包括第一预设连通条件或第二预设连通条件。

3.根据权利要求2所述最优碰撞点搜索方法，其特征在于，当搜索不出满足第一预设连通条件的栅格，且搜索不出满足第二预设连通条件的栅格时，在激光帧内搜索出激光距离最小的激光点，再将该激光点对应的栅格的坐标标记为最优碰撞点在预配置地图内的坐标；

其中，机器人所搜索到的激光点都是来源于机器人采集到的激光帧；一个激光点对应一个激光距离。

4.根据权利要求2所述最优碰撞点搜索方法，其特征在于，激光点是用于表征机器人的激光传感器发射的激光在障碍物上的反射位置，激光点是来源于机器人采集到的激光帧；

其中，激光点是位于激光传感器的有效探测角度范围内，并映射到所述预配置地图的对应栅格中；

在有效探测角度范围内，一个激光点对应一个单位探测角度，一个激光点对应一个栅格，一个激光点对应一个激光距离，激光距离用于反映所探测的障碍物与机器人所安装的激光传感器之间的距离。

5.根据权利要求4所述最优碰撞点搜索方法，其特征在于，满足第一预设连通条件的栅格是：在预配置地图内，最佳邻域连通像素数量大于预设像素数量阈值、最佳邻域连通像素数量最大且激光距离最小的第一有效激光点对应的栅格；

其中，一个第一有效激光点对应的栅格的预设范围覆盖到该第一有效激光点对应的栅格；

其中，一个第一有效激光点的最佳邻域连通像素数量是该第一有效激光点对应的栅格的预设范围与预配置地图的重叠区域内，所有栅格的连通像素数量当中的最大值；一个栅格对应一个连通像素数量；

其中，第一有效激光点是激光距离处于预设探测距离范围内的激光点。

6.根据权利要求5所述最优碰撞点搜索方法，其特征在于，所述在预配置地图内搜索出满足第一预设连通条件的栅格的方法包括：

每当搜索完一个第一有效激光点对应的栅格的预设范围内所有栅格，则将最佳邻域连通像素数量大于预设像素数量阈值的第一有效激光点标记为第一一目标激光点；

当搜索完每个第一有效激光点对应的栅格的预设范围内所有栅格时，若判断到只存在一个第一二目标激光点，则将第一二目标激光点对应的栅格标记为满足第一预设连通条件的栅格，并将第一二目标激光点对应的栅格的坐标标记为最优碰撞点在所述预配置地图内的坐标，并确定第一二目标激光点所在的物理位置点是最优碰撞点；

当搜索完每个第一有效激光点对应的栅格的预设范围内所有栅格时，若判断到存在至少两个第一二目标激光点，则将激光距离最小的第一二目标激光点对应的栅格标记为满足第一预设连通条件的栅格，并将激光距离最小的第一二目标激光点对应的栅格的坐标标记为最优碰撞点在所述预配置地图内的坐标，并确定第一二目标激光点所在的物理位置点是最优碰撞点；

其中，第一二目标激光点是在预配置地图内，最佳邻域连通像素数量最大的第一一目标激光点。

7.根据权利要求6所述最优碰撞点搜索方法，其特征在于，在搜索完每个第一有效激光点对应的栅格的预设范围内所有栅格后，若在预配置地图内搜索不出连通像素数量大于预设像素数量阈值的栅格，则确定在预配置地图内搜索不出满足第一预设连通条件的栅格，然后开始在所述预配置地图内搜索所述满足第二预设连通条件的栅格；

其中，连通像素数量用于反映障碍物的尺寸，以使得满足第一预设连通条件的栅格或满足第二预设连通条件的栅格被配置为所述连续型障碍物所占用的栅格。

8.根据权利要求7所述最优碰撞点搜索方法，其特征在于，满足第二预设连通条件的栅格是：在预配置地图内，最佳邻域连通像素数量大于预设像素数量阈值且激光距离最小的第二有效激光点对应的栅格；

其中，一个第二有效激光点对应的栅格的预设范围都覆盖到该第二有效激光点对应的栅格；

其中，一个第二有效激光点的最佳邻域连通像素数量是该第二有效激光点对应的栅格的预设范围与预配置地图的重叠区域内，所有栅格的连通像素数量当中的最大值；

其中，第二有效激光点是激光距离与机身尺寸相关联的激光点；第二有效激光点在预配置地图内的分布范围大于第一有效激光点在预配置地图内的分布范围。

9.根据权利要求8所述最优碰撞点搜索方法，其特征在于，所述在预配置地图内搜索出满足第二预设连通条件的栅格的方法包括：

每当搜索完一个第二有效激光点对应的栅格的预设范围内所有栅格，则在检测到最佳邻域连通像素数量大于预设像素数量阈值的第二有效激光点时，将该第二有效激光点标记为第二一目标激光点；

当搜索完每个第二有效激光点对应的栅格的预设范围内所有栅格时，将激光距离最小的第二一目标激光点对应的栅格标记为满足第二预设连通条件的栅格，并将第二一目标激光点对应的栅格的坐标标记为最优碰撞点在预配置地图内的坐标，并确定第二一目标激光点所在的物理位置是最优碰撞点。

10.根据权利要求9所述最优碰撞点搜索方法，其特征在于，当搜索完每个第二有效激光点对应的栅格的预设范围内所有栅格后，若在预配置地图内搜索不出连通像素的数量大于预设像素数量阈值的栅格，则确定在预配置地图内搜索不出满足第二预设连通条件的栅格，然后在所述激光帧内搜索激光距离最小的激光点，再将激光点对应的栅格的坐标标记为最优碰撞点在预配置地图内的坐标，并确定该激光点所在的物理位置是最优碰撞点。

11.根据权利要求4所述最优碰撞点搜索方法，其特征在于，激光点对应的栅格的坐标的来源包括：以激光点的激光距离的三角函数换算结果为坐标偏移量，对该激光点进行坐标偏移，再按照预设比率将经过坐标偏移的激光点的坐标换算为栅格坐标，实现将该激光点转换到所述预配置地图的坐标系内。

12.根据权利要求11所述最优碰撞点搜索方法，其特征在于，激光传感器的有效探测角度范围是0度至360度，激光帧中存在360个激光点，分别对应360个不同的激光距离；

其中，激光点的激光距离跟随该激光点所处的单位探测角度的变化而变化，该激光点所处的单位探测角度是处于激光传感器的有效探测角度范围内。

13.根据权利要求5或8所述最优碰撞点搜索方法，其特征在于，激光点对应的栅格的预设范围是该激光点对应的栅格的邻域栅格范围，包括该激光点对应的栅格。

14.根据权利要求13所述最优碰撞点搜索方法，其特征在于，所述激光点对应的栅格的预设范围是该激光点对应的栅格的四邻域，包括以该激光点对应的栅格、以及以该激光点对应的栅格为中心的上下左右的相邻栅格，以减少坐标的计算量。

15.根据权利要求11所述最优碰撞点搜索方法，其特征在于，每个激光点对应的栅格在所述预配置地图内使用像素点表示，每个像素点使用栅格表示；所述预配置地图是属于机器人的激光传感器采集的激光点所映射出的特定尺寸的图像；

其中，在所述预配置地图内，每个障碍物都是由像素值相同且相邻接的像素点组成，使得每个障碍物在所述预配置地图内由相邻接的栅格组合成。

16.根据权利要求15所述最优碰撞点搜索方法，其特征在于，一个栅格的连通像素数量是该栅格所处的连通域内所包含的栅格的数量，使得一个激光点对应的栅格与一个连通域相对应；

其中，连通域是由像素值相同且位置相邻的像素点组成的图像区域、或由具有相同像素值的相邻栅格组成的栅格集合，同一个连通域内的每个栅格或每个像素点都有相同的连通像素数量。

17.根据权利要求16所述最优碰撞点搜索方法，其特征在于，在所述预配置地图内搜索出满足预设连通条件的栅格之前，先对所述预配置地图进行闭操作，使得所述预配置地图中标记的障碍物的轮廓线得到完整的描述，其中，所述闭操作用于连接所述预配置地图中的连通域；

其中，所述预配置地图是属于机器人构建出的用于描述激光点的位置特征的特定尺寸的图像。

18.根据权利要求17所述最优碰撞点搜索方法，其特征在于，所述闭操作包括：

在将所述预配置地图二值化处理后，获得二值化地图；然后对二值化地图进行图像膨胀处理，再对经过图像膨胀处理后的二值化地图进行图像腐蚀处理，使得部分表示非障碍物的像素点被配置为表示障碍物的像素点；

其中，二值化地图中，表示障碍物的像素点的像素值和表示非障碍物的像素点的像素值不同。

19.一种芯片，内置控制程序，所述控制程序用于控制机器人执行权利要求1至18任一项所述的最优碰撞点搜索方法。

20.一种机器人，该机器人装配有支持360度探测的激光传感器，其特征在于，该机器人内置权利要求19所述的芯片。