Movement Algorithm in Biomimetic Multi-Robot Systems Using Communication Data

近幾年來，多群組機械系統被廣泛的利用在各種工程領域裡面，例如軍事行動的事先偵查、太空行星的探勘或者是地圖的製作，都是多群組機械系統非常典型的應用。而本論文所要探討的主題是集中在使一隊的多群組機械可以進行探勘、搜尋和聚集方面的行為。 本論文提出一個讓多群組機械可以在未知環境下進行聚集跟分散行為的移動演算法，而這個演算法的主要判斷資訊是一些容易取得的通訊資訊，多群組機械在這個演算法裡的行為是模仿自然界生物的行為模式，而有著生物行為模式的機械我們稱它為仿生機械。對於進行一個探勘的任務時，在一個未知的環境裡面仿生機械會套用分散移動演算法盡可能的去分散然後蒐集有關環境的資訊。對於一個聚集的任務時，仿生機械會套用聚集移動的演算法去移動到同一個小區域以方便仿生機械的回收或者一起搬運目標物等行為。而這裡所提到容易取得的通訊資訊是指不用再進行額外的步驟或者是加裝其他感測器或儀器就可以取得的資訊。例如：可以和自己通訊的仿生機械的數目和彼此可互相通訊的兩隻仿生機械之間大概的距離，都會被利用來發展這個演算法。 本論文中首先介紹有關多群組機械、生物的行為模式和無線通訊架構的觀念。其次討論根據利用簡單易得的資訊讓多群組仿生機械可以進行分散和聚集等行為的移動演算法。最後提出模擬結果來佐證這個演算法，以及一些實際硬體的實驗來證明這個演算法的可行性。In recent years, multi-robot systems have a broad range of applications in the engineering field. For example, military reconnaissance, planetary exploration, and geophysical mapping are typical applications of multi-robot systems. The objective of this thesis focuses on the exploration and the foraging and concentration of a multi-robot team. This thesis proposes a dispersion movement algorithm and a concentration movement algorithm for multi-robots in an unknown environment. The judging information of these two algorithms is easily got information through communication. The action of the movement algorithm is based on the study of the group behaviors of biological systems. For the exploration task, bio-robots apply the dispersion movement algorithm to spread out in an unknown environment as wide as possible in order to collect information about the exploratory area. For the concentration task, bio-robots apply the concentration movement algorithm to move to the same place for retrieving the exploratory robots or transporting the target. The easily got information means that it can be got without other redundant steps or equipping other sensor or instrument. Particularly, the number of neighbors and the rough distance between two bio-robots are used to develop the algorithm. In this thesis, the multi-robot systems, the behaviors of biological systems, and the wireless communication architecture are introduced first. Second, the proposed movement algorithms developed by the easily got communication information in multiple bio-robots are discussed. Finally, the analysis of the movement algorithm is studied with simulations and the algorithm is also implemented on the hardware of CC1010 to show the feasibility of the algorithm.摘要 i Abstract iii Contents v List of Figures vii List of Tables xi Chapter 1 1 Introduction 1 1.1 Motivation 1 1.2 Organization of the Thesis 2 Chapter 2 5 Background and Literature Survey 5 2.1 Introduction of the Multi-Robot Systems 5 2.2 Social and Intelligent Foraging 7 2.3 Biologically Inspired Behaviors 7 2.4 Bacterial Foraging 8 2.4.1 Introduction to Bacterium E. coli 9 2.4.2 Bacterial Motile Behavior 10 2.5 Routing Protocol 11 2.5.1 Routing in ad hoc wireless networks 11 2.6 Partition of an ad hoc network 12 2.6.1 Introduction to partition in the ad hoc network 12 2.6.2 Related work for partition avoidance 13 2.6.2.1 Delaying critical link failures to avoid or delay partitioning 13 2.6.2.2 Choosing paths that prevent network partitioning 14 Chapter 3 17 Dispersion and Concentration Algorithms 17 3.1 Problem Formulation 17 3.2 Introduction to Movement Algorithms 19 3.2.1 Assumption for the bio-robots and the environment 19 3.2.2 Movement algorithms 19 3.2.3 Parameter definition of the movement algorithm 23 3.3 The Dispersion Algorithm 24 3.3.1 The flow chart of the dispersion algorithm 26 3.3.2 The moving condition of the dispersion algorithm 28 3.3.3 Direction decision of the dispersion movement algorithm 28 3.3.4 Partition of the dispersion movement algorithm 33 3.3.5 The reason for partition 35 3.3.6 Partition avoidance in the movement algorithm 35 3.3.7 Tradeoff between connection and exploratory area 36 3.3.8 Pseudo code of the dispersion movement algorithm 36 3.4 The Concentration Movement Algorithm 37 3.4.1 The flow chart of the concentration algorithm 39 3.4.2 Moving condition of concentration movement algorithm 40 3.4.3 Direction decision of the concentration movement algorithm 41 3.4.4 Pseudo code of the concentration movement algorithm 44 Chapter 4 47 Simulation and Experimental Results 47 4.1 Simulation for the Effect of and 47 4.1.1 Probability of the partition 48 4.1.2 Exploratory area 49 4.2 Simulation for Dispersion Movement Algorithm 56 4.2.1 Simulation results of dispersion algorithm 56 4.2.2 Trajectory of the dispersion algorithm 59 4.3 Simulation of Concentration Movement Algorithm 60 4.3.1 Simulation result for one target 61 4.4 Application of Dispersion and Concentration Algorithm 65 4.4.1 Scenario one 66 4.4.2 Scenario two 70 4.5 The Experiment of the Moving Algorithm on the CC1010 Chip 72 4.5.1 Hardware introduction 73 4.5.2 Communication architecture 76 4.5.2.1 Physical layer 76 4.5.2.2 Packet format 77 4.5.2.3 Routing layer 79 4.5.3 Experimental result 80 4.6 Experiment of the Routing on the CC1010 Chip 83 Chapter 5 85 Conclusion and Future Works 85 References 8