Categories
程式開發

混合時空圖卷積網絡:能“推導”未來路況的智能算法


2020雲棲大會於9月17日-18日在線上舉行,阿里巴巴高德地圖攜手合作夥伴精心組織了 “智慧出行” 專場,為大家分享高德地圖在打造基於 DT + AI全面上雲架構 下的 新一代出行生活服務平台 過程中的思考和實踐,並重點分享了「高精地圖、高精算法、智能時空預測模型、自動駕駛、AR導航、車道級技術」等話題。

「高德技術」把本場講師分享的主要內容整理成文並陸續發佈出來,本文為第3篇。

【演講視頻播放地址】https://yunqi.aliyun.com/2020/session31

阿里巴巴高級算法專家冀晨光帶來的話題是 《混合時空圖卷積網絡:更精準的時空預測模型》 。冀晨光分享了高德提出的时空图卷积算法,巧妙利用海量用户的导航规划信息,“推导”出未来拥堵状况,显著提升预测准确度,并重点介绍了这一业界领先的技术及其在高德业务中的应用。

【相關閱讀】高德KDD2020論文解讀更精準的時空預測模型

作為一款國民級出行生活服務平台,高德擁有5.3億+月活用戶,在過去一年間,為出行用戶節省至少19.3億+小時擁堵時間,創造了巨大的社會效益。這裡廣為大家所熟知的 躲避擁堵功能背後的核心技術,就是交通路況預測算法

冀晨光的分享主要分三部分展開。

  • 路況預測是什麼。
  • 混合時空圖卷積網絡:能“推導”未來路況的算法。
  • 應用前瞻:從“路況預測”到“交通調度”。

路況預測是什麼

下面的三幅圖,展示了北京西單金融街附近的區域,在三個相鄰時間點上的交通狀況。其中綠色代表暢通,黃色代表緩行,紅色代表擁堵。假設現在是18點整,路況預測的目標就是預估未來時刻上的交通狀況,例如半小時之後、18:30的路況。從三個時刻的路況狀態及彼此的關聯中可以觀察到,擁堵會在時空上演化和傳播,路況預測就是要對這背後的規律進行精確的刻畫和建模。

混合時空圖卷積網絡:能“推導”未來路況的智能算法 1

路況預測技術支撐了高德地圖很多的核心功能。冀晨光舉了兩個代表性的案例。第一個案例是 路線的旅行時間預估 ,術語上叫做 。下方左圖是駕車路線規劃頁面,右圖是導航的頁面。其中紅框高亮的部分就是預估的ETA。 ETA是路線排序的重要因子,ETA預估的準確與否,直接決定了能否幫助用戶有效躲避擁堵。

混合時空圖卷積網絡:能“推導”未來路況的智能算法 2

第二個案例是 隨時間推演的路線規劃 。北京有外地小客車早晚高峰限行的政策,命中該政策的車在7到9點間不能進入五環。假設有一個這樣的車在6:45分出發。如下圖左圖所示,常規路線規劃只能基於當前時刻的限行信息算路,而6:45分時限行政策尚未生效,所以算出的路線就是穿越五環區域的路線,會導致用戶在7點後違章。

為了解決這個問題,高德設計了隨時間推演的路線規划算法,這個算法具有未來視角,能幫助用戶避讓未來即將來到的限行,如下圖右圖所示,推演路線會引導用戶在7點前駛出五環,走六環到達目的地。因此未來路況預測的是否精準,會影響到對用戶駛離五環時刻的判斷,也就會直接影響到用戶是否違章。

混合時空圖卷積網絡:能“推導”未來路況的智能算法 3

如何預測準未來路況 的問題上,業界主要有兩類方法。一類是 交通仿真 ,在車輛行駛的起終點信息之上,結合交通動力學理論,聯合仿真、預估車輛的行駛路徑和交通路況。這類方法屬於知識驅動的方法。另一類是 數據驅動的方法 ,通過訓練模型學習歷史路況和未來路況之間的統計關聯進而進行預測。這類方法是目前各大出行科技公司所主要依賴的方法。

业界现有的数据驱动方案,主要以历史交通状况为特征,辅助以部分事件类特征,例如异常天气、体育赛事等,常常难以预测准拥堵的起始时刻,导致预测延迟的问题。以下图中右图为例,横轴代表一天的不同时刻,纵轴代表一条道路的旅行时间。红色曲线代表道路的实际旅行时间,即真值。绿色曲线代表模型提前一小时给出的预测值。可以看到,在拥堵发生的阶段,大约8-9点之间,模型的预测表现出了显著的延迟。

這類問題不能通過單純升級模型的表達能力來徹底解決,不管是早期的經典機器學習模型,如隨機森林、GBDT,抑或是初期的深度學習模型,如stacked autoencoder、sequence-to-sequence model,還是近期提出的基於卷積網絡、圖卷積網絡的更先進的結構等等,就預測效果而言都存在類似的缺陷。

混合時空圖卷積網絡:能“推導”未來路況的智能算法 4

