<mark id="oztn4"></mark>
0
| 本文作者： 我在思考中 | 2021-08-31 11:25 | 專題：KDD 2019 |
8月18日，國(guó)際知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘大會(huì)（ACM SIGKDD）KDD CUP 2021 City Brain Challenge在新加坡落下帷幕。
來自上海交通大學(xué)電子工程系的“IntelligentLight”團(tuán)隊(duì)從眾多技術(shù)實(shí)力強(qiáng)勁的公司和研究機(jī)構(gòu)中脫穎而出，斬獲冠軍。該團(tuán)隊(duì)由上海交通大學(xué)電子工程系宮新保老師作為指導(dǎo)教師。
KDD CUP大賽為何方神圣？
KDD Cup 作為全球數(shù)據(jù)挖掘領(lǐng)域最有影響力的賽事，自1997年以來由 ACM 協(xié)會(huì)的SIGKDD每年舉辦一次，被譽(yù)為數(shù)據(jù)科學(xué)領(lǐng)域的“世界杯”。
該賽事每年都吸引著眾多世界頂級(jí)的企業(yè)、高校與研究機(jī)構(gòu)的參與，為數(shù)據(jù)挖掘領(lǐng)域研究者提供了一個(gè)學(xué)術(shù)交流和研究成果展示的理想平臺(tái)。KDD Cup多年來一直保持著很高的產(chǎn)業(yè)界參與度以及對(duì)解決實(shí)際問題的敏感度。
城市大腦挑戰(zhàn)賽
今年數(shù)據(jù)挖掘頂會(huì)KDD在數(shù)據(jù)競(jìng)賽單元KDD Cup特別設(shè)置了City Brain Challenge，旨在挑戰(zhàn)城市容納車輛極限，助力城市交通決策規(guī)劃。主辦方為參賽者提供了一個(gè)城市規(guī)模的真實(shí)道路網(wǎng)絡(luò)，且其交通需求來自真實(shí)的交通數(shù)據(jù)。參賽者將負(fù)責(zé)協(xié)調(diào)交通信號(hào)，以最大程度地服務(wù)車輛，同時(shí)保持可接受的延遲。
本次競(jìng)賽一共吸引了來自全球的 1156 支參賽隊(duì)伍，其中不乏 4Paradigm、German Aerospace Center、NTT、BOE、Alibaba Group、Didi Chuxing以及Purdue University、NYU、IIT等國(guó)際頂尖研究機(jī)構(gòu)的身影。
來自上海交通大學(xué)高速信號(hào)處理實(shí)驗(yàn)室的 IntelligentLight 團(tuán)隊(duì)，從上千支參賽隊(duì)伍中脫穎而出，在預(yù)賽和決賽階段都取得了第一名的好成績(jī)，最終斬獲City Brain Challenge賽道冠軍。
（官方競(jìng)賽結(jié)果網(wǎng)頁鏈接：http://www.yunqiacademy.org/poster）
圖1 ：來自上海交通大學(xué)高速信號(hào)處理實(shí)驗(yàn)室的IntelligentLight團(tuán)隊(duì)在City Brain Challenge賽道摘得桂冠，團(tuán)隊(duì)成員包括宋罡（碩士）、張正（碩士生）、王楚凡（碩士生）、顧煜程（本科生）、孫澤鈺（本科生），指導(dǎo)教師是宮新保老師。
為什么參加這個(gè)比賽？
上海交通大學(xué)高速數(shù)字信號(hào)處理實(shí)驗(yàn)室在宮新保老師的帶領(lǐng)下，長(zhǎng)期從事高速數(shù)字信號(hào)處理領(lǐng)域的系統(tǒng)設(shè)計(jì)和軟硬件實(shí)現(xiàn)工作，成功研發(fā)了多種高速數(shù)字處理系統(tǒng)，在相關(guān)領(lǐng)域積累了豐富的關(guān)鍵技術(shù)和工程經(jīng)驗(yàn)。近年來，實(shí)驗(yàn)室依托自身優(yōu)勢(shì)，在人工智能、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域也取得了突出成績(jī)。
實(shí)驗(yàn)室的鮮明特色是以需求為導(dǎo)向，做科學(xué)研究的同時(shí)解決實(shí)際問題，為社會(huì)發(fā)展貢獻(xiàn)力量。而 KDD Cup 2021 城市大腦挑戰(zhàn)賽的賽題源自真實(shí)的交通場(chǎng)景，真實(shí)的交通數(shù)據(jù)，激發(fā)了實(shí)驗(yàn)室?guī)熒膮①悷崆椤?/span>這是實(shí)驗(yàn)室第一次參加KDD CUP 這樣的國(guó)際頂級(jí)賽事，首次比賽即獲得冠軍，這也充分展現(xiàn)了實(shí)驗(yàn)室在數(shù)據(jù)挖掘領(lǐng)域的技術(shù)積累和研究實(shí)力。
解決方案
1）問題分析
KDD Cup 2021城市大腦挑戰(zhàn)賽提供了一個(gè)城市規(guī)模的道路網(wǎng)絡(luò)，其交通需求來自真實(shí)的交通數(shù)據(jù)。每個(gè)隊(duì)伍負(fù)責(zé)協(xié)調(diào)個(gè)路口的交通信號(hào)燈，以最大限度地增加服務(wù)車輛的數(shù)量，同時(shí)保持可接受的延誤。
在這個(gè)問題中，最重要的評(píng)價(jià)指標(biāo)是延遲指標(biāo)（Delay Index）。延遲指標(biāo)的定義是，其中，是車輛已經(jīng)行駛的時(shí)間加上車輛在剩余道路上自由通行的時(shí)間，是車輛在整條行駛路徑上自由行駛的時(shí)間。
在本次比賽中，每個(gè)紅綠燈有8個(gè)相位，我們的任務(wù)具體而言就是在城市路網(wǎng)中對(duì)這8個(gè)相位之間選擇和切換，使總延誤指標(biāo)，也就是每輛車延誤指標(biāo)的均值最小。
圖2 南昌道路路網(wǎng)信息 
圖3 城市路網(wǎng)可視化示例
經(jīng)過大量文獻(xiàn)閱讀和調(diào)研，我們發(fā)現(xiàn)現(xiàn)有的交通信號(hào)燈控制方法主要分為強(qiáng)化學(xué)習(xí)算法和傳統(tǒng)交通模型分析算法。傳統(tǒng)算法中比較具有代表性的是最大壓力法（Max Pressure），它的總體思想是定義一個(gè)合適的車道壓力來反映車道的擁堵情況，并根據(jù)這一概念選擇壓力最大的車道放行。在本次比賽中，我們吸收了最大壓力法的許多基本思想。
圖4 最大壓力法示意圖
我們也研究并實(shí)驗(yàn)了一些強(qiáng)化學(xué)習(xí)（Reinforcement Learning）方法（比如DQN、PG、PPO、A3C等）。RL方法的優(yōu)點(diǎn)是可以建模許多超出邏輯理解能力的抽象特征，用神經(jīng)網(wǎng)絡(luò)完成計(jì)算和更新。
但在挑戰(zhàn)賽中，它也有一些不可避免的缺點(diǎn)：首先，我們很難將延遲指標(biāo)直接設(shè)置為獎(jiǎng)勵(lì)函數(shù)，而延遲指標(biāo)與其他類型的獎(jiǎng)勵(lì)函數(shù)之間又存在不確定的數(shù)學(xué)關(guān)系；其次，城市規(guī)模的路網(wǎng)對(duì)數(shù)據(jù)和計(jì)算資源有很大的需求，很難做到高效的訓(xùn)練和模型迭代。
2）建模過程
我們算法總體框架的核心思想是，以每輛車為中心建模，根據(jù)我們收集的信息給每輛車分配一個(gè)投票分?jǐn)?shù)。對(duì)于信號(hào)燈路口的每個(gè)時(shí)間點(diǎn)，我們分析如圖5所示的八種相位的情況，將其Q值定義為該相位下車輛投票得分的總和，繼而選擇Q值最大的相位作為該路口在當(dāng)前時(shí)間點(diǎn)的最佳相位。
圖5 路口八相位示意圖
經(jīng)過數(shù)據(jù)特性的搜集和數(shù)據(jù)預(yù)處理，我們從比賽方提供的車流仿真器——CBEngine 中搜集并清洗出了3萬多條數(shù)據(jù)，用于后期訓(xùn)練集成學(xué)習(xí)模型。而分析數(shù)據(jù)的過程也極大的啟發(fā)了模型的建立。我們基于數(shù)據(jù)分析建立了一個(gè)簡(jiǎn)化的交通模式識(shí)別機(jī)制：當(dāng)一輛車進(jìn)入路網(wǎng)時(shí)，它的路線將被記錄并與現(xiàn)有的車輛道路進(jìn)行比較和交叉研究；在這一過程中，我們假設(shè)在同一路口且朝著同一方向移動(dòng)的車輛有相似路線的概率很高，并依據(jù)該假設(shè)對(duì)新出現(xiàn)的車輛的未來路徑和總行駛時(shí)間進(jìn)行預(yù)測(cè)。
有了這一識(shí)別機(jī)制，我們嘗試預(yù)測(cè)車輛一段時(shí)間后的距離、速度，這些嘗試啟發(fā)了我們后面建立的時(shí)間項(xiàng)；并且用歷史信息對(duì)車輛路徑信息的預(yù)測(cè)經(jīng)驗(yàn)證達(dá)到了60%的準(zhǔn)確率，這一信息對(duì)后面提到的壓力項(xiàng)的設(shè)計(jì)作用極大。
接下來就是具體的模型建立，在Max Pressure方法與交通模式識(shí)別機(jī)制的有效的基礎(chǔ)上，為了提高性能，我們又進(jìn)一步添加了各種特征。最終將每輛車的投票得分定義為三個(gè)項(xiàng)目的乘積：
第一項(xiàng)是車輛在時(shí)間點(diǎn) t 時(shí)總行駛路徑的時(shí)間預(yù)測(cè)項(xiàng)。根據(jù)延遲指標(biāo)的定義，自由行駛時(shí)間較小的車輛的延遲指標(biāo)會(huì)對(duì)總延誤指標(biāo)造成更大的影響，因此我們提升了這些車輛的票值，并區(qū)分為以下兩種情況：對(duì)于路徑信息已知車輛，該項(xiàng)值為一常數(shù)除以其自由行駛時(shí)間，該常數(shù)為實(shí)驗(yàn)中得到經(jīng)驗(yàn)值；對(duì)于路徑信息未知車輛，該項(xiàng)值為1。實(shí)驗(yàn)結(jié)果表明，這一項(xiàng)添加進(jìn)方程確實(shí)對(duì)模型性能的提高有一定作用。
第二項(xiàng)為時(shí)間點(diǎn) t 時(shí)的壓力項(xiàng)。對(duì)于車道中的某一輛車，它的上游車道壓力可以容易得到（即為當(dāng)前所在車道的壓力）；而由于其下游車道未知，下游壓力的定義需要借鑒我們構(gòu)建的交通模式識(shí)別機(jī)制（有60%的預(yù)測(cè)準(zhǔn)確率），具體也分為兩種不同情況：如果道路可以根據(jù)歷史信息被準(zhǔn)確預(yù)測(cè)出，那么下游壓力就是其目的地的壓力；如果道路信息無法被預(yù)測(cè)，那么下游壓力取為下游內(nèi)側(cè)車道和直行車道壓力中的最大值。這一項(xiàng)的定義基于車輛不會(huì)在上游道路中變換其車道的假設(shè)。
第三項(xiàng)為基于道路的時(shí)間項(xiàng)。由于靠近路口的車輛更有可能快速到達(dá)交叉路口，在下一階段的投票中，它們應(yīng)該有更大的票值權(quán)重。為了精確衡量車輛到達(dá)路口的時(shí)間，我們將道路剩余長(zhǎng)度、車輛當(dāng)前速度、道路限速等信息進(jìn)行了綜合考量，以此為基礎(chǔ)設(shè)計(jì)了基于道路的時(shí)間項(xiàng)。
在實(shí)驗(yàn)過程中我們發(fā)現(xiàn)，在車輛通行高峰時(shí)間或發(fā)生事故時(shí)，某些路口的下游車道可能完全阻塞導(dǎo)致壓力項(xiàng)失效。針對(duì)這一問題，我們?cè)O(shè)計(jì)了一種動(dòng)態(tài)黑名單機(jī)制，對(duì)車輛模型進(jìn)行修正：
如果在綠燈放行階段檢測(cè)到任一上游車道上的第一輛車沒有移動(dòng)，那么我們就認(rèn)為該車道存在異常情況。對(duì)于每輛車而言，參數(shù)取決于車輛當(dāng)前所在車道是否被列入黑名單。
圖6 下游壓力黑名單項(xiàng)示意圖
在競(jìng)賽中，有兩種情況會(huì)使道路被列入黑名單：當(dāng)前道路有過高的下游壓力或由于未知原因產(chǎn)生異常。對(duì)于過高下游壓力的車道，我們?cè)O(shè)置一個(gè)放行閾值，當(dāng)下游壓力低于該閾值時(shí)放行；對(duì)于未知原因的異常車道，我們建立一個(gè)指數(shù)衰減的測(cè)量因子來轉(zhuǎn)移對(duì)這些車道的關(guān)注，直至其恢復(fù)正常。
舉一個(gè)簡(jiǎn)單的例子，在圖6中，5車道由于下游道路擁堵將會(huì)被認(rèn)為有異常情況，將被列入黑名單暫時(shí)封堵直至其下游道路壓力釋放。因此，在相位選擇時(shí)會(huì)優(yōu)先考慮上游壓力更小的8車道。
算法實(shí)現(xiàn)中，我們的智能體首先檢測(cè)在黑名單中的上游車道能否被移出黑名單，再檢測(cè)當(dāng)前路口的車道中是否有部分需要被加入黑名單。在這一過程中我們?cè)O(shè)置的移除黑名單的條件總是比加入黑名單的條件強(qiáng)。并且黑名單機(jī)制具有很強(qiáng)的擴(kuò)展性，可以添加其它原因以提升模型的適應(yīng)力。
3）實(shí)驗(yàn)結(jié)果
圖7 和最大壓力法相比的實(shí)驗(yàn)結(jié)果
為了測(cè)試我們的模型效果，我們?cè)诒荣惙教峁┑能嚵魃线M(jìn)行測(cè)試。圖7中是與Max Pressure 方法比較的結(jié)果，可以看到我們的方法幾乎在每一個(gè)時(shí)間步長(zhǎng)上的延遲指標(biāo)都小于 Max Pressure。表中反映的是以20秒為時(shí)間步長(zhǎng)，延遲指標(biāo)為1.4時(shí)所用的時(shí)間和服務(wù)車輛數(shù)，證明了我們的算法在更短時(shí)間內(nèi)服務(wù)了更多的車輛。
圖8 開關(guān)不同機(jī)制性能比較
圖8則反映了我們?cè)O(shè)計(jì)的各種機(jī)制的合理性。圖中藍(lán)色的折線表示了我們最終提交的模型的性能，可以看到各個(gè)機(jī)制都對(duì)提升模型效果起到了獨(dú)特的作用。
專訪
1）我們是從4月下旬熱身賽的后期進(jìn)入比賽，之后全程參與了資格賽（預(yù)賽）和決賽，一直到7月5日比賽結(jié)束。總共持續(xù)了2個(gè)多月的時(shí)間。
2）比賽中實(shí)際投入的時(shí)間要少一些，因?yàn)閰①愱?duì)員都是在校學(xué)生，準(zhǔn)備期末考試花費(fèi)了3周左右的時(shí)間。剩下的時(shí)間投入的精力比較多。
因?yàn)槭堑谝淮螀①悾覀兊闹饕康倪€是學(xué)習(xí)和積累經(jīng)驗(yàn)，同時(shí)檢驗(yàn)我們的能力；所以并沒有想到會(huì)拿冠軍。
只是到了決賽的最后階段，我們的分?jǐn)?shù)逐漸和其他參賽隊(duì)伍拉開差距以后，才覺得可能會(huì)拿到冠軍。
3、AI科技評(píng)論：比賽中遇到的最大挑戰(zhàn)是什么？
1）首先是特征提取和建模。比賽提供的是接近真實(shí)道路網(wǎng)絡(luò)模型的仿真體；參賽方獲得的直接信息是仿真體的行為，即車流的行為信息。我們需要根據(jù)具體的行為，提取出有價(jià)值的特征，并進(jìn)行問題建模。
2）其次是算法創(chuàng)新。因?yàn)閱栴}不是直接照搬現(xiàn)有算法就能解決的，必須針對(duì)問題提出創(chuàng)新性的解決方案。
3）總體而言，對(duì)問題的理解越深入，特征提取越準(zhǔn)確，建模越精細(xì)、越貼近實(shí)際，提出的算法越能夠“對(duì)癥下藥”，那么獲得的性能就越好。
4、AI科技評(píng)論：比賽方案的核心亮點(diǎn)是什么？為何能奪冠？
1）核心亮點(diǎn)之一是精細(xì)建模。我們精心設(shè)計(jì)了抽象度高的路網(wǎng)特征；這些特征對(duì)算法的訓(xùn)練和參數(shù)調(diào)整有很大的幫助。
2）核心亮點(diǎn)之二是用強(qiáng)化學(xué)習(xí)對(duì)模型中不可導(dǎo)的參數(shù)進(jìn)行了訓(xùn)練。
3）我們這次比賽之所以能夠取得好成績(jī)，一方面是我們團(tuán)隊(duì)的工程經(jīng)驗(yàn)比較豐富，對(duì)問題分析——建模——求解這套流程非常熟悉，閉環(huán)速度快，而且能夠根據(jù)實(shí)際情況快速調(diào)整；
另一方面是我們對(duì)人工智能和數(shù)據(jù)挖掘領(lǐng)域都有一定的了解，能夠快速的篩選和提取有價(jià)值的算法思路。
5、AI科技評(píng)論：比賽方案還有優(yōu)化和進(jìn)步空間嗎？
1）因?yàn)楸荣惖膯栴}接近實(shí)際場(chǎng)景，所以我們還是有一些想法可以繼續(xù)嘗試的；只是因?yàn)楸荣惖臅r(shí)間限制，而沒有來得及實(shí)施。
2）首先我們打算用類似圖神經(jīng)網(wǎng)絡(luò)的手段實(shí)現(xiàn)多個(gè)路口之間的信息傳遞，增加信息傳播的維度和廣度。（目前在我們的算法中，路口之間的信息傳遞主要靠路口車輛密度來傳遞。）
3）其次是可以嘗試通過多路口的協(xié)調(diào)機(jī)制，來實(shí)現(xiàn)類似交通控制學(xué)中的綠波控制和紅波控制。
6、AI科技評(píng)論：其他隊(duì)伍的比賽方案有什么亮點(diǎn)或借鑒之處嗎？
1）我們?cè)诒荣愔蟮膹?fù)盤階段，對(duì)其它參賽隊(duì)伍的比賽方案也進(jìn)行了仔細(xì)研究。前幾名隊(duì)伍的方案大體可以分為以交通學(xué)模型為主和以強(qiáng)化學(xué)習(xí)為主的兩種類型，二者各有優(yōu)勢(shì)。
2）以交通學(xué)模型為主的方法和我們最終的解決方案的總體思路比較接近，即基于對(duì)路網(wǎng)和車流信息的數(shù)據(jù)分析、實(shí)現(xiàn)對(duì)交通燈的智能調(diào)控；不過各個(gè)隊(duì)的特征選取和參數(shù)設(shè)定有比較大的區(qū)別。
3）以強(qiáng)化學(xué)習(xí)為主的方法針對(duì)具體的應(yīng)用場(chǎng)景，對(duì)DQN等強(qiáng)化學(xué)習(xí)方法進(jìn)行了大量的優(yōu)化和改進(jìn)，最終也達(dá)到了很好的效果。這也有點(diǎn)出乎我們的意料。
4）這些參賽隊(duì)伍采用的方法和思路都有自己的亮點(diǎn)和絕活，都值得我們研究和借鑒。
7、AI科技評(píng)論：比賽全程下來有對(duì)哪個(gè)環(huán)節(jié)或者設(shè)置上有不滿意的地方嗎？
1）首先要說的是，這種高質(zhì)量的賽事在賽題設(shè)置、比賽環(huán)境和賽事組織方面都相當(dāng)完善和高效，用于模擬現(xiàn)實(shí)環(huán)境的仿真體的質(zhì)量也相當(dāng)高、在兩個(gè)多月的運(yùn)行中基本上沒有bug，這也讓我們很開眼界。
2）如果非要說有什么不滿意的地方，就是決賽賽題的設(shè)置：模擬時(shí)長(zhǎng)較短（上限20分鐘），車流密度高（測(cè)算下來高于實(shí)際路網(wǎng)的車流密度）。這雖然提升了比賽難度，但是會(huì)傾向于讓貪婪算法類型的方案獲得更好的效果，這可能和賽題設(shè)置的初衷不太一樣。
8、AI科技評(píng)論：有用到比賽提供的城市大腦開放研究平臺(tái)嗎？感覺如何？
1）確實(shí)用到了比賽方提供的云計(jì)算平臺(tái)，而且對(duì)我們的幫助很大。
2）云計(jì)算平臺(tái)提供的算力規(guī)模龐大，大大提高了算法迭代的速度和調(diào)參速度，不是一般的服務(wù)器能夠相比的。
3) 所以這次比賽讓我們學(xué)習(xí)了計(jì)算機(jī)集群的使用方法，也領(lǐng)教了其巨大算力。
總結(jié)與展望
KDD是數(shù)據(jù)挖掘領(lǐng)域的最頂級(jí)會(huì)議，而 KDD Cup 可以說是數(shù)據(jù)挖掘競(jìng)賽里的皇冠，能摘下桂冠，對(duì)我們的意義是非同凡響的。經(jīng)過本次比賽，上海交通大學(xué)高速信號(hào)處理實(shí)驗(yàn)室不僅進(jìn)一步凝聚了實(shí)驗(yàn)室力量，而且證明了實(shí)驗(yàn)室的研究能力和技術(shù)實(shí)力。
這次比賽的賽題非常貼近實(shí)際場(chǎng)景，具有很高的挑戰(zhàn)性和實(shí)際意義。接下來，上海交通大學(xué)高速信號(hào)處理實(shí)驗(yàn)室將更加注重產(chǎn)學(xué)研相結(jié)合，推進(jìn)相關(guān)技術(shù)的成果轉(zhuǎn)化和實(shí)際落地應(yīng)用，為智慧交通的發(fā)展貢獻(xiàn)力量。
贈(zèng)書福利
AI科技評(píng)論本次聯(lián)合Springer為大家?guī)?strong style="outline: 0px;">5本周志華教授親筆簽名的《Machine Learning》正版新書。
在AI科技評(píng)論8月28日頭條文章“周志華《西瓜書》上線英文版！”（注意不是本文，僅限AI科技評(píng)論微信公眾號(hào)端）留言區(qū)留言，歡迎大家暢所欲言，談一談你對(duì)本書的看法和期待。在綜合留言質(zhì)量（留言是敷衍還是走心）和留言點(diǎn)贊最高（注：點(diǎn)贊最高的前5不意味著一定會(huì)中獎(jiǎng)）的讀者中選出5位讀者獲得贈(zèng)書。獲得贈(zèng)書的讀者請(qǐng)聯(lián)系 AI 科技評(píng)論客服（aitechreview）。
留言內(nèi)容會(huì)有篩選，例如“選我上去”、“這書寫的很棒（僅僅幾個(gè)字）”等內(nèi)容將不會(huì)被篩選，亦不會(huì)中獎(jiǎng)。
留言送書活動(dòng)時(shí)間為2021年8月28日 - 2021年9月01日（23:00），活動(dòng)推送時(shí)間內(nèi)僅允許贈(zèng)書福利中獎(jiǎng)一次。
雷鋒網(wǎng)雷鋒網(wǎng)雷鋒網(wǎng)
雷峰網(wǎng)特約稿件，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
專題
本專題其他文章
