Studies in Computational Intelligence 729 Yaniv Altshuler Alex Pentland Alfred M. Bruckstein Swarms and Network Intelligence in Search Studies in Computational Intelligence Volume 729 Series editor Janusz Kacprzyk, Polish Academy of Sciences, Warsaw, Poland e-mail: [email protected] About this Series The series “Studies in Computational Intelligence” (SCI) publishes new develop- mentsandadvancesinthevariousareasofcomputationalintelligence—quicklyand with a high quality. The intent is to cover the theory, applications, and design methods of computational intelligence, as embedded in the fields of engineering, computer science, physics and life sciences, as well as the methodologies behind them. The series contains monographs, lecture notes and edited volumes in computational intelligence spanning the areas of neural networks, connectionist systems, genetic algorithms, evolutionary computation, artificial intelligence, cellular automata, self-organizing systems, soft computing, fuzzy systems, and hybrid intelligent systems. Of particular value to both the contributors and the readership are the short publication timeframe and the worldwide distribution, which enable both wide and rapid dissemination of research output. More information about this series at http://www.springer.com/series/7092 Yaniv Altshuler Alex Pentland (cid:129) Alfred M. Bruckstein Swarms and Network Intelligence in Search 123 YanivAltshuler Alfred M.Bruckstein MITMedia Lab Computer Science Department Massachusetts Institute of Technology Israeli Institute of Technology (Technion) Cambridge, MA Haifa USA Israel AlexPentland MITMedia Lab Massachusetts Institute of Technology Cambridge, MA USA ISSN 1860-949X ISSN 1860-9503 (electronic) Studies in Computational Intelligence ISBN978-3-319-63602-3 ISBN978-3-319-63604-7 (eBook) DOI 10.1007/978-3-319-63604-7 LibraryofCongressControlNumber:2017947832 ©SpringerInternationalPublishingAG2018 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpart of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission orinformationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodologynowknownorhereafterdeveloped. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfrom therelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authorsortheeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinor for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictionalclaimsinpublishedmapsandinstitutionalaffiliations. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringerInternationalPublishingAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface Lastdecadehasseenaparadigmaticchangeintheoperationalprocessesofmodern armies’ aerial forces, as designers and commanders have been gradually shifting their focus towards unmanned aerial vehicles (UAVs). Indeed, over 50% of the planesintheUSAtodayareunmanned,withthistrendexpectedtofurtherincrease, andbeadoptedbyadditionalWesternarmiesinthecomingyears.Thishasbeenthe case in visual intelligent (VISINT), and recently also in tactical signal intelligence (SIGINT), which is traditionally in charge of 80% of the information gathered by the intelligence corps. Therefore, as the use of Drones as an integral component on ongoing intelli- gencegatheringinwartime,aswellasduringthe“battlewithinthewars”increases, sogrowstheimportanceoftheneedtobasethisuseonanefficientinfrastructure.In otherwords,aninnovativesmall-scalededicatedUAVsquadron(namely,aDrones Swarm), designed for special missions, may function perfectly with high redun- dancy and inefficient use of its resources, but a regular large-scale information gathering that is based on unmanned vehicles operating in swarms cannot. Furthermore, the lack of an efficient infrastructure that assumes control of the low-levelresourceutilizationtasksmeansthatthesetasksmustultimatelybetaken careofbythehumanoperators(asisbeingdonetoday)—dramaticallyreducingthe numberoftasksthesecanengage,increasingthetimeittakesthemtodoso,aswell astheoverallcostofthisprocess,andultimatelysignificantlylimitingthevehicles’ operational potential. As the complexity of the problem increases, so does the impact of optimizing capabilities on the overall resources required in order to guarantee a pre-defined level of performance. In other words, a successful use of large-scale swarms of UAVs as a combat and intelligence gathering tool necessitates the development of an efficient mechanism for optimization of their utilization, specifically in the design and maintenance of their patrolling routes. Thisbookoffersacomprehensiveanalysisofthetheoryandtoolsneededforthe developmentofanefficientandrobustinfrastructureforthedesignofcollaborative patrollingUAVswarms,focusingonitsapplicationsfortacticintelligenceDrones. The systems under discussion enable flocks of semi-autonomous vehicles to v vi Preface perform an ongoing dynamic efficient patrolling and scanning of pre-defined “searchregion”,inarobustandnear-optimalway,inasfasttimeaspossible,while guaranteeing detection of all targets that are located in that region. Theoretical limitations of such systems are discussed, as well as the trade-offs between the various economic and operational parameters of the system. Cambridge, USA Yaniv Altshuler Cambridge, USA Alex Pentland Haifa, Israel Alfred M. Bruckstein Contents Introduction to Swarm Search..... .... .... .... .... .... ..... .... 1 1 Overview .. .... .... .... ..... .... .... .... .... .... ..... .... 1 2 Swarm Intelligence... .... ..... .... .... .... .... .... ..... .... 2 3 Building Intelligent Swarms Using Stupid Drones .... .... ..... .... 5 4 Organization .... .... .... ..... .... .... .... .... .... ..... .... 6 5 Conclusion . .... .... .... ..... .... .... .... .... .... ..... .... 8 References .... .... .... .... ..... .... .... .... .... .... ..... .... 8 Cooperative “Swarm Cleaning” of Stationary Domains. .... ..... .... 15 1 Introduction. .... .... .... ..... .... .... .... .... .... ..... .... 15 2 The Cooperative Cleaners Problem.... .... .... .... .... ..... .... 16 3 Related Work ... .... .... ..... .... .... .... .... .... ..... .... 17 4 The Cleaning Protocol .... ..... .... .... .... .... .... ..... .... 18 4.1 Cleaning Protocol — Definitions and Requirements .. ..... .... 19 4.2 The SWEEP Cleaning Protocol.. .... .... .... .... ..... .... 20 4.3 Pivot Point. .... .... ..... .... .... .... .... .... ..... .... 21 4.4 Signaling .. .... .... ..... .... .... .... .... .... ..... .... 22 4.5 Connectivity Preservation... .... .... .... .... .... ..... .... 24 4.6 Agents Synchronization.... .... .... .... .... .... ..... .... 24 4.7 Clustering Problem .. ..... .... .... .... .... .... ..... .... 27 4.8 Mission Termination . ..... .... .... .... .... .... ..... .... 28 5 Analysis ... .... .... .... ..... .... .... .... .... .... ..... .... 28 5.1 Definitions. .... .... ..... .... .... .... .... .... ..... .... 29 5.2 Correctness .... .... ..... .... .... .... .... .... ..... .... 30 5.3 Detailed Analysis.... ..... .... .... .... .... .... ..... .... 31 5.4 Robustness. .... .... ..... .... .... .... .... .... ..... .... 38 5.5 Comparison to Existing Work ... .... .... .... .... ..... .... 39 6 Regions with Obstacles.... ..... .... .... .... .... .... ..... .... 41 7 Experimental Results.. .... ..... .... .... .... .... .... ..... .... 42 8 Conclusion . .... .... .... ..... .... .... .... .... .... ..... .... 46 References .... .... .... .... ..... .... .... .... .... .... ..... .... 47 vii viii Contents Swarm Search of Expanding Regions in Grids: Lower Bounds ... .... 51 1 Introduction. .... .... .... ..... .... .... .... .... .... ..... .... 51 2 The Dynamic “Cooperative Cleaners” Problem... .... .... ..... .... 52 3 A Protocol-Agnostic Lower Bound for the Cleaning Time.. ..... .... 58 4 Impossibility Result .. .... ..... .... .... .... .... .... ..... .... 67 5 The Cleaning Protocol .... ..... .... .... .... .... .... ..... .... 68 6 Experimental Results.. .... ..... .... .... .... .... .... ..... .... 69 7 Isoperimetric Inequality on the Grid... .... .... .... .... ..... .... 69 8 Discussion and Conclusion. ..... .... .... .... .... .... ..... .... 77 Appendix – Definitions... .... ..... .... .... .... .... .... ..... .... 78 References .... .... .... .... ..... .... .... .... .... .... ..... .... 87 Swarm Search of Expanding Regions in Grids: Upper Bounds ... .... 91 1 Introduction. .... .... .... ..... .... .... .... .... .... ..... .... 91 2 The Dynamic “Cooperative Cleaners” Problem... .... .... ..... .... 92 3 The Cleaning Protocol .... ..... .... .... .... .... .... ..... .... 98 4 Recursive Upper Bound ... ..... .... .... .... .... .... ..... .... 99 5 Direct Upper Bounds . .... ..... .... .... .... .... .... ..... .... 110 6 Simplifying Theorem 2.... ..... .... .... .... .... .... ..... .... 112 7 An Upper Bound for k .... ..... .... .... .... .... .... ..... .... 114 8 Discussion and Conclusion. ..... .... .... .... .... .... ..... .... 116 Appendix – Definitions... .... ..... .... .... .... .... .... ..... .... 117 References .... .... .... .... ..... .... .... .... .... .... ..... .... 126 The Search Complexity of Collaborative Swarms in Expanding Z2 Grid Regions ... .... .... ..... .... .... .... .... .... ..... .... 129 1 Introduction. .... .... .... ..... .... .... .... .... .... ..... .... 129 2 Related Work ... .... .... ..... .... .... .... .... .... ..... .... 131 3 The Dynamic Cooperative Cleaners Problem .... .... .... ..... .... 133 4 Grid Coverage — Analysis. ..... .... .... .... .... .... ..... .... 140 5 Dynamic Cleaners as Cooperative Hunters.. .... .... .... ..... .... 147 6 Conclusions. .... .... .... ..... .... .... .... .... .... ..... .... 148 References .... .... .... .... ..... .... .... .... .... .... ..... .... 149 Collaborative Patrolling Swarms in Stochastically Expanding Environments . .... .... .... ..... .... .... .... .... .... ..... .... 155 1 Introduction. .... .... .... ..... .... .... .... .... .... ..... .... 155 2 Related Work ... .... .... ..... .... .... .... .... .... ..... .... 156 3 Definitions.. .... .... .... ..... .... .... .... .... .... ..... .... 157 4 Lower Bound ... .... .... ..... .... .... .... .... .... ..... .... 160 4.1 Direct Bound... .... ..... .... .... .... .... .... ..... .... 160 4.2 Using the Bound .... ..... .... .... .... .... .... ..... .... 167 4.3 Parameters Selection . ..... .... .... .... .... .... ..... .... 170 5 Lower Bound - Markovian Model .... .... .... .... .... ..... .... 173 6 Impossibility Results.. .... ..... .... .... .... .... .... ..... .... 178 Contents ix 6.1 Direct Result ... .... ..... .... .... .... .... .... ..... .... 178 6.2 Markovian Model ... ..... .... .... .... .... .... ..... .... 179 7 Experimental Results.. .... ..... .... .... .... .... .... ..... .... 181 8 Conclusions. .... .... .... ..... .... .... .... .... .... ..... .... 183 References .... .... .... .... ..... .... .... .... .... .... ..... .... 183 The Cooperative Hunters – Efficient and Scalable Drones Swarm for Multiple Targets Detection..... .... .... .... .... .... ..... .... 187 1 Introduction. .... .... .... ..... .... .... .... .... .... ..... .... 187 2 Related Work ... .... .... ..... .... .... .... .... .... ..... .... 188 3 The Cooperative Hunters Problem .... .... .... .... .... ..... .... 190 3.1 The Targets .... .... ..... .... .... .... .... .... ..... .... 190 3.2 UAVs and Sensors... ..... .... .... .... .... .... ..... .... 190 3.3 The Search Region... ..... .... .... .... .... .... ..... .... 191 3.4 The Goal .. .... .... ..... .... .... .... .... .... ..... .... 191 4 Previous Results . .... .... ..... .... .... .... .... .... ..... .... 191 5 Improved Geometrical Flying Patterns . .... .... .... .... ..... .... 192 5.1 Description of the Algorithm.... .... .... .... .... ..... .... 193 5.2 Analysis of the Algorithm .. .... .... .... .... .... ..... .... 194 5.3 Lower Bound on the Number of UAVs — Optimality Proof. .... 196 6 Conclusion . .... .... .... ..... .... .... .... .... .... ..... .... 201 References .... .... .... .... ..... .... .... .... .... .... ..... .... 201 Optimal Dynamic Coverage Infrastructure for Large-Scale Fleets of Reconnaissance UAVs .... ..... .... .... .... .... .... ..... .... 207 1 Introduction. .... .... .... ..... .... .... .... .... .... ..... .... 207 2 Related Work ... .... .... ..... .... .... .... .... .... ..... .... 208 3 Patrolling System Optimizing — Problem Definitions . .... ..... .... 210 4 The Optimal Number of Monitoring Units .. .... .... .... ..... .... 211 5 Which Drones to Use? Optimizing the Drones’ Cost .. .... ..... .... 214 6 Case Study I – Theoretical Analysis... .... .... .... .... ..... .... 215 7 Case Study II – Real World Transportation Network Monitoring.. .... 218 7.1 Betweenness Centrality Versus Traffic Flow .... .... ..... .... 219 7.2 Origin-Destination Based Betweenness Centrality.... ..... .... 221 7.3 Improving Betweenness Centrality Using Travel Properties.. .... 221 7.4 Optimizing the Locations of Surveillance and Monitoring Stations ... .... .... ..... .... .... .... .... .... ..... .... 223 7.5 Modeling Various Deployment Schemes as a Gompertz Function.... .... .... .... .... .... ..... .... 226 8 Transportation Network Dataset .. .... .... .... .... .... ..... .... 228 8.1 Network Structure ... ..... .... .... .... .... .... ..... .... 230 8.2 Congestions.... .... ..... .... .... .... .... .... ..... .... 230 8.3 Flow . .... .... .... ..... .... .... .... .... .... ..... .... 232 9 Conclusions. .... .... .... ..... .... .... .... .... .... ..... .... 233 References .... .... .... .... ..... .... .... .... .... .... ..... .... 234