Cooperative Control of Multi-Agent Systems E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Fachliteratur
• Sprache: Englisch

Seitenzahl: 379

Veröffentlichungsjahr: 2017

Beschreibung

A comprehensive review of the state of the art in the control of multi-agent systems theory and applications

The superiority of multi-agent systems over single agents for the control of unmanned air, water and ground vehicles has been clearly demonstrated in a wide range of application areas. Their large-scale spatial distribution, robustness, high scalability and low cost enable multi-agent systems to achieve tasks that could not successfully be performed by even the most sophisticated single agent systems.

Cooperative Control of Multi-Agent Systems: Theory and Applications provides a wide-ranging review of the latest developments in the cooperative control of multi-agent systems theory and applications. The applications described are mainly in the areas of unmanned aerial vehicles (UAVs) and unmanned ground vehicles (UGVs). Throughout, the authors link basic theory to multi-agent cooperative control practice — illustrated within the context of highly-realistic scenarios of high-level missions — without losing site of the mathematical background needed to provide performance guarantees under general working conditions. Many of the problems and solutions considered involve combinations of both types of vehicles. Topics explored include target assignment, target tracking, consensus, stochastic game theory-based framework, event-triggered control, topology design and identification, coordination under uncertainty and coverage control.

• Establishes a bridge between fundamental cooperative control theory and specific problems of interest in a wide range of applications areas
• Includes example applications from the fields of space exploration, radiation shielding, site clearance, tracking/classification, surveillance, search-and-rescue and more
• Features detailed presentations of specific algorithms and application frameworks with relevant commercial and military applications
• Provides a comprehensive look at the latest developments in this rapidly evolving field, while offering informed speculation on future directions for collective control systems

The use of multi-agent system technologies in both everyday commercial use and national defense is certain to increase tremendously in the years ahead, making this book a valuable resource for researchers, engineers, and applied mathematicians working in systems and controls, as well as advanced undergraduates and graduate students interested in those areas.

Leseprobe

Table of Contents

Cover

Title Page

Copyright

Dedication

List of Contributors

Preface

Acknowledgment

Chapter 1: Introduction

1.1 Introduction

1.2 Chapter Summary and Contributions

References

Chapter 2: Sensor Placement Algorithms for a Path Covering Problem

2.1 Problem Statement

2.2 Algorithm

2.3 Algorithm

2.4 Numerical Results

2.5 Conclusions

Acknowledgment

References

Chapter 3: Robust Coordination of Small UAVs for Vision-Based Target Tracking Using Output-Feedback MPC with MHE

3.1 Vision-Based Target Tracking

3.2 Problem Formulation

3.3 Robust Output-Feedback MPC/MHE

3.4 Simulation Results

3.5 Conclusion and Future Work

References

Chapter 4: Projection-Based Consensus for Time-Critical Coordination of Unmanned Aerial Vehicles under Velocity Constraints

4.1 Introduction

4.2 Problem Statement

4.3 Projection-Based Consensus Algorithm

4.4 Convergence Analysis

4.5 Convergence Time

4.6 Feasibility

4.7 Simulation

4.8 Summary

References

Chapter 5: Greedy Maximization for Asset-Based Weapon–Target Assignment with Time-Dependent Rewards

5.1 Introduction

5.2 Problem Formulation

5.3 Properties of the Objective Function

5.4 Algorithmic Details

5.5 Numerical Case Studies

5.6 Conclusion

Acknowledgment

References

Chapter 6: Coordinated Threat Assignments and Mission Management of Unmanned Aerial Vehicles

6.1 Introduction

6.2 Problem Statement

6.3 Decentralized Assignment of Threats

6.4 Assignment Constraints

6.5 Multiple Main Targets

6.6 Conclusions

References

Chapter 7: Event-Triggered Communication and Control for Multi-Agent Average Consensus

7.1 Introduction

7.2 Preliminaries

7.3 Problem Statement

7.4 Centralized Event-Triggered Control

7.5 Decentralized Event-Triggered Control

7.6 Decentralized Event-Triggered Communication and Control

7.7 Periodic Event-Triggered Coordination

7.8 Conclusions and Future Outlook

References

Appendix

Chapter 8: Topology Design and Identification for Dynamic Networks

8.1 Introduction

8.2 Network Topology Design Problems

8.3 Network Topology Identification Problems

8.4 Iterative Rank Minimization Approach

8.5 Simulation Examples

8.6 Conclusions

References

Chapter 9: Distributed Multi-Agent Coordination with Uncertain Interactions: A Probabilistic Perspective

9.1 Introduction

9.2 Preliminaries

9.3 Fixed Interaction Graph

9.4 Switching Interaction Graph

9.5 Conclusion

References

Chapter 10: Awareness Coverage Control in Unknown Environments Using Heterogeneous Multi-Robot Systems

10.1 Introduction

10.2 Problem Formulation

10.3 Cooperative Control of Heterogeneous Multi-Robot Systems

10.4 Simulation Results

10.5 Conclusion

References

