Maximal Coverage Problems with Routing Constraints using Cross-Entropy Monte Carlo Tree Search

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：46

、訪客IP：3.23.103.203

姓名

林寶德(Pao-TE Lin) 查詢紙本館藏

畢業系所

數學系

論文名稱

(Maximal Coverage Problems with Routing Constraints using Cross-Entropy Monte Carlo Tree Search)

相關論文

★ 3D Map Exploration and Search using Topological Fourier Sparse Set	★ 次模深度壓縮感知用於空間搜尋
★ Evasion and Pursuit Games via Adaptive Submodularity	★ Learning Spatial Search and Map Exploration using Adaptive Submodular Inverse Reinforcement Learning
★ Localizing Complex Terrain for Quadruped Robots using Adaptive Submodularity	★ 使用成本效益生成樹的資訊軌跡規劃
★ Map Explorations via Dynamic Tree-Structured Graph	★ Multi-robot Search in 3D Environments using Submodularity with Matroid Intersection Constraints

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

最大覆蓋問題在路徑限制下是NP-hard問題。廣義成本收益演算法(GCB)能解決這樣的問題，並達到1/2(1-1/e)的近似最佳值。但是GCB和近似最佳解仍有有一段差距。此研究提出基於交叉熵的蒙地卡羅搜尋樹演算法 (CE-MCTS) 來解決這個問題。這個演算法包含三個部分: 演化演算法 (EA) 用於採樣分支、信賴上界策略 (UCB) 用於選擇展開和估計分布演算法 (EDA) 用於模擬。實驗證實了CE-MCTS在不同地圖及成本限制底下的效能比其他兩個演算法(GCB、EAMC)更好。

摘要(英)

The maximal coverage problems with routing constraints are NP-hard problems.
The generalized cost-benefit algorithm (GCB) is able to solve this problem with a $frac{1}{2}(1-frac{1}{e})widetilde{OPT}$ guarantee.
There is a space between the approximation optimal solution $(widetilde{OPT})$ and GCB performance.
In this research, the cross-entropy based Monte Carlo Tree Search algorithm (CE-MCTS) is proposed to solve this problem.
It consists of three parts: the evolutionary algorithm (EA) for sampling the branches, the upper confidence bound (UCB) policy for selections, and the estimation of distribution algorithm (EDA) for simulations.
The experiments demonstrate that the CE-MCTS outperforms benchmark approaches (e.g., GCB, EAMC) in different maps with various budget constraints.

關鍵字(中)

★ 次模性
★ 最大覆蓋問題
★ 交叉熵
★ 蒙地卡羅搜尋樹演算法

關鍵字(英)

★ Submodularity
★ Maximal coverage problem
★ Cross-Entropy
★ Monte-Carlo Tree Search

論文目次

摘要 ... i
Abstract.... ii
Acknowledgements.... iii
Contents .... iv
Figures.... vi
Tables .... xi
1 Introduction.... 1
1.1 Publication Note . . . . 3
2 Related work .... 4
2.1 Map exploration . . . . 4
2.2 Submodular maximization problems . . . . 5
2.3 Evolutionary algorithms . . . . 6
2.4 Cross-entropy method . . . . 6
2.5 Monte-carlo tree search . . . . 7
3 Background knowledge .... 8
3.1 Submodularity . . . . 8
3.2 CEM . . . . . 9
3.3 MCTS . . . . 11
4 Problem formulation.... 14
4.1 CE-MCTS . . . . 14
4.2 Denitions, theorems, and lemmas . . . . 17
4.3 Terminal conditions of CE-MCTS . . . . 20
5 Proposed algorithms.... 23
6 Experiments.... 26
6.1 Experiment setup . . . . 26
6.2 EX1: 2D coverage maximization . . . . 30
6.3 EX2: search problem . . . . 32
6.4 EX3: the feasibility of terminal criterion . . . . 32
7 Conclusions and future work .... 45
References .... 46

參考文獻

