1. NCCU Academic Hub
  2. 學術產出
  3. College of Informatics
  4. Theses
  5. Item

學術產出-Theses

Article View/Open

Publication Export

Google ScholarTM

政大圖書館

Citation Infomation

  • No doi shows Citation Infomation
題名 受時序空間資訊變動影響之停車機率預測與路線搜尋
Parking Space Probability Prediction and Route Planning Affected by Spatio-Temporal Information Fluctuation
作者 葉冠宏
YEH, KUAN-HUNG
貢獻者 張宏慶
CHANG, HUNG-CHIN
葉冠宏
YEH, KUAN-HUNG
關鍵詞 停車位搜尋
深度強化學習
時空圖神經網路
Parking Space Searching
Reinforcement Learning
Spatio-Temporal Graph Neural Network
日期 2023
上傳時間 1-Sep-2023 15:22:48 (UTC+8)
摘要 隨著城市內的購車人口越來越多，停車位搜尋的需求也隨之提高。然而，由於城市空
間有限，因此距離自己最近的停車格不見得隨時都會有空位。近年來，有許多應用程
式可以雲端地提供駕駛人各地停車位空位的資訊，以供其作參考。也有許多研究是聚
焦在如何利用過往停車格變化的資訊來去用模型預測未來每個時間點的停車空位數。
然而，這些資訊往往並未考量到駕駛人驅車前往中間所需付出的距離、時間差距等等
情況，因此我們無法有效地結合所預測機率的時間點和抵達所需時間等因素。在駕駛
人前往某個停車格的路途當中，有可能因為過程中會有塞車、或是距離遙遠等情況而
造成抵達目的地停車格時，機率已經有所變化。除此之外，近年來，也有一些研究是
利用道路本身所記載的過往資訊，結合相關的啟發式演算法或是強化學習演算法去提
供代理人搜尋停車位的路線建議。然而，這些研究仍然未考量到代理人與停車格目的
地之間的距離關係，抵達目的地前所需的時間等，也並未考量到停車格空位的機率變
化，還有代理人與周邊各個停車格之間的地理拓樸關係。因此，本研究的貢獻在於如
何同時整合並考量這些因素，並設計出一個好的效用函數，使模型做出訓練，提供代
理人一個好的路線建議，以最快的時間找尋到停車位。
在本研究的實驗中，我比較了深度強化學習模型 Agent57 和 DQN 在停車位搜尋問題上
的效率差異。在模型中，我加入了 ST-GNN 的神經網路架構以利獲取道路間和停車格
之間的地理拓樸關係，以及資訊時序變化。除此之外，我也設計了相關的回饋函式，
使模型能考量到代理人在抵達停車格前由於塞車、旅行距離所造成未來的機率變化。
由於實驗的資料難以取得，因此本研究以 SUMO 模擬器(Simulation of Urban MObility)，
根據所設定的環境，給予不一樣的環境車流，以測試不同模型在不同壅塞程度、不同
停車需求程度，以及在綜合或是單一的設定環境中彈性應變的能力。
As more people buying cars, the demand for searching parking space also increases. However,
due to limited resources, the nearest parking space is not always available to park.
Recently, some applications provide drivers with instant information of vacant parking space
around the city, which enables drivers to decide the direction to go by themselves. It takes time
for drivers to arrive at the parking space from the spot they search for the information. Hence,
the decision they made at the beginning may not be accurate because the environment has
changed and drivers don’t know any information about the future. Many researches have
studied on how to predict future amount of parking space by utilizing the historical data.
Nevertheless, not many of the researches have related the probabilities of the future vacant
parking space with the suggestion of driving route.
In our research, we use ST-GNN model to extract topological relationship between different
parking spaces and roads nearby from past few timestamps to predict the concerned parking
space. In order to guide the agent to find the available parking space as soon as possible, we
use reinforcement learning model to decide which direction to go. Here, we compare two
reinforcement models, Agent57 and Deep Q learning.
When the agent drives towards the destination, traffic jam would slow down the speed of
vehicle and increase time required to travel. Besides, longer distance between two spots usually
means more time spent on driving. Considering these factors, we design a proper reward
function, which takes the probabilities predicted by ST-GNN model into calculation. Therefore,
we are able to calculate the future estimated probabilities of finding vacant parking space when
vehicle arrives at the destination. The reward function is weighted by time required to travel,
and is fed into the reinforcement model.
Our contribution is to design a proper reward function and solves the problem of estimated
probability variance induced by travelling time. The model is able to provide user with advice
of finding available parking space as soon as possible. Due to the difficulty of acquiring real
world data, we conduct the experiment by SUMO (Simulation of Urban Mobility) simulator.
To test the robustness of our model, we also design different environment setting.
參考文獻 1. E. Avşar1, Y. C. Anar2, A. Ö. Polat3, “Parking lot occupancy prediction using long short-term
memory and statistical methods”, MANAS Journal of Engineering. Volume 10, Issue 1, pp. 35-
41, June 2022.
2. D. Ayala, O. Wolfson, B. Xu, B. DasGupta, J. Lin, ”Pricing of parking for congestion reduction” ,
in: Proceedings of the 20th International Conference on Advances in Geographic Information
Systems, New York, NY, USA, 2012, pp. 43–51.
3. A. P. Badia, B. Piot, S. Kapturowski, P. Sprechmann, A. Vitvitskyi, D. Guo, C. Blundell, “Agent57:
outperforming the Atari human benchmark”, arXiv:2003.13350 [cs.LG], March 2020.
4. A. P. Badia, P. Sprechmann, A. Vitvitskyi, D. Guo, B. Piot, S. Kapturowski, O. Tieleman, M.
Arjovsky, A. Pritzel, A. Bolt, C. Blundell, ” Never give up: learning directed exploration
strategies”, arXiv:2002.06038 [cs.LG], February 2020.
5. L. Bai, L. Yao, S. S. Kanhere, Z. Yang, J. Chu, X. Wang, “Passenger demand forecasting with
multi-task convolutional recurrent neural networks,” in Pacific-Asia Conference on Knowledge
Discovery and Data Mining, Springer, 2019, pp. 29–42.
6. M. Balmer, R. Weibel, H. Huang, “Value of incorporating geospatial information into the
prediction of on-street parking occupancy – a case study”, Geo-spatial Information Science,
Volume 24:3, pp. 438-457, May 2021.
7. Y. Burda, H. Edwards, A. Storkey, O. Klimov, “Exploration by random network distillation”,
arXiv:1810.12894 [cs.LG], October 2018.
8. F. Caicedo, C. Blazquez, P. Miranda, ”Prediction of parking space availability in real time”,
Expert Systems with Applications, Volume 39, Issue 8, Pages 7281-7290, June 2012.
9. D. Cao, Y. Wang, J. Duan, C. Zhang, X. Zhu, C. Huang, Y. Tong, B. Xu, J. Bai, J. Tong, Q.
Zhang, ”Spectral temporal graph neural network for multivariate time-series forecasting”, in:
Proceedings of the 34th International Conference on Neural Information Processing Systems,
Vancouver, BC, Canada, 2020, pp. 17766–17778.
10. M. Chen, ”Urban parking scheme in Hangzhou based on reinforcement learning”, in:
Proceedings of IOP Conference Series: Earth and Environmental Science, 2021.
11. C. Chen, K. Li, S. G. Teo, X. Zou, K. Wang, J. Wang, Z. Zeng, ”Gated residual recurrent graph
neural networks for traffic prediction”, in: Proceedings of the AAAI Conference on Artificial
Intelligence, Honolulu, Hawaii, USA, 2019, pp. 485-492.
123
12. K. Cho, B. V. Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, Y.
Bengio, ”Learning phrase representations using RNN encoder-decoder for statistical machine
translation”, arXiv:1406.1078 [cs.CL], September 2014.
13. H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, L. Song, ”Learning combinatorial optimization
algorithms over graphs”, in: Proceedings of the 31st International Conference on Neural
Information Processing Systems, Long Beach, California, USA, 2017, pp. 6351–6361.
14. S. Dong, M. Chen, L. Peng, H. Li, "Parking rank: a novel method of parking lots sorting and
recommendation based on public information," 2018 IEEE International Conference on
Industrial Technology (ICIT), Lyon, France, 2018, pp. 1381-1386.
15. J. Fan, Q. Hu, Z. Tang, ”Predicting vacant parking space availability: an SVR method with fruit
fly optimisation.”, IET Intelligent Transport Systems, Volume 12, Issue 10, pp. 1414–1420,
December 2018.
16. A. Garivier, E. Moulines, “On upper-confidence bound policies for non-stationary bandit
problems”, arXiv:0805.3415 [math.ST], May 2008.
17. A. Ghafelebashi, M. Razaviyayn, M. Dessouky, ” Congestion reduction via personalized
incentives”, Transportation Research Part C: Emerging Technologies, Volume 152, July 2023.
18. A. Haydari, Y. Yilmaz, “Deep reinforcement learning for intelligent transportation systems: a
survey”, arXiv:2005.00935 [cs.LG], May 2020.
19. A. Houissa, D. Barth, N. Faul, T. Mautor, "A learning algorithm to minimize the expectation
time of finding a parking place in urban area," in: Proceedings of IEEE Symposium on
Computers and Communications (ISCC), Heraklion, Greece, 2017, pp. 29-34.
20. B. T. Hung, P. Chakrabarti, ‘‘Parking lot occupancy detection using hybrid deep learning CNNLSTM approach,’’ in: Proceedings of 2nd International Conference on Artificial Intelligence:
Advances and Applications, Singapore, 2022, pp. 501–509.
21. B. Jin, Y. Zhao, J. Ni, ”Sustainable transport in a smart city: prediction of short-term parking
space through improvement of LSTM algorithm”, Applied Sciences, Volume 12, Issue 21,
October 2022.
22. Q. V. Khanh, N. V. Hoai, L. D. Manh, A. N. Le, G. Jeon, ”Wireless communication technologies
for IoT in 5G: vision, applications, and challenges.”, Wireless Communications and Mobile
Computing, Volume 2022, February 2022.
23. T. N. Kipf, M. Welling, “Semi-Supervised Classification with Graph Convolutional Networks”,
arXiv:1609.02907 [cs.LG], February 2017.
24. J. F. Kolen, S. C. Kremer, "Gradient flow in recurrent nets: the difficulty of learning long-term
dependencies," in A Field Guide to Dynamical Recurrent Networks , IEEE, 2001, pp.237-243.
124
25. V. R. Konda, J. N. Tsitsiklis, “Actor-critic algorithms”, in: Proceedings of NIPS, Denver, Colorado,
USA, 1999, pp. 1008-1014.
26. N. D. Kullman, J. E. Mendoza, M. Cousineau, J. C. Goodson, “Atari-fying the vehicle routing
problem with stochastic service requests”, arXiv:1911.05922 [cs.LG], November 2019.
27. C. Li, L. Bai, W. Liu, L. Yao, S. T. Waller, "Graph neural network for robust public transit demand
prediction," in IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 5, pp.
4086-4098, May 2022.
28. M. Lippi, M. Bertini, P. Frasconi, "Short-term traffic flow forecasting: an experimental
comparison of time-series analysis and supervised learning," in IEEE Transactions on
Intelligent Transportation Systems, vol. 14, no. 2, pp. 871-882, June 2013.
29. F. Liu, F. Hao, J. Hao, Y. Zhou, G. Xin, ”Parking prediction algorithm based on optimized LSTM
model”, Journal of Computer Applications, Volume 39 (Supply 1), pp. 65–69, 2019.
30. M. Liu, J. Naoum-Sawaya, Y. Gu, F. Lecue, R. Shorten, "A distributed markovian parking assist
system," in IEEE Transactions on Intelligent Transportation Systems, vol. 20, no. 6, pp. 2230-
2240, June 2019.
31. R. Liu, Y. Yang, D. Kwak, ”Your search path tells others where to park: towards fine-grained
parking availability crowdsourcing using parking decision models”, in: proceedings of the ACM
on Interactive, Mobile, Wearable and Ubiquitous Technologies, USA, 2017, pp 1–27.
32. R. Liu, S. Zhao, B. Cheng, H. Yang, H. Tang, F. Yang, “ST-MFM: a spatiotemporal multi-modal
fusion model for urban anomalies prediction”, in: Proceedings of the European Conference on
Artificial Intelligence, Santiago de Compostela, Spain, 2020, pp. 1-8.
33. E. H. C. Lu, C. H. Liao, ”A parking occupancy prediction approach based on spatial and temporal
analysis” in: Proceedings of ACIIDS. Cham, Switzerland, 2018, pp. 500–509.
34. V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, M. Riedmiller,
“Playing Atari with deep reinforcement learning”, arXiv:1312.5602 [cs.LG], December 2013.
35. L. Nan, L. J. Y. Flores, Y. Zhao, Y. Liu, L. Benson, W. Zou, D. Radev, “R2D2: robust data-to-text
with replacement detection”, arXiv:2205.12467 [cs.CL], May 2022.
36. Narenda, Thathachar, “Learning automata : An introduction”, Prentice, Hall, Michigan, MI,
USA, 1989, pp. 1-476.
37. I. Osband, C. Blundell, A. Pritzel, B. V. Roy, “Deep exploration via bootstrapped DQN”, in:
Proceedings of the 30th International Conference on Neural Information Processing Systems,
Barcelona, Spain, 2016, pp. 4033–4041.
38. B. Peng, J. Wang, Z. Zhang, “A deep reinforcement learning algorithm using dynamic attention
model for vehicle routing problems” In: K. Li, W. Li, H. Wang, Y. Liu, (eds.), “Artificial
125
Intelligence Algorithms and Applications. ISICA 2019. Communications in Computer and
Information Science”, vol 1205, Springer, Singapore, 2020.
39. M. L. Puterman, “Markov decision processes: discrete stochastic dynamic programming”,
Wiley-Interscience, USA, 2005.
40. C. Qiu, Y. Zhang, Z. Feng, P. Zhang, S. Cui, "Spatio-temporal wireless traffic prediction with
recurrent neural network," in IEEE Wireless Communications Letters, vol. 7, no. 4, pp. 554-
557, August 2018.
41. A. B. Reis, S. Sargento, O. K. Tonguz, "Smarter cities with parked cars as roadside units," in IEEE
Transactions on Intelligent Transportation Systems, vol. 19, no. 7, pp. 2338-2352, July 2018.
42. X. Renault, F. Kordon, J. Hugues, "Adapting models to model checkers, a case study : analysing
AADL using time or colored Petri Nets," in: Proceedings of IEEE/IFIP International Symposium
on Rapid System Prototyping, Paris, France, 2009, pp. 26-33.
43. L. Sanchez, L. Muñoz, J.A. Galache, P. Sotres, J.R. Santana, V. Gutierrez, R. Ramdhany, A.
Gluhak, S. Krco, E. Theodoridis, et al., ”Smartsantander: Iot experimentation over a smart city
testbed”, Computer Networks, Volume 61, Pages 217–238, March 2014.
44. Y. Sasaki, J. Takayama, J. R. Santana, S. Yamasaki, T. Okuno, M. Onizuka, “Predicting parking
lot availability by graph-to-sequence model: a case study with SmartSantander”,
arXiv:2206.10160 [cs.LG], June 2022.
45. M. Schneble, G. Kauermann, ”Statistical modeling of on-street parking lot occupancy in smart
cities”, arXiv:2106.06197 [stat.AP] , June 2021.
46. J. Sun, S. Kousik, D. F. Keil, M. Schwager, "Self-supervised traffic advisors: distributed, multiview traffic prediction for smart cities," in: Proceedings of IEEE 25th International Conference
on Intelligent Transportation Systems (ITSC), Macau, China, 2022, pp. 917-922.
47. H. Tavafoghia, K. Poolla, P. Varaiya, “A queuing approach to parking: modeling, verification,
and prediction”, arXiv:1908.11479. [cs.LG], August 2019.
48. P. Veliˇckovi´c, G. Cucurull, A. Casanova, A. Romero, P. Lio, Y. Bengio, ”Graph attention
networks”, arXiv:1710.10903 [stat.ML], February 2018.
49. X. Wang, Y. Ma, Y. Wang, W. Jin, X. Wang, J. Tang, C. Jia, J. Yu, “Traffic flow prediction via
spatial temporal graph neural network”, in: Proceedings of The Web Conference 2020, Taipei,
Taiwan, 2020, pp. 1082–1092.
50. Y. Wang, M. Papageorgiou, “Real-time freeway traffic state estimation based on extended
kalman filter: a general approach,” Transportation Research Part B: Methodological, vol. 39,
no. 2, pp. 141–167, February 2005.
126
51. Y. Wang, H. Yin, H. Chen, T. Wo, J. Xu, K. Zheng, “Origin-destination matrix prediction via graph
convolution: a new perspective of passenger demand modeling,” in Proceedings of the 25th
ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Anchorage,
AK, USA, 2019, pp. 1227–1235.
52. B. M. Williams, L. A. Hoel, “Modeling and forecasting vehicular traffic flow as a seasonal ARIMA
process: theoretical basis and empirical results”, Journal of Transportation Engineering,
Volume 129, Issue 6, pp. 664-672, November 2003.
53. J. Xiao, Y. Lou, J. Frisby, “How likely am I to find parking? –a practical model-based framework
for predicting parking availability”, Transportation Research Part B: Methodological, Volume
112, pp. 19-39, June 2018.
54. J. Xu, R. Rahmatizadeh, L. Bölöni and D. Turgut, "Real-time prediction of taxi demand using
recurrent neural networks," in IEEE Transactions on Intelligent Transportation Systems, vol.
19, no. 8, pp. 2572-2581, Aug. 2018.
55. B. Xu, O. Wolfson, J. Yang, L. Stenneth, P. S. Yu, P. C. Nelson, "Real-Time Street Parking
Availability Estimation," 2013 IEEE 14th International Conference on Mobile Data
Management, Milan, Italy, 2013, pp. 16-25.
56. S. Yang, W. Ma, X. Pi, S. Qian , “A deep learning approach to real-time parking occupancy
prediction in spatio-temporal networks incorporating multiple spatio-temporal data sources”,
Transportation Research Part C: Emerging Technologies. Volume 107, pp. 248-265, October
2019.
57. X. Ye, J. Wang, T. Wang, X. Yan, Q. Ye, J. Chen, "Short-term prediction of available parking
space based on machine learning approaches," in IEEE Access, vol. 8, pp. 174530-174541,
2020.
58. H. Yu, Z. Wu, S. Wang, Y. Wang, X. Ma, “Spatiotemporal recurrent convolutional networks for
traffic prediction in transportation networks,” Sensors, vol. 17, no. 7, p. 1501, June 2017.
59. B. Yu, H. Yin, Z. Zhu, ”Spatio-temporal graph convolutional networks: a deep learning
framework for traffic forecasting”, in: Proceedings of the 27th International Joint Conference
on Artificial Intelligence, Stockholm, Sweden, 2018, pp. 3634–3640.
60. C. Zeng, C. Ma, K. Wang, Z. Cui, "Parking occupancy prediction method based on multi factors
and stacked GRU-LSTM" in IEEE Access, vol. 10, pp. 47361-47370, 2022.
61. W. Zhang, ”Research on multi-step forecasting method of urban parking park multi-step
reservation strategy” M.S. thesis, Zhejiang University, Hangzhou, China, 2018.
127
62. W. Zhang, H. Liu, Y. Liu, J. Zhou, T. Xu, H. Xiong, "Semi-supervised city-wide parking availability
prediction via hierarchical recurrent graph neural network," in IEEE Transactions on
Knowledge and Data Engineering, vol. 34, no. 8, pp. 3984-3996, August 2022.
63. Jun. Zhang, S. Wang, Z. Yang, “Application technology of parking place numbers short-term
prediction based on WNN optimised by PSO and its study”, Computer applications and
software, Issue 11, pp. 66-68,138, 2015.
64. J. Zhang, Y. Zheng, D. Qi, R. Li, X. Yi, T. Li, ”Predicting citywide crowd flows using deep spatiotemporal residual networks.” , Artificial Intelligence , Volume 259, pp. 147–166, June 2018.
65. L. Zhao, Y. Song, C. Zhang, Y. Liu, P. Wang, T. Lin, M. Deng, H. Li, "T-GCN: a temporal graph
convolutional network for traffic prediction," in IEEE Transactions on Intelligent
Transportation Systems, vol. 21, no. 9, pp. 3848-3858, September 2020.
66. L. Zheng, X. Xiao, B. Sun, D. Mei, B. Peng, "Short-Term Parking Demand Prediction Method
Based on Variable Prediction Interval," in IEEE Access, vol. 8, pp. 58594-58602, February 2020.
67. “Connected vehicle technology industry Delphi study”, Center for Automotive Research (CAR),
Michigan, MI, USA, September, 2012.
68. 李俊毅，「Q-Learning 與 Deep Q-Learning 於都市路邊停車位搜尋之研究」，碩士論文，
國立政治大學資訊科學系，2022，https://hdl.handle.net/11296/2j9v22。
描述 碩士
國立政治大學
資訊科學系
108753208
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0108753208
資料類型 thesis
dc.contributor.advisor 張宏慶zh_TW
dc.contributor.advisor CHANG, HUNG-CHINen_US
dc.contributor.author (Authors) 葉冠宏zh_TW
dc.contributor.author (Authors) YEH, KUAN-HUNGen_US
dc.creator (作者) 葉冠宏zh_TW
dc.creator (作者) YEH, KUAN-HUNGen_US
dc.date (日期) 2023en_US
dc.date.accessioned 1-Sep-2023 15:22:48 (UTC+8)-
dc.date.available 1-Sep-2023 15:22:48 (UTC+8)-
dc.date.issued (上傳時間) 1-Sep-2023 15:22:48 (UTC+8)-
dc.identifier (Other Identifiers) G0108753208en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/147025-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學系zh_TW
dc.description (描述) 108753208zh_TW
dc.description.abstract (摘要) 隨著城市內的購車人口越來越多，停車位搜尋的需求也隨之提高。然而，由於城市空
間有限，因此距離自己最近的停車格不見得隨時都會有空位。近年來，有許多應用程
式可以雲端地提供駕駛人各地停車位空位的資訊，以供其作參考。也有許多研究是聚
焦在如何利用過往停車格變化的資訊來去用模型預測未來每個時間點的停車空位數。
然而，這些資訊往往並未考量到駕駛人驅車前往中間所需付出的距離、時間差距等等
情況，因此我們無法有效地結合所預測機率的時間點和抵達所需時間等因素。在駕駛
人前往某個停車格的路途當中，有可能因為過程中會有塞車、或是距離遙遠等情況而
造成抵達目的地停車格時，機率已經有所變化。除此之外，近年來，也有一些研究是
利用道路本身所記載的過往資訊，結合相關的啟發式演算法或是強化學習演算法去提
供代理人搜尋停車位的路線建議。然而，這些研究仍然未考量到代理人與停車格目的
地之間的距離關係，抵達目的地前所需的時間等，也並未考量到停車格空位的機率變
化，還有代理人與周邊各個停車格之間的地理拓樸關係。因此，本研究的貢獻在於如
何同時整合並考量這些因素，並設計出一個好的效用函數，使模型做出訓練，提供代
理人一個好的路線建議，以最快的時間找尋到停車位。
在本研究的實驗中，我比較了深度強化學習模型 Agent57 和 DQN 在停車位搜尋問題上
的效率差異。在模型中，我加入了 ST-GNN 的神經網路架構以利獲取道路間和停車格
之間的地理拓樸關係，以及資訊時序變化。除此之外，我也設計了相關的回饋函式，
使模型能考量到代理人在抵達停車格前由於塞車、旅行距離所造成未來的機率變化。
由於實驗的資料難以取得，因此本研究以 SUMO 模擬器(Simulation of Urban MObility)，
根據所設定的環境，給予不一樣的環境車流，以測試不同模型在不同壅塞程度、不同
停車需求程度，以及在綜合或是單一的設定環境中彈性應變的能力。		zh_TW
dc.description.abstract (摘要) As more people buying cars, the demand for searching parking space also increases. However,
due to limited resources, the nearest parking space is not always available to park.
Recently, some applications provide drivers with instant information of vacant parking space
around the city, which enables drivers to decide the direction to go by themselves. It takes time
for drivers to arrive at the parking space from the spot they search for the information. Hence,
the decision they made at the beginning may not be accurate because the environment has
changed and drivers don’t know any information about the future. Many researches have
studied on how to predict future amount of parking space by utilizing the historical data.
Nevertheless, not many of the researches have related the probabilities of the future vacant
parking space with the suggestion of driving route.
In our research, we use ST-GNN model to extract topological relationship between different
parking spaces and roads nearby from past few timestamps to predict the concerned parking
space. In order to guide the agent to find the available parking space as soon as possible, we
use reinforcement learning model to decide which direction to go. Here, we compare two
reinforcement models, Agent57 and Deep Q learning.
When the agent drives towards the destination, traffic jam would slow down the speed of
vehicle and increase time required to travel. Besides, longer distance between two spots usually
means more time spent on driving. Considering these factors, we design a proper reward
function, which takes the probabilities predicted by ST-GNN model into calculation. Therefore,
we are able to calculate the future estimated probabilities of finding vacant parking space when
vehicle arrives at the destination. The reward function is weighted by time required to travel,
and is fed into the reinforcement model.
Our contribution is to design a proper reward function and solves the problem of estimated
probability variance induced by travelling time. The model is able to provide user with advice
of finding available parking space as soon as possible. Due to the difficulty of acquiring real
world data, we conduct the experiment by SUMO (Simulation of Urban Mobility) simulator.
To test the robustness of our model, we also design different environment setting.		en_US
dc.description.tableofcontents 第一章 緒論 11
1.1 背景簡介 11
1.1.1 智慧城市 11
1.1.2 物聯網與停車格的搜尋 12
1.1.3 停車空位機率的預測 13
1.1.4 停車格尋找路徑的預測 20
1.1.5 LSTM 22
1.1.6 深度強化學習 22
1.1.7Deep Q Learning (DQN) 24
1.1.8 NGU 26
1.1.9 Agent57 30
1.1.10 ST-GNN 32
1.2 研究背景與動機 36
1.3 論文架構 37
第二章 相關研究 39
2.1 A Distributed Markovian Parking Assist System [30] 39
2.2 A learning algorithm to minimize the expectation time of finding a parking place in urban area [19] 42
2.3 Semi-Supervised City-Wide Parking Availability Prediction via Hierarchical Recurrent Graph Neural Network [62] 43
2.4 Spatio-Temporal Wireless Traffic Prediction With Recurrent Neural Network [40] 46
2.5 Predicting Parking Lot Availability by Graph-to-Sequence Model: A Case Study with
SmartSantander [44] 47
2.6 Q-Learning 與 Deep Q-Learning 於都市路邊停車位搜尋之研究 [68] 48
第三章 研究方法 49
3.1 相關文獻探討以及論文啟發 49
3.2 提出方法與問題分析 50
3.2.1 問題定義與系統設計 50
3.2.2 資料來源與模擬車流環境 55
3.2.3 模擬實驗與停車狀況分析 57
3.3 實驗流程 59
3.4 流程圖 62
3.5 研究方法總結 62
第四章 模擬實驗與結果分析 64
4.1 模擬實驗環境設定 64
4.2 實驗結果及分析 67
4.2.1 不同壅塞程度對於模型的影響 67
4.2.2 不同停車需求程度的環境對於模型的影響 75
4.2.3 是否使用 STGNN 模型產生回饋對於尋找停車位空格效率的影響 82
4.2.4 使用單一環境和綜合環境對於模型尋找停車空位效率的影響 96
4.2.5 在同樣的環境下，使用 Agent57 和 DQN 對於尋找停車位效率的影響 100
4.2.6 綜合結果分析 117
第五章 結論與未來研究 120
參考文獻 122		zh_TW
dc.format.extent 4424470 bytes-
dc.format.mimetype application/pdf-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0108753208en_US
dc.subject (關鍵詞) 停車位搜尋zh_TW
dc.subject (關鍵詞) 深度強化學習zh_TW
dc.subject (關鍵詞) 時空圖神經網路zh_TW
dc.subject (關鍵詞) Parking Space Searchingen_US
dc.subject (關鍵詞) Reinforcement Learningen_US
dc.subject (關鍵詞) Spatio-Temporal Graph Neural Networken_US
dc.title (題名) 受時序空間資訊變動影響之停車機率預測與路線搜尋zh_TW
dc.title (題名) Parking Space Probability Prediction and Route Planning Affected by Spatio-Temporal Information Fluctuationen_US
dc.type (資料類型) thesisen_US
dc.relation.reference (參考文獻) 1. E. Avşar1, Y. C. Anar2, A. Ö. Polat3, “Parking lot occupancy prediction using long short-term
memory and statistical methods”, MANAS Journal of Engineering. Volume 10, Issue 1, pp. 35-
41, June 2022.
2. D. Ayala, O. Wolfson, B. Xu, B. DasGupta, J. Lin, ”Pricing of parking for congestion reduction” ,
in: Proceedings of the 20th International Conference on Advances in Geographic Information
Systems, New York, NY, USA, 2012, pp. 43–51.
3. A. P. Badia, B. Piot, S. Kapturowski, P. Sprechmann, A. Vitvitskyi, D. Guo, C. Blundell, “Agent57:
outperforming the Atari human benchmark”, arXiv:2003.13350 [cs.LG], March 2020.
4. A. P. Badia, P. Sprechmann, A. Vitvitskyi, D. Guo, B. Piot, S. Kapturowski, O. Tieleman, M.
Arjovsky, A. Pritzel, A. Bolt, C. Blundell, ” Never give up: learning directed exploration
strategies”, arXiv:2002.06038 [cs.LG], February 2020.
5. L. Bai, L. Yao, S. S. Kanhere, Z. Yang, J. Chu, X. Wang, “Passenger demand forecasting with
multi-task convolutional recurrent neural networks,” in Pacific-Asia Conference on Knowledge
Discovery and Data Mining, Springer, 2019, pp. 29–42.
6. M. Balmer, R. Weibel, H. Huang, “Value of incorporating geospatial information into the
prediction of on-street parking occupancy – a case study”, Geo-spatial Information Science,
Volume 24:3, pp. 438-457, May 2021.
7. Y. Burda, H. Edwards, A. Storkey, O. Klimov, “Exploration by random network distillation”,
arXiv:1810.12894 [cs.LG], October 2018.
8. F. Caicedo, C. Blazquez, P. Miranda, ”Prediction of parking space availability in real time”,
Expert Systems with Applications, Volume 39, Issue 8, Pages 7281-7290, June 2012.
9. D. Cao, Y. Wang, J. Duan, C. Zhang, X. Zhu, C. Huang, Y. Tong, B. Xu, J. Bai, J. Tong, Q.
Zhang, ”Spectral temporal graph neural network for multivariate time-series forecasting”, in:
Proceedings of the 34th International Conference on Neural Information Processing Systems,
Vancouver, BC, Canada, 2020, pp. 17766–17778.
10. M. Chen, ”Urban parking scheme in Hangzhou based on reinforcement learning”, in:
Proceedings of IOP Conference Series: Earth and Environmental Science, 2021.
11. C. Chen, K. Li, S. G. Teo, X. Zou, K. Wang, J. Wang, Z. Zeng, ”Gated residual recurrent graph
neural networks for traffic prediction”, in: Proceedings of the AAAI Conference on Artificial
Intelligence, Honolulu, Hawaii, USA, 2019, pp. 485-492.
123
12. K. Cho, B. V. Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, Y.
Bengio, ”Learning phrase representations using RNN encoder-decoder for statistical machine
translation”, arXiv:1406.1078 [cs.CL], September 2014.
13. H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, L. Song, ”Learning combinatorial optimization
algorithms over graphs”, in: Proceedings of the 31st International Conference on Neural
Information Processing Systems, Long Beach, California, USA, 2017, pp. 6351–6361.
14. S. Dong, M. Chen, L. Peng, H. Li, "Parking rank: a novel method of parking lots sorting and
recommendation based on public information," 2018 IEEE International Conference on
Industrial Technology (ICIT), Lyon, France, 2018, pp. 1381-1386.
15. J. Fan, Q. Hu, Z. Tang, ”Predicting vacant parking space availability: an SVR method with fruit
fly optimisation.”, IET Intelligent Transport Systems, Volume 12, Issue 10, pp. 1414–1420,
December 2018.
16. A. Garivier, E. Moulines, “On upper-confidence bound policies for non-stationary bandit
problems”, arXiv:0805.3415 [math.ST], May 2008.
17. A. Ghafelebashi, M. Razaviyayn, M. Dessouky, ” Congestion reduction via personalized
incentives”, Transportation Research Part C: Emerging Technologies, Volume 152, July 2023.
18. A. Haydari, Y. Yilmaz, “Deep reinforcement learning for intelligent transportation systems: a
survey”, arXiv:2005.00935 [cs.LG], May 2020.
19. A. Houissa, D. Barth, N. Faul, T. Mautor, "A learning algorithm to minimize the expectation
time of finding a parking place in urban area," in: Proceedings of IEEE Symposium on
Computers and Communications (ISCC), Heraklion, Greece, 2017, pp. 29-34.
20. B. T. Hung, P. Chakrabarti, ‘‘Parking lot occupancy detection using hybrid deep learning CNNLSTM approach,’’ in: Proceedings of 2nd International Conference on Artificial Intelligence:
Advances and Applications, Singapore, 2022, pp. 501–509.
21. B. Jin, Y. Zhao, J. Ni, ”Sustainable transport in a smart city: prediction of short-term parking
space through improvement of LSTM algorithm”, Applied Sciences, Volume 12, Issue 21,
October 2022.
22. Q. V. Khanh, N. V. Hoai, L. D. Manh, A. N. Le, G. Jeon, ”Wireless communication technologies
for IoT in 5G: vision, applications, and challenges.”, Wireless Communications and Mobile
Computing, Volume 2022, February 2022.
23. T. N. Kipf, M. Welling, “Semi-Supervised Classification with Graph Convolutional Networks”,
arXiv:1609.02907 [cs.LG], February 2017.
24. J. F. Kolen, S. C. Kremer, "Gradient flow in recurrent nets: the difficulty of learning long-term
dependencies," in A Field Guide to Dynamical Recurrent Networks , IEEE, 2001, pp.237-243.
124
25. V. R. Konda, J. N. Tsitsiklis, “Actor-critic algorithms”, in: Proceedings of NIPS, Denver, Colorado,
USA, 1999, pp. 1008-1014.
26. N. D. Kullman, J. E. Mendoza, M. Cousineau, J. C. Goodson, “Atari-fying the vehicle routing
problem with stochastic service requests”, arXiv:1911.05922 [cs.LG], November 2019.
27. C. Li, L. Bai, W. Liu, L. Yao, S. T. Waller, "Graph neural network for robust public transit demand
prediction," in IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 5, pp.
4086-4098, May 2022.
28. M. Lippi, M. Bertini, P. Frasconi, "Short-term traffic flow forecasting: an experimental
comparison of time-series analysis and supervised learning," in IEEE Transactions on
Intelligent Transportation Systems, vol. 14, no. 2, pp. 871-882, June 2013.
29. F. Liu, F. Hao, J. Hao, Y. Zhou, G. Xin, ”Parking prediction algorithm based on optimized LSTM
model”, Journal of Computer Applications, Volume 39 (Supply 1), pp. 65–69, 2019.
30. M. Liu, J. Naoum-Sawaya, Y. Gu, F. Lecue, R. Shorten, "A distributed markovian parking assist
system," in IEEE Transactions on Intelligent Transportation Systems, vol. 20, no. 6, pp. 2230-
2240, June 2019.
31. R. Liu, Y. Yang, D. Kwak, ”Your search path tells others where to park: towards fine-grained
parking availability crowdsourcing using parking decision models”, in: proceedings of the ACM
on Interactive, Mobile, Wearable and Ubiquitous Technologies, USA, 2017, pp 1–27.
32. R. Liu, S. Zhao, B. Cheng, H. Yang, H. Tang, F. Yang, “ST-MFM: a spatiotemporal multi-modal
fusion model for urban anomalies prediction”, in: Proceedings of the European Conference on
Artificial Intelligence, Santiago de Compostela, Spain, 2020, pp. 1-8.
33. E. H. C. Lu, C. H. Liao, ”A parking occupancy prediction approach based on spatial and temporal
analysis” in: Proceedings of ACIIDS. Cham, Switzerland, 2018, pp. 500–509.
34. V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, M. Riedmiller,
“Playing Atari with deep reinforcement learning”, arXiv:1312.5602 [cs.LG], December 2013.
35. L. Nan, L. J. Y. Flores, Y. Zhao, Y. Liu, L. Benson, W. Zou, D. Radev, “R2D2: robust data-to-text
with replacement detection”, arXiv:2205.12467 [cs.CL], May 2022.
36. Narenda, Thathachar, “Learning automata : An introduction”, Prentice, Hall, Michigan, MI,
USA, 1989, pp. 1-476.
37. I. Osband, C. Blundell, A. Pritzel, B. V. Roy, “Deep exploration via bootstrapped DQN”, in:
Proceedings of the 30th International Conference on Neural Information Processing Systems,
Barcelona, Spain, 2016, pp. 4033–4041.
38. B. Peng, J. Wang, Z. Zhang, “A deep reinforcement learning algorithm using dynamic attention
model for vehicle routing problems” In: K. Li, W. Li, H. Wang, Y. Liu, (eds.), “Artificial
125
Intelligence Algorithms and Applications. ISICA 2019. Communications in Computer and
Information Science”, vol 1205, Springer, Singapore, 2020.
39. M. L. Puterman, “Markov decision processes: discrete stochastic dynamic programming”,
Wiley-Interscience, USA, 2005.
40. C. Qiu, Y. Zhang, Z. Feng, P. Zhang, S. Cui, "Spatio-temporal wireless traffic prediction with
recurrent neural network," in IEEE Wireless Communications Letters, vol. 7, no. 4, pp. 554-
557, August 2018.
41. A. B. Reis, S. Sargento, O. K. Tonguz, "Smarter cities with parked cars as roadside units," in IEEE
Transactions on Intelligent Transportation Systems, vol. 19, no. 7, pp. 2338-2352, July 2018.
42. X. Renault, F. Kordon, J. Hugues, "Adapting models to model checkers, a case study : analysing
AADL using time or colored Petri Nets," in: Proceedings of IEEE/IFIP International Symposium
on Rapid System Prototyping, Paris, France, 2009, pp. 26-33.
43. L. Sanchez, L. Muñoz, J.A. Galache, P. Sotres, J.R. Santana, V. Gutierrez, R. Ramdhany, A.
Gluhak, S. Krco, E. Theodoridis, et al., ”Smartsantander: Iot experimentation over a smart city
testbed”, Computer Networks, Volume 61, Pages 217–238, March 2014.
44. Y. Sasaki, J. Takayama, J. R. Santana, S. Yamasaki, T. Okuno, M. Onizuka, “Predicting parking
lot availability by graph-to-sequence model: a case study with SmartSantander”,
arXiv:2206.10160 [cs.LG], June 2022.
45. M. Schneble, G. Kauermann, ”Statistical modeling of on-street parking lot occupancy in smart
cities”, arXiv:2106.06197 [stat.AP] , June 2021.
46. J. Sun, S. Kousik, D. F. Keil, M. Schwager, "Self-supervised traffic advisors: distributed, multiview traffic prediction for smart cities," in: Proceedings of IEEE 25th International Conference
on Intelligent Transportation Systems (ITSC), Macau, China, 2022, pp. 917-922.
47. H. Tavafoghia, K. Poolla, P. Varaiya, “A queuing approach to parking: modeling, verification,
and prediction”, arXiv:1908.11479. [cs.LG], August 2019.
48. P. Veliˇckovi´c, G. Cucurull, A. Casanova, A. Romero, P. Lio, Y. Bengio, ”Graph attention
networks”, arXiv:1710.10903 [stat.ML], February 2018.
49. X. Wang, Y. Ma, Y. Wang, W. Jin, X. Wang, J. Tang, C. Jia, J. Yu, “Traffic flow prediction via
spatial temporal graph neural network”, in: Proceedings of The Web Conference 2020, Taipei,
Taiwan, 2020, pp. 1082–1092.
50. Y. Wang, M. Papageorgiou, “Real-time freeway traffic state estimation based on extended
kalman filter: a general approach,” Transportation Research Part B: Methodological, vol. 39,
no. 2, pp. 141–167, February 2005.
126
51. Y. Wang, H. Yin, H. Chen, T. Wo, J. Xu, K. Zheng, “Origin-destination matrix prediction via graph
convolution: a new perspective of passenger demand modeling,” in Proceedings of the 25th
ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Anchorage,
AK, USA, 2019, pp. 1227–1235.
52. B. M. Williams, L. A. Hoel, “Modeling and forecasting vehicular traffic flow as a seasonal ARIMA
process: theoretical basis and empirical results”, Journal of Transportation Engineering,
Volume 129, Issue 6, pp. 664-672, November 2003.
53. J. Xiao, Y. Lou, J. Frisby, “How likely am I to find parking? –a practical model-based framework
for predicting parking availability”, Transportation Research Part B: Methodological, Volume
112, pp. 19-39, June 2018.
54. J. Xu, R. Rahmatizadeh, L. Bölöni and D. Turgut, "Real-time prediction of taxi demand using
recurrent neural networks," in IEEE Transactions on Intelligent Transportation Systems, vol.
19, no. 8, pp. 2572-2581, Aug. 2018.
55. B. Xu, O. Wolfson, J. Yang, L. Stenneth, P. S. Yu, P. C. Nelson, "Real-Time Street Parking
Availability Estimation," 2013 IEEE 14th International Conference on Mobile Data
Management, Milan, Italy, 2013, pp. 16-25.
56. S. Yang, W. Ma, X. Pi, S. Qian , “A deep learning approach to real-time parking occupancy
prediction in spatio-temporal networks incorporating multiple spatio-temporal data sources”,
Transportation Research Part C: Emerging Technologies. Volume 107, pp. 248-265, October
2019.
57. X. Ye, J. Wang, T. Wang, X. Yan, Q. Ye, J. Chen, "Short-term prediction of available parking
space based on machine learning approaches," in IEEE Access, vol. 8, pp. 174530-174541,
2020.
58. H. Yu, Z. Wu, S. Wang, Y. Wang, X. Ma, “Spatiotemporal recurrent convolutional networks for
traffic prediction in transportation networks,” Sensors, vol. 17, no. 7, p. 1501, June 2017.
59. B. Yu, H. Yin, Z. Zhu, ”Spatio-temporal graph convolutional networks: a deep learning
framework for traffic forecasting”, in: Proceedings of the 27th International Joint Conference
on Artificial Intelligence, Stockholm, Sweden, 2018, pp. 3634–3640.
60. C. Zeng, C. Ma, K. Wang, Z. Cui, "Parking occupancy prediction method based on multi factors
and stacked GRU-LSTM" in IEEE Access, vol. 10, pp. 47361-47370, 2022.
61. W. Zhang, ”Research on multi-step forecasting method of urban parking park multi-step
reservation strategy” M.S. thesis, Zhejiang University, Hangzhou, China, 2018.
127
62. W. Zhang, H. Liu, Y. Liu, J. Zhou, T. Xu, H. Xiong, "Semi-supervised city-wide parking availability
prediction via hierarchical recurrent graph neural network," in IEEE Transactions on
Knowledge and Data Engineering, vol. 34, no. 8, pp. 3984-3996, August 2022.
63. Jun. Zhang, S. Wang, Z. Yang, “Application technology of parking place numbers short-term
prediction based on WNN optimised by PSO and its study”, Computer applications and
software, Issue 11, pp. 66-68,138, 2015.
64. J. Zhang, Y. Zheng, D. Qi, R. Li, X. Yi, T. Li, ”Predicting citywide crowd flows using deep spatiotemporal residual networks.” , Artificial Intelligence , Volume 259, pp. 147–166, June 2018.
65. L. Zhao, Y. Song, C. Zhang, Y. Liu, P. Wang, T. Lin, M. Deng, H. Li, "T-GCN: a temporal graph
convolutional network for traffic prediction," in IEEE Transactions on Intelligent
Transportation Systems, vol. 21, no. 9, pp. 3848-3858, September 2020.
66. L. Zheng, X. Xiao, B. Sun, D. Mei, B. Peng, "Short-Term Parking Demand Prediction Method
Based on Variable Prediction Interval," in IEEE Access, vol. 8, pp. 58594-58602, February 2020.
67. “Connected vehicle technology industry Delphi study”, Center for Automotive Research (CAR),
Michigan, MI, USA, September, 2012.
68. 李俊毅，「Q-Learning 與 Deep Q-Learning 於都市路邊停車位搜尋之研究」，碩士論文，
國立政治大學資訊科學系，2022，https://hdl.handle.net/11296/2j9v22。		zh_TW