Evasion and Pursuit Games via Adaptive Submodularity

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：31

、訪客IP：18.220.1.239

姓名

趙訢(Hsin Chao) 查詢紙本館藏

畢業系所

數學系

論文名稱

(Evasion and Pursuit Games via Adaptive Submodularity)

相關論文

★ 3D Map Exploration and Search using Topological Fourier Sparse Set	★ 次模深度壓縮感知用於空間搜尋
★ Learning Spatial Search and Map Exploration using Adaptive Submodular Inverse Reinforcement Learning	★ Maximal Coverage Problems with Routing Constraints using Cross-Entropy Monte Carlo Tree Search
★ Localizing Complex Terrain for Quadruped Robots using Adaptive Submodularity	★ 使用成本效益生成樹的資訊軌跡規劃
★ Map Explorations via Dynamic Tree-Structured Graph

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

這篇論文專注於多機器人追逐單一目標的追趕問題。在已知的地
圖上，目標為最大化目標物的偵測機率。此研究提出以聚類演算法與
貪婪演算法來解決這個問題，在目標函數為次模函數的情況下，貪
婪演算法帶有理論保證值。模擬證實了提出的演算法比起另一個演算
法更好。

摘要(英)

This research focuses on pursuit-evasion(PE) games with multi-pursuer and an evader. Given the map, the objective function is to maximize the probability of the evader detection. The proposed algorithms compute search path of pursuers via cluster algorithm and greedy algorithms. Since the objective function is submodular, the algorithms have theoretical guarantees. The simulations demonstrate that the proposed method outperforms benchmark approaches.

關鍵字(中)

★ 次模性
★ 追趕問題
★ 多機器人合作,
★ 機率搜尋

關鍵字(英)

★ Submodularity
★ Pursuit-evasion games
★ Multi-robot cooperation
★ Probability search

論文目次

摘要.................................................................................................... i
Abstract.............................................................................................. ii
Contents ............................................................................................. iii
Figures ................................................................................................ iv
Tables ................................................................................................. vi
1 Introduction........................................................................ 1
2 Related work ...................................................................... 3
2.1 adaptive submodular . . . . . . . . . . . . . . . . . . 3
2.2 pursuit-evasion game . . . . . . . . . . . . . . . . . . 4
2.3 multi-robot cooperation . . . . . . . . . . . . . . . . 5
2.4 clustering . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Background knowledge ....................................................... 7
3.1 adaptive submodularity . . . . . . . . . . . . . . . . 7
3.2 clustering . . . . . . . . . . . . . . . . . . . . . . . . 10
4 Problem formulation........................................................... 13
4.1 robotic search . . . . . . . . . . . . . . . . . . . . . 13
5 Proposed algorithm ............................................................ 14
6 Experiments........................................................................ 15
6.1 Experimental setup . . . . . . . . . . . . . . . . . . 15
6.2 EX1: Search . . . . . . . . . . . . . . . . . . . . . . 15
6.2.1 simulations . . . . . . . . . . . . . . . . . . . . . . . 15
7 Conclusions and future work .............................................. 18
References........................................................................................... 19

參考文獻

