Guided Monte Carlo Tree Search for Planning in Learned Environments

Jelle Van Eyck, Jan Ramon, Fabian Guiza, Geert MeyFroidt, Maurice Bruynooghe, Greet Van den Berghe
Proceedings of the 5th Asian Conference on Machine Learning, PMLR 29:33-47, 2013.

Abstract

Monte Carlo tree search (MCTS) is a sampling and simulation based technique for searching in large search spaces containing both decision nodes and probabilistic events. This technique has recently become popular due to its successful application to games, e.g. Poker and Go. Such games have known rules and the alternation between self-moves and non-deterministic events or opponent moves can be used to prune uninteresting branches. In this paper we study a real-world setting where the processes in the domain have a high degree of uncertainty and the need for longer-term planning implies a sequence of (planning) decisions without any intermediate feedback. Fortunately, unlike the combinatorial complexity in strategic games, many real-world environments can be approximated by efficient algorithms on a short term. This paper proposes an MCTS variant using a new type of prior information based on estimating the effects of part of the world and explores its application to the problem of hospital planning, where machine learning algorithms can be used to predict the length of stay of patients for each of the different stages of their recovery.

Cite this Paper


BibTeX
@InProceedings{pmlr-v29-Eyck13, title = {Guided Monte Carlo Tree Search for Planning in Learned Environments}, author = {Eyck, Jelle Van and Ramon, Jan and Guiza, Fabian and MeyFroidt, Geert and Bruynooghe, Maurice and Berghe, Greet Van den}, booktitle = {Proceedings of the 5th Asian Conference on Machine Learning}, pages = {33--47}, year = {2013}, editor = {Ong, Cheng Soon and Ho, Tu Bao}, volume = {29}, series = {Proceedings of Machine Learning Research}, address = {Australian National University, Canberra, Australia}, month = {13--15 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v29/Eyck13.pdf}, url = {https://proceedings.mlr.press/v29/Eyck13.html}, abstract = {Monte Carlo tree search (MCTS) is a sampling and simulation based technique for searching in large search spaces containing both decision nodes and probabilistic events. This technique has recently become popular due to its successful application to games, e.g. Poker and Go. Such games have known rules and the alternation between self-moves and non-deterministic events or opponent moves can be used to prune uninteresting branches. In this paper we study a real-world setting where the processes in the domain have a high degree of uncertainty and the need for longer-term planning implies a sequence of (planning) decisions without any intermediate feedback. Fortunately, unlike the combinatorial complexity in strategic games, many real-world environments can be approximated by efficient algorithms on a short term. This paper proposes an MCTS variant using a new type of prior information based on estimating the effects of part of the world and explores its application to the problem of hospital planning, where machine learning algorithms can be used to predict the length of stay of patients for each of the different stages of their recovery.} }
Endnote
%0 Conference Paper %T Guided Monte Carlo Tree Search for Planning in Learned Environments %A Jelle Van Eyck %A Jan Ramon %A Fabian Guiza %A Geert MeyFroidt %A Maurice Bruynooghe %A Greet Van den Berghe %B Proceedings of the 5th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Cheng Soon Ong %E Tu Bao Ho %F pmlr-v29-Eyck13 %I PMLR %P 33--47 %U https://proceedings.mlr.press/v29/Eyck13.html %V 29 %X Monte Carlo tree search (MCTS) is a sampling and simulation based technique for searching in large search spaces containing both decision nodes and probabilistic events. This technique has recently become popular due to its successful application to games, e.g. Poker and Go. Such games have known rules and the alternation between self-moves and non-deterministic events or opponent moves can be used to prune uninteresting branches. In this paper we study a real-world setting where the processes in the domain have a high degree of uncertainty and the need for longer-term planning implies a sequence of (planning) decisions without any intermediate feedback. Fortunately, unlike the combinatorial complexity in strategic games, many real-world environments can be approximated by efficient algorithms on a short term. This paper proposes an MCTS variant using a new type of prior information based on estimating the effects of part of the world and explores its application to the problem of hospital planning, where machine learning algorithms can be used to predict the length of stay of patients for each of the different stages of their recovery.
RIS
TY - CPAPER TI - Guided Monte Carlo Tree Search for Planning in Learned Environments AU - Jelle Van Eyck AU - Jan Ramon AU - Fabian Guiza AU - Geert MeyFroidt AU - Maurice Bruynooghe AU - Greet Van den Berghe BT - Proceedings of the 5th Asian Conference on Machine Learning DA - 2013/10/21 ED - Cheng Soon Ong ED - Tu Bao Ho ID - pmlr-v29-Eyck13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 29 SP - 33 EP - 47 L1 - http://proceedings.mlr.press/v29/Eyck13.pdf UR - https://proceedings.mlr.press/v29/Eyck13.html AB - Monte Carlo tree search (MCTS) is a sampling and simulation based technique for searching in large search spaces containing both decision nodes and probabilistic events. This technique has recently become popular due to its successful application to games, e.g. Poker and Go. Such games have known rules and the alternation between self-moves and non-deterministic events or opponent moves can be used to prune uninteresting branches. In this paper we study a real-world setting where the processes in the domain have a high degree of uncertainty and the need for longer-term planning implies a sequence of (planning) decisions without any intermediate feedback. Fortunately, unlike the combinatorial complexity in strategic games, many real-world environments can be approximated by efficient algorithms on a short term. This paper proposes an MCTS variant using a new type of prior information based on estimating the effects of part of the world and explores its application to the problem of hospital planning, where machine learning algorithms can be used to predict the length of stay of patients for each of the different stages of their recovery. ER -
APA
Eyck, J.V., Ramon, J., Guiza, F., MeyFroidt, G., Bruynooghe, M. & Berghe, G.V.d.. (2013). Guided Monte Carlo Tree Search for Planning in Learned Environments. Proceedings of the 5th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 29:33-47 Available from https://proceedings.mlr.press/v29/Eyck13.html.

Related Material