Freshly Printed - allow 7 days lead
Couldn't load pickup availability
Cooperative Control of Distributed Multi-Agent Systems
Jeff Shamma (Edited by), J Shamma (Author)
9780470060315, Wiley
Hardback, published 7 December 2007
464 pages
25 x 17.4 x 3 cm, 0.948 kg
The paradigm of ‘multi-agent’ cooperative control is the challenge frontier for new control system application domains, and as a research area it has experienced a considerable increase in activity in recent years. This volume, the result of a UCLA collaborative project with Caltech, Cornell and MIT, presents cutting edge results in terms of the “dimensions” of cooperative control from leading researchers worldwide. This dimensional decomposition allows the reader to assess the multi-faceted landscape of cooperative control. Cooperative Control of Distributed Multi-Agent Systems is organized into four main themes, or dimensions, of cooperative control: distributed control and computation, adversarial interactions, uncertain evolution and complexity management. The military application of autonomous vehicles systems or multiple unmanned vehicles is primarily targeted; however much of the material is relevant to a broader range of multi-agent systems including cooperative robotics, distributed computing, sensor networks and data network congestion control. Cooperative Control of Distributed Multi-Agent Systems offers the reader an organized presentation of a variety of recent research advances, supporting software and experimental data on the resolution of the cooperative control problem. It will appeal to senior academics, researchers and graduate students as well as engineers working in the areas of cooperative systems, control and optimization.
List of Contributors xiii Preface xv Part I Introduction 1 1 Dimensions of cooperative control 3 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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
Jeff S. Shamma and Gurdal Arslan
Reza Olfati-Saber
Sonja Glavaˇski, Anca Williams and Tariq Samad
William B. Dunbar
Tam´as Keviczky, Francesco Borrelli and Gary J. Balas
Brandon J. Moore and Kevin M. Passino
Alessandro Arsie, John J. Enright and Emilio Frazzoli
Eric Feron and Jan DeMot
Vincent Pei-wen Seah and Jeff S. Shamma
Matthew G. Earl and Raffaello D’Andrea
Georgios C. Chasparis and Jeff S. Shamma
Ashitosh Swarup and Jason L. Speyer
Nuno C. Martins and Munther A. Dahleh
Daniel Choukroun and Jason L. Speyer
Y. Lee, T.C. Collier, C.E. Taylor and E.P. Stabler
Domitilla Del Vecchio and Richard M. Murray
V. G. Rao, S. Goldfarb and R. D’Andrea
Subject Areas: Electronics & communications engineering [TJ]
