{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:19:20Z","timestamp":1760242760125,"version":"build-2065373602"},"reference-count":21,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2016,6,27]],"date-time":"2016-06-27T00:00:00Z","timestamp":1466985600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100014036","name":"MURI","doi-asserted-by":"publisher","award":["W911NF-11-1-0332"],"award-info":[{"award-number":["W911NF-11-1-0332"]}],"id":[{"id":"10.13039\/100014036","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Games"],"abstract":"<jats:p>Game theoretic approaches have recently been used to model the deterrence effect of patrol officers\u2019 assignments on opportunistic crimes in urban areas. One major challenge in this domain is modeling the behavior of opportunistic criminals. Compared to strategic attackers (such as terrorists) who execute a well-laid out plan, opportunistic criminals are less strategic in planning attacks and more flexible in executing well-laid plans based on their knowledge of patrol officers\u2019 assignments. In this paper, we aim to design an optimal police patrolling strategy against opportunistic criminals in urban areas. Our approach is comprised by two major parts: learning a model of the opportunistic criminal (and how he or she responds to patrols) and then planning optimal patrols against this learned model. The planning part, by using information about how criminals responds to patrols, takes into account the strategic game interaction between the police and criminals. In more detail, first, we propose two categories of models for modeling opportunistic crimes. The first category of models learns the relationship between defender strategy and crime distribution as a Markov chain. The second category of models represents the interaction of criminals and patrol officers as a Dynamic Bayesian Network (DBN) with the number of criminals as the unobserved hidden states. To this end, we: (i) apply standard algorithms, such as Expectation Maximization (EM), to learn the parameters of the DBN; (ii) modify the DBN representation that allows for a compact representation of the model, resulting in better learning accuracy and the increased speed of learning of the EM algorithm when used for the modified DBN. These modifications exploit the structure of the problem and use independence assumptions to factorize the large joint probability distributions. Next, we propose an iterative learning and planning mechanism that periodically updates the adversary model. We demonstrate the efficiency of our learning algorithms by applying them to a real dataset of criminal activity obtained from the police department of the University of Southern California (USC) situated in Los Angeles, CA, USA. We project a significant reduction in crime rate using our planning strategy as compared to the actual strategy deployed by the police department. We also demonstrate the improvement in crime prevention in simulation when we use our iterative planning and learning mechanism when compared to just learning once and planning. Finally, we introduce a web-based software for recommending patrol strategies, which is currently deployed at USC. In the near future, our learning and planning algorithm is planned to be integrated with this software. This work was done in collaboration with the police department of USC.<\/jats:p>","DOI":"10.3390\/g7030015","type":"journal-article","created":{"date-parts":[[2016,6,27]],"date-time":"2016-06-27T12:56:01Z","timestamp":1467032161000},"page":"15","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Keeping Pace with Criminals: An Extended Study of Designing Patrol Allocation against Adaptive Opportunistic Criminals"],"prefix":"10.3390","volume":"7","author":[{"given":"Chao","family":"Zhang","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Southern California, Los Angeles, CA 90089, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shahrzad","family":"Gholami","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Southern California, Los Angeles, CA 90089, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Debarun","family":"Kar","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Southern California, Los Angeles, CA 90089, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arunesh","family":"Sinha","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Southern California, Los Angeles, CA 90089, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manish","family":"Jain","sequence":"additional","affiliation":[{"name":"Armorway. Inc., Los Angeles, CA 90291, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ripple","family":"Goyal","sequence":"additional","affiliation":[{"name":"Armorway. Inc., Los Angeles, CA 90291, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Milind","family":"Tambe","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Southern California, Los Angeles, CA 90089, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2016,6,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1249","DOI":"10.1142\/S0218202508003029","article-title":"A statistical model of criminal behavior","volume":"18","author":"Short","year":"2008","journal-title":"Math. Models Methods Appl. Sci."},{"key":"ref_2","unstructured":"Zhang, C., Jiang, A.X., Short, M.B., Brantingham, P.J., and Tambe, M. (2014). Decision and Game Theory for Security, Springer."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1287\/inte.1100.0505","article-title":"Software assistants for randomized patrol planning for the lax airport police and the federal air marshal service","volume":"40","author":"Jain","year":"2010","journal-title":"Interfaces"},{"key":"ref_4","first-page":"13","article-title":"PROTECT: A deployed game theoretic system to protect the ports of the United States","volume":"Volume 1","author":"Shieh","year":"2012","journal-title":"Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1109\/MC.2004.1297301","article-title":"Crime data mining: A general framework and some examples","volume":"37","author":"Chen","year":"2004","journal-title":"Computer"},{"key":"ref_6","unstructured":"Boyen, X., and Koller, D. (1998, January 24\u201326). Tractable inference for complex stochastic processes. Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, Madison, WI, USA."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Nath, S.V. (2006, January 18\u201322). Crime pattern detection using data mining. Proceedings of the 2006 IEEE\/WIC\/ACM International Conference on Web Intelligence and Intelligent Agent Technology Workshops, WI-IAT 2006 Workshops, Hong Kong, China.","DOI":"10.1109\/WI-IATW.2006.55"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"De Bruin, J.S., Cocx, T.K., Kosters, W.A., Laros, J.F., and Kok, J.N. (2006, January 18\u201322). Data mining approaches to criminal career analysis. Sixth International Conference on Data Mining, ICDM\u201906, Hong Kong, China.","DOI":"10.1109\/ICDM.2006.47"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s10506-006-9023-z","article-title":"Decision support systems for police: Lessons from the application of data mining techniques to soft forensic evidence","volume":"14","author":"Oatley","year":"2006","journal-title":"Artif. Intell. Law"},{"key":"ref_10","first-page":"2272","article-title":"Probabilistic pursuit-evasion games: A one-step nash approach","volume":"Volume 3","author":"Hespanha","year":"2000","journal-title":"Proceedings of the 39th IEEE Conference on Decision and Control"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Tambe, M. (2011). Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned, Cambridge University Press.","DOI":"10.1017\/CBO9780511973031"},{"key":"ref_12","unstructured":"Jiang, A.X., Yin, Z., Zhang, C., Tambe, M., and Kraus, S. (2013, January 6\u201310). Game-theoretic randomization for security patrolling with dynamic execution uncertainty. Proceedings of the 2013 International Conference on Autonomous Agents and Multi-Agent Systems, Saint Paul, MN, USA."},{"key":"ref_13","unstructured":"Yang, R., Ford, B., Tambe, M., and Lemieux, A. (2014, January 5\u20139). Adaptive resource allocation for wildlife protection against illegal poachers. Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems, Paris, France."},{"key":"ref_14","first-page":"57","article-title":"Leader-follower strategies for robotic patrolling in environments with arbitrary topologies","volume":"Volume 1","author":"Basilico","year":"2009","journal-title":"Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1109\/WI-IAT.2009.211","article-title":"Extending algorithms for mobile robot patrolling in the presence of adversaries to more realistic settings","volume":"Volume 2","author":"Basilico","year":"2009","journal-title":"Proceedings of the 2009 IEEE\/WIC\/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Blum, A., Haghtalab, N., and Procaccia, A.D. (2014, January 8\u201313). Learning optimal commitment to overcome insecurity. Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS), Montreal, QC, Canada.","DOI":"10.1609\/aaai.v28i1.8799"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1863","DOI":"10.1109\/TVCG.2014.2346926","article-title":"Proactive spatiotemporal resource allocation and predictive visual analytics for community policing and law enforcement","volume":"20","author":"Malik","year":"2014","journal-title":"Vis. Comput. Graph."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","article-title":"Maximum likelihood from incomplete data via the EM algorithm","volume":"39","author":"Dempster","year":"1977","journal-title":"J. R. Stat. Soc. Ser. B (Methodol.)"},{"key":"ref_19","unstructured":"Bishop, C.M. (2006). Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag New York, Inc."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0020-0190(87)90114-1","article-title":"Occam\u2019s Razor","volume":"24","author":"Blumer","year":"1987","journal-title":"Inf. Process. Lett."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1109\/18.825794","article-title":"The generalized distributive law","volume":"46","author":"Aji","year":"2000","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Games"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-4336\/7\/3\/15\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:24:54Z","timestamp":1760210694000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-4336\/7\/3\/15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,27]]},"references-count":21,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2016,9]]}},"alternative-id":["g7030015"],"URL":"https:\/\/doi.org\/10.3390\/g7030015","relation":{},"ISSN":["2073-4336"],"issn-type":[{"type":"electronic","value":"2073-4336"}],"subject":[],"published":{"date-parts":[[2016,6,27]]}}}