[1] Bing-Xian Lu and Kuo-Shih Tseng. 3d map exploration via learning submodular functions in the fourier domain. International Conference on Unmanned Aircraft Systems (ICUAS), pages 1199-1205, 2020.
[2] Kuo-Shih Tseng and Bérénice Mettler. Near-optimal probabilistic search via submodularity and sparse regression. Autonomous Robots, 41(1):205-229, 2017.
[3] Kuo-Shih Tseng and Bérénice Mettler. Near-optimal probabilistic search using spatial fourier sparse set. Autonomous Robots, 42(2):329-351, 2018.
[4] Pablo Lanillos, Eva Besada-Portas, Gonzalo Pajares, and José J Ruz. Minimum time search for lost targets using cross entropy optimization. IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 602-609, 2012.
[5] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functionsi. Mathematical programming, 14(1):265-294, 1978.
[6] Tal Grossman and Avishai Wool. Computational experience with approximation algorithms for the set covering problem. European journal of operational research, 101(1):81-92, 1997.
[7] Shen Lin and Brian W Kernighan. An eective heuristic algorithm for the traveling-salesman problem. Operations research, 21(2):498-516, 1973.
[8] Haifeng Zhang and Yevgeniy Vorobeychik. Submodular optimization with routing constraints. Proceedings of the AAAI Conference on Articial Intelligence, 30(1):819-825, 2016.
[9] Chao Bian, Chao Feng, Chao Qian, and Yang Yu. An ecient
evolutionary algorithm for subset selection with general cost constraints. Proceedings of the AAAI Conference on Articial Intelligence, 34(4):3267-3274, 2020.
[10] Reuven Rubinstein. The cross-entropy method for combinatorial and continuous optimization. Methodology and computing in applied probability, 1(2):127-190, 1999.
[11] Benjamin Doerr and Frank Neumann. A survey on recent progress in the theory of evolutionary algorithms for discrete optimization. ACM Transactions on Evolutionary Learning and Optimization, 1(4):1-43, 2021.
[12] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484-489, 2016.
[13] Pao-Te Lin and Kuo-Shih Tseng. Maximal Coverage Problems with Routing Constraints using Cross-Entropy Monte Carlo Tree Search. Autonomous Robots (AURO), under review.
[14] Brian Yamauchi. A frontier-based approach for autonomous exploration. IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA), pages 146-151, 1997.
[15] Di Deng, Zhefan Xu, Wenbo Zhao, and Kenji Shimada. Frontierbased automatic-dierentiable information gain measure for robotic exploration of unknown 3d environments. arXiv preprint arXiv:2011.05288, 2020.
[16] Di Deng, Runlin Duan, Jiahong Liu, Kuangjie Sheng, and Kenji Shimada. Robotic exploration of unknown 2d environment using a frontier-based automatic-dierentiable information gain measure. IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM), pages 1497-1503, 2020.
[17] Boyu Zhou, Yichen Zhang, Xinyi Chen, and Shaojie Shen. Fuel: Fast uav exploration using incremental frontier structure and hierarchical planning. IEEE Robotics and Automation Letters, 6(2):779-786, 2021.
[18] Titus Cieslewski, Elia Kaufmann, and Davide Scaramuzza. Rapid exploration with multi-rotors: A frontier selection method for high speed ight. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 2135-2142, 2017.
[19] Hassan Umari and Shayok Mukhopadhyay. Autonomous robotic
exploration based on multiple rapidly-exploring randomized trees. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1396-1402, 2017.
[20] Matteo Luperto, Michele Antonazzi, Francesco Amigoni, and N Alberto Borghese. Robot exploration of indoor environments using incomplete and inaccurate prior knowledge. Robotics and Autonomous Systems, 133, 2020.
[21] Cl Connolly. The determination of next best views. IEEE International Conference on Robotics and Automation, 2:432-435, 1985.
[22] Francesco Amigoni and Alessandro Gallo. A multi-objective exploration strategy for mobile robots. IEEE International Conference on Robotics and Automation, pages 3850-3855, 2005.
[23] Héctor H González-Banos and Jean-Claude Latombe. Navigation strategies for exploring indoor environments. The International Journal of Robotics Research, 21(10-11):829-848, 2002.
[24] Andreas Bircher, Mina Kamel, Kostas Alexis, Helen Oleynikova, and Roland Siegwart. Receding horizon" next-best-view" planner for 3d exploration. IEEE International Conference on Robotics and Automation (ICRA), pages 1462-1468, 2016.
[25] Andreas Bircher, Mina Kamel, Kostas Alexis, Helen Oleynikova, and Roland Siegwart. Receding horizon path planning for 3d exploration and surface inspection. Autonomous Robots, 42(2):291-306, 2018.
[26] Samir Khuller, Anna Moss, and Joseph Se Naor. The budgeted maximum coverage problem. Information processing letters, 70(1):39-45, 1999.
[27] Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41-43, 2004.
[28] Marshall L Fisher, George L Nemhauser, and Laurence A Wolsey. An analysis of approximations for maximizing submodular set functionsii. Polyhedral combinatorics, pages 73-87, 1978.
[29] Uriel Feige. A threshold of ln n for approximating set cover. Journal of Applied and Computational Mechanics (JACM), 45(4):634-652, 1998.
[30] Andreas Krause and Carlos Guestrin. A note on the budgeted maximization of submodular functions. 2005.
[31] Micah Corah and Nathan Michael. Distributed matroid-constrained submodular maximization for multi-robot exploration: Theory and practice. Autonomous Robots, 43(2):485-501, 2019.
[32] Andreas Krause and Carlos Guestrin. Near-optimal observation selection using submodular functions. Conference on Articial Intelligence (AAAI) Nectar track, 7:1650-1654, 2007.
[33] Andreas Krause, Carlos Guestrin, Anupam Gupta, and Jon Kleinberg. Near-optimal sensor placements: Maximizing information while minimizing communication cost. Proceedings of the 5th international conference on Information processing in sensor networks, pages 2-10, 2006.
[34] Amarjeet Singh, Andreas Krause, Carlos Guestrin, William J Kaiser, and Maxim A Batalin. Ecient planning of informative
paths for multiple robots. International Joint Conference on Arti-cial Intelligence (IJCAI), pages 2204-2211, 2006.
[35] Oliver Brock, Je Trinkle, and Fabio Ramos. Proofs and experiments in scalable, near-optimal search by multiple robots. Robotics: Science and Systems IV, pages 206-213, 2009.
[36] Peter Stobbe and Andreas Krause. Learning fourier sparse set functions. Articial Intelligence and Statistics, pages 1125-1133, 2012.
[37] Tobias Friedrich and Frank Neumann. Maximizing submodular functions under matroid constraints by evolutionary algorithms. Evolutionary computation, 23(4):543-558, 2015.
[38] Chao Qian, Jing-Cheng Shi, Yang Yu, and Ke Tang. On subset selection with general cost constraints. International Joint Conference on Articial Intelligence, 17:2613-2619, 2017.
[39] Chao Qian, Yang Yu, and Zhi-Hua Zhou. Subset selection by pareto optimization. In Advances in Neural Information Processing Systems, pages 1774-1782, 2015.
[40] Vahid Roostapour, Aneta Neumann, Frank Neumann, and Tobias Friedrich. Pareto optimization for subset selection with dynamic cost constraints. Proceedings of the AAAI Conference on Articial Intelligence, 33(01):2354-2361, 2019.
[41] Pieter-Tjerk De Boer, Dirk P Kroese, Shie Mannor, and Reuven Y Rubinstein. A tutorial on the cross-entropy method. Annals of operations research, 134(1):19-67, 2005.
[42] Andre Costa, Owen Dafydd Jones, and Dirk Kroese. Convergence properties of the cross-entropy method for discrete optimization. Operations Research Letters, 35(5):573-580, 2007.
[43] MJB Guillaume, Mark HM Winands, István Szita, and H Jaap
van den Herik. Cross-entropy for monte-carlo tree search. International Computer Games Association, 31(3):145-156, 2008.
[44] Pierre-Arnaud Coquelin and Rémi Munos. Bandit algorithms for tree search. arXiv preprint cs/0703062, 2007.
[45] Guillaume Chaslot, Sander Bakkes, Istvan Szita, and Pieter Spronck. Monte-carlo tree search: A new framework for game ai. Proceedings of the AAAI Conference on Articial Intelligence and Interactive Digital Entertainment, 4(1):216-217, 2008.
[46] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
[47] Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. European conference on machine learning, pages 282-293, 2006.
[48] Maarten PD Schadd, Mark HM Winands, Mandy JW Tak, and
Jos WHM Uiterwijk. Single-player monte-carlo tree search for
samegame. Knowledge-Based Systems, 34:311, 2012.
[49] Thomas M Moerland, Joost Broekens, Aske Plaat, and Catholijn M Jonker. The second type of uncertainty in monte carlo tree search. arXiv preprint arXiv:2005.09645, 2020.
[50] Chenjun Xiao, Ruitong Huang, Jincheng Mei, Dale Schuurmans, and Martin Müller. Maximum entropy monte-carlo planning. In Advances in Neural Information Processing Systems, 32:9520-9528, 2019.
[51] Steven James, George Konidaris, and Benjamin Rosman. An analysis of monte carlo tree search. AAAI Conference on Articial Intelligence, pages 3576-3582, 2017.
[52] Rémi Coulom. Ecient selectivity and backup operators in montecarlo tree search. International conference on computers and games, pages 72-83, 2006.
[53] Michele Conforti and Gérard Cornuéjols. Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discrete applied mathematics, 7(3):251-274, 1984.
[54] Kuo-Shih Tseng. Transfer learning of coverage functions via invariant properties in the fourier domain. Autonomous Robots, 45(4):519-542, 2021.

指導教授

曾國師(Kuo-Shih Tseng)

審核日期

2022-7-25

推文