Cover
Preface
About the Companion Website
1 Introduction
1. 1.1 Motivation
2. 1.2 Notation
3. 1.3 Graph Theory
4. 1.4 Formation Control Problems
5. 1.5 Book Overview and Organization
6. 1.6 Notes and References
2 Single‐Integrator Model
1. 2.1 Formation Acquisition
2. 2.2 Formation Maneuvering
3. 2.3 Flocking
4. 2.4 Target Interception with Unknown Target Velocity
5. 2.5 Dynamic Formation Acquisition
6. 2.6 Simulation Results
7. 2.7 Notes and References
3 Double‐Integrator Model
1. 3.1 Cross‐Edge Energy
2. 3.2 Formation Acquisition
3. 3.3 Formation Maneuvering
4. 3.4 Target Interception with Unknown Target Acceleration
5. 3.5 Dynamic Formation Acquisition
6. 3.6 Simulation Results
7. 3.7 Notes and References
4 Robotic Vehicle Model
1. 4.1 Model Description
2. 4.2 Nonholonomic Kinematics
3. 4.3 Holonomic Dynamics
4. 4.4 Notes and References
5 Experimentation
1. 5.1 Experimental Platform
2. 5.2 Vehicle Equations of Motion
3. 5.3 Low‐Level Control Design
4. 5.4 Experimental Results
Appendix A: Matrix Theory and Linear Algebra
Appendix B: Functions and Signals
Appendix C: Systems Theory
1. C.1 Linear Systems
2. C.2 Nonlinear Systems
3. C.3 Lyapunov Stability
4. C.4 Input‐to‐State Stability
5. C.5 Nonsmooth Systems
6. C.6 Integrator Backstepping
Appendix D: Dynamic Model Terms
References
Index
End User License Agreement

List of Illustrations

