GAPs: Geospatial Abduction Problems

There are many applications where we observe various phenomena in space (e.g., locations of victims of a serial killer), and where we want to infer “partner” locations (e.g., the location where the killer lives) that are geospatially related to the observed phenomena. In this article, we define geospatial abduction problems (GAPs for short). We analyze the complexity of GAPs, develop exact and approximate algorithms (often with approximation guarantees) for these problems together with analyses of these algorithms, and develop a prototype implementation of our GAP framework. We demonstrate accuracy of our algorithms on a real world data set consisting of insurgent IED (improvised explosive device) attacks against U.S. forces in Iraq (the observations were the locations of the attacks, while the “partner” locations we were trying to infer were the locations of IED weapons caches).