GAPs: Geospatial abduction problems

Paulo Shakarian, V. S. Subrahmanian, Maria Luisa Sapino

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


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).

Original languageEnglish (US)
Article number7
JournalACM Transactions on Intelligent Systems and Technology
Issue number1
StatePublished - Oct 2011
Externally publishedYes


  • Abduction
  • Complexity analysis
  • Heuristic algorithms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Artificial Intelligence


Dive into the research topics of 'GAPs: Geospatial abduction problems'. Together they form a unique fingerprint.

Cite this