Machine Behavior Design And Analysis : A Consensus Perspective

In this book, we present our systematic investigations into consensus in multi-agent systems. We show the design and analysis of various types of consensus protocols from a multi-agent perspective with a focus on min-consensus and its variants. We also discuss second-order and high-order min-consensus. A very interesting topic regarding the link between consensus and path planning is also included. We show that a biased min-consensus protocol can lead to the path planning phenomenon, which means that the complexity of shortest path planning can emerge from a perturbed version of min-consensus protocol, which as a case study may encourage researchers in the field of distributed control to rethink the nature of complexity and the distance between control and intelligence. We also illustrate the design and analysis of consensus protocols for nonlinear multi-agent systems derived from an optimal control formulation, which do not require solving a Hamilton-Jacobi-Bellman (HJB) equation. The book was written in a self-contained format. For each consensus protocol, the performance is verified through simulative examples and analyzed via mathematical derivations, using tools like graph theory and modern control theory. The book’s goal is to provide not only theoretical contributions but also explore underlying intuitions from a methodological perspective. Preface 6 Acknowledgments 9 Contents 10 Acronyms 13 1 Background 14 1.1 Collective Machine Behaviour 14 1.2 Consensus 14 1.3 Theoretical Tools 15 1.4 Summary 16 References 16 2 Second-Order Min-Consensus 17 2.1 Introduction 17 2.2 Problem Formulation 18 2.3 Min-Consensus Under Switching Topology 18 2.3.1 Protocol 19 2.3.2 Theoretical Analysis 20 2.4 Simulation Example 24 2.5 Summary 25 References 26 3 High-Order Discrete-Time Consensus 32 3.1 Introduction 32 3.2 Problem Formulation 34 3.3 Consensus Protocols 35 3.3.1 Min-Type Protocol 35 3.3.2 Max-Type Protocol 36 3.4 Theoretical Analysis 37 3.4.1 Static Graphs 37 3.4.2 Time-Varying Graphs 40 3.5 Computer Simulations 43 3.5.1 Example 1 43 3.5.2 Example 2 45 3.5.3 Example 3 47 3.6 Summary 49 References 50 4 Continuous-Time Biased Min-Consensus 56 4.1 Introduction 56 4.2 Protocol 58 4.3 Theoretical Analysis 59 4.4 Equivalence to Shortest Path Planning 69 4.5 Simulations and Applications 70 4.5.1 Illustrative Example 71 4.5.2 Application to Maze Solving 72 4.5.3 Application to Complete Coverage 75 4.6 Summary 76 References 76 5 Discrete-Time Biased Min-Consensus 83 5.1 Introduction 83 5.2 Consensus Protocols 84 5.2.1 Protocol 85 5.2.2 Convergence Analysis 86 5.2.3 Relationship with Shortest Path Planning 91 5.3 Algorithms 92 5.3.1 Maze Solving 93 5.3.2 Complete Coverage 96 5.4 Computer Simulations 96 5.5 Applications 98 5.6 Summary 101 References 102 6 Biased Consensus Based Distributed Neural Network 107 6.1 Introduction 107 6.2 Problem Description 109 6.3 Unified Method 112 6.3.1 Classical Shortest Path Problem 112 6.3.2 Generalized Shortest Path Problem 114 6.4 Theoretical Analysis 116 6.5 Computer Simulations 121 6.5.1 Example 1 122 6.5.2 Example 2 122 6.6 Robot Navigation Application 125 6.7 Summary 127 References 128 7 Near-Optimal Consensus 135 7.1 Introduction 135 7.2 Problem Background 137 7.3 Consensus Protocols 139 7.3.1 Multiple Double Integrators 139 7.3.2 Multiple Linear Agents 142 7.3.3 Multiple Nonlinear Agents 145 7.4 Theoretical Analysis 148 7.4.1 Stability 149 7.4.2 Optimality of Cost Function 152 7.4.3 Existence of Matrix L 154 7.5 Simulation Results 156 7.5.1 Double-Integrator Agents 156 7.5.2 Second-Order Linear Agents 157 7.5.3 Second-Order Nonlinear Agents 158 7.6 Summary 160 References 161 8 Adaptive Near-Optimal Consensus 167 8.1 Introduction 167 8.2 Problem Formulation 169 8.3 Nominal Design 170 8.4 Adaptive Design 179 8.5 Computer Simulations 187 8.6 Conclusions 191 References 191 Decision making is an important component of machine behavior. The investi-gations on cooperative control and computing have shown that via cooperations,a team of simple agents can perform complex tasks. In this book, we show thedesign and analysis of machine behaviors from a consensus perspective. We discusssecond-order and high-order min-consensus. A very interesting topic regardingthe link between consensus and path planning is also included. We show that abiased min-consensus protocol can lead to the path planning phenomenon, whichmeans that the complexity of shortest path planning can emerge from a perturbedmin-consensus protocol, which as a case study may encourage researchers in thefield of distributed control to rethink the nature of complexity and the distancebetween control and intelligence