Worker’s knowledge evaluation with single-player Monte Carlo tree search for a practical reentrant scheduling problem

详细信息    查看全文

• 作者：Ryota Furuoka ; Shimpei Matsumoto
• 关键词：Single ; player Monte Carlo tree search ; Reentrant scheduling problem ; IF ; THEN ; Knowledge evaluation
• 刊名：Artificial Life and Robotics
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：22
• 期：1
• 页码：130-138
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence (incl. Robotics); Computation by Abstract Devices; Control, Robotics, Mechatronics;
• 出版者：Springer Japan
• ISSN：1614-7456
• 卷排序：22

文摘

This paper shows the application results of single-player Monte Carlo tree search (SP-MCTS), an alternative of MCTS, for a practical reentrant scheduling problem addressed by our previous works. Especially in this paper, worker’s IF-THEN knowledge evaluation method with SP-MCTS is proposed. SP-MCTS is thought to be a meta-heuristic algorithm for NP-completeness problems, because SP-MCTS is applicable for any types of problems, where the problem’s state changes determinately in each discrete time. Therefore, SP-MCTS might be useful for not only perfect-information one-player games, but also other problems, as long as search spaces are describable as a tree structure, and the solution is stoppable with the termination determinably. The authors have considered that SP-MCTS is useful for obtaining/evaluating knowledge. This paper first describes the basic idea of SP-MCTS, and second shows the detail of the scheduling problem, including formulation. After, this paper examines the availability of SP-MCTS for a practical problem. Especially, the potentiality of SP-MCTS for knowledge evaluation is discussed from the experimental results.