Any angle path finding in stochastic obstacle scenes

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Türkiye

Tezin Onay Tarihi: 2019

Tezin Dili: İngilizce

Öğrenci: Ufuk Aslan

Danışman: Ali Fuat Alkaya

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Path planning with stochastic obstacles is a well-known research 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 on the fly when the agent reaches to an adjacent vertex. Stochastic obstacle scene problem (SOSP) has obstacles in continuous environment which requires huge state spaces for the exact solution. Thus, discretized version of stochastic obstacle scene problem (D-SOSP) is most commonly used variant of CTP which has group of stochastic edges with probability dependency. States of these edges are assigned as ambiguous, traversable, or untraversable. The objective is to design a travel plan that would guarantee the shortest path including the obstacle disambiguation cost. Obstacle neutralization problem (ONP) is defined as obstacle neutralization capability, which is limited and predefined, of an agent on optimal path with an additional cost. In this work, we present Any-angle (ANYA) path finding in discretized stochastic obstacle scenes using the exact algorithms AO* with caching (CAO*) and AO* with caching and neutralization (CAON*). 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 those shortest path algorithms at the highest level of development on grid-based graphs. It looks for optimum length paths by investigating the interval sets which are established dynamically. Our methodology is clearly demonstrated through computational experiments using a data map called COBRA, a real example of US naval forces, and the use of several synthetically produced minefields.