[1] Timothy H Chung, Georey A Hollinger, and Volkan Isler. Search
and pursuit-evasion in mobile robotics. Autonomous robots,
31(4):299316, 2011.
[2] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher.
An analysis of approximations for maximizing submodular set
functions-i. Mathematical programming, 14(1):265294, 1978.
[3] Uriel Feige. A threshold of ln n for approximating set cover. Journal
of the ACM (JACM), 45(4):634652, 1998.
[4] Andreas Krause, Carlos Guestrin, Anupam Gupta, and Jon Kleinberg.
Near-optimal sensor placements: Maximizing information
while minimizing communication cost. In Proceedings of the 5th
international conference on Information processing in sensor net-
works, pages 210, 2006.
[5] Amarjeet Singh. Nonmyopic adaptive informative path planning for
multiple robots. 2009.
[6] Beatriz A. Asfora, Jacopo Ban, and Mark Campbell. Mixedinteger
linear programming models for multi-robot non-adversarial
search. IEEE Robotics and Automation Letters, 5(4):68056812,
2020.
[7] Haifeng Zhang and Yevgeniy Vorobeychik. Submodular optimization
with routing constraints. In Proceedings of the AAAI confer-
ence on articial intelligence, volume 30, 2016.
[8] Samir Khuller, Anna Moss, and Joseph Se Naor. The budgeted
maximum coverage problem. Information processing letters,
70(1):3945, 1999.
[9] Maxim Sviridenko. A note on maximizing a submodular set function
subject to a knapsack constraint. Operations Research Letters,
32(1):4143, 2004.
[10] Marshall L Fisher, George L Nemhauser, and Laurence A Wolsey.
An analysis of approximations for maximizing submodular set functions
ii. In Polyhedral combinatorics, pages 7387. Springer, 1978.
[11] Andreas Krause and Carlos Guestrin. Near-optimal observation
selection using submodular functions. In AAAI, volume 7, pages
16501654, 2007.
[12] Bing-Xian Lu and Kuo-Shih Tseng. 3d map exploration via learning
submodular functions in the fourier domain. In 2020 International
Conference on Unmanned Aircraft Systems (ICUAS), pages 1199
1205. IEEE, 2020.
[13] Robbert Fokkink, Thomas Lidbetter, and László A Végh. On submodular
search and machine scheduling. Mathematics of Operations
Research, 44(4):14311449, 2019.
[14] Amarjeet Singh, Andreas Krause, Carlos Guestrin, and William J
Kaiser. Ecient informative sensing using multiple robots. Journal
of Articial Intelligence Research, 34:707755, 2009.
[15] Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory
and applications in active learning and stochastic optimization.
Journal of Articial Intelligence Research, 42:427486, 2011.
[16] Adish Singla and Andreas Krause. Incentives for privacy tradeo
in community sensing. In First AAAI Conference on Human Com-
putation and Crowdsourcing, 2013.
[17] Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik, and
Patrick Lin. Scenario submodular cover. In International Workshop
on Approximation and Online Algorithms, pages 116128. Springer,
2016.
[18] Daniel Golovin and Andreas Krause. Adaptive submodular
optimization under matroid constraints. arXiv preprint
arXiv:1101.4450, 2011.
[19] Shaojie Tang. Beyond pointwise submodularity: Non-monotone
adaptive submodular maximization in linear time. Theoretical Com-
puter Science, 850:249261, 2021.
[20] Andrew Guillory and Je Bilmes. Interactive submodular set cover.
arXiv preprint arXiv:1002.3345, 2010.
[21] Shaojie Tang. Robust adaptive submodular maximization. IN-
FORMS Journal on Computing, 2022.
[22] Torrence D Parsons. Pursuit-evasion in a graph. In Theory and
applications of graphs, pages 426441. Springer, 1978.
[23] Leonidas J Guibas, Jean-Claude Latombe, Steven M LaValle, David
Lin, and Rajeev Motwani. Visibility-based pursuit-evasion in a
polygonal environment. InWorkshop on algorithms and data struc-
tures, pages 1730. Springer, 1997.
[24] Steven M LaValle, David Lin, Leonidas J Guibas, J-C Latombe, and
Rajeev Motwani. Finding an unpredictable target in a workspace
with obstacles. In Proceedings of International Conference on
Robotics and Automation, volume 1, pages 737742. IEEE, 1997.
[25] Nicholas Roy, Georey Gordon, and Sebastian Thrun. Finding approximate
pomdp solutions through belief compression. Journal of
articial intelligence research, 23:140, 2005.
[26] Hanna Kurniawati, David Hsu, and Wee Sun Lee. Sarsop: Ecient
point-based pomdp planning by approximating optimally reachable
belief spaces. In Robotics: Science and systems, volume 2008. Citeseer,
2008.
[27] Joao P Hespanha, Maria Prandini, et al. Optimal pursuit under
partial information. In In Proceedings of the 10th Mediterranean
Conference on Control and Automation, 2002.
[28] Joao P Hespanha, Maria Prandini, and Shankar Sastry. Probabilistic
pursuit-evasion games: A one-step nash approach. In Proceed-
ings of the 39th IEEE Conference on Decision and Control (Cat.
No. 00CH37187), volume 3, pages 22722277. IEEE, 2000.
[29] Lawrence D Stone. Theory of optimal search. Elsevier, 1976.
[30] Frederic Bourgault, Tomonari Furukawa, and Hugh F Durrant-
Whyte. Coordinated decentralized search for a lost target in a
bayesian world. In Proceedings 2003 IEEE/RSJ International Con-
ference on Intelligent Robots and Systems (IROS 2003)(Cat. No.
03CH37453), volume 1, pages 4853. IEEE, 2003.
[31] Rudolph Emil Kalman. A new approach to linear ltering and
prediction problems. 1960.
[32] Jun S Liu and Rong Chen. Sequential monte carlo methods for
dynamic systems. Journal of the American statistical association,
93(443):10321044, 1998.
[33] Jorge Pena Queralta, Jussi Taipalmaa, Bilge Can Pullinen, Victor
Kathan Sarker, Tuan Nguyen Gia, Hannu Tenhunen, Moncef
Gabbouj, Jenni Raitoharju, and Tomi Westerlund. Collaborative
multi-robot search and rescue: Planning, coordination, perception,
and active vision. Ieee Access, 8:191617191643, 2020.
[34] Wei Dai, Huimin Lu, Junhao Xiao, and Zhiqiang Zheng. Task
allocation without communication based on incomplete information
game theory for multi-robot systems. Journal of Intelligent
& Robotic Systems, 94(3):841856, 2019.
[35] Junyan Hu, Hanlin Niu, Joaquin Carrasco, Barry Lennox, and Farshad
Arvin. Voronoi-based multi-robot autonomous exploration
in unknown environments via deep reinforcement learning. IEEE
Transactions on Vehicular Technology, 69(12):1441314423, 2020.
[36] Siobhán Grayson. Search & rescue using multi-robot systems.
School of Computer Science and Informatics, University College
Dublin, pages 231432, 2014.
[37] Daniel S Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein.
The complexity of decentralized control of markov decision
processes. Mathematics of operations research, 27(4):819840, 2002.
[38] Jeongeun Kim and Hyoung Il Son. A voronoi diagram-based
workspace partition for weak cooperation of multi-robot system in
orchard. IEEE Access, 8:2067620686, 2020.
[39] Prithviraj Dasgupta, José Baca, KR Guruprasad, Angélica Muñoz-
Meléndez, and Janyl Jumadinova. The comrade system for multirobot
autonomous landmine detection in postconict regions. Jour-
nal of Robotics, 2015, 2015.
[40] Georey Hollinger and Sanjiv Singh. Proofs and experiments in
scalable, near-optimal search by multiple robots. Proceedings of
Robotics: Science and Systems IV, Zurich, Switzerland, 1, 2008.
[41] Nicholas Roy and Caleb Earnest. Dynamic action spaces for information
gain maximization in search and exploration. In 2006
American Control Conference. IEEE, 2006.
[42] Timothy H Chung and Joel W Burdick. Analysis of search decision
making using probabilistic search strategies. IEEE Transactions on
Robotics, 28(1):132144, 2011.
[43] Kuo-Shih Tseng and Bérénice Mettler. Near-optimal probabilistic
search via submodularity and sparse regression. Autonomous
Robots, 41(1):205229, 2017.

指導教授

曾國師(Kuo-Shih Tseng)

審核日期

2023-1-16

推文