Index

End User License Agreement

Pages

xiii

xiv

xv

xvii

xviii

xix

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

Guide

Cover

Table of Contents

Preface

Begin Reading

List of Illustrations

Chapter 2: Sensor Placement Algorithms for a Path Covering Problem

Figure 2.1 Scenario where the landmarks must be suitably placed to facilitate accurate tracking of the vehicle's paths visiting the targets.

Figure 2.2 A feasible solution to the landmark placement problem. For this example, was chosen to be 50 units and was set to 5 units. A landmark is present at the center of each circle. The circle shows the boundary of the area covered by its respective landmark. One can verify that each target is covered by at least two well-spaced landmarks in this example.

Figure 2.3 An illustration for the proof of Lemma 2.2.3.

Figure 2.4 Placing five landmarks at the marked locations will cover every point in the segment at least twice.

Figure 2.5 An illustration for the proof of Lemma 2.2.4.

Figure 2.6 Output after the greedy algorithm in phase 1 for a sample instance. The targets selected in the set are also shown. Each of the semicircles is centered at a target in and has a radius equal to . Note that every other target not in is present within at least one of the semicircles.

Figure 2.7 The shaded region in the Figure around target is denoted by and is defined as . Ten landmarks are placed to cover each point in this region at least twice. Note that the distance between any two landmarks is at least equal to units.

Figure 2.8 Each circle shown in the Figure is centered at a landmark and has a radius equal to . Any point in the area is covered by at least two landmarks.

Chapter 3: Robust Coordination of Small UAVs for Vision-Based Target Tracking Using Output-Feedback MPC with MHE

Figure 3.1 Trajectories of two UAVs, subject to 6 m/s wind, tracking a constant-velocity target over a 5-min window. The starting positions of all vehicles are denoted by an “” while the ending positions are indicated by an “”. In the legend, corresponds to the target while and refer to the UAVs.

Figure 3.3 Estimate of the wind speed in the -direction (a) and -direction (b) for the constant-velocity target scenario.

Figure 3.2 3D distances (a) and stage cost (b) for two UAVs, subject to 6 m/s wind, tracking a constant-velocity target. The solid black line shows .

Figure 3.4 Trajectories of two UAVs, subject to 3 m/s wind, tracking an evasive target over a 5-min window. The starting positions of all vehicles are denoted by an “” while the ending positions are indicated by an “”. In the legend, corresponds to the target while and refer to the UAVs.

Figure 3.5 3D distances (a) and stage cost (b) for two UAVs, subject to 3 m/s wind, tracking an evasive target. The solid black line shows .

Figure 3.6 Estimate of the wind speed in the -direction (a) and -direction (b) for the evasive target scenario.

Figure 3.7 Trajectories of two UAVs, subject to 0 m/s wind, tracking a target moving based on an experimental target log over a 5-min window. The starting positions of all vehicles are denoted by a “” while the ending positions are indicated by a “”. In the legend, corresponds to the target while and refer to the UAVs.

Figure 3.8 3D distances

(a) and stage cost

(b) for two UAVs tracking a target moving according to an experimental target log. The minimum distance

is shown as a solid black line.

Figure 3.9 Estimate of the wind speed in the -direction (a) and -direction (b) for the experimental target log scenario.

Chapter 4: Projection-Based Consensus for Time-Critical Coordination of Unmanned Aerial Vehicles under Velocity Constraints

Figure 4.1 The history of the velocity with .

Figure 4.2 The history of the ETA with .

Figure 4.3 The history of the remaining paths with .

Figure 4.4 The history of the velocity with .

Figure 4.5 The history of the ETA with

.

Figure 4.6 The history of the remaining paths with .

Figure 4.7 The history of the velocity with disturbances.

Figure 4.9 The history of the remaining paths with disturbances.

Figure 4.8 The history of the ETA with disturbances.

Chapter 5: Greedy Maximization for Asset-Based Weapon–Target Assignment with Time-Dependent Rewards

Figure 5.1 Battlefield Diagram. The targets (three incoming missiles on the upper right) are aimed to attack each asset (buildings at the bottom left) along the arrows, and the defensive weapons (or interceptor missiles) from each weapon farm (at the bottom) are launched to intercept targets along the arrows and defend the assets. Each weapon farm may launch multiple defensive weapons, although not depicted in the figure.

Figure 5.2 An example of generating time slot by Algorithm 1.

Figure 5.3 Simple example of TSWTA problem, . (a) Diagram of overall situation. 2D situation with time . Left rectangle: asset region, central rectangle: weapon farm region, right rectangle: initial target-searching region. (b) Kill probability of defensive weapons in weapon farm 1 to each target versus time. (c) Kill probability of defensive weapons in weapon farm 2 to each target versus time.

Figure 5.4 Simulation results for various cases. (a) , . (b) , . (c) , .

Figure 5.5 Simulation results for various cases.(a)

,

. (b)

,

. (c)

,

.

Figure 5.6 Simulation results for various cases. (a) , . (b) , . (c) , .

