@article{Kim_Lee_Lim_Kaelbling_Lozano-Perez_2020, title={Monte Carlo Tree Search in Continuous Spaces Using Voronoi Optimistic Optimization with Regret Bounds}, volume={34}, url={https://ojs.aaai.org/index.php/AAAI/article/view/6546}, DOI={10.1609/aaai.v34i06.6546}, abstractNote={<p>Many important applications, including robotics, data-center management, and process control, require planning action sequences in domains with continuous state and action spaces and discontinuous objective functions. Monte Carlo tree search (MCTS) is an effective strategy for planning in discrete action spaces. We provide a novel MCTS algorithm (<span style="font-variant: small-caps;">voot</span>) for deterministic environments with continuous action spaces, which, in turn, is based on a novel black-box function-optimization algorithm (<span style="font-variant: small-caps;">voo</span>) to efficiently sample actions. The <span style="font-variant: small-caps;">voo</span> algorithm uses Voronoi partitioning to guide sampling, and is particularly efficient in high-dimensional spaces. The <span style="font-variant: small-caps;">voot</span> algorithm has an instance of <span style="font-variant: small-caps;">voo</span> at each node in the tree. We provide regret bounds for both algorithms and demonstrate their empirical effectiveness in several high-dimensional problems including two difficult robotics planning problems.</p>}, number={06}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Kim, Beomjoon and Lee, Kyungjae and Lim, Sungbin and Kaelbling, Leslie and Lozano-Perez, Tomas}, year={2020}, month={Apr.}, pages={9916-9924} }