Distributed Control of Robotic Networks.pdf-资料库

habby_soso-9708199-16359647490449412033.pdf-第1页.png

第1页 / 共323页

habby_soso-9708199-16359647490449412033.pdf-第2页.png

第2页 / 共323页

habby_soso-9708199-16359647490449412033.pdf-第3页.png

第3页 / 共323页

habby_soso-9708199-16359647490449412033.pdf-第4页.png

第4页 / 共323页

habby_soso-9708199-16359647490449412033.pdf-第5页.png

第5页 / 共323页

habby_soso-9708199-16359647490449412033.pdf-第6页.png

第6页 / 共323页

habby_soso-9708199-16359647490449412033.pdf-第7页.png

第7页 / 共323页

habby_soso-9708199-16359647490449412033.pdf-第8页.png

第8页 / 共323页

share March 22, 2009 Distributed Control of Robotic Networks A Mathematical Approach to Motion Coordination Algorithms Francesco Bullo Jorge Cort´es Sonia Mart´ınez

share March 22, 2009 Copyright c 2006-2009 by F. Bullo, J. Cort´es, and S. Mart´ınez This document is a complete free online version of the following book. Distributed Control of Robotic Networks, by Francesco Bullo, Jorge Cort´es and Sonia Mart´ınez, Applied Mathematics Series, Princeton University Press, 2009, ISBN 978-0-691-14195-4. The book is available online at http://coordinationbook.info (i) You are allowed to freely download, share, print, or photocopy this document. (ii) You are not allowed to modify, sell, or claim authorship of any part of this document. (iii) We thank you for any feedback information, including suggestions, evaluations, error descriptions, or comments about teaching or re- search uses.

share March 22, 2009 To Lily, to Sonia, and to Olimpia and Leonardo

share March 22, 2009 Contents Preface Chapter 1. An introduction to distributed algorithms 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 Elementary concepts and notation Matrix theory Dynamical systems and stability theory Graph theory Distributed algorithms on synchronous networks Linear distributed algorithms Notes Proofs Exercises Chapter 2. Geometric models and optimization 2.1 2.2 2.3 2.4 2.5 2.6 Basic geometric notions Proximity graphs Geometric optimization problems and multicenter functions Notes Proofs Exercises Chapter 3. Robotic network models and complexity notions 3.1 3.2 3.3 3.4 3.5 3.6 3.7 A model for synchronous robotic networks Robotic networks with relative sensing Coordination tasks and complexity notions Complexity of direction agreement and equidistance Notes Proofs Exercises Chapter 4. Connectivity maintenance and rendezvous 4.1 4.2 Problem statement Connectivity maintenance algorithms vi 1 1 6 12 20 37 52 66 68 84 93 93 102 109 122 123 131 136 136 148 155 162 163 165 172 175 176 178

DCRN March 22, 2009 4.3 4.4 4.5 4.6 4.7 Rendezvous algorithms Simulation results Notes Proofs Exercises Chapter 5. Deployment 5.1 5.2 5.3 5.4 5.5 5.6 Problem statement Deployment algorithms Simulation results Notes Proofs Exercises Chapter 6. Boundary estimation and tracking 6.1 6.2 6.3 6.4 6.5 6.6 6.7 Event-driven asynchronous robotic networks Problem statement Estimate update and cyclic balancing law Simulation results Notes Proofs Exercises Bibliography Algorithm Index Subject Index Symbol Index 187 196 197 199 211 214 215 217 228 232 233 240 242 243 247 251 261 263 265 270 273 299 300 306 v “Distributed Control of Robotic Networks” by F. Bullo, J. Cort´es and S. Mart´ınez Copyright c 2006-2009. Manuscript under contract. This version: March 22, 2009

share March 22, 2009 Preface OBJECTIVES Recent years have witnessed a thriving research activity on cooperative con- trol and motion coordination. This interest is motivated by the growing possibilities enabled by robotic networks in the monitoring of natural phe- nomena and the enhancement of human capabilities in hazardous and un- known environments. Our ﬁrst objective in this book is to present a coherent introduction to basic distributed algorithms for robotic networks. This emerging discipline sits at the intersection of diﬀerent areas such as distributed algorithms, par- allel processing, control, and estimation. Our second objective is to provide a self-contained, broad exposition of the notions and tools from these areas that are relevant in cooperative control problems. These concepts include graph-theoretic notions (connectivity, adjacency, and Laplacian matrices), distributed algorithms from computer science (leader election, basic tree computations) and from parallel processing (averaging algorithms, conver- gence rates), and geometric models and optimization (Voronoi partitions, proximity graphs). Our third objective is to put forth a model for robotic networks that helps to rigorously formalize coordination algorithms running on them. We illustrate how computational geometry plays an important role in modeling the interconnection topology of robotic networks. We draw on classical notions from distributed algorithms to provide complexity measures that characterize the execution of coordination algorithms. Such measures allow us to quantify the algorithm performance and implementation costs. Our fourth and last objective is to present various algorithms for coordina- tion tasks such as connectivity maintenance, rendezvous, and deployment. We especially emphasize the analysis of the correctness and of the complex- ity of the proposed algorithms. The technical treatment combines control- theoretic tools such as Lyapunov functions and invariance principles with techniques from computer science and parallel processing, such as induction and message counting.

