強化學習與基於計程車軌跡資料的時空基礎模型

Abstract

為了妥善安排行程，通常透過各種方式規劃可能行經的軌跡路線，在這樣的背景下，了解所經道路的交通狀態至關重要，然而，各地的交通狀態不只隨時間變化，也被空間的特性影響，為了考慮時空間的關聯性，我們希望能探索基於時空基礎模型進行路線規劃的可能性，時空基礎模型是近幾年隨著語言基礎模型發展的一種大型深度神經網路模型，透過大量歷史資料的深度預訓練以及針對特定任務的微調訓練，對於擁有時空間特徵的軌跡或是圖片資訊學習其潛在的關聯，在我們的研究中，根據計程車駕駛的載客軌跡資料，以及足夠精細的路網資訊，可以看到計程車深入每一個大街小巷的旅行行為，我們希望時空基礎模型能學習到台北市路網中的潛在時空間關係，並且，根據歷史旅行時間，預測不同時空間組合情況下的軌跡其所需的預期旅行時間，這將為規劃路線打下了基礎，有別於過去只針對特定時段或是區域的模型，時空基礎模型學習的資訊包含整個城市與整個月的計程車軌跡資料，在隨機預測預期旅行時間的任務上，我們的模型達到17.28%的MAPE，然後，我們將這個模型作為路線選擇模型的參考基準，在本研究中，使用強化學習作為訓練路線選擇模型的基底，在不斷於路網中遊走的同時，不只參考與終點可能路線的靜態特徵，也根據時空基礎模型的預期旅行時間修正模型，強化學習的路線選擇模型通常用馬可夫決策過程作為整個架構的基礎，考量當下狀態與選擇進行策略調整，我們的模型還考慮在不同時間段中的路網動態車速變化，從而調整整體選擇的行為，我們的獎勵函數分成時間懲罰、距離獎勵以及抵達獎勵，透過這樣的設計促使模型能夠在不浪費時間的情況下抵達終點，本研究的模型架構具有針對不同使用者調整的彈性，未來能夠對於想要解決的問題進行進一步的調整，最後，我們比較強化學習的路線選擇模型、Google route API以及最短路徑演算法這三種策略，將大安區中的四個點作為起點，隨機挑選大安區中其他路段作為迄點，我們的模型與Google皆考慮時間特徵為星期五下午兩點與晚上六點的動態路網影響，在結果中發現，Google所提供的路線多以主要道路為主，最短路徑演算法多喜歡走路網中的小路，本研究所提出的強化模型則主要介於兩者之間，達到與Google差不多的路徑規劃能力以及優於最短路徑演算法的結果，藉由可能相對於Google公司較少的資料達到這樣的結果。

In order to arrange the schedule properly, there are several strategies to generate the possible route. In this context, understanding the road states is crucial. However, the road states are affected not only by temporal shifting but also the spatial properties. We expect to explore the possibility of planning a route upon spatial temporal foundation model (STFM) by considering the spatial and temporal characteristics. STFM is an extension of language foundation model, a large deep learning model. It is pretrained by historical data and finetuned for task. And it learns the implicit relationship from trajectory or image with spatial temporal features. In our research, we expect the STFM can understand the implicit spatial temporal meaning in Taipei city, by comprehensive taxi trajectory and highly detailed road network. Furthermore, predicting the estimated travel time of different combination of trajectory based on historical travel time. That lays on the foundation for route planning. STFM is different from the former travel time estimation model which is confined with certain time and space condition. It considers the information including entire city and complete month. In our model, the travel time estimation achieves 17.28% MAPE. Thus, this is the foundation of our route finding model (RFM). We conduct reinforcement learning (RL) as our structure of RFM, which considered the path feature and STFM expected travel time to adjust the model during the training in network. The RFM of RL is constructed on Markov Decision Process (MDP) by considering the current state and action to finetune the policy. Moreover, our model considers the dynamic speed changing as well. In our reward function, it divides to time penalty, distance reward and arrive reward. This design expects the agent arriving the destination without losing time. Finally, we compared the strategy of our RFM, Google route API and shortest path algorithm. The case study is set in Daan district, Taipei. The origin is four different locations and randomly road in the network as destination. Our model framework has the flexibility to adjust to different users. We can easily improve further for other research questions. In advance, our RFM and Google route API consider the time feature of Friday, 2 p.m. and 6 p.m. As a result, Google routes prefer main roads, shortest path likes alley and our RFM choice between Google and shortest path. We achieve same performance as Google route in simulation and better than shortest path algorithm in terms of expected travel time. This research is conducted by relatively few resources to reach this result, compared with Google.