Table of Contents
List of Contributors xiii
Preface xv
Part I Introduction 1
1 Dimensions of cooperative control 3
Jeff S. Shamma and Gurdal Arslan
1.1 Why cooperative control? 3
1.1.1 Motivation 3
1.1.2 Illustrative example: command and control of networked vehicles 4
1.2 Dimensions of cooperative control 5
1.2.1 Distributed control and computation 5
1.2.2 Adversarial interactions 11
1.2.3 Uncertain evolution 14
1.2.4 Complexity management 15
1.3 Future directions 16
Acknowledgements 17
References 17
Part II Distributed Control and Computation 19
2 Design of behavior of swarms: From flocking to data fusion using microfilter networks 21
Reza Olfati-Saber
2.1 Introduction 21
2.2 Consensus problems 22
2.3 Flocking behavior for distributed coverage 25
2.3.1 Collective potential of flocks 27
2.3.2 Distributed flocking algorithms 29
2.3.3 Stability analysis for flocking motion 30
2.3.4 Simulations of flocking 32
2.4 Microfilter networks for cooperative data fusion 32
Acknowledgements 39
References 39
3 Connectivity and convergence of formations 43
Sonja Glavaˇski, Anca Williams and Tariq Samad
3.1 Introduction 43
3.2 Problem formulation 44
3.3 Algebraic graph theory 46
3.4 Stability of vehicle formations in the case of time-invariant communication 48
3.4.1 Formation hierarchy 48
3.5 Stability of vehicle formations in the case of time-variant communication 54
3.6 Stabilizing feedback for the time-variant communication case 57
3.7 Graph connectivity and stability of vehicle formations 58
3.8 Conclusion 60
Acknowledgements 60
References 61
4 Distributed receding horizon control: stability via move suppression 63
William B. Dunbar
4.1 Introduction 63
4.2 System description and objective 64
4.3 Distributed receding horizon control 68
4.4 Feasibility and stability analysis 72
4.5 Conclusion 76
Acknowledgement 76
References 76
5 Distributed predictive control: synthesis, stability and feasibility 79
Tam´as Keviczky, Francesco Borrelli and Gary J. Balas
5.1 Introduction 79
5.2 Problem formulation 81
5.3 Distributed MPC scheme 83
5.4 DMPC stability analysis 85
5.4.1 Individual value functions as Lyapunov functions 87
5.4.2 Generalization to arbitrary number of nodes and graph 89
5.4.3 Exchange of information 90
5.4.4 Stability analysis for heterogeneous unconstrained LTI subsystems 91
5.5 Distributed design for identical unconstrained LTI subsystems 93
5.5.1 LQR properties for dynamically decoupled systems 95
5.5.2 Distributed LQR design 98
5.6 Ensuring feasibility 102
5.6.1 Robust constraint fulfillment 102
5.6.2 Review of methodologies 103
5.7 Conclusion 106
References 107
6 Task assignment for mobile agents 109
Brandon J. Moore and Kevin M. Passino
6.1 Introduction 109
6.2 Background 111
6.2.1 Primal and dual problems 111
6.2.2 Auction algorithm 113
6.3 Problem statement 115
6.3.1 Feasible and optimal vehicle trajectories 115
6.3.2 Benefit functions 117
6.4 Assignment algorithm and results 118
6.4.1 Assumptions 118
6.4.2 Motion control for a distributed auction 119
6.4.3 Assignment algorithm termination 120
6.4.4 Optimality bounds 124
6.4.5 Early task completion 128
6.5 Simulations 130
6.5.1 Effects of delays 130
6.5.2 Effects of bidding increment 132
6.5.3 Early task completions 133
6.5.4 Distributed vs. centralized computation 134
6.6 Conclusions 136
Acknowledgements 137
References 137
7 On the value of information in dynamic multiple-vehicle routing problems 139
Alessandro Arsie, John J. Enright and Emilio Frazzoli
7.1 Introduction 139
7.2 Problem formulation 141
7.3 Control policy description 144
7.3.1 A control policy requiring no explicit communication: the unlimited sensing capabilities case 144
7.3.2 A control policy requiring communication among closest neighbors: the limited sensing capabilities case 145
7.3.3 A sensor-based control policy 148
7.4 Performance analysis in light load 150
7.4.1 Overview of the system behavior in the light load regime 150
7.4.2 Convergence of reference points 152
7.4.3 Convergence to the generalized median 156
7.4.4 Fairness and efficiency 157
7.4.5 A comparison with algorithms for vector quantization and centroidal Voronoi tessellations 160
7.5 A performance analysis for sTP, mTP/FG and mTP policies 161
7.5.1 The case of sTP policy 161
7.5.2 The case of mTP/FG and mTP policies 167
7.6 Some numerical results 169
7.6.1 Uniform distribution, light load 169
7.6.2 Non-uniform distribution, light load 169
7.6.3 Uniform distribution, dependency on the target generation rate 170
7.6.4 The sTP policy 171
7.7 Conclusions 172
References 175
8 Optimal agent cooperation with local information 177
Eric Feron and Jan DeMot
8.1 Introduction 177
8.2 Notation and problem formulation 179
8.3 Mathematical problem formulation 181
8.3.1 DP formulation 181
8.3.2 LP formulation 182
8.4 Algorithm overview and LP decomposition 184
8.4.1 Intuition and algorithm overview 184
8.4.2 LP decomposition 185
8.5 Fixed point computation 193
8.5.1 Single agent problem 193
8.5.2 Mixed forward-backward recursion 194
8.5.3 Forward recursion 198
8.5.4 LTI system 199
8.5.5 Computation of the optimal value function at small separations 202
8.6 Discussion and examples 205
8.7 Conclusion 209
Acknowledgements 209
References 210
9 Multiagent cooperation through egocentric modeling 213
Vincent Pei-wen Seah and Jeff S. Shamma
9.1 Introduction 213
9.2 Centralized and decentralized optimization 215
9.2.1 Markov model 215
9.2.2 Fully centralized optimization 218
9.2.3 Fully decentralized optimization 219
9.3 Evolutionary cooperation 220
9.4 Analysis of convergence 222
9.4.1 Idealized iterations and main result 222
9.4.2 Proof of Theorem 9.4.2 224
9.5 Conclusion 227
Acknowledgements 228
References 228
Part III Adversarial Interactions 231
10 Multi-vehicle cooperative control using mixed integer linear programming 233
Matthew G. Earl and Raffaello D’Andrea
10.1 Introduction 233
10.2 Vehicle dynamics 235
10.3 Obstacle avoidance 238
10.4 RoboFlag problems 241
10.4.1 Defensive Drill 1: one-on-one case 242
10.4.2 Defensive Drill 2: one-on-one case 247
10.4.3 ND-on-NA case 250
10.5 Average case complexity 251
10.6 Discussion 254
10.7 Appendix: Converting logic into inequalities 255
10.7.1 Equation (10.24) 256
10.7.2 Equation (10.33) 257
Acknowledgements 258
References 258
11 LP-based multi-vehicle path planning with adversaries 261
Georgios C. Chasparis and Jeff S. Shamma
11.1 Introduction 261
11.2 Problem formulation 263
11.2.1 State-space model 263
11.2.2 Single resource models 264
11.2.3 Adversarial environment 265
11.2.4 Model simplifications 265
11.2.5 Enemy modeling 266
11.3 Optimization set-up 267
11.3.1 Objective function 267
11.3.2 Constraints 268
11.3.3 Mixed-integer linear optimization 268
11.4 LP-based path planning 269
11.4.1 Linear programming relaxation 269
11.4.2 Suboptimal solution 269
11.4.3 Receding horizon implementation 270
11.5 Implementation 271
11.5.1 Defense path planning 271
11.5.2 Attack path planning 274
11.5.3 Simulations and discussion 276
11.6 Conclusion 278
Acknowledgements 278
References 279
12 Characterization of LQG differential games with different information patterns 281
Ashitosh Swarup and Jason L. Speyer
12.1 Introduction 281
12.2 Formulation of the discrete-time LQG game 282
12.3 Solution of the LQG game as the limit to the LEG Game 283
12.3.1 Problem formulation of the LEG Game 284
12.3.2 Solution to the LEG Game problem 285
12.3.3 Filter properties for small values of θ 288
12.3.4 Construction of the LEG equilibrium cost function 290
12.4 LQG game as the limit of the LEG Game 291
12.4.1 Behavior of filter in the limit 291
12.4.2 Limiting value of the cost 291
12.4.3 Convexity conditions 293
12.4.4 Results 293
12.5 Correlation properties of the LQG game filter in the limit 294
12.5.1 Characteristics of the matrix P−1 i Pi 295
12.5.2 Transformed filter equations 295
12.5.3 Correlation properties of ε2 i 296
12.5.4 Correlation properties of ε1 i 297
12.6 Cost function properties—effect of a perturbation in up 297
12.7 Performance of the Kalman filtering algorithm 298
12.8 Comparison with the Willman algorithm 299
12.9 Equilibrium properties of the cost function: the saddle interval 299
12.10 Conclusion 300
Acknowledgements 300
References 301
Part IV Uncertain Evolution 303
13 Modal estimation of jump linear systems: an information theoretic viewpoint 305
Nuno C. Martins and Munther A. Dahleh
13.1 Estimation of a class of hidden markov models 305
13.1.1 Notation 307
13.2 Problem statement 308
13.2.1 Main results 308
13.2.2 Posing the problem statement as a coding paradigm 309
13.2.3 Comparative analysis with previous work 309
13.3 Encoding and decoding 310
13.3.1 Description of the estimator (decoder) 311
13.4 Performance analysis 312
13.4.1 An efficient decoding algorithm 312
13.4.2 Numerical results 314
13.5 Auxiliary results leading to the proof of theorem 13.4.3 316
Acknowledgements 319
References 320
14 Conditionally-linear filtering for mode estimation in jump-linear systems 323
Daniel Choukroun and Jason L. Speyer
14.1 Introduction 323
14.2 Conditionally-Linear Filtering 324
14.2.1 Short review of the standard linear filtering problem 324
14.2.2 The conditionally-linear filtering problem 326
14.2.3 Discussion 330
14.3 Mode-estimation for jump-linear systems 333
14.3.1 Statement of the problem 333
14.3.2 State-space model for y k 335
14.3.3 Development of the conditionally-linear filter 337
14.3.4 Discussion 340
14.3.5 Reduced order filter 341
14.3.6 Comparison with Wonham filter 343
14.3.7 Case of noisy observations of xk 345
14.4 Numerical Example 350
14.4.1 Gyro failure detection from accurate spacecraft attitude measurements Description 350
14.5 Conclusion 354
14.6 Appendix A: Inner product of equation (14.14) 355
14.7 Appendix B: Development of the filter equations (14.36) to (14.37) 356
Acknowledgements 358
References 358
15 Cohesion of languages in grammar networks 359
Y. Lee, T.C. Collier, C.E. Taylor and E.P. Stabler
15.1 Introduction 359
15.2 Evolutionary dynamics of languages 360
15.3 Topologies of language populations 361
15.4 Language structure 363
15.5 Networks induced by structural similarity 365
15.5.1 Three equilibrium states 366
15.5.2 Density of grammar networks and language convergence 368
15.5.3 Rate of language convergence in grammar networks 370
15.6 Conclusion 372
Acknowledgements 374
References 374
Part V Complexity Management 377
16 Complexity management in the state estimation of multi-agent systems 379
Domitilla Del Vecchio and Richard M. Murray
16.1 Introduction 379
16.2 Motivating example 381
16.3 Basic concepts 384
16.3.1 Partial order theory 384
16.3.2 Deterministic transition systems 386
16.4 Problem formulation 387
16.5 Problem solution 388
16.6 Example: the RoboFlag Drill 391
16.6.1 RoboFlag Drill estimator 392
16.6.2 Complexity of the RoboFlag Drill estimator 394
16.6.3 Simulation results 395
16.7 Existence of discrete state estimators on a lattice 395
16.8 Extensions to the estimation of discrete and continuous variables 399
16.8.1 RoboFlag Drill with continuous dynamics 404
16.9 Conclusion 405
Acknowledgement 406
References 406
17 Abstraction-based command and control with patch models 409
V. G. Rao, S. Goldfarb and R. D’Andrea
17.1 Introduction 409
17.2 Overview of patch models 411
17.3 Realization and verification 415
17.4 Human and artificial decision-making 419
17.4.1 Example: the surround behavior 421
17.5 Hierarchical control 423
17.5.1 Information content and situation awareness 426
17.6 Conclusion 429
References 431
Index 433