DCRN March 22, 2009 THE INTENDED AUDIENCE The intended audience for this book consists of ﬁrst- and second-year grad- uate students in control and robotics from Computer Science, Electrical Engineering, Mechanical Engineering, and Aerospace Engineering. A famil- iarity with basic concepts from analysis, linear algebra, dynamical systems, and control theory is assumed. The writing style is mathematical: we have aimed at being precise in the introduction of the notions, the statement of the results, and the formal description of the algorithms. This mathematical style is complemented by numerous examples, exercises, intuitive explana- tions and motivating discussions for the introduction of novel concepts. Researchers in the ﬁelds of control theory and robotics who are not aware of the literature on distributed algorithms will also beneﬁt from the book. The book uses notions with a clear computer-science ﬂavor such as syn- chronous networks, complexity measures, basic tree computations, and lin- ear distributed iterations, and integrates them into the study of robotic networks. Likewise, researchers in the ﬁelds of distributed algorithms and automata theory who are not aware of robotic networks and distributed con- trol will also ﬁnd the book useful. The numerous connections that can be drawn between the classical study of distributed algorithms and the present book provide a friendly roadmap with which to step into the ﬁeld of con- trolled coordination of robotic networks. AN OUTLINE OF THE BOOK Chapter 1 presents a broad introduction to distributed algorithms on syn- chronous networks. We start by presenting basic matrix notions and a primer on graph theory that gives special emphasis to linear algebraic as- pects such as adjacency and Laplacian matrices. After this, we introduce the notion of synchronous networks, and we present time, communication, and space complexity notions. We examine these notions in basic algorithms such as broadcast, tree computation, and leader election. The chapter ends with a thorough treatment of linear iterations and averaging algorithms. Chapter 2 presents basic geometric notions that are relevant in motion co- ordination. Robotic networks have a spatial component which is not always present in synchronous networks as studied in computer science. Geometric objects such as polytopes, Voronoi partitions, and geometric centers play an important role in modeling the interaction of robotic networks with the physical environment. Proximity graphs allow us to rigorously formalize the interconnection topology of a network of robotic agents, and characterize the spatially distributed character of coordination algorithms. This notion is a natural translation of the notion of distributed algorithms treated in the previous chapter. The chapter concludes with a detailed discussion on concepts from geometric optimization and multicenter functions. vii “Distributed Control of Robotic Networks” by F. Bullo, J. Cort´es and S. Mart´ınez Copyright c 2006-2009. Manuscript under contract. This version: March 22, 2009

DCRN March 22, 2009 Chapter 3 introduces a model for a group of robots that synchronously communicate/sense locally, process information, and move. We describe the physical components of the robotic network and we introduce a formal notion of a motion coordination algorithm as a control and communication law. Generalizing the notions introduced in Chapter 1, we introduce the notions of task and of time, communication, and space complexity. We illustrate these concepts by means of a simple and insightful example of a group of robots moving on a circle. Chapter 4 analyzes in detail two coordination tasks: connectivity main- tenance and rendezvous. The objective of “connectivity maintenance” is to establish local rules that allow agents to move without losing the connec- tivity of the overall networks. The objective of “rendezvous” is to establish local rules that allow agents to agree on a common spatial location. We present coordination algorithms that achieve these tasks, making use of the geometric concepts introduced in the previous chapters. Furthermore, we provide results on the correctness and complexity of these algorithms. Chapter 5 considers deployment problems. The objective of “deployment” is to establish local rules that allow agents to achieve optimal network conﬁg- urations in an environment of interest. Here, optimality is deﬁned using the multicenter functions from geometric optimization introduced in Chapter 2. We present coordination algorithms that achieve these tasks, characterizing their correctness and complexity. Chapter 6 has a dual purpose. First, we introduce an event-driven control and communication law, in which computation and communication actions are triggered by asynchronous events, rather than taking place on a periodic schedule. Second, we consider a boundary tracking problem, and propose an “estimation and balancing” algorithm that allows a robotic network to monitor a moving boundary eﬃciently. The reader will note that, as the discussion progresses, the selection of topics emphasizes problems in which we have been directly involved. There are exciting topics that have been considered in the literature and are not presented here in depth, albeit we brieﬂy discuss a number of them through- out the exposition. In this, our ﬁrst eﬀort, we decided to tackle the problems that we knew better, postponing the rest for the future. We hope the reader will appreciate the result and share, while reading it, some of the fun we had in writing it. HOW TO USE THIS BOOK AS A TEXT Our experience and opinion is that this text can be used for a quarter- or semester-long course on “Distributed Control” or on “Robotic Networks.” Such a course could be taught in an Engineering or a Computer Science department. We taught such a course at our respective institutions over a viii “Distributed Control of Robotic Networks” by F. Bullo, J. Cort´es and S. Mart´ınez Copyright c 2006-2009. Manuscript under contract. This version: March 22, 2009

资料库

Distributed Control of Robotic Networks.pdf

相关推荐

课程资源

热门标签

最新资料