• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computational Intelligence and AI in Games, IEEE Transactions on >Solving the Physical Traveling Salesman Problem: Tree Search and Macro Actions
【24h】

Solving the Physical Traveling Salesman Problem: Tree Search and Macro Actions

机译：解决实际的旅行推销员问题：树搜索和宏动作

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper presents a number of approaches for solving a real-time game consisting of a ship that must visit a number of waypoints scattered around a 2-D maze full of obstacles. The game, the Physical Traveling Salesman Problem (PTSP), which featured in two IEEE conference competitions during 2012, provides a good balance between long-term planning (finding the optimal sequence of waypoints to visit), and short-term planning (driving the ship in the maze). This paper focuses on the algorithm that won both PTSP competitions: it takes advantage of the physics of the game to calculate the optimal order of waypoints, and it employs Monte Carlo tree search (MCTS) to drive the ship. The algorithm uses repetitions of actions (macro actions) to reduce the search space for navigation. Variations of this algorithm are presented and analyzed, in order to understand the strength of each one of its constituents and to comprehend what makes such an approach the best controller found so far for the PTSP.
机译：本文提出了许多解决实时游戏的方法，其中包括一艘必须访问散布在充满障碍物的二维迷宫周围的多个航路点的船。该游戏名为“实物旅行推销员问题（PTSP）”，该游戏在2012年的两次IEEE会议竞赛中均得到了体现，该游戏在长期计划（确定访问的最佳路点顺序）和短期计划（推动旅行的船在迷宫中）。本文着重介绍在PTSP竞赛中均获胜的算法：它利用游戏的物理学原理计算出最佳的航路点顺序，并采用蒙特卡罗树搜索（MCTS）来驱动飞船。该算法使用动作重复（宏动作）来减少导航的搜索空间。提出并分析了该算法的变体，以了解其每个组成部分的强度，并了解是什么使这种方法成为迄今为止为PTSP找到的最佳控制器。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号