Navigation algorithms for optimal pathfinding in stochastic obstacle scene problem

In the stochastic obstacle scene (SOS) problem (a continuous counterpart of the Canadian traveler's problem), a navigating agent seeks a low-cost route from a source to a target in the presence of obstacles whose true/false status is initially uncertain. We study the discretized SOS setting and develop a family of penalty-based navigation heuristics that incorporate both sensor-derived obstacle probabilities and a disambiguation cost incurred upon querying an obstacle at its boundary. Our main methodological contribution is a parametric unification of classical penalty rules via the ACS(k) family, together with norm-based approximations that relate ACS(k) to existing penalties. We valuate the resulting heuristics through extensive Monte Carlo experiments across sensor-accuracy regimes, disambiguation costs, and obstacle densities, and we summarize which penalty-growth behaviors are preferable under each regime. The results provide practical guidance for selecting a penalty-based navigation rule for a given sensor and operational cost configuration.