1 公司简介
Realtime Robotics 是一家2016年成立的初创公司，位于美国波士顿。Realtime Robotics的核心技术是通过定制化的硬件对运动规划进行加速，从而让机器人实现实时的运动能力。Realtime Robotics的硬件产品可以被比喻成人类大脑的运动皮层，它能够让机器人灵活的运动。不久前（2021年6月4日），该公司又获得了3140 万美元的融资。该公司是典型的技术人员创业，公司的创始人之一George Konidaris本身也是一个机器人学者。George Konidaris在MIT做过4年博士后，而且是在Lozano-Perez手下干活。Lozano-Perez是研究机器人运动规划的大牛，提出了著名的构形空间概念，深刻影响了机器人的发展。
2 技术背景
2.1 现在的机器人很强大吗？
如今，机器人已经不是什么稀罕的东西，在自动化工厂里经常能看到机械臂和无人搬运车忙碌的工作。无论在力量、速度还是精度上，机器人都已经全面碾压人类。可以说，机器人行业已经发展到了这样一个阶段，即它们完全有能力实现复杂的、精密的、迅速的动作。但是你可能和笔者有同样的一个疑问——为什么机器人还没有替换掉所有的体力劳动？要回答这个问题并不容易，如果勉强给出一个答案，那就是现在的机器人还不够“智能”。
如果在机器人的工作现场仔细观察一段时间你就会发现，这些机器人的动作都是重复的。你看到的机器人更像“机器”而不是“人”，它们只知道死板地执行人类的命令，没有一点灵气。这也是为什么在机器人工作的环境中绝对不能有人员进入，因为它们无法不撞到你。机器人在“肉体”上早已超越了人类，但是在“智能”上却连三岁小孩都不如。机器人学家对这样的现状满意吗？当然不满意，他们早就开始为机器人设计复杂的算法期望让机器人表现的更灵活。但是事实是，我们依然只能看到笨笨的机器人，为什么？要想继续了解这个问题，下面就不得不涉及一些技术背景知识了。
2.2 猪队友——规划
不太严格的划分，机器人领域有三大方向：感知、规划、控制。要让机器人灵活的运动，这三个方向都是要研究的。但是，感知和控制已经可以满足普通的使用场景了，唯独规划这个猪队友拖了后腿。规划到底是干什么的呢？简单来说，规划的任务就是告诉机器人应该怎么动作。如果说的专业一点，规划的目的是为机器人生成安全、高效的运动轨迹。作为人来说，你肯定觉得规划是一个很简单的任务，因为我们每天都在进行大量的运动，不管简单还是复杂，每个运动都在进行规划。但是，实际上恰好相反，规划是件相当有挑战性的任务，尤其是对机器人来说。它刚好就陷入莫拉维克悖论里了：“对于人类很简单的东西，对于机器人来说却很困难”。
规划的问题出在哪里呢？如果我们先考虑一些简单的情况，例如环境中的障碍物都是固定的，现在已经有一些规划方法可以为机器人生成运动了，只是不那么快而已。但是既然环境是不变的，障碍物也就是固定的，那么我们可以提前计算出安全的轨迹然后存储起来即可。这种用空间换时间的方法是没问题的，可是实际情况可没有这么理想，就算没有人员进入机器人的工作范围，其它机器人的运动也可能造成障碍。此时，现有的方法就遇到问题了，它们都太慢了，以至于慢到无法忍受，无法适应时刻变化的环境。Realtime Robotics公司就是为了解决这个痛点的，这也是为什么公司的名字叫Realtime，因为Realtime的意思就是实时，暂时你可以理解成快。
3 技术方案揭秘
Realtime Robotics公司采用了什么方法解决了规划的难题呢？这可以从公司发表的一系列论文中一探究竟，论文的作者中就有创始人。The microarchitecture of a real-time robot motion planning accelerator、Robot Motion Planning on a Chip。
3.1 碰撞检测
对规划问题分解后发现，规划中耗费时间最多的步骤是碰撞检测，而探索算法其实是比较高效的。碰撞检测的目的是判断两个物体也没有发生碰撞。碰撞检测是一个非常重要的步骤，可以说只要机器人与不确定的环境打交道，都离不开碰撞检测，重要的应用有自动驾驶和协作机械臂。但是碰撞检测的计算量极大，有人统计过，在极端的情况下，规划99%的时间都消耗在碰撞检测环节上，碰撞检测成为瓶颈。因此作者提出，通过加速碰撞检测的计算过程，能够提高规划的速度。如何加速碰撞检测呢？这就要分析碰撞检测的计算过程了。通过分析发现，碰撞检测中包含很多独立的计算环节，这就意味着可以并行计算从而加速。当然作者不是第一个这么干的人，已经有人在GPU上实现过了。但是，该文作者采用了另一种思路——用FPGA实现，并通过对比证明FPGA比CPU和GPU都要快。文章本身没有什么太难的地方，思路也比较简单直接。
下面我们安装论文的安排顺序讲解一下作者是如何解决规划的问题的。
首先，作者开始考虑应该使用哪种运动规划方法。显然，图搜索方法存在组合爆炸问题，并不适合。因此作者把目光投向基于概率的方法，概率的方法主要就是PRM和RRT，作者选择的是PRM，当然作者也说RRT方法也是可以使用的。
然后，作者开始思考如何让碰撞检测计算得更快。这里，作者没有一下把最终答案给出来，而是把尝试的失败过程也描述了。通常碰撞检测主要有两类方法：几何边界碰撞检测和栅格空间覆盖枚举。作者首先尝试的是对现有的碰撞检测算法直接进行加速，即用三角形相交的方法检测碰撞，但是后来发现这种方法并不是最好的。
3.2 三角形面片相交检测
机器人的几何外形一般比较复杂，人们用很多小的三角形面片来近似的表示，这是从计算机图形学中借鉴的思想，如下图所示。您可能会问，为什么不用其它的形状，比如四边形。这是因为三角形是最简单的多边形，它涉及到的一些计算实现起来也最简单。
我们把环境中的障碍物也用三角形面片进行表示。对于障碍物上的三角形和机器人身上的三角形，如果这两个三角形面片交叉了，就说明发生碰撞了。因此碰撞检测问题就转换成了一个几何问题，专门研究这个方向的学科叫计算几何。具有复杂外形的机器人或者障碍物可能会离散成很多三角形，通过组合遍历，实际要检测的三角形对可能有上万甚至几百万个。
当然，三角形交叉还是不能直接判断，要继续分解，把每个三角形用三条线段表示。计算每条线段与另一个三角形所在的平面的交点，根据交点的坐标范围就能判断交点是否落在三角形内部。任何一条线段与对应三角形相交于内部就可以判定两个三角形相交，即发生碰撞。对于每对三角形（分别记为A和B），A要判断三次，反过来，B也要判断三次，所以一共是6次。作者根据这个逻辑设计了实现的加速器的框图，如下图所示。
但是在FPGA中实现时作者遇到了困难。每个三角形对相交判断需要做114次乘法，48次加法和21次减法。如果在FPGA中实现，最多只能支持几十个这样的三角形对检测，这显然无法满足实际要求的至少上万次，因此这种方法不可行。由于笔者不是FPGA专家，所以不深入探讨实现的原理。
3.3 占据栅格检测
既然三角形检测不太适合FPGA加速，那就换一种方法。要想知道环境中都有哪些障碍物，就需要借助可感知物体的传感器。常用的感知传感器就是激光雷达或者深度相机。这两种传感器输出的是覆盖物体表面的点云数据，从点云中可以得到的重要信息是某个点处是有障碍物还是没有。如果我们使用三角形面片连接这些点云，那我们就又回到了上面的老路。为了更简单的描述障碍物的位置和形状，一种做法是把环境按照一定的分辨率划分为网格，当网格中一个单元内存在激光点则说明这个单元包含障碍物的一部分，那么就将该单元的状态标记为被占据，反之则是未被占据，这样得到的结构就叫占据网格。当然，机器人真实的工作空间是三维的，所以前面的网格应该叫三维栅格，或者叫体素（像素的三维版）。可以想到，占据栅格是一种对物体形状的近似表示方法，单元分辨率越高则表示的精度越高，与之相比三角形方法则是一种精确的表示（即便它其实也是一种近似表示，但显然比栅格要准确）。举个例子，例如安装Intel深度相机的机器人看到的世界是这样的，见下图。
机器人的躯干占据了空间中一定的区域，将其离散化之后就是一些体素。环境障碍物也占据了空间中一定的区域，将其离散化之后也是一些体素。我们只需要判断机器人占据的体素是否与障碍物占据的体素存在交集就能知道是否存在碰撞。所有体素的信息被送到FPGA，逐个体素进行布尔值逻辑判断是非常容易在FPGA中实现的。当然机器人在运动的过程中，其躯干占据空间中的区域也一直在变化，因此它占据的体素是不断变化的，如果障碍物也在运动，则同理它占据的体素是不断变化的。
凭借着FPGA的并行加速能力，作者声称他们的碰撞检测效率提高了三个数量级，即1000倍。每次运动规划所需的时间在毫秒级，也就是说每秒可以进行100~1000次规划，如此高的规划频率能够适应绝大多数的动态环境。作者后面也对感知能力进行了提升，能够在8个深度相机的输出数据上实现90Hz的刷新率，这相当惊人了。
Realtime Robotics公司还制作了一个完整的机器人控制器以及运动解决方案。控制器可以和厂家的机器人控制PLC通信，从而控制机器人，其实就是个PCI总线插着FPGA板卡的工控机。Realtime Robotics公司已经与很多机器人制造商建立和合作，能够提供控制器接口。
公司创始人George Konidaris还说，他们认为自己的工作非常有意义，因为绝大多数的创业公司都是为已有的技术寻找一个应用领域，而他们做的是实打实的硬核科技，设计一个app或者搭建一个网站对科技边界的推动实在是太小了。哈哈，也不知道他在讽刺哪些创业公司。
因为运动规划与环境障碍物是紧密相关的，这就离不开感知。所以公司也开发了感知相机标定软件RapidSense。
