自动驾驶技术应用于扫地机器人,激光雷达+SLAM理论到实践简介

2018-07-17 04:25:52 PM

近几年扫地机器人搭载LDS(激光导航)系统,有“眼”可看见,有“脑”可规划,清扫效率大大提高,体验度变好很多,不再乱碰乱撞、离家出走、随地罢工。扫地机器人这个小家电近两年出现了购买狂潮,各大电商平台销售数据可观,好评如潮。


1531988984560704.jpg


扫地机器人顶部的激光雷达可360°扫描室内环境,建立家庭环境地图,SLAM算法完成机器人的定位和路径规划,使得扫地机器人在未知环境中得以实时描述环境、认识环境,知道自己在哪里,要往哪里去,如何最快走遍家里每个角落。这类似自动驾驶技术家用化,人工智能对大众总是有莫名的吸引力。


SLAM 是同步定位与地图构建 (Simultaneous Localization And Mapping) 的缩写,最早由 Hugh Durrant-Whyte 和 John J.Leonard 提出。SLAM 更像是一个概念而不是一个算法,它本身包含许多步骤,其中的每一个步骤均可以使用不同的算法实现。主要用于解决移动机器人在未知环境中运行时即时定位与地图构建的问题。

机器人的地图的表示方法有四种:栅格地图、特征地图、直接表征法以及拓扑地图。


栅格地图

机器人对环境地图的描述的方式最常见的为栅格地图 (Grid map) 或者称为 Occupancy Map。栅格地图就是把环境划分成一系列栅格,其中每一栅格给定一个可能值,表示该栅格被占据的概率。


1531813008106051.jpg

这种地图看起来和人们所认知的地图没什么区别,它最早由 NASA 的 Alberto Elfes 在 1989 年提出,在火星探测车上就用到过,其本质是一张位图图片,但其中每个「像素」则表示了实际环境中存在障碍物的概率分布。


一般来说,采用激光雷达、深度摄像头、超声波传感器等可以直接测量距离数据的传感器进行 SLAM 时,可以使用该地图。这种地图也可以通过距离测量传感器、超声波(早期)、激光雷达(现在)绘制出来。


特征点地图

特征点地图,是用有关的几何特征(如点、直线、面)表示环境,常见于vSLAM(视觉SLAM)技术中。


1531813582114464.jpg


相比栅格地图,这种地图看起来就不那么直观了。它一般通过如GPS、UWB以及摄像头配合稀疏方式的vSLAM算法产生,优点是相对数据存储量和运输量比较小,多见于最早的SLAM算法中。

直接表征法

直接表征法中,省去了特征或栅格表示这一中间环节,直接用传感器读取的数据来构造机器人的位姿空间。


1531813774217396.jpg


上图就是直接记录了屋子内天花板画面的图像地图。这种方法就像卫星地图一样,直接将传感器原始数据通过简单处理拼接形成地图,相对来说更加直观。


拓扑地图

拓扑地图,是一种相对更加抽象的地图形式,它把室内环境表示为带结点和相关连接线的拓扑结构图,其中结点表示环境中的重要位置点(拐角、门、电梯、楼梯等),边表示结点间的连接关系,如走廊等。这种方法只记录所在环境拓扑链接关系,这类地图一般是由前几类地图通过相关算法提取得到。

比如扫地机器人要进行房间清扫的时候,就会建立这样的拓扑地图:


1531813916135984.jpg


小结

在机器人技术中,SLAM 的地图构建通常指的是建立与环境几何一致的地图。


一般算法中建立的拓扑地图只反映了环境中的各点连接关系,并不能构建几何一致的地图,因此,这些拓扑算法不能被用于 SLAM。


直接表征法类似卫星地图,它是直接使用传感器(一般是图像传感器)构建得到。这种方法的信息冗余度最大,对于数据存储是很大的挑战,同时,机器人要从中提取出有用的数据也要耗费一番周折,因此在实际应用中很少使用。


特征点地图又是另一个极端,虽然数据量少,但是它往往不能反应所在环境的一些必须的信息,比如环境中障碍物的位置。vSLAM 技术中,多采用这种地图来解决机器人定位问题。想让机器人进行自主避障和路径规划,还需要额外配置距离传感器,如激光雷达、超声波来完成。


栅格地图,或者 Occupancy Map(占据地图)恰好介于其中,一方面它能表示空间环境中的很多特征,机器人可以用它来进行路径规划,另一方面,它又不直接记录传感器的原始数据,相对实现了空间和时间消耗的最优。因此,栅格地图是目前机器人所广泛应用的地图存储方式。



1531814124451016.jpg


自 1988 年被提出以来,SLAM 的理论研究发展十分迅速。在实际应用时,除配备激光雷达外,还需要机器人具有 IMU(惯性测量单元)、里程计来为激光雷达提供辅助数据,这一过程的运算消耗是巨大的,传统上需要 PC 级别的处理器,这也成为限制 SLAM 广泛应用的瓶颈之一。

那么,实现 SLAM 的过程中,都会遇到哪些坑呢?


SLAM 实现过程中的难点

这是一个完整的 SLAM 和导航系统的主要架构图:


1531814273810288.jpg


其中,SLAM 核心过程包括 3 个步骤,第一步称为预处理。某一个时刻激光雷达只能获取它所在位置的环境信息,只能反映机器人所在环境中的一个部分,所以激光雷达扫描获取的原始点云数据需要优化,剔除一些有问题的数据,或者进行滤波,获取清晰图像。