Figure 5.7 Simulation result for the real-world case. (a) Targets are launched from northern region and aiming at assets located in southern region. Weapon farms are near the assets to protect the set of assets. (b) One sample of a weapon farm's assignment result. (c) Number of assigned missiles versus sum of asset values.

Chapter 6: Coordinated Threat Assignments and Mission Management of Unmanned Aerial Vehicles

Figure 6.1 Voronoi diagram. Main target: •. threats: . artificial threats: . UAV: .

Figure 6.2 Assignment 1: UAV 1.

Figure 6.3 Assignment 1: UAV 2.

Figure 6.4 Assignment 1: UAV 3.

Figure 6.5 Assignment 2: UAV 1.

Figure 6.6 Assignment 2: UAV 3.

Figure 6.7 Assignment 3: UAV 3.

Figure 6.8 Multiple main targets: UAV 1.

Figure 6.9 Multiple main targets: UAV 2.

Figure 6.10 Multiple main targets: UAV 3.

Figure 6.11 Multiple main targets: UAV 4.

Figure 6.12 Rewards: UAV 2.

Figure 6.13 Rewards: UAV 4.

Figure 6.14 HR: UAV 1.

Figure 6.15 HR: UAV 2.

Figure 6.16 HR: UAV 3.

Chapter 8: Topology Design and Identification for Dynamic Networks

Figure 8.1 An illustrative example of NTI concept.

Figure 8.2 Distribution of all feasible solutions satisfying the cardinality constraint on edge set to maximize for a network with .

Figure 8.3 Optimal topology from IRM for maximum with . The total computation time for 44 iterations is 5.5100 s.

Figure 8.4 Optimal topology for maximum with .

Figure 8.5 Convergence history of for maximum with .

Figure 8.6 Designed edge weights for maximum with at each iteration.

Figure 8.7 Optimal topology for minimum total effective resistance with .

Figure 8.8 Designed edge weights for the minimum total effective resistance with at each iteration.

Figure 8.9 Original graph topology with six nodes for the simulation example of network identification problem.

Figure 8.10 Simulation example for network identification of a six-node graph: convergence history of at each iteration.

Chapter 9: Distributed Multi-Agent Coordination with Uncertain Interactions: A Probabilistic Perspective

Figure 9.1 The lower bound of the probability of coordination for agents.

Figure 9.2 . The nodes represent the agents and the line connecting a pair of agents represents the undirected interaction between them.

Figure 9.3

. The nodes represent the agents and the line connecting a pair of agents represents the undirected interaction between them.

Figure 9.4 . The nodes represent the agents and the line connecting a pair of agents represents the undirected interaction between them.

Figure 9.5 Simulation results for Case 1 with 100 repeated tests.

Figure 9.6 Simulation results for Case 2 with 100 repeated tests.

Chapter 10: Awareness Coverage Control in Unknown Environments Using Heterogeneous Multi-Robot Systems

Figure 10.1 Nonholonomic differential drive wheeled mobile robot model.

Figure 10.2 An UAV tracks the boundary of the task domain. The boundary line is represented by the solid line starts from and ends at . The shaded area represents the camera sensing range.

Figure 10.3 Camera sensor model with pose , where .

Figure 10.4 An illustrative example of robot 's map construction with information from three boundary-tracking UAVs.

Figure 10.5 Saturation function.

Figure 10.6 Vectors within the sensor range.

Figure 10.7 Simulated simultaneous boundary tracking and domain coverage. Time steps (a) , (b) , (c) , (d) , (e) , and (f) .

Figure 10.8 Coverage metrics and robot poses. (a) Global awareness metrics. (b) Local awareness metrics. (c) Pose of coverage robots.

List of Tables

Chapter 2: Sensor Placement Algorithms for a Path Covering Problem

Table 2.1 Numerical guarantees obtained for

Table 2.2 Numerical guarantees obtained for

Chapter 3: Robust Coordination of Small UAVs for Vision-Based Target Tracking Using Output-Feedback MPC with MHE

Table 3.1 Simulation parameters

Table 3.2 Computation time and percent of convergence

Table 3.3 Constant velocity target

Table 3.4 Evasive target

Table 3.5 Experimental target log

Chapter 5: Greedy Maximization for Asset-Based Weapon–Target Assignment with Time-Dependent Rewards

Table 5.1 Parameters for simple TSWTA example

Chapter 6: Coordinated Threat Assignments and Mission Management of Unmanned Aerial Vehicles

Table 6.1 Multiple targets

Table 6.2 Multiple targets with target rewards

Table 6.3 Multiple Targets: three UAVs

Chapter 7: Event-Triggered Communication and Control for Multi-Agent Average Consensus

Table 7.1 Event-triggered multi-agent average consensus

Table 7.2 Centralized event-triggered control

Table 7.3 Decentralized event-triggered control

Table 7.4 Decentralized event-triggered coordination (time-dependent)

Table 7.5 Decentralized event-triggered coordination (state-dependent)

