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

但话说回来，「可认证算法」所扮演的角色虽然听起来很简单，研究起来却并不容易，因为在这个研究的过程中涉及到了对截断最小二乘法（Truncated Least Squares, TLS）的求解。TLS是一个非凸优化问题，其可行域集合可能存在局部最优点，但求解全局最优的难度相当于NP难题。
因此，尽管早期欧洲有些学校也沿着可认证算法的方向研究，但他们解决问题的切入点只停留在建模阶段，且面向的场景为没有异常值的情况。
基于Bandeira的工作，杨珩与他的博士导师 Luca Carlone 还就「可认证算法」制定了更高的标准。
假设算法为 A，A 的目标是解决优化问题 P，而优化问题取决于输入数据 D。那么，如果该算法是可认证的，则必须同时满足三个条件：
1）A 必须是多项式算法（polynomial algorithm），理论上必须要快；
2）在解决 P 后，A 要么得到一个全局最优解，以及证明该解为全局最优的“证书”（certificate）；要么失败，没有得到全局最优解，只得到所谓的“measurable suboptimality”，即所求得的解与全局最优解之间的距离；
3）对于大部分 D，A 都能将 P 解到全局最优。
第三个条件由杨珩与 Luca Carlone 添加，目的是为了排除近似算法。所谓“近似算法”（approximate algorithm），指的是算法得到的解永远只能是近似最优。在自动驾驶中，近似算法相当于在任何情况下都无法取得全局最优解，一直“报错”，这会对驾驶安全造成极大隐患。
所以，在杨珩与团队的假设中，A 只有在处理大多数不同情形时能得到全局最优解，才能被称为「可认证算法」，满足自动驾驶的安全需求。

2. “非凸”转“凸”
2018年12月，杨珩加入麻省理工学院信息与决策系统实验室（Laboratory for Information & Decision Systems, LIDS），师从MIT莱纳多职业发展副教授 Luca Carlone，开始从事计算机视觉与机器人的结合研究。
一开始，他们只是从一个小的点云配准/重建（point cloud registration）问题出发。所谓“点云配准”，指的是求两个点云之间的旋转平移矩阵，将源点云变换到与目标点云相同的坐标系下。比如，一辆车无人车分别处在 a 点与 b 点，用无人车点雷达分别对着一栋楼扫一下，再把两张扫描的图融合在一起。
他们针对这个问题设置了一个可认证算法，并在2019年1月投了一篇文章到机器人顶会 RSS（Robotics: Science and System），文章被接收。在这篇工作中，他们使用TLS来重新设计点云优化估测问题，使估计对大部分虚假的点到点对应关系不敏感，可以容忍高达 99% 的异常值（outliers）。

文章插图

图注：杨珩被 RSS 2019 接收的工作，论文地址为 https://arxiv.org/pdf/1903.08588.pdf
但是，他们在 RSS 2019 中提出的可认证算法精确度并不够突出，有时无法满足上述所说的第三个条件（对大部分输入数据都能获得最优解）。许多时候，该算法得到的差距至多是 1e-2、1e-3，而不是1e-6或1e-10等接近0的差距。
从 RSS 2019 开始，他们就一直在研究可认证算法。
2019年2月左右，杨珩用两周时间独自琢磨，看了许多数学资料，尝试换一种对原问题（TLS）的求解方法。他从一个数学思维出发，提出了半正定规划（Semidefinite Programming）松弛，将非凸优化问题 TLS 转化为凸优化问题。这个方法十分成功，他们投到了 ICCV 2019，被成功接收。

文章插图

图注：杨珩被 ICCV 2019 接收的工作，论文地址为 https://arxiv.org/pdf/1905.12536.pdf
对杨珩来说，ICCV 2019 的这篇工作有里程碑式的纪念意义：因为那篇文章是第一个能将有异常值（outliers）的机器人感知问题在多项式时间内（polynomial time）解到全局最优（global optimality）的工作。我们设计的半正定规划松弛（SDP relaxation）是extremely tight，那个算法几乎对所有问题都能得到全局最优，而且它解的原问题是一个带有二元变量（+1 和 -1，mixed integer）的非凸问题。这种问题是一个NP-hard问题。