3D Map Exploration and Search using Topological Fourier Sparse Set

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：137

、訪客IP：3.138.174.95

姓名

呂秉憲(Bing-Xian Lu) 查詢紙本館藏

畢業系所

數學系

論文名稱

(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	★ 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 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

3D地圖探索是機器人技術中的關鍵技術之一。
然而，由於環境未知，尋找最佳的勘探路徑是一個挑戰。
這項研究提出了拓撲傅立葉稀疏集(TFSS)演算法，
使無人飛行器(UAV)能夠在理論上保證探索3D環境效能。
該演算法由Rips複合體和傅立葉稀疏集組成。
Rips複合體用於擴展子目標以進行地圖探索，
而傅立葉稀疏集用於學習子目標選擇的子模函數。
由於空間探索的目標函數被重新構造為路徑限制下的最大化子模函數，
貪婪算法可以達到(1/2)(1-e^(-1))的近似最佳值。
使用該演算法進行的實驗證明，無人機可以比基準方法探索更多環境。
此外，該演算法顯示了探索問題的持續同調性。

摘要(英)

3D map exploration is one of key technologies in robotics.
However, nding an optimal exploration path is a challenge due to unknown environments.
This research proposed the Topological Fourier Sparse Set (TFSS) algorithm to enable an unmanned aerial vehicle (UAV) to explore 3D environments with theoretical guarantees.
The algorithm consists of the Rips complex and Fourier sparse set.
The Rips complex is to expand subgoals for map exploration while the Fourier sparse set is to learn submodular functions for subgoal selection.
Since the objective function of spatial exploration is reformulated as a maximizing submodular function with path constraints,
greedy algorithms can achieve (1/2)(1-e^(-1)) of the optimum.
Experiments conducted with this algorithm demonstrates that the UAV can explore the environments more than the benchmark approaches.
Furthermore, the algorithm shows the persistence homology of exploration problems.

關鍵字(中)

★ 3D 地圖勘探
★ 壓縮感測
★ 物件搜尋

關鍵字(英)

★ 3D map exploration
★ Compressed sensing
★ Object search

論文目次

摘要 . i
Abstract. ii
Acknowledgements iii
Contents iv
Figures vi
Tables . ix
1 Introduction 1
1.1 Publication Note 5
2 Relevant Work.. 6
2.1 Map exploration 6
2.2 Learning Submodular functions 6
2.3 Probabilistic search 7
2.4 Topological motion planning . 8
3 Background. 10
3.1 Submodularity . 10
3.2 Spatial Fourier Sparse Set (SFSS) Leaning 11
3.3 ech and rips complexes 14
3.4 Hexagonal packing in Topology and Fourier domain . 15
3.5 Strength and weakness of Topological and Fourier
approaches for coverage problems . 16
4 The proposed algorithms and complex. 17
4.1 Problem formulation 17
4.2 Overview of the proposed approach 17
4.3 Topological Fourier Sparse Set algorithm . 18
4.4 Extended Rips complex 21
4.5 Strength of topological Fourier sparse set . 23
4.6 Proofs of TFSS properties . 24
5 Experiments 28
5.1 Experimental setup 28
5.2 EX1: Exploration with xed subgoals 31
5.3 EX2: Exploration with dynamic subgoals 32
5.4 Topological analysis 37
5.5 Search experiments . 40
6 CONCLUSIONS.. 42
References..44

參考文獻

[1] Héctor H. González-Baños and Jean-Claude Latombe. Navigation
strategies for exploring indoor environments. The International
Journal of Robotics Research, 21:829848, 2002.
[2] Lionel Heng, Alkis Gotovos, Andreas Krause, and Marc Pollefeys.
Ecient visual exploration and coverage with a micro aerial vehicle
in unknown environments. IEEE International Conference on
Robotics and Automation, 2015.
[3] Andreas Bircher, Mina Kamel, Kostas Alexis, Helen Oleynikova,
and Roland Siegwart. Receding horizon nextbestview planner
for 3d exploration. IEEE International Conference on Robotics and
Automation, 2016.
[4] 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):291306,
2018.
[5] George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher.
An analysis of approximations for maximizing submodular set functions.
Mathematical Programming, 14:265294, 1978.
[6] U. Feige. A threshold of ln n for approximating set cover. Journal
of the ACM, 45(4):634652, 1998.
[7] S. Khuller, A. Moss, and J. Naor. The budgeted maximum coverage
problem. Information Processing Letters, 70(1):3945, 1999.
[8] Haifeng Zhang and Yevgeniy Vorobeychik. Submodular optimization
with routing constraints. AAAI Conference on Articial Intelligence,
2016.
[9] Kuo-Shih Tseng and Bérénice Mettler. Near-optimal probabilistic
search using spatial fourier sparse set. Autonomous Robots, 2017.
[10] Kuo-Shih Tseng. Learning in human and robot search: Subgoal,
submodularity, and sparsity. University of Minnesota Ph.D. dissertation,
2016.
[11] 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), 2020.
[12] Bing-Xian Lu and Kuo-Shih Tseng. 3d map exploration using topological
fourier sparse set. Autonomous Robots, Under review.
[13] H. Durrant-Whyte and T. Bailey. Simultaneous localization and
mapping (SLAM): part i. IEEE Robotics and Automation Magazine,
13(2):99110, 2006.
[14] Steven M. LaValle and James J. Kuner Jr. Randomized kinodynamic
planning. IEEE International Conference on Robotics and
Automation, pages 473479, 1999.
[15] Cesar Cadena, Luca Carlone, Henry Carrillo, Yasir Latif, Davide
Scaramuzza, José Neira, Ian Reid, and John Leonard. Past, present,
and future of simultaneous localization and mapping: Toward the
robust-perception age. IEEE Transactions on Robotics, 32(6):1309
1332, 2016.
[16] Amarjeet Singh, Andreas Krause, and William Kaiser. Nonmyopic
adaptive informative path planning for multiple robots. International
Joint Conference on Articial Intelligence, pages 18431850,
2009.
[17] Georey Hollinger and Sanjiv Singh. Proofs and experiments in
scalable, near-optimal search by multiple robots. Robotics: Science
and Systems, pages 14261431, 2008.
[18] Kuo-Shih Tseng and Bérénice Mettler. Near-optimal probabilistic
search via submodularity and sparse regression. Autonomous
Robots, 2015.
[19] Georey Hollinger, Chiranjib Choudhuri, Urbashi Mitra, and Gaurav
S. Sukhatme. Squared error distortion metrics for motion planning
in robotic sensor networks,. in proceedings International Workshop
Wireless Networking for Unmanned Autonomous Vehicles,,
pages 14261431, 2013.
[20] Maria-Florina Balcan and Nicholas J.A. Harvey. Learning submodular
functions. Proceedings of the 43rd annual ACM symposium on
Theory of computing, 2011.
[21] Peter Stobbe and Andreas Krause. Learning fourier sparse set functions.
Proceedings of the Fifteenth International Conference on Arti
cial Intelligence and Statistics, pages 11251133, 2012.
[22] Lawrence D. Stone. The theory of optimal search. Operations Research
Society of America, 1975.
[23] Frederic Bourgault, Tomonari Furukawa, and Hough F. Durrant-
Whyte. Coordinated decentralized search for a lost target in a
bayesian world. IEEE/RSJ International Intelligent Robots and
Systems, pages 4853, 2003.
[24] Nassirou Lo, Jean Berger, and Martin Noel. Toward optimizing
static target search path planning. IEEE Symposium on Computational
Intelligence for Security and Defence Applications, pages
17, 2012.
[25] Haye Lau, Shoudong Huang, and Gamini Dissanayake. Discounted
mean bound for the optimal searcher path problem with nonuniform
travel times. European Journal of Operational Research,
190(2):383-397, 2008.
[26] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability
of persistence diagrams. Discrete and Computational Geometry,
37(1):103120, 2007.
[27] Subhrajit Bhattacharya, Robert Ghrist, and Vijay Kumar. Persistent
homology for path planning in uncertain environments. IEEE
Transactions on Robotics, 31(3):578590, 2015.
[28] Vijay Govindarajan, Subhrajit Bhattacharya, and Vijay Kumar.
Human-robot collaborative topological exploration for search and
rescue applications. Distributed Autonomous Robotic Systems,
112:1732, 2016.
[29] V. de Silva and R. Ghrist. Coordinate-free coverage in sensor networks
with controlled boundaries via homology. The International
Journal of Robotics Research, 25(12):12051222, 2006.
[30] Henry Adams and Gunnar Carlsson. Evasion paths in mobile sensor
networks. International Journal of Robotics Research, 34:90104,
2015.
[31] Jason Derenick, Vijay Kumar, and Ali Jadbabaie. Towards simplicial
coverage repair for mobile robot teams. IEEE International
Conference on Robotics and Automation, 2010.
[32] Rattanachai Ramaithitima, Michael Whitzer, Subhrajit Bhattacharya,
and Vijay Kumar. Sensor coverage robot swarms using
local sensing without metric information. IEEE International Conference
on Robotics and Automation, 2015.
[33] R.G. Baraniuk. Compressive sensing,. IEEE Signal Processing Magazine,
24(4):118121, 2007.
[34] Qaisar S., Pakistan Islamabad, R.M. Bilal, W. Iqbal, and M. Naureen.
Compressive sensing: From theory to applications, a survey.
Journal of Communications and Networks,, 15(5):443456, 2013.
[35] Mark Schmidt. Least squares optimization with l1-norm regularization.
2005.
[36] Robert Tibshirani. Regression shrinkage and selection via the lasso.
Journal of the Royal Statistical Society, Series B, 58:267288, 1996.
[37] Amir Beck and Marc Teboulle. A fast iterative shrinkagethresholding
algorithm for linear inverse problems. SIAM Journal
on Imaging Sciences, 2:183202, 2009.
[38] Emmanuel Candes, Justin Romberg, and Terence Tao. Robust uncertainty
principles: Exact signal reconstruction from highly incomplete
frequency information. IEEE Transaction on Information
Theory, 52(2):489509, 2006.
[39] Robert Ghrist. Elementary applied topology. Createspace, 2014.
[40] Yu-Chung Tsai and Kuo-Shih Tseng. Deep compressed sensing for
learning submodular functions. Sensors, 20(9):2591, 2020.
[41] Kuo-Shih Tseng and Bérénice Mettler. Human planning and coordination
in spatial search problems. 1st IFAC Conference on Cyber-
Physical and Human-Systems, 2016.
[42] Kuo-Shih Tseng and Bérénice Mettler. Analysis and augmentation
of human performance on telerobotic search problems. IEEE Access,
8:5659056606, 2020.
[43] Kuo-Shih Tseng and Bérénice Mettler. Analysis of coordination
patterns between gaze and control in human spatial search. 2nd
IFAC Conference on Cyber-Physical and Human-Systems, 2018.
[44] Bing-Xian Lu, Ji-Jie Wu, Yu-Chung Tsai, Wan-Ting Jiang, and
Kuo-Shih Tseng. A novel telerobotic search system using an unmanned
aerial vehicle. IEEE International Conference on Robotic
Computing, 2020.
[45] Markus Wulfmeier, Peter Ondruska, and Ingmar Posner. Maximum
entropy deep inverse reinforcement learning. arxiv., 2015.
[46] Markus Wulfmeier, Dominic Zeng Wang, and Ingmar Posner. Maximum
entropy deep inverse reinforcement learning. IEEE/RSJ International
Conference on Intelligent Robots and Systems, pages
21530866, 2016.

指導教授

曾國師(Kuo-Shih Tseng)

審核日期

2020-7-17

推文