Table 7.6 Decentralized event-triggered coordination on directed graphs

Table 7.7 Periodic event-triggered coordination on directed graphs

Cooperative Control of Multi-Agent Systems

Theory and Applications

Edited by

Yue Wang

Clemson University, USA

Eloy Garcia

InfoSciTex Corp, USA and Air Force Research Laboratory, USA

David Casbeer

Air Force Research Laboratory, USA

Fumin Zhang

Georgia Institute of Technology, USA

This edition first published 2017 © 2017 John Wiley and Sons Ltd

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by law. Advice on how to obtain permision to reuse material from this title is available at http://www.wiley.com/go/permissions.

The right of Yue Wang, Eloy Garcia, David Casbeer and Fumin Zhang to be identified as the editors of this work/of the editorial material in this work has been asserted in accordance with law.

Registered Offices

John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA

John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, UK

Editorial Office

The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, UK

For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.

Wiley also publishes its books in a variety of electronic formats and by print-on-demand. Some content that appears in standard print versions of this book may not be available in other formats.

Limit of Liability/Disclaimer of Warranty: While the publisher and authors have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

Library of Congress Cataloging-in-Publication Data applied for

Hardback ISBN: 9781119266129

Cover Design: Wiley

Cover Image: © Stocktrek Images/Gettyimages

To our advisors, students, and family

List of Contributors

Yongcan Cao

Department of Electrical and Computer Engineering

University of Texas at San Antonio

San Antonio, TX

USA

David Casbeer

The Control Science Center of Excellence

Air Force Research Laboratory

Wright-Patterson AFB, OH

USA

Doo-Hyun Cho

Department of Aerospace Engineering

Korea Advanced Institute of Science and Technology

Daejeon

South Korea

Han-Lim Choi

Department of Aerospace Engineering

Korea Advanced Institute of Science and Technology

Daejeon

South Korea

David A. Copp

Center for Control, Dynamical Systems, and Computation

University of California

Santa Barbara, CA

USA

Jorge Cortes

Department of Mechanical and Aerospace Engineering

University of California

San Diego, CA

USA

Ran Dai

The Aerospace Engineering Department

Iowa State University

Ames, IA

USA

Eloy Garcia

InfoSciTex Corp, USA and

Air Force Research Laboratory

Wright-Patterson AFB, OH

USA

João P. Hespanha

Center for Control, Dynamical Systems, and Computation

University of California

Santa Barbara, CA

USA

Derek Kingston

The Control Science Center of Excellence

Air Force Research Laboratory

Wright-Patterson AFB, OH

USA

Cameron Nowzari

Department of Electrical and Systems Engineering

University of Pennsylvania

Pennsylvania, PA

USA

George J. Pappas

Department of Electrical and Systems Engineering

University of Pennsylvania

Pennsylvania, PA

USA

Steven A. P. Quintero

Center for Control, Dynamical Systems, and Computation

University of California

Santa Barbara, CA

USA

Sivakumar Rathinam

Department of Mechanical Engineering

Texas A&M University

College Station, TX

USA

Corey Schumacher

Air Force Research Laboratory

Wright-Patterson AFB, OH

USA

Rajnikant Sharma

Department of Electrical and Computer Engineering

Utah State University

Logan, UT

USA

Chuangchuang Sun

The Aerospace Engineering Department

Iowa State University

Ames, IA

USA

Li Wang

Department of Mechanical Engineering

Clemson University

Clemson, SC

USA

Xiaofeng Wang

Department of Electrical Engineering

University of South Carolina

Columbia, SC

USA

Yue Wang

Department of Mechanical Engineering

Clemson University

Clemson, SC

USA

Fumin Zhang

School of Electrical and Computer Engineering

Georgia Institute of Technology

Atlanta, GA

USA

Zheqing Zhou

Department of Electrical Engineering

University of South Carolina

Columbia, SC

USA

Preface

This book presents new developments in both the fundamental research and applications in the field of multi-agent systems where a team of agents cooperatively achieve a common goal. Multi-agent systems play an important role in defense and civilian sectors and have the potential to impact on areas such as search and rescue, surveillance, and transportation. Cooperative control algorithms are essential to the coordination among multiple agents and hence realization of an effective multi-agent system. The contents of this book aim at linking basic research and cooperative control methodologies with more advanced applications and real-world problems.