Chapter 1
1. Figure 1.1 Examples of collective behavior in nature: a flock of birds (top lef...
2. Figure 1.2 Examples of engineering multi‐agent systems.
3. Figure 1.3 Centralized (left) and decentralized (right) formation control.
4. Figure 1.4 The complete graph .
5. Figure 1.5 Examples of bar‐and‐joint frameworks, although the joints here are no...
6. Figure 1.6 Example of (a) a graph and (b) a corresponding framework.
7. Figure 1.7 Rigid body kinematics.
8. Figure 1.8 Isomorphic frameworks.
9. Figure 1.9 Examples of (a) flexible and (b) rigid bar‐and‐joint frameworks.
10. Figure 1.10 Example of a rigid framework that is not infinitesimally rigid.
11. Figure 1.11 A nongeneric framework in .
12. Figure 1.12 A tetrahedron framework.
13. Figure 1.13 (a) Minimally and (b) nonminimally rigid graphs.
14. Figure 1.14 Examples of nonunique realizations for infinitesimally rigid framew...
15. Figure 1.15 (a) Rigidity versus (b) global rigidity.
16. Figure 1.16 Example of the construction of : a tetrahedron formation where st...
17. Figure 1.17 Overview of the book organization.
Chapter 2
1. Figure 2.1 Energy landscape showing the two equilibrium points, Iso and Amb , ...
2. Figure 2.2 (a) The collinearity of agents 1, 2, 3, and 4 is invariant. (b) The c...
3. Figure 2.3 Fixed and local coordinate frames.
4. Figure 2.4 Formation acquisition: desired formation .
5. Figure 2.5 Formation acquisition: agent trajectories , .
6. Figure 2.6 Formation acquisition: distance errors , .
7. Figure 2.7 Formation acquisition: control inputs , .
8. Figure 2.8 Formation acquisition: agents converging to an ambiguous framework.
9. Figure 2.9 Formation acquisition: (a) distance errors , and (b) distance erro...
10. Figure 2.10 Desired formation with modified edge set.
11. Figure 2.11 Formation acquisition: agents converging to correct formation after ...
12. Figure 2.12 Formation maneuvering (Simulation 1): desired formation .
13. Figure 2.13 Formation maneuvering (Simulation 1): snapshots of at different in...
14. Figure 2.14 Formation maneuvering (Simulation 1): distance errors , .
15. Figure 2.15 Formation maneuvering (Simulation 1): control inputs , .
16. Figure 2.16 Formation maneuvering (Simulation 2): desired formation .
17. Figure 2.17 Formation maneuvering (Simulation 2): snapshots in time of the forma...
18. Figure 2.18 Formation maneuvering (Simulation 2): distance errors , .
19. Figure 2.19 Formation maneuvering (Simulation 2): control inputs , in the ,
20. Figure 2.20 Flocking (continuous controller–observer; ): snapshots of at diff...
21. Figure 2.21 Flocking (continuous controller–observer; ): distance errors , .
22. Figure 2.22 Flocking (continuous controller–observer; ): velocity estimation er...
23. Figure 2.23 Flocking (continuous controller–observer; ): control inputs , in...
24. Figure 2.24 Flocking (continuous controller–observer; ): distance errors , .
25. Figure 2.25 Flocking (continuous controller–observer; ): velocity estimation er...
26. Figure 2.26 Flocking (continuous controller–observer; ): control inputs , in...
27. Figure 2.27 Flocking (continuous controller–observer; ): velocity estimation er...
28. Figure 2.28 Flocking (continuous controller–observer; ): distance errors with t...
29. Figure 2.29 Flocking (discontinuous controller–observer; ): distance errors wit...
30. Figure 2.30Figure 2.30 Flocking (discontinuous controller–observer; ): velocity...
31. Figure 2.31 Flocking (discontinuous controller–observer; ): control inputs.
32. Figure 2.32 Target interception: snapshots of at different instants of time al...
33. Figure 2.33 Target interception: distance errors , .
34. Figure 2.34 Target interception: control inputs , .
35. Figure 2.35 Dynamic formation: snapshots of at different instants of time alon...
36. Figure 2.36 Dynamic formation: distance errors , .
37. Figure 2.37 Dynamic formation: control inputs .
Chapter 3
1. Figure 3.1 Relationship between the (a) single‐ and (b) double‐integrator contr...
2. Figure 3.2 Energy landscape where the formation is at position with velocity
3. Figure 3.3 Desired formation (solid line) and a flip ambiguity (dashed line).
4. Figure 3.4 Triangulated hexagon framework.
5. Figure 3.5 Formation acquisition: desired formation .
6. Figure 3.6 Formation acquisition: agent trajectories , .
7. Figure 3.7 Formation acquisition: distance errors , .
8. Figure 3.8 Formation acquisition: velocity errors , .
9. Figure 3.9 Formation acquisition: control inputs , .
10. Figure 3.10 Dynamic formation acquisition with maneuvering: snapshots of at di...
11. Figure 3.11 Dynamic formation acquisition with maneuvering: distance errors ,
12. Figure 3.12 Dynamic formation acquisition with maneuvering: velocity errors ,
13. Figure 3.13 Dynamic formation acquisition with maneuvering: control inputs , .
14. Figure 3.14 Target interception: snapshots of at different instants of time al...
15. Figure 3.15 Target interception: distance errors , .
16. Figure 3.16 Target interception: velocity errors , .
17. Figure 3.17Figure 3.17 Target interception: control inputs , .
Chapter 4
1. Figure 4.1 The th robotic vehicle.
2. Figure 4.2 Desired formation .
3. Figure 4.3 Trajectory of the poses , .
4. Figure 4.4 Distance errors , (top) and orientation errors , (bottom).
5. Figure 4.5 Control inputs , (top) and , (bottom).
6. Figure 4.6 Trajectory of the hand positions , .
7. Figure 4.7 Distance errors , .
8. Figure 4.8 Control inputs , .
9. Figure 4.9 Parameter estimates for vehicle 1, .
Chapter 5
1. Figure 5.1 Top view of the experimental UGV platform.
2. Figure 5.2 Side view of the UGV.
3. Figure 5.3 Experimental control and communication scheme.
4. Figure 5.4 Schematic of the experimental UGV.
5. Figure 5.5 Friction force on the UGV.
6. Figure 5.6 Initial configuration of the UGVs during the experimental runs.
7. Figure 5.7 Single integrator: formation acquisition. UGV position trajectories
8. Figure 5.8 Single integrator: formation acquisition. UGV distance errors , .
9. Figure 5.9 Single integrator: formation acquisition. Drive‐wheel DC motor voltag...
10. Figure 5.10 Single integrator: formation acquisition. Steering angle commands ,...
11. Figure 5.11 Single integrator: formation acquisition. Velocity error for each ...
12. Figure 5.12 Single integrator: formation translation. UGV position trajectories
13. Figure 5.13 Single integrator: formation translation. UGV distance errors , .
14. Figure 5.14 Single integrator: formation translation. UGV speeds and heading ang...
15. Figure 5.15 Single integrator: formation translation. Drive‐wheel DC motor volta...
16. Figure 5.16 Single integrator: formation translation. Steering angle commands ,...
17. Figure 5.17 Single integrator: formation translation/rotation. UGV position traj...
18. Figure 5.18 Single integrator: formation translation/rotation. UGV distance erro...
19. Figure 5.19 Single integrator: formation translation/rotation. UGV bearing rate
20. Figure 5.20 Single integrator: formation translation/rotation. Velocity error ...
21. Figure 5.21 Single integrator: formation translation/rotation. Drive‐wheel DC mo...
22. Figure 5.22 Single integrator: formation translation/rotation. Steering angle co...
23. Figure 5.23 Single integrator: target interception. UGV position trajectories ,...
24. Figure 5.24 Single integrator: target interception. UGV distance errors , .
25. Figure 5.25 Single integrator: target interception. Target interception error .
26. Figure 5.26 Single integrator: target interception. Drive‐wheel DC motor voltage...
27. Figure 5.27 Single integrator: target interception. Steering angle commands ,
28. Figure 5.28 Single integrator: dynamic formation. UGV position trajectories ,
29. Figure 5.29 Single integrator: dynamic formation. UGV distance errors , .
30. Figure 5.30 Single integrator: dynamic formation. Drive‐wheel DC motor voltages
31. Figure 5.31 Single integrator: dynamic formation. Steering angle commands , .
32. Figure 5.32 Double integrator: formation acquisition. UGV position trajectories
33. Figure 5.33 Comparison of UGV position trajectories.
34. Figure 5.34 Double integrator: formation acquisition. UGV distance errors , .
35. Figure 5.35 Comparison of distance errors.
36. Figure 5.36 Double integrator: formation acquisition. Drive‐wheel DC motor volta...
37. Figure 5.37 Double integrator: formation acquisition. Steering angle commands ,...
38. Figure 5.38 Double integrator: formation maneuvering. UGV position trajectories
39. Figure 5.39 Comparison of UGV position trajectories.
40. Figure 5.40 Double integrator: formation maneuvering. UGV distance errors , .
41. Figure 5.41 Comparison of distance errors.
42. Figure 5.42 Double integrator: formation maneuvering. Velocity error of each U...
43. Figure 5.43 Double integrator: formation maneuvering. Drive‐wheel DC motor volta...
44. Figure 5.44 Double integrator: formation maneuvering. Steering angle commands ,...
45. Figure 5.45 Double integrator: target interception. UGV position trajectories ,...
46. Figure 5.46 Double integrator: target interception. UGV distance errors , .
47. Figure 5.47 Double integrator: target interception. Target interception error .
48. Figure 5.48 Double integrator: target interception. Velocity error of each UGV...
49. Figure 5.49 Double integrator: target interception. Drive‐wheel DC motor voltage...
50. Figure 5.50 Double integrator: target interception. Steering angle commands ,
51. Figure 5.51 Double integrator: dynamic formation. UGV position trajectories ,
52. Figure 5.52Figure 5.52 Comparison of UGV position trajectories.
53. Figure 5.53 Double integrator: dynamic formation. UGV distance errors , .
54. Figure 5.54Figure 5.54 Comparison of distance errors.
55. Figure 5.55 Double integrator: dynamic formation. Drive‐wheel DC motor voltages
56. Figure 5.56 Double integrator: dynamic formation. Steering angle commands , .
57. Figure 5.57 Holonomic dynamics: formation acquisition. UGV position trajectories...
58. Figure 5.58 Holonomic dynamics: formation acquisition. UGV distance errors , .
59. Figure 5.59 Comparison of distance errors.
60. Figure 5.60 Holonomic dynamics: formation acquisition. Parameter estimates for U...
61. Figure 5.61 Holonomic dynamics: formation acquisition. Velocity error of each ...
62. Figure 5.62 Holonomic dynamics: formation acquisition. Drive‐wheel DC motor volt...
63. Figure 5.63 Holonomic dynamics: formation acquisition. Steering angle commands

Copyright

This edition first published 2019

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 permission to reuse material from this title is available at http://www.wiley.com/go/permissions.

The right of Marcio de Queiroz, Xiaoyu Cai and Matthew Feemster to be identified as the authors of 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

MATLAB^® is a trademark of The MathWorks, Inc. and is used with permission. The MathWorks does not warrant the accuracy of the text or exercises in this book. This work's use or discussion of MATLAB^® software or related products does not constitute endorsement or sponsorship by The MathWorks of a particular pedagogical approach or particular use of the MATLAB^® software.

While the publisher and authors have used their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials or promotional statements for this work. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. 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

Names: Queiroz, Marcio S. de, author. | Cai, Xiaoyu, 1987‐ author. |

Feemster, Matthew, author.

Title: Formation control of multi‐agent systems : a graph rigidity approach /

Professor Marcio de Queiroz (Louisiana State University), Dr. Xiaoyu Cai

(Louisiana State University), Dr. Matthew Feemster (United States Naval

Academy).

Description: Hoboken, NJ : John Wiley & Sons, Inc., [2019] | Includes

bibliographical references and index. |

Identifiers: LCCN 2018040373 (print) | LCCN 2018050691 (ebook) | ISBN

9781118887479 (Adobe PDF) | ISBN 9781118887462 (ePub) | ISBN 9781118887448

(hardcover)

Subjects: LCSH: Multiagent systems. | Formation control (Machine theory) |

Graph theory. | Rigidity (Geometry) | Automatic control–Mathematical

models. | Robotics–Mathematical models.

Classification: LCC QA76.76.I58 (ebook) | LCC QA76.76.I58 Q84 2019 (print) |

DDC 006.3/0285436–dc23

LC record available at https://lccn.loc.gov/2018040373

Cover Design: Wiley

Cover Image: © Kypros/Getty Images, © aapsky/Shutterstock, © Andrei Trentea/Shutterstock

Preface

As the initial hurdles of unmanned robotic platform development have been passed, focus is now being placed on advancing the behavior of these platforms so they perform coordinated operations in groups with and without human supervision. Over the past several years, a considerable amount of work has been conducted in this area under various names: multi‐agent systems, networked systems, cooperative control, and swarming. Research has evolved from fundamental studies of biological swarms in nature to the development and application of systems theoretical tools for modeling such behaviors to, more recently, the synthesis and experimental validation of engineered multi‐agent systems.

The premise behind engineering multi‐agent systems is that cooperation among group members can lead to the execution of complex functions that are otherwise not possible. Engineering multi‐agent systems have the potential to impact a variety of military, civilian, and commercial applications that involve some of form situational awareness. Examples include patrolling, monitoring, surveying, scouting, and element tracking over large geographical areas with unmanned robotic vehicles or mobile sensor networks.

Decentralization is a key characteristic of biological and engineered multi‐agent systems since it provides adaptability and robustness to the system operation. Several coordination‐type problems have been studied within the robotics, systems, and control research communities that involve some level of distributed operation. Graph theory plays an important role in modeling the decentralization and interaction among the multiple agents needed to achieve the common goal. Our interest in this book is in the class of coordination problems known as formation control and in the use of rigid graph theory as a solution tool. Specifically, the goal of the book is to provide the first comprehensive and unified treatment of the subject of graph rigidity‐based formation control of multi‐agent systems. The presentation is mostly based on the authors' own work and perspectives.

The book begins with an introduction to rigid graph theory for readers not familiar with the subject. The heart of the book is divided into three parts according to the model of the agents' equations of motion: the single‐integrator model, the double‐integrator model, and the robotic vehicle model. For each model, three types of formation problems are studied: formation acquisition, formation maneuvering, and target interception. All formation control results in the book are supported by computer simulations, while most are demonstrated experimentally using unmanned ground vehicles. The book is organized such that the material is presented in ascending level of difficulty, building upon previous sections and chapters.

The book is intended for researchers and graduate students in the areas of robotics, systems, and control who are interested in the topic of multi‐agent systems. We assume readers have a graduate‐level knowledge of linear algebra, matrix theory, control systems, and nonlinear systems, especially Lyapunov stability theory.

We would like to acknowledge and express our gratitude to Pengpeng Zhang and Milad Khaledyan for their assistance with some of the theoretical results and computer simulations presented in the book, and to Dr. Bingqing Wu for her assistance with the creation of Figures 1.3 and 1.5. We would also like to thank Eric Willner and Jemima Kingsly at Wiley for giving us the opportunity to publish this work and for their patience while we completed it.

Finally, we acknowledge the following entities for allowing us to reproduce their pictures:

Weaver ants making an emergency bridge between two plants by Rose Thumboor (see Figure 1.1). Retrieved from commons.wikimedia.org/ wiki/File:Weaver_Ants_‐_Oecophylla_smaragdina.jpg. Used under Creative Commons Attribution‐Share Alike 4.0 International license (creative commons.org/licenses/by‐sa/4.0/deed.en).
School of convict surgeonfish (Acanthurus triostegus) by Thomas Shahan (see Figure 1.1). Retrieved from www.flickr.com/photos/49580580 @N02/14280168344/. Used under Creative Commons Attribution 2.0 Generic license (creativecommons.org/licenses/by/2.0/).
xBee module (see Figure 5.3). Retrieved from www.sparkfun.com/products/8665?. Used under Creative Commons Attribution 2.0 Generic license (creativecommons.org/licenses/by/2.0/).

March 2018

Baton Rouge, LA, USA

Marcio de Queiroz

Exton, PA, USA

Xiaoyu Cai

Annapolis, MD, USA

Matthew Feemster

Formation Control of Multi‐Agent Systems De Queiroz, Cai and Feemster February 2019 A Graph Rigidity Approach
Finite‐Time Stability	Amato, Tommasi and Pironti	August 2018
An Input‐Output Approach
Process Control System Fault Diagnosis	Gonzalez, Qi and Huang	September 2016
A Bayesian Approach
Variance‐Constrained Multi‐Objective	Ma, Wang and Bo	April 2015
Stochastic Control and Filtering
Sliding Mode Control of Uncertain	Wu, Shi and Su	July 2014
Parameter‐Switching Hybrid Systems
Algebraic Identification and Estimation	Sira‐Ramírez, García Rodríguez,	May 2014
Methods in Feedback Control Systems Cortes	Romero and Luviano Juárez

Formation Control of Multi-Agent Systems: A Graph Rigidity Approach

Copyright

Dedication

Preface

About the Companion Website