Geospatial Abduction Paulo Shakarian • V.S. Subrahmanian Geospatial Abduction Principles and Practice Foreword by Charles P. Otstott Paulo Shakarian V.S. Subrahmanian Kings Valley Drive University of Maryland - College Park 20721 Bowie Maryland Potomac Maryland USA USA [email protected] [email protected] ISBN 978-1-4614-1793-4 e-ISBN 978-1-4614-1794-1 DOI 10.1007/978-1-4614-1794-1 Springer New York Dordrecht Heidelberg London Library of Congress Control Number: 2011938690 © Springer Science+Business Media, LLC 2012 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com) Toourwives,JanaandMary Foreword Increasingly,USforces,multinationalcoalitiontroops,andUNpeacekeepingforces worldwide are coming under asymmetric attacks including Improvised Explosive Device (IED) attacks. These attacks are carried out by adversaries who are out- matched in conventional military capabilities by opposing forces. However, such adversariestakeadvantageoftheirdeepknowledgeofthelocalterrain,ethno-social makeupoftheareasinwhichtheyoperate,andknowledgeoflocalhistoryandcul- ture,tolaunchsuccessfulIEDattacks. This book is the first in the field of geospatial abduction—a mathematical and computationaltechniqueinventedbytheauthorstosolveavarietyofproblemsin- cludinglocatingweaponscachesthatsupportIEDattacks,identifyinghabitatsthat support hosts of disease-carrying viruses, identifying illegal drug labs and/or drug distribution centers, and solving problems related to locations of burglars and/or serialkillers.Anyonewithaninterestinperforminggeospatialinferencesandana- lyticsinvolvingtheseandotherapplicationswhereoneneedstoidentifylocations basedonafewobservedclues,wouldfindthisbookinvaluable. CollegePark,MD,August2011 CharlesP.Otstott LieutenantGeneralUSArmy(Ret.) vii Preface There are numerous applications in which we make observations about events in time and space, and where we wish to infer one or more other locations that are causally related to the observations we made. Such applications span a number of fields and include finding habitats of hosts of disease carrying viruses (epidemiol- ogy),identifyinglocationswhereelusiveanimalssuchastigersandleopardsmight live (wildlife conservation), identifying locations of illegal drug labs and distribu- tion centers (criminology), and identifying the locations of weapons caches that facilitateimprovisedexplosivedevice(IED)attacksonsoldiersorcivilians. Thisbookdescribesthetechniqueofgeospatialabductioninwhichwecanuse knowledgeaboutthelocationsofobservations,aswellascertainapplicationspecific properties, to make the types of inferences needed to enable applications such as thoselistedabove. Thebookisintendedasaresearchmonographonthisemergingnewfield.The book provides a detailed technical definition of many forms of geospatial abduc- tion, as well as many different theoretical results, as well as exact algorithms and approximationalgorithmsandheuristicstosolvegeospatialabductionproblems.In order to facilitate readability, a number of examples are used throughout the book to illustrate basic concepts and algorithms. Moreover, we discuss in detail, a spe- cificapplicationtofindingweaponscachesthatterroristgroupsusetolaunchIED attacks. The intended audience includes faculty and graduate students in not only com- puter science, but any field (e.g., geography, epidemiology, wildlife conservation, criminology)whereweneedtomakeintelligentinferencesfromobservationaldata, together with application-specific information. Military planners and analysts, as wellaslawenforcementofficialswillalsofindpartsofthebooktobeofinterest. The authors are indebted to many people who either were involved in some of ourresearchorwhofacilitatedtheworkinoneofmanyways. First, both authors would like to thank their wives—Jana Shakarian and Mary Andrews—fortheirconstantloveandsupport. Second,theauthorswouldliketothankJohnDickersonforservingasaco-author ofChapter4. ix