摘要：智能汽车的网联化协同驾驶将进一步提升道路交通的通行效率。随着受控车群规模的增长，所求解的问题规模增加迅速，这对云控或边缘平台的计算效率提出了很高的要求。智能驾驶课题组（iDLab）提出了一种适用于大规模网联车群集中式控制的并行求解算法，将问题计算复杂度将多项式级降低为线性级。通过引入一致性约束解耦原问题，进一步结合ADMM（交替方向乘子法）框架分解为一系列可并行计算的子问题，每一个子问题可分配一个计算单元，利用单元之间的信息交互达到最优解的一致性收敛，实现了大规模网联多车协同问题的并行加速求解。

1.介绍

通过ADMM（交替方向乘子法）框架对大规模智能网联汽车协同控制问题进行求解。通过对车车间的约束进行解耦，将问题分解为可以同时求解而不是顺序计算的子问题。之后利用计算节点组成的集群网络对问题进行并行求解，以期望达到计算复杂度与规模无关的目的，从而极大提高求解效率，拓展问题的求解规模。由于车辆之间的空间位置关系复杂多变，车车交互耦合难以处理；因此如何应用合理的解耦方案，实现车车耦合约束的分解，从而实现并行计算是本工作的研究重点。课题组研究工作的主要贡献：a.设计了用于分布式计算方法部署的计算节点网络结构。b.提出了用于求解大规模协同控制问题的并行计算方法。

2. 交替方向乘子法

科学研究与工程实践中，诸多问题都可以构建为凸优化问题。当规模较大时，计算效率往往成为问题求解的瓶颈。将问题进行解耦，使其可以分布式并行计算，是解决大规模问题求解效率低的可行方案之一。交替方向乘子法（alternating direction method of multipliers, ADMM），适用于大规模凸优化问题的分布式并行求解。ADMM提出于上个世纪70年代，经过多年的研究，理论逐渐完善，由于它在机器学习、网络优化等领域应用，受到研究界的关注。ADMM适用于求解如下2-block的优化问题：

该问题可以通过对偶上升进行迭代：

该过程相当于迭代求解的过程。

ADMM在对偶上升法的基础之上，将与单独交替迭代，即：

这使得与为可分解函数（类似于这种形式）时，问题的求解过程可以实现解耦，从而为分布式并行计算提供了条件。

3.网联多车协同控制问题的构建 

首先，构建集中式协同的最优控制问题。思路是采用分层式处理方案，首先每个车辆从导航模块获取各自的行驶路线；之后以此为参考轨迹行驶，由于参考轨迹未考虑约束关系，时空上存在重叠，导致车车间有碰撞风险，因此需要在行驶过程中进行动态避撞。

工作用图论来描述整个车群系统，构建车车交互拓扑图。车车交互拓扑图为一无向图，即节点间不存在次序关系。图中每一节点和每一辆车相对应，图中的边对应两辆车间存在的潜在冲突关系。同时，可以定义与每一个节点有邻接关系的节点集合为该节点邻域。通过邻域节点的定义，构建如下的车车避撞约束：

该约束为一个非凸约束，而非凸约束在优化问题中比较难以处理，工作结合车辆的空间位置变化特点和有限时域优化问题的特性，利用泰勒展开线性化的方式，将非凸约束转化为凸约束近似处理。

据此，构建如下的集中式最优控制问题

在优化问题中以车辆待优化的性能指标为目标函数，同时考虑自车动力学约束，以及车车交互拓扑图描述的协同避撞约束。

4.并行求解算法设计

 对该最优控制问题中的耦合关系进行分析。利用指示函数，可以将约束写入目标函数中，得到一个更为简洁的问题形式。

对优化问题新的形式进行分析，问题分为两个加和部分，分别为自车性能部分和交互约束部分。两部分的变量存在重叠而互相关联，造成整个问题耦合在一起，如何对这一约束进行解耦，是实现并行计算的关键。我们期望对问题的原形式进行变形，令其可以通过ADMM框架进行分解，以期实现问题解耦及并行计算。首先观察原问题，自车性能部分与交互约束部分变量相同，互相重叠，造成两部分耦合。工作通过引入一致性约束的方法对原问题进行处理，从而实现解耦。方法流程如下：对交互约束部分的求解变量生成一个与之前不同的副本。为了使得问题的与原来等价，通过引入约束，使这两部分的变量相等于同一个值，从而做到问题的不变，因为该约束形式是使不同变量相等于同一个值，因此称之为一致性约束，而这种优化形式称为一致性优化问题。下图展现了这一变换过程。