Region-Based Geospatial Abduction with Counter-IED Applications

Geospatial abduction problems (GAPsfor short) were introduced in Shakarian et al. (Gaps: Geospatial abduction problems. ACM Transactions on Intelligent Systems and Technology. (2011)). Given a set \(\mathcal{O}\) of observations, GAPstry to find a set of “partner” locations (points) that best explain those observations. For instance, the observations may refer to improvised-explosive device (IED) attacks (or burglaries) and the partner locations may refer to caches supporting those attacks (or the burglar’s house/office). A region-based GAP(or RGAP) tries to find a set of regions that best explain the observations. We study the complexity and mathematical properties of region-based GAPswhere we vary the shape of the region(s) we are seeking. We develop several exact and approximate algorithms for RGAPs, often with guarantees – we also explore practical implementation issues. We performed experiments where we attempted to use RGAPsto locate weapons caches in Baghdad based on IED attack locations. Our implementation was able to find regions that contained multiple weapons caches (on average 1. 7 cache sites) as well as a significantly higher density such caches (8 caches per square kilometer vs. the city-wide average of 0. 4). Further, the algorithm ran quickly, performing computation in just over 2 s on commodity desktop hardware.