多群組微型仿生體之合作型搜尋演算法發展與行為設計

Cooperative Search Algorithm and Behavior Design for Micro Bio-mimetic Multi-Robot Systems

田家倫(Chia-Lun Tien)

指導教授 ： 陳永耀

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2006年)

https://doi.org/10.6342/NTU.2006.10521

摘要

多群組機器人是近年來被廣泛研究的一個主題，且被應用於各種領域。如何設計多群組機器人的行為一直以來是個有趣的問題，本論文試著從觀察及模仿生物行為的角度切入，探討及設計如何使得一群只具有簡單能力的機器人能在一個未知的環境中進行搜尋任務。此類機器人可被應用在危險環境中的搜索。
本論文主要研究內容包含兩個主題，分別為個體行為和群體行為的建立，以及在有限感測及通訊能力下，多群組仿生微型機器人所能達成之預期工作目標。在個體行為建立的部份，由於所設定的是分散式多群組機器人，因此每個成員都具有相同的能力及地位，故機器人的行為皆相同，而無階級的分別。每隻機器人的行為皆分為三個模式，並以所偵測到的氣味濃度作為切換的依據。在第二部份中，本論文發展了一套合作型氣味搜尋演算法，有別於一般常見設計多群組機器人行為的方法，本演算法引進了人工生命所提及的基本概念－存在於個體之間的些許規則規範著其行為。受限於氣味場的特性，微型仿生機器人在距離氣味源較遠的地方或是有障礙物阻擋的關係，無法感測出該處的氣味濃度或濃度梯度，本演算法利用和通訊範圍內的其餘微型仿生機器人交換而得的資訊，進行鄰近微型仿生機器人分布的估測，並由此分部估測推算氣味場的梯度，並決定行進方向。
在本論文中，首先介紹仿生學在工程及科學領域的應用。其次對於設計機器人行為的過程及合作型氣味搜尋演算法有詳細的介紹。最後，呈現在不同環境條件下，模擬群體行為的結果。

關鍵字

多群組機器人 ； 仿生學 ； 人工生命 ； 群體行為 ； 氣味搜尋

並列摘要

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.

並列關鍵字

Multi-robot system ； Bio-mimicry ； Artificial Life ； Scent Search

參考文獻

[2] 李源華，”微型仿生體之氣味追蹤演算法與氣味快散環境建立”，國立台灣大學電機工程研究所。

[3] J. E. Hopcroft, R. E. Tarjan, “Dividing a Graph into Triconnected Component,” SIAM J. Comput., pp. 135-158, February (1973).

[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.

[9] Marco Dorigo, Eric Bonabeaub, Guy Theraulaz, “Ant Algorithms and Stigmergy,” Future Generation Computer Systems, pp.851–871, 2000.