EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Navigation algorithms for optimal pathfinding in the stochastic obstacle scene problem

Elvan Ceyhan, Polat Charyyev, Li Zhou

RAIRO - Operations Research · 2026-07 · 60 (4) · 2189-2226

DOI: 10.1051/ro/2026063 ↗

Kurz gefasst

Fachartikel in der Zeitschrift RAIRO - Operations Research, online erschienen am 28.07.2026. Verfasst von Elvan Ceyhan und 2 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Office of Naval Research, National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Office of Naval Research
  • National Science Foundation

Zitieren

APA

Ceyhan, E., Charyyev, P., & Zhou, L. (2026). Navigation algorithms for optimal pathfinding in the stochastic obstacle scene problem. RAIRO - Operations Research, 60(4), 2189-2226. https://doi.org/10.1051/ro/2026063

Vancouver

Ceyhan E, Charyyev P, Zhou L. Navigation algorithms for optimal pathfinding in the stochastic obstacle scene problem. RAIRO - Operations Research. 2026;60(4):2189-2226. doi:10.1051/ro/2026063

BibTeX
@article{Ceyhan2026,
  author = {Ceyhan, Elvan and Charyyev, Polat and Zhou, Li},
  title = {Navigation algorithms for optimal pathfinding in the stochastic obstacle scene problem},
  journal = {RAIRO - Operations Research},
  year = {2026},
  volume = {60},
  number = {4},
  pages = {2189--2226},
  doi = {10.1051/ro/2026063}
}
Kostenlos starten →