{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:45:38Z","timestamp":1760060738432,"version":"build-2065373602"},"reference-count":39,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T00:00:00Z","timestamp":1758758400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-22-1-2572","#2319157"],"award-info":[{"award-number":["N00014-22-1-2572","#2319157"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF Award","award":["N00014-22-1-2572","#2319157"],"award-info":[{"award-number":["N00014-22-1-2572","#2319157"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>We investigate the Optimal Obstacle Placement (OOP) problem under uncertainty, framed as the dual of the Optimal Traversal Path problem in the Stochastic Obstacle Scene paradigm. We consider both continuous domains, discretized for analysis, and already discrete spatial grids that form weighted geospatial networks using 8-adjacency lattices. Our unified framework integrates OOP with stochastic geometry, modeling obstacle placement via Strauss (regular) and Mat\u00e9rn (clustered) processes, and evaluates traversal using the Reset Disambiguation algorithm. Through extensive Monte Carlo experiments, we show that traversal cost increases by up to 40% under strongly regular placements, while clustered configurations can decrease traversal costs by as much as 25% by leaving navigable corridors compared to uniform random layouts. In mixed (with both true and false obstacles) scenarios, increasing the proportion of true obstacles from 30% to 70% nearly doubles the traversal cost. These findings are further supported by statistical analysis and stochastic ordering, providing rigorous insights into how spatial patterns and obstacle compositions influence navigation under uncertainty.<\/jats:p>","DOI":"10.3390\/ijgi14100374","type":"journal-article","created":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T12:05:13Z","timestamp":1758801913000},"page":"374","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Adversarial Obstacle Placement with Spatial Point Processes for Optimal Path Disruption"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-0339-2325","authenticated-orcid":false,"given":"Li","family":"Zhou","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics, Auburn University, Auburn, AL 36849, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2423-3178","authenticated-orcid":false,"given":"Elvan","family":"Ceyhan","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, Auburn University, Auburn, AL 36849, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-3862-3214","authenticated-orcid":false,"given":"Polat","family":"Charyyev","sequence":"additional","affiliation":[{"name":"MAP Akademi, Istanbul 34840, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,9,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","article-title":"Shortest paths without a map","volume":"84","author":"Papadimitriou","year":"1991","journal-title":"Theor. Comput. Sci."},{"key":"ref_2","unstructured":"Bar-Noy, A., and Schieber, B. (1991, January 28\u201330). The Canadian traveller problem. Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA."},{"key":"ref_3","unstructured":"Diggle, P.J. (2003). Statistical Analysis of Spatial Point Patterns, Edward Arnold. [2nd ed.]."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"M\u00f8ller, J., and Waagepetersen, R.P. (2004). Statistical Inference and Simulation for Spatial Point Processes, Chapman & Hall\/CRC.","DOI":"10.1201\/9780203496930"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Illian, J., Penttinen, A., Stoyan, H., and Stoyan, D. (2008). Statistical Analysis and Modelling of Spatial Point Patterns, John Wiley & Sons.","DOI":"10.1002\/9780470725160"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"LaValle, S.M. (2006). Planning Algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9780511546877"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Howard, A., Mataric, M.J., and Sukhatme, G.S. (2002, January 25\u201327). Mobile sensor network deployment using potential fields: A distributed, scalable solution to the area coverage problem. Proceedings of the 6th International Symposium on Distributed Autonomous Robotic Systems (DARS), Berlin, Germany.","DOI":"10.1007\/978-4-431-65941-9_30"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Parajuli, G., Neupane, S., Kunwar, S., Adhikari, R., and Acharya, T. (2023). A GIS-Based Evacuation Route Planning in Flood-Susceptible Area of Siraha Municipality, Nepal. ISPRS Int. J. Geo-Inf., 12.","DOI":"10.3390\/ijgi12070286"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Lv, Z., Ni, L., Peng, H., Zhou, K., Zhao, D., Qu, G., Yuan, W., Gao, Y., and Zhang, Q. (2024). Research on Global Off-Road Path Planning Based on Improved A* Algorithm. ISPRS Int. J. Geo-Inf., 13.","DOI":"10.3390\/ijgi13100362"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1730","DOI":"10.1214\/12-AOAS556","article-title":"Optimal obstacle placement with disambiguations","volume":"6","author":"Aksakalli","year":"2012","journal-title":"Ann. Appl. Stat."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1002\/nav.20454","article-title":"The reset disambiguation policy for navigating stochastic obstacle fields","volume":"58","author":"Aksakalli","year":"2011","journal-title":"Nav. Res. Logist."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"An, Z., Rui, X., and Gao, C. (2024). Improved A* Navigation Path-Planning Algorithm Based on Hexagonal Grid. ISPRS Int. J. Geo-Inf., 13.","DOI":"10.3390\/ijgi13050166"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1010933404324","article-title":"Random Forests","volume":"1","author":"Breiman","year":"2001","journal-title":"Mach. Learn."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.18637\/jss.v027.i08","article-title":"Regression Models for Count Data in R","volume":"27","author":"Zeileis","year":"2008","journal-title":"J. Stat. Softw."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1002\/net.10039","article-title":"Shortest-path network interdiction","volume":"40","author":"Israeli","year":"2002","journal-title":"Networks"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1016\/j.ejor.2019.06.024","article-title":"A survey of network interdiction models and algorithms","volume":"283","author":"Smith","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1109\/TCNS.2021.3050128","article-title":"Credible interdiction for transmission systems","volume":"8","author":"Sundar","year":"2021","journal-title":"IEEE Trans. Control Netw. Syst."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1007\/s10479-023-05350-1","article-title":"Shortest path network interdiction with incomplete information: A robust optimization approach","volume":"335","author":"Azizi","year":"2024","journal-title":"Ann. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/s10479-024-06157-4","article-title":"A modified scenario bundling method for shortest path network interdiction under endogenous uncertainty","volume":"343","author":"Sadeghi","year":"2024","journal-title":"Ann. Oper. Res."},{"key":"ref_20","unstructured":"Nikolova, E., and Karger, D.R. (2008, January 13\u201317). Route planning under uncertainty: The Canadian traveller problem. Proceedings of the 23rd AAAI Conference on Artificial Intelligence, Chicago, IL, USA."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Eyerich, P., Keller, T., and Helmert, M. (2010, January 11\u201315). High-quality policies for the Canadian traveler\u2019s problem. Proceedings of the 24th AAAI Conference on Artificial Intelligence, Atlanta, GA, USA.","DOI":"10.1609\/aaai.v24i1.7542"},{"key":"ref_22","unstructured":"Missiuro, P., and Roy, N. (2006, January 15\u201319). Adapting Probabilistic Roadmaps to Handle Uncertain Maps. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Orlando, FL, USA."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s10514-013-9334-3","article-title":"Probabilistically Safe Motion Planning to Avoid Dynamic Obstacles with Uncertain Motion Patterns","volume":"35","author":"Aoude","year":"2013","journal-title":"Auton. Robot."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1109\/TASE.2022.3215562","article-title":"NR-RRT: Neural Risk-Aware Near-Optimal Path Planning in Uncertain Nonconvex Environments","volume":"21","author":"Meng","year":"2022","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1177\/0278364918781009","article-title":"Risk-aware graph search with dynamic edge cost discovery","volume":"38","author":"Chung","year":"2019","journal-title":"Int. J. Robot. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1117\/12.211346","article-title":"The Coastal Battlefield Reconnaissance and Analysis (COBRA) Program for Minefield Detection","volume":"2496","author":"Witherspoon","year":"1995","journal-title":"SPIE Detect. Technol. Mines Minelike Targets"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s10878-008-9156-y","article-title":"The Canadian traveller problem and its competitive analysis","volume":"18","author":"Xu","year":"2009","journal-title":"J. Comb. Optim."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_29","unstructured":"West, D. (2001). Introduction to Graph Theory, Prentice Hall. [2nd ed.]."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/j.compenvurbsys.2014.02.003","article-title":"Road network vulnerability analysis: Conceptualization, implementation and application","volume":"49","author":"Jenelius","year":"2015","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"2712","DOI":"10.1890\/07-1861.1","article-title":"Using circuit theory to model connectivity in ecology, evolution, and conservation","volume":"89","author":"McRae","year":"2008","journal-title":"Ecology"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"116417","DOI":"10.1016\/j.oceaneng.2023.116417","article-title":"Risk-based path planning for preventing collisions and groundings of maritime autonomous surface ships","volume":"290","author":"Maidana","year":"2023","journal-title":"Ocean Eng."},{"key":"ref_33","unstructured":"Aksakalli, V. (2007, January 12\u201314). The BAO* algorithm for stochastic shortest path problem with dynamic learning. Proceedings of the IEEE Conference on Decision and Control, New Orleans, LA, USA."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1109\/TSMCA.2007.902634","article-title":"Disambiguation protocols based on risk simulation","volume":"37","author":"Fishkind","year":"2007","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1287\/ijoc.2013.0571","article-title":"Penalty-based algorithms for stochastic obstacle scene problem","volume":"26","author":"Aksakalli","year":"2013","journal-title":"INFORMS J. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1002\/nav.20071","article-title":"Random disambiguation paths for traversing a mapped hazard field","volume":"52","author":"Priebe","year":"2005","journal-title":"Nav. Res. Logist."},{"key":"ref_37","unstructured":"Baddeley, A. (2010). Analysing Spatial Point Patterns in R, CSIRO. Workshop Notes Version 4.1."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Huber, P. (1981). Robust Statistics, John Wiley & Sons.","DOI":"10.1002\/0471725250"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Kuhn, M., and Johnson, K. (2013). Applied Predictive Modeling, Springer Inc.","DOI":"10.1007\/978-1-4614-6849-3"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/14\/10\/374\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:49:28Z","timestamp":1760035768000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/14\/10\/374"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,25]]},"references-count":39,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2025,10]]}},"alternative-id":["ijgi14100374"],"URL":"https:\/\/doi.org\/10.3390\/ijgi14100374","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2025,9,25]]}}}