The chapters in this book seek to provide recent developments in the cooperative control of multi-agent systems from a practical perspective. Chapter 1 provides an overview of the state of the art in multi-agent systems and summarizes existing works in consensus control, formation control, synchronization and output regulation, leader and/or target tracking, optimal control, coverage control, passivity-based control, and event-triggered control. Chapter 2 develops sensor placement algorithms for a team of autonomous unmanned vehicles (AUVs) for a path covering problem with monitoring applications in GPS-denied environments. Chapter 3 proposes vision-based output-feedback MPC algorithms with moving horizon estimation for target tracking using fixed-wing unmanned aerial vehicles (UAVs) in measurements gathering and real-time decision-making tasks. Chapter 4 presents the continuous-time projection-based consensus algorithms for multi-UAV simultaneous arrival problem under velocity constraints and finds the convergence rate of the proposed consensus algorithms. Chapter 5 discusses the asset-based weapon-target assignment (WTA) problem to find the optimal launching time of a weapon to maximize the sum of asset values with time-dependent rewards. Chapter 6 presents a coordinated decision algorithm where a group of UAVs is assigned to a set of targets to minimize some cost terms associated with the mission. Chapter 7 provides a formal analysis of event-triggered control and communication techniques for multi-agent average consensus problems. Chapter 8 solves network topology design and identification problems for dynamic networks. Chapter 9 discusses stochastic interaction for distributed multi-agent systems and presents results about the probabilities to achieve multi-agent coordination. Finally, Chapter 10 addresses a cooperative coverage control problem employing wheeled mobile robots (WMRs) and UAVs.

August 2016

Yue WangClemson University

Eloy GarciaAir Force Research Laboratory,Wright-Patterson AFB

David CasbeerAir Force Research Laboratory,Wright-Patterson AFB

Fumin ZhangGeorgia Institute of Technology

Acknowledgment

The editors would like to thank the authors of all the chapters and reviewers who worked together on this book. A special acknowledgment goes to all the graduate students in the Interdisciplinary & Intelligent Research (I2R) Laboratory in the Mechanical Engineering Department at Clemson University, who assisted the editors to review chapters and provided useful feedbacks to improve the quality of the book. The first editor would like to thank the support from the National Science Foundation under Grant No. CMMI-1454139. The editors would also like to thank Wiley and its staff for the professional support.

Chapter 1Introduction

Yue Wang1, Eloy Garcia2, David Casbeer2 and Fumin Zhang3

1Department of Mechanical Engineering, Clemson University, Clemson, SC, USA

2The Control Science Center of Excellence, Air Force Research Laboratory, Wright-Patterson AFB, OH, USA

3School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA, USA

1.1 Introduction

Many military and civilian applications require a team of agents to coordinate with each other to perform specific tasks without human intervention. In those systems, individual agents (e.g., unmanned underwater/ground/aerial vehicles) have limited capabilities due to short sensing and communication ranges, and small computational power. However, their collective behavior exhibits significant advantages compared to a single sophisticated agent, including large-scale spatial distribution, robustness, high scalability, and low cost [1]. The deployment of large-scale multi-agent systems with constrained costs and smaller sizes can thus achieve tasks that are otherwise unable to be finished by a single agent. Teams of engineered multi-agent systems can collect and process data and perform tasks cooperatively [2–8]. Multi-agent systems play an important role in a wide range of applications such as search and rescue [9], tracking/classification [10–14], surveillance [15, 16], space exploration [17], and radiation shielding and site clearing [18]. Multi-agent systems have also been considered and utilized in fields such as cooperative mobile robotics [19], distributed artificial intelligence and computing [20–22], wireless sensor networks [23], biology [24], social study [25], smart grids [26], traffic management [27, 28], and supply-chain management [29]. Therefore, the use of multi-agent system technologies in both everyday modern society and national defense and homeland security is bound to tremendously increase. In this book, we aim to provide an overview of recent progresses made in the cooperative control of multi-agent systems on both fundamental theory development as well as applications.

In the control community, multi-agent system theory has focused on developing vehicle motion control laws for various tasks including consensus and formation control [2, 30–43], coverage control [44–48], target search and tracking [3–5, 49, 50], task allocation problems [25, 51–53], sensor management problems [14], output regulation [54, 55], optimization [56], and estimation. Three types of control schemes for multi-agent systems have been proposed in the open literature, that is, centralized [57], decentralized [58], and distributed multi-agent control [1]. The centralized control scheme assumes global knowledge of the multi-agent system and seeks to achieve some control objective considering all agents' states, which inevitably suffers from the scalability issue. The decentralized control scheme computes control actions based only on an agent's local information while the more popular distributed control scheme takes both the agent's own information and neighboring agents' information into account to calculate the control action. Both the decentralized and distributed control algorithms provide scalable solutions and can be implemented under minimal connectivity properties. On the other hand, connectivity preserving protocols are developed for multi-agent systems to keep connected and hence guarantee motion stability [59, 60]. The problem has been considered in scenarios such as flocking [61, 62], rendezvous [59, 63], and formation control [64, 65]. The control hierarchy for multi-agent systems can be categorized into two classes, that is, top-down and bottom-up methodologies [66]. The top-down scheme assigns an overarching objective for the multi-agent system and designs control action for each individual agent to achieve this objective. The top-down multi-agent task decomposition is often difficult. While the bottom-up scheme directly defines each individual agent's local control action and their cooperation protocol, which however cannot guarantee any global objective. The paper [67] provides an overview of progresses made in the distributed multi-agent coordination. The books [64, 68] provide an introduction to the distributed control of multi-agent systems. The book [1] discusses the distributed control of multi-agent systems from four main themes, or dimensions: distributed control and computation, adversarial interactions, uncertain evolution, and complexity management. A special category of multi-agent systems, multi-robot systems, has become one of the most important areas of research in robotics [19]. Significant advance has been made in distributed control and collaboration of multi-robot systems in control theory and artificial intelligence [68–70]. There are a considerable amount of works on multi-agent consensus and formation control, and synchronization. We briefly summarize the main results as follows.

