人工智能科技评论报告
编辑|陈大新8月18日,国际知识发现和数据挖掘大会“KDD杯2021城市大脑挑战赛”在新加坡落下帷幕。来自上海交通大学电子工程系的“IntelligentLight”团队从众多技术实力雄厚的公司和研究机构中脱颖而出,获得冠军。该团队由上海交通大学电子工程系的龚新宝老师指导。
一个
KDD杯比赛的神圣性是什么?作为全球数据挖掘领域最具影响力的赛事,KDD杯自1997年起每年由ACM协会SIGKDD举办,被誉为数据科学领域的“世界杯”。
大赛每年都吸引了众多世界级企业、高校和研究机构的参与,为数据挖掘领域的研究人员提供了一个交流学术信息、展示研究成果的理想平台。KDCUP多年来一直保持着高度的行业参与度和解决实际问题的敏感性。
2
城市大脑挑战赛今年,数据挖掘峰会KDD特别设立了KDD杯城市大脑挑战赛这一数据竞赛单元,旨在挑战城市对车辆的容纳极限,助力城市交通决策。它为参与者提供了一个城市规模的真实路网,其交通需求来源于真实的交通数据。参与者将负责协调交通信号,以最大程度地为车辆提供服务,同时保持可接受的延迟。
本次大赛共吸引了来自世界各地的1156支队伍,包括4Paradigm、德国航空航天中心、NTT、BOE、阿里巴巴集团、滴滴出行、普渡大学、NYU、IIT等国际顶级研究机构。
来自上海交通大学高速信号处理实验室的IntelligentLight团队从数千支参赛队伍中脱颖而出,取得了初赛和决赛阶段的第一名,最终获得了城市大脑挑战赛赛道的称号。
图1:来自上海交通大学高速信号处理实验室的IntelligentLight团队在城市大脑挑战赛中获得冠军。队员有宋刚、张峥、王楚凡、顾玉成、孙泽宇,指导老师是龚新宝。
三
你为什么参加这个比赛?上海交通大学高速数字信号处理实验室在龚新宝的带领下,长期从事高速数字信号处理的系统设计和软硬件实现,成功开发了多种高速数字处理系统,积累了丰富的相关领域关键技术和工程经验。近年来,实验室依托自身优势,在人工智能、机器学习、数据挖掘等领域取得了突出成就。
实验室的显著特点是以需求为导向,在做科研的同时解决实际问题,为社会发展做贡献。KDD杯2021城市大脑挑战赛的问题源于真实的交通场景和真实的交通数据,激发了实验室师生的热情。这是实验室首次参加KDD杯这样的国际顶级赛事,并在首届比赛中获得冠军,充分展示了实验室在数据挖掘领域的技术积累和研究实力。
四
解决办法1)问题分析
KDCUP 2021城市大脑挑战赛提供了城市规模的路网,其交通需求来自真实的交通数据。每个小组负责协调20个十字路口的交通灯,在保持可接受的延误的同时,最大限度地增加服务车辆的数量。
在这个问题中,最重要的评价指标是延迟指标。延误指数的定义是,其中,车辆已经行驶的时间加上车辆在剩余道路上自由行驶的时间,以及车辆在整个行驶路径上自由行驶的时间。
在这场比赛中,每个红绿灯有八个相位。我们的任务是在城市路网中的这八个相位之间进行选择和切换,使总延误指标,即每辆车延误指标的平均值最小。
图2南昌路网信息图3城市路网可视化实例
经过大量的文献阅读和调查,我们发现现有的交通信号控制方法主要分为强化学习算法和传统的交通模型分析算法。传统算法中最具代表性的是最大压力法,其总体思想是定义一个合适的车道压力来反映车道的拥挤程度,并根据这一概念选择压力最高的车道进行释放。在这次比赛中,我们吸收了很多最大压力法的基本思想。
图4最大压力法示意图
我们也研究和实验了一些强化学习的方法。RL方法的优势在于可以对很多超出逻辑理解能力的抽象特征进行建模,利用神经网络完成计算和更新。
但是,在挑战中,它也有一些不可避免的缺点:首先,我们很难直接将延迟指标设置为奖励函数,延迟指标与其他类型的奖励函数之间存在不确定的数学关系;其次,城市规模的路网对数据和计算资源的需求很大,难以实现高效的训练和模型迭代。
2)建模过程
我们算法总体框架的核心思想是以每辆车为中心建模,根据我们收集的信息给每辆车分配一个投票分数。对于信号灯路口的每个时间点,我们分析如图5所示的八个相位的情况,将它们的Q值定义为该相位的车辆投票得分之和,然后选择Q值最大的相位作为当前时间点路口的最佳相位。
图5交叉口八相示意图
经过数据特征的收集和数据预处理,我们从竞赛方提供的交通模拟器——CBEngine中收集和清洗了3万多条数据,用于集成学习模型的后期训练。分析数据的过程也极大地启发了模型的建立。基于数据分析,我们建立了一个简化的交通模式识别机制:当车辆进入路网时,其路线会被记录下来,并与现有的车辆道路进行比较和交叉研究;在这个过程中,我们假设在同一个路口同方向行驶的车辆有很大概率有相似的路线,并根据这个假设预测新车未来的路径和总行驶时间。
通过这种识别机制,我们试图预测一段时间后车辆的距离和速度。这些尝试启发了我们后来建立的时间术语。而且利用历史信息对车辆路径信息的预测达到了60%的准确率,对后面提到的压力项的设计起到了很大的作用。
下一步是具体模型的建立。在最大压力方法和流量模式识别机制的基础上,我们进一步增加了各种功能来提高性能。每辆车的最终投票分数定义为三项的乘积:
第一项是车辆在时间点T的总行驶路径的时间预测项..根据延误指数的定义,自由行驶时间短的车辆的延误指数会对总延误指数产生较大的影响,所以我们提高了这些车辆的票值,分为以下两种情况:对于路线信息已知的车辆,这个值是一个常数除以其自由行驶时间,这个值是实验得到的经验值;对于路径信息未知的车辆,该值为1。实验结果表明,在方程中加入这一项可以提高模型的性能。
第二项是t时刻的压力项,对于车道内的某一辆车,其上游车道压力可以很容易得到;由于其下游车道未知,下游压力的定义需要借鉴我们构建的交通模式识别机制,分为两种不同情况:如果道路可以根据历史信息准确预测,那么下游压力就是其目的地的压力;如果无法预测道路信息,则下游压力为下游内车道压力和直行车道压力的最大值。该术语的定义基于这样的假设,即车辆不会在上游道路上改变车道。
第三项是基于道路的时间项。由于靠近十字路口的车辆更有可能快速到达十字路口,因此它们在下一阶段的投票中应该具有更大的票值权重。为了准确测量车辆到达路口的时间,综合考虑道路剩余长度、车辆当前速度、道路限速等信息,设计了一个基于道路的时间项。
我们在实验过程中发现,在高峰时段或事故发生时,一些交叉口的下游车道可能会完全堵塞,导致压力项失效。为了解决这个问题,我们设计了一个动态黑名单机制来修改车辆模型:
如果检测到任何上游车道的第一辆车在绿灯放行阶段没有移动,那么我们认为该车道存在异常情况。对于每辆车,参数取决于车辆的当前车道是否在黑名单中。
图6下游压力黑名单项目示意图
在比赛中,有两种情况会使道路上黑名单:当前道路下游压力过大或不明原因异常。对于下游压力过高的车道,我们设置一个放行阈值,当下游压力低于这个阈值时放行;对于原因未知的异常车道,我们建立一个指数衰减测量因子来转移对这些车道的注意力,直到它们恢复正常。
举个简单的例子,在图6中,五条车道会因为下游道路拥堵而被认为异常,会被列入黑名单,暂时封锁,直到下游道路压力释放。因此,优先选择上游压力较低的8车道。
在算法的实现中,我们的代理首先检测黑名单中的上游车道是否可以从黑名单中删除,然后检测当前路口的一些车道是否需要被列入黑名单。在这个过程中,我们设定的去除黑名单的条件总是强于加入黑名单的条件。并且黑名单机制具有很强的扩展性,可以添加其他原因来提高模型的适应性。
3)实验结果
图7与最大压力法比较的实验结果
为了测试我们模型的效果,我们在竞赛方提供的流量上进行了测试。图7显示了与最大压力方法相比的结果。可以看出,我们的方法在几乎每个时间步的延迟指数都小于最大压力的延迟指数。该表反映了当时间步长为20秒,延迟指数为1.4时所用的时间和服务的车辆数,证明了我们的算法可以在更短的时间内服务更多的车辆。
图8不同交换机制的性能比较
图8反映了我们设计的各种机制的合理性。图中蓝色虚线表示我们最终提交的模型的性能。可以看出,每种机制在提高模型效果方面都发挥了独特的作用。
五
进行一次特别的面试1.AI科技评论:整场比赛用了多长时间,你投入了很多精力吗?
1)我们从4月下旬的热身赛后期开始参赛,然后一路参加资格赛和决赛,直到7月5日比赛结束。总共持续了两个多月。2)实际投入比赛的时间较少,因为参赛选手都是在校学生,准备期末考试大概花了3周时间。剩下的时间投入更多的精力。
2.AI科技评论:你是在比赛过程中还是比赛结束后期待夺冠的?
因为是第一次参加比赛,我们的主要目的是学习和积累经验,同时检验自己的能力;所以没想到会拿冠军。只是在决赛的最后阶段,我们的成绩逐渐落后于其他队伍之后,我们才想到我们可能夺冠。
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)如果非要说不满意的地方,那就是最后题目的设定:模拟时间短,流量密度大。这虽然提高了竞赛的难度,但却倾向于让贪婪算法类型的方案获得更好的成绩,这可能与设置竞赛题的初衷有所不同。
8.AI技术评论:你们使用大赛提供的城市大脑开放研究平台吗?你感觉如何?
1)我们确实使用了竞赛方提供的云计算平台,它对我们帮助很大。
2)云计算平台提供的计算能力是巨大的,大大提高了算法迭代和参数调整的速度,这是普通服务器无法比拟的。
3)所以这次比赛让我们学会了如何使用计算机集群,也学到了它巨大的计算能力。
六
总结与展望KDD是数据挖掘领域的顶级大会,KDD杯可以说是数据挖掘大赛中的皇冠。夺冠对我们来说意义非凡。经过这次比赛,上海交通大学高速信号处理实验室不仅进一步凝聚了实验室实力,也证明了自己的研究能力和技术实力。
本次比赛题目非常贴近实际场景,具有较高的挑战性和现实意义。接下来,上海交大高速信号处理实验室将更加注重产学研结合,推动相关技术的转化和实际应用,为智能交通的发展贡献力量。
图书福利
《AI科技评论》这次联合斯普林格,在本周为大家带来志华教授签名的正版新书《机器学习》。
《AI科技评论》8月28日头条文章《周志华的西瓜书英文上线了留言吧,欢迎大家畅所欲言,谈谈你对这本书的看法和期待。在综合留言质量和留言好评最高的读者中,选出5位读者获得礼品册。获得赠书的读者请联系AI科技评论客服。
留言会被筛选,比如“接我”、“这文笔太棒了”,不被筛选就拿不到奖。
消息传递活动时间为2021年8月28日至2021年9月01日。活动推送时间内礼品福利只允许有一个奖品。
雷锋。com雷锋网。com



