Freiburg, Germany
June 11-16, 2011
21st International Conference on Automated Planning and Scheduling
Freiburg

Monte-Carlo Tree Search: Theory and Applications

Recent advances in Monte-Carlo planning, a combination of low-overhead simulation with probabilistic decision making, have led to progress in applications ranging from networking to real-time strategy games. This workshop aims to bring together researchers interested in both theoretical analysis and applications of Monte-Carlo planning with the goal of creating a shared foundation for additional research in this area.

Schedule

This schedule as a PDF file.

The workshop will be held on June 12, 2011 in hall 101–00–010/014 on the computer science campus.

09:00-09:15Welcome
Keynote Speaker
09:15-10:30 Remi Munos
Hierarchical Bandits for Sequential Decision Making
Coffee Break
11:00-11:30 Zahy Bnaya, Ariel Felner, Dror Fried, Solomon Eyal Shimony and Olga Maksin
Repeated-task Canadian Traveler Problem
(pdf)
11:30-12:00 Raghuram Ramanujan, Ashish Sabharwal and Bart Selman
On the Behavior of UCT in Synthetic Search Spaces
(pdf)
12:00-12:30 John Asmuth and Michael Littman
Approaching Bayes-optimality using Monte-Carlo Tree Search
(pdf)
Lunch Break
14:00-14:30 Ashish Sabharwal and Horst Samulowitz
Guiding Combinatorial Optimization with UCT
(pdf)
14:30-14:45 Lucian Busoniu, Remi Munos, Bart De Schutter and Robert Babuska
Optimistic Planning for Sparsely Stochastic Systems
(pdf)
14:45-15:00 Lars Schaefers, Marco Platzner and Ulf Lorenz
UCT-Treesplit – Parallel MCTS on Distributed Memory
(pdf)
15:00-15:30 Poster Session
Coffee Break
16:00-16:30 Poster Session
16:30-17:30 Panel Discussion

Call for papers

MCTS planners were developed to combat the curse of dimensionality in large state spaces and appear to have a different portfolio of strengths and weaknesses compared to traditional search methods. One example of an algorithm in this class, Upper Confidence applied to Trees (UCT), is credited with providing the foundations for new human-competitive Go-playing programs.

The success in Go motivated further work on understanding the theoretical properties of MCTS algorithms. Several papers were published questioning the tractability of these approaches in the worst case, leading to new algorithms and approaches. While trivial exponential lower bounds were proved, the success of this class of methods in real applications points towards the necessity of developing a better understanding of the type of inputs for which these algorithms perform well. Such an understanding would in turn allow a better recognition of the type of applications for which MCTS algorithms would be best suited.

The goal of this workshop is to understand the techniques that led to the breakthroughs in computer Go, translate these gains into other domains and push forward the theoretical understanding of this probabilistic planning framework. The topics include (but are not limited to):

  • MCTS planning in MDPs and POMDPs.
  • MCTS planning in games (Go, RTS games etc.).
  • Exploration and exploitation in MCTS algorithms.
  • Bandit-algorithm foundations for MCTS.
  • Integration of learning and planning.
  • Representational aspects of MCTS algorithms.
  • Theoretical foundations of MCTS.
  • Open problems.
  • Innovative applications of MCTS algorithms.

Work still in-progress is welcomed to the workshop under the form of position papers (which will be candidates for short, 5 minutes talks) while full-fledged research papers will be considered for long, 20 minutes talks (see submission procedure for details).

Important Dates

  • Submission deadline: March 25, 2011
  • Author notification: April 15, 2011
  • Workshop date: June 12th, 2011

Submission Procedure

Papers should be submitted using EasyChair ( http://www.easychair.org/conferences/?conf=mcts11) in pdf format according to AAAI style specifications (see http://www.aaai.org/Publications/Author/author.php for details). The length of the papers should be 2 pages for position papers and 6 pages for research papers (including references).

Workshop Format

The workshop is a full day workshop and it will consist of an invited talk, a set of oral presentations (both short - 5 minutes, and long - 20 minutes), a poster session and a panel discussion.

Organizing Committee

Program Committee