究其原因,從物理上講,擁堵來源於車流量的增大,現有方案的事件類特徵時空顆粒度較粗,不能在分鐘級別、路段級別上充分錶達未來車流量的信息,也即缺乏一個預示擁堵發生的提前量信號,因此無法從根本上克服這個問題。

隨後,冀晨光重點介紹了高德提出的解法。這項研究成果發表在今年的數據挖掘頂會KDD上。

混合時空圖卷積網絡:能“推導”未來路況的算法

第一步,從高德海量的實時駕車導航數據中預估出每條道路未來的車流量。如下圖中左圖的所示,在導航開始時刻,以及行中每隔固定的時間段,用戶的高德客戶端都會與雲端的導航引擎進行交互,請求引擎更新剩餘旅程的ETA。對應的,在導航引擎側,根據這同一個ETA,就能預估出單個用戶未來貢獻的流量值。

接下來,高德對 全體用戶的未來流量值按道路進行聚合 ,就獲取了未來任一時刻全路網的車流量分佈。以下圖中右圖為例,黃、紅、綠三輛車在出發時均使用了高德導航,對應顏色的虛線代表高德給出的規劃路線,箭頭代表預計到達該道路的時間點。可以看到,在8點05分,三輛車將一同到達灰色方框裡的道路。通過這樣的方式,高德可以提前幾十分鐘預判到這條道路在8點05分的車流量為3。實際中,高德導航行業領先的路面滲透率,讓這種方式預估的未來車流量能夠較好的近似真實的未來車流量。

混合時空圖卷積網絡:能“推導”未來路況的智能算法 5

第二步,高德提出了一個獨特的 混合時空圖卷積網絡 ,簡稱 高速鐵路 ,能夠有效的將這個未來車流量的特徵與傳統的道路旅行時間特徵整合處理。

具體來說,高德提出了一個域轉換器結構,將未來車流量特徵轉換成對應的道路通行時間特徵。接下來,一維時域門控卷積從這兩部分時間特徵上提取出更高維的模式。之後,基於提出的複合關聯矩陣的圖卷積網絡會捕捉住路網上各處擁堵之間的空間關聯關係。最後,兩個額外的時域門控卷積和全連接網絡進一步處理前述信號後進行解碼,輸出全路網道路未來的通行時間。

混合時空圖卷積網絡:能“推導”未來路況的智能算法 6

直觀的講,HSTGCN可以學習到車流量增大、道路變擁堵的交通動力學規律,能夠基於規劃的流量,推導出未來路況。這個方案,作為知識驅動和數據驅動方法的有機結合體,兼備了交通仿真和統計學習這兩種主流方法雙方的優勢。

下圖是模型佈署的工程架構圖。從左至右,導航客戶端實時上傳相關數據。其中路線規劃數據經過Blink實時流處理,生成前面提到的全路網未來的流量分佈。定位軌跡數據,經過路網匹配和處理,生成各個道路的旅行時間。 HSTGCN接入這兩個特徵源,實時預測、發布未來的交通路況,進而幫助導航引擎更精準的計算ETA和規劃路線。

混合時空圖卷積網絡:能“推導”未來路況的智能算法 7

冀晨光介紹了一個模型預測突發擁堵的實例。下圖裡有上下兩張圖,分別是HSTGCN和此前學術界的代表性路況預測模型STGCN的預測結果。圖的橫軸是一天的全部時刻,縱軸是一條道路的旅行時間。藍色曲線代表真實的路況,橙色曲線代表路況的歷史均值,其他顏色的曲線對應模型提前5-15分鐘的預測結果。可以看到,HSTGCN克服了上一代方法的不足,很好的解決了突發擁堵的預測問題。

混合時空圖卷積網絡:能“推導”未來路況的智能算法 8

此外,因為HSTGCN的預測是基於規劃車流量的,而這個預測值又會影響到下一個時刻的路線規劃,所以HSTGCN帶來了動態分流、消解擁堵的能力。

應用前瞻:從“路況預測”到“交通調度”

今天,各大出行科技公司所做的路況預測主要是被動式的統計預測,而HSTGCN則為主動式的交通調動第一次提供了工業界可落地的、數據驅動的解決方案。

可以暢想一下未來的情景。路線規劃引擎會從今天的單模態規劃演變成多模態規劃,綜合考慮駕車、公交、騎行、步行等多種出行方式。 HSTGCN利用規劃引擎產出的路線及預估時間,推導出未來路網上的交通狀況。接下來,智能調度模塊,例如紅綠燈相位調控引擎或是高速費調控引擎,基於預估的路況進行決策,決策的結果又反饋迴路線規劃引擎,干預路線推薦。

混合時空圖卷積網絡:能“推導”未來路況的智能算法 9

整個系統實時、動態的運轉,形成交通調度的智能閉環,有希望大大緩解交通擁堵,節約交通資源和成本,提高全局的運輸效率。

本文轉載自公眾號高德技術(ID:amap_tech)。

原文鏈接

混合時空圖卷積網絡:能“推導”未來路況的智能算法