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: ALİ FUAT ALKAYA

Özet:

Stokastik engellerin olduğu yol planlaması, çok populer bir araştırma alanı olarak bilinir. Zorlayıcı bir stokastik optimizasyon problemi olan Kanadalı Gezgin Probleminde (CTP), bloke edilmiş yollar içeren bir haritada engele bitişik bir köşeye ulaşıldığında önceden tanımlanmış olasılıkla bu engel anlık olarak yok edilebilir. Stokastik engelli yol bulma probleminin (SOSP) gerçek çözümünde, sürekli bir ortamda büyük durum aralıkları gerektiren engeller bulunur. Bu nedenle, stokastik engel alanı probleminin ayrıklaştırılmış versiyonu (D-SOSP), olasılık bağımlılığı olan bir grup stokastik kenara sahip olduğu için CTP’nin en sık kullanılan çeşididir. Bu kenarların durumları belirsiz, geçilebilir veya değiştirilemez olarak atanır. Amaç, engeli yok etme maliyeti de dahil olmak üzere en kısa ayrık yolu garanti edecek bir seyahat planı tasarlamaktır. Engeli etkisizleştirme problemi (ONP), sınırlı ve önceden belirli ek maliyeti olan etkisizleştirme kabiliyetini barındırır. Bu çalışmada; ayrıklaştırılmış stokastik engel alanlarında problemin tam çözümü için, önbellek kullanan AO* (CAO*) ve engeli etkisizleştiren AO* (CAON*) algoritmaları kullanarak herhangi açı (ANYA) yol bulma metodunun faydalarını sunuyoruz. Standart CAO*, kabul edilebilir üst sınırları bulurken Dijkstra’nın en kısa yol metodu kulanır. Bununla birlikte; yakın zamanda önerilen ANYA algoritmasının, ayrıklaştırılmış grafik üzerindeki üst düzey kısa yol algoritmaları arasında en iyi performans gösterdiği görülmüştür. ANYA, dinamik olarak kurulan aralık kümelerini inceleyerek optimum uzunluktaki yolları arar. Gerçek hayattan bir örnek olan ABD donanma kuvvetlerine ait mayın tarlası veri haritası COBRA ve rastgele oluşturulmuş çeşitli yapay haritalar üzerinde metodolojimizi çalıştırarak elde ettiğimiz hesaplama sonuçları, belirsizliği giderme ve engeli imha etme -------------------- 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.