請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/47653
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 黃漢邦 | |
dc.contributor.author | Jou-Feng Huang | en |
dc.contributor.author | 黃柔丰 | zh_TW |
dc.date.accessioned | 2021-06-15T06:10:49Z | - |
dc.date.available | 2010-08-16 | |
dc.date.copyright | 2010-08-16 | |
dc.date.issued | 2010 | |
dc.date.submitted | 2010-08-12 | |
dc.identifier.citation | [1] M. R. Anderberg, Cluster Analysis for Applications, New York: Academic Press, 1973.
[2] L.A.A. Andersson and J. Nygards, “C-SAM: Multi-Robot SLAM Using Square Root Information Smoothing,” Proceeding of IEEE International Conference on Robotics and Automation, Pasadena, CA, USA, pp. 2798-2805, May 2008. [3] M. Boose and R. Zlot, “Map Matching and Data Association for Large-Scale Two-dimensional Laser Scan-based SLAM,” The International Journal of Robotics Research, Vol. 27, No. 6, pp. 667–691, June 2008. [4] N. Bouraqadi and A. Doniec, “Flocking-Based Multi-Robot Exploration,” in the 4th National Conference on Control Architectures of Robots, Toulouse, France, April 2009. [5] P. Brass, A. Gasparri, C. M. Flavio, and J. Xiao, “Multi-Robot Tree and Graph Exploration,” Proceeding of IEEE International Conference on Robotics and Automation, Kobe, Japan, pp. 495-500, May 2009. [6] W. Burgard, M. Moors, C. Stachniss, and F. Schneider, “Coordinated Multi-Robot Exploration,” IEEE Transactions on Robotics, Vol. 21, No. 3, pp. 376-386, June 2005. [7] W. Burgard, M. Moors, D. Fox, R. Simmons and S. Thrun, “Collaborative Multi-Robot Exploration,” Proceeding of IEEE International Conference on Robotics and Automation, San Francisco, CA, Vol. 1, pp. 476-481, April 2000. [8] T. H. Chen, “Development of the Multi-Robot Patrolling System,” Master Thesis, Department of Mechanical Engineering, National Taiwan University, July 2010. [9] S. Y. Chung and H. P. Huang, “Robot Motion Planning in Dynamic Uncertain Environments,” Advanced Robotics, To appear in 2011. [10] S. Y. Chung and H. P. Huang, “SLAMMOT-SP: Simultaneous SLAMMOT and Scene Prediction,” Advanced Robotics, Vol. 24, No. 10, pp. 979-1002, April 2010. [11] M. B. Dias and A. Stentz, “A Comparative Study between Centralized, Market-based, and Behavioral Multi-Robot Coordination Approaches,” Proceeding of IEEE/RSJ International Conference on Intelligent Robots and System, Las Vegas, USA, Vol. 3, pp. 2279-2284, October 2003. [12] E. W. Dijkstra, “A Note on Two Problems in Connection with Graphs,” Numerical Mathematics, pp. 269–271, 1959. [13] E. Ferranti, N. Trigoni, and M. Levene, “Rapid Exploration of Unknown Areas through Dynamic Deployment of Mobile and Stationary Sensor Nodes,” Autonomous Agents and Multi-Agent Systems, Vol. 19, No. 2, pp. 210-243, 2009. [14] D. Fox, “Distributed Multi-Robot Exploration and Mapping,” Proceeding of the 2nd Canadian Conference on Computer and Robot Vision, Washington, DC, USA, pp. .15-xv, May 2005. [15] A. Franchi, L. Freda, G. Oriolo, and M.Vendittelli, “The Sensor-based Random Graph Method for Cooperative Robot Exploration,” IEEE/ASME Transactions on Mechatronics, Vol. 14, No. 2, pp. 163-175, April 2009. [16] C. M. Gifford, R.Webb, J. Bley, D. Leung, M. Calnon, J. Makarewicz, B. Banz, and A. Agah, “Low-Cost Multi-Robot Exploration and Mapping,” Proceeding of IEEE International Conference on Technologies for Practical Robot Applications, Woburn, MA, USA, pp. 74-79, November 2008. [17] X. Guangming, G. Jianwei, C. Huiyan, and S. Zhibao, “Multi-Robot Exploration Based on Market Approach and Immune Optimizing Strategy,” in the 3rd International Conference on Autonomic and Autonomous Systems, Athens, USA, pp. 29, June 2007. [18] G. Gutin, A. Yeo, and A. Zverovich, “Traveling Salesman Should not be Greedy: Domination Analysis of Greedy-Type Heuristics for the TSP,” in Basic Research in Computer Science, RS-01-6, 2001. [19] A. D. Haumann, K. D. Listmann, and V. Willert, “DisCoverage: A new Paradigm for Multi-Robot Exploration,” Proceeding of IEEE International Conference on Robotics and Automation, Anchorage, Alaska, May 2010. [20] S. Huang and G. Dissanayake, “Convergence Analysis for Extended Kalman Filter Based SLAM,” Proceeding of IEEE International Conference on Robotics and Automation, Orlando, Florida, USA, pp. 412-417, May 2006. [21] D. W. Hugh and T. Bailey, “Simultaneous Localization and Mapping (SLAM): Part I The Essential Algorithms,” IEEE Robotics and Automation Magazine, Vol. 13, No. 2, pp. 99-110, 2006. [22] E. C. Juan , R. T. Gabriel, and T. P. Gregorio, “Multi-Robot Exploration and Mapping Using Self Biddings,” Proceeding of the 11th Ibero-American Conference on Artificial Intelligence, Lisbon, Portugal, pp. 392-401, October 2008. [23] E. C. Juan , R. T. Gabriel, and T. P. Gregorio, “Multi-Robot Exploration and Mapping Using Self Biddings and Stop Signals,” Proceeding of the 7th Mexican International Conference on Artificial Intelligence, Mexico City, Mexico, pp. 615-625, October 2008. [24] M. Julia´, O. Reinoso, A. Gil, M. Ballesta, and L. Paya´, “A Hybrid Solution to the Multi-Robot Integrated Exploration Problem,” Engineering Applications of Artificial Intelligence, Vol. 23, No. 4, pp. 473-486, June 2010. [25] J. Ko, B. Stewart, D.Fox, K. Konolige, and B. Limketkai, “A Practical, Decision-theoretic Approach to Multi-robot Mapping and Exploration,” Proceeding of IEEE/RSJ International Conference on Intelligent Robots and System, Las Vegas, USA, Vol. 4, pp. 3232-3238, October 2003. [26] S. Koenig, C. Tovey, and W. Halliburton, “Greedy Mapping of Terrain,” Proceeding of IEEE International Conference on Robotics and Automation, Seoul, Korea, Vol. 4, pp. 3594-3599, May 2001. [27] F. Lu and E. Milios, “Globally Consistent Range Scan Alignment for Environment Mapping,” Autonomous Robots, Vol. 4, No. 4, pp. 333-349, October 1997. [28] A. Marjovi, J. G. Nunes, L. Marques, and A. Almeida, “Multi-Robot Exploration and Fire Searching,” Proceeding of IEEE/RSJ International Conference on Intelligent Robots and System, St. Louis, MO, USA, pp. 1929-1934, October 2009. [29] P. Max, S. Bayu, and V. Arnoud, “A Scalable Hybrid Multi-Robot SLAM Method for Highly Detailed Maps,” in RoboCup 2007: Robot Soccer World Cup XI, Atlanta, GA, USA, pp. 457-464, July 2008. [30] A.K. Poernomo and S. Y. Huang, “New Cost Function for Multi-Robot Exploration,” in the 9th International Conference on Control, Automation, Robotics and Vision, Singapore, pp. 1-6, December 2006. [31] N. M. Rooker and A. Birk, “Multi-Robot Exploration Under the Constraints of Wireless Networking,” Control Engineering Practice, Vol. 15, No. 4, pp. 435-445, March 2007. [32] S. J. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 2nd Edition, Pearson Education, 2003. [33] C. X. Shi, B. R. Hong, and Y. Q. Wang, “Cooperative Exploration by Multi-Robots without Global Localization,” International Journal of Advanced Robotic Systems, Vol. 5, No. 2, pp. 129-138, June 2008. [34] R. Simmons, D. Apfelbaum, W. Burgard, D. Fox, M. Moors, S. Thrun, and H. Younes, “Coordination for Multi-Robot Exploration and Mapping,” Proceeding of the 17th National Conference on Artificial Intelligence, Austin, Texas, USA, pp. 852-858, 2000. [35] C. C. Sotzing and D. M. Lane, “Improving the Coordination Efficiency of Limited-Communication Multi-Autonomus Underwater Vehicle Operations Using a Multiagent Architecture,” Journal of Field Robotics, Vol. 27, No. 4, pp. 412-429, 2010. [36] C. Stachniss, O.M. Mozos, and W. Burgard, “Speeding-Up Multi-Robot Exploration by Considering Semantic Place Information,” Proceeding of IEEE International Conference on Robotics and Automation, Orlando, Florida, FL, USA, pp. 1692-1697, May 2006. [37] A.W. Stroupe, R. Ravichandran, and T. Balch, “Value-based Action Selection for Exploration and Dynamic Target Observation with Robot Teams,” Proceeding of IEEE International Conference on Robotics and Automation, New Orleans, LA, USA, Vol. 4, pp. 4190-4197, April 2004. [38] S. Thrun, W. Burgard, and D. Fox,” Probabilistic Robotics”, 2nd Edition, MIT, Cambridge, 2005. [39] Y. C. Tsai, “Motion Planning of a Dual-Arm Mobile Robot in Complex Environments,” Master Thesis, Department of Mechanical Engineering, National Taiwan University, June 2008. [40] A. Visser and B.A. Slamet, “Including Communication Success in the Estimation of Information Gain for Multi-Robot Exploration,” in the 6th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks and Workshops, Berlin, Germany, pp. 680-687, April 2008. [41] S. Weihua, Y. Qingyan, C. Song, and X. Ning, “Multi-Robot Area Exploration with Limited-Range Communications,” Proceeding of IEEE/RSJ International Conference on Intelligent Robots and System, Sendai, Japan, Vol. 2, pp. 1414-1419, September 2004. [42] K. M. Wurm, C. Stachniss, and W. Burgard, “Coordinated Multi-Robot Exploration Using a Segmentation of the Environment,” Proceeding of IEEE/RSJ International Conference on Intelligent Robots and Systems, Nice, France, pp. 1160-1165, September 2008. [43] M. Xin, Z. Qin, and L. Yibin, “Genetic Algorithm-Based Multi-robot Cooperative Exploration,” Proceeding of IEEE International Conference on Control and Automation, Guangzhou, China, pp. 1018-1023, May 2007. [44] B. Yamauchi, “Frontier-Based Exploration Using Multiple Robots,” Proceeding of the 2nd International Conference on Autonomous Agents, Minneapolis, MN, USA, pp. 47–53, May 1998. [45] J. Zhao, X. Su, and J. Yan, “A Novel Strategy for Distributed Multi-robot Coordination in Area Exploration,” International Conference on Measuring Technology and Mechatronics Automation, Zhangjiajie, Hunan, China, Vol. 2, pp. 24-27, April 2009. [46] R. Zlot, A. Stentz, M. B. Dias and S. Thayer, Market-Driven Multi-Robot Exploration, Academic Press, 2002. [47] R. Zlot, A. Stentz, M.B. Dias, and S. Thayer, “ Multi-Robot Exploration Controlled by a Market Economy,” Proceeding of IEEE International Conference on Robotics and Automation, Washington, DC, USA, Vol. 3, pp. 3016-3023, May 2002. [48] Wikipedia, September 2008, “Nearest neighbor algorithm,” “http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm” [49] Wikipedia, June 2010, “Travelling salesman problem,” “http://en.wikipedia.org/wiki/Travelling_salesman_problem“ [50] Plan of ancient Chang’ An city, January 2004, “http://big5.china.com.cn/zhuanti2005/txt/2004-05/08/content_5475962.htm” [51] Louvre Official Website, June 2010, “http://www.louvre.fr/llvr/informations.jsp “ [52] OpenCV wiki, June 2010, “OpenCV wiki,” “http://opencv.willowgarage.com/wiki/” [53] OpenGL official website, June 2010, “http://www.opengl.org/” [54] NVIDIA PhysX System, June 2010, “http://www.nvidia.com/object/physx_9.10.0129.html” | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/47653 | - |
dc.description.abstract | 本文主要目的在設計多機器人處於嚴苛限制通訊下的環境探索機制,由於機器人在探索過程中很少有通訊的機會,因此我們將重點放在如何增加機器人相遇的機會以避免重複探索。
首先,我們提出兩隻機器人探索機制作為多機器人探索的基礎。機器人用一些邊界性質像是邊界樹追蹤以及邊界面積,幫助了解目前探索過的環境,然後用相遇導向目標指定(Meeting-Oriented Goal Assignment, MOGA)演算法得到一個流暢的探索順序。在脫離通訊後,機器人用相遇導向邊界搜尋(Meeting-Oriented Frontier Search, MOFS)法平衡深度探索以及往約好的相遇點靠近,最後搭配一些規則幫助完成兩隻機器人環境探索機制。 然後,我們將多機器人探索簡化為兩隻一組的多組機器人探索。當機器人相遇時,每隻機器人可能狀態為Full Team (FT)、One Teamer (OT)、 Not Teamer (NT)、以及Not-Meeting Robot (NMR)。NMR的資訊追蹤以及OT的目標指定可以幫助確保同組組員相遇機率,而組別的相遇導向目標指定(MOGA for teams)可將殘餘的邊界適當的分派給FT與NT。最後,我們在MOFS中加入排斥力項以避免組與組間的重複探索。 在模擬方面,我們使用了三張地圖比較我們的探索策略和'合作(coordinated)'探索策略,並驗證出我們的策略較有效率,且即使探索環境變大,我們的探索機制依然表現優異。在實作上,我們解決了實體地圖整合與通訊問題,並將兩隻機器人用於真實環境探索。 | zh_TW |
dc.description.abstract | The main objective of this thesis is to develop a frontier-based multi-robot exploration structure with strictly limited communication. Generally, robots explore unknown areas without communication; therefore, this study aims to improve the future possibility of these robots coming into contact with one another in order to avoid overlap.
First, a two-robot exploration strategy, which is the foundation of multi-robot exploration structures, is proposed. Various frontier properties, such as frontier tree tracking and frontier area, are described to assist the robot in understanding the present situation. Then, the meeting-oriented goal assignment (MOGA) is proposed to provide smooth frontier exploration orders for the two robots. This is followed by the development of the meeting-oriented frontier search (MOFS), which is aimed to make robots determine the balance between deep exploration and meeting-point approach. Rules are also summed up to complete the two-robot exploration structure. Next, the two-robot structure is extended to a multi-robot exploration structure by dividing the robots into several two-robot groups. In a given communication process, each robot has one identity, assigned from several possibilities: Full Team (FT), One Teamer (OT), Not Teamer (NT), and Not-Meeting Robot (NMR). The NMR information tracking and the OT goal assignment are proposed to ensure possible meetings of team members. MOGA for teams is developed to assign left frontiers to FT and NT, in order for each team to identify its own goals. Finally, a rejection force term is added to the multi-robot MOFS to avoid the overlap of teams. Three maps are used in the simulation environment. The strategy is compared with the “coordinated” algorithm and better results are observed. The proposed strategy performs satisfactorily, even if the environment has become larger. A real-world two-robot exploration is also implemented after solving a number of practical problems, such as map merging and wireless communication. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T06:10:49Z (GMT). No. of bitstreams: 1 ntu-99-R97522805-1.pdf: 5851921 bytes, checksum: 93b58fb1b2e39424b9ca8018eefa056f (MD5) Previous issue date: 2010 | en |
dc.description.tableofcontents | List of Tables vii
List of Figures viii Chapter 1 Introduction 1 1.1 Related Works and Motivation 1 1.2 Objectives and Contributions 4 1.3 Thesis Organization 6 Chapter 2 Background knowledge 8 2.1 SLAM and Path Planning 9 2.1.1 Simultaneous Localization and Mapping 9 2.1.2 Heuristic Search as Path Planning 12 2.2 Frontier-based Exploration 15 2.3 Map Merging 18 Chapter 3 Two-Robot Exploration 20 3.1 Structure and Assumptions 21 3.2 Frontier Property 23 3.2.1 Frontier area detection 24 3.2.2 Frontier Tracking and State 25 3.3 Goal Assignment Method 27 3.3.1 Competition-based Goal Assignment 28 3.3.2 Meeting-Oriented Goal Assignment for Two Robots 32 3.3.3 Comparison 39 3.4 Frontier Search Algorithm 43 3.4.1 Meeting-Oriented Frontier Search 43 3.4.2 Frontier Search Parameter Property 45 3.5 Exploration Rules and Framework 48 Chapter 4 Multi-Robot Exploration 51 4.1 Structure and Term Explanation 52 4.2 Multi robot Communication Process 54 4.2.1 Not-Meeting Robot Information 58 4.2.2 One Teamer Goal Assignment 62 4.2.3 Meeting-Oriented Goal Assignment for teams 65 4.3 Multi-robot Decision Process 69 Chapter 5 Simulations and Experiments 73 5.1 Software Platform 73 5.2 Hardware Platform 75 5.3 Experiment Results 76 5.3.1 Map Chang’ An 76 5.3.2 Map Louvre 83 5.3.3 Map Large Chang’ An 88 5.3.4 Real-world Implementation 94 5.3.5 Application to Patrolling 97 Chapter 6 Conclusions and Future Works 100 6.1 Conclusions 100 6.2 Future Works 102 References 104 | |
dc.language.iso | en | |
dc.title | 嚴苛限制通訊下多機器人環境探索 | zh_TW |
dc.title | Multi-Robot Exploration with Strictly Limited Communication | en |
dc.type | Thesis | |
dc.date.schoolyear | 98-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 王傑智,周瑞仁 | |
dc.subject.keyword | 多機器人探索,相遇導向目標指定法,相遇導向邊界搜尋法, | zh_TW |
dc.subject.keyword | Multi-Robot Exploration, Meet-Oriented Goal Assignment,Meet-Oriented Frontier Search, | en |
dc.relation.page | 110 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2010-08-13 | |
dc.contributor.author-college | 工學院 | zh_TW |
dc.contributor.author-dept | 機械工程學研究所 | zh_TW |
顯示於系所單位: | 機械工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 5.71 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。