Adversarial Obstacle Placement with Spatial Point Processes for Optimal Path Disruption
Preprint
Abstract
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érn (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.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- A modified scenario bundling method for shortest path network interdiction under endogenous uncertaintyAnnals of Operations Research, 2024
- Shortest path network interdiction with incomplete information: a robust optimization approachAnnals of Operations Research, 2023
- Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patternsAutonomous Robots, 2013
- Applied Predictive Modeling2013
- The reset disambiguation policy for navigating stochastic obstacle fieldsNaval Research Logistics (NRL), 2011
- The canadian traveller problem and its competitive analysisJournal of Combinatorial Optimization, 2008
- Statistical Analysis and Modelling of Spatial Point Patterns2007
- Random disambiguation paths for traversing a mapped hazard fieldNaval Research Logistics (NRL), 2005
- Shortest paths without a mapTheoretical Computer Science, 1991
- A note on two problems in connexion with graphsNumerische Mathematik, 1959