Any Angle Path Finding in Stochastic Obstacle Scenes

Path planning with stochastic obstacles is well known researching area. The Canadian traveler problem (CTP) is a challenging stochastic optimization problem of traversing in a given graph having blocked edges and the disambiguation status of these edges can be settled with predefined probabilities. Discretized version of stochastic obstacle scene problem (D-SOSP) is most commonly used variant of CTP. The objective is to design a travel plan that would guarantee the shortest path including the obstacle disambiguation cost. In this work, we present Any-Angle (ANYA) path finding in discretized stochastic obstacle scenes using the exact algorithm AO* with caching (CAO*). The admissible upper bounds in the CAO* are found by making use of Dijkstra's shortest path. However, ANYA algorithm, being recently proposed, is already shown to outperform shortest path algorithms by investigating the interval sets. Our methodology is exhibited distinctly via computational examples involving a data map of navy forces minefield.