針對城市計算之多路口轉向預測的推衍技術

A Deriving Technique for Multiple Crossroads Turn Prediction for Urban Computing

劉成成(Cheng-Cheng Liu)

指導教授 ： 金仲達

國立清華大學/電機資訊學院/資訊系統與應用研究所/碩士(2016年)

摘要

近年來，智慧城市的概念盛行，與之相關的研究課題豐富多彩，智慧城市管理是重要的內容之一。未來，政府需要快速有效的掌控城市規劃狀況，並對得到的不完整因素實施調整修正計劃。例如，政府在不藉助人力的前提下得知城市的道路平整狀況，並及時對不平整的路段進行修補。然而，要收集全某一路段的路面平整性，需要提前一定的距離完成預測工作並打開安裝在城市移動物體上的道路平整性測試傳感器裝置，因此要解決移動方向預測問題。解決這個問題的模型在本文叫做方向感知模型Turn Prediction Models (TPMs) 。
宏觀來看，城市的交叉路段數量繁多，如果每一個十字路口都建立一個預測模型則會影響總體的預測速度，因此，需要一個技術去精簡十字路口模型的建立數量。
本論文的目標就是通過經過某一個十字路口的歷史軌跡數據進行機器學習，從而得到相關性方程，以感知待預測方向的移動裝置的前進方向，同時驗證是否週末、是否高峰時間段以及進入路段等相關資訊對預測準確度的影響。並在此基礎上提出了模型數量壓縮技術Center-Deduced technique (CDT) ，通過外圍的模型推測中心的模型以減少模型的建立數量。

關鍵字

城市計算 ； 行動感測 ； 路徑預測 ； 機器學習 ； 預測模型推衍

並列摘要

Urban computing refers to the use of information and communication technologies (ICT) to acquire and analyze the data of an urban space in order to solve the many issues caused by rapid urbanization, such as air pollution, traffic congestion, and waste management. Besides infrastructural sensors, urban computing often relies on vehicles running on the roads to help collecting data relevant to the urban space. It is important to predict their routes so that data collection tasks can be planned in advance. As roads are joined by crossroads, the problem then becomes that of predicting the turns of vehicles on entering the crossroads. The problem is complicated by the fact that the turn prediction often has to be made several blocks ahead so that data collection tasks can be scheduled in time. A general model that predicts the turn of a vehicle on approaching a crossroad is thus needed. Furthermore, as the number of crossroads in a city is normally large, it is inefficient to build a model for each crossroad. A technique that derives the turn model of a crossroad from those of the neighboring crossroads is thus interesting and useful. In this thesis, we address the above two issues. We first propose the Turn Prediction Model (TPM), which predicts in advance the turns of vehicles on entering a crossroad using machne learning techniques and information such as route history and time of day. Based on TPM, we then propose the Center-Deduced Technique (CDT) to derive the TPM of a crossroad from the TPMs of the neighboring crossroads. In this way, we only need to build and store the TPMs for a small number of crossroads while others can be derived using CDT. Perforamnces of the proposed techniques are evaluated using real-world road traces and the results demonstrate their effectiveness.

並列關鍵字

Urban computing ； mobile sensing ； route prediction ； machine learning ； derivative prediction model

參考文獻

[1] Yu Zheng, Licia Capra, Ouri Wolfson, Hai Yang, “Urban Computing: Concepts, Methodologies, and Applications,” ACM Transaction on Intelligent Systems and Technology, 5(3), 2014.

[2] Yu Zheng, “Trajectory Data Mining: An Overview,” ACM Transactions on Intelligent Systems Technology, May 2015.

[4] T. Anagnostopoulos, C.B. Anagnostopoulos, S. Hadjiefthymiades, A. Kalousis, M. Kyriakakos, “Path Prediction through Data Mining,” Proc. of International Conference on Pervasive Services, pp. 128-135, 2007.

[5] M. Kyriakakos, N. Frangiadakis, S. Hadjiefthymiades, L. Merakos, “RMPG: A Realistic Mobility Pattern Generator for the Performance Assessment of Mobility Functions,” Simulation Modelling Practice and Theory, 12, 2004.

[8] Jing Yuan,Yu Zheng, Xing Xie, Guangzhong Sun, “Driving with Knowledge from the Physical World,” Proc. of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (KDD '11), 2011.