The multi-agent consensus control problem ensures that a group of mobile agents stays connected and reaches agreement while achieving some performance objective [64]. The papers [71, 72] provide a good survey of consensus problems in multi-agent cooperative control. In [64], the consensus problem is considered over dynamic interaction graphs by adding appropriate weights to the edges in the graphs. Theoretical results regarding consensus seeking under both time-invariant and dynamically changing information exchange topologies are summarized. Applications of consensus protocols to multi-agent coordination are investigated. In [73, 74], consensus algorithms are extended for second-order nonlinear dynamics in a dynamic proximity network. Necessary and sufficient conditions are given to ensure second-order consensus. In [75], leader-following consensus algorithms are developed for a linear multi-agent system on a switching network, where the input of each agent is subject to saturation. In [76], multi-agent consensus based on the opinion dynamics introduced by Krause is studied. A new proof of convergence is given with all agents in the same cluster holding the same opinion (represented by a real number). Lower bounds on the inter-cluster distances at a stable equilibrium are derived. In [33], multi-agent consensus is considered for an active leader-tracking problem under variable interconnection topology. The effects of delays on multi-agent consensus have been considered in [77].

The paper [78] provides a survey of formation control of multi-agent systems. The existing results are categorized into position-, displacement-, and distance-based control. The finite-time formation control for nonlinear multi-agent systems is investigated in [43]. A small number of agents navigate the whole team based on the global information of the desired formation while the other agents regulate their positions by the local information in a distributed manner. A class of nonlinear consensus protocols is first ensured and then applied to the formation control. In [79], a model-independent coordination strategy is proposed for multi-agent formation control in combination with tracking control for a virtual leader. The authors show that the formation error can be stabilized if the agents can track their respective reference points perfectly or if the tracking errors are bounded. In [80], a decentralized cooperative controller for multi-agent formation control and collision avoidance is developed based on the navigation function formalism. The control law is designed as the gradient of a navigation function whose minimum corresponds to the desired formation. Multi-agent formation control with intermittent information exchange is considered in [81]. Energy-based analysis is utilized to derive stability conditions. The paper [82] investigates rotating consensus and formation control problems of second-order multi-agent systems based on Lyapunov theory. Both theoretical and experimental results are presented in [42] on multi-agent decentralized control that achieves leader–follower formation control and collision avoidance for multiple nonholonomic robots.

In [83], synchronization approach is developed for trajectory tracking of multiple mobile robots while maintaining time-varying formations. In [84], synchronization algorithms are designed in a leader–follower cooperative tracking control problem where the agents are modeled as identical general linear systems on a digraph containing a spanning tree. The control framework includes full-state feedback control, observer design, and dynamic output feedback control. In [54], a distributed control scheme is adopted for robust output regulation in a multi-agent system where both the reference inputs and disturbances are generated by an exosystem. In [55], the output regulation problem is extended to multi-agent systems where a group of subsystems cannot access the exogenous signal. In [85], output consensus algorithms are developed for heterogeneous agents with parametric uncertainties. The multi-agent output synchronization problem is also studied in [86] where the coupling among the agents is nonlinear and there are communication delays. In [87], a general result for the robust output regulation problem has been studied for linear uncertain multi-agent systems. In [88], finite-time synchronization is proposed for a class of second-order nonlinear homogenous multi-agent systems with a leader–follower architecture. A finite-time convergent observer and an observer-based finite-time output feedback controller are developed to achieve the goal.

In [89], distributed tracking control is developed for linear multi-agent systems and a leader whose control input is nonzero, bounded, and not available to any follower. The paper [90] considers multi-agent tracking of a high-dimensional active leader, whose state not only keeps changing but also may not be measured. A neighbor-based local state-estimator and controller is developed for each autonomous following agent. A collision-free target-tracking problem of multi-agent robot system is considered in [91], where a cost function using a semi-cooperative Stackelberg equilibrium point component with weights tuned by a proportional-derivative (PD)-like fuzzy controller is formulated. The distributed finite-time tracking control of second-order multi-agent systems is considered in [92]. Observer-based state feedback control algorithms are designed to achieve finite-time tracking in a multi-agent leader-follower system and extended to multiple active leaders. There are also a lot of works focusing on multi-agent target tracking. In [93], the optimal sensor placement and motion coordination strategies for mobile sensor networks are developed in a target-tracking application. Gradient-descent decentralized motion planning algorithms are developed in [94] for multiple cooperating mobile sensor agents for the tracking of dynamic targets. The problem of target tracking and obstacle avoidance for multi-agent systems is considered in [95]. A potential function-based motion control algorithm is proposed to solve the problem where multiple agents cannot effectively track the target while avoiding obstacles at the same time.

