rss|MIT博士生杨珩：从L1到L5，自动驾驶的“拦路虎”可能是一个数学问题( 四 ) 系统|扬声器|彭博社|汽车|苹果

而且，在将非凸问题（下图左）转为凸问题（下图右）的过程中，算法不仅在凸问题上求解，还会将凸问题的解投射到原来的非凸问题中，来回求解。在这个过程中，非凸问题的解会加速凸问题的求解，非凸问题的局部最优也可以映射到凸问题的顶点（vertexes），加速求解。目前，他们的工作是第一次在SDP求解中用到了这种「不舍原问题」的求解思想，极具创新。

文章插图

而对于第二个难点，杨珩他们所面临的难点是：目前市面上现有的求解器最多只能求解规模为小到中等的 SDP 问题。所以，他们只能自己研发求解器。

3. 研发求解器 STRIDE
找到全局最优解，与证明全局最优解，是两码事。比如，在ICRA 2020的机器视觉最佳论文奖中，杨珩所提出的算法便能快速找到全局最优解，但是无法证明该解是全局最优，即找不到一个明确的“证书”（certificate）来佐证。
杨珩解释，从本质上看，Robotics（关于机器的学科）的核心是优化，车辆的3D姿态估计便是在解一个优化问题。不仅是感知，自动驾驶中的车辆控制、规划等，都是在解决优化问题。
针对不同的优化问题，研究人员会使用不同的优化框架，并根据某个特定的框架寻找是否有合适的求解器。研究分为两步进行：建模（modeling）与求解（solving）。
所谓「建模」，就是将一个真实世界的问题（如上述所说的自动驾驶汽车感知周围事物）转化为一个数学问题。建模完成后，解决这个数学优化问题的过程就叫做「求解」。一般情况下，目前在机器人（Robotics）领域，大多数工作都是只做建模，仅依靠现存的求解器来解决数学上的优化问题。杨珩的博士导师 Luca Carlone 此前便主要做建模。
但在研究可认证算法的过程中，他们发现，如果只做建模是无法解决100万参数量的问题。市面上也没有成熟的SDP求解器可以帮助他们解决这个问题，所以他们只能自己去开发求解器。
从2019年开始，他们就在寻找适合的求解器。一开始，他们的问题也没有包含那么多的变量，现有求解器已能满足这个凸问题的计算要求。直到去年9月，他们的研究要面临越来越多的参数量，才发现「还是得自己开发求解器，因为现有的求解器解决不了我们的问题。」
从去年9月到今年4月，他们一直在尝试不同的求解器，发现结果均不尽如人意。于是，他们就去找了新加坡国立大学数学系的系主任 Kim-Chuan Toh 和他的学生 Ling Liang，与他们一起合作，针对待解凸问题的特质，用大约 4 个月的时间开发出了一个主要面向 SDP 问题的约束求解器——STRIDE。（STRIDE的源码目前已在Github上公开：https://github.com/MIT-SPARK/STRIDE）
开发求解器的难点，主要是利用好待解决问题的优势。半正定规划（SDP）是一个很大的数学问题，而杨珩要解决的SDP问题除了通用特征，还有一些特殊的性质。比如，它的最优解是低阶（low rank）。
而有了 STRIDE 的助力后，杨珩所提出的可认证感知算法在求解速度与准确度上均有了明显的提升。
如下图所示，原来的非凸问题 TLS 只有 54 个变量时，它所对应的凸问题 SDP 至少有 8154 个变量；TLS 只有 1004 个变量时，SDP 问题的变量超过了 300 万。MOSEK 与 SDPT3 被视为目前最出色的 SDP 求解器，但随着问题的变量越来越多，MOSEK 与 SDPT3 不仅无法求解，甚至连存储该问题的内存都没有。

文章插图

在上图中，1e-10、1e-12等数值为精确度。数值越低，求解的精确度越高。从第 1 行到第 5 行，优化的问题越来越大，测度（measurement）越来越多。回到一开始的例子，就是自动驾驶车辆周围的汽车越来越多，汽车的关键点与连线也会越来越多。