

small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution


COOPERATIVE CONTROL, LEARNING AND SENSING IN MOBILE SENSOR NETWORKS By HUNG MANH LA Bachelor of Science Thai Nguyen University of Technology Thai Nguyen City, Thai Nguyen, Vietnam 2001 Master of Science Thai Nguyen University of Technology Thai Nguyen City, Thai Nguyen, Vietnam 2003 Submitted to the Faculty of the Graduate College of Oklahoma State University in partial fulfillment of the requirements for the Degree of DOCTOR OF PHILOSOPHY December, 2011 COPYRIGHT c By HUNG MANH LA December, 2011 COOPERATIVE CONTROL, LEARNING AND SENSING IN MOBILE SENSOR NETWORKS Dissertation Approved: Dr. Weihua Sheng Dissertation Advisor Dr. Gary G. Yen Dr. Satish Bukkapatnam Dr. Qi Cheng Dr. Mark Payton Dean of the Graduate College iii TABLE OF CONTENTS Chapter Page 1 INTRODUCTION 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4.1 Cooperative Control . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4.2 Cooperative Learning in MSNs . . . . . . . . . . . . . . . . . . . 13 1.4.3 Cooperative Sensing in MSNs . . . . . . . . . . . . . . . . . . . . 14 1.5 Organization of This Dissertation . . . . . . . . . . . . . . . . . . . . . . . 16 2 FLOCKING CONTROL FOR DYNAMIC TARGET TRACKING 17 2.1 Single Mobile Sensor Node and Dynamic Target Tracking . . . . . . . . . 17 2.1.1 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1.2 Potential field approach . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.3 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Flocking Control for Single Target Tracking and Observing . . . . . . . . . 23 2.2.1 Flocking control background . . . . . . . . . . . . . . . . . . . . . 23 2.2.2 Algorithm description . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.3 Stability analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2.4 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 iv 3 COOPERATIVE CONTROL BASED FLOCKING FOR MSNs IN NOISEFREE ENVIRONMENTS 37 3.1 Decentralized Flocking Control with a Minority of Informed Agents . . . . 37 3.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.1.2 Decentralized Flocking Control with aMinority of Informed Agents (MIA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.1.3 Experimental and Simulation Results . . . . . . . . . . . . . . . . 44 3.2 Adaptive Flocking Control for Moving Target Tracking . . . . . . . . . . . 51 3.2.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.2.2 Adaptive Flocking Control . . . . . . . . . . . . . . . . . . . . . . 52 3.2.3 Stability Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2.4 Simulation and Experiment Results . . . . . . . . . . . . . . . . . 57 3.3 Multiple Dynamic Targets Tracking . . . . . . . . . . . . . . . . . . . . . 63 3.3.1 Sensor Network Partitioning . . . . . . . . . . . . . . . . . . . . . 63 3.3.2 Multiple Dynamic Targets Tracking . . . . . . . . . . . . . . . . . 66 3.3.3 Experimental Tests . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4 COOPERATIVE CONTROL BASED FLOCKING FOR MSNs IN NOISY ENVIRONMENTS 83 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.2 Flocking Control Algorithm in Noisy Environments . . . . . . . . . . . . . 84 4.2.1 MultiCoMShrink Algorithm . . . . . . . . . . . . . . . . . . . . 85 4.2.2 MultiCoMCohesion Algorithm . . . . . . . . . . . . . . . . . . . 88 4.3 Stability Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.4.1 Parameter Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 v 5 COOPERATIVE LEARNING OF PREDATOR AVOIDANCE IN MSNs 100 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.2 General Framework of Hybrid System in Multiple Mobile Sensors Domain 102 5.3 Modeling and Cooperative Learning Algorithm . . . . . . . . . . . . . . . 105 5.3.1 Model of Multiple Mobile Sensors Learning . . . . . . . . . . . . . 105 5.3.2 Cooperative Learning Algorithm . . . . . . . . . . . . . . . . . . . 106 5.4 Convergence Analysis of Cooperative Learning Algorithm . . . . . . . . . 111 5.5 Simulation and Experiment Results . . . . . . . . . . . . . . . . . . . . . . 115 5.5.1 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.5.2 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.5.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . 122 5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 6 COOPERATIVEAND ACTIVE SENSING FORMSNs BASED ON DISTRIBUTED CONSENSUS 129 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.2 Scalar Field and Measurement Modeling and Problem Statement . . . . . . 131 6.2.1 Model of the Scalar Field . . . . . . . . . . . . . . . . . . . . . . . 131 6.2.2 Measurement Model . . . . . . . . . . . . . . . . . . . . . . . . . 132 6.2.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.3 Distributed Sensor Fusion Algorithm . . . . . . . . . . . . . . . . . . . . . 133 6.3.1 Overall Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.3.2 Distributed Consensus Filters . . . . . . . . . . . . . . . . . . . . 134 6.3.3 Convergence Analysis . . . . . . . . . . . . . . . . . . . . . . . . 138 6.3.4 Distributed Fusion Algorithm . . . . . . . . . . . . . . . . . . . . 141 6.4 Path Planning Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 6.5 Cooperative and Active Sensing . . . . . . . . . . . . . . . . . . . . . . . 146 6.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 vi 6.5.2 Distance Controller . . . . . . . . . . . . . . . . . . . . . . . . . . 148 6.5.3 Potential Controller . . . . . . . . . . . . . . . . . . . . . . . . . . 151 6.5.4 Quasi Uniformity of Confidence . . . . . . . . . . . . . . . . . . . 154 6.6 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 6.6.1 Tests of Consensus Filter 1 and 2 . . . . . . . . . . . . . . . . . . 159 6.6.2 Simulation Results of Cooperative Sensing . . . . . . . . . . . . . 161 6.6.3 Simulation Results of Cooperative Sensing and the Flocking Control with a Minority of Informed Agents . . . . . . . . . . . . . . . 165 6.6.4 Simulation Results of Active Sensing . . . . . . . . . . . . . . . . 170 6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 7 CONCLUSION AND FUTUREWORK 181 7.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 7.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 BIBLIOGRAPHY 186 Abstract 206 vii LIST OF TABLES Table Page 3.1 Comparison between two algorithms (SGGP and RS). . . . . . . . . . . . . 71 viii LIST OF FIGURES Figure Page 1.1 (a) Schooling of fish. (b) A predator and a school of fish (source: www. inmagine.com). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 The organization of the dissertation. . . . . . . . . . . . . . . . . . . . . . 16 2.1 A mobile sensor tracks a moving target. . . . . . . . . . . . . . . . . . . . 18 2.2 The mobile sensor tracks the target moving in a circular trajectory. . . . . . 22 2.3 Tracking error between the mobile sensor and the moving target. . . . . . . 22 2.4 The projection method for finding the positions and velocities of b neighbors of each a  sensor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.5 (a) A mobile sensor network with a single CoM (SingleCoM), (b) A mobile sensor network with multiple CoMs (MultiCoM). . . . . . . . . . . . 30 2.6 Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, forming a network, avoiding obstacles, and at the ending positions, respectively. (a, b, c) the mobile sensor network is tracking the target moving in the sine wave trajectory, and (a’, b’, c’) the mobile sensor network is tracking the target moving in the circle trajectory using flocking control algorithms with NoCoM (2.38), SingleCoM (2.42) and MultiCoM (2.43), respectively. . . . . . . . . . . . . . . . . . . . . . . . 34 2.7 Position errors between the CoM’s positions and the moving target in the sine wave trajectory (a, b, c) and the circle trajectory (a’, b’, c’) using flocking control algorithms with NoCoM (2.38), SingleCoM (2.42) and MultiCoM (2.43), respectively. . . . . . . . . . . . . . . . . . . . . . . . 35 ix 3.1 Snapshots of the agents when applying the flocking control algorithm (3.1). We select 6 out of 50 agents which are closest to the target to have the information (position and velocity) of the target. . . . . . . . . . . . . . . . 40 3.2 Motion Capture System from VICON [1] in the experimental setup. . . . . 44 3.3 If one or two of the links (1,2), (3,4), (5,6) is broken the graph connectivity is still remained, but if all of that links is broken the graph connectivity is lost. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.4 Connectivity evaluation in experiment of 7 Rovio robots when applying our proposed flocking control algorithm 3. . . . . . . . . . . . . . . . . . . 47 3.5 Snapshots of 7 Rovio robots flocking together when applying our proposed flocking control algorithm 3. . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.6 Trajectories of simulation and real robots when applying our proposed flocking control algorithm 3. . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.7 Snapshots of 50 robots flocking together (simulation) with two of them knowing the information of the target. . . . . . . . . . . . . . . . . . . . . 49 3.8 Average of positions of 2 informed robots (tracking performance) in simulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.9 Connectivity evaluation in simulation of 50 robots. Solid line is for our proposed algorithm 3, and dash line is for the existing algorithm (3.1) . . . 50 3.10 Illustration of the adaptive flocking control. . . . . . . . . . . . . . . . . . 52 3.11 Experimental setup for adaptive flocking control. . . . . . . . . . . . . . . 59 3.12 Snapshots of the mobile sensor network (a) when the mobile sensors form a network, (b) when the mobile sensors avoid obstacles, (c) when the mobile sensors get stuck in the narrow space between two obstacles. (a’, b’, c’) are closer look of (a, b, c), respectively. These results is obtained by using algorithm (2.38). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 x 3.13 Snapshots of the mobile agent network (a) when the mobile agents form a network, (b, c) when the mobile agent network shrinks to avoid obstacles, (d) when the mobile agents successfully passed through the narrow space between two obstacles, (e) when the mobile agents recover the original size. (a’, b’, c’, d’, e’) are closer look of (a, b, c, d, e), respectively. These results are obtained by using our adaptive flocking control algorithm (3.12). 61 3.14 Velocity matching among agents, connectivity, and error of positions between the CoM and the moving target in (a, b, c), respectively using our adaptive flocking control algorithm (3.12), (a’, b’, c’) using the algorithm (2.38). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.15 Snapshots of adaptive flocking control with 7 Rovio robots using our adaptive flocking control algorithm(3.12). (a) 7 robots are randomly distributed. (b) 7 robots form a lattice formation. (c) 7 robots begin to shrink the size of the network. (d) 7 robots pass through the narrow space between 2 obstacles. (e) 7 robots begin to recover the size of the network. (f) 7 robots completely recover the size of the network. . . . . . . . . . . . . . . . . . 62 3.16 Trajectories of 7 robots are obtained by using the adaptive flocking control algorithm (3.12). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.17 Example of seed growing graph partition. . . . . . . . . . . . . . . . . . . 65 xi 3.18 (a) Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, forming a network at time t = 1.26, and decomposing into two subgroups, respectively to track the targets moving in the sine wave trajectories, (b) Error between the average of sensors’s positions in the whole network and the moving target 1 (iteration 1 to 839), and between average of sensors’s positions in subgroup 1 and the moving target 1 (iteration 839 to the end), (c) Error between the average of sensors’s positions in subgroup 2 and the moving target 2. This result is obtained by using the flocking control NoCoM (3.18) and SGGP algorithm . . . . . . . 69 3.19 (a) Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, when the mobile sensors form a network at time t = 1.26, when the mobile sensors decompose into two subgroups, and when two subgroups merge, (b) Error between the average of sensors’s positions in the whole network and the moving target 1 (iteration 1 to 839, and iteration 4200 to the end), and between the average of sensors’s positions in subgroup 1 and the moving target 1 (iteration 840 to 4200), (c) Error between the average of sensors’s positions in subgroup 2 and the moving target 2. This result is obtained by using the flocking control with NoCoM (3.18) and SGGP algorithm. . . . . . . . . . . . . . . . . . . . . 70 xii 3.20 (a) Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, forming a network at time t = 1.26, and decomposing into two subgroups, respectively to track the targets moving in the sine wave trajectories, (b) Error between the average of sensors’s positions in the whole network and the moving target 1 (iteration 1 to 839), and between average of sensors’s positions in subgroup 1 and the moving target 1 (iteration 840 to the end), (c) Error between the average of sensors’s positions in subgroup 2 and the moving target 2. This result is obtained by using the flocking control with NoCoM (3.18) and RS algorithm. . . . . . 72 3.21 Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, forming a network at time t = 1.26, and decomposing into two subgroups, respectively to track the targets moving in the sine wave trajectories. This result is obtained by using the MultiCoM flocking control and SGGP algorithms. . . . . . . . . . . . . . . . . . . . . . . . . 75 3.22 (a, c) are closer look of (b, d) at iterations from 1 to 100. (b) Position errors between the CoM of the whole network and target 1 (from iteration 1 to 839), and between the CoM of the subgroup 1 and target 1 (from iteration 840 to the end). (d) Position errors between the CoM of the subgroup 2 and target 2. This result is obtained by using the MultiCoM flocking control and SGGP algorithms. . . . . . . . . . . . . . . . . . . . . . . . . 76 3.23 Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, forming a network at time t = 1.26, and decomposing into two subgroups, respectively to track the targets moving in the sine wave trajectories. This result is obtained by using the MultiCoM flocking control and RS algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . 77 xiii 3.24 (a, c) are closer look of (b, d) at iterations from 1 to 100. (b) Position errors between the CoM of the whole network and target 1 (from iteration 1 to 839), and between the CoM of the subgroup 1 and target 1 (from iteration 840 to the end). (d) Position errors between the CoM of the subgroup 2 and target 2. This result is obtained by using the MultiCoM flocking control and RS algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.25 Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, when the mobile sensors form a network at time t = 1.26, when the mobile sensors decompose into two subgroups, and when two subgroups merge. This result is obtained by using the MultiCoM flocking control and SGGP algorithms. . . . . . . . . . . . . . . . . . . . . . . . . 80 3.26 (a, c) are closer look of (b, d) at iterations from 1 to 100. (b) Position errors between the CoM of the whole network and target 1 (from iteration 1 to 839, and 3301 to the end), between the CoM of the subgroup 1 and target 1 (from iteration 840 to 3300). (d) Position errors between the CoM of the subgroup 2 and target 2. This result is obtained by using the MultiCoM flocking control and SGGP algorithms. . . . . . . . . . . . . . . . . . . . . 81 4.1 Agent 2 is considered as a neighbor of agent 1 because the estimated distance dˆa is less than the active range r. . . . . . . . . . . . . . . . . . . . . 86 4.2 Snapshots of agents when they are randomly distributed (a, e, i), and when they form a network and track a target (red/dark line) moving in a sine wave trajectory (b, c, d; f, g, h; j, k, l), where (a, b, c, d) are for the NoCoM flocking control algorithm (2.38), (e, f, g, h) are for the MultiCoMShrink flocking control algorithm, and (i, j, k, l) are for the MultiCoMCohesion flocking control algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 95 xiv 4.3 Snapshots of agents when they are randomly distributed (a, e, i), and when they form a network and track a target (red/dark line) moving in a circle trajectory (b, c, d; f, g, h; j, k, l), where (a, b, c, d) are for the NoCoM flocking control algorithm (2.38), (e, f, g, h) are for the MultiCoMShrink flocking control algorithm, and (i, j, k, l) are for the MultiCoMCohesion flocking control algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.4 The tracking performance results (error between the CoM and target positions): (a) is for the NoCoM flocking control algorithm (2.38), (b) is for the MultiCoMShrink flocking control algorithm, and (c) is for the Multi CoMCohesion flocking control algorithm. The connectivity is evaluated by the C(t) value: (d) is for the NoCoM flocking control algorithm (2.38), (e) is for the MultiCoMShrink flocking control algorithm, and (f) is for the MultiCoMCohesion flocking control algorithm. . . . . . . . . . . . . 97 5.1 The hybrid system for reinforcement learning and flocking control in multiple mobile sensors domain. . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.2 Illustration of the safe places to choose. . . . . . . . . . . . . . . . . . . . 105 5.3 Illustration of the predator and prey detection ranges. R1 is the active range of the mobile sensor (prey), R2 is the predator detection range, and Rp is the prey detection range. . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.4 Four safe places are generated based on the moving direction of the predator.108 5.5 Q value update based on the mobile sensor’s action/state and its neighboring actions/states. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 5.6 Snapshots of our proposed cooperative learning algorithmin the first episode. Four red/darker dots as shown in snapshots (d, e, f) are four safe places. The empty red circle is the predator. The filled red circles are the obstacles. . . . 116 xv 5.7 Snapshots of our proposed cooperative learning algorithm in the second episode. Four red/darker dots as shown in snapshots (e, f) are four safe places. The empty red circle is the predator. The filled red circles are the obstacles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.8 Snapshots of the proposed cooperative learning algorithmin the third episode. Four red/darker dots as shown in snapshots (e, f) are the four safe places. The empty red circle is the predator. The filled red circles are the obstacles. 118 5.9 Snapshots of the proposed cooperative learning algorithm in the fourth episode. Four red/darker dots as shown in snapshots (e, f) are the four safe places. The empty red circle is the predator. The filled red circles are the obstacles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.10 Snapshots of the proposed cooperative learning algorithmin the fifth episode. Four red/darker dots as shown in snapshots (c, d) are the four safe places. The empty red circle is the predator. The filled red circles are the obstacles. 120 5.11 Seven Rovio prey mobile sensors and one Rovio predator robot (marked with a yellow cup) are used in the experiment. . . . . . . . . . . . . . . . . 121 5.12 Infrared cameras tracking system for experimental setup of multirobot cooperative learning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 5.13 The trajectories of 7 Rovio robots and one predator in the first learning episode. The green small squares are the safe places, and the filled red squares are the obstacles. . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.14 The trajectories of 7 Rovio robots and one predator in the third learning episode. The green small squares are the safe places, and the filled red squares are the obstacles. . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.15 Connectivity evaluation for the independent learning algorithm (a, c) and our proposed cooperative learning algorithm (b, d), here (c) is a zoomin at 100th episode of (a), and (d) is a zoomin at 4th episode of (b) . . . . . . . 125 xvi 5.16 Topology evaluation for the independent learning algorithm (left) and our proposed cooperative learning algorithm (right). . . . . . . . . . . . . . . . 126 5.17 Convergence of Q values for the independent learning algorithm (left) and our proposed cooperative learning algorithm (right). . . . . . . . . . . . . . 127 5.18 Global reward evaluation for the independent learning algorithm (left) and our proposed cooperative learning algorithm (right). . . . . . . . . . . . . . 127 6.1 (a) Evacuation: Ships and rig workers evacuate the oil spill area as Tropical Storm Bonnie approaches the region (Photo by Mario Tama/Getty Images). (b) The estimated field of chlorophyll generated by the harmful algal blooms observation system [2] by the National Oceanic and Atmospheric Administration (NOAA), (Photo courtesy of NOAA). . . . . . . . . . . . . 130 6.2 Illustration of the measurement model using multiple mobile sensor nodes. . 133 6.3 Framework of distributed sensor fusion algorithm based two different consensus filters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 6.4 Seven mobile sensor nodes flock together and cover the scalar field (the filled square: 12 × 12). The motion path (red color) is generated by the leader, and the CoM (black/darker color) of the network tracks the leader with small overshoots at sharp change points of the path. . . . . . . . . . . 145 6.5 The confidence at each cell of the scalar field F. . . . . . . . . . . . . . . . 146 6.6 Framework of active sensing via confidence feedback . . . . . . . . . . . . 149 6.7 Diagram of active sensing based on the distance controller via confidence feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 6.8 Illustration of confidence feedback for lower bound only. . . . . . . . . . . 150 6.9 Diagram of cooperative and active sensing based on the potential controller enhanced with attractive force via confidence feedback. . . . . . . . . . . . 151 6.10 Illustration of creating virtual attractive forces in the cells which have the confidence level lower than the lower bound. . . . . . . . . . . . . . . . . . 152 xvii 6.11 Illustration of confidence feedback for quasi uniformity of the confidence. The upper bound and lower bound are used to create a quasi uniform of the confidence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 6.12 Diagram of cooperative and active sensing based on the potential controller enhanced with attractive and repulsive forces via confidence feedback. . . . 156 6.13 Illustration of creating virtual repulsive forces in the cells which have the confidence level higher than the upper bound. . . . . . . . . . . . . . . . . 156 6.14 (a). 10 nodes estimate the value at cell k (pink square). (b, c) Result of convergence of 10 nodes, and agreement of 10 nodes when applyingWeight Design 1 in (6.15). (d, e) Result of convergence of 10 nodes, and agreement of 10 nodes when applying Weight Design 2 in (6.21). . . . . . . . . . . . 160 6.15 (a). Distribution of 10 nodes. (b, c) Result of convergence of 10 nodes, and agreement of 10 nodes when applying the Consensus Filter 2 in (6.25) with Metropolis weight (6.26). . . . . . . . . . . . . . . . . . . . . . . . . 161 6.16 (a) the original map of the scalar field F, (b) the built map of the scalar field F using Algorithm 6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 6.17 The snapshots of building the map of the scalar field F using Algorithm 6 and flocking control algorithm (6.40). . . . . . . . . . . . . . . . . . . . . 163 6.18 The error between the built and original maps for all cells in one dimension. (a) for Algorithm 1 with the normal average update protocol; (b) for centralized fusion algorithm; (c) for Algorithm1 with the weighted average update protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 6.19 The error between the built and original maps for all cells in three dimensions. (a) for Algorithm 6 with the normal average update protocol; (b) for centralized fusion algorithm; (c) for Algorithm6 with the weighted average update protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 6.20 The confidence at each cell of the scalar field F. . . . . . . . . . . . . . . . 164 xviii 6.21 Seven mobile sensor nodes flock together and cover the scalar field (the filled square: 12 × 12). The motion path (red color) is generated by the leader, and the CoM (black/darker color) of the network tracks the leader with small overshoots at sharp turning points of the path. . . . . . . . . . . 167 6.22 Snapshots of multiple mobile sensors flocking together and building the map of the scalar field. In these snapshots, only two mobile sensors (blue squares) have information of the virtual leader. The white line is the trajectory of the center of of position of two informed mobile sensors. . . . . . . 168 6.23 (a) The error between the built and true maps for all cells in one dimension; (b) The error between the built and true maps for all cells in three dimensions; (c) The three dimensional confidence map. . . . . . . . . . . 168 6.24 (a) The original map of the scalar field F; (b) The built map of the scalar field F using Algorithm 1. . . . . . . . . . . . . . . . . . . . . . . . . . . 169 6.25 Tracking error between the position of the virtual leader (qt ) and the average of the position of the two informed agents (mean(qin f )). . . . . . . . . 169 6.26 Snapshots of building the map of the scalar field F using Algorithm 6 and the cooperative and active sensing algorithm (6.48). . . . . . . . . . . . . . 171 6.27 (a) The error between the built and true maps for all cells in one dimension; (b) The error between the built and true maps for all cells in three dimensions using Algorithm 6 and the cooperative and active sensing algorithm (6.48). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 6.28 Confidence over the cells in 3 dimensions: (a) for active sensing with Potential Controller using attractive force only, Algorithm (6.46) ; (b) for active sensing with Potential Controller using both attractive and repulsive, Algorithm (6.48). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 xix 6.29 Confidence over the cells in one dimension: (a) for normal cooperative sensing; (b) for active sensing with Distance Controller; (c) for active sensing with Potential Controller using only attractive force (6.46); (d) for active sensing with Potential Controller using both attractive and repulsive forces (6.48). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 6.30 Distance between the mobile sensor 1 and its neighbor: (a) for normal cooperative sensing; (b) for active sensing with Distance Controller; (c) for active sensing with Potential Controller using only attractive force (6.46); (d) for active sensing with Potential Controller using both attractive and repulsive forces (6.48). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 6.31 Error between the original map and the built map in one dimension over cells: (a) for the normal sensing; (b) for the active sensing. . . . . . . . . . 177 6.32 (a) Confidence over cells; (b) Error between the original map and the built map in one dimension over cells. . . . . . . . . . . . . . . . . . . . . . . . 178 6.33 (a) For Potential Controller with attractive force only; (b) For Potential Controller with both attractive and repulsive force. . . . . . . . . . . . . . 179 7.1 Illustration of coverage with limited sensing range. . . . . . . . . . . . . . 184 7.2 A mobile sensor network test bed. . . . . . . . . . . . . . . . . . . . . . . 185 xx CHAPTER 1 INTRODUCTION In this chapter, we first present the motivation of our work, then present the challenges, the contributions and the current state of the art of the cooperative control, learning and sensing in MSNs. 1.1 Motivation Mobile sensor networks (MSNs) [3], one type of sensor networks [4, 5, 6, 7], have been studied by many researchers in recent years. A typical mobile sensor is a mobile robot with various sensors such as camera, sonar or laser for sensing and navigation. Mobile sensor networks have several advantages over stationary sensor networks, such as the adaptation to environmental changes and reconfigurability for better sensing performance. Therefore mobile sensor networks can be applied in many applications including cooperative detection of toxic chemicals in contaminated environments [8, 9, 10]; environment exploring, monitoring and coverage [11, 12, 13]; performing search and rescue operation after disasters [14, 15]; target tracking [16, 17, 18] and protection of endangered species [19]. A main issue for multiple mobile sensors move together is that these sensors have to avoid collision among them, which requires the use of cooperative control methods [20, 21, 22, 23, 24]. One of these methods is flocking control [23]. We know that flocking or schooling is a phenomenon that a number of mobile agents move together and interact with each other while ensuring no collision, velocity matching, and flock centering [25]. In the nature, schools of fish (see Figure 1.1), birds, ants, and bees, etc. demonstrate the phenomenon of flocking [26]. The problem of flocking has been studied for many years. 1 (a) (b) Figure 1.1: (a) Schooling of fish. (b) A predator and a school of fish (source: www. inmagine.com). It has attracted many researchers in physics [27, 28], mathematics [29], biology [30], and especially in control science in recent years [31, 32, 33, 23, 34, 35, 36, 37, 38, 39, 40]. There are several interesting features established by the school of fish or flock of birds. These features can inspire us to design cooperative control, learning and sensing algorithms for MSNs. • Fish school and bird flock can track a target (source of food) efficiently while avoiding obstacles. This inspires us to design a cooperative control algorithm that can allow mobile sensors to track a target better in cluttered environments. • Each individual fish or bird communicates/interacts with its neighbors within its limited sensing range in order to move in the same direction as its neighbors, remain close to its neighbor, and avoid collision with its neighbors [25]. Based on only these local communications/interactions, the fish school or bird flock can still achieve a global goal. For example, in some cases only some individuals have the knowledge about the location of a food source and migration route, but the fish school or bird flock can still find the food source and track the migration route efficiently [41, 42]. Inspired by this natural ability we would like to design a cooperative control algorithm that can allow mobile sensors to track a target when only a very small subset of 2 them know the information of the target while maintaining the network connectivity. • Fish school and bird flock also have ability to change their size of the formation in order to adapt to the environments. This motivates us to design an adaptive control algorithm for an MSN that can automatically adjust its size (shrink/recover) in order to adapt to the complex environments while maintaining the network connectivity and similar topology. • Fish school and bird flock can track multiple food sources (targets) simultaneously. This ability encourages us to design a splitting/merging algorithm that can allow an MSN to track multiple moving targets simultaneously and efficiently in a dynamic fashion. • Each individual fish or bird may not sense the position and velocity of its neighbors accurately, but it can still move with its neighbors and maintain the cohesion with them. This feature inspires us to design flocking control algorithms that can allow mobile sensors to work in noisy environments while maintaining the cohesion to the network. • Fish schooling and bird flocking together can help the individual to avoid predators because many moving individuals create a sensory overload for the predator’s visual channel [43, 44, 45] (see Figure 1.1b). This motivates us to design a cooperative learning algorithm that can allow an MSN to learn to avoid the enemy (predator) in a distributed fashion while maintaining the network connectivity and similar topology. • Finally, each individual fish or bird only interacts locally, but as a whole the fish school or bird flock can agree on the same velocity (velocitymatching ability) through distributed consensus. Understanding this feature can help us design cooperative and active sensing algorithms for an MSN which can allow each sensor to find an agreement among observations of itself and its neighbors by reaching consensus. 3 1.2 Challenges Development of cooperative control, learning and sensing algorithms in a distributed fashion for MSNs is very challenging. These algorithms have to be performed at each sensor node using only local information, while as a whole they exhibit collective intelligence and achieve a global goal. In a resourceconstrained multiagent system, the communication range and sensing range of each agent are small compared to the size of the environments. Hence, agents cannot accomplish the mission without careful design of cooperative control, learning and sensing algorithms. Here are several challenges in designing cooperative control, learning and sensing algorithms for MSNs. • Cooperative Control in MSNs: First, designing flocking control algorithms which maintain the target tracking performance in cluttered environments is a challenging task. In these environments, the agents usually get stuck behind the obstacles and sometimes can not follow the target [23], [17], [34], [35], [46], therefore causing poor tracking performance. Second, designing a distributed flocking control algorithm which can still perform well in terms of better tracking performance and connectivity maintenance when only few agents have information of the target is a difficult task. Flocking control algorithms [23] can allow agents to move together without collision and track a target. However, they are designed under the assumption that all agents have the information of the target. Su et al. [34, 35, 46] relaxed this assumption, however the network connectivity is not maintained. Third, designing an adaptive flocking control algorithm that can adapt to the complex environments, for example passing through a narrow space among obstacles, while maintaining connectivity, tracking performance and similar formation is a challenging task. Existing works [47, 48] do not consider controlling the size of the network, hence the connectivity and topology are not maintained. 4 Fourth, tracking multiple targets simultaneously in a dynamic fashion in a MSN is difficult, since this requires that some sensors should split from the existing formation( s) to track new targets while ensuring the least disturbance to other sensors. This raises the question of which sensors should split from the existing formation and how they should split. In addition, when some targets disappear the sensors which are tracking these targets should rejoin (merge with) the existing groups that are still tracking targets. Fifth, designing distributed flocking control algorithms for MSNs which can still perform well when the measurements are corrupted by noise is very challenging. Existing works [37, 38, 23, 34, 35, 46] do not consider this issue in their flocking control algorithms. • Cooperative Learning in MSNs: Designing an intelligent MSN which can provide ability to learn to avoid enemy (predator) while maintaining the network topology and connectivity is difficult, since this is a distributed decision making problem where each individual has a number of options (safe places) to choose from when the predators appear. Often in these decisions there is a benefit for consensus, where all individuals choose the same safe place. However, the existing consensus methods [40, 49, 50, 51, 52, 53, 54, 55, 56] require a connected network in which all robots can communicate with each other. This may not be valid in real environments because some robots may not connect to the network during the escape. In that case the consensus algorithms will fail. Therefore, there is a need to reach consensus even when the robots cannot connect to the network at sometimes. • Cooperative Sensing in MSNs: Designing a distributed sensor fusion algorithm for MSNs with an emphasis on the task of environment estimation and mapping is an open problem, since it requires a 5 combination of cooperative sensing, cooperative motion control, and complete coverage path planning while using only local information. Existing works in the area of cooperative sensing using MSNs [57, 58, 59, 60, 61, 11, 62, 13] focus on target(s) tracking, environment exploring, sampling, modeling, and coverage. The problem of environmental estimation and mapping based on multiagent cooperative and distributed sensing is still an open research. 1.3 Contributions This work contributes to the research of MSNs by developing cooperative control, learning and sensing in a distributed fashion to realize coordinated motion control and intelligent situational awareness. Here are the main contributions of our work: • Cooperative Control: We propose a novel approach to the problem of flocking control of a MSN to track and observe a moving target. Flocking algorithms that constrain the center of mass of positions and velocities of all mobile sensors in each group (SingleCoM) or the center of mass of position and velocity of each sensor and its neighbors (MultiCoM) are developed. The main benefit of both algorithms is to make the center of mass (CoM) of each group track the target in the obstacle space. This makes the mobile sensors surround the target closely. We study the flocking control in the case of a small subset of informed agents. In nature, only few agents in a group have the information of the target, such as knowledge about the location of a food source, or the migration route. However, they can still flock together in a group based on local information. Inspired by this natural phenomenon, we propose a flocking control algorithm to coordinate the motion of multiple agents. Based on our algorithm, all agents can form a network, maintain connectivity and track the target even only very few of them know the information of 6 the target. To deal with changing environments, for example in the case when the mobile sensor networks have to pass through a narrow space among obstacles, we propose an adaptive flocking control algorithm in which each agent (sensor) can cooperatively learn the network’s parameters to decide the size of network in a decentralized fashion so that the connectivity, formation and tracking performance can be improved. In the scenario of multiple dynamic target tracking, to solve the problem of sensor splitting/merging, a seed growing graph partition (SGGP) algorithm is proposed. In noisy environments, a flocking control algorithm is proposed to coordinate the activities of multiple agents through noisy measurements. Based on our algorithm, all agents can form a network and maintain connectivity. This is of great advantage for agents to exchange information. We show that even with noisy measurements the flocks can achieve cohesion and follow the moving target. The stability and scalability of our algorithm are also investigated. • Cooperative Learning: We propose a hybrid system that integrates reinforcement learning and flocking control in order to create adaptive and intelligent multirobot systems. We study two problems in multirobot concurrent learning of cooperative behaviors: (1) how to generate efficient combination of high level behaviors (discrete states and actions) and low level behaviors (continuous states and actions) for multirobot cooperation; (2) how to conduct concurrent learning in a distributed fashion. To evaluate our theoretical framework, we apply it to enable multirobot networks to learn avoiding predators while maintaining network topology and connectivity. We also investigate the stability and scalability of our algorithm. 7 • Cooperative Sensing: We propose a novel method for multiple mobile sensor nodes to build a map of a scalar field through noisy measurements. Our method consists of three parts. First, we develop a distributed sensor fusion algorithm integrating two different distributed consensus filters to achieve cooperative sensing among sensor nodes. Second, we use the distributed flocking control algorithm to drive the center of the mobile sensor formation to track the desired paths. Third, we build a path planning strategy to obtain a complete coverage of the field. Additionally, we extend our cooperative sensing method to active sensing in order to improve the sensing performance. 1.4 Literature Review In this section, we review existing literature related to our work, which includes cooperative control, multiagent learning, and cooperative sensing. 1.4.1 Cooperative Control Cooperative control in multirobot systems has been receiving growing attention in recent years [63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73], and its applications include multitarget tracking [63, 64], multivehicle formation control [65, 66, 67, 68], optimization based control [69, 70], cooperative control with limited communications [71, 72], graphrigidity based control [74, 75, 76], and data gathering using mobile sensors [73]. In this subsection we review the existing works in the area of cooperative control which includes flocking control, adaptive flocking control, multiple targets tracking in both stationary sensor networks and mobile sensor networks. Flocking Control Flocking control has been studied by many researchers in recent years [77, 78, 64, 79, 80]. Wang and Gu [40] presented a survey of recent research achievements of robot flocking. 8 Their paper gave an overview of the related basic knowledge of graph theory, potential function, network communication and system stability analysis. In [23], a theoretical framework for design and analysis of distributed flocking algorithms was proposed. These algorithms solved the flocking control in the absence and presence of obstacles. The static and dynamic virtual leaders were used as a navigational feedback for all mobile agents. An extension of the flocking control algorithms in [23], flocking of agents with a virtual leader in the case of a minority of informed agents and in the case of varying velocity of the virtual leader, was presented in [34, 35, 46]. Shi and Wang [36] investigated the dynamic properties of mobile agents for the case where the state of the virtual leader is time varying and the topology of the neighboring relations between agents is dynamic was proposed. Anderson et al. [31] demonstrated a new technique for generating the constrained group animations of flocks in which users can impose constraints on agents’ positions at any time in the animation, or control the entire group to meet the shape constraints. Tanner et al. [37, 38] studied the stability properties of a system of multiple mobile agents with double integrator dynamics in the case of fixed and dynamic topologies. In addition, the experimental implementation of flocking algorithms proposed in [37] and [38] on wheeled mobile robots was presented in [39]. Gervasi and Prencipe [33] studied the distributed coordination and control of a set of asynchronous, anonymous, memoryless mobile vehicles in the case of no communication among the vehicles. In particular, their paper analyzed the problem of flocking in a certain pattern and following a designated leader vehicle, while maintaining the pattern. OlfatiSaber [17] developed a distributed flocking algorithm for mobile sensor networks to track a moving target. In his paper, an extension of a distributed Kalman filtering algorithm was used for the sensors to estimate the target’s position. In [32], a scalable multivehicle platform was developed to demonstrate a cooperative control algorithm in mobile sensor networks. Their flocking algorithm was implemented with five TXT1 monster truck robots. 9 Adaptive Flocking Control Adaptive flocking control, an extension of flocking control, has also gained attention from researchers in recent years. Folino and Spezzano [81] presented a parallel clustering algorithm based on the use of swarm intelligence techniques. Their algorithm is a combination of a smart exploratory strategy based on a flock of birds and a densitybased cluster algorithm to discover clusters of arbitrary shape and size in spatial data. Yang et al. [47] proposed an adaptive flocking control algorithm to avoid collision among robots themselves and between robots and obstacles. However, their algorithm did not consider the problem of formation, connectivity and tracking performance. Lee and Chong [48] proposed a decentralized approach for adaptive flocking of swarms of mobile robots to navigate autonomously in complex environments populated with obstacles. The problem of splitting/merging mobile robots in the network according to the environment conditions is addressed in their paper. In their work, the problem of controlling the size of the network was not considered. Multiple Targets Tracking Multiple targets tracking in mobile sensor networks has received adequate attention in the last decade. Jung et al. [82] introduced a regionbased approach to address the problem of multiple targets tracking using a network of communicating robots and stationary sensors. A coarse deployment controller distributes robots across regions using a topological map, and a targetfollowing controller maximizes the number of tracked targets within a region. Chung et al. [57] proposed a gradient search based decentralized algorithm for the problem of active sensing using multiple cooperative sensor nodes for distributed sensing to estimate the state of dynamic targets. Tang and Ozguner [83] investigated the motion planning for a limited number of mobile sensor agents in an environment with multiple dynamic targets. The motion planning problem is formulated as an optimization problem to minimize the average time duration between two consecutive observations of each target. 10 Jung and Sukhatme [63] proposed an algorithm based on treating the densities of robots and targets as properties of the environment in which they are embedded to improve the target tracking performance. Kamath et al. [3] studied the problem of motion planning and sensor assignment in a mobile sensor network for tracking multiple targets. The triangulation based tracking where two sensors merge their measurements to estimate the position of a target is considered. Kolling and Carpin [84] presented a distributed control algorithm for multiple targets surveillance by multiple robots. Their algorithm utilizes information from sensors and communication to predict the minimum time before a robot loses a target. Sensor network partitioning, a fundamental technique for sensor networks dealing with multiple targets tracking, has been studied by many researchers. The methods for network partitioning can be divided into centralized and decentralized. For centralized graph partition, there are several algorithms such as the decomposition scheme to partition a given graph into compactly connected two terminal subgraphs [85], a graph clustering method based on the minimum cuts within a graph [86] , a new graphical adaptation of the kmedoids algorithm [87] and the GirvanNewman method [88]. For distributed graph partition, Derbel and Mosbah [89] proposed a linear time distributed algorithm for decomposing a graph into a disjointed set of clusters. In [90, 91], Goebels et al. presented a neighborhoodbased strategy, a border switch strategy, and an exchange target strategy for the partitioning of large sets of agents into multiple groups. Derbel et al. [92] proposed efficient deterministic and randomized distributed algorithms for decomposing a graph into a disjointed set of connected clusters with small radius and few intercluster edges. Bettstetter [93] gave equations for the cluster density and cluster order of hemogeneously distributed nodes running the distributed mobile adaptive clustering algorithm. Virrankoski and Savvides [94] proposed a topology adaptive spatial clustering (TASC) for sensor networks. Durresi and Paruchuri [95] presented an adaptive clustering protocol for sensor network. This approach is based on the covering problem that aims at covering an area with minimum possible circular disk assuming ideal conditions. Meka and Singh [96] presented a 11 distributed algorithm called ELink based on a quadtree decomposition and a level by level expansion using sentinel sets. Belghith et al. [97] proposed a novel distributed clustering algorithm for ahhoc networks. Their algorithm is based on a synchronized and layered process. Summary of Cooperative Control In general, for cooperative control based on flocking control, most works focus on the configuration and topology of flocks. For single target tracking based on the flocking control, the literatures solve the problem of estimating the target’s state by using the distributed Kalman filter, or solve the problem of target tracking while a minority of agents in the network have the knowledge of the target. Their algorithms work well in free space, but in the obstacle space they have some limitations such as bad tracking performance, low speed and connectivity loss. To our best knowledge, for adaptive flocking control most of existing works focused on the coordination, formation and splitting/merging problems in both fixed and switching topologies. For multiple targets tracking all of reviewed literatures solve the tracking problem in both stationary and mobile sensor networks without paying attention to the network formation such as alattice. The problem of graph partitioning focuses on both centralized and decentralized methods, and most of them decompose the network based on the density of node’s distribution. This means that the size of subgraphs after decomposing are not predetermined. There are several open problems in cooperative control based on flocking control such as: • How to utilize the a minority of informed agents to lead the whole network to track the target while maintaining the connectivity. • How to control the size of the network in a decentralized and adaptive fashion in complex or changing environment while maintaining connectivity, tracking performance and similar formation. 12 • How to partition theMSN to track multiple moving target while minimizing the total energy consumption and time consumption. • How to design a flocking control algorithm to maintain the cohesion among agents while the measurements are corrupted by noise. 1.4.2 Cooperative Learning in MSNs Through cooperative learning agents in a MSN attempt via their interactions to jointly solve tasks or to maximize utility [98]. Cooperative learning has been studied by many researchers in recent years. The overview of cooperative learning including reinforcement learning, evolutionary computation, game theory, complex systems, agent modeling, and robotics can be found in [98, 99]. Reinforcement learning, one of the most powerful machine learning techniques, has been developed for multirobot systems that allow robots to learn cooperation [100, 101, 99, 102]. Reinforcement learning techniques for solving cooperative problems in teams of homogeneous robots such as the problem of maintaining a formation of mobile robots are studied in [103]. Cooperative reinforcement learning associating VQQL (Vector Quantization to Q Learning) is developed and applied for multirobot observation of multiple moving targets [104, 105, 101]. In their work, they solved two problems. The first one focuses on defining the reinforcement signal for each robot in a cooperative team to achieve a global goal. The second one is working with large domains, where the amount of data can be large and different in each moment of a learning step. As a result, their work achieved successful cooperative behaviours, but the learned behaviors are still discrete, and the learning space is still large. Other work on cooperative multirobot reinforcement learning [102] tried to reduce the learning space by using a hybrid state space that integrates a neural perception module and a progressive rescheduling algorithm. Their algorithm can online execute and learn through experience to adapt to environmental uncertainties and enhance performance. However, their work still relies on discrete and finite state/action spaces. 13 To our best knowledge most of existing works in the area of cooperative reinforcement learning assumes discrete and finite state/action spaces; therefore, it is difficult to directly apply reinforcement learning to most real world applications that inherently involve with continuous and infinite space. Furthermore, even if the states can be discretized, the learned behaviors are still discrete. In addition, the switching of discrete behaviors usually causes the control of the robots to become nonsmooth, which is undesirable in most applications. The open question is can we combine reinforcement learning and flocking control to create a general framework for intelligent robot systems that can allow (1) to generate efficient combination of high level behaviors (discrete states and actions) and low level behaviors (continuous states and actions) for multirobot cooperation; (2) and to conduct concurrent learning in a distributed fashion? 1.4.3 Cooperative Sensing in MSNs Cooperative sensing in MSNs has recently attracted researchers in control engineering [11, 12, 13], and it can be utilized in target tracking, and environmental mapping, monitoring, exploration and coverage. Cooperative sensing networks have been developed [106, 60, 13] for environmental sampling and exploring. In [106], underwater vehicles are deployed to measure temperature, currents, and other distributed oceanographic signals. The vehicles communicate via an acoustic local area network and coordinate their motion in response to local sensing information and to evolving environments. This mobile sensor network has the ability to sample the environment adaptively in space and time. By identifying evolving temperature and current gradients with higher accuracy and resolution than current static sensors, this technology could lead to the development and validation of improved oceanographic models. In [60], a class of underwater vehicles are used to obtain a sampling coverage over a large area. A cooperative control method is proposed to control vehicles to generate patterns on closed smooth curves. To further improve the cooperative sensing performance, 14 both the cooperative motion control and the cooperative sensing are integrated based on cooperative Kalman filter [13] to control the shape of the sensor node formation in order to minimize error in the estimates. Other significant works in cooperative sensing developing for environmental estimation, coverage and modeling can be found in [59, 11, 12, 62]. Cooperative sensing based on the gradient descent algorithms to obtain the optimal coverage is developed in [59]. For dynamic environment coverage, a control strategy based on the discrete Kalman filter is developed [11]. The approach relies on using the Kalman filter to estimate the field and on the filter’s prediction step to plan the vehicles’ next move to maximize the quality of the field estimate. In [62], an optimal filtering approach toward fusing local sensor data into a global model of the environment is developed. Their approach is based on the use of average consensus filters to distributedly fuse the sensory data through the communication network. Along with the consensus filters, the control laws are developed for mobile sensors to move to maximize their sensory information relative to current uncertainties in the model. Additionally, cooperative sensing for estimating the state of dynamic targets can be found in [57, 58]. The localization and tracking tasks of dynamic targets are addressed in [58]. In their work, the mobility of sensing agents is utilized to improve this quality of sensing. However, their gradient controller for cooperative sensing is designed in centralized way. The extension to make the control algorithm in [58] distributedly is proposed in [61], and both formation control and cooperative sensing are integrated to improve the sensing performance. Overall, all of the existing works in the area of cooperative sensing using MSNs focus on target(s) tracking, environment exploring, sampling, modeling, and coverage. The problem of environmental estimation and mapping based on multiagent cooperative and distributed sensing is still open research. 15 1.5 Organization of This Dissertation The rest of this dissertation is organized as follows. In Chapter 2 we first present the potential field based moving target tracking algorithm for a single mobile sensor and then extend it to multiple mobile sensors coordination based on flocking control. Chapter 3 describes the flocking control algorithm with a minority of informed agents; the adaptive flocking control algorithm for single target tracking and observing; and the algorithm for dynamic multiple targets tracking and observing, respectively. Chapter 4 presents the flocking control algorithms in noisy environments. Chapter 5 presents a hybrid system of flocking control and reinforcement learning for cooperative predator avoidance. Chapter 6 presents the cooperative sensing algorithm based on distributed consensus filters and flocking control, then extends to cooperative and active sensing algorithm. Conclusions and future work are given in Chapter 7. The flowchart of the organization of the dissertation is illustrated in Figure 1.2. Chapter 7 Conclusion and Future Work Chapter 1 Introduction Chapter 2 Flocking Control Chapter 3 Cooperative Control Based Flocking in NoiseFree Environments Chapter 4 Cooperative Control Based Flocking in Noisy Environments Chapter 5 Cooperative Learning Chapter 6 Cooperative and Active Sensing Figure 1.2: The organization of the dissertation. 16 CHAPTER 2 FLOCKING CONTROL FOR DYNAMIC TARGET TRACKING In this chapter, we first present a potential field approach for a single mobile sensor node to track a moving target. This establishes the background of the potential field method that is extended to multiple mobile sensor nodes. Then, we present the flocking control background which establishes three basic flocking rules: no collision among agents, velocity matching among agents, and flocking centering. We extend the existing flocking control to more constraints such as SingleCoM (Center of Mass) or MultiCoM to allow MSNs to track a target better in cluttered environments. In addition, stability analysis and simulation results with a comparison among the flocking control without CoM(NoCoM), SingleCoM and MultiCoM, respectively, are given. This chapter is organized as follows. Section 2.1 presents a potential field approach for one mobile sensor node to track a moving target. Section 2.2 presents flocking control for MSNs to track a moving target. Finally, Section 2.3 concludes this chapter. 2.1 Single Mobile Sensor Node and Dynamic Target Tracking 2.1.1 Problem formulation We consider a mobile sensor tracking a target which moves in a two dimensional environment. The dynamic equation of the mobile sensor is described as follows: ˙ qr = pr ˙ pr = ur. (2.1) Figure 2.1 shows a mobile sensor tracking a moving target with notations defined as 17 follows. q j q Figure 2.1: A mobile sensor tracks a moving target. qr ∈ R2, pr ∈ R2,qr ∈ R1 are position, velocity, and heading of the mobile sensor at time t, respectively. qmt ∈ R2, pmt ∈ R2,qmt ∈ R1 are position, velocity, and heading of the moving target at time t, respectively. qrt ,j are the relative position from the mobile sensor to the moving target and the angle of qrt , respectively. Assumption 1. We have the following assumption: The mobile sensor is equipped with sensors such as cameras, sonars or laser sensors and the associated algorithms to estimate the trajectory (position and velocity) of the moving target. Let qrt = [xrt , yrt ]T be the relative position between a mobile sensor and a moving target, then the relative velocity between them can be expressed as the derivative of relative position qrt . Hence the relative velocity vector is prt = q˙rt = [x˙rt , y˙rt ]T , where x˙rt and y˙rt 18 are computed as follows: ˙ xrt = kpmtkcos(qmt)−kprkcos(qr) ˙ yrt = kpmtksin(qmt)−kprksin(qr), (2.2) where k.k is the Euclidean distance. The tracking task is to make kqrtk approach to zero as soon as possible. This means that qr = qmt and pr = pmt . 2.1.2 Potential field approach To solve the problem of moving target tracking, we use the potential field approach which consists of an attractive potential function defined as follows [107, 108, 109]: Va = 0.5l1qT rtqrt , (2.3) here l1 is a positive scale factor for the attractive potential field function. In target tracking, we want the mobile sensor to follow a target. Hence, we only need the attractive potential field for the total potential field of qrt . V =Va = 0.5l1qT rtqrt . (2.4) The velocity pr of the mobile sensor is computed as pr = ˙ qr = ÑqrtV = l1qrt . (2.5) Equation (2.5) is with respect to the stationary target (pmt = 0) (conventional potential field method). While for a moving target (pmt 6= 0) we compute the velocity pr of the mobile sensor as follows [107]: pr = pmt +l1qrt . (2.6) Equation (2.6) is equivalent to the following equations [107]: kprksin(qr−j) = kpmtksin(qmt −j), (2.7) 19 kprk = (kpmtk2+2l1kqrtkkpmtkcos(qmt −j)+l21 kqrtk2)1/2. (2.8) Assumption 2. The velocity of the moving target is limited by its maximum velocity pmax mt . From this assumption we have: kprk = min(kpmax mt k, (kpmtk2+2l1kqrtkkpmtk ×cos(qmt −j)+l21 kqrtk2)1/2). (2.9) By dividing both sides of Equation (2.7) with kprk and taking arcsin we obtain the heading or direction of the mobile sensor as qr = j+arcsin(kpmtksin(qmt −j) kprk ). (2.10) The velocity of the mobile sensor in a two dimensional space is obtained as Equation (2.11). pr = [kprkcos(qr), kprksin(qr)]T . (2.11) Theorem 1. Equation (2.6) allows the mobile sensor (qr, pr) to track a moving target (qmt , pmt ). Proof : We choose a Lyapunov function as follows: L =Va = 0.5l1qT rtqrt = 0.5l1kqrtk2. (2.12) This function is positive definite, and the derivative of L is given by ˙L = ¶L ¶qrt ˙ qrt = ¶L ¶qrt prt , (2.13) where the relative velocity between the mobile sensor and the moving target is designed as prt = −ÑqrtVa = −ÑqrtL. Hence, Equation (2.13) is rewritten as follows: ˙L = − ¶L ¶qrt ÑqrtL = −l21 kqrtk2 = −2l1 1 2 l1kqrtk2 = −2l1Va < 0. (2.14) 20 Since the Lyapunov function L is considered the same as the attractive potential field function Va, Equation (2.14) is rewritten as follows: V˙a = −2l1Va. (2.15) Solving this equation we get the solution as follows: Va =Va(0)e−2l1t (2.16) here Va(0) is the value of Va at t =0. This solution shows that Va and kqrtk converge to zero with the converging rate l1, or the position and velocity of the mobile sensor asymptotically converges to those of the moving target after a certain time (t > 0). 2.1.3 Simulation results In this section we test our theoretical results with a circular trajectory of the moving target. Parameters used in this simulation are specified as follows: Parameters of circle trajectory: qmt = [210−70cos(t), 80+70sin(t)]T . Parameters of moving target: pmt = [3, 3]T , pmax mt = [55, 55]T , and qmt = p2 −t. Initial parameters of the mobile sensor: qr(0)=[0, 0]T , pr(0)=[0, 0]T , and qr(0)= p2 , and other parameters: l1 = 9, 0 ≤ t ≤ 5. Figure 2.2 represents the result of one mobile sensor tracking the target moving in a circular trajectory. At the beginning, the position of the sensor is far from the target, but after certain time the sensor can catch up the moving target and then continue to track the target. This confirms the theory stated in Theorem 1. Figure 2.3 shows the tracking performance (position error between the mobile sensor and the moving target). As can be seen in this figure, after 33 iterations the mobile sensor tracks a moving target very well with very small error. 21 0 10 20 30 40 50 60 70 80 −5 0 5 10 15 20 25 30 35 40 45 50 x (pos) y (pos) Initial position of robot (blue triangle) Initial position of target (red solid circle) Ending positions of mobile sensor and target Moving target direction (red line) Mobile sensor trajectory (blue dot line) Figure 2.2: The mobile sensor tracks the target moving in a circular trajectory. 0 20 40 60 80 100 120 −10 0 10 20 30 40 50 60 iterations norm(qmt−qr) Figure 2.3: Tracking error between the mobile sensor and the moving target. 22 2.2 Flocking Control for Single Target Tracking and Observing In this section we will extend the potential field approach to multiple mobile sensor nodes (agents) based on flocking control. The artificial potential field is created to generate a pairwise attractive/repulsive force to control agents to form a lattice formation while tracking the target. However, with this type of traditional flocking control [23], there are still some problems in cluttered environments where the agents usually get stuck behind the obstacles and sometimes can not follow the target [23]. To handle this problem we present new approaches to flocking control of multiagent systems to track a moving target while avoiding obstacles. The main motivation of these approaches is to make the CoM (Center of Mass) of the network track the moving target better in cluttered environments where the traditional flocking control algorithms [23], [17], [34], [35], [46] have poor tracking performance. In our methods all mobile agents can surround the target closely in the obstacle space. This will allow the network to observe and recognize the target more accurately. Specifically, in our SingleCoM algorithm, the center of mass of positions and velocities of all mobile agents in the network is controlled to track a moving target. This algorithm works well in small networks, but it has limited scalability in large networks. In contrast with the Single CoM algorithm, we proposed another flocking control algorithm called MultiCoM where the center of mass of positions and velocities of each agent’s local neighborhood, respectively is controlled to track a moving target. This algorithm allows agents to perform better in large networks in a distributed fashion. 2.2.1 Flocking control background To describe a dynamic topology of flocks or swarms we consider a dynamic graph G(J,E) consisting of a vertex set J = {1,2...,n} and an edge set E ⊆ {(i, j) : i, j ∈ J, i 6= j}. In this topology each vertex denotes one member of the flock, and each edge denotes the communication link between two members. 23 Let qi, pi ∈ Rm (m = 2,3) be the position and velocity of node i, respectively. We know that during the motion of sensors, the relative distance between them may change, hence the neighbors of each sensor also change. Therefore, we can define a set of neighborhood of sensor i at time t as follows: Ni(t) = j ∈ J : kqj −qik ≤ r, J = {1,2, ...,n}, i 6= j (2.17) Here, r is an interaction range (radius of the neighborhood circle in the case of two dimensions, m = 2, or radius of the neighborhood sphere in the case of three dimensions, m = 3), and k.k is the Euclidean distance. In this chapter we consider n sensors moving in an m dimensional Euclidean space. We address the motion control problem for a group of sensors with the objective of dynamic target(s) tracking. We assume that each sensor has a large enough communication range to allow it to communicate with others and a large enough sensing range to allow it to sense the target. We also assume that each sensor is equipped with sonar or laser sensor that allows it to estimate the position and velocity of the target. The dynamic equation of each sensor is described as follows: ˙ qi = pi ˙ pi = ui, i = 1,2, ...,n (2.18) The geometry of a flock ismodeled by an alattice [23] that has the following condition: kqi−qjk = d, j ∈ Ni (2.19) here d is a positive constant indicating the distance between sensor i and its neighbor j. The configuration which approximately satisfies the condition (2.19) is called a quasi alattice, i.e. (kqi−qjk−d)2 < d2, with d << d. To construct a collective potential (discuss later) that is differentiable at singular configuration (qi = qj), the set of algebraic constrains is rewritten in term of s  norm (defined in (2.24)) as follows: kqj−qiks = da, j ∈ Ni (2.20) 24 In [23], OlfatiSaber proposed his control law for flocking of multiple mobile agents with obstacle avoidance. This algorithm consists of three components as follows: ui = f a i + f b i + f g i (2.21) The first component of Equation (2.21) f a i which consists of a gradientbased component and a consensus component (more details about these components see [73], [50], [51]) is used to regulate the gradient of potentials (impulsive or attractive forces) and the velocity among sensors. f a i = ca1 å j∈Na i fa(kqj−qiks)ni j+ca2 å j∈Na i ai j(q)(pj− pi) (2.22) where each term in (2.22) is computed as follows [23]: The set of a neighbors at time t is Na i (t) = j ∈ J : kqj −qik ≤ r, J = {1,2, ...,n}, i 6= j (2.23) The s−norm, k.ks, of a vector is a map Rm =⇒R+ defined as kzks = 1 e [ q 1+ekzk2−1] (2.24) here e is the positive constant. The action function fa(z) vanishing for all z ≥ ra with ra = krks is used to construct a smooth pairwise attractive/repulsive potential function, ya(z) = R z da fa(s)ds. This action function fa(z) is defined as follows: fa(z) = rh(z/ra)f(z−da) (2.25) where f(z) is the uneven sigmoidal function f(z) = 0.5[(a+b)s1(z+c)+(a−b)] (2.26) here s1(z) = z/√1+z2, and parameters 0 < a ≤ b, c = a−b/√4ab to guarantee f(0) = 0, and constraints da = kdks with d = r/k for k being the scaling factor (in the simulations in this dissertation k = 1.2). 25 The bump function rh(z) with h ∈ (0,1) rh(z) = 1, z ∈ [0,h) 0.5[1+cos(p( z−h 1−h))], z ∈ [h,1] 0, otherwise. (2.27) The vector along the line connecting qi and qj is defined as ni j = (qj−qi)/ q 1+ekqj−qik2 (2.28) The adjacency matrix ai j(q) is defined as ai j(q) = rh(kqj−qiks/ra), i f j 6= i 0, i f j = i (2.29) The second component of Equation (2.21) f b i is used to control the mobile sensors to avoid obstacles, f b i = cb1 å k∈Nb i fb(k ˆ qi,k−qiks) ˆ ni,k+cb2 å k∈Nb i bi,k(q)( ˆ pi,k− pi) (2.30) where the set of b neighbors (virtual neighbors) of sensor i at time t with k obstacles is Nb i (t) = n k ∈ Jb : k ˆ qi,k−qik ≤ r′,Jb = {1,2, ..., k} o (2.31) here r′ is selected to be less than r, in our simulations r′ = 0.6r. Jb is a set of obstacles. ˆ qi,k, ˆ pi,k are the position and velocity of sensor i projecting on the obstacle k, respectively. Similar to vector ni j defined in Equation (2.28), vector ˆ ni,k is defined as ˆ ni,k = ( ˆ qi,k−qi)/ q 1+ek ˆ qi,k−qik2. (2.32) The adjacency matrix bi,k(q) is defined as bi,k(q) = rh( ˆ qi,k−qiks/db) (2.33) where db = kr′ks. 26 The repulsive action function of b neighbors is defined as fb(z) = rh(z/db)(s1(z−db)−1). (2.34) Now we want to show more details on how to find out b neighbors ( ˆ qi,k, ˆ pi,k) generated by each a agent. Firstly, we have the following assumption regarding the obstacles. Assumption 3. Obstacles are the convex regions in Rm with boundaries being smooth manifolds. Based on this assumption, we can choose obstacles to be circles (two dimensions, m = 2) or spheres (three dimensions, m = 3) with radius Rk at center yk. We project each sensor to obstacles and find out which shadow of that sensor on obstacles satisfies the condition k ˆ qi,k−qik≤r′, and the obtained results of ˆ qi,k are neighbors of sensor i. Equation (2.35) illustrates the projection method to find the positions and velocities of b neighbors generated by sensor i. ˆ qi,k = μqi+(1−μ)yk, ˆ pi,k = μPpi (2.35) where μ= Rk/kqi−ykk. P=I−akaTk is the projection matrix with ak = (qi−yk/kqi−ykk) and an unit matrix or identity matrix I. Example 1. In this case, we have three obstacles O1, O2 and O3 as shown in Figure 2.4. After projecting asensor i on all obstacles, we see that only two shadows (bneighbors) on the obstacles O1 and O2 satisfying the condition (2.23). The obstacle O3 is out of active range r′, hence there is no shadow of asensor i on it. Consequently, we found out two bneighbors ( ˆ qi,1, ˆ pi,1) and ( ˆ qi,2, ˆ pi,2) of asensor i. The third component of (2.21) f g i is a distributed navigational feedback. f g i = −cg 1s1(qi−qg)−cg 2(pi− pg) (2.36) where s1(qi −qg) = (qi −qg)/ q 1+kqi−qgk2, and the g  sensor (qg, pg) is the virtual leader (more information of virtual leader, see [110]) defined as follows ˙ qg = pg ˙ pg = fg(qg, pg) (2.37) 27 Figure 2.4: The projection method for finding the positions and velocities of b neighbors of each a  sensor. The constants of three components used in (2.21) are chosen as ca1 < cg 1 < cb1 , and cn2 = 2 p cn1 . Here cn h are positive constants for ∀h = 1,2 and n = a,b, g. 2.2.2 Algorithm description In this section, we will extend the above described flocking algorithm with obstacle avoidance [23]. Two problems, named SingleCoM and MultiCoM, respectively, will be investigated. In the SingleCoM problem, the CoM of positions and velocities of all sensors is controlled to track the moving target. In this case, each sensor need to know the positions and velocity of all other sensors, or it requires the global knowledge of the whole network. To address the scalability problem the MultiCoM (CoM of positions and velocities of each sensor’s local neighborhood, respectively) problem is studied, where each sensor only need to know the positions and velocity of its neighbors. In the following algorithms we assume if one of the sensors in the network can estimate the position and velocity of the target, it will broadcast this obtained information to all other nodes. Consequently all sensors in the network can get the knowledge of target. 28 SingleCoM tracking Firstly, based on OlfatiSaber’s flocking algorithm we design an algorithm with a dynamic gagent. In this scenario, the dynamic gagent is considered as the moving target. ui = ca1 å j∈Na i fa(kqj−qiks)ni j+ca2 å j∈Na i ai j(q)(pj− pi) +cb1 å k∈Nb i fb(k ˆ qi,k−qiks) ˆ ni,k+cb2 å k∈Nb i bi,k(q)( ˆ pi,k− pi) −cmt 1 (qi−qmt)−cmt 2 (pi− pmt ) (2.38) here the pair (qmt , pmt) is the position and velocity of the moving target, respectively, and cmt 1 , cmt 2 are positive constants, and cmt 2 = 2 p cmt 1 . By observing the control protocol (2.38), we see that the CoM is difficult to reach the target in the presence of obstacles. This creates the difficulty for sensors to track and observe the target. Therefore this protocol should be extended with more constraint on the CoM as follows: ui = f a i + f b i + f mt (2.39) where f mt is a tracking feedback applied to sensor i by a moving target with position and velocity (qmt , pmt), respectively. f mt i = −cmt 1 (qi−qmt)−cmt 2 (pi− pmt) −cmt 1 (q−qmt)−cmt 2 (p− pmt) (2.40) where the pair (q, p) is the center of mass (CoM) of positions and velocities of all sensors, respectively, as defined in (2.41). q = 1 n åni =1 qi p = 1 n åni =1 pi. (2.41) The SingleCoM tracking is illustrated in Figure 2.5 (a). The CoMof the whole network (red dot) is created to track the target. 29 Figure 2.5: (a) A mobile sensor network with a single CoM (SingleCoM), (b) A mobile sensor network with multiple CoMs (MultiCoM). Consequently, the extended control protocol (2.39) is explicitly specified as follows: ui = ca1 å j∈Na i fa(kqj−qiks)ni j+ca2 å j∈Na i ai j(q)(pj− pi) +cb1 å k∈Nb i fb(k ˆ qi,k−qiks) ˆ ni,k+cb2 å k∈Nb i bi,k(q)( ˆ pi,k− pi) −cmt 1 (qi−qmt)−cmt 2 (pi− pmt ) −csc 1 (q−qmt)−csc 2 (p− pmt ) (2.42) here csc 1 , csc 2 are positive constants. In control protocol (2.42), each mobile sensor at each time t need to know the position and velocity of all other sensors for computing the CoM (q, p). This means that this protocol is limited by the number of sensors, or the scalability is limited because at each time t all other sensors have to send their positions to sensor i. Hence the communication problem is a big challenge and need to be considered when implementing this protocol in real sensor networks. MultiCoM tracking To make the algorithmscalable we implement a distributed flocking algorithmcalledMulti CoM tracking in which the CoM of each sensor’s local neighborhood is controlled to track the target. TheMultiCoM tracking is illustrated in Figure 2.5 (b). In this figure each mobile 30 sensor creates its own CoM, as a result multiple CoMs are created as a virtual network to track a taeget. The MultiCoM tracking algorithm is presented as follows. ui = ca1 å j∈Na i fa(kqj−qiks)ni j+ca2 å j∈Na i ai j(q)(pj− pi) +cb1 å k∈Nb i fb(k ˆ qi,k−qiks) ˆ ni,k+cb2 å k∈Nb i bi,k(q)( ˆ pi,k− pi) −cmt 1 (qi−qmt)−cmt 2 (pi− pmt ) −cmc 1 (q(Na i ∪{i})−qt)−cmc 2 (p(Na i ∪{i})− pt ), (2.43) here (cmc 1 , cmc 2 ) are the positive constants, and the pair (q(i+Na i ), p(i+Na i )) is defined as (2.44). q(Na i ∪{i}) = 1 Na i ∪{i} åNa i ∪{i} i=1 qi p(Na i ∪{i}) = 1 Na i ∪{i} åNa i ∪{i} i=1 pi, (2.44) here Na i ∪{i} is the number of agents in agent i’s local neighborhood including agent i itself. In control protocol (2.43), each mobile sensor only need local knowledge, or it means that each sensor only requires the position and velocity knowledge of itself and its neighbors. In alattice configuration [23] the maximum number of each sensor’s neighbors is 6. Therefore this protocol can scale up to lager mobile sensor networks. 2.2.3 Stability analysis In this subsection we will analyze the stability of our algorithms, flocking control with SingleCoM and MultiCoM, respectively, in free space, and we will explain why the tracking performance in the presence of CoM constraint is better than without CoM constraint in obstacle space. Theorem 2. In free space, by controlling the CoM based on the control protocol (2.42), the CoM of positions and velocities of all sensors in the network will exponentially converge to the target. In addition, the formation of all mobile sensors will maintain in the process of the moving target tracking. 31 Proof : In free space, this means that åk∈Nb i fb(k ˆ qi,k−qiks) = 0. Hence we can rewrite control protocol (2.42) with ignoring constants cn h (for ∀h = 1,2 and n = a,b) as follows: ui = − å j∈Na i Ñqiya(kqj−qiks)+ å j∈Na i ai j(q)(pj− pi) −cmt 1 (qi−qmt)−cmt 2 (pi− pmt ). −csc 1 (q−qmt )−csc 2 (p− pmt). (2.45) where ya(z) = R z da fa(s)ds is the pairwise attractive/repulsive potential function. From (2.45), we can compute the average of the control law u as follows: u = 1 n nå i=1 ui = 1 n nå i=1 (− å j∈Na i Ñqiya(kqj−qiks)+ å j∈Na i ai j(q)(pj− pi)) −(cmt 1 +csc 1 )(q−qmt)−(cmt 2 +csc 2 )(p− pmt). (2.46) Obviously, we see that the pair (ya,a(q)) is symmetric. Hence we can rewrite (2.46) as: u = −(cmt 1 +csc 1 )(q−qmt)−(cmt 2 +csc 2 )(p− pmt ) (2.47) Equation (2.47) implies that ˙q = p ˙p = −(cmt 1 +csc 1 )(q−qmt)−(cmt 2 +csc 2 )(p− pmt ). (2.48) The solution of (2.48) indicates that the position and velocity of the CoM will exponentially converge to those of the target. The formation or collisionfree and velocity matching among mobile sensors will be maintained in the free space tracking because the gradientbased term and the consensus term are considered in this situation. For the MultiCoM flocking control algorithm, we have the following statement for the stability properties. In cluttered environments, consider a system of n mobile agents, that have dynamics (2.18) and are controlled by the MultiCoM flocking algorithm (2.43). Then based on our observations which are shown in the simulation results we see that: 32 1. The CoM of positions and velocities of all agents in the network will exponentially converge to the target in the free space. 2. The error between the CoM’s position and the target’s position is reduced in the obstacle space. The results of the MultiCoM flocking algorithm are similar to the SingleCoM flocking algorithm. However, the benefit of the MultiCoM flocking algorithm is that each agent is controlled locally instead of globally as in the SingleCoM flocking algorithm. 2.2.4 Simulation results In this section we test our theoretical results in simulation with different trajectories of the moving target. First of all we test the case where target moves with a sine wave trajectory. Parameters used in this simulation are specified as follows:  Parameters of flocking: number of sensors = 120; the initial positions of sensors are randomly distributed in a box with a size of [0 90]x[0 90]; the initial velocities of sensors are set to zero. Parameters a = b = 5; the interaction range r = 1.2d = 9; e = 0.1 for the snorm; h = 0.2 for the bump function (fa(z)); h = 0.9 for the bump function (fb(z)).  Parameters of target movement: The target moves in the sine wave trajectory: qmt = [50+35t, 295−35sin(t)]T with 0 ≤t ≤ 8.5, and pmt = (qmt(t)−qmt(t−1))/Dt with Dt = 0.002. Second we test the case where the target moves in a circle trajectory. Parameters used in this simulation are specified as follows:  Parameters of flocking: parameters used in this case are the same with those in the sine trajectory case.  Parameters of target movement: The target moves in a circle trajectory: qmt = [310− 160cos(t), 255+160sin(t)]T with 0 ≤ t ≤ 5, and pmt = (qmt(t)−qmt(t −1))/Dt . To compare three algorithms NoCoM (2.38), SingleCoM (2.42) andMultiCoM (2.43) we use the same initial state (position and velocity) of mobile sensors. Figures 2.6 repre 33 0 50 100 150 200 250 300 350 400 450 500 550 50 100 150 200 250 300 350 400 450 x (pos) y (pos) Begin random initial positions of mobile sensors 1. Moving target (red line) 2. CoM of positions (black dots) All mobile sensors formed a connected network End positions of mobile sensors Mobile sensors are avoiding obstacles Obstacle O1 Obstacle O2 0 50 100 150 200 250 300 350 400 100 150 200 250 300 350 400 x (pos) y (pos) Mobile sensors are avoiding obstacles Obstacle O1 Obstacle O2 End positions of mobile sensors All mobile sensors formed a connected network Begin random initial positions of mobile sensors 1. Moving target (red line) 2. CoM of positions (black dots) 0 50 100 150 200 250 300 350 400 100 150 200 250 300 350 400 x (pos) y (pos) Begin random initial positions of mobile sensors Obstacle O1 Obstacle O2 Mobile sensors are avoiding obstacles End positions of mobile sensors All mobile sensors formed a connected network 1. Moving target (red line) 2. CoM of positions (black dots) 0 50 100 150 200 250 300 350 400 100 150 200 250 300 350 400 x (pos) y (pos) Begin random initial positions of mobile sensors All mobile sensors formed a connected network Obstacle O2 Obstacle O1 End positions of mobile sensors Mobile sensors are avoiding obstacles 1. Moving target (red line) 2. CoM of positions (black dots) 0 50 100 150 200 250 300 350 400 450 500 550 50 100 150 200 250 300 350 400 450 x (pos) y (pos) 1. Moving target (red line) 2. CoM of positions (black dots) All mobile sensors formed a connected network Mobile sensors are avoiding obstacles Obstacle O2 Obstacle O1 Begin random initial positions of mobile sensors End positions of mobile sensors 0 50 100 150 200 250 300 350 400 450 500 550 50 100 150 200 250 300 350 400 450 x (pos) y (pos) All mobile sensors formed a connected network 1. Moving target (red line) 2. CoM of positions (black dots) Begin random initial positions of mobile sensors End positions of mobile sensors Mobile sensors are avoiding obstacles Obstacle O1 Obstacle O2 Figure 2.6: Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, forming a network, avoiding obstacles, and at the ending positions, respectively. (a, b, c) the mobile sensor network is tracking the target moving in the sine wave trajectory, and (a’, b’, c’) the mobile sensor network is tracking the target moving in the circle trajectory using flocking control algorithms with NoCoM (2.38), SingleCoM (2.42) and MultiCoM (2.43), respectively. 34 0 500 1000 1500 2000 2500 3000 3500 4000 4500 0 50 100 150 iterations q mt mean(q) 0 500 1000 1500 2000 2500 3000 3500 4000 4500 0 50 100 150 iterations q mt mean(q) 0 500 1000 1500 2000 2500 3000 3500 4000 4500 0 50 100 150 iterations qmtmean(q) 0 500 1000 1500 2000 2500 3000 0 50 100 150 iterations q mt mean(q) 0 500 1000 1500 2000 2500 3000 0 50 100 150 iterations qmtmean(q) 0 500 1000 1500 2000 2500 3000 0 50 100 150 iterations q mt mean(q) Figure 2.7: Position errors between the CoM’s positions and the moving target in the sine wave trajectory (a, b, c) and the circle trajectory (a’, b’, c’) using flocking control algorithms with NoCoM (2.38), SingleCoM (2.42) and MultiCoM (2.43), respectively. sents the snapshots of mobile agents tracking the target moving in the sine wave and circle trajectories using three algorithms, NoCoM, SingleCoM and MultiCoM, respectively. Figures 2.7 represents the error between the CoM’s positions and the target (tracking performance) in the sine wave and circle trajectories using three algorithms, NoCoM, Single CoM and MultiCoM, respectively. We see that the results of tracking performance in Figure 2.7 (b, b’, c, c’) for both trajectories of the target using SingleCoM and MultiCoM algorithms, respectively, are better than that in Figure 2.7 (a, a’) using NoCoM algorithm. In addition, we can see the snapshots of mobile robots avoiding obstacle taken at the same time, but in Figures 2.6 (b, b’, c, c’) more agents (sensors) passed through the narrow space between two obstacles than that in Figures 2.6 (a, a’). This means that the CoM in the algorithms SingleCoM and MultiCoM (Figures 2.7 b, b’, c, c’) is closer to the target than that in the NoCoM algorithm (Figures 2.7 a, a’). 35 2.3 Summary This chapter first studied the problem of single moving target tracking using a mobile robot based on the artificial potential field approach. The simulation results were collected to show the effectiveness of the proposed approach. Then, this approach is extended to target tracking in mobile sensor networks based on flocking control. We designed a flocking control algorithm with SingleCoM and MultiCoM to enable mobile sensors to track and observe the moving target more effectively while maintaining their formation and no collision among them. We prove that the CoM of positions and velocities of all mobile sensors exponentially converges to the target. By controlling the CoM explicitly, the mobile sensor network can track and observe the moving target better. This means that all mobile sensors in the network can surround the target closely which will allow them to see the target easily for recognition purpose. In addition, flocking control with NoCoM, flocking control with SingleCoM, and flocking control with MultiCoM are compared. Several simulations are conducted with different target trajectories to demonstrate our theoretical results. 36 CHAPTER 3 COOPERATIVE CONTROL BASED FLOCKING FOR MSNs IN NOISEFREE ENVIRONMENTS In this chapter we study the cooperative control for MSNs in noisefree environments in which each mobile sensor node can sense the location and velocity of itself and its neighbors precisely. Three cooperative control algorithms are proposed. The first one is the flocking control algorithm for MSNs to track a target in the case of a small subset of informed agents while maintaining the network connectivity. The second one is the adaptive flocking control for MSNs to track a moving target in complex environments where the MSNs have to change the size of their formation to adapt to the environment in order to maintain the network connectivity and similar topology. The last one is the multiple dynamic target tracking algorithm which is designed for MSNs to track multitarget simultaneously. This chapter is organized as follows. Section 3.1 presents the decentralized flocking control with a minority of informed agents. Section 3.2 presents the adaptive flocking control for MSNs to track a moving target. Section 3.3 describes multitarget tracking algorithm for MSNs. Finally, Section 3.4 concludes this chapter. 3.1 Decentralized Flocking Control with a Minority of Informed Agents In this section we study the flocking control in the case of a small subset of informed agents. In nature, only few agents in the group have information of the target, such as knowledge about the location of a food source, or of a migration route, but they can still flock together in a group to find the source of food (target) based on local information. 37 Inspired by this natural phenomenon, a flocking control algorithm is designed to coordinate the motion of multiple agents. Based on our algorithm, all agents can form a network, maintain connectivity and track the target even only a few agents know the information of the target. 3.1.1 Introduction Early work on flocking control includes [37, 38, 23]. Tanner et al. [37], [38] studied flocking control of a system of multiple mobile agents with double integrator dynamics in the case of fixed and dynamic topologies. In [23], the theoretical framework for design and analysis of distributed flocking algorithm was proposed. This established a foundation for flocking control design for a group of agents. As an extension of the flocking algorithm in [23], flocking control of agents with a virtual leader in the case of a minority of informed agents and varying velocity of virtual leader was presented in [46]. However, in their work the network can not maintain its connectivity because some agents may fall out of the network. In this section we study how to utilize a minority of informed agents to lead the whole network to track the target while maintaining the connectivity. The main differences with the above related work are: 1. We adopt a target navigation term in order to reduce the large tracking force at the initial tracking time so that the connectivity is maintained. 2. We use a damping force term to reduce the tracking overshoot. Overall, we propose a new flocking control algorithm that allows the flock to preserve connectivity, avoid collision, and track the target without overshooting. We demonstrate that by applying our algorithm the agents can flock together and maintain connectivity better compared to existing flocking control algorithms. Most of existing flocking control algorithms [37, 38, 23] are designed under the assumption that all agents need information of the position and velocity of the target in order 38 to flock together. However, in reality this assumption is not valid. It can be seen in many cases that only very few agents have information of the target due to their limited sensing range. For example, in fish schools and bird flocks, only some agents have knowledge about the location of a food source, or of a migration route [41, 42]. Motivated by these observations we will study how to design a distributed flocking control algorithm which can still maintain good tracking performance and connectivity when only few agents have information of the target. 3.1.2 Decentralized Flocking Control with a Minority of Informed Agents (MIA) In this subsection, we design a distributed flocking control algorithm for multiagent systems in the case that only a few agents are informed with the position and velocity of the target. We call these agents as informed agents. Let us define NI as a subset of informed agents and NUI as a subset of uninformed agents with NI << NUI . Hence we have NI ∪NUI = N, here N is the set of all agents (uninformed and informed agents). Paper [46] proposed the following flocking control algorithm based on the algorithm (2.38): ui = å j∈Ni fa(kqj−qiks)ni j+ å j∈Ni ai j(q)(pj− pi) −ct 1(qi−qt)Ii−ct 2(pi− pt )Ii. (3.1) here if Ii = 1 the agent i has information (position and velocity) of the target. Otherwise Ii = 0 agent i does not have information of the target. We implemented the algorithm (3.1) in which we let some agents closest to the target have the information (position and velocity) of the target. The result is shown in Figure 3.1. In this figure we clearly see that the network is broken, and only the agents which have information of the target can track the target. Additionally, we find that the target tracking performance has big overshoot. In order to solve these two problems we introduce two 39 0 50 100 150 200 250 300 350 400 450 500 100 150 200 250 300 350 400 450 500 Y (POS) X (POS) Initial positions of 50 agents Ony six informed agents can track the target Target Six informed agents can not drag the whole network to track the target (the network is broken) 1. Blue Squares: Informed agents 2. Purple Trianges: Noninformed agents Figure 3.1: Snapshots of the agents when applying the flocking control algorithm (3.1). We select 6 out of 50 agents which are closest to the target to have the information (position and velocity) of the target. terms. The first term is a navigation term, and the second one is a damping force term. The main purpose of the navigation term is to maintain the connectivity among agents, and the purpose of the damping force term is to reduce the tracking overshoot. Navigation Term The navigation term allows the agents to stay together. The main idea behind this term is that if we let the informed agents keep strong cohesion to uninformed agents at the initial time of the target tracking process, the connectivity can be maintained. In order to do this, we have to reduce the initial momentum of the attractive force to the target for the informed agents. This means that we should have small attractive force at the initial time when the distance between the informed agent and the target is large. Based on this analysis we design the navigation term as shown in Algorithm 1. In this algorithm the constant K1 chosen between 0.9 and 1 is to ensure that a small attractive force is applied at the initial 40 time of the target tracking process. The weights, K2 kqin f i (t)−qt (t)k and K3 kqin f i (t)−qt (t)k are designed so that the attractive force is small enough at the initial time, and then it becomes bigger when the distance kqin f i (t)−qt(t)k decreases. Algorithm 1: Design of the Navigation Term for each informed agent j, j ∈ NI do if kqin f i (t)−qt(t)k > K1kqin f i (0)−qt(0)k then f t j = − K2 kqin f i (t)−qt(t)k (qin f j −qt) − K3 kqin f i (t)−qt(t)k (pin f j − pt ) here, 0.9 < K1 < 1, K2 > 0 and K3 > 0, else f t i = −ct 1(qin f j −qt)−ct 2(pin f j − pt ) end end Damping Force Term Since only the informed agents NI have the information of the target, the damping force can be only applied to these agents. The idea behind this damping force is to reduce the tracking overshoot when the informed agents are close to the target. That is, the damping force for the informed agents is only effective if the distance between the informed agent and the target is less than a certain threshold. This threshold is designed based on the active range r. This means that when the target is inside the active range of the informed agent j the damping force f dam j is applied, otherwise f dam j = 0. In order to do that the constant K4 is used (0 < K4 < 1). When the damping force f dam j is applied, the informed agent j will reduce its speed gradually to approach the target. Hence, the tracking overshoot is reduced. 41 Algorithm 2: Design of the Damping Force Term for each informed agent j, j ∈ NI do if kqin f i (t)−qt(t)k < K4r then f dam j = −Kdampin f j here, 0 < K4 < 1 and Kdam > 0, else f dam j = 0 end end Overall, the damping force is designed in Algorithm 2. Finally the whole decentralized flocking control algorithm is proposed in Algorithm 3. In this algorithm we have two options of the initial network configuration, and both options are to allow the network of agents to be connected at the beginning. 42 Algorithm 3: Decentralized Flocking Control Algorithm with a MIA Input : Position and velocity of each agent (qi, pi); Position and velocity of the target (qt , pt ) for the informed agents (NI). Output: Control law for each agent ui Initialization phase: Option 1. Deploy the agents to form a connected network; Option 2. All agents are programmed based on flocking algorithm (2.38) to go to the rendezvous point so that they can form a connected network. Implementation phase: for each agent i do Compute: f a i = åj∈Ni fa(kqj−qiks)ni j+åj∈Ni ai j(q)(pj− pi). end for each informed agent j, j ∈ NI do if kqin f i (t)−qt(t)k > K1kqin f i (0)−qt(0)k then f t j = − K2 kqin f i (t)−qt(t)k (qin f j −qt)− K3 kqin f i (t)−qt(t)k (pin f j − pt ), else f t i = −ct 1(qin f j −qt)−ct 2(pin f j − pt ). end if kqin f i (t)−qt(t)k < K4r then f dam j = −Kdampin f j , (0 < K4 < 1 and Kdam > 0). else f dam j = 0. end end for each uninformed agent k, k ∈ NUI do f dam k = 0, ftk = 0. end Update the control law for each agent i: ui = f a i + f dam i + f t i . 43 3.1.3 Experimental and Simulation Results In this section we test our proposed flocking control Algorithm 3 and compare it with the existing flocking control algorithm (3.1) in the case of a minority of informed agents. First we test our algorithm with 7 real robots. Then to show the effectiveness and the scalability of our algorithm we test it with 50 robots in simulation. In addition, we show a metric to evaluate the network connectivity of our algorithm and the existing algorithm. Experimental Setup In this experiment we use 7 Rovio robots [111] that have omnidirectional motion capability. Basically, these robots can freely move in 6 directions. The dynamic model of the Rovio robot can be approximated by Equation (2.18). However, the accuracy of the localization of the Rovio robot is low, and the robot does not have any sensing device to sense the pose (position and velocity) of its neighbors or the obstacles. Hence we use a VICON motion capture system [1] in our lab (Figure 3.2) that includes 12 cameras to track objects. This tracking system can give the location and velocity of each moving object with over 95 percent of accuracy. Figure 3.2: Motion Capture System from VICON [1] in the experimental setup. We use the following parameters: 44  Parameters of flocking: a = b = 5; d = 600mm; the scaling factor kc = 1.2; the active range r = kc.d; e = 0.1 for the s norm; h = 0.2 for the bump function (fa(z)); h = 0.9 for the other bump function (fb(z)).  Parameters of the target: The target location is at [0, 500mm] for the experiment. The velocity vector pt = [5, 5]. Simulation Setup In the simulation 50 agents are randomly distributed in the square area of 120 × 120 size, and we use the following parameters:  Parameters of flocking: the constants a = b = 5 for the sigmoidal function (f(z)); the distance among agents d = 16 units; the scaling factor kc = 1.2; the active range r = kc ∗d; e = 0.1 for the s norm; h = 0.2 for the bump function (fa(z)); h = 0.9 for the other bump function (fb(z)).  Parameters of the target: The target location is at [450, 450]. The velocity vector pt = [5, 5]. Network Connectivity Evaluation To evaluate the the network connectivity maintenance, first we know that the link (connectivity) between node i and node j is maintained if the distance 0 < kqi −qjk ≤ r. Otherwise this link is considered broken. For graph connectivity, a dynamic graph G(J,E) is connected at time t if there exists a path between any two vertices. An example of graph connectivity is shown in Figure 3.3. Based on the above analysis, to analyze the connectivity of the network we define a connectivity matrix [ci j(t)] as follows: [ci j(t)] = 1, i f j ∈ Ni(t), i 6= j 0, i f j /∈ Ni(t), i 6= j 45 Figure 3.3: If one or two of the links (1,2), (3,4), (5,6) is broken the graph connectivity is still remained, but if all of that links is broken the graph connectivity is lost. and cii = 0. Since the rank of Laplacian of a connected graph [23] [ci j(t)] of order n is at most (n−1) or rank([ci j(t)]) ≤ (n−1), the relative connectivity of a network at time t is defined as: C(t)= 1 n−1 rank([ci j(t)]). If 0 ≤C(t)< 1 the network is broken, and if C(t)= 1 the network is connected. Based on this metric we can evaluate the network connectivity in our proposed flocking control Algorithm 3 and the existing flocking control algorithm (3.1). Experimental Results Initially, the seven Rovio robots are randomly deployed so that they can form a connected network (see Option 1 in Algorithm 3). Then, two robots which are closest to the target are selected to be the informed agents (the two robots with cameras facing up as shown in snapshot (d) in Figure 3.5). We obtained the results of our flocking control Algorithm 3 in Figures 3.4, 3.5 and 3.6. Specially, Figure 3.5 (a, b, c) show the snapshots of simulation results for seven robots, and Figure 3.5 (d, e, f) show the snapshots of experiment results for seven robots. In Figure 3.6 we compare the trajectories of three out of seven robots in both simulation and experiment, and we see that the experimental trajectories have small difference with the ones in simulation since the motion of the robots is limited to only six directions. In addition, Figure 3.4 shows the connectivity result, and we clearly see that the seven robots can flock together even only two of them know the information of the target. 46 0 100 200 300 400 500 600 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 ITERATION C Figure 3.4: Connectivity evaluation in experiment of 7 Rovio robots when applying our proposed flocking control algorithm 3. 600 400 200 0 200 400 600 800 1500 1000 500 0 500 Y (POS) X ( P O S ) 100 0 100 200 300 400 500 600 700 800 3300 3200 3100 3000 2900 2800 2700 2600 2500 2400 X (POS) Y (POS) 800 600 400 200 0 200 400 600 400 200 0 200 400 600 800 1000 Y (POS) X (POS) ! " # " ! $%&'()*+,*%./ $%&'()*+,*%./.,(*.01234 $%&'()*+,*%./.,(*.01234 Figure 3.5: Snapshots of 7 Rovio robots flocking together when applying our proposed flocking control algorithm 3. 47 1000 500 0 500 1000 1500 5000 0 5000 1000 500 0 500 1000 1500 5000 0 5000 1000 500 0 500 1000 1500 5000 0 5000 1000 500 0 500 1000 1500 5000 0 5000 1000 500 0 500 1000 1500 5000 0 5000 1000 500 0 500 1000 1500 5000 0 5000 1000 500 0 500 1000 1500 5000 0 5000 real trajectory simulation trajectory real trajectory simulation trajectory real trajectory simulation trajectory real trajectory simulation trajectory real trajectory simulation trajectory real trajectory simulation trajectory real trajectory simulation trajectory initial location of robot 1 initial location of robot 2 initial location of robot 3 initial location of robot 6 initial location of robot 7 initial location of robot 5 initial location of robot 4 Figure 3.6: Trajectories of simulation and real robots when applying our proposed flocking control algorithm 3. 48 Simulation Results In simulation, we test our proposed Algorithm 3 with fifty robots which are randomly deployed so that they do not form a connected network initially. Then, these robots are programed based on the flocking algorithm (2.38) to go to the rendezvous point (see Option 2 in Algorithm 3). This step is to make sure that the fifty robots form a connected network at the rendezvous point. After that we let two robots (blue squares) which are closest to the target know the position and velocity of the target. By observing Figure 3.7 we can see that the two informed robots can drag all 48 other robots (purple triangles) to flock together. The connectivity for the proposed Algorithm 3 and the algorithm (3.1) is shown in Figure 3.9, and from this figure we can see that the connectivity is maintained for Algorithm 3 while it is broken when applying algorithm (3.1). The tracking overshoot is evaluated in Figure 3.8, and we see that without the damping force term the tracking overshoot is big, and the network oscillates around the target. 0 50 100 150 200 250 300 350 400 450 500 100 150 200 250 300 350 400 450 500 X (POS) Y (POS) 1. Blue Squares: Informed agents 2. Purple Trianges: Noninformed agents Initial positions of 50 agents 50 agents form an alpha lattice formation and go to the rendezvous point (red dot) Target Two informed agents drag the whole network to track the target Two informed agents which are closest to the target Figure 3.7: Snapshots of 50 robots flocking together (simulation)with two of themknowing the information of the target. 49 250 300 350 400 450 500 550 600 250 300 350 400 450 500 550 600 650 700 X (POS) Y (POS) Result of the proposed algorithm with damping force Target Result of the existing flocking algorithm Result of the proposed algorithm without damping force Target Figure 3.8: Average of positions of 2 informed robots (tracking performance) in simulation. 0 200 400 600 800 1000 1200 1400 1600 1800 0.96 0.965 0.97 0.975 0.98 0.985 0.99 0.995 1 1.005 ITERATION C Figure 3.9: Connectivity evaluation in simulation of 50 robots. Solid line is for our proposed algorithm 3, and dash line is for the existing algorithm (3.1) 50 3.2 Adaptive Flocking Control for Moving Target Tracking In this section, an adaptive flocking control algorithm is designed to allow an MSN to deal with complex environments while maintaining connectivity, tracking performance and similar formation. The stability analysis of the adaptive flocking control is provided. In addition, simulations and experiments are conducted to compare the adaptive flocking control and regular flocking control. 3.2.1 Problem Formulation In reality, a mobile sensor network has to deal with changing or complex environments. For example the agents have to pass through a narrow space among obstacles. In that situation the existing flocking control algorithms have some limitations such as: 1. Formation of the network is totally changed. 2. Connectivity is lost because of the fragmentation phenomenon. 3. Low speed or getting stuck causes poor tracking performance. Therefore designing an adaptive flocking control algorithm to deal with these problems is a challenging task. In this section, we present a novel approach to flocking control of a mobile sensor network to track a moving target with changing environments. In this approach, each agent cooperatively and adaptively learns the network’s parameters to decide its’s size in a decentralized fashion so that the connectivity, tracking performance and formation can be improved when avoiding obstacles. The reason for maintaining the connectivity and similar formation is that when the network shrinks to deal with changing environments the neighborhood of each agent can be maintained. This allows the network to keep the same topology that reduces the complexity of control during the tracking process. Computer simulations are conducted to prove our theoretical results. The problem is how to cooperatively control the size of the network which forms an a lattice configuration in an adaptive fashion while maintaining the network’s connectivity, 51 Figure 3.10: Illustration of the adaptive flocking control. tracking performance and similar formation in the presence of obstacles. Here, the similar formation is understood as the neighbors of each agent in the whole tracking process are kept. One example of such flocking control is illustrated in Figure 3.10. 3.2.2 Adaptive Flocking Control To control the size of the network, we need to control the set of algebraic constraints in Equation (2.20), which means that if we want the size of the network to be smaller to pass the narrow space then da should be smaller. This raises the question of how small the size of network should be reduced and how to control the size in a decentralized and dynamic fashion. To control the constraint da one possible method is based on the knowledge of obstacle obtained by any agent in the network, which will broadcast a new da to all other agents, then the network will shrink into small size to pass through the narrow space between the obstacles. However, it is difficult for a single agent to learn the obstacles due to its limited sensing range. Therefore, one agent is not able to know the whole environment to determine the size of the network. To overcome this problem we propose the second method based 52 on the repulsive force, åk∈Nb i fb(k ˆ qi,k−qiks), which is generated by the bagent projected on the obstacles. If any agent of the network gets this repulsive force it will shrink its own da i . If this repulsive force is big (agent is close to obstacle(s)) da i will be further reduced. Then, in order to maintain the neighbors (topology) the active range of each agent is redesigned. To create the agreement on the relative distance and active range among agents in a decentralized way, a consensus or a local average update law is proposed. Furthermore, to maintain the connectivity each agent is designed with an adaptive weight of attractive force from the target and an adaptive weight of interaction force from its neighbors so that the network reduces or recovers the size gradually. That is if an agent has weak connection to the network it should have big weight of attraction force to the target and small weight of interaction force from its neighbors. Firstly, we control the set of algebraic constraints as in Equation (3.2) kqj−qiks = da i , j ∈ Ni (3.2) and let each agent have its own da i , which is designed as in Equation (3.3) da i = da, i f åk∈Nb i fb(k ˆ qi,k−qiks) = 0 ca å k∈Nb i fb(k ˆ qi,k−qiks)+1 , i f åk∈Nb i fb(k ˆ qi,k−qiks) 6= 0. (3.3) here ca is the positive constant. From Equation (3.3) we see that if the repulsive force generated from the obstacles åk∈Nb i fb(k ˆ qi,k −qiks) = 0 or Nb i ∈ /0 (empty set) then the agent will keep its original da. When the agent senses the obstacles it reduces its own da i , and how small da i depends on the repulsive force that the agent gets from obstacles. In order to control the size of network each sensor need its own ra i that relates to da i as follows: ra i = kkdks with kdks = da i or d = q (eda i +1)2−1 e . Explicitly, ra i is computed as in Equation (3.4). ra i = ra, i f åk∈Nb i fb(k ˆ qi,k−qiks) = 0 1e [ q k2 (eda i +1)2−1 e +1−1], i f åk∈Nb i fb(k ˆ qi,k−qiks) 6= 0. (3.4) 53 Similar to computing ra i , ri which also relates to ra i is computed as ri = r, i f åk∈Nb i fb(k ˆ qi,k−qiks) = 0 q 1e [(era i +1)2−1], i f åk∈Nb i fb(k ˆ qi,k−qiks) 6= 0. (3.5) It should be pointed out that the active range ri is different from the physical communication (sensing) range. Namely, the active range is the range that each agent decides its neighbors to talk with, but the physical communication range is the range defined by the RF module. This implies that even a robot can communicate with all other robots in the network, it will only talk (interact) with robots in its active range. That is why we want to control the active range of each robot in order to reduce the communication and maintain the similar formation when the network shrinks into smaller sizes. To achieve agreement on da i , ra i and ri among agents in the connected network we use the following update law based on local average for da i , ra i and ri: da i = 1 Na i ∪{i} åNa i ∪{i} j=1 daj ra i = 1 Na i ∪{i} åNa i ∪{i} j=1 raj ri = 1 Na i ∪{i} åNa i ∪{i} j=1 r j (3.6) here Na i ∪{i} is the number of agents in agent i’s local neighborhood including agent i itself. In addition, to better maintain the network connectivity each agent should have an adaptive weight of attractive force from the target and interaction force from its neighbors as discussed before. Firstly, in the control protocol (2.38), the first two terms are used to control the formation (velocity matching, collision avoidance among robots). The third and fourth terms are used to allow robots to avoid obstacles, and the last term is used for target tracking. If the last term is absent the control will lead to the network fragmentation [23]. The coefficients of the interaction forces (ca1 , ca2 ), (cb1 , cb2 ) and attractive force (cmt 1 , cmt 2 ) which deliver desired swarmlike behaviour are used to adjust the weight of interaction forces and attractive force. Namely, the pair (ca1 , ca2 ) is used to adjust the attractive/repulsive forces 54 among agent i and its actual neighbors (aagent), and the pair (cb1 , cb2 ) is used to adjust the repulsive forces among agent i and its virtual neighbors (bagent) that is generated from agent i when it see the obstacles, and the pair (cmt 1 , cmt 2 ) is used to adjust the attractive forces between agent i and its target. The bigger (cmt 1 , cmt 2 ) the faster convergence to the target. However if (cmt 1 , cmt 2 ) is too big the center of mass (CoM) as defined in Equation (2.41) oscillates around the target, and the formation of network is not guaranteed. In addition, in order to guarantee that no agent hit obstacle the pair (cb1 , cb2 ) is selected to be bigger than the other two pairs, (ca1 , ca2 ) and (cmt 1 , cmt 2 ). Finally we have the relationship among these pairs as: (ca1 ,2 < cmt 1,2 < cb1 ,2). From the above analysis of choosing the coefficients of the interaction forces and attractive force we see that these adaptive weights allow the network to reduce and recover the size gradually. This also allows the network to maintain the connectivity during the obstacle avoidance. We will let each sensor have its own weight of the interaction forces as in Equation (3.7) and attractive force as in Equation (3.8). Keep in mind that in the alattice configuration if the sensor has less than 3 neighbors it is considered as having a weak connection to the network. This means that this sensor is on the border of network, or far from the target hence it should have bigger weight of attractive force from its target and smaller weight of interaction forces from its neighbors to get closer to the target. This design also has the benefit for the whole network to track the target faster. From this analysis ca1 ,2 and cmt 1,2 of each agent are designed as follows: ca1 (i) = ca1 , i f Na i  ≥ 3 ca′ 1 , i f Na i  < 3 (3.7) here ca′ 1 < ca1, ca2 (i) = 2 p ca1 (i), and i = 1,2, ...,n. cmt 1 (i) = cmt 1 , i f Na i  ≥ 3 cmt′ 1 , i f Na i  < 3 (3.8) here cmt′ 1 > cmt 1 , cmt 2 (i) = 2 p cmt 1 (i), and i = 1,2, ...,n. 55 Hence, the neighbor set of sensor i at time t (N′a i (t)), the new adjacency matrix ai j(q) and the new action function fa(z) are defined as follows: N′a i (t) = j ∈ J : kqj −qik ≤ ri, J = {1,2, ...,n}, j 6= i (3.9) a′ i j(q) = rh(kqj−qiks/ra i ), i f j 6= i 0, i f j = i (3.10) f′ a(kqj−qiks) = rh(kqj−qiks/ra)f(kqj−qiks−da i ). (3.11) Finally, the adaptive flocking control law for dynamic target tracking is as follows, ui = ca1 (i) å j∈N′a i f′ a(kqj−qiks)ni j +ca2 (i) å j∈N′a i a′ i j(q)(pj− pi) +cb1 å k∈Nb i fb(k ˆ qi,k−qiks) ˆ ni,k+cb2 å k∈Nb i bi,k(q)( ˆ pi,k− pi) −cmt 1 (i)(qi−qmt)−cmt 2 (i)(pi− pmt ). (3.12) 3.2.3 Stability Analysis By applying the control protocol (3.12), the CoM (defined in Equation (2.41)) of positions and velocities of all mobile sensors in the network will exponentially converge to the target in both free space and obstacle space. In addition, the formation or no collision and velocity matching among mobile sensors will maintain in the process of the moving target tracking. Let us consider two cases of adaptive flocking control in free space and obstacle space, respectively. Case 1 (Free space): In free space, this means that åk∈Nb i fb(k ˆ qi,k−qiks) = 0. Hence we can rewrite the control protocol (3.12) with ignoring constants cn h (for ∀h = 1,2 and n = a,b) as follows: ui = − å j∈Na i Ñqiya(kqj−qiks)+ å j∈Na i ai j(q)(pj− pi) −cmt 1 (qi−qmt)−cmt 2 (pi− pmt ) (3.13) 56 where ya(z) = R z da fa(s)ds is the pairwise attractive/repulsive potential function. From (3.13), we can compute the center of mass of control law u as follows: u = 1 n nå i=1 ui = 1 n nå i=1 (− å j∈Na i Ñqiya(kqj−qiks) + å j∈Na i ai j(q)(pj− pi)) −cmt 1 (q−qmt)−cmt 2 (p− pmt ). (3.14) Obviously, we see that the pair (ya,a(q)) are symmetric. Hence we can rewrite (3.14) as: u = −cmt 1 (q−qmt)−cmt 2 (p− pmt ). (3.15) Equation (3.15) implies that ˙q = p ˙p = −cmt 1 (q−qmt)−cmt 2 (p− pmt ). (3.16) The solution of (3.16) indicates that the position and velocity of the CoM exponentially converge to those of target. The formation or collisionfree and velocity matching among mobile sensors are kept in the free space tracking because the gradientbased term and the consensus term are considered in this situation (more details please see [23]). Case 2 (Obstacle space): da i is designed to be reduced when each agent senses the obstacles. Therefore, when the sensor network has to pass through the narrow space between two obstacles it will shrink the size gradually, and when the network already passed this narrow space it grows back to the original size gradually. This reduces the impact of the obstacle on the network hence the speed of agents can be maintained or the CoM keeps tracking the target. Also, the connectivity and similar formation can be maintained in this scenario. 3.2.4 Simulation and Experiment Results The parameters used in the simulation and experiment of the adaptive flocking are specified as follows: 57  Parameters of flocking in simulation: we use 50 mobile sensor nodes which are randomly distributed in the box of 100x100 size. Other parameters are a = b = 5; the active range r = 8.5; the desired distance d = 7; e = 0.1 for the snorm; h = 0.2 for the bump functions (fa(z), f′ a(z)); h = 0.9 for the bump function (fb(z)). Parameters of target movement for simulation: The target moves in the line trajectory: qt = [100+130t, t]T .  Parameters of flocking in experiment: a = b = 5; d = 1100mm; the scaling factor kc = 1.2; the active range r = kc ∗d; e = 0.1 for the snorm; h = 0.2 for the bump functions (fa(z), f′ a(z)); h = 0.9 for the bump function (fb(z)). Parameters of target movement for experiment: The virtual target moves in the line trajectory: qt = [230+t, −3000+130t]T .  Experimental setup: In this experiment we use 7 Rovio robots [111] that have omnidirectional motion capability. Basically, these robots can freely move in 6 directions. The dynamic model of the Rovio robot can be approximated by Equation (2.18). However, the localization accuracy of the Rovio robot is low, and the robot does not has any sensing device to sense the pose (position and velocity) of its neighbors or the obstacles. Hence we use a VICON motion capture system setup [1] in our lab (Figure 3.11) that includes 12 infrared cameras to track moving objects. This tracking system can provide the location and velocity of each moving object with high accuracy. Figures 3.12 represents the results of moving target (red/dark line) tracking in the line trajectory using the existing flocking control algorithm (2.38). Figure 3.13 represents the results of moving target tracking in the line trajectory using the adaptive flocking control algorithm (3.12). Figure 3.14 shows the results of velocity matching among agents (a, a’), connectivity (b, b’) and error positions between the CoM (black/darker line) and the target (tracking performance) (c, c’) of both flocking control algorithms (3.12) and (2.38), respectively. To compare these algorithms we use the same initial state (position and velocity) of 58 Figure 3.11: Experimental setup for adaptive flocking control. mobile agents. By comparing these figures we see that by applying the adaptive flocking control algorithm (3.12) the connectivity, similar formation and tracking performance are maintained when the network passes through the narrow space between two obstacles (two red/dark circles) while the existing flocking control algorithm (2.38) could not handle these problems. In Figures 3.13 when the network enters the small gap between two obstacles its size is shrunk gradually in order to pass this space, then the network size grows back gradually when it passed. Therefore the connectivity and similar formation are maintained. Figure 3.15 shows the snapshots (a to f) of the experiment result for 7 Rovio robots using our adaptive flocking algorithm (3.12). The results look similar with the simulation result in Figure 3.13. Figure 3.16 (Left) shows the trajectories of 7 robots in simulation, and Figure 3.16 (Right) compares the trajectories of 7 robots in both simulation and experiment. 59 0 100 200 300 400 500 600 200 150 100 50 0 50 100 150 200 0 50 100 150 200 250 300 350 400 450 500 200 150 100 50 0 50 100 150 200 0 50 100 150 200 250 300 350 400 450 500 200 150 100 50 0 50 100 150 200 350 400 450 500 550 60 40 20 0 20 40 60 80 340 350 360 370 380 390 400 410 30 20 10 0 10 20 30 200 210 220 230 240 250 260 270 30 20 10 0 10 20 30 Figure 3.12: Snapshots of the mobile sensor network (a) when the mobile sensors form a network, (b) when the mobile sensors avoid obstacles, (c) when the mobile sensors get stuck in the narrow space between two obstacles. (a’, b’, c’) are closer look of (a, b, c), respectively. These results is obtained by using algorithm (2.38). 60 220 230 240 250 260 270 20 15 10 5 0 5 10 15 20 25 100 150 200 250 300 350 400 450 150 100 50 0 50 100 150 325 330 335 340 345 350 355 360 365 20 15 10 5 0 5 10 15 20 385 390 395 400 405 410 415 420 425 430 435 25 20 15 10 5 0 5 10 15 20 100 150 200 250 300 350 400 450 150 100 50 0 50 100 150 250 300 350 400 450 500 550 600 150 100 50 0 50 100 150 535 540 545 550 555 560 565 570 575 15 10 5 0 5 10 15 20 25 0 50 100 150 200 250 300 350 400 450 150 100 50 0 50 100 150 365 370 375 380 385 390 8 6 4 2 0 2 4 6 8 10 12 100 150 200 250 300 350 400 450 150 100 50 0 50 100 150
Click tabs to swap between content that is broken into logical sections.
Rating  
Title  Cooperative Control, Learning and Sensing in Mobile Sensor Networks 
Date  20111201 
Author  La, Hung Manh 
Keywords  Cooperative learning, Cooperative sensing, Flocking control, Mobile sensor networks, Multiagent systems, Sensor fusion 
Department  Electrical Engineering 
Document Type  
Full Text Type  Open Access 
Abstract  Mobile sensor networks (MSNs) have great potential in many applications including environment exploring and monitoring; search and rescue; cooperative detection of toxic chemicals, etc. Motivated by the broad and important applications of MSNs and inspired by the cooperative ability and the intelligence of fish schools and bird flocks, this dissertation develops cooperative control, learning and sensing algorithms in a distributed fashion for MSNs to realize coordinated motion control and intelligent situational awareness. The proposed algorithms can allow MSNs to track a moving target efficiently in cluttered environments and even when only a very small subset of the sensor nodes know the information of the target; adjust their size (shrink/recover) in order to adapt to complex environments while maintaining the network connectivity and topology; form a lattice structure and maintain the cohesion even when the measurements are corrupted by noise; track multiple moving targets simultaneously and efficiently in a dynamic fashion; learn to evade the enemy (predators) in a distributed fashion while maintaining the network connectivity and topology; estimate and build the map of a scalar field. We conducted several experiments using both simulation and real mobile robots to show the effectiveness of the proposed algorithms. We also extended our framework to cooperative and active sensing in which the mobile sensors have the ability to adjust their movements to adapt to the environments in order to improve the sensing performance in a distributed fashion. 
Note  Dissertation 
Rights  © Oklahoma Agricultural and Mechanical Board of Regents 
Transcript  COOPERATIVE CONTROL, LEARNING AND SENSING IN MOBILE SENSOR NETWORKS By HUNG MANH LA Bachelor of Science Thai Nguyen University of Technology Thai Nguyen City, Thai Nguyen, Vietnam 2001 Master of Science Thai Nguyen University of Technology Thai Nguyen City, Thai Nguyen, Vietnam 2003 Submitted to the Faculty of the Graduate College of Oklahoma State University in partial fulfillment of the requirements for the Degree of DOCTOR OF PHILOSOPHY December, 2011 COPYRIGHT c By HUNG MANH LA December, 2011 COOPERATIVE CONTROL, LEARNING AND SENSING IN MOBILE SENSOR NETWORKS Dissertation Approved: Dr. Weihua Sheng Dissertation Advisor Dr. Gary G. Yen Dr. Satish Bukkapatnam Dr. Qi Cheng Dr. Mark Payton Dean of the Graduate College iii TABLE OF CONTENTS Chapter Page 1 INTRODUCTION 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4.1 Cooperative Control . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4.2 Cooperative Learning in MSNs . . . . . . . . . . . . . . . . . . . 13 1.4.3 Cooperative Sensing in MSNs . . . . . . . . . . . . . . . . . . . . 14 1.5 Organization of This Dissertation . . . . . . . . . . . . . . . . . . . . . . . 16 2 FLOCKING CONTROL FOR DYNAMIC TARGET TRACKING 17 2.1 Single Mobile Sensor Node and Dynamic Target Tracking . . . . . . . . . 17 2.1.1 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1.2 Potential field approach . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.3 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Flocking Control for Single Target Tracking and Observing . . . . . . . . . 23 2.2.1 Flocking control background . . . . . . . . . . . . . . . . . . . . . 23 2.2.2 Algorithm description . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.3 Stability analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2.4 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 iv 3 COOPERATIVE CONTROL BASED FLOCKING FOR MSNs IN NOISEFREE ENVIRONMENTS 37 3.1 Decentralized Flocking Control with a Minority of Informed Agents . . . . 37 3.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.1.2 Decentralized Flocking Control with aMinority of Informed Agents (MIA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.1.3 Experimental and Simulation Results . . . . . . . . . . . . . . . . 44 3.2 Adaptive Flocking Control for Moving Target Tracking . . . . . . . . . . . 51 3.2.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.2.2 Adaptive Flocking Control . . . . . . . . . . . . . . . . . . . . . . 52 3.2.3 Stability Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2.4 Simulation and Experiment Results . . . . . . . . . . . . . . . . . 57 3.3 Multiple Dynamic Targets Tracking . . . . . . . . . . . . . . . . . . . . . 63 3.3.1 Sensor Network Partitioning . . . . . . . . . . . . . . . . . . . . . 63 3.3.2 Multiple Dynamic Targets Tracking . . . . . . . . . . . . . . . . . 66 3.3.3 Experimental Tests . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4 COOPERATIVE CONTROL BASED FLOCKING FOR MSNs IN NOISY ENVIRONMENTS 83 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.2 Flocking Control Algorithm in Noisy Environments . . . . . . . . . . . . . 84 4.2.1 MultiCoMShrink Algorithm . . . . . . . . . . . . . . . . . . . . 85 4.2.2 MultiCoMCohesion Algorithm . . . . . . . . . . . . . . . . . . . 88 4.3 Stability Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.4.1 Parameter Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 v 5 COOPERATIVE LEARNING OF PREDATOR AVOIDANCE IN MSNs 100 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.2 General Framework of Hybrid System in Multiple Mobile Sensors Domain 102 5.3 Modeling and Cooperative Learning Algorithm . . . . . . . . . . . . . . . 105 5.3.1 Model of Multiple Mobile Sensors Learning . . . . . . . . . . . . . 105 5.3.2 Cooperative Learning Algorithm . . . . . . . . . . . . . . . . . . . 106 5.4 Convergence Analysis of Cooperative Learning Algorithm . . . . . . . . . 111 5.5 Simulation and Experiment Results . . . . . . . . . . . . . . . . . . . . . . 115 5.5.1 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.5.2 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.5.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . 122 5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 6 COOPERATIVEAND ACTIVE SENSING FORMSNs BASED ON DISTRIBUTED CONSENSUS 129 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.2 Scalar Field and Measurement Modeling and Problem Statement . . . . . . 131 6.2.1 Model of the Scalar Field . . . . . . . . . . . . . . . . . . . . . . . 131 6.2.2 Measurement Model . . . . . . . . . . . . . . . . . . . . . . . . . 132 6.2.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.3 Distributed Sensor Fusion Algorithm . . . . . . . . . . . . . . . . . . . . . 133 6.3.1 Overall Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.3.2 Distributed Consensus Filters . . . . . . . . . . . . . . . . . . . . 134 6.3.3 Convergence Analysis . . . . . . . . . . . . . . . . . . . . . . . . 138 6.3.4 Distributed Fusion Algorithm . . . . . . . . . . . . . . . . . . . . 141 6.4 Path Planning Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 6.5 Cooperative and Active Sensing . . . . . . . . . . . . . . . . . . . . . . . 146 6.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 vi 6.5.2 Distance Controller . . . . . . . . . . . . . . . . . . . . . . . . . . 148 6.5.3 Potential Controller . . . . . . . . . . . . . . . . . . . . . . . . . . 151 6.5.4 Quasi Uniformity of Confidence . . . . . . . . . . . . . . . . . . . 154 6.6 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 6.6.1 Tests of Consensus Filter 1 and 2 . . . . . . . . . . . . . . . . . . 159 6.6.2 Simulation Results of Cooperative Sensing . . . . . . . . . . . . . 161 6.6.3 Simulation Results of Cooperative Sensing and the Flocking Control with a Minority of Informed Agents . . . . . . . . . . . . . . . 165 6.6.4 Simulation Results of Active Sensing . . . . . . . . . . . . . . . . 170 6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 7 CONCLUSION AND FUTUREWORK 181 7.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 7.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 BIBLIOGRAPHY 186 Abstract 206 vii LIST OF TABLES Table Page 3.1 Comparison between two algorithms (SGGP and RS). . . . . . . . . . . . . 71 viii LIST OF FIGURES Figure Page 1.1 (a) Schooling of fish. (b) A predator and a school of fish (source: www. inmagine.com). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 The organization of the dissertation. . . . . . . . . . . . . . . . . . . . . . 16 2.1 A mobile sensor tracks a moving target. . . . . . . . . . . . . . . . . . . . 18 2.2 The mobile sensor tracks the target moving in a circular trajectory. . . . . . 22 2.3 Tracking error between the mobile sensor and the moving target. . . . . . . 22 2.4 The projection method for finding the positions and velocities of b neighbors of each a  sensor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.5 (a) A mobile sensor network with a single CoM (SingleCoM), (b) A mobile sensor network with multiple CoMs (MultiCoM). . . . . . . . . . . . 30 2.6 Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, forming a network, avoiding obstacles, and at the ending positions, respectively. (a, b, c) the mobile sensor network is tracking the target moving in the sine wave trajectory, and (a’, b’, c’) the mobile sensor network is tracking the target moving in the circle trajectory using flocking control algorithms with NoCoM (2.38), SingleCoM (2.42) and MultiCoM (2.43), respectively. . . . . . . . . . . . . . . . . . . . . . . . 34 2.7 Position errors between the CoM’s positions and the moving target in the sine wave trajectory (a, b, c) and the circle trajectory (a’, b’, c’) using flocking control algorithms with NoCoM (2.38), SingleCoM (2.42) and MultiCoM (2.43), respectively. . . . . . . . . . . . . . . . . . . . . . . . 35 ix 3.1 Snapshots of the agents when applying the flocking control algorithm (3.1). We select 6 out of 50 agents which are closest to the target to have the information (position and velocity) of the target. . . . . . . . . . . . . . . . 40 3.2 Motion Capture System from VICON [1] in the experimental setup. . . . . 44 3.3 If one or two of the links (1,2), (3,4), (5,6) is broken the graph connectivity is still remained, but if all of that links is broken the graph connectivity is lost. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.4 Connectivity evaluation in experiment of 7 Rovio robots when applying our proposed flocking control algorithm 3. . . . . . . . . . . . . . . . . . . 47 3.5 Snapshots of 7 Rovio robots flocking together when applying our proposed flocking control algorithm 3. . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.6 Trajectories of simulation and real robots when applying our proposed flocking control algorithm 3. . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.7 Snapshots of 50 robots flocking together (simulation) with two of them knowing the information of the target. . . . . . . . . . . . . . . . . . . . . 49 3.8 Average of positions of 2 informed robots (tracking performance) in simulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.9 Connectivity evaluation in simulation of 50 robots. Solid line is for our proposed algorithm 3, and dash line is for the existing algorithm (3.1) . . . 50 3.10 Illustration of the adaptive flocking control. . . . . . . . . . . . . . . . . . 52 3.11 Experimental setup for adaptive flocking control. . . . . . . . . . . . . . . 59 3.12 Snapshots of the mobile sensor network (a) when the mobile sensors form a network, (b) when the mobile sensors avoid obstacles, (c) when the mobile sensors get stuck in the narrow space between two obstacles. (a’, b’, c’) are closer look of (a, b, c), respectively. These results is obtained by using algorithm (2.38). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 x 3.13 Snapshots of the mobile agent network (a) when the mobile agents form a network, (b, c) when the mobile agent network shrinks to avoid obstacles, (d) when the mobile agents successfully passed through the narrow space between two obstacles, (e) when the mobile agents recover the original size. (a’, b’, c’, d’, e’) are closer look of (a, b, c, d, e), respectively. These results are obtained by using our adaptive flocking control algorithm (3.12). 61 3.14 Velocity matching among agents, connectivity, and error of positions between the CoM and the moving target in (a, b, c), respectively using our adaptive flocking control algorithm (3.12), (a’, b’, c’) using the algorithm (2.38). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.15 Snapshots of adaptive flocking control with 7 Rovio robots using our adaptive flocking control algorithm(3.12). (a) 7 robots are randomly distributed. (b) 7 robots form a lattice formation. (c) 7 robots begin to shrink the size of the network. (d) 7 robots pass through the narrow space between 2 obstacles. (e) 7 robots begin to recover the size of the network. (f) 7 robots completely recover the size of the network. . . . . . . . . . . . . . . . . . 62 3.16 Trajectories of 7 robots are obtained by using the adaptive flocking control algorithm (3.12). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.17 Example of seed growing graph partition. . . . . . . . . . . . . . . . . . . 65 xi 3.18 (a) Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, forming a network at time t = 1.26, and decomposing into two subgroups, respectively to track the targets moving in the sine wave trajectories, (b) Error between the average of sensors’s positions in the whole network and the moving target 1 (iteration 1 to 839), and between average of sensors’s positions in subgroup 1 and the moving target 1 (iteration 839 to the end), (c) Error between the average of sensors’s positions in subgroup 2 and the moving target 2. This result is obtained by using the flocking control NoCoM (3.18) and SGGP algorithm . . . . . . . 69 3.19 (a) Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, when the mobile sensors form a network at time t = 1.26, when the mobile sensors decompose into two subgroups, and when two subgroups merge, (b) Error between the average of sensors’s positions in the whole network and the moving target 1 (iteration 1 to 839, and iteration 4200 to the end), and between the average of sensors’s positions in subgroup 1 and the moving target 1 (iteration 840 to 4200), (c) Error between the average of sensors’s positions in subgroup 2 and the moving target 2. This result is obtained by using the flocking control with NoCoM (3.18) and SGGP algorithm. . . . . . . . . . . . . . . . . . . . . 70 xii 3.20 (a) Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, forming a network at time t = 1.26, and decomposing into two subgroups, respectively to track the targets moving in the sine wave trajectories, (b) Error between the average of sensors’s positions in the whole network and the moving target 1 (iteration 1 to 839), and between average of sensors’s positions in subgroup 1 and the moving target 1 (iteration 840 to the end), (c) Error between the average of sensors’s positions in subgroup 2 and the moving target 2. This result is obtained by using the flocking control with NoCoM (3.18) and RS algorithm. . . . . . 72 3.21 Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, forming a network at time t = 1.26, and decomposing into two subgroups, respectively to track the targets moving in the sine wave trajectories. This result is obtained by using the MultiCoM flocking control and SGGP algorithms. . . . . . . . . . . . . . . . . . . . . . . . . 75 3.22 (a, c) are closer look of (b, d) at iterations from 1 to 100. (b) Position errors between the CoM of the whole network and target 1 (from iteration 1 to 839), and between the CoM of the subgroup 1 and target 1 (from iteration 840 to the end). (d) Position errors between the CoM of the subgroup 2 and target 2. This result is obtained by using the MultiCoM flocking control and SGGP algorithms. . . . . . . . . . . . . . . . . . . . . . . . . 76 3.23 Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, forming a network at time t = 1.26, and decomposing into two subgroups, respectively to track the targets moving in the sine wave trajectories. This result is obtained by using the MultiCoM flocking control and RS algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . 77 xiii 3.24 (a, c) are closer look of (b, d) at iterations from 1 to 100. (b) Position errors between the CoM of the whole network and target 1 (from iteration 1 to 839), and between the CoM of the subgroup 1 and target 1 (from iteration 840 to the end). (d) Position errors between the CoM of the subgroup 2 and target 2. This result is obtained by using the MultiCoM flocking control and RS algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.25 Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, when the mobile sensors form a network at time t = 1.26, when the mobile sensors decompose into two subgroups, and when two subgroups merge. This result is obtained by using the MultiCoM flocking control and SGGP algorithms. . . . . . . . . . . . . . . . . . . . . . . . . 80 3.26 (a, c) are closer look of (b, d) at iterations from 1 to 100. (b) Position errors between the CoM of the whole network and target 1 (from iteration 1 to 839, and 3301 to the end), between the CoM of the subgroup 1 and target 1 (from iteration 840 to 3300). (d) Position errors between the CoM of the subgroup 2 and target 2. This result is obtained by using the MultiCoM flocking control and SGGP algorithms. . . . . . . . . . . . . . . . . . . . . 81 4.1 Agent 2 is considered as a neighbor of agent 1 because the estimated distance dˆa is less than the active range r. . . . . . . . . . . . . . . . . . . . . 86 4.2 Snapshots of agents when they are randomly distributed (a, e, i), and when they form a network and track a target (red/dark line) moving in a sine wave trajectory (b, c, d; f, g, h; j, k, l), where (a, b, c, d) are for the NoCoM flocking control algorithm (2.38), (e, f, g, h) are for the MultiCoMShrink flocking control algorithm, and (i, j, k, l) are for the MultiCoMCohesion flocking control algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 95 xiv 4.3 Snapshots of agents when they are randomly distributed (a, e, i), and when they form a network and track a target (red/dark line) moving in a circle trajectory (b, c, d; f, g, h; j, k, l), where (a, b, c, d) are for the NoCoM flocking control algorithm (2.38), (e, f, g, h) are for the MultiCoMShrink flocking control algorithm, and (i, j, k, l) are for the MultiCoMCohesion flocking control algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.4 The tracking performance results (error between the CoM and target positions): (a) is for the NoCoM flocking control algorithm (2.38), (b) is for the MultiCoMShrink flocking control algorithm, and (c) is for the Multi CoMCohesion flocking control algorithm. The connectivity is evaluated by the C(t) value: (d) is for the NoCoM flocking control algorithm (2.38), (e) is for the MultiCoMShrink flocking control algorithm, and (f) is for the MultiCoMCohesion flocking control algorithm. . . . . . . . . . . . . 97 5.1 The hybrid system for reinforcement learning and flocking control in multiple mobile sensors domain. . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.2 Illustration of the safe places to choose. . . . . . . . . . . . . . . . . . . . 105 5.3 Illustration of the predator and prey detection ranges. R1 is the active range of the mobile sensor (prey), R2 is the predator detection range, and Rp is the prey detection range. . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.4 Four safe places are generated based on the moving direction of the predator.108 5.5 Q value update based on the mobile sensor’s action/state and its neighboring actions/states. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 5.6 Snapshots of our proposed cooperative learning algorithmin the first episode. Four red/darker dots as shown in snapshots (d, e, f) are four safe places. The empty red circle is the predator. The filled red circles are the obstacles. . . . 116 xv 5.7 Snapshots of our proposed cooperative learning algorithm in the second episode. Four red/darker dots as shown in snapshots (e, f) are four safe places. The empty red circle is the predator. The filled red circles are the obstacles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.8 Snapshots of the proposed cooperative learning algorithmin the third episode. Four red/darker dots as shown in snapshots (e, f) are the four safe places. The empty red circle is the predator. The filled red circles are the obstacles. 118 5.9 Snapshots of the proposed cooperative learning algorithm in the fourth episode. Four red/darker dots as shown in snapshots (e, f) are the four safe places. The empty red circle is the predator. The filled red circles are the obstacles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.10 Snapshots of the proposed cooperative learning algorithmin the fifth episode. Four red/darker dots as shown in snapshots (c, d) are the four safe places. The empty red circle is the predator. The filled red circles are the obstacles. 120 5.11 Seven Rovio prey mobile sensors and one Rovio predator robot (marked with a yellow cup) are used in the experiment. . . . . . . . . . . . . . . . . 121 5.12 Infrared cameras tracking system for experimental setup of multirobot cooperative learning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 5.13 The trajectories of 7 Rovio robots and one predator in the first learning episode. The green small squares are the safe places, and the filled red squares are the obstacles. . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.14 The trajectories of 7 Rovio robots and one predator in the third learning episode. The green small squares are the safe places, and the filled red squares are the obstacles. . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.15 Connectivity evaluation for the independent learning algorithm (a, c) and our proposed cooperative learning algorithm (b, d), here (c) is a zoomin at 100th episode of (a), and (d) is a zoomin at 4th episode of (b) . . . . . . . 125 xvi 5.16 Topology evaluation for the independent learning algorithm (left) and our proposed cooperative learning algorithm (right). . . . . . . . . . . . . . . . 126 5.17 Convergence of Q values for the independent learning algorithm (left) and our proposed cooperative learning algorithm (right). . . . . . . . . . . . . . 127 5.18 Global reward evaluation for the independent learning algorithm (left) and our proposed cooperative learning algorithm (right). . . . . . . . . . . . . . 127 6.1 (a) Evacuation: Ships and rig workers evacuate the oil spill area as Tropical Storm Bonnie approaches the region (Photo by Mario Tama/Getty Images). (b) The estimated field of chlorophyll generated by the harmful algal blooms observation system [2] by the National Oceanic and Atmospheric Administration (NOAA), (Photo courtesy of NOAA). . . . . . . . . . . . . 130 6.2 Illustration of the measurement model using multiple mobile sensor nodes. . 133 6.3 Framework of distributed sensor fusion algorithm based two different consensus filters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 6.4 Seven mobile sensor nodes flock together and cover the scalar field (the filled square: 12 × 12). The motion path (red color) is generated by the leader, and the CoM (black/darker color) of the network tracks the leader with small overshoots at sharp change points of the path. . . . . . . . . . . 145 6.5 The confidence at each cell of the scalar field F. . . . . . . . . . . . . . . . 146 6.6 Framework of active sensing via confidence feedback . . . . . . . . . . . . 149 6.7 Diagram of active sensing based on the distance controller via confidence feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 6.8 Illustration of confidence feedback for lower bound only. . . . . . . . . . . 150 6.9 Diagram of cooperative and active sensing based on the potential controller enhanced with attractive force via confidence feedback. . . . . . . . . . . . 151 6.10 Illustration of creating virtual attractive forces in the cells which have the confidence level lower than the lower bound. . . . . . . . . . . . . . . . . . 152 xvii 6.11 Illustration of confidence feedback for quasi uniformity of the confidence. The upper bound and lower bound are used to create a quasi uniform of the confidence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 6.12 Diagram of cooperative and active sensing based on the potential controller enhanced with attractive and repulsive forces via confidence feedback. . . . 156 6.13 Illustration of creating virtual repulsive forces in the cells which have the confidence level higher than the upper bound. . . . . . . . . . . . . . . . . 156 6.14 (a). 10 nodes estimate the value at cell k (pink square). (b, c) Result of convergence of 10 nodes, and agreement of 10 nodes when applyingWeight Design 1 in (6.15). (d, e) Result of convergence of 10 nodes, and agreement of 10 nodes when applying Weight Design 2 in (6.21). . . . . . . . . . . . 160 6.15 (a). Distribution of 10 nodes. (b, c) Result of convergence of 10 nodes, and agreement of 10 nodes when applying the Consensus Filter 2 in (6.25) with Metropolis weight (6.26). . . . . . . . . . . . . . . . . . . . . . . . . 161 6.16 (a) the original map of the scalar field F, (b) the built map of the scalar field F using Algorithm 6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 6.17 The snapshots of building the map of the scalar field F using Algorithm 6 and flocking control algorithm (6.40). . . . . . . . . . . . . . . . . . . . . 163 6.18 The error between the built and original maps for all cells in one dimension. (a) for Algorithm 1 with the normal average update protocol; (b) for centralized fusion algorithm; (c) for Algorithm1 with the weighted average update protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 6.19 The error between the built and original maps for all cells in three dimensions. (a) for Algorithm 6 with the normal average update protocol; (b) for centralized fusion algorithm; (c) for Algorithm6 with the weighted average update protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 6.20 The confidence at each cell of the scalar field F. . . . . . . . . . . . . . . . 164 xviii 6.21 Seven mobile sensor nodes flock together and cover the scalar field (the filled square: 12 × 12). The motion path (red color) is generated by the leader, and the CoM (black/darker color) of the network tracks the leader with small overshoots at sharp turning points of the path. . . . . . . . . . . 167 6.22 Snapshots of multiple mobile sensors flocking together and building the map of the scalar field. In these snapshots, only two mobile sensors (blue squares) have information of the virtual leader. The white line is the trajectory of the center of of position of two informed mobile sensors. . . . . . . 168 6.23 (a) The error between the built and true maps for all cells in one dimension; (b) The error between the built and true maps for all cells in three dimensions; (c) The three dimensional confidence map. . . . . . . . . . . 168 6.24 (a) The original map of the scalar field F; (b) The built map of the scalar field F using Algorithm 1. . . . . . . . . . . . . . . . . . . . . . . . . . . 169 6.25 Tracking error between the position of the virtual leader (qt ) and the average of the position of the two informed agents (mean(qin f )). . . . . . . . . 169 6.26 Snapshots of building the map of the scalar field F using Algorithm 6 and the cooperative and active sensing algorithm (6.48). . . . . . . . . . . . . . 171 6.27 (a) The error between the built and true maps for all cells in one dimension; (b) The error between the built and true maps for all cells in three dimensions using Algorithm 6 and the cooperative and active sensing algorithm (6.48). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 6.28 Confidence over the cells in 3 dimensions: (a) for active sensing with Potential Controller using attractive force only, Algorithm (6.46) ; (b) for active sensing with Potential Controller using both attractive and repulsive, Algorithm (6.48). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 xix 6.29 Confidence over the cells in one dimension: (a) for normal cooperative sensing; (b) for active sensing with Distance Controller; (c) for active sensing with Potential Controller using only attractive force (6.46); (d) for active sensing with Potential Controller using both attractive and repulsive forces (6.48). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 6.30 Distance between the mobile sensor 1 and its neighbor: (a) for normal cooperative sensing; (b) for active sensing with Distance Controller; (c) for active sensing with Potential Controller using only attractive force (6.46); (d) for active sensing with Potential Controller using both attractive and repulsive forces (6.48). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 6.31 Error between the original map and the built map in one dimension over cells: (a) for the normal sensing; (b) for the active sensing. . . . . . . . . . 177 6.32 (a) Confidence over cells; (b) Error between the original map and the built map in one dimension over cells. . . . . . . . . . . . . . . . . . . . . . . . 178 6.33 (a) For Potential Controller with attractive force only; (b) For Potential Controller with both attractive and repulsive force. . . . . . . . . . . . . . 179 7.1 Illustration of coverage with limited sensing range. . . . . . . . . . . . . . 184 7.2 A mobile sensor network test bed. . . . . . . . . . . . . . . . . . . . . . . 185 xx CHAPTER 1 INTRODUCTION In this chapter, we first present the motivation of our work, then present the challenges, the contributions and the current state of the art of the cooperative control, learning and sensing in MSNs. 1.1 Motivation Mobile sensor networks (MSNs) [3], one type of sensor networks [4, 5, 6, 7], have been studied by many researchers in recent years. A typical mobile sensor is a mobile robot with various sensors such as camera, sonar or laser for sensing and navigation. Mobile sensor networks have several advantages over stationary sensor networks, such as the adaptation to environmental changes and reconfigurability for better sensing performance. Therefore mobile sensor networks can be applied in many applications including cooperative detection of toxic chemicals in contaminated environments [8, 9, 10]; environment exploring, monitoring and coverage [11, 12, 13]; performing search and rescue operation after disasters [14, 15]; target tracking [16, 17, 18] and protection of endangered species [19]. A main issue for multiple mobile sensors move together is that these sensors have to avoid collision among them, which requires the use of cooperative control methods [20, 21, 22, 23, 24]. One of these methods is flocking control [23]. We know that flocking or schooling is a phenomenon that a number of mobile agents move together and interact with each other while ensuring no collision, velocity matching, and flock centering [25]. In the nature, schools of fish (see Figure 1.1), birds, ants, and bees, etc. demonstrate the phenomenon of flocking [26]. The problem of flocking has been studied for many years. 1 (a) (b) Figure 1.1: (a) Schooling of fish. (b) A predator and a school of fish (source: www. inmagine.com). It has attracted many researchers in physics [27, 28], mathematics [29], biology [30], and especially in control science in recent years [31, 32, 33, 23, 34, 35, 36, 37, 38, 39, 40]. There are several interesting features established by the school of fish or flock of birds. These features can inspire us to design cooperative control, learning and sensing algorithms for MSNs. • Fish school and bird flock can track a target (source of food) efficiently while avoiding obstacles. This inspires us to design a cooperative control algorithm that can allow mobile sensors to track a target better in cluttered environments. • Each individual fish or bird communicates/interacts with its neighbors within its limited sensing range in order to move in the same direction as its neighbors, remain close to its neighbor, and avoid collision with its neighbors [25]. Based on only these local communications/interactions, the fish school or bird flock can still achieve a global goal. For example, in some cases only some individuals have the knowledge about the location of a food source and migration route, but the fish school or bird flock can still find the food source and track the migration route efficiently [41, 42]. Inspired by this natural ability we would like to design a cooperative control algorithm that can allow mobile sensors to track a target when only a very small subset of 2 them know the information of the target while maintaining the network connectivity. • Fish school and bird flock also have ability to change their size of the formation in order to adapt to the environments. This motivates us to design an adaptive control algorithm for an MSN that can automatically adjust its size (shrink/recover) in order to adapt to the complex environments while maintaining the network connectivity and similar topology. • Fish school and bird flock can track multiple food sources (targets) simultaneously. This ability encourages us to design a splitting/merging algorithm that can allow an MSN to track multiple moving targets simultaneously and efficiently in a dynamic fashion. • Each individual fish or bird may not sense the position and velocity of its neighbors accurately, but it can still move with its neighbors and maintain the cohesion with them. This feature inspires us to design flocking control algorithms that can allow mobile sensors to work in noisy environments while maintaining the cohesion to the network. • Fish schooling and bird flocking together can help the individual to avoid predators because many moving individuals create a sensory overload for the predator’s visual channel [43, 44, 45] (see Figure 1.1b). This motivates us to design a cooperative learning algorithm that can allow an MSN to learn to avoid the enemy (predator) in a distributed fashion while maintaining the network connectivity and similar topology. • Finally, each individual fish or bird only interacts locally, but as a whole the fish school or bird flock can agree on the same velocity (velocitymatching ability) through distributed consensus. Understanding this feature can help us design cooperative and active sensing algorithms for an MSN which can allow each sensor to find an agreement among observations of itself and its neighbors by reaching consensus. 3 1.2 Challenges Development of cooperative control, learning and sensing algorithms in a distributed fashion for MSNs is very challenging. These algorithms have to be performed at each sensor node using only local information, while as a whole they exhibit collective intelligence and achieve a global goal. In a resourceconstrained multiagent system, the communication range and sensing range of each agent are small compared to the size of the environments. Hence, agents cannot accomplish the mission without careful design of cooperative control, learning and sensing algorithms. Here are several challenges in designing cooperative control, learning and sensing algorithms for MSNs. • Cooperative Control in MSNs: First, designing flocking control algorithms which maintain the target tracking performance in cluttered environments is a challenging task. In these environments, the agents usually get stuck behind the obstacles and sometimes can not follow the target [23], [17], [34], [35], [46], therefore causing poor tracking performance. Second, designing a distributed flocking control algorithm which can still perform well in terms of better tracking performance and connectivity maintenance when only few agents have information of the target is a difficult task. Flocking control algorithms [23] can allow agents to move together without collision and track a target. However, they are designed under the assumption that all agents have the information of the target. Su et al. [34, 35, 46] relaxed this assumption, however the network connectivity is not maintained. Third, designing an adaptive flocking control algorithm that can adapt to the complex environments, for example passing through a narrow space among obstacles, while maintaining connectivity, tracking performance and similar formation is a challenging task. Existing works [47, 48] do not consider controlling the size of the network, hence the connectivity and topology are not maintained. 4 Fourth, tracking multiple targets simultaneously in a dynamic fashion in a MSN is difficult, since this requires that some sensors should split from the existing formation( s) to track new targets while ensuring the least disturbance to other sensors. This raises the question of which sensors should split from the existing formation and how they should split. In addition, when some targets disappear the sensors which are tracking these targets should rejoin (merge with) the existing groups that are still tracking targets. Fifth, designing distributed flocking control algorithms for MSNs which can still perform well when the measurements are corrupted by noise is very challenging. Existing works [37, 38, 23, 34, 35, 46] do not consider this issue in their flocking control algorithms. • Cooperative Learning in MSNs: Designing an intelligent MSN which can provide ability to learn to avoid enemy (predator) while maintaining the network topology and connectivity is difficult, since this is a distributed decision making problem where each individual has a number of options (safe places) to choose from when the predators appear. Often in these decisions there is a benefit for consensus, where all individuals choose the same safe place. However, the existing consensus methods [40, 49, 50, 51, 52, 53, 54, 55, 56] require a connected network in which all robots can communicate with each other. This may not be valid in real environments because some robots may not connect to the network during the escape. In that case the consensus algorithms will fail. Therefore, there is a need to reach consensus even when the robots cannot connect to the network at sometimes. • Cooperative Sensing in MSNs: Designing a distributed sensor fusion algorithm for MSNs with an emphasis on the task of environment estimation and mapping is an open problem, since it requires a 5 combination of cooperative sensing, cooperative motion control, and complete coverage path planning while using only local information. Existing works in the area of cooperative sensing using MSNs [57, 58, 59, 60, 61, 11, 62, 13] focus on target(s) tracking, environment exploring, sampling, modeling, and coverage. The problem of environmental estimation and mapping based on multiagent cooperative and distributed sensing is still an open research. 1.3 Contributions This work contributes to the research of MSNs by developing cooperative control, learning and sensing in a distributed fashion to realize coordinated motion control and intelligent situational awareness. Here are the main contributions of our work: • Cooperative Control: We propose a novel approach to the problem of flocking control of a MSN to track and observe a moving target. Flocking algorithms that constrain the center of mass of positions and velocities of all mobile sensors in each group (SingleCoM) or the center of mass of position and velocity of each sensor and its neighbors (MultiCoM) are developed. The main benefit of both algorithms is to make the center of mass (CoM) of each group track the target in the obstacle space. This makes the mobile sensors surround the target closely. We study the flocking control in the case of a small subset of informed agents. In nature, only few agents in a group have the information of the target, such as knowledge about the location of a food source, or the migration route. However, they can still flock together in a group based on local information. Inspired by this natural phenomenon, we propose a flocking control algorithm to coordinate the motion of multiple agents. Based on our algorithm, all agents can form a network, maintain connectivity and track the target even only very few of them know the information of 6 the target. To deal with changing environments, for example in the case when the mobile sensor networks have to pass through a narrow space among obstacles, we propose an adaptive flocking control algorithm in which each agent (sensor) can cooperatively learn the network’s parameters to decide the size of network in a decentralized fashion so that the connectivity, formation and tracking performance can be improved. In the scenario of multiple dynamic target tracking, to solve the problem of sensor splitting/merging, a seed growing graph partition (SGGP) algorithm is proposed. In noisy environments, a flocking control algorithm is proposed to coordinate the activities of multiple agents through noisy measurements. Based on our algorithm, all agents can form a network and maintain connectivity. This is of great advantage for agents to exchange information. We show that even with noisy measurements the flocks can achieve cohesion and follow the moving target. The stability and scalability of our algorithm are also investigated. • Cooperative Learning: We propose a hybrid system that integrates reinforcement learning and flocking control in order to create adaptive and intelligent multirobot systems. We study two problems in multirobot concurrent learning of cooperative behaviors: (1) how to generate efficient combination of high level behaviors (discrete states and actions) and low level behaviors (continuous states and actions) for multirobot cooperation; (2) how to conduct concurrent learning in a distributed fashion. To evaluate our theoretical framework, we apply it to enable multirobot networks to learn avoiding predators while maintaining network topology and connectivity. We also investigate the stability and scalability of our algorithm. 7 • Cooperative Sensing: We propose a novel method for multiple mobile sensor nodes to build a map of a scalar field through noisy measurements. Our method consists of three parts. First, we develop a distributed sensor fusion algorithm integrating two different distributed consensus filters to achieve cooperative sensing among sensor nodes. Second, we use the distributed flocking control algorithm to drive the center of the mobile sensor formation to track the desired paths. Third, we build a path planning strategy to obtain a complete coverage of the field. Additionally, we extend our cooperative sensing method to active sensing in order to improve the sensing performance. 1.4 Literature Review In this section, we review existing literature related to our work, which includes cooperative control, multiagent learning, and cooperative sensing. 1.4.1 Cooperative Control Cooperative control in multirobot systems has been receiving growing attention in recent years [63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73], and its applications include multitarget tracking [63, 64], multivehicle formation control [65, 66, 67, 68], optimization based control [69, 70], cooperative control with limited communications [71, 72], graphrigidity based control [74, 75, 76], and data gathering using mobile sensors [73]. In this subsection we review the existing works in the area of cooperative control which includes flocking control, adaptive flocking control, multiple targets tracking in both stationary sensor networks and mobile sensor networks. Flocking Control Flocking control has been studied by many researchers in recent years [77, 78, 64, 79, 80]. Wang and Gu [40] presented a survey of recent research achievements of robot flocking. 8 Their paper gave an overview of the related basic knowledge of graph theory, potential function, network communication and system stability analysis. In [23], a theoretical framework for design and analysis of distributed flocking algorithms was proposed. These algorithms solved the flocking control in the absence and presence of obstacles. The static and dynamic virtual leaders were used as a navigational feedback for all mobile agents. An extension of the flocking control algorithms in [23], flocking of agents with a virtual leader in the case of a minority of informed agents and in the case of varying velocity of the virtual leader, was presented in [34, 35, 46]. Shi and Wang [36] investigated the dynamic properties of mobile agents for the case where the state of the virtual leader is time varying and the topology of the neighboring relations between agents is dynamic was proposed. Anderson et al. [31] demonstrated a new technique for generating the constrained group animations of flocks in which users can impose constraints on agents’ positions at any time in the animation, or control the entire group to meet the shape constraints. Tanner et al. [37, 38] studied the stability properties of a system of multiple mobile agents with double integrator dynamics in the case of fixed and dynamic topologies. In addition, the experimental implementation of flocking algorithms proposed in [37] and [38] on wheeled mobile robots was presented in [39]. Gervasi and Prencipe [33] studied the distributed coordination and control of a set of asynchronous, anonymous, memoryless mobile vehicles in the case of no communication among the vehicles. In particular, their paper analyzed the problem of flocking in a certain pattern and following a designated leader vehicle, while maintaining the pattern. OlfatiSaber [17] developed a distributed flocking algorithm for mobile sensor networks to track a moving target. In his paper, an extension of a distributed Kalman filtering algorithm was used for the sensors to estimate the target’s position. In [32], a scalable multivehicle platform was developed to demonstrate a cooperative control algorithm in mobile sensor networks. Their flocking algorithm was implemented with five TXT1 monster truck robots. 9 Adaptive Flocking Control Adaptive flocking control, an extension of flocking control, has also gained attention from researchers in recent years. Folino and Spezzano [81] presented a parallel clustering algorithm based on the use of swarm intelligence techniques. Their algorithm is a combination of a smart exploratory strategy based on a flock of birds and a densitybased cluster algorithm to discover clusters of arbitrary shape and size in spatial data. Yang et al. [47] proposed an adaptive flocking control algorithm to avoid collision among robots themselves and between robots and obstacles. However, their algorithm did not consider the problem of formation, connectivity and tracking performance. Lee and Chong [48] proposed a decentralized approach for adaptive flocking of swarms of mobile robots to navigate autonomously in complex environments populated with obstacles. The problem of splitting/merging mobile robots in the network according to the environment conditions is addressed in their paper. In their work, the problem of controlling the size of the network was not considered. Multiple Targets Tracking Multiple targets tracking in mobile sensor networks has received adequate attention in the last decade. Jung et al. [82] introduced a regionbased approach to address the problem of multiple targets tracking using a network of communicating robots and stationary sensors. A coarse deployment controller distributes robots across regions using a topological map, and a targetfollowing controller maximizes the number of tracked targets within a region. Chung et al. [57] proposed a gradient search based decentralized algorithm for the problem of active sensing using multiple cooperative sensor nodes for distributed sensing to estimate the state of dynamic targets. Tang and Ozguner [83] investigated the motion planning for a limited number of mobile sensor agents in an environment with multiple dynamic targets. The motion planning problem is formulated as an optimization problem to minimize the average time duration between two consecutive observations of each target. 10 Jung and Sukhatme [63] proposed an algorithm based on treating the densities of robots and targets as properties of the environment in which they are embedded to improve the target tracking performance. Kamath et al. [3] studied the problem of motion planning and sensor assignment in a mobile sensor network for tracking multiple targets. The triangulation based tracking where two sensors merge their measurements to estimate the position of a target is considered. Kolling and Carpin [84] presented a distributed control algorithm for multiple targets surveillance by multiple robots. Their algorithm utilizes information from sensors and communication to predict the minimum time before a robot loses a target. Sensor network partitioning, a fundamental technique for sensor networks dealing with multiple targets tracking, has been studied by many researchers. The methods for network partitioning can be divided into centralized and decentralized. For centralized graph partition, there are several algorithms such as the decomposition scheme to partition a given graph into compactly connected two terminal subgraphs [85], a graph clustering method based on the minimum cuts within a graph [86] , a new graphical adaptation of the kmedoids algorithm [87] and the GirvanNewman method [88]. For distributed graph partition, Derbel and Mosbah [89] proposed a linear time distributed algorithm for decomposing a graph into a disjointed set of clusters. In [90, 91], Goebels et al. presented a neighborhoodbased strategy, a border switch strategy, and an exchange target strategy for the partitioning of large sets of agents into multiple groups. Derbel et al. [92] proposed efficient deterministic and randomized distributed algorithms for decomposing a graph into a disjointed set of connected clusters with small radius and few intercluster edges. Bettstetter [93] gave equations for the cluster density and cluster order of hemogeneously distributed nodes running the distributed mobile adaptive clustering algorithm. Virrankoski and Savvides [94] proposed a topology adaptive spatial clustering (TASC) for sensor networks. Durresi and Paruchuri [95] presented an adaptive clustering protocol for sensor network. This approach is based on the covering problem that aims at covering an area with minimum possible circular disk assuming ideal conditions. Meka and Singh [96] presented a 11 distributed algorithm called ELink based on a quadtree decomposition and a level by level expansion using sentinel sets. Belghith et al. [97] proposed a novel distributed clustering algorithm for ahhoc networks. Their algorithm is based on a synchronized and layered process. Summary of Cooperative Control In general, for cooperative control based on flocking control, most works focus on the configuration and topology of flocks. For single target tracking based on the flocking control, the literatures solve the problem of estimating the target’s state by using the distributed Kalman filter, or solve the problem of target tracking while a minority of agents in the network have the knowledge of the target. Their algorithms work well in free space, but in the obstacle space they have some limitations such as bad tracking performance, low speed and connectivity loss. To our best knowledge, for adaptive flocking control most of existing works focused on the coordination, formation and splitting/merging problems in both fixed and switching topologies. For multiple targets tracking all of reviewed literatures solve the tracking problem in both stationary and mobile sensor networks without paying attention to the network formation such as alattice. The problem of graph partitioning focuses on both centralized and decentralized methods, and most of them decompose the network based on the density of node’s distribution. This means that the size of subgraphs after decomposing are not predetermined. There are several open problems in cooperative control based on flocking control such as: • How to utilize the a minority of informed agents to lead the whole network to track the target while maintaining the connectivity. • How to control the size of the network in a decentralized and adaptive fashion in complex or changing environment while maintaining connectivity, tracking performance and similar formation. 12 • How to partition theMSN to track multiple moving target while minimizing the total energy consumption and time consumption. • How to design a flocking control algorithm to maintain the cohesion among agents while the measurements are corrupted by noise. 1.4.2 Cooperative Learning in MSNs Through cooperative learning agents in a MSN attempt via their interactions to jointly solve tasks or to maximize utility [98]. Cooperative learning has been studied by many researchers in recent years. The overview of cooperative learning including reinforcement learning, evolutionary computation, game theory, complex systems, agent modeling, and robotics can be found in [98, 99]. Reinforcement learning, one of the most powerful machine learning techniques, has been developed for multirobot systems that allow robots to learn cooperation [100, 101, 99, 102]. Reinforcement learning techniques for solving cooperative problems in teams of homogeneous robots such as the problem of maintaining a formation of mobile robots are studied in [103]. Cooperative reinforcement learning associating VQQL (Vector Quantization to Q Learning) is developed and applied for multirobot observation of multiple moving targets [104, 105, 101]. In their work, they solved two problems. The first one focuses on defining the reinforcement signal for each robot in a cooperative team to achieve a global goal. The second one is working with large domains, where the amount of data can be large and different in each moment of a learning step. As a result, their work achieved successful cooperative behaviours, but the learned behaviors are still discrete, and the learning space is still large. Other work on cooperative multirobot reinforcement learning [102] tried to reduce the learning space by using a hybrid state space that integrates a neural perception module and a progressive rescheduling algorithm. Their algorithm can online execute and learn through experience to adapt to environmental uncertainties and enhance performance. However, their work still relies on discrete and finite state/action spaces. 13 To our best knowledge most of existing works in the area of cooperative reinforcement learning assumes discrete and finite state/action spaces; therefore, it is difficult to directly apply reinforcement learning to most real world applications that inherently involve with continuous and infinite space. Furthermore, even if the states can be discretized, the learned behaviors are still discrete. In addition, the switching of discrete behaviors usually causes the control of the robots to become nonsmooth, which is undesirable in most applications. The open question is can we combine reinforcement learning and flocking control to create a general framework for intelligent robot systems that can allow (1) to generate efficient combination of high level behaviors (discrete states and actions) and low level behaviors (continuous states and actions) for multirobot cooperation; (2) and to conduct concurrent learning in a distributed fashion? 1.4.3 Cooperative Sensing in MSNs Cooperative sensing in MSNs has recently attracted researchers in control engineering [11, 12, 13], and it can be utilized in target tracking, and environmental mapping, monitoring, exploration and coverage. Cooperative sensing networks have been developed [106, 60, 13] for environmental sampling and exploring. In [106], underwater vehicles are deployed to measure temperature, currents, and other distributed oceanographic signals. The vehicles communicate via an acoustic local area network and coordinate their motion in response to local sensing information and to evolving environments. This mobile sensor network has the ability to sample the environment adaptively in space and time. By identifying evolving temperature and current gradients with higher accuracy and resolution than current static sensors, this technology could lead to the development and validation of improved oceanographic models. In [60], a class of underwater vehicles are used to obtain a sampling coverage over a large area. A cooperative control method is proposed to control vehicles to generate patterns on closed smooth curves. To further improve the cooperative sensing performance, 14 both the cooperative motion control and the cooperative sensing are integrated based on cooperative Kalman filter [13] to control the shape of the sensor node formation in order to minimize error in the estimates. Other significant works in cooperative sensing developing for environmental estimation, coverage and modeling can be found in [59, 11, 12, 62]. Cooperative sensing based on the gradient descent algorithms to obtain the optimal coverage is developed in [59]. For dynamic environment coverage, a control strategy based on the discrete Kalman filter is developed [11]. The approach relies on using the Kalman filter to estimate the field and on the filter’s prediction step to plan the vehicles’ next move to maximize the quality of the field estimate. In [62], an optimal filtering approach toward fusing local sensor data into a global model of the environment is developed. Their approach is based on the use of average consensus filters to distributedly fuse the sensory data through the communication network. Along with the consensus filters, the control laws are developed for mobile sensors to move to maximize their sensory information relative to current uncertainties in the model. Additionally, cooperative sensing for estimating the state of dynamic targets can be found in [57, 58]. The localization and tracking tasks of dynamic targets are addressed in [58]. In their work, the mobility of sensing agents is utilized to improve this quality of sensing. However, their gradient controller for cooperative sensing is designed in centralized way. The extension to make the control algorithm in [58] distributedly is proposed in [61], and both formation control and cooperative sensing are integrated to improve the sensing performance. Overall, all of the existing works in the area of cooperative sensing using MSNs focus on target(s) tracking, environment exploring, sampling, modeling, and coverage. The problem of environmental estimation and mapping based on multiagent cooperative and distributed sensing is still open research. 15 1.5 Organization of This Dissertation The rest of this dissertation is organized as follows. In Chapter 2 we first present the potential field based moving target tracking algorithm for a single mobile sensor and then extend it to multiple mobile sensors coordination based on flocking control. Chapter 3 describes the flocking control algorithm with a minority of informed agents; the adaptive flocking control algorithm for single target tracking and observing; and the algorithm for dynamic multiple targets tracking and observing, respectively. Chapter 4 presents the flocking control algorithms in noisy environments. Chapter 5 presents a hybrid system of flocking control and reinforcement learning for cooperative predator avoidance. Chapter 6 presents the cooperative sensing algorithm based on distributed consensus filters and flocking control, then extends to cooperative and active sensing algorithm. Conclusions and future work are given in Chapter 7. The flowchart of the organization of the dissertation is illustrated in Figure 1.2. Chapter 7 Conclusion and Future Work Chapter 1 Introduction Chapter 2 Flocking Control Chapter 3 Cooperative Control Based Flocking in NoiseFree Environments Chapter 4 Cooperative Control Based Flocking in Noisy Environments Chapter 5 Cooperative Learning Chapter 6 Cooperative and Active Sensing Figure 1.2: The organization of the dissertation. 16 CHAPTER 2 FLOCKING CONTROL FOR DYNAMIC TARGET TRACKING In this chapter, we first present a potential field approach for a single mobile sensor node to track a moving target. This establishes the background of the potential field method that is extended to multiple mobile sensor nodes. Then, we present the flocking control background which establishes three basic flocking rules: no collision among agents, velocity matching among agents, and flocking centering. We extend the existing flocking control to more constraints such as SingleCoM (Center of Mass) or MultiCoM to allow MSNs to track a target better in cluttered environments. In addition, stability analysis and simulation results with a comparison among the flocking control without CoM(NoCoM), SingleCoM and MultiCoM, respectively, are given. This chapter is organized as follows. Section 2.1 presents a potential field approach for one mobile sensor node to track a moving target. Section 2.2 presents flocking control for MSNs to track a moving target. Finally, Section 2.3 concludes this chapter. 2.1 Single Mobile Sensor Node and Dynamic Target Tracking 2.1.1 Problem formulation We consider a mobile sensor tracking a target which moves in a two dimensional environment. The dynamic equation of the mobile sensor is described as follows: ˙ qr = pr ˙ pr = ur. (2.1) Figure 2.1 shows a mobile sensor tracking a moving target with notations defined as 17 follows. q j q Figure 2.1: A mobile sensor tracks a moving target. qr ∈ R2, pr ∈ R2,qr ∈ R1 are position, velocity, and heading of the mobile sensor at time t, respectively. qmt ∈ R2, pmt ∈ R2,qmt ∈ R1 are position, velocity, and heading of the moving target at time t, respectively. qrt ,j are the relative position from the mobile sensor to the moving target and the angle of qrt , respectively. Assumption 1. We have the following assumption: The mobile sensor is equipped with sensors such as cameras, sonars or laser sensors and the associated algorithms to estimate the trajectory (position and velocity) of the moving target. Let qrt = [xrt , yrt ]T be the relative position between a mobile sensor and a moving target, then the relative velocity between them can be expressed as the derivative of relative position qrt . Hence the relative velocity vector is prt = q˙rt = [x˙rt , y˙rt ]T , where x˙rt and y˙rt 18 are computed as follows: ˙ xrt = kpmtkcos(qmt)−kprkcos(qr) ˙ yrt = kpmtksin(qmt)−kprksin(qr), (2.2) where k.k is the Euclidean distance. The tracking task is to make kqrtk approach to zero as soon as possible. This means that qr = qmt and pr = pmt . 2.1.2 Potential field approach To solve the problem of moving target tracking, we use the potential field approach which consists of an attractive potential function defined as follows [107, 108, 109]: Va = 0.5l1qT rtqrt , (2.3) here l1 is a positive scale factor for the attractive potential field function. In target tracking, we want the mobile sensor to follow a target. Hence, we only need the attractive potential field for the total potential field of qrt . V =Va = 0.5l1qT rtqrt . (2.4) The velocity pr of the mobile sensor is computed as pr = ˙ qr = ÑqrtV = l1qrt . (2.5) Equation (2.5) is with respect to the stationary target (pmt = 0) (conventional potential field method). While for a moving target (pmt 6= 0) we compute the velocity pr of the mobile sensor as follows [107]: pr = pmt +l1qrt . (2.6) Equation (2.6) is equivalent to the following equations [107]: kprksin(qr−j) = kpmtksin(qmt −j), (2.7) 19 kprk = (kpmtk2+2l1kqrtkkpmtkcos(qmt −j)+l21 kqrtk2)1/2. (2.8) Assumption 2. The velocity of the moving target is limited by its maximum velocity pmax mt . From this assumption we have: kprk = min(kpmax mt k, (kpmtk2+2l1kqrtkkpmtk ×cos(qmt −j)+l21 kqrtk2)1/2). (2.9) By dividing both sides of Equation (2.7) with kprk and taking arcsin we obtain the heading or direction of the mobile sensor as qr = j+arcsin(kpmtksin(qmt −j) kprk ). (2.10) The velocity of the mobile sensor in a two dimensional space is obtained as Equation (2.11). pr = [kprkcos(qr), kprksin(qr)]T . (2.11) Theorem 1. Equation (2.6) allows the mobile sensor (qr, pr) to track a moving target (qmt , pmt ). Proof : We choose a Lyapunov function as follows: L =Va = 0.5l1qT rtqrt = 0.5l1kqrtk2. (2.12) This function is positive definite, and the derivative of L is given by ˙L = ¶L ¶qrt ˙ qrt = ¶L ¶qrt prt , (2.13) where the relative velocity between the mobile sensor and the moving target is designed as prt = −ÑqrtVa = −ÑqrtL. Hence, Equation (2.13) is rewritten as follows: ˙L = − ¶L ¶qrt ÑqrtL = −l21 kqrtk2 = −2l1 1 2 l1kqrtk2 = −2l1Va < 0. (2.14) 20 Since the Lyapunov function L is considered the same as the attractive potential field function Va, Equation (2.14) is rewritten as follows: V˙a = −2l1Va. (2.15) Solving this equation we get the solution as follows: Va =Va(0)e−2l1t (2.16) here Va(0) is the value of Va at t =0. This solution shows that Va and kqrtk converge to zero with the converging rate l1, or the position and velocity of the mobile sensor asymptotically converges to those of the moving target after a certain time (t > 0). 2.1.3 Simulation results In this section we test our theoretical results with a circular trajectory of the moving target. Parameters used in this simulation are specified as follows: Parameters of circle trajectory: qmt = [210−70cos(t), 80+70sin(t)]T . Parameters of moving target: pmt = [3, 3]T , pmax mt = [55, 55]T , and qmt = p2 −t. Initial parameters of the mobile sensor: qr(0)=[0, 0]T , pr(0)=[0, 0]T , and qr(0)= p2 , and other parameters: l1 = 9, 0 ≤ t ≤ 5. Figure 2.2 represents the result of one mobile sensor tracking the target moving in a circular trajectory. At the beginning, the position of the sensor is far from the target, but after certain time the sensor can catch up the moving target and then continue to track the target. This confirms the theory stated in Theorem 1. Figure 2.3 shows the tracking performance (position error between the mobile sensor and the moving target). As can be seen in this figure, after 33 iterations the mobile sensor tracks a moving target very well with very small error. 21 0 10 20 30 40 50 60 70 80 −5 0 5 10 15 20 25 30 35 40 45 50 x (pos) y (pos) Initial position of robot (blue triangle) Initial position of target (red solid circle) Ending positions of mobile sensor and target Moving target direction (red line) Mobile sensor trajectory (blue dot line) Figure 2.2: The mobile sensor tracks the target moving in a circular trajectory. 0 20 40 60 80 100 120 −10 0 10 20 30 40 50 60 iterations norm(qmt−qr) Figure 2.3: Tracking error between the mobile sensor and the moving target. 22 2.2 Flocking Control for Single Target Tracking and Observing In this section we will extend the potential field approach to multiple mobile sensor nodes (agents) based on flocking control. The artificial potential field is created to generate a pairwise attractive/repulsive force to control agents to form a lattice formation while tracking the target. However, with this type of traditional flocking control [23], there are still some problems in cluttered environments where the agents usually get stuck behind the obstacles and sometimes can not follow the target [23]. To handle this problem we present new approaches to flocking control of multiagent systems to track a moving target while avoiding obstacles. The main motivation of these approaches is to make the CoM (Center of Mass) of the network track the moving target better in cluttered environments where the traditional flocking control algorithms [23], [17], [34], [35], [46] have poor tracking performance. In our methods all mobile agents can surround the target closely in the obstacle space. This will allow the network to observe and recognize the target more accurately. Specifically, in our SingleCoM algorithm, the center of mass of positions and velocities of all mobile agents in the network is controlled to track a moving target. This algorithm works well in small networks, but it has limited scalability in large networks. In contrast with the Single CoM algorithm, we proposed another flocking control algorithm called MultiCoM where the center of mass of positions and velocities of each agent’s local neighborhood, respectively is controlled to track a moving target. This algorithm allows agents to perform better in large networks in a distributed fashion. 2.2.1 Flocking control background To describe a dynamic topology of flocks or swarms we consider a dynamic graph G(J,E) consisting of a vertex set J = {1,2...,n} and an edge set E ⊆ {(i, j) : i, j ∈ J, i 6= j}. In this topology each vertex denotes one member of the flock, and each edge denotes the communication link between two members. 23 Let qi, pi ∈ Rm (m = 2,3) be the position and velocity of node i, respectively. We know that during the motion of sensors, the relative distance between them may change, hence the neighbors of each sensor also change. Therefore, we can define a set of neighborhood of sensor i at time t as follows: Ni(t) = j ∈ J : kqj −qik ≤ r, J = {1,2, ...,n}, i 6= j (2.17) Here, r is an interaction range (radius of the neighborhood circle in the case of two dimensions, m = 2, or radius of the neighborhood sphere in the case of three dimensions, m = 3), and k.k is the Euclidean distance. In this chapter we consider n sensors moving in an m dimensional Euclidean space. We address the motion control problem for a group of sensors with the objective of dynamic target(s) tracking. We assume that each sensor has a large enough communication range to allow it to communicate with others and a large enough sensing range to allow it to sense the target. We also assume that each sensor is equipped with sonar or laser sensor that allows it to estimate the position and velocity of the target. The dynamic equation of each sensor is described as follows: ˙ qi = pi ˙ pi = ui, i = 1,2, ...,n (2.18) The geometry of a flock ismodeled by an alattice [23] that has the following condition: kqi−qjk = d, j ∈ Ni (2.19) here d is a positive constant indicating the distance between sensor i and its neighbor j. The configuration which approximately satisfies the condition (2.19) is called a quasi alattice, i.e. (kqi−qjk−d)2 < d2, with d << d. To construct a collective potential (discuss later) that is differentiable at singular configuration (qi = qj), the set of algebraic constrains is rewritten in term of s  norm (defined in (2.24)) as follows: kqj−qiks = da, j ∈ Ni (2.20) 24 In [23], OlfatiSaber proposed his control law for flocking of multiple mobile agents with obstacle avoidance. This algorithm consists of three components as follows: ui = f a i + f b i + f g i (2.21) The first component of Equation (2.21) f a i which consists of a gradientbased component and a consensus component (more details about these components see [73], [50], [51]) is used to regulate the gradient of potentials (impulsive or attractive forces) and the velocity among sensors. f a i = ca1 å j∈Na i fa(kqj−qiks)ni j+ca2 å j∈Na i ai j(q)(pj− pi) (2.22) where each term in (2.22) is computed as follows [23]: The set of a neighbors at time t is Na i (t) = j ∈ J : kqj −qik ≤ r, J = {1,2, ...,n}, i 6= j (2.23) The s−norm, k.ks, of a vector is a map Rm =⇒R+ defined as kzks = 1 e [ q 1+ekzk2−1] (2.24) here e is the positive constant. The action function fa(z) vanishing for all z ≥ ra with ra = krks is used to construct a smooth pairwise attractive/repulsive potential function, ya(z) = R z da fa(s)ds. This action function fa(z) is defined as follows: fa(z) = rh(z/ra)f(z−da) (2.25) where f(z) is the uneven sigmoidal function f(z) = 0.5[(a+b)s1(z+c)+(a−b)] (2.26) here s1(z) = z/√1+z2, and parameters 0 < a ≤ b, c = a−b/√4ab to guarantee f(0) = 0, and constraints da = kdks with d = r/k for k being the scaling factor (in the simulations in this dissertation k = 1.2). 25 The bump function rh(z) with h ∈ (0,1) rh(z) = 1, z ∈ [0,h) 0.5[1+cos(p( z−h 1−h))], z ∈ [h,1] 0, otherwise. (2.27) The vector along the line connecting qi and qj is defined as ni j = (qj−qi)/ q 1+ekqj−qik2 (2.28) The adjacency matrix ai j(q) is defined as ai j(q) = rh(kqj−qiks/ra), i f j 6= i 0, i f j = i (2.29) The second component of Equation (2.21) f b i is used to control the mobile sensors to avoid obstacles, f b i = cb1 å k∈Nb i fb(k ˆ qi,k−qiks) ˆ ni,k+cb2 å k∈Nb i bi,k(q)( ˆ pi,k− pi) (2.30) where the set of b neighbors (virtual neighbors) of sensor i at time t with k obstacles is Nb i (t) = n k ∈ Jb : k ˆ qi,k−qik ≤ r′,Jb = {1,2, ..., k} o (2.31) here r′ is selected to be less than r, in our simulations r′ = 0.6r. Jb is a set of obstacles. ˆ qi,k, ˆ pi,k are the position and velocity of sensor i projecting on the obstacle k, respectively. Similar to vector ni j defined in Equation (2.28), vector ˆ ni,k is defined as ˆ ni,k = ( ˆ qi,k−qi)/ q 1+ek ˆ qi,k−qik2. (2.32) The adjacency matrix bi,k(q) is defined as bi,k(q) = rh( ˆ qi,k−qiks/db) (2.33) where db = kr′ks. 26 The repulsive action function of b neighbors is defined as fb(z) = rh(z/db)(s1(z−db)−1). (2.34) Now we want to show more details on how to find out b neighbors ( ˆ qi,k, ˆ pi,k) generated by each a agent. Firstly, we have the following assumption regarding the obstacles. Assumption 3. Obstacles are the convex regions in Rm with boundaries being smooth manifolds. Based on this assumption, we can choose obstacles to be circles (two dimensions, m = 2) or spheres (three dimensions, m = 3) with radius Rk at center yk. We project each sensor to obstacles and find out which shadow of that sensor on obstacles satisfies the condition k ˆ qi,k−qik≤r′, and the obtained results of ˆ qi,k are neighbors of sensor i. Equation (2.35) illustrates the projection method to find the positions and velocities of b neighbors generated by sensor i. ˆ qi,k = μqi+(1−μ)yk, ˆ pi,k = μPpi (2.35) where μ= Rk/kqi−ykk. P=I−akaTk is the projection matrix with ak = (qi−yk/kqi−ykk) and an unit matrix or identity matrix I. Example 1. In this case, we have three obstacles O1, O2 and O3 as shown in Figure 2.4. After projecting asensor i on all obstacles, we see that only two shadows (bneighbors) on the obstacles O1 and O2 satisfying the condition (2.23). The obstacle O3 is out of active range r′, hence there is no shadow of asensor i on it. Consequently, we found out two bneighbors ( ˆ qi,1, ˆ pi,1) and ( ˆ qi,2, ˆ pi,2) of asensor i. The third component of (2.21) f g i is a distributed navigational feedback. f g i = −cg 1s1(qi−qg)−cg 2(pi− pg) (2.36) where s1(qi −qg) = (qi −qg)/ q 1+kqi−qgk2, and the g  sensor (qg, pg) is the virtual leader (more information of virtual leader, see [110]) defined as follows ˙ qg = pg ˙ pg = fg(qg, pg) (2.37) 27 Figure 2.4: The projection method for finding the positions and velocities of b neighbors of each a  sensor. The constants of three components used in (2.21) are chosen as ca1 < cg 1 < cb1 , and cn2 = 2 p cn1 . Here cn h are positive constants for ∀h = 1,2 and n = a,b, g. 2.2.2 Algorithm description In this section, we will extend the above described flocking algorithm with obstacle avoidance [23]. Two problems, named SingleCoM and MultiCoM, respectively, will be investigated. In the SingleCoM problem, the CoM of positions and velocities of all sensors is controlled to track the moving target. In this case, each sensor need to know the positions and velocity of all other sensors, or it requires the global knowledge of the whole network. To address the scalability problem the MultiCoM (CoM of positions and velocities of each sensor’s local neighborhood, respectively) problem is studied, where each sensor only need to know the positions and velocity of its neighbors. In the following algorithms we assume if one of the sensors in the network can estimate the position and velocity of the target, it will broadcast this obtained information to all other nodes. Consequently all sensors in the network can get the knowledge of target. 28 SingleCoM tracking Firstly, based on OlfatiSaber’s flocking algorithm we design an algorithm with a dynamic gagent. In this scenario, the dynamic gagent is considered as the moving target. ui = ca1 å j∈Na i fa(kqj−qiks)ni j+ca2 å j∈Na i ai j(q)(pj− pi) +cb1 å k∈Nb i fb(k ˆ qi,k−qiks) ˆ ni,k+cb2 å k∈Nb i bi,k(q)( ˆ pi,k− pi) −cmt 1 (qi−qmt)−cmt 2 (pi− pmt ) (2.38) here the pair (qmt , pmt) is the position and velocity of the moving target, respectively, and cmt 1 , cmt 2 are positive constants, and cmt 2 = 2 p cmt 1 . By observing the control protocol (2.38), we see that the CoM is difficult to reach the target in the presence of obstacles. This creates the difficulty for sensors to track and observe the target. Therefore this protocol should be extended with more constraint on the CoM as follows: ui = f a i + f b i + f mt (2.39) where f mt is a tracking feedback applied to sensor i by a moving target with position and velocity (qmt , pmt), respectively. f mt i = −cmt 1 (qi−qmt)−cmt 2 (pi− pmt) −cmt 1 (q−qmt)−cmt 2 (p− pmt) (2.40) where the pair (q, p) is the center of mass (CoM) of positions and velocities of all sensors, respectively, as defined in (2.41). q = 1 n åni =1 qi p = 1 n åni =1 pi. (2.41) The SingleCoM tracking is illustrated in Figure 2.5 (a). The CoMof the whole network (red dot) is created to track the target. 29 Figure 2.5: (a) A mobile sensor network with a single CoM (SingleCoM), (b) A mobile sensor network with multiple CoMs (MultiCoM). Consequently, the extended control protocol (2.39) is explicitly specified as follows: ui = ca1 å j∈Na i fa(kqj−qiks)ni j+ca2 å j∈Na i ai j(q)(pj− pi) +cb1 å k∈Nb i fb(k ˆ qi,k−qiks) ˆ ni,k+cb2 å k∈Nb i bi,k(q)( ˆ pi,k− pi) −cmt 1 (qi−qmt)−cmt 2 (pi− pmt ) −csc 1 (q−qmt)−csc 2 (p− pmt ) (2.42) here csc 1 , csc 2 are positive constants. In control protocol (2.42), each mobile sensor at each time t need to know the position and velocity of all other sensors for computing the CoM (q, p). This means that this protocol is limited by the number of sensors, or the scalability is limited because at each time t all other sensors have to send their positions to sensor i. Hence the communication problem is a big challenge and need to be considered when implementing this protocol in real sensor networks. MultiCoM tracking To make the algorithmscalable we implement a distributed flocking algorithmcalledMulti CoM tracking in which the CoM of each sensor’s local neighborhood is controlled to track the target. TheMultiCoM tracking is illustrated in Figure 2.5 (b). In this figure each mobile 30 sensor creates its own CoM, as a result multiple CoMs are created as a virtual network to track a taeget. The MultiCoM tracking algorithm is presented as follows. ui = ca1 å j∈Na i fa(kqj−qiks)ni j+ca2 å j∈Na i ai j(q)(pj− pi) +cb1 å k∈Nb i fb(k ˆ qi,k−qiks) ˆ ni,k+cb2 å k∈Nb i bi,k(q)( ˆ pi,k− pi) −cmt 1 (qi−qmt)−cmt 2 (pi− pmt ) −cmc 1 (q(Na i ∪{i})−qt)−cmc 2 (p(Na i ∪{i})− pt ), (2.43) here (cmc 1 , cmc 2 ) are the positive constants, and the pair (q(i+Na i ), p(i+Na i )) is defined as (2.44). q(Na i ∪{i}) = 1 Na i ∪{i} åNa i ∪{i} i=1 qi p(Na i ∪{i}) = 1 Na i ∪{i} åNa i ∪{i} i=1 pi, (2.44) here Na i ∪{i} is the number of agents in agent i’s local neighborhood including agent i itself. In control protocol (2.43), each mobile sensor only need local knowledge, or it means that each sensor only requires the position and velocity knowledge of itself and its neighbors. In alattice configuration [23] the maximum number of each sensor’s neighbors is 6. Therefore this protocol can scale up to lager mobile sensor networks. 2.2.3 Stability analysis In this subsection we will analyze the stability of our algorithms, flocking control with SingleCoM and MultiCoM, respectively, in free space, and we will explain why the tracking performance in the presence of CoM constraint is better than without CoM constraint in obstacle space. Theorem 2. In free space, by controlling the CoM based on the control protocol (2.42), the CoM of positions and velocities of all sensors in the network will exponentially converge to the target. In addition, the formation of all mobile sensors will maintain in the process of the moving target tracking. 31 Proof : In free space, this means that åk∈Nb i fb(k ˆ qi,k−qiks) = 0. Hence we can rewrite control protocol (2.42) with ignoring constants cn h (for ∀h = 1,2 and n = a,b) as follows: ui = − å j∈Na i Ñqiya(kqj−qiks)+ å j∈Na i ai j(q)(pj− pi) −cmt 1 (qi−qmt)−cmt 2 (pi− pmt ). −csc 1 (q−qmt )−csc 2 (p− pmt). (2.45) where ya(z) = R z da fa(s)ds is the pairwise attractive/repulsive potential function. From (2.45), we can compute the average of the control law u as follows: u = 1 n nå i=1 ui = 1 n nå i=1 (− å j∈Na i Ñqiya(kqj−qiks)+ å j∈Na i ai j(q)(pj− pi)) −(cmt 1 +csc 1 )(q−qmt)−(cmt 2 +csc 2 )(p− pmt). (2.46) Obviously, we see that the pair (ya,a(q)) is symmetric. Hence we can rewrite (2.46) as: u = −(cmt 1 +csc 1 )(q−qmt)−(cmt 2 +csc 2 )(p− pmt ) (2.47) Equation (2.47) implies that ˙q = p ˙p = −(cmt 1 +csc 1 )(q−qmt)−(cmt 2 +csc 2 )(p− pmt ). (2.48) The solution of (2.48) indicates that the position and velocity of the CoM will exponentially converge to those of the target. The formation or collisionfree and velocity matching among mobile sensors will be maintained in the free space tracking because the gradientbased term and the consensus term are considered in this situation. For the MultiCoM flocking control algorithm, we have the following statement for the stability properties. In cluttered environments, consider a system of n mobile agents, that have dynamics (2.18) and are controlled by the MultiCoM flocking algorithm (2.43). Then based on our observations which are shown in the simulation results we see that: 32 1. The CoM of positions and velocities of all agents in the network will exponentially converge to the target in the free space. 2. The error between the CoM’s position and the target’s position is reduced in the obstacle space. The results of the MultiCoM flocking algorithm are similar to the SingleCoM flocking algorithm. However, the benefit of the MultiCoM flocking algorithm is that each agent is controlled locally instead of globally as in the SingleCoM flocking algorithm. 2.2.4 Simulation results In this section we test our theoretical results in simulation with different trajectories of the moving target. First of all we test the case where target moves with a sine wave trajectory. Parameters used in this simulation are specified as follows:  Parameters of flocking: number of sensors = 120; the initial positions of sensors are randomly distributed in a box with a size of [0 90]x[0 90]; the initial velocities of sensors are set to zero. Parameters a = b = 5; the interaction range r = 1.2d = 9; e = 0.1 for the snorm; h = 0.2 for the bump function (fa(z)); h = 0.9 for the bump function (fb(z)).  Parameters of target movement: The target moves in the sine wave trajectory: qmt = [50+35t, 295−35sin(t)]T with 0 ≤t ≤ 8.5, and pmt = (qmt(t)−qmt(t−1))/Dt with Dt = 0.002. Second we test the case where the target moves in a circle trajectory. Parameters used in this simulation are specified as follows:  Parameters of flocking: parameters used in this case are the same with those in the sine trajectory case.  Parameters of target movement: The target moves in a circle trajectory: qmt = [310− 160cos(t), 255+160sin(t)]T with 0 ≤ t ≤ 5, and pmt = (qmt(t)−qmt(t −1))/Dt . To compare three algorithms NoCoM (2.38), SingleCoM (2.42) andMultiCoM (2.43) we use the same initial state (position and velocity) of mobile sensors. Figures 2.6 repre 33 0 50 100 150 200 250 300 350 400 450 500 550 50 100 150 200 250 300 350 400 450 x (pos) y (pos) Begin random initial positions of mobile sensors 1. Moving target (red line) 2. CoM of positions (black dots) All mobile sensors formed a connected network End positions of mobile sensors Mobile sensors are avoiding obstacles Obstacle O1 Obstacle O2 0 50 100 150 200 250 300 350 400 100 150 200 250 300 350 400 x (pos) y (pos) Mobile sensors are avoiding obstacles Obstacle O1 Obstacle O2 End positions of mobile sensors All mobile sensors formed a connected network Begin random initial positions of mobile sensors 1. Moving target (red line) 2. CoM of positions (black dots) 0 50 100 150 200 250 300 350 400 100 150 200 250 300 350 400 x (pos) y (pos) Begin random initial positions of mobile sensors Obstacle O1 Obstacle O2 Mobile sensors are avoiding obstacles End positions of mobile sensors All mobile sensors formed a connected network 1. Moving target (red line) 2. CoM of positions (black dots) 0 50 100 150 200 250 300 350 400 100 150 200 250 300 350 400 x (pos) y (pos) Begin random initial positions of mobile sensors All mobile sensors formed a connected network Obstacle O2 Obstacle O1 End positions of mobile sensors Mobile sensors are avoiding obstacles 1. Moving target (red line) 2. CoM of positions (black dots) 0 50 100 150 200 250 300 350 400 450 500 550 50 100 150 200 250 300 350 400 450 x (pos) y (pos) 1. Moving target (red line) 2. CoM of positions (black dots) All mobile sensors formed a connected network Mobile sensors are avoiding obstacles Obstacle O2 Obstacle O1 Begin random initial positions of mobile sensors End positions of mobile sensors 0 50 100 150 200 250 300 350 400 450 500 550 50 100 150 200 250 300 350 400 450 x (pos) y (pos) All mobile sensors formed a connected network 1. Moving target (red line) 2. CoM of positions (black dots) Begin random initial positions of mobile sensors End positions of mobile sensors Mobile sensors are avoiding obstacles Obstacle O1 Obstacle O2 Figure 2.6: Snapshots of the mobile sensor network when the mobile sensors are at the initial positions, forming a network, avoiding obstacles, and at the ending positions, respectively. (a, b, c) the mobile sensor network is tracking the target moving in the sine wave trajectory, and (a’, b’, c’) the mobile sensor network is tracking the target moving in the circle trajectory using flocking control algorithms with NoCoM (2.38), SingleCoM (2.42) and MultiCoM (2.43), respectively. 34 0 500 1000 1500 2000 2500 3000 3500 4000 4500 0 50 100 150 iterations q mt mean(q) 0 500 1000 1500 2000 2500 3000 3500 4000 4500 0 50 100 150 iterations q mt mean(q) 0 500 1000 1500 2000 2500 3000 3500 4000 4500 0 50 100 150 iterations qmtmean(q) 0 500 1000 1500 2000 2500 3000 0 50 100 150 iterations q mt mean(q) 0 500 1000 1500 2000 2500 3000 0 50 100 150 iterations qmtmean(q) 0 500 1000 1500 2000 2500 3000 0 50 100 150 iterations q mt mean(q) Figure 2.7: Position errors between the CoM’s positions and the moving target in the sine wave trajectory (a, b, c) and the circle trajectory (a’, b’, c’) using flocking control algorithms with NoCoM (2.38), SingleCoM (2.42) and MultiCoM (2.43), respectively. sents the snapshots of mobile agents tracking the target moving in the sine wave and circle trajectories using three algorithms, NoCoM, SingleCoM and MultiCoM, respectively. Figures 2.7 represents the error between the CoM’s positions and the target (tracking performance) in the sine wave and circle trajectories using three algorithms, NoCoM, Single CoM and MultiCoM, respectively. We see that the results of tracking performance in Figure 2.7 (b, b’, c, c’) for both trajectories of the target using SingleCoM and MultiCoM algorithms, respectively, are better than that in Figure 2.7 (a, a’) using NoCoM algorithm. In addition, we can see the snapshots of mobile robots avoiding obstacle taken at the same time, but in Figures 2.6 (b, b’, c, c’) more agents (sensors) passed through the narrow space between two obstacles than that in Figures 2.6 (a, a’). This means that the CoM in the algorithms SingleCoM and MultiCoM (Figures 2.7 b, b’, c, c’) is closer to the target than that in the NoCoM algorithm (Figures 2.7 a, a’). 35 2.3 Summary This chapter first studied the problem of single moving target tracking using a mobile robot based on the artificial potential field approach. The simulation results were collected to show the effectiveness of the proposed approach. Then, this approach is extended to target tracking in mobile sensor networks based on flocking control. We designed a flocking control algorithm with SingleCoM and MultiCoM to enable mobile sensors to track and observe the moving target more effectively while maintaining their formation and no collision among them. We prove that the CoM of positions and velocities of all mobile sensors exponentially converges to the target. By controlling the CoM explicitly, the mobile sensor network can track and observe the moving target better. This means that all mobile sensors in the network can surround the target closely which will allow them to see the target easily for recognition purpose. In addition, flocking control with NoCoM, flocking control with SingleCoM, and flocking control with MultiCoM are compared. Several simulations are conducted with different target trajectories to demonstrate our theoretical results. 36 CHAPTER 3 COOPERATIVE CONTROL BASED FLOCKING FOR MSNs IN NOISEFREE ENVIRONMENTS In this chapter we study the cooperative control for MSNs in noisefree environments in which each mobile sensor node can sense the location and velocity of itself and its neighbors precisely. Three cooperative control algorithms are proposed. The first one is the flocking control algorithm for MSNs to track a target in the case of a small subset of informed agents while maintaining the network connectivity. The second one is the adaptive flocking control for MSNs to track a moving target in complex environments where the MSNs have to change the size of their formation to adapt to the environment in order to maintain the network connectivity and similar topology. The last one is the multiple dynamic target tracking algorithm which is designed for MSNs to track multitarget simultaneously. This chapter is organized as follows. Section 3.1 presents the decentralized flocking control with a minority of informed agents. Section 3.2 presents the adaptive flocking control for MSNs to track a moving target. Section 3.3 describes multitarget tracking algorithm for MSNs. Finally, Section 3.4 concludes this chapter. 3.1 Decentralized Flocking Control with a Minority of Informed Agents In this section we study the flocking control in the case of a small subset of informed agents. In nature, only few agents in the group have information of the target, such as knowledge about the location of a food source, or of a migration route, but they can still flock together in a group to find the source of food (target) based on local information. 37 Inspired by this natural phenomenon, a flocking control algorithm is designed to coordinate the motion of multiple agents. Based on our algorithm, all agents can form a network, maintain connectivity and track the target even only a few agents know the information of the target. 3.1.1 Introduction Early work on flocking control includes [37, 38, 23]. Tanner et al. [37], [38] studied flocking control of a system of multiple mobile agents with double integrator dynamics in the case of fixed and dynamic topologies. In [23], the theoretical framework for design and analysis of distributed flocking algorithm was proposed. This established a foundation for flocking control design for a group of agents. As an extension of the flocking algorithm in [23], flocking control of agents with a virtual leader in the case of a minority of informed agents and varying velocity of virtual leader was presented in [46]. However, in their work the network can not maintain its connectivity because some agents may fall out of the network. In this section we study how to utilize a minority of informed agents to lead the whole network to track the target while maintaining the connectivity. The main differences with the above related work are: 1. We adopt a target navigation term in order to reduce the large tracking force at the initial tracking time so that the connectivity is maintained. 2. We use a damping force term to reduce the tracking overshoot. Overall, we propose a new flocking control algorithm that allows the flock to preserve connectivity, avoid collision, and track the target without overshooting. We demonstrate that by applying our algorithm the agents can flock together and maintain connectivity better compared to existing flocking control algorithms. Most of existing flocking control algorithms [37, 38, 23] are designed under the assumption that all agents need information of the position and velocity of the target in order 38 to flock together. However, in reality this assumption is not valid. It can be seen in many cases that only very few agents have information of the target due to their limited sensing range. For example, in fish schools and bird flocks, only some agents have knowledge about the location of a food source, or of a migration route [41, 42]. Motivated by these observations we will study how to design a distributed flocking control algorithm which can still maintain good tracking performance and connectivity when only few agents have information of the target. 3.1.2 Decentralized Flocking Control with a Minority of Informed Agents (MIA) In this subsection, we design a distributed flocking control algorithm for multiagent systems in the case that only a few agents are informed with the position and velocity of the target. We call these agents as informed agents. Let us define NI as a subset of informed agents and NUI as a subset of uninformed agents with NI << NUI . Hence we have NI ∪NUI = N, here N is the set of all agents (uninformed and informed agents). Paper [46] proposed the following flocking control algorithm based on the algorithm (2.38): ui = å j∈Ni fa(kqj−qiks)ni j+ å j∈Ni ai j(q)(pj− pi) −ct 1(qi−qt)Ii−ct 2(pi− pt )Ii. (3.1) here if Ii = 1 the agent i has information (position and velocity) of the target. Otherwise Ii = 0 agent i does not have information of the target. We implemented the algorithm (3.1) in which we let some agents closest to the target have the information (position and velocity) of the target. The result is shown in Figure 3.1. In this figure we clearly see that the network is broken, and only the agents which have information of the target can track the target. Additionally, we find that the target tracking performance has big overshoot. In order to solve these two problems we introduce two 39 0 50 100 150 200 250 300 350 400 450 500 100 150 200 250 300 350 400 450 500 Y (POS) X (POS) Initial positions of 50 agents Ony six informed agents can track the target Target Six informed agents can not drag the whole network to track the target (the network is broken) 1. Blue Squares: Informed agents 2. Purple Trianges: Noninformed agents Figure 3.1: Snapshots of the agents when applying the flocking control algorithm (3.1). We select 6 out of 50 agents which are closest to the target to have the information (position and velocity) of the target. terms. The first term is a navigation term, and the second one is a damping force term. The main purpose of the navigation term is to maintain the connectivity among agents, and the purpose of the damping force term is to reduce the tracking overshoot. Navigation Term The navigation term allows the agents to stay together. The main idea behind this term is that if we let the informed agents keep strong cohesion to uninformed agents at the initial time of the target tracking process, the connectivity can be maintained. In order to do this, we have to reduce the initial momentum of the attractive force to the target for the informed agents. This means that we should have small attractive force at the initial time when the distance between the informed agent and the target is large. Based on this analysis we design the navigation term as shown in Algorithm 1. In this algorithm the constant K1 chosen between 0.9 and 1 is to ensure that a small attractive force is applied at the initial 40 time of the target tracking process. The weights, K2 kqin f i (t)−qt (t)k and K3 kqin f i (t)−qt (t)k are designed so that the attractive force is small enough at the initial time, and then it becomes bigger when the distance kqin f i (t)−qt(t)k decreases. Algorithm 1: Design of the Navigation Term for each informed agent j, j ∈ NI do if kqin f i (t)−qt(t)k > K1kqin f i (0)−qt(0)k then f t j = − K2 kqin f i (t)−qt(t)k (qin f j −qt) − K3 kqin f i (t)−qt(t)k (pin f j − pt ) here, 0.9 < K1 < 1, K2 > 0 and K3 > 0, else f t i = −ct 1(qin f j −qt)−ct 2(pin f j − pt ) end end Damping Force Term Since only the informed agents NI have the information of the target, the damping force can be only applied to these agents. The idea behind this damping force is to reduce the tracking overshoot when the informed agents are close to the target. That is, the damping force for the informed agents is only effective if the distance between the informed agent and the target is less than a certain threshold. This threshold is designed based on the active range r. This means that when the target is inside the active range of the informed agent j the damping force f dam j is applied, otherwise f dam j = 0. In order to do that the constant K4 is used (0 < K4 < 1). When the damping force f dam j is applied, the informed agent j will reduce its speed gradually to approach the target. Hence, the tracking overshoot is reduced. 41 Algorithm 2: Design of the Damping Force Term for each informed agent j, j ∈ NI do if kqin f i (t)−qt(t)k < K4r then f dam j = −Kdampin f j here, 0 < K4 < 1 and Kdam > 0, else f dam j = 0 end end Overall, the damping force is designed in Algorithm 2. Finally the whole decentralized flocking control algorithm is proposed in Algorithm 3. In this algorithm we have two options of the initial network configuration, and both options are to allow the network of agents to be connected at the beginning. 42 Algorithm 3: Decentralized Flocking Control Algorithm with a MIA Input : Position and velocity of each agent (qi, pi); Position and velocity of the target (qt , pt ) for the informed agents (NI). Output: Control law for each agent ui Initialization phase: Option 1. Deploy the agents to form a connected network; Option 2. All agents are programmed based on flocking algorithm (2.38) to go to the rendezvous point so that they can form a connected network. Implementation phase: for each agent i do Compute: f a i = åj∈Ni fa(kqj−qiks)ni j+åj∈Ni ai j(q)(pj− pi). end for each informed agent j, j ∈ NI do if kqin f i (t)−qt(t)k > K1kqin f i (0)−qt(0)k then f t j = − K2 kqin f i (t)−qt(t)k (qin f j −qt)− K3 kqin f i (t)−qt(t)k (pin f j − pt ), else f t i = −ct 1(qin f j −qt)−ct 2(pin f j − pt ). end if kqin f i (t)−qt(t)k < K4r then f dam j = −Kdampin f j , (0 < K4 < 1 and Kdam > 0). else f dam j = 0. end end for each uninformed agent k, k ∈ NUI do f dam k = 0, ftk = 0. end Update the control law for each agent i: ui = f a i + f dam i + f t i . 43 3.1.3 Experimental and Simulation Results In this section we test our proposed flocking control Algorithm 3 and compare it with the existing flocking control algorithm (3.1) in the case of a minority of informed agents. First we test our algorithm with 7 real robots. Then to show the effectiveness and the scalability of our algorithm we test it with 50 robots in simulation. In addition, we show a metric to evaluate the network connectivity of our algorithm and the existing algorithm. Experimental Setup In this experiment we use 7 Rovio robots [111] that have omnidirectional motion capability. Basically, these robots can freely move in 6 directions. The dynamic model of the Rovio robot can be approximated by Equation (2.18). However, the accuracy of the localization of the Rovio robot is low, and the robot does not have any sensing device to sense the pose (position and velocity) of its neighbors or the obstacles. Hence we use a VICON motion capture system [1] in our lab (Figure 3.2) that includes 12 cameras to track objects. This tracking system can give the location and velocity of each moving object with over 95 percent of accuracy. Figure 3.2: Motion Capture System from VICON [1] in the experimental setup. We use the following parameters: 44  Parameters of flocking: a = b = 5; d = 600mm; the scaling factor kc = 1.2; the active range r = kc.d; e = 0.1 for the s norm; h = 0.2 for the bump function (fa(z)); h = 0.9 for the other bump function (fb(z)).  Parameters of the target: The target location is at [0, 500mm] for the experiment. The velocity vector pt = [5, 5]. Simulation Setup In the simulation 50 agents are randomly distributed in the square area of 120 × 120 size, and we use the following parameters:  Parameters of flocking: the constants a = b = 5 for the sigmoidal function (f(z)); the distance among agents d = 16 units; the scaling factor kc = 1.2; the active range r = kc ∗d; e = 0.1 for the s norm; h = 0.2 for the bump function (fa(z)); h = 0.9 for the other bump function (fb(z)).  Parameters of the target: The target location is at [450, 450]. The velocity vector pt = [5, 5]. Network Connectivity Evaluation To evaluate the the network connectivity maintenance, first we know that the link (connectivity) between node i and node j is maintained if the distance 0 < kqi −qjk ≤ r. Otherwise this link is considered broken. For graph connectivity, a dynamic graph G(J,E) is connected at time t if there exists a path between any two vertices. An example of graph connectivity is shown in Figure 3.3. Based on the above analysis, to analyze the connectivity of the network we define a connectivity matrix [ci j(t)] as follows: [ci j(t)] = 1, i f j ∈ Ni(t), i 6= j 0, i f j /∈ Ni(t), i 6= j 45 Figure 3.3: If one or two of the links (1,2), (3,4), (5,6) is broken the graph connectivity is still remained, but if all of that links is broken the graph connectivity is lost. and cii = 0. Since the rank of Laplacian of a connected graph [23] [ci j(t)] of order n is at most (n−1) or rank([ci j(t)]) ≤ (n−1), the relative connectivity of a network at time t is defined as: C(t)= 1 n−1 rank([ci j(t)]). If 0 ≤C(t)< 1 the network is broken, and if C(t)= 1 the network is connected. Based on this metric we can evaluate the network connectivity in our proposed flocking control Algorithm 3 and the existing flocking control algorithm (3.1). Experimental Results Initially, the seven Rovio robots are randomly deployed so that they can form a connected network (see Option 1 in Algorithm 3). Then, two robots which are closest to the target are selected to be the informed agents (the two robots with cameras facing up as shown in snapshot (d) in Figure 3.5). We obtained the results of our flocking control Algorithm 3 in Figures 3.4, 3.5 and 3.6. Specially, Figure 3.5 (a, b, c) show the snapshots of simulation results for seven robots, and Figure 3.5 (d, e, f) show the snapshots of experiment results for seven robots. In Figure 3.6 we compare the trajectories of three out of seven robots in both simulation and experiment, and we see that the experimental trajectories have small difference with the ones in simulation since the motion of the robots is limited to only six directions. In addition, Figure 3.4 shows the connectivity result, and we clearly see that the seven robots can flock together even only two of them know the information of the target. 46 0 100 200 300 400 500 600 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 ITERATION C Figure 3.4: Connectivity evaluation in experiment of 7 Rovio robots when applying our proposed flocking control algorithm 3. 600 400 200 0 200 400 600 800 1500 1000 500 0 500 Y (POS) X ( P O S ) 100 0 100 200 300 400 500 600 700 800 3300 3200 3100 3000 2900 2800 2700 2600 2500 2400 X (POS) Y (POS) 800 600 400 200 0 200 400 600 400 200 0 200 400 600 800 1000 Y (POS) X (POS) ! " # " ! $%&'()*+,*%./ $%&'()*+,*%./.,(*.01234 $%&'()*+,*%./.,(*.01234 Figure 3.5: Snapshots of 7 Rovio robots flocking together when applying our proposed flocking control algorithm 3. 47 1000 500 0 500 1000 1500 5000 0 5000 1000 500 0 500 1000 1500 5000 0 5000 1000 500 0 500 1000 1500 5000 0 5000 1000 500 0 500 1000 1500 5000 0 5000 1000 500 0 500 1000 1500 5000 0 5000 1000 500 0 500 1000 1500 5000 0 5000 1000 500 0 500 1000 1500 5000 0 5000 real trajectory simulation trajectory real trajectory simulation trajectory real trajectory simulation trajectory real trajectory simulation trajectory real trajectory simulation trajectory real trajectory simulation trajectory real trajectory simulation trajectory initial location of robot 1 initial location of robot 2 initial location of robot 3 initial location of robot 6 initial location of robot 7 initial location of robot 5 initial location of robot 4 Figure 3.6: Trajectories of simulation and real robots when applying our proposed flocking control algorithm 3. 48 Simulation Results In simulation, we test our proposed Algorithm 3 with fifty robots which are randomly deployed so that they do not form a connected network initially. Then, these robots are programed based on the flocking algorithm (2.38) to go to the rendezvous point (see Option 2 in Algorithm 3). This step is to make sure that the fifty robots form a connected network at the rendezvous point. After that we let two robots (blue squares) which are closest to the target know the position and velocity of the target. By observing Figure 3.7 we can see that the two informed robots can drag all 48 other robots (purple triangles) to flock together. The connectivity for the proposed Algorithm 3 and the algorithm (3.1) is shown in Figure 3.9, and from this figure we can see that the connectivity is maintained for Algorithm 3 while it is broken when applying algorithm (3.1). The tracking overshoot is evaluated in Figure 3.8, and we see that without the damping force term the tracking overshoot is big, and the network oscillates around the target. 0 50 100 150 200 250 300 350 400 450 500 100 150 200 250 300 350 400 450 500 X (POS) Y (POS) 1. Blue Squares: Informed agents 2. Purple Trianges: Noninformed agents Initial positions of 50 agents 50 agents form an alpha lattice formation and go to the rendezvous point (red dot) Target Two informed agents drag the whole network to track the target Two informed agents which are closest to the target Figure 3.7: Snapshots of 50 robots flocking together (simulation)with two of themknowing the information of the target. 49 250 300 350 400 450 500 550 600 250 300 350 400 450 500 550 600 650 700 X (POS) Y (POS) Result of the proposed algorithm with damping force Target Result of the existing flocking algorithm Result of the proposed algorithm without damping force Target Figure 3.8: Average of positions of 2 informed robots (tracking performance) in simulation. 0 200 400 600 800 1000 1200 1400 1600 1800 0.96 0.965 0.97 0.975 0.98 0.985 0.99 0.995 1 1.005 ITERATION C Figure 3.9: Connectivity evaluation in simulation of 50 robots. Solid line is for our proposed algorithm 3, and dash line is for the existing algorithm (3.1) 50 3.2 Adaptive Flocking Control for Moving Target Tracking In this section, an adaptive flocking control algorithm is designed to allow an MSN to deal with complex environments while maintaining connectivity, tracking performance and similar formation. The stability analysis of the adaptive flocking control is provided. In addition, simulations and experiments are conducted to compare the adaptive flocking control and regular flocking control. 3.2.1 Problem Formulation In reality, a mobile sensor network has to deal with changing or complex environments. For example the agents have to pass through a narrow space among obstacles. In that situation the existing flocking control algorithms have some limitations such as: 1. Formation of the network is totally changed. 2. Connectivity is lost because of the fragmentation phenomenon. 3. Low speed or getting stuck causes poor tracking performance. Therefore designing an adaptive flocking control algorithm to deal with these problems is a challenging task. In this section, we present a novel approach to flocking control of a mobile sensor network to track a moving target with changing environments. In this approach, each agent cooperatively and adaptively learns the network’s parameters to decide its’s size in a decentralized fashion so that the connectivity, tracking performance and formation can be improved when avoiding obstacles. The reason for maintaining the connectivity and similar formation is that when the network shrinks to deal with changing environments the neighborhood of each agent can be maintained. This allows the network to keep the same topology that reduces the complexity of control during the tracking process. Computer simulations are conducted to prove our theoretical results. The problem is how to cooperatively control the size of the network which forms an a lattice configuration in an adaptive fashion while maintaining the network’s connectivity, 51 Figure 3.10: Illustration of the adaptive flocking control. tracking performance and similar formation in the presence of obstacles. Here, the similar formation is understood as the neighbors of each agent in the whole tracking process are kept. One example of such flocking control is illustrated in Figure 3.10. 3.2.2 Adaptive Flocking Control To control the size of the network, we need to control the set of algebraic constraints in Equation (2.20), which means that if we want the size of the network to be smaller to pass the narrow space then da should be smaller. This raises the question of how small the size of network should be reduced and how to control the size in a decentralized and dynamic fashion. To control the constraint da one possible method is based on the knowledge of obstacle obtained by any agent in the network, which will broadcast a new da to all other agents, then the network will shrink into small size to pass through the narrow space between the obstacles. However, it is difficult for a single agent to learn the obstacles due to its limited sensing range. Therefore, one agent is not able to know the whole environment to determine the size of the network. To overcome this problem we propose the second method based 52 on the repulsive force, åk∈Nb i fb(k ˆ qi,k−qiks), which is generated by the bagent projected on the obstacles. If any agent of the network gets this repulsive force it will shrink its own da i . If this repulsive force is big (agent is close to obstacle(s)) da i will be further reduced. Then, in order to maintain the neighbors (topology) the active range of each agent is redesigned. To create the agreement on the relative distance and active range among agents in a decentralized way, a consensus or a local average update law is proposed. Furthermore, to maintain the connectivity each agent is designed with an adaptive weight of attractive force from the target and an adaptive weight of interaction force from its neighbors so that the network reduces or recovers the size gradually. That is if an agent has weak connection to the network it should have big weight of attraction force to the target and small weight of interaction force from its neighbors. Firstly, we control the set of algebraic constraints as in Equation (3.2) kqj−qiks = da i , j ∈ Ni (3.2) and let each agent have its own da i , which is designed as in Equation (3.3) da i = da, i f åk∈Nb i fb(k ˆ qi,k−qiks) = 0 ca å k∈Nb i fb(k ˆ qi,k−qiks)+1 , i f åk∈Nb i fb(k ˆ qi,k−qiks) 6= 0. (3.3) here ca is the positive constant. From Equation (3.3) we see that if the repulsive force generated from the obstacles åk∈Nb i fb(k ˆ qi,k −qiks) = 0 or Nb i ∈ /0 (empty set) then the agent will keep its original da. When the agent senses the obstacles it reduces its own da i , and how small da i depends on the repulsive force that the agent gets from obstacles. In order to control the size of network each sensor need its own ra i that relates to da i as follows: ra i = kkdks with kdks = da i or d = q (eda i +1)2−1 e . Explicitly, ra i is computed as in Equation (3.4). ra i = ra, i f åk∈Nb i fb(k ˆ qi,k−qiks) = 0 1e [ q k2 (eda i +1)2−1 e +1−1], i f åk∈Nb i fb(k ˆ qi,k−qiks) 6= 0. (3.4) 53 Similar to computing ra i , ri which also relates to ra i is computed as ri = r, i f åk∈Nb i fb(k ˆ qi,k−qiks) = 0 q 1e [(era i +1)2−1], i f åk∈Nb i fb(k ˆ qi,k−qiks) 6= 0. (3.5) It should be pointed out that the active range ri is different from the physical communication (sensing) range. Namely, the active range is the range that each agent decides its neighbors to talk with, but the physical communication range is the range defined by the RF module. This implies that even a robot can communicate with all other robots in the network, it will only talk (interact) with robots in its active range. That is why we want to control the active range of each robot in order to reduce the communication and maintain the similar formation when the network shrinks into smaller sizes. To achieve agreement on da i , ra i and ri among agents in the connected network we use the following update law based on local average for da i , ra i and ri: da i = 1 Na i ∪{i} åNa i ∪{i} j=1 daj ra i = 1 Na i ∪{i} åNa i ∪{i} j=1 raj ri = 1 Na i ∪{i} åNa i ∪{i} j=1 r j (3.6) here Na i ∪{i} is the number of agents in agent i’s local neighborhood including agent i itself. In addition, to better maintain the network connectivity each agent should have an adaptive weight of attractive force from the target and interaction force from its neighbors as discussed before. Firstly, in the control protocol (2.38), the first two terms are used to control the formation (velocity matching, collision avoidance among robots). The third and fourth terms are used to allow robots to avoid obstacles, and the last term is used for target tracking. If the last term is absent the control will lead to the network fragmentation [23]. The coefficients of the interaction forces (ca1 , ca2 ), (cb1 , cb2 ) and attractive force (cmt 1 , cmt 2 ) which deliver desired swarmlike behaviour are used to adjust the weight of interaction forces and attractive force. Namely, the pair (ca1 , ca2 ) is used to adjust the attractive/repulsive forces 54 among agent i and its actual neighbors (aagent), and the pair (cb1 , cb2 ) is used to adjust the repulsive forces among agent i and its virtual neighbors (bagent) that is generated from agent i when it see the obstacles, and the pair (cmt 1 , cmt 2 ) is used to adjust the attractive forces between agent i and its target. The bigger (cmt 1 , cmt 2 ) the faster convergence to the target. However if (cmt 1 , cmt 2 ) is too big the center of mass (CoM) as defined in Equation (2.41) oscillates around the target, and the formation of network is not guaranteed. In addition, in order to guarantee that no agent hit obstacle the pair (cb1 , cb2 ) is selected to be bigger than the other two pairs, (ca1 , ca2 ) and (cmt 1 , cmt 2 ). Finally we have the relationship among these pairs as: (ca1 ,2 < cmt 1,2 < cb1 ,2). From the above analysis of choosing the coefficients of the interaction forces and attractive force we see that these adaptive weights allow the network to reduce and recover the size gradually. This also allows the network to maintain the connectivity during the obstacle avoidance. We will let each sensor have its own weight of the interaction forces as in Equation (3.7) and attractive force as in Equation (3.8). Keep in mind that in the alattice configuration if the sensor has less than 3 neighbors it is considered as having a weak connection to the network. This means that this sensor is on the border of network, or far from the target hence it should have bigger weight of attractive force from its target and smaller weight of interaction forces from its neighbors to get closer to the target. This design also has the benefit for the whole network to track the target faster. From this analysis ca1 ,2 and cmt 1,2 of each agent are designed as follows: ca1 (i) = ca1 , i f Na i  ≥ 3 ca′ 1 , i f Na i  < 3 (3.7) here ca′ 1 < ca1, ca2 (i) = 2 p ca1 (i), and i = 1,2, ...,n. cmt 1 (i) = cmt 1 , i f Na i  ≥ 3 cmt′ 1 , i f Na i  < 3 (3.8) here cmt′ 1 > cmt 1 , cmt 2 (i) = 2 p cmt 1 (i), and i = 1,2, ...,n. 55 Hence, the neighbor set of sensor i at time t (N′a i (t)), the new adjacency matrix ai j(q) and the new action function fa(z) are defined as follows: N′a i (t) = j ∈ J : kqj −qik ≤ ri, J = {1,2, ...,n}, j 6= i (3.9) a′ i j(q) = rh(kqj−qiks/ra i ), i f j 6= i 0, i f j = i (3.10) f′ a(kqj−qiks) = rh(kqj−qiks/ra)f(kqj−qiks−da i ). (3.11) Finally, the adaptive flocking control law for dynamic target tracking is as follows, ui = ca1 (i) å j∈N′a i f′ a(kqj−qiks)ni j +ca2 (i) å j∈N′a i a′ i j(q)(pj− pi) +cb1 å k∈Nb i fb(k ˆ qi,k−qiks) ˆ ni,k+cb2 å k∈Nb i bi,k(q)( ˆ pi,k− pi) −cmt 1 (i)(qi−qmt)−cmt 2 (i)(pi− pmt ). (3.12) 3.2.3 Stability Analysis By applying the control protocol (3.12), the CoM (defined in Equation (2.41)) of positions and velocities of all mobile sensors in the network will exponentially converge to the target in both free space and obstacle space. In addition, the formation or no collision and velocity matching among mobile sensors will maintain in the process of the moving target tracking. Let us consider two cases of adaptive flocking control in free space and obstacle space, respectively. Case 1 (Free space): In free space, this means that åk∈Nb i fb(k ˆ qi,k−qiks) = 0. Hence we can rewrite the control protocol (3.12) with ignoring constants cn h (for ∀h = 1,2 and n = a,b) as follows: ui = − å j∈Na i Ñqiya(kqj−qiks)+ å j∈Na i ai j(q)(pj− pi) −cmt 1 (qi−qmt)−cmt 2 (pi− pmt ) (3.13) 56 where ya(z) = R z da fa(s)ds is the pairwise attractive/repulsive potential function. From (3.13), we can compute the center of mass of control law u as follows: u = 1 n nå i=1 ui = 1 n nå i=1 (− å j∈Na i Ñqiya(kqj−qiks) + å j∈Na i ai j(q)(pj− pi)) −cmt 1 (q−qmt)−cmt 2 (p− pmt ). (3.14) Obviously, we see that the pair (ya,a(q)) are symmetric. Hence we can rewrite (3.14) as: u = −cmt 1 (q−qmt)−cmt 2 (p− pmt ). (3.15) Equation (3.15) implies that ˙q = p ˙p = −cmt 1 (q−qmt)−cmt 2 (p− pmt ). (3.16) The solution of (3.16) indicates that the position and velocity of the CoM exponentially converge to those of target. The formation or collisionfree and velocity matching among mobile sensors are kept in the free space tracking because the gradientbased term and the consensus term are considered in this situation (more details please see [23]). Case 2 (Obstacle space): da i is designed to be reduced when each agent senses the obstacles. Therefore, when the sensor network has to pass through the narrow space between two obstacles it will shrink the size gradually, and when the network already passed this narrow space it grows back to the original size gradually. This reduces the impact of the obstacle on the network hence the speed of agents can be maintained or the CoM keeps tracking the target. Also, the connectivity and similar formation can be maintained in this scenario. 3.2.4 Simulation and Experiment Results The parameters used in the simulation and experiment of the adaptive flocking are specified as follows: 57  Parameters of flocking in simulation: we use 50 mobile sensor nodes which are randomly distributed in the box of 100x100 size. Other parameters are a = b = 5; the active range r = 8.5; the desired distance d = 7; e = 0.1 for the snorm; h = 0.2 for the bump functions (fa(z), f′ a(z)); h = 0.9 for the bump function (fb(z)). Parameters of target movement for simulation: The target moves in the line trajectory: qt = [100+130t, t]T .  Parameters of flocking in experiment: a = b = 5; d = 1100mm; the scaling factor kc = 1.2; the active range r = kc ∗d; e = 0.1 for the snorm; h = 0.2 for the bump functions (fa(z), f′ a(z)); h = 0.9 for the bump function (fb(z)). Parameters of target movement for experiment: The virtual target moves in the line trajectory: qt = [230+t, −3000+130t]T .  Experimental setup: In this experiment we use 7 Rovio robots [111] that have omnidirectional motion capability. Basically, these robots can freely move in 6 directions. The dynamic model of the Rovio robot can be approximated by Equation (2.18). However, the localization accuracy of the Rovio robot is low, and the robot does not has any sensing device to sense the pose (position and velocity) of its neighbors or the obstacles. Hence we use a VICON motion capture system setup [1] in our lab (Figure 3.11) that includes 12 infrared cameras to track moving objects. This tracking system can provide the location and velocity of each moving object with high accuracy. Figures 3.12 represents the results of moving target (red/dark line) tracking in the line trajectory using the existing flocking control algorithm (2.38). Figure 3.13 represents the results of moving target tracking in the line trajectory using the adaptive flocking control algorithm (3.12). Figure 3.14 shows the results of velocity matching among agents (a, a’), connectivity (b, b’) and error positions between the CoM (black/darker line) and the target (tracking performance) (c, c’) of both flocking control algorithms (3.12) and (2.38), respectively. To compare these algorithms we use the same initial state (position and velocity) of 58 Figure 3.11: Experimental setup for adaptive flocking control. mobile agents. By comparing these figures we see that by applying the adaptive flocking control algorithm (3.12) the connectivity, similar formation and tracking performance are maintained when the network passes through the narrow space between two obstacles (two red/dark circles) while the existing flocking control algorithm (2.38) could not handle these problems. In Figures 3.13 when the network enters the small gap between two obstacles its size is shrunk gradually in order to pass this space, then the network size grows back gradually when it passed. Therefore the connectivity and similar formation are maintained. Figure 3.15 shows the snapshots (a to f) of the experiment result for 7 Rovio robots using our adaptive flocking algorithm (3.12). The results look similar with the simulation result in Figure 3.13. Figure 3.16 (Left) shows the trajectories of 7 robots in simulation, and Figure 3.16 (Right) compares the trajectories of 7 robots in both simulation and experiment. 59 0 100 200 300 400 500 600 200 150 100 50 0 50 100 150 200 0 50 100 150 200 250 300 350 400 450 500 200 150 100 50 0 50 100 150 200 0 50 100 150 200 250 300 350 400 450 500 200 150 100 50 0 50 100 150 200 350 400 450 500 550 60 40 20 0 20 40 60 80 340 350 360 370 380 390 400 410 30 20 10 0 10 20 30 200 210 220 230 240 250 260 270 30 20 10 0 10 20 30 Figure 3.12: Snapshots of the mobile sensor network (a) when the mobile sensors form a network, (b) when the mobile sensors avoid obstacles, (c) when the mobile sensors get stuck in the narrow space between two obstacles. (a’, b’, c’) are closer look of (a, b, c), respectively. These results is obtained by using algorithm (2.38). 60 220 230 240 250 260 270 20 15 10 5 0 5 10 15 20 25 100 150 200 250 300 350 400 450 150 100 50 0 50 100 150 325 330 335 340 345 350 355 360 365 20 15 10 5 0 5 10 15 20 385 390 395 400 405 410 415 420 425 430 435 25 20 15 10 5 0 5 10 15 20 100 150 200 250 300 350 400 450 150 100 50 0 50 100 150 250 300 350 400 450 500 550 600 150 100 50 0 50 100 150 535 540 545 550 555 560 565 570 575 15 10 5 0 5 10 15 20 25 0 50 100 150 200 250 300 350 400 450 150 100 50 0 50 100 150 365 370 375 380 385 390 8 6 4 2 0 2 4 6 8 10 12 100 150 200 250 300 350 400 450 150 100 50 0 50 100 150 



A 

B 

C 

D 

E 

F 

I 

J 

K 

L 

O 

P 

R 

S 

T 

U 

V 

W 


