Reinforcement learning based Monte Carlo Tree Search for temporal path discovery

Pengfei Ding, Guanfeng Liu, Pengpeng Zhao, An Liu, Zhixu Li, Kai Zheng

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

Abstract

An Attributed Dynamic Graph (ADG) contains multiple dynamic attributes associated with each edge. In ADG based applications, people usually can specify multiple constrains in the attributes to illustrate their requirements, such as the total cost, the total travel time and the stopover interval of a flight between two cities. This inspires a type of Multi-Constrained Temporal Path (MCTP) discovery in ADGs, which is a challenging NP-Complete problem. In order to deliver an efficient and effective temporal path discovery method to be used in real-time environment, we propose a Reinforcement Learning (RL) based, Monte Carlo Tree Search algorithm (RLMCTS). RL-MCTS uses a newly designed memory structure to address the challenges of Monte Carlo Tree Search (MCTS) in MCTP discovery. To the best of our knowledge, RL-MCTS is the first RL algorithm that supports path discovery in ADGs. The experimental results on ten real dynamic graphs demonstrate that our algorithm outperforms the state-of-the-art methods in terms of both efficiency and effectiveness.
Original languageEnglish
Title of host publicationProceedings 19th IEEE International Conference on Data Mining
EditorsJianyong Wang, Kyuseok Shim, Xindong Wu
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages140-149
Number of pages10
ISBN (Electronic)9781728146041
ISBN (Print)9781728146034, 9781728146058
DOIs
Publication statusPublished - 2019
Event19th IEEE International Conference on Data Mining, ICDM 2019 - Beijing, China
Duration: 8 Nov 201911 Nov 2019

Conference

Conference19th IEEE International Conference on Data Mining, ICDM 2019
CountryChina
CityBeijing
Period8/11/1911/11/19

Keywords

  • Dynamic graph
  • Monte carlo tree
  • Path discovery

Fingerprint Dive into the research topics of 'Reinforcement learning based Monte Carlo Tree Search for temporal path discovery'. Together they form a unique fingerprint.

  • Cite this

    Ding, P., Liu, G., Zhao, P., Liu, A., Li, Z., & Zheng, K. (2019). Reinforcement learning based Monte Carlo Tree Search for temporal path discovery. In J. Wang, K. Shim, & X. Wu (Eds.), Proceedings 19th IEEE International Conference on Data Mining (pp. 140-149). Piscataway, NJ: Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/ICDM.2019.00024