第二步是匹配,也就是说把当前这一个局部环境的点云数据在已经建立地图上寻找到对应的位置,这个步骤非常关键。我们用 ICP 的点云匹配算法来实现匹配,这一步直接影响了 SLAM 构建地图的精度。这个过程和我们玩拼图游戏有点类似,就是在已经拼好的画面中找到相似之处,确定新的一个拼图该放在哪里


1531814445229058.jpg

第三步地图融合,也就是将这一轮来自激光雷达的新数据拼接到原始地图当中,最终完成地图的更新。这个过程很复杂,需要用很多概率算法,并采用滤波的方式进行融合。将上述这个过程逐次执行,就最终产生了我们看到的栅格地图。这里举几个例子,比如叫做 Loop Closure(回环)问题。如果匹配算法不足够优秀,或者环境中存在很不巧的干扰,当机器人绕着环境一圈后,就会发现原本是应该闭合的一个环形走廊(下图左),出来的图却断开了(下图右)。一个好的商用化 SLAM 系统,回环问题是否能很好的解决,就成为评判这个系统实力的指标了。



1531814730658257.jpg1531814854274843.jpg


除了算法层面的回环问题,SLAM 实际应用中还有很多这种坑。

那么,机器人利用 SLAM 技术得到了有效的空间信息后,它是怎样实现路径规划的?SLAM 和路径规划之间关系是怎样的?


路径规划

我们先来看看 SLAM 与路径规划的关系:


1531815020117231.jpg

实际上,SLAM 算法本身只是完成了机器人的定位和地图构建两件事情,与我们说的导航定位并不是完全等价的。这里的导航,其实是 SLAM 算法做不了的。它在业内叫做运动规划 (Motion Planning)。完成 SLAM 后,要进行一个叫做目标点导航的能力。通俗的说,就是规划一条从 A 点到 B 点的路径出来,然后让机器人移动过去。



1531815091978413.jpg



要实现这个过程,运动规划要实现至少两个层次的模块,一个叫做全局规划,这个和我们车载导航仪有一点像,它需要在地图上预先规划一条线路,也要有当前机器人的位置。这是由我们的 SLAM 系统提供出来的。行业内一般会用叫做 A * 的算法来实现这个过程,它是一种启发式的搜索算法,非常优秀。它最多的应用,是在游戏中,比如像星际争霸、魔兽争霸之类的即时战略游戏,都是使用这个算法来计算单位的运动轨迹的。


仅仅规划了路径还是不够的,现实中会有很多突发情况,比如正巧有个小孩子挡道了,就需要调整原先的路径。当然,有时候这种调整并不需要重新计算一遍全局路径,机器人可能稍微绕一个弯就可以。此时,我们就需要另一个层次的规划模块,叫做局部规划。它可能并不知道机器人最终要去哪,但是对于机器人怎么绕开眼前的障碍物特别在行。


这两个层次的规划模块协同工作,机器人就可以很好的实现从 A 点到 B 点的行动了,不过实际工作环境下,上述配置还不够。比如 A*算法规划的路径是根据已知地图,预先规划好的,一旦机器人前往目的地的过程中遇到了新的障碍物,就只好完全停下来,等待障碍物离开或者重新规划路径了。如果扫地机器人买回家,必须先把屋子都走一遍以后才肯扫地,那用户体验就会很差。这需要动态启发式路径搜索算法来改进,让机器人在陌生环境中行动自如,在瞬息万变的环境中游刃有余。


一般来说,扫地机需要这么几个规划能力:贴边打扫、折返的工字形清扫以及没电时候自主充电。所以还需要有额外的规划算法,比如针对折返的工字形清扫,有很多问题要处理。扫地机如何最有效进行清扫而不重复清扫?如何让扫地机和人一样,理解房间、门、走廊这种概念?



针对这些问题,学术界长久以来有一个专门的研究课题,叫做空间覆盖(space coverage),同时也提出了非常多的算法和理论。其中,比较有名的是 Morse Decompositions,扫地机通过它实现对空间进行划分,随后进行清扫。


1531815199557993.jpg

20 世纪 70 年代,卡内基梅陇大学(CMU)完全依靠超声波做到了现在我们扫地机的行为,当然造价也十分昂贵。前面介绍的从 A 点到 B 点移动路径规划也是实现这类更高级路径规划的基础。实际上,要从 SLAM 实现到扫地机器人所需要的这些功能,还是有非常多的工作要做的。


1531815284201087.jpg


目前,常见的测距单元包括激光测距、超声波测距以及图像测距三种。其中,凭借激光良好的指向性和高度聚焦性,激光雷达已经成为移动机器人的核心传感器,同时它也是目前最可靠、最稳定的定位技术。


中科天芯科技(北京)有限公司联合中科院研究所成立实验室,在开发高端OPA技术路线固态激光雷达的途中,开发了这款单线360°扫描式激光雷达,5Hz人体仿真学旋转式扫描,4000点/秒频率让平面点云细致光滑,采用CLASS 1人眼安全激光光源,提前设计紧凑结构,简单皮实,元器件选择合理,渠道成熟,易实现量产。经过接近半年的送样评估,中科天芯M1C0激光雷达已获得国内多个大品牌扫地机器人LDS研发组的认可,首条生产线按100万台+/年设计上线,满足爆款LDS扫地机器人厂家供货需求。