0
| 本文作者：我在思考中 | 2021-08-31 11:25 | 专题：KDD 2019 |
8月18日，国际知识发现与数据挖掘大会（ACM SIGKDD）KDD CUP 2021 City Brain Challenge在新加坡落下帷幕。
来自上海交通大学电子工程系的“IntelligentLight”团队从众多技术实力强劲的公司和研究机构中脱颖而出，斩获冠军。该团队由上海交通大学电子工程系宫新保老师作为指导教师。
KDD CUP大赛为何方神圣？
KDD Cup 作为全球数据挖掘领域最有影响力的赛事，自1997年以来由 ACM 协会的SIGKDD每年举办一次，被誉为数据科学领域的“世界杯”。
该赛事每年都吸引着众多世界顶级的企业、高校与研究机构的参与，为数据挖掘领域研究者提供了一个学术交流和研究成果展示的理想平台。KDD Cup多年来一直保持着很高的产业界参与度以及对解决实际问题的敏感度。
城市大脑挑战赛
今年数据挖掘顶会KDD在数据竞赛单元KDD Cup特别设置了City Brain Challenge，旨在挑战城市容纳车辆极限，助力城市交通决策规划。主办方为参赛者提供了一个城市规模的真实道路网络，且其交通需求来自真实的交通数据。参赛者将负责协调交通信号，以最大程度地服务车辆，同时保持可接受的延迟。
本次竞赛一共吸引了来自全球的 1156 支参赛队伍，其中不乏 4Paradigm、German Aerospace Center、NTT、BOE、Alibaba Group、Didi Chuxing以及Purdue University、NYU、IIT等国际顶尖研究机构的身影。
来自上海交通大学高速信号处理实验室的 IntelligentLight 团队，从上千支参赛队伍中脱颖而出，在预赛和决赛阶段都取得了第一名的好成绩，最终斩获City Brain Challenge赛道冠军。
（官方竞赛结果网页链接：http://www.yunqiacademy.org/poster）
图1 ：来自上海交通大学高速信号处理实验室的IntelligentLight团队在City Brain Challenge赛道摘得桂冠，团队成员包括宋罡（硕士）、张正（硕士生）、王楚凡（硕士生）、顾煜程（本科生）、孙泽钰（本科生），指导教师是宫新保老师。
为什么参加这个比赛？
上海交通大学高速数字信号处理实验室在宫新保老师的带领下，长期从事高速数字信号处理领域的系统设计和软硬件实现工作，成功研发了多种高速数字处理系统，在相关领域积累了丰富的关键技术和工程经验。近年来，实验室依托自身优势，在人工智能、机器学习、数据挖掘等领域也取得了突出成绩。
实验室的鲜明特色是以需求为导向，做科学研究的同时解决实际问题，为社会发展贡献力量。而 KDD Cup 2021 城市大脑挑战赛的赛题源自真实的交通场景，真实的交通数据，激发了实验室师生的参赛热情。这是实验室第一次参加KDD CUP 这样的国际顶级赛事，首次比赛即获得冠军，这也充分展现了实验室在数据挖掘领域的技术积累和研究实力。
解决方案
1）问题分析
KDD Cup 2021城市大脑挑战赛提供了一个城市规模的道路网络，其交通需求来自真实的交通数据。每个队伍负责协调个路口的交通信号灯，以最大限度地增加服务车辆的数量，同时保持可接受的延误。
在这个问题中，最重要的评价指标是延迟指标（Delay Index）。延迟指标的定义是，其中，是车辆已经行驶的时间加上车辆在剩余道路上自由通行的时间，是车辆在整条行驶路径上自由行驶的时间。
在本次比赛中，每个红绿灯有8个相位，我们的任务具体而言就是在城市路网中对这8个相位之间选择和切换，使总延误指标，也就是每辆车延误指标的均值最小。
图2 南昌道路路网信息 
图3 城市路网可视化示例
经过大量文献阅读和调研，我们发现现有的交通信号灯控制方法主要分为强化学习算法和传统交通模型分析算法。传统算法中比较具有代表性的是最大压力法（Max Pressure），它的总体思想是定义一个合适的车道压力来反映车道的拥堵情况，并根据这一概念选择压力最大的车道放行。在本次比赛中，我们吸收了最大压力法的许多基本思想。
图4 最大压力法示意图
我们也研究并实验了一些强化学习（Reinforcement Learning）方法（比如DQN、PG、PPO、A3C等）。RL方法的优点是可以建模许多超出逻辑理解能力的抽象特征，用神经网络完成计算和更新。
但在挑战赛中，它也有一些不可避免的缺点：首先，我们很难将延迟指标直接设置为奖励函数，而延迟指标与其他类型的奖励函数之间又存在不确定的数学关系；其次，城市规模的路网对数据和计算资源有很大的需求，很难做到高效的训练和模型迭代。
2）建模过程
我们算法总体框架的核心思想是，以每辆车为中心建模，根据我们收集的信息给每辆车分配一个投票分数。对于信号灯路口的每个时间点，我们分析如图5所示的八种相位的情况，将其Q值定义为该相位下车辆投票得分的总和，继而选择Q值最大的相位作为该路口在当前时间点的最佳相位。
图5 路口八相位示意图
经过数据特性的搜集和数据预处理，我们从比赛方提供的车流仿真器——CBEngine 中搜集并清洗出了3万多条数据，用于后期训练集成学习模型。而分析数据的过程也极大的启发了模型的建立。我们基于数据分析建立了一个简化的交通模式识别机制：当一辆车进入路网时，它的路线将被记录并与现有的车辆道路进行比较和交叉研究；在这一过程中，我们假设在同一路口且朝着同一方向移动的车辆有相似路线的概率很高，并依据该假设对新出现的车辆的未来路径和总行驶时间进行预测。
有了这一识别机制，我们尝试预测车辆一段时间后的距离、速度，这些尝试启发了我们后面建立的时间项；并且用历史信息对车辆路径信息的预测经验证达到了60%的准确率，这一信息对后面提到的压力项的设计作用极大。
接下来就是具体的模型建立，在Max Pressure方法与交通模式识别机制的有效的基础上，为了提高性能，我们又进一步添加了各种特征。最终将每辆车的投票得分定义为三个项目的乘积：
第一项是车辆在时间点 t 时总行驶路径的时间预测项。根据延迟指标的定义，自由行驶时间较小的车辆的延迟指标会对总延误指标造成更大的影响，因此我们提升了这些车辆的票值，并区分为以下两种情况：对于路径信息已知车辆，该项值为一常数除以其自由行驶时间，该常数为实验中得到经验值；对于路径信息未知车辆，该项值为1。实验结果表明，这一项添加进方程确实对模型性能的提高有一定作用。
第二项为时间点 t 时的压力项。对于车道中的某一辆车，它的上游车道压力可以容易得到（即为当前所在车道的压力）；而由于其下游车道未知，下游压力的定义需要借鉴我们构建的交通模式识别机制（有60%的预测准确率），具体也分为两种不同情况：如果道路可以根据历史信息被准确预测出，那么下游压力就是其目的地的压力；如果道路信息无法被预测，那么下游压力取为下游内侧车道和直行车道压力中的最大值。这一项的定义基于车辆不会在上游道路中变换其车道的假设。
第三项为基于道路的时间项。由于靠近路口的车辆更有可能快速到达交叉路口，在下一阶段的投票中，它们应该有更大的票值权重。为了精确衡量车辆到达路口的时间，我们将道路剩余长度、车辆当前速度、道路限速等信息进行了综合考量，以此为基础设计了基于道路的时间项。
在实验过程中我们发现，在车辆通行高峰时间或发生事故时，某些路口的下游车道可能完全阻塞导致压力项失效。针对这一问题，我们设计了一种动态黑名单机制，对车辆模型进行修正：
如果在绿灯放行阶段检测到任一上游车道上的第一辆车没有移动，那么我们就认为该车道存在异常情况。对于每辆车而言，参数取决于车辆当前所在车道是否被列入黑名单。
图6 下游压力黑名单项示意图
在竞赛中，有两种情况会使道路被列入黑名单：当前道路有过高的下游压力或由于未知原因产生异常。对于过高下游压力的车道，我们设置一个放行阈值，当下游压力低于该阈值时放行；对于未知原因的异常车道，我们建立一个指数衰减的测量因子来转移对这些车道的关注，直至其恢复正常。
举一个简单的例子，在图6中，5车道由于下游道路拥堵将会被认为有异常情况，将被列入黑名单暂时封堵直至其下游道路压力释放。因此，在相位选择时会优先考虑上游压力更小的8车道。
算法实现中，我们的智能体首先检测在黑名单中的上游车道能否被移出黑名单，再检测当前路口的车道中是否有部分需要被加入黑名单。在这一过程中我们设置的移除黑名单的条件总是比加入黑名单的条件强。并且黑名单机制具有很强的扩展性，可以添加其它原因以提升模型的适应力。
3）实验结果
图7 和最大压力法相比的实验结果
为了测试我们的模型效果，我们在比赛方提供的车流上进行测试。图7中是与Max Pressure 方法比较的结果，可以看到我们的方法几乎在每一个时间步长上的延迟指标都小于 Max Pressure。表中反映的是以20秒为时间步长，延迟指标为1.4时所用的时间和服务车辆数，证明了我们的算法在更短时间内服务了更多的车辆。
图8 开关不同机制性能比较
图8则反映了我们设计的各种机制的合理性。图中蓝色的折线表示了我们最终提交的模型的性能，可以看到各个机制都对提升模型效果起到了独特的作用。
专访
1）我们是从4月下旬热身赛的后期进入比赛，之后全程参与了资格赛（预赛）和决赛，一直到7月5日比赛结束。总共持续了2个多月的时间。
2）比赛中实际投入的时间要少一些，因为参赛队员都是在校学生，准备期末考试花费了3周左右的时间。剩下的时间投入的精力比较多。
因为是第一次参赛，我们的主要目的还是学习和积累经验，同时检验我们的能力；所以并没有想到会拿冠军。
只是到了决赛的最后阶段，我们的分数逐渐和其他参赛队伍拉开差距以后，才觉得可能会拿到冠军。
3、AI科技评论：比赛中遇到的最大挑战是什么？
1）首先是特征提取和建模。比赛提供的是接近真实道路网络模型的仿真体；参赛方获得的直接信息是仿真体的行为，即车流的行为信息。我们需要根据具体的行为，提取出有价值的特征，并进行问题建模。
2）其次是算法创新。因为问题不是直接照搬现有算法就能解决的，必须针对问题提出创新性的解决方案。
3）总体而言，对问题的理解越深入，特征提取越准确，建模越精细、越贴近实际，提出的算法越能够“对症下药”，那么获得的性能就越好。
4、AI科技评论：比赛方案的核心亮点是什么？为何能夺冠？
1）核心亮点之一是精细建模。我们精心设计了抽象度高的路网特征；这些特征对算法的训练和参数调整有很大的帮助。
2）核心亮点之二是用强化学习对模型中不可导的参数进行了训练。
3）我们这次比赛之所以能够取得好成绩，一方面是我们团队的工程经验比较丰富，对问题分析——建模——求解这套流程非常熟悉，闭环速度快，而且能够根据实际情况快速调整；
另一方面是我们对人工智能和数据挖掘领域都有一定的了解，能够快速的筛选和提取有价值的算法思路。
5、AI科技评论：比赛方案还有优化和进步空间吗？
1）因为比赛的问题接近实际场景，所以我们还是有一些想法可以继续尝试的；只是因为比赛的时间限制，而没有来得及实施。
2）首先我们打算用类似图神经网络的手段实现多个路口之间的信息传递，增加信息传播的维度和广度。（目前在我们的算法中，路口之间的信息传递主要靠路口车辆密度来传递。）
3）其次是可以尝试通过多路口的协调机制，来实现类似交通控制学中的绿波控制和红波控制。
6、AI科技评论：其他队伍的比赛方案有什么亮点或借鉴之处吗？
1）我们在比赛之后的复盘阶段，对其它参赛队伍的比赛方案也进行了仔细研究。前几名队伍的方案大体可以分为以交通学模型为主和以强化学习为主的两种类型，二者各有优势。
2）以交通学模型为主的方法和我们最终的解决方案的总体思路比较接近，即基于对路网和车流信息的数据分析、实现对交通灯的智能调控；不过各个队的特征选取和参数设定有比较大的区别。
3）以强化学习为主的方法针对具体的应用场景，对DQN等强化学习方法进行了大量的优化和改进，最终也达到了很好的效果。这也有点出乎我们的意料。
4）这些参赛队伍采用的方法和思路都有自己的亮点和绝活，都值得我们研究和借鉴。
7、AI科技评论：比赛全程下来有对哪个环节或者设置上有不满意的地方吗？
1）首先要说的是，这种高质量的赛事在赛题设置、比赛环境和赛事组织方面都相当完善和高效，用于模拟现实环境的仿真体的质量也相当高、在两个多月的运行中基本上没有bug，这也让我们很开眼界。
2）如果非要说有什么不满意的地方，就是决赛赛题的设置：模拟时长较短（上限20分钟），车流密度高（测算下来高于实际路网的车流密度）。这虽然提升了比赛难度，但是会倾向于让贪婪算法类型的方案获得更好的效果，这可能和赛题设置的初衷不太一样。
8、AI科技评论：有用到比赛提供的城市大脑开放研究平台吗？感觉如何？
1）确实用到了比赛方提供的云计算平台，而且对我们的帮助很大。
2）云计算平台提供的算力规模庞大，大大提高了算法迭代的速度和调参速度，不是一般的服务器能够相比的。
3) 所以这次比赛让我们学习了计算机集群的使用方法，也领教了其巨大算力。
总结与展望
KDD是数据挖掘领域的最顶级会议，而 KDD Cup 可以说是数据挖掘竞赛里的皇冠，能摘下桂冠，对我们的意义是非同凡响的。经过本次比赛，上海交通大学高速信号处理实验室不仅进一步凝聚了实验室力量，而且证明了实验室的研究能力和技术实力。
这次比赛的赛题非常贴近实际场景，具有很高的挑战性和实际意义。接下来，上海交通大学高速信号处理实验室将更加注重产学研相结合，推进相关技术的成果转化和实际落地应用，为智慧交通的发展贡献力量。
赠书福利
AI科技评论本次联合Springer为大家带来5本周志华教授亲笔签名的《Machine Learning》正版新书。
在AI科技评论8月28日头条文章“周志华《西瓜书》上线英文版！”（注意不是本文，仅限AI科技评论微信公众号端）留言区留言，欢迎大家畅所欲言，谈一谈你对本书的看法和期待。在综合留言质量（留言是敷衍还是走心）和留言点赞最高（注：点赞最高的前5不意味着一定会中奖）的读者中选出5位读者获得赠书。获得赠书的读者请联系 AI 科技评论客服（aitechreview）。
留言内容会有筛选，例如“选我上去”、“这书写的很棒（仅仅几个字）”等内容将不会被筛选，亦不会中奖。
留言送书活动时间为2021年8月28日 - 2021年9月01日（23:00），活动推送时间内仅允许赠书福利中奖一次。
雷锋网雷锋网雷锋网(公众号：雷锋网)
雷锋网特约稿件，未经授权禁止转载。详情见转载须知。
专题
文章点评：