Monte Carlo Tree Search in Continuous Spaces Using Voronoi Optimistic Optimization with Regret Bounds
<jats: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...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Association for the Advancement of Artificial Intelligence (AAAI)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/132316 |
| _version_ | 1826191423680020480 |
|---|---|
| author | Kim, Beomjoon Lee, Kyungjae Lim, Sungbin Kaelbling, Leslie Lozano-Perez, Tomas |
| author_facet | Kim, Beomjoon Lee, Kyungjae Lim, Sungbin Kaelbling, Leslie Lozano-Perez, Tomas |
| author_sort | Kim, Beomjoon |
| collection | MIT |
| description | <jats: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 (voot) for deterministic environments with continuous action spaces, which, in turn, is based on a novel black-box function-optimization algorithm (voo) to efficiently sample actions. The voo algorithm uses Voronoi partitioning to guide sampling, and is particularly efficient in high-dimensional spaces. The voot algorithm has an instance of voo 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.</jats:p> |
| first_indexed | 2024-09-23T08:55:58Z |
| format | Article |
| id | mit-1721.1/132316 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:55:58Z |
| publishDate | 2021 |
| publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
| record_format | dspace |
| spelling | mit-1721.1/1323162021-09-21T04:01:42Z Monte Carlo Tree Search in Continuous Spaces Using Voronoi Optimistic Optimization with Regret Bounds Kim, Beomjoon Lee, Kyungjae Lim, Sungbin Kaelbling, Leslie Lozano-Perez, Tomas <jats: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 (voot) for deterministic environments with continuous action spaces, which, in turn, is based on a novel black-box function-optimization algorithm (voo) to efficiently sample actions. The voo algorithm uses Voronoi partitioning to guide sampling, and is particularly efficient in high-dimensional spaces. The voot algorithm has an instance of voo 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.</jats:p> 2021-09-20T18:21:48Z 2021-09-20T18:21:48Z 2020-12-22T18:54:11Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/132316 en 10.1609/AAAI.V34I06.6546 Proceedings of the AAAI Conference on Artificial Intelligence Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for the Advancement of Artificial Intelligence (AAAI) Other repository |
| spellingShingle | Kim, Beomjoon Lee, Kyungjae Lim, Sungbin Kaelbling, Leslie Lozano-Perez, Tomas Monte Carlo Tree Search in Continuous Spaces Using Voronoi Optimistic Optimization with Regret Bounds |
| title | Monte Carlo Tree Search in Continuous Spaces Using Voronoi Optimistic Optimization with Regret Bounds |
| title_full | Monte Carlo Tree Search in Continuous Spaces Using Voronoi Optimistic Optimization with Regret Bounds |
| title_fullStr | Monte Carlo Tree Search in Continuous Spaces Using Voronoi Optimistic Optimization with Regret Bounds |
| title_full_unstemmed | Monte Carlo Tree Search in Continuous Spaces Using Voronoi Optimistic Optimization with Regret Bounds |
| title_short | Monte Carlo Tree Search in Continuous Spaces Using Voronoi Optimistic Optimization with Regret Bounds |
| title_sort | monte carlo tree search in continuous spaces using voronoi optimistic optimization with regret bounds |
| url | https://hdl.handle.net/1721.1/132316 |
| work_keys_str_mv | AT kimbeomjoon montecarlotreesearchincontinuousspacesusingvoronoioptimisticoptimizationwithregretbounds AT leekyungjae montecarlotreesearchincontinuousspacesusingvoronoioptimisticoptimizationwithregretbounds AT limsungbin montecarlotreesearchincontinuousspacesusingvoronoioptimisticoptimizationwithregretbounds AT kaelblingleslie montecarlotreesearchincontinuousspacesusingvoronoioptimisticoptimizationwithregretbounds AT lozanopereztomas montecarlotreesearchincontinuousspacesusingvoronoioptimisticoptimizationwithregretbounds |