English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  Items with full text/Total items : 109952/140891 (78%)
Visitors : 46236394      Online Users : 955
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    政大機構典藏 > 資訊學院 > 資訊科學系 > 學位論文 >  Item 140.119/147025
    Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/147025


    Title: 受時序空間資訊變動影響之停車機率預測與路線搜尋
    Parking Space Probability Prediction and Route Planning Affected by Spatio-Temporal Information Fluctuation
    Authors: 葉冠宏
    YEH, KUAN-HUNG
    Contributors: 張宏慶
    CHANG, HUNG-CHIN
    葉冠宏
    YEH, KUAN-HUNG
    Keywords: 停車位搜尋
    深度強化學習
    時空圖神經網路
    Parking Space Searching
    Reinforcement Learning
    Spatio-Temporal Graph Neural Network
    Date: 2023
    Issue Date: 2023-09-01 15:22:48 (UTC+8)
    Abstract: 隨著城市內的購車人口越來越多,停車位搜尋的需求也隨之提高。然而,由於城市空
    間有限,因此距離自己最近的停車格不見得隨時都會有空位。近年來,有許多應用程
    式可以雲端地提供駕駛人各地停車位空位的資訊,以供其作參考。也有許多研究是聚
    焦在如何利用過往停車格變化的資訊來去用模型預測未來每個時間點的停車空位數。
    然而,這些資訊往往並未考量到駕駛人驅車前往中間所需付出的距離、時間差距等等
    情況,因此我們無法有效地結合所預測機率的時間點和抵達所需時間等因素。在駕駛
    人前往某個停車格的路途當中,有可能因為過程中會有塞車、或是距離遙遠等情況而
    造成抵達目的地停車格時,機率已經有所變化。除此之外,近年來,也有一些研究是
    利用道路本身所記載的過往資訊,結合相關的啟發式演算法或是強化學習演算法去提
    供代理人搜尋停車位的路線建議。然而,這些研究仍然未考量到代理人與停車格目的
    地之間的距離關係,抵達目的地前所需的時間等,也並未考量到停車格空位的機率變
    化,還有代理人與周邊各個停車格之間的地理拓樸關係。因此,本研究的貢獻在於如
    何同時整合並考量這些因素,並設計出一個好的效用函數,使模型做出訓練,提供代
    理人一個好的路線建議,以最快的時間找尋到停車位。
    在本研究的實驗中,我比較了深度強化學習模型 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.
    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。
    Description: 碩士
    國立政治大學
    資訊科學系
    108753208
    Source URI: http://thesis.lib.nccu.edu.tw/record/#G0108753208
    Data Type: thesis
    Appears in Collections:[資訊科學系] 學位論文

    Files in This Item:

    File Description SizeFormat
    320801.pdf4320KbAdobe PDF20View/Open


    All items in 政大典藏 are protected by copyright, with all rights reserved.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,惟仍請適度,合理使用本網站之內容,以尊重著作權人之權益。商業上之利用,則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作,已盡力防止侵害著作權人之權益,如仍發現本網站之數位內容有侵害著作權人權益情事者,請權利人通知本網站維護人員(nccur@nccu.edu.tw),維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback