Maximal coverage problems with routing constraints using cross-entropy Monte Carlo tree search

Pao Te Lin, Kuo Shih Tseng

研究成果: 雜誌貢獻期刊論文同行評審

摘要

Spatial search, and environmental monitoring are key technologies in robotics. These problems can be reformulated as maximal coverage problems with routing constraints, which are NP-hard problems. The generalized cost-benefit algorithm (GCB) can solve these problems with theoretical guarantees. To achieve better performance, evolutionary algorithms (EA) boost its performance via more samples. However, it is hard to know the terminal conditions of EA to outperform GCB. To solve these problems with theoretical guarantees and terminal conditions, in this research, the cross-entropy based Monte Carlo Tree Search algorithm (CE-MCTS) is proposed. It consists of three parts: the EA for sampling the branches, the upper confidence bound policy for selections, and the estimation of distribution algorithm for simulations. The experiments demonstrate that the CE-MCTS outperforms benchmark approaches (e.g., GCB, EAMC) in spatial search problems.

原文???core.languages.en_GB???
文章編號3
期刊Autonomous Robots
48
發行號1
DOIs
出版狀態已出版 - 1月 2024

指紋

深入研究「Maximal coverage problems with routing constraints using cross-entropy Monte Carlo tree search」主題。共同形成了獨特的指紋。

引用此