請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/25636完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳永耀(Yung-Yaw Chen) | |
| dc.contributor.author | Chia-Lun Tien | en |
| dc.contributor.author | 田家倫 | zh_TW |
| dc.date.accessioned | 2021-06-08T06:22:23Z | - |
| dc.date.copyright | 2006-08-09 | |
| dc.date.issued | 2006 | |
| dc.date.submitted | 2006-07-30 | |
| dc.identifier.citation | [1] L. F. Lian, “Group Behavior of Biological Systems and Integration of Wireless Communication Protocol Design,” Proceedings of 2005 CACS Automatic Control Conference, Tainan, Taiwan, Nov 18-19, 2005.
[2] 李源華，”微型仿生體之氣味追蹤演算法與氣味快散環境建立”，國立台灣大學電機工程研究所。 [3] J. E. Hopcroft, R. E. Tarjan, “Dividing a Graph into Triconnected Component,” SIAM J. Comput., pp. 135-158, February (1973). [4] http://dart.stanford.edu:88/ [5] http://web.mit.edu/towtank/www/ [6] J. C. Heudin, “Artificial Life and Evolutionary Computing in Machine Perception,” IEEE Proceeding of Computer Architectures for Machine Perception, pp. 418-428, 18-20 Sep 1995.s [7] N. Forbes, “Life as it could be: Alife attempts to simulate evolution,” IEEE Intelligent Systems, Nov/Dec 2000. [8] A. Wagner, M. Lindenbaum, and A. M. Bruckstein, “Distributed covering by Ant-Robots Using Evaporating Traces,” IEEE Transactions on Robotics and Automation, VOL. 15, NO. 5, October 1999. [9] Marco Dorigo, Eric Bonabeaub, Guy Theraulaz, “Ant Algorithms and Stigmergy,” Future Generation Computer Systems, pp.851–871, 2000. [10] Marco Dorigo, Vittorio Maniezzo, and Alberto Colorni, “Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Trans. On Systems, Man, and Cyvernetics-Part B: Cybernetics, Vol. 26, NO. 1, Feb 1996. [11] Artificial Life: Selected Links & Literature, 82 http://homepages.feis.herts.ac.uk/~comqkd/Alife.htm [12] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 2nd Ed., McGraw-Hill Book Company, 2001. [13] J. B. Saxe, “Embeddability of weighted graphs in k-space is strongly NP-hard,” Proc. 17th Allerton Conference in Communications, Control and Computing, pp. 480-489, 1979. [14] B. Hendrickson, “Conditions for Unique Graph Realizations,” SIAM J. Comput., 21(1): 65-84, February 1992. [15] L. Asimow, B. Roth, “The Rigidity of Graphs,” Transaction Of the American Mathematical Society, Vol. 245, November 1978. [16] H. N. Gabow, H. H. Westermann, “Forests, Frames, and Games: Algorithms for Matroid Sums and Applications,” in Proc. 20th Annual Symposium on the Theory of Computing, Chicago, pp. 407-421, 1988. [17] H. Imai, “On Combinatorial Structures of Line Drawings of Polyhedron,” Discr. Appl. Math., pp. 79-92, October 1985. [18] K. Sugihara, “On Redundant Bracing in Plane Skeletal Structures,” Bull. Electrotech, Lab. 44, pp. 376-286, 1980. [19] Reinhard Diestel, Graph Theory, 3 Ed., Springer, 2005.rd [20] J. E. Hopcroft, R. E. Tarjan, “Dividing a Graph into Triconnected Component,” SIAM J. Comput., pp. 135-158, February (1973). [21] M. Stoer, F. Wagner, “A simple Min-Cut Algorithm,” Journal of the ACM, Vol.44, No. 4, pp. 585-591, July 1997. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/25636 | - |
| dc.description.abstract | 多群組機器人是近年來被廣泛研究的一個主題，且被應用於各種領域。如何設計多群組機器人的行為一直以來是個有趣的問題，本論文試著從觀察及模仿生物行為的角度切入，探討及設計如何使得一群只具有簡單能力的機器人能在一個未知的環境中進行搜尋任務。此類機器人可被應用在危險環境中的搜索。
本論文主要研究內容包含兩個主題，分別為個體行為和群體行為的建立，以及在有限感測及通訊能力下，多群組仿生微型機器人所能達成之預期工作目標。在個體行為建立的部份，由於所設定的是分散式多群組機器人，因此每個成員都具有相同的能力及地位，故機器人的行為皆相同，而無階級的分別。每隻機器人的行為皆分為三個模式，並以所偵測到的氣味濃度作為切換的依據。在第二部份中，本論文發展了一套合作型氣味搜尋演算法，有別於一般常見設計多群組機器人行為的方法，本演算法引進了人工生命所提及的基本概念－存在於個體之間的些許規則規範著其行為。受限於氣味場的特性，微型仿生機器人在距離氣味源較遠的地方或是有障礙物阻擋的關係，無法感測出該處的氣味濃度或濃度梯度，本演算法利用和通訊範圍內的其餘微型仿生機器人交換而得的資訊，進行鄰近微型仿生機器人分布的估測，並由此分部估測推算氣味場的梯度，並決定行進方向。 在本論文中，首先介紹仿生學在工程及科學領域的應用。其次對於設計機器人行為的過程及合作型氣味搜尋演算法有詳細的介紹。最後，呈現在不同環境條件下，模擬群體行為的結果。 | zh_TW |
| dc.description.abstract | Multi-robot systems have been an important research area in robotics and applied to various domains. Multi-robot systems can improve the efficiency of a robotic system either from the viewpoint of the performance in accomplishing certain tasks, or in the robustness and reliability of the system. A biological-inspired approach is used to design a multi-robot system. And the concepts of Artificial Life (ALife) are introduced to the developments.
The thesis consists of two parts. The first one is the development of individual robot’s and group behaviors; while the second part is the development of the proposed cooperative search algorithm for scent sources. The thesis focuses on distributed multi-robots systems. Each of the members in the system is homogeneous and only aware of its local situations. Individual robot’s behavior is composed of three modes. They switch modes according to the sensed scent concentrations. The proposed cooperative search algorithm is applied in the search mode which is one of the three. In the searching process, robots have to maintain communications with at least a mount of others. They exchange information with each other since they are only aware of small areas of their surroundings. And then they estimate the configurations of those adjacent to them in order to decide the direction for the next move. Simulations with different conditions are given in the last chapter. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-08T06:22:23Z (GMT). No. of bitstreams: 1 ntu-95-R93921082-1.pdf: 2065090 bytes, checksum: 4f93311f66ee65336872633be88bfd25 (MD5) Previous issue date: 2006 | en |
| dc.description.tableofcontents | 中文摘要...................................................i
ABSTRACT..................................................ii TABLE OF CONTENTS........................................iii LIST OF FIGURES............................................v CHAPTER 1 INTRODUCTION.....................................1 1.1 MOTIVATION.............................................1 1.2 PROBLEM STATEMENT......................................2 1.3 ORGANIZATION OF THE THESIS.............................3 CHAPTER 2 BACKGROUND.......................................5 2.1 MULTI-ROBOT SYSTEMS....................................5 2.2 BIO-MIMICRY............................................6 2.3 ARTIFICIAL LIFE........................................9 2.4 SUMMARY...............................................12 CHAPTER 3 BEHAVIOR DEVELOPMENT OF BIO-MIMETIC ROBOT.......13 3.1 INTRODUCTION..........................................13 3.2 DISPERSION MODE.......................................15 3.3 COOPERATIVE SEARCH MODE...............................22 3.4 LINE-UP MODE..........................................25 3.5 SUMMARY...............................................26 CHAPTER 4 COOPERATIVE SEARCH ALGORITHM....................29 4.1 INTRODUCTION..........................................29 4.2 GRAPH THEORY..........................................29 4.2.1 REPRESENTATIONS OF GRAPHS...........................29 4.2.2 GRAPH REALIZATION...................................31 4.2.3 GRAPH RIGIDITY AND PARTIAL REFLECTIONS..............32 4.3 SCENT DISTRIBUTION MODEL..............................39 4.4 CONFIGURATION ESTIMATION FROM LOCAL INFORMATION.......42 4.4.1 NEIGHBOR SEEKING....................................44 4.4.2 INFORMATION EXCHANGE................................46 4.4.3 CONFIGURATION DETERMINATION.........................47 4.4.4 ATTITUDE SELECTION..................................52 4.5 SUMMARY...............................................56 CHAPTER 5 SIMULATION RESULTS..............................57 5.1 CONFIGURATION ESTIMATION..............................58 5.2 FLOWING OUT MECHANISM.................................60 5.3 BEHAVIOR OF INDIVIDUAL BIO-ROBOT......................65 5.3.1 SINGLE TARGET, NO OBSTACLES.........................66 5.3.2 MULTIPLE TARGETS, NO OBSTACLES......................72 5.3.3 SINGLE TARGET, WITH OBSTACLES.......................74 5.4 SUMMARY...............................................78 CHAPTER 6 CONCLUSIONS AND FUTURE WORKS....................79 REFERENCE.................................................81 | |
| dc.language.iso | en | |
| dc.subject | 群體行為 | zh_TW |
| dc.subject | 多群組機器人 | zh_TW |
| dc.subject | 仿生學 | zh_TW |
| dc.subject | 人工生命 | zh_TW |
| dc.subject | 氣味搜尋 | zh_TW |
| dc.subject | Artificial Life | en |
| dc.subject | Scent Search | en |
| dc.subject | Multi-robot system | en |
| dc.subject | Bio-mimicry | en |
| dc.title | 多群組微型仿生體之合作型搜尋演算法發展與行為設計 | zh_TW |
| dc.title | Cooperative Search Algorithm and Behavior Design for Micro Bio-mimetic Multi-Robot Systems | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 94-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 顏家鈺(Jia-Yush Yen),連豊力(Feng-Li Lian),林進燈(Chin-Teng Lin) | |
| dc.subject.keyword | 多群組機器人,仿生學,人工生命,群體行為,氣味搜尋, | zh_TW |
| dc.subject.keyword | Multi-robot system,Bio-mimicry,Artificial Life,Scent Search, | en |
| dc.relation.page | 82 | |
| dc.rights.note | 未授權 | |
| dc.date.accepted | 2006-07-31 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-95-1.pdf 未授權公開取用 | 2.02 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。