The book [96] gives an overview of optimal and adaptive control methods for multi-agent systems. In [56], a distributed subgradient method is developed to solve a multi-agent convex optimization problem where every agent minimizes its own objective function while exchanging information locally with other agents in the network over a time-varying topology. An inverse optimality-based distributed cooperative control law is designed in [97] to guarantee consensus and global optimality of multi-agent systems, where the communication graph topology interplays with the agent dynamics. The work [98] applies stochastic optimal control theory to multi-agent systems, where the agent dynamics evolve with Wiener noise. The goal is to minimize some cost function of different agent–target combinations so that decentralized agents are distributed optimally over a number of targets. An optimal control framework for persistent monitoring using multi-agent systems is developed in [99] to design cooperative motion control laws to minimize an uncertainty metric in a given mission space. The problem leads to hybrid systems analysis, and an infinitesimal perturbation analysis (IPA) is used to obtain an online solution.

Coverage control considers the problem of fully covering a task domain using multi-agent systems. The problem can be solved by either deploying multiple agents to optimal locations in the domain or designing dynamic motion control laws for the agents so as to gradually cover the entire domain. The former solutions entail locational optimization for networked multi-agent systems. Voronoi diagram–based approaches are introduced in [100] to develop decentralized control laws for multiple vehicles for optimal coverage and sensing policies. Gradient descent–based schemes are utilized to drive a vehicle toward the Voronoi centeriod for optimal localization. In [101], the discrete coverage control law is developed and unified with averaging control laws over acyclic digraphs with fixed and controlled-switching topology. In [102], unicycle dynamics are considered and the coverage control algorithms are analyzed with an invariance principle for hybrid systems. The latter solutions focus on the case when the union of the agents' sensor cannot cover the task domain and hence dynamic motion control needs to be designed so that the agents can travel and collaboratively cover the entire domain [103]. A distributed coverage control scheme is developed in [104, 105] for mobile sensor networks, where the sensor has a limited range and is defined by a probabilistic model. A gradient-based control algorithm is developed to maximize the joint detection probabilities of random events taking place. Effective coverage control is developed to dynamically cover a given 2D region using a set of mobile sensor agents [46, 106]. Awareness-based coverage control has been proposed to dynamically cover a task domain based on the level of awareness an agent has with respect to the domain [48]. The paper [107] extends the awareness coverage control by defining a density function that characterizes the importance of each point in the domain and the desired awareness coverage level as a nondecreasing differentiable function of the density distribution. In [108], awareness and persistence coverage control are addressed simultaneously so that the mission domain can be covered periodically while the desired awareness is satisfied.

Passivity-based control approaches have also been developed to guarantee the stability of multi-agent systems [109]. Passivity is an energy-based method and a stronger system property that implies stability [110, 111]. A system is passive if it does not create energy, that is, the stored energy is less than the supplied energy. The negative feedback interconnection and parallel interconnection of passive systems are still passive. The paper [112] discusses the stabilization and output synchronization for a network of interconnected nonlinear passive agents by characterizing the information exchange structure. In [113], a passivity-based cooperative control is developed for multi-agent systems and the group synchronization is proved with the proposed backstepping controller using the Krasovskii–LaSalle invariance principle. The paper [114] introduces a discrete-time asymptotic multi-unmanned aerial vehicle (UAV) formation control that uses a passivity-based method to ensure stability in the presence of overlay network topology with delays and data loss. Passivity-based motion coordination has also been used in [115] for the attitude synchronization of rigid bodies in the leader–follower case with communication delay and temporary communication failures. The work [116] uses the multiple Lyapunov function method for the output synchronization of a class of networked passive agents with switching topology. The concept of stochastic passivity is studied for a team of agents modeled as discrete-time Markovian jump nonlinear systems [117]. Passivity-based approaches have also been widely used in the bilateral teleoperation of robots and multi-agent systems. A good amount of work has utilized the scattering wave transformation and two-port network theory to provide stability of the teleoperation under constant communication delays for velocity tracking. A passifying PD controller is developed in [118] for the bilateral teleoperation of multiple mobile slave agents coupled to a single master robot under constant, bounded communication delays. The paper [119] extends the passivity-based architecture to guarantee state (velocity as well as position) synchronization of master/slave robots without using the wave scattering transformation. Passivity-based control strategies are also utilized for the bilateral teleoperation of multiple UAVs [120].

