Navigation algorithms for optimal pathfinding in the stochastic obstacle scene problem

¹ Department of Mathematics and Statistics, Auburn University, Auburn, AL 36849, USA
² MAP Akademi, Levent Çarşı, Beşiktaş, Istanbul, Turkey

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 18 July 2024
Accepted: 27 May 2026

Abstract

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 evaluate 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.