{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:48Z","timestamp":1750307208612,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,2,1]],"date-time":"2012-02-01T00:00:00Z","timestamp":1328054400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF0910206W911NF0910525"],"award-info":[{"award-number":["W911NF0910206W911NF0910525"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA95500610405"],"award-info":[{"award-number":["FA95500610405"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2012,2]]},"abstract":"<jats:p>\n            Geospatial Abduction Problems (GAPs) involve the inference of a set of locations that \u201cbest explain\u201d 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 \u201cagent\u201d and an \u201cadversary\u201d) use a probabilistic model of their opponent (i.e., a mixed strategy). There is asymmetry as the adversary can\n            <jats:italic>choose<\/jats:italic>\n            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\n            <jats:italic>reward functions<\/jats:italic>\n            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\n            <jats:italic>Optimal Adversary Strategy<\/jats:italic>\n            (OAS) problem and the\n            <jats:italic>Maximal Counter-Adversary strategy<\/jats:italic>\n            (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.\n          <\/jats:p>","DOI":"10.1145\/2089094.2089110","type":"journal-article","created":{"date-parts":[[2012,10,12]],"date-time":"2012-10-12T20:56:02Z","timestamp":1350075362000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Adversarial Geospatial Abduction Problems"],"prefix":"10.1145","volume":"3","author":[{"given":"Paulo","family":"Shakarian","sequence":"first","affiliation":[{"name":"United States Military Academy"}]},{"given":"John P.","family":"Dickerson","sequence":"additional","affiliation":[{"name":"University of Maryland"}]},{"given":"V. S.","family":"Subrahmanian","sequence":"additional","affiliation":[{"name":"University of Maryland"}]}],"member":"320","published-online":{"date-parts":[[2012,2]]},"reference":[{"volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation (ICRA\u201908)","author":"Agmon N.","key":"e_1_2_2_1_1","unstructured":"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\u201908) . 2339--2345. 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\u201908). 2339--2345."},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI\u201909). 1811","author":"Agmon N.","year":"1817","unstructured":"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\u201909). 1811 -- 1817 . 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\u201909). 1811--1817."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800090303"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/123953.123965"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00961655"},{"volume-title":"Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201910)","author":"Dickerson J.","key":"e_1_2_2_6_1","unstructured":"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\u201910) . 299--306. 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\u201910). 299--306."},{"volume-title":"Advances in Artificial Intelligence: In Proceedings of the Brazilian Symposium on Artificial Intelligence (SBIA). 106--118","author":"do Lago Pereira S.","key":"e_1_2_2_7_1","unstructured":"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 . 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."},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Dyer M. Goldberg L. A. Greenhill C. and Jerrum M. 2000. On the relative complexity of approximate counting problems. Tech. rep. Coventry UK. Dyer M. Goldberg L. A. Greenhill C. and Jerrum M. 2000. On the relative complexity of approximate counting problems. Tech. rep. Coventry UK.","DOI":"10.1007\/3-540-44436-X_12"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.40"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793304601"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90018-9"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB).","author":"Kakas A. C.","key":"e_1_2_2_13_1","unstructured":"Kakas , A. C. and Mancarella , P . 1990. Database updates through abduction . In Proceedings of the International Conference on Very Large Databases (VLDB). Kakas, A. C. and Mancarella, P. 1990. Database updates through abduction. In Proceedings of the International Conference on Very Large Databases (VLDB)."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Leyton-Brown K. and Shoham Y. 2008. Essentials of Game Theory: A Concise Multidisciplinary Introduction. Morgan and Claypool Publishers. Leyton-Brown K. and Shoham Y. 2008. Essentials of Game Theory: A Concise Multidisciplinary Introduction . Morgan and Claypool Publishers.","DOI":"10.1007\/978-3-031-01545-8"},{"key":"e_1_2_2_16_1","unstructured":"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. 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."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1160633.1160681"},{"volume-title":"Philosophical Writings of Peirce, Selected and Edited with an Introduction by Justus Buchler","author":"Peirce C. S.","key":"e_1_2_2_20_1","unstructured":"Peirce , C. S. 1955. Philosophical Writings of Peirce, Selected and Edited with an Introduction by Justus Buchler . Dover Publications , New York . Peirce, C. S. 1955. Philosophical Writings of Peirce, Selected and Edited with an Introduction by Justus Buchler. Dover Publications, New York."},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Peng Y. and Reggia J. A. 1990. Abductive Inference Models for Diagnostic Problem-Solving. Springer New York. Peng Y. and Reggia J. A. 1990. Abductive Inference Models for Diagnostic Problem-Solving . Springer New York.","DOI":"10.1007\/978-1-4419-8682-5"},{"volume-title":"Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201909)","author":"Pita J.","key":"e_1_2_2_22_1","unstructured":"Pita , J. , Jain , M. , Ord\u00f3\u00f1ez , 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\u201909) . 369--376. Pita, J., Jain, M., Ord\u00f3\u00f1ez, 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\u201909). 369--376."},{"key":"e_1_2_2_23_1","unstructured":"Rossmo D. K. and Rombouts S. 2008. Geographic profiling. In Enviromental Criminology and Crime Analysis R. Wortley and L. Mazerolle Eds. 136--149. Rossmo D. K. and Rombouts S. 2008. Geographic profiling. In Enviromental Criminology and Crime Analysis R. Wortley and L. Mazerolle Eds. 136--149."},{"volume-title":"Proceedings of the 3rd International Conference on Computational Cultural Dynamics. AAAI.","author":"Shakarian P.","key":"e_1_2_2_24_1","unstructured":"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. 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."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2036264.2036271"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.2307\/1235442"},{"key":"e_1_2_2_27_1","unstructured":"U.S. Army. 1994. Intelligence Preparation of the Battlefiled (US Army Field Manual) (FM 34-130 Ed). U.S. Army . 1994. Intelligence Preparation of the Battlefiled (US Army Field Manual) (FM 34-130 Ed)."},{"key":"e_1_2_2_28_1","volume-title":"Proceedings of the 5th National Conference on Artificial Intelligence (AAAI\u201986)","author":"Peng Y. J. R.","year":"1986","unstructured":"Peng , Y. J. R. 1986 . Plausibility of diagnostic hypotheses . In Proceedings of the 5th National Conference on Artificial Intelligence (AAAI\u201986) . 140--145. Peng, Y. J. R. 1986. Plausibility of diagnostic hypotheses. In Proceedings of the 5th National Conference on Artificial Intelligence (AAAI\u201986). 140--145."}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2089094.2089110","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2089094.2089110","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:30Z","timestamp":1750241190000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2089094.2089110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["10.1145\/2089094.2089110"],"URL":"https:\/\/doi.org\/10.1145\/2089094.2089110","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"type":"print","value":"2157-6904"},{"type":"electronic","value":"2157-6912"}],"subject":[],"published":{"date-parts":[[2012,2]]},"assertion":[{"value":"2011-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}