Extensive results presenting algorithms and control methodologies for multi-agent systems cooperation rely on continuous communication between agents. Continuous actuation and continuous measurement of local states may be restricted by particular hardware limitations. A problem in many scenarios is given by the limited communication bandwidth where neighboring agents are not capable of communicating continuously but only at discrete time instants. Limitations and constraints on inter-agent communication may affect any multi-agent network. Consensus problems, in particular, have been analyzed in the context of noncontinuous actuation and noncontinuous inter-agent communication. Several techniques are devised in order to schedule sensor and actuation updates. The sampled-data (periodic) approach [121–123], and [124] represents a first attempt to address these issues. The implementation of periodic communication represents a simple and practical tool that addresses the continuous communication constraint. However, an important drawback of periodic transmission is that it requires synchronization between the agents in two similar aspects: sampling period and sampling time instants, both of which are difficult to meet in practice. First, most results available require every agent to implement the same sampling period. This may not be achievable in many networks of decentralized agents and it is also difficult to globally redefine new sampling periods. Second, not only the agents need to implement the same sampling periods, but also they need to transmit information all at the same time instants. Under this situation each agent is also required to determine the time instants at which it needs to transmit relevant information to its neighbors. Even when agents can adjust and implement the same sampling periods, they also need to synchronize and transmit information at the same time instants for the corresponding algorithms to guarantee the desired convergence properties. Besides being a difficult task to achieve in a decentralized way, the synchronization of time instants is undesirable because all agents are occupying network resources at the same time instants. In wireless networks, the simultaneous transmission of information by each agent may increase the likelihood of packet dropouts since agents that are supposed to receive information from different sources may not be able to successfully receive and process all information at the same time.

Therefore, event-triggered and self-triggered controls for multi-agent systems have been considered for agents with limited resources to gather information and actuate. The event-triggered schemes allow each agent to only send information across the network intermittently and independently determine the time instants when they need to communicate [57]. The use of event-triggered control techniques for decentralized control and coordination has spurred a new area of research that relaxes previous assumptions and constraints associated with the control of multiple agents. In event-triggered control [125–130], a subsystem monitors its own state and transmits a state measurement to the non-collocated controller only when it is necessary, that is, only when a measure of the local subsystem state error is above a specified threshold. In general, the state error measures the difference between the current state and the last transmitted state value. The controller transmits an update by examining the measurement errors with respect to some state-dependent threshold and hence requires continuous monitoring of state error. In many instances, it is possible to reduce communication instances using event-triggered communication with respect to periodic implementations. This is of great importance in applications where bandwidth or communication resources are scarce. Consensus problems where all agents are described by general linear models [131, 132], have been studied assuming continuous communication among agents. Event-triggered control and communication methods for agents with linear dynamics were recently studied in [133–138]. Event-triggered control methods have also been applied to analyze consensus problems with limited actuation rates. In [139], agents with single integrator dynamics are considered and an event-triggered control technique is implemented in order for each agent to determine the time instants to update their control inputs. Continuous exchange of information is assumed in [139] and the event-triggered controller is only used to avoid continuous actuation at each node. In general, the decentralized event-triggered consensus problem with limited communication is a more challenging problem than the event-triggered control for limiting actuation updates. The main reason is that agents need to take decisions (on when to transmit their state information) based on outdated neighbor state updates. In this scenario, each agent has continuous access to its own state; however, it only has access to the last update transmitted by its neighbors. Several approaches for the event-triggered consensus with limited communication are documented in [140–145]. In this sense, event-triggered control provides a more robust and efficient use of network bandwidth. Its implementation in multi-agent systems also provides a highly decentralized way to schedule transmission instants, which does not require synchronization compared to periodic sampled-data approaches. Different problems concerning the transmission of information in multi-agent networks such as communication delays and packet dropouts have been explicitly addressed using event-triggered control methods [146]. In the extended self-triggered control, each agent will compute its next update time based on the available information from the last sampled state, without the necessity to keep track of the state error in order to determine when a future sample of the state should be taken. In [140], an event-based scheduling is developed for multi-agent broadcasting and asymptotic convergence to average consensus is guaranteed. This paradigm has also been extended to distributed estimation and optimization [147].

1.2 Chapter Summary and Contributions

Chapter 2 develops sensor deployment algorithms for a team of autonomous unmanned vehicles (AUVs) for path coverage problem with monitoring applications in GPS-denied environments. The approach used in this chapter tracks the AUV position in GPS-denied environments by analyzing the radio signals received from a suitably positioned network of proxy landmarks. This problem is referred to as the landmark placement problem (LPP) and it is required to use minimum number of landmarks to cover the entire path of the AUV. Two -approximate ( and 5, respectively) algorithms are proposed to solve the LPP in polynomial time and provide solutions whose cost is at most times from the optimum. It is assumed that a target in a vehicle's path is defined to be covered by a landmark and the distance between a target and a landmark is at most equal to . A greedy algorithm is first proposed for a simpler LPP where all the targets lie within a vertical strip of width equal to and the landmarks are restricted to be on a single, vertical line. The algorithm is then extended to a general LPP by partitioning the plane into vertical strips of width with approximation ratio . The second approximate algorithm with is developed based on a 4-approximation algorithm for a unit disc problem. Two phases are involved in this algorithm: (i) identification of a subset of targets using a simple greedy algorithm and (ii) addition of landmarks in the vicinity of each target in the subset. Both theoretical guarantees and numerical simulations are provided to show the performance of the proposed approximation algorithms.

Chapter 3