前言：又到春招季！作為國民級出行服務平台，高德業務快速發展，大量校招/社招名額開放，歡迎大家投遞履歷，詳情見文末。為幫助大家更了解高德技術，我們策劃了#春招專欄#的系列文章，組織各業務團隊的高年級同學以科普+應用實踐為主要内容為大家做相關介紹。
本文是#春招專欄#系列的第1篇，根據高德機器學習研發部負責人damon在AT技術講壇所分享的《AI在出行領域的應用實踐》的内容整理而成。在不影響原意的情況下對内容略作删節。
AT技術講壇(Amap Technology Tribune)是高德發起的一檔技術交流活動，每期圍繞一個主題，我們會邀請阿裡集團内外的專家以演講、QA、開放讨論的方式，與大家做技術交流。
damon根據使用者在出行前，出行中和出行後如何使用導航服務，分别選取了幾個典型的業務場景來介紹AI算法在其中的應用，最後對未來做了一些展望。
以某位同學周末和朋友相約去“木屋燒烤”店撸串為例，假設這位同學選擇駕車前往目的地，我們來看下AI算法是如何在導航過程中起到作用的。
出行前，先做路線規劃，ETA（預估到達時間），不要遲到；出行中，最怕的就是遇到突發動态事件而影響到出行時間；出行後（到目的地），餐館是否還在正常營業，也需要通過技術挖掘，幫助使用者提前規避白跑一趟的風險。
下面分别介紹。
出行前-路線規劃
路線規劃，和網頁搜尋，商品搜尋的推薦算法很相似，為使用者推薦一條符合個人喜好的優質路線。推薦的路線要符合以下幾個條件：
- 能走：此路能通，按照路線可以到達終點。
- 好走：路線品質在目前地點時間下確定優質。
- 千人千面：不同使用者在保證路線優質的前提下，個性化調整更符合使用者偏好。
同時，在不對使用者産生誤導的前提下，提供更多的對比參考給使用者來選擇：
- 優質：相比首路線/主路線，有一定的、使用者可感受到的優勢。
- 多樣：相比首路線/主路線，盡可能有自己的特長。
路線規劃算法的特點
從使用者産生出行需求，到需求得到滿足。在使用者搜尋的時候，上傳的Query除了有起終點和導航政策，也會像其他搜尋一樣，有隐含的需求，比如個性化和場景化。在導航業務裡面，個性化可以拆分成熟路和偏好兩個次元，熟路比較容易了解，偏好是指使用者對時間、距離、紅綠燈、收費等不同次元上的偏好。
那麼，對應的解決方案，我們引入使用者ID，存儲記憶了使用者的起終點對應的熟路資訊。對使用者的偏好，類似DIN的網絡結構，對使用者曆史導航序列進行模組化，擷取使用者偏好資訊。
在使用者送出搜尋需求之後，對導航引擎來說，也分為召回，排序和過濾幾部分。
對于導航的召回，對性能要求比較高，是以目前召回的結果較少。對排序來說，同樣是多目标，而且多目标之間要進行平衡的業務。類比到電商推薦領域，不僅希望使用者更多地對商品進行點選浏覽，還希望使用者在看完商品介紹之後進行購買，提高GMV。
對于地圖出行，不僅希望使用者更多的使用導航且按照推薦的路線走，還希望實走時間要盡可能短，使用者回報盡量好。
而且，和其他領域類似，多個目标之間會存在沖突，比如電商CTR和GMV。在導航領域，讓使用者盡可能的走封閉道路，沒有出口，那肯定實走覆寫率就上升了，但是這樣規劃的路線會繞遠，時間和距離都變差。
多目标的平衡，如何在“帕累托最優”的情況下，進行多個目标之間的取舍、平衡，是大家一直在探索的問題，我們目前采用的是帶限制的最優化問題來進行模組化，就是保證其他名額不變差的情況下，把某個名額最優化。
最後，使用者拿到導航引擎傳回的路線結果，特點是資訊少，使用者隻能看到整條路線的總時間、總距離和收費等統計資訊，對于這條路好不好走，能不能走很難知道。
而且，大部分使用者是在陌生場景下用導航，對導航依賴很重，很難決策走哪條路更好，這就導緻排序在首條的方案選擇率很高，達到90%以上，這個偏置是很嚴重的，在訓練實走覆寫率的時候，我們設計了偏置網絡，來吸收使用者這種傾向。
導航還有一個特點，一旦出錯，對使用者傷害特别大，比如遇到小路，使用者的車可能會出現刮蹭；遇到封路，使用者可能就得繞路，付出相當的時間和金錢成本。這往往會比資訊搜尋給使用者帶來的影響和傷害更大。是以，我們在過濾階段，對Badcase的過濾也是嚴格作為限制要求的。
路線規劃召回算法
路線規劃算法，經典的是教科書上的Dijkstra算法，存在的問題就是性能比較差，線上實際應用都做了優化，這裡就不展開介紹了。
當起終點距離超過500公裡，性能基本就不可接受了，雖然有啟發式A star算法，但是A star算法有可能丢最優解，并不是完美解決性能問題的方法。
解決性能問題的思路，一個是分布式，一個是Cache，而最短路線搜尋并不像網頁搜尋，分布式并不能很好的解決性能問題，是以目前工業界實際使用的算法都是基于Cache的方法。
Cache的方法就是提前把一些起終點對之間的最短路線計算好（Shortcuts），在使用者請求過來的時候，利用好這些Shortcuts，達到加快求路的目的（簡單舉例子，比如從北京到廣州，如果提前計算好了從北京到濟南，濟南到南京，南京到廣州的最短路徑，那就可以在計算北京到廣州的時候，利用這些提前計算好的最短路線）。
其中最為經典的一個算法就是CH算法(Contraction Hierarchies)，在預處理階段，對所有節點進行了重要性排序，逐漸把不重要的點去掉，然後增加Shortcuts；Query查詢階段，從起點和終點分别開始雙向求路，隻找重要性高的點，來達到加速的目的。
既然是Cache，就會面臨一個更新的問題，比如原始路網的路況變化了，或者原始路網某條路封路了，那麼提前緩存好的Shortcuts也需要更新。
這個時候CH的算法，由于Shortcuts結構設計不夠規律，更新就很慢，無法響應實時路況的變化。于是，路線規劃算法推進到了下一代，CBR算法（Cell based Routing），這個算法通過分而治之的思想，在預處理階段，把全國路網切分成n個子圖，切分的要求是子圖之間連接配接的邊（邊界邊）盡可能的少。
在每個子圖内，再繼續往下切分，進而形成金字塔結構，預處理階段就是把邊界邊之間的最短路徑都提前算好，Cache下來求路的時候，就可以利用這些Shortcuts了。
CBR的優點是，在預處理階段，路網的切分是分層的，每一層都足夠小，在更新這一層的Shortcuts的時候，可以把資料都放到CPU的L1 Cache裡去，是以計算速度特别快。
總結一下CBR和CH的差別：
- Query查詢性能，CH更快，CH是0.1ms級别，CBR是1-2ms級别。
- Shortcuts更新性能，CH全國路網更新最快能做到10分鐘，而CBR能做到15秒更新全國，可以滿足實時路況變化和路網實時更新的需求。
- CH的Shortcuts不規律，導緻不同政策之間（躲避擁堵，高速優先等）不能很好的複用Shortscuts的起終點結構，是以不同政策需要單獨重建Shortcuts，記憶體占用非常大。
這是我們排序的網絡結構，左邊是使用者偏置網絡，把路線排序的順序，以及引導路線之間的相似度資訊輸入進去，期望盡可能消除掉偏置帶來的影響。中間輸入的使用者曆史統計資訊和使用者導航序列資訊，用來提取使用者的個性化偏好。優化的主要目标是實走覆寫率。
新一代的路線規劃算法，要求提供随時間推演的能力。比如8:00從起點出發，後面要走 1 2 3 ..n條路到達目的地，假設8:10走到第2條道路，8:20走到第3條道路，那麼我們在8:00計算Shortcuts的時候，就不能隻用到8:00的路況，需要把後續進入某個道路的時刻考慮進來，用那個時刻的路況來計算，這就是TDR求路算法，目前是高德首創的，能真正實作躲避未來的擁堵，并利用未來的暢通來規劃路徑。
出行前-ETA（預估到達時間）
上面三幅圖，選取的是北京西單金融街附近的區域，展示了在三個相鄰時間點上的交通狀況。其中綠色、黃色、紅色代表交通路況不同的狀态。
假設現在是18點整，路況預測的目标就是預估未來時刻的交通狀況，需要依賴每條道路的曆史資訊，以及周邊鄰居的道路擁堵資訊，對時空兩個次元進行模組化。
對時間序列的模組化，用RNN，LSTM等SEQ2SEQ的序列，也有采用CNN，TCN等。對空間資訊的模組化，目前主流的方法是用GRAPH.
盡管模型在不斷更新，越來越複雜，但是對于突發事件導緻的擁堵，根據曆史統計資訊，很難預測精準，比如去年9月份在上海世博園區舉行外灘大會，世博園平時很少有人去，曆史路況都是暢通，而在開會期間，車很多導緻很堵。
這個時候靠曆史資訊是很難預測準确，我們需要一個能代表未來的信号，才能預測，這就是路線規劃的資訊，如果想去世博園的人很多，那麼規劃的量就會很多，我們根據規劃的量，就能知道未來有很多人想要去世博園，就會導緻世博園擁堵。
是以，我們把規劃的量，通過一個流量往時間域的轉換，引入到路況預測模型，效果取得明顯提升，尤其是在突發擁堵的時候，高德的這個研究成果被KDD2020收錄，并且已經在業務場景中得到了應用，有興趣的同學可以詳細檢視我們的論文。
行中-用文本資料挖掘動态交通事件
繼續向餐館前進，導航途中，最怕遇到擁堵，封路等事件，是以高德會想盡一切辦法挖掘這些動态事件，幫助使用者規避開。現在高德用到了多個次元的資料源，其中的行業和網際網路情報都是文本資料，要用到NLP的技術來挖掘。
介紹一下怎麼用AI算法來挖掘動态事件。
下面一段文本就是典型的來自于網絡媒體的資訊：
G0612（西和）高速南繞城路段西山隧道ZK33+844（蘭州方向）應急車道停一輛故障大客車暫時封閉，行車道和超車道正常通行，請車輛注意避讓、減速慢行。
這段資訊是非結構化的，需要我們做預處理，要素提取，再進行事件的組織，組織成架構化的資訊，才能自動化的應用。
很自然的，針對要素提取，我們用BERT模型模組化，但是BERT模型太複雜，性能比較差，線上實際應用帶來很大的挑戰。
我們采取了知識蒸餾的方法，訓練一個簡單的Student的網絡，來解決性能問題。知識蒸餾最主要的是如何捕捉潛在語義資訊。高德在業界率先提出了用對比學習架構進行知識蒸餾，同時，在計算樣本之間距離的時候，提出COS-距離代替歐氏距離的方法，能夠讓模型有效的學習到潛在語義表達資訊。
對于Student表達的特征向量與Teacher特征向量距離靠近，而要遠離負例。使用餘弦距離，比如歐式距離，能夠更好适應Teacher網絡和Student網絡，輸出的特征向量長度分布不一緻的問題，這個工作成果發表在了AAAI2021上。
出行後-POI資料過期（增強現勢性）的問題
人們在高德地圖上會看到很多地理位置興趣點（Point of Interest，縮寫為POI），例如餐廳、超市、景點、酒店、車站、停車場等。對POI資料的評價次元包括現勢性、準确性、完備性和豐富性。
其中，現勢性就是地圖所提供的地理空間資訊反映目前最新情況的程度，簡而言之，增強現勢性就是指盡可能快速地發現已停業、搬遷、更名、拆遷的過期備援POI資料，并将其處理成下線狀态的過程。這部分可以參考我們之前釋出的文章《高德地理位置興趣點現勢性增強演進之路》。
以上僅是AI算法在出行場景應用的一些舉例，更多的技術方案歡迎大家來和我們一起探讨。
出行前景-全局排程
對網頁搜尋來說，結果是資訊，可以無限複制，互不影響；對電商搜尋來說，結果是商品，可以認為商品足夠多，不夠再生産，是以也可以認為互不影響。
不同的是，導航搜尋出來的道路資源是有限的，你用的多了，我就用的少。比如，一條路暢通，我們把人導過去，那麼這條路就堵死了，是以我們要做全局排程，提高道路資源的使用率。
我們希望全局排程系統能和交通信号燈打通，在一個交通仿真的環境下，用多智能體強化學習的方法，學習到更大規模的交通系統上如何統籌協調車輛、交通燈，充分利用道路資源，進一步緩解擁堵。我們一起來探索！
春招火熱進行中，2022屆畢業生看過來！