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），活動推送時間內僅允許贈書福利中獎一次。
雷鋒網雷鋒網雷鋒網
雷峰網特約稿件，未經授權禁止轉載。詳情見轉載須知。
專題
