Monte Carlo Tree Search with macro-actions and heuristic route planning for the Physical Travelling Salesman Problem
Monte Carlo Tree Search with macro-actions and heuristic route planning for the Physical Travelling Salesman Problem
复制标题
蒙特卡罗树搜索与宏观行动和启发式路线规划用于物理旅行推销员问题
DOI：
10.1109/cig.2012.6374161
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Powley E
中科院分区：
文献类型：
--
作者：
Powley E
针对物理旅行商问题（Physical traveling Salesman Problem, ptp），一个模拟连续实时域的路径规划和转向问题，提出了一种控制器。我们的方法是分层的，使用特定领域的算法和启发式来规划粗粒度的路线，使用蒙特卡罗树搜索（MCTS）来规划和引导细粒度的路径。MCTS组件使用宏操作来减少单位时间内要做出的决策数量，从而大大减少决策树的大小。2012年WCCI ptp竞赛的结果表明，这种方法显著且持续地优于所有其他提交的AI控制器，并且与强大的人类玩家竞争。我们的方法在移动计划和控制中的许多其他问题上都有潜在的应用，包括电子游戏。
We present a controller for the Physical Travelling Salesman Problem (PTSP), a path planning and steering problem in a simulated continuous real-time domain. Our approach is hierarchical, using domain-specific algorithms and heuristics to plan a coarse-grained route and Monte Carlo Tree Search (MCTS) to plan and steer along fine-grained paths. The MCTS component uses macro-actions to decrease the number of decisions to be made per unit of time and thus drastically reduce the size of the decision tree. Results from the 2012 WCCI PTSP Competition show that this approach significantly and consistently outperforms all other submitted AI controllers, and is competitive with strong human players. Our approach has potential applications to many other problems in movement planning and control, including video games.
登录
查看更多内容
Tron 的 UCT 代理：初步调查
DOI：
--
发表时间：
2010
期刊：
Proceedings of the 2010 IEEE Conference on Computational Intelligence and Games
影响因子：
--
作者：
Spyridon Samothrakis;David Robles;S. Lucas
通讯作者：
S. Lucas
用于同时移动游戏的蒙特卡罗树搜索：Tron 游戏中的案例研究
DOI：
--
发表时间：
2013
期刊：
影响因子：
--
作者：
Marc Lanctot;Christopher Wittlinger;M. Winands;N. D. Teuling
通讯作者：
N. D. Teuling
同步移动游戏 Tron 的蒙特卡洛树搜索
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
N. D. Teuling;M. Winands
通讯作者：
M. Winands
实体旅行商问题：WCCI 2012 竞赛
DOI：
10.1109/cec.2012.6256440
发表时间：
2012
期刊：
--
影响因子：
--
作者：
Perez D
通讯作者：
Perez D
蒙特卡罗技术和计算机围棋特刊
DOI：
--
发表时间：
2010
期刊：
IEEE Trans. Comput. Intell. AI Games
影响因子：
--
作者：
Chang;Martin Müller;O. Teytaud
通讯作者：
O. Teytaud