Dynamic Task Sequencing of Manipulator by Monte Carlo Tree Search
Yanwei Huang, Chongfeng Liu, Sufeng Hu, Zhang-Hua Fu, Yong-Quan Chen · 2018
Nowadays manipulators are widely used in logistics systems, thus being important to improve the efficiency. In this paper, we transform the task sequencing problem of manipulator into a dynamic traveling salesman problem (DTSP), and use the Monte Carlo tree search (MCTS) approach to determine the execution order of the tasks. MCTS is an effective self-learning algorithm, which consists of four phases, i.e., initialization, simulation, selection and back propagation. Furthermore, to fit the dynamic feature of real-life applications, we introduce a dynamic mechanism using the information of historically found solutions. Finally, we carry out experiments based on 30 randomly generated task sets. The results show that, compared to the most popular method which executes all the tasks in sequence, MCTS is able to save 14.37%, 15.68%, 18.10% execution time (respectively on the small-scale, mid-scale and large-scale task sets), indicating its ability in improving the efficiency of manipulator.