Adversarial Geospatial Abduction Problems

Abstract

Geospatial Abduction Problems (GAPs) involve the inference of a set of locations that “best explain” a given set of locations of observations. For example, the observations might include locations where a serial killer committed murders or where insurgents carried out Improvised Explosive Device (IED) attacks. In both these cases, we would like to infer a set of locations that explain the observations, for example, the set of locations where the serial killer lives/works, and the set of locations where insurgents locate weapons caches. However, unlike all past work on abduction, there is a strong adversarial component to this; an adversary actively attempts to prevent us from discovering such locations. We formalize such abduction problems as a two-player game where both players (an “agent” and an “adversary”) use a probabilistic model of their opponent (i.e., a mixed strategy). There is asymmetry as the adversary can choose both the locations of the observations and the locations of the explanation, while the agent (i.e., us) tries to discover these. In this article, we study the problem from the point of view of both players. We define reward functions axiomatically to capture the similarity between two sets of explanations (one corresponding to the locations chosen by the adversary, one guessed by the agent). Many different reward functions can satisfy our axioms. We then formalize the Optimal Adversary Strategy (OAS) problem and the Maximal Counter-Adversary strategy (MCA) and show that both are NP-hard, that their associated counting complexity problems are #P-hard, and that MCA has no fully polynomial approximation scheme unless P=NP. We show that approximation guarantees are possible for MCA when the reward function satisfies two simple properties (zero-starting and monotonicity) which many natural reward functions satisfy. We develop a mixed integer linear programming algorithm to solve OAS and two algorithms to (approximately) compute MCA; the algorithms yield different approximation guarantees and one algorithm assumes a monotonic reward function. Our experiments use real data about IED attacks over a 21-month period in Baghdad. We are able to show that both the MCA algorithms work well in practice; while MCA-GREEDY-MONO is both highly accurate and slightly faster than MCA-LS, MCA-LS (to our surprise) always completely and correctly maximized the expected benefit to the agent while running in an acceptable time period.

References

1. Agmon, N., Kraus, S., and Kaminka, G. 2008. Multi-robot perimeter patrol in adversarial settings. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’08). 2339--2345.
2. Agmon, N., Kraus, S., Kaminka, G., and Sadov, V. 2009. Adversarial uncertainty in multi-robot patrol. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI’09). 1811--1817.
3. Charnes, A. and Cooper, W. 1962. Programming with linear fractional functionals. Naval Res. Logistics Quart. 9, 3, 163--297.
4. Console, L., Portinale, L., and Dupré, D. T. 1991. Focusing abductive diagnosis. AI Comm. 4, 2--3, 88--97.
5. Console, L., Sapino, M. L., and Dupré, D. T. 1995. The role of abduction in database view updating. J. Intell. Info. Syst. 4, 3, 261--280.
6. Dickerson, J., Simari, G., Subrahmanian, V., and Kraus, S. 2010. A graph-theoretic approach to protect static and moving targets from adversaries. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’10). 299--306.
7. do Lago Pereira, S. and de Barros, L. N. 2004. Planning with abduction: A logical framework to explore extensions to classical planning. Advances in Artificial Intelligence: In Proceedings of the Brazilian Symposium on Artificial Intelligence (SBIA). 106--118.
8. Dyer, M., Goldberg, L. A., Greenhill, C., and Jerrum, M. 2000. On the relative complexity of approximate counting problems. Tech. rep., Coventry, UK.
9. Feige, U. 1998. A threshold of ln n for approximating set cover. J. ACM 45, 4, 634--652.
10. Feige, U., Mirrokni, V. S., and Vondrak, J. 2007. Maximizing non-monotone submodular functions. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). IEEE Computer Society. 461--471.
11. Hunt III, H. B., Marathe, M. V., Radhakrishnan, V., and Stearns, R. E. 1998. The complexity of planar counting problems. SIAM J. Comput. 27, 4, 1142--1167.
12. Johnson, D. 1982. The NP-completeness column: An ongoing guide. J. Algorithms 3, 2, 182--195.
13. Kakas, A. C. and Mancarella, P. 1990. Database updates through abduction. In Proceedings of the International Conference on Very Large Databases (VLDB).
14. Karmarkar, N. 1984. A new polynomial-time algorithm for linear programming. Combinatorica 4, 4, 373--395.
15. Leyton-Brown, K. and Shoham, Y. 2008. Essentials of Game Theory: A Concise, Multidisciplinary Introduction. Morgan and Claypool Publishers.
16. Masuyama, S. T. and Ibaraki, T. H. 1981. The computational complexity of the m-center problems on the plane. Trans. IECE Japan E84, 57--64.
17. Nemhauser, G., Wolsey, L., and Fisher, M. 1978. An analysis of the approximations for maximizing submodular set functions. Math. Program. 14, 265--294.
18. Pagnucco, M. 1996. The role of abductive reasoning within the process of belief revision. Ph.D. thesis, Basser Department of Computer Science, University of Sydney, Australia.
19. Paruchuri, P., Tambe, M., Ordóñez, F., and Kraus, S. 2006. Security in multiagent systems by policy randomization. In Proceedings of the 5th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’06).
20. Peirce, C. S. 1955. Philosophical Writings of Peirce, Selected and Edited with an Introduction by Justus Buchler. Dover Publications, New York.
21. Peng, Y. and Reggia, J. A. 1990. Abductive Inference Models for Diagnostic Problem-Solving. Springer, New York.
22. Pita, J., Jain, M., Ordóñez, F., Tambe, M., Kraus, S., and Magori-Cohen, R. 2009. Effective solutions for real-world stackelberg games: When agents must deal with human uncertainties. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’09). 369--376.
23. Rossmo, D. K. and Rombouts, S. 2008. Geographic profiling. In Enviromental Criminology and Crime Analysis, R. Wortley and L. Mazerolle Eds., 136--149.
24. Shakarian, P., Subrahmanian, V., and Sapino, M. L. 2009. SCARE: A case study with Baghdad. In Proceedings of the 3rd International Conference on Computational Cultural Dynamics. AAAI.
25. Shakarian, P., Subrahmanian, V., and Sapino, M. L. 2010. GAPs: Geospatial Abduction Problems. ACM Trans. Intell. Syst. Technol. http://www.di.unito.it/~mlsapino/Conferma-I-fascia/TIST.pdf.
26. Stollsteimer, J. F. 1963. A working model for plant numbers and locations. J. Farm Econ. 45, 3, 631--645.
27. U.S. Army. 1994. Intelligence Preparation of the Battlefiled (US Army Field Manual) (FM 34-130 Ed).
28. Peng, Y. J. R. 1986. Plausibility of diagnostic hypotheses. In Proceedings of the 5th National Conference on Artificial Intelligence (AAAI’86). 140--145.

Index Terms

• Applied computing

  • Computers in other domains

    • Cartography

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

      • Nonmonotonic, default reasoning and belief revision

    • Search methodologies

      • Heuristic function construction