The optimal obstacle placement with disambiguation problem

Belirsizliği giderme özellikli optimal engel yerleştirme (OPD) probleminde, yol uzunluğunun uzaysal desen türlerine göre nasıl etkilendiğini araştırıyoruz. OPD probleminde, navigasyon aracının (NAVA) gideceği yolu mümkün olduğunca uzun tutmak için yüzeye engel yerleştirme aracı (OPA) tarafından gerçek veya sahte en- geller yerleştirilmektedir. NAVA her diskin gerçek engel olma ihtimalini belirleyen sensör ile donatılmış olup, disklerin gerçek veya sahte olduğunu diskin sınırlarına gelene kadar bilmemektedir. Fakat NAVA diskin sınırlarında iken belirli bir maliyetin toplam süreye/uzunluğa eklenmesi karşılığında disklerin gerçek veya sahte olduğunu öğrenebilmektedir. İlk olarak, OPA'nın çalışma bölgesine sahte ve/veya gerçek en- gelleri tüm engel desenin tekdüzelikten düzenliliğe ve tekdüzelikten kümelenmeye göre yerleştirilmesi sonucunda toplam geçiş uzunluğunun engel desenin tekdüzelikten düzenliliğe göre artmakta ve tekdüzelikten kümelenmeye göre ise azalmaktadır. İkinci olarak, RD algoritmasının değiştirilmiş versiyonu olan ve temel olarak disk başına düşen belirsizlik nokta sayısının akıllıca seçilmesine bağlı olan M2k algoritmasını tanıtmaktayız. M2k algoritması tarafından hesaplanan yol uzunluğunun RD algoritması tarafından hesaplanan yol uzunluğu ile benzer eğilimler gösterdiğini gözlemledik ve dahası hesaplama süresi azaltılmış olup, toplam geçiş uzunluğu en fazla %2.5 sapmaktadır. Buna ek olarak, engellerin lineer, V-şeklinde, yarı çembersel, ve eliptik gibi değişik şekil içinde dağılımları engel şekillerin lokasyon, oryantasyon, ve kurvatür gibi parametrelerine göre incelenmiştir. Ayrıca, sahte engellerin yerleşimine bağlı olarak Voronoi çokgen veya Delaunay üçgen alanlarına orantılı olacak şekilde gerçek engellerin yerleştirilme durumu ele alınmıştır. Ortalama olarak, NAVA'nın toplam geçiş uzunluğunu maksimuma çıkarmak için engel şekillerin arasından eliptik engel şekli (V-şeklinin sürekli versiyonu) en optimal değeri vermektedir ve Dirichlet mozaiği gibi düzenlemeler için ise geçiş uzunluğu engellerin tekdüze dağılımındakine yakın değeri vermektedir. Diğer taraftan, OPD problemindeki NAVA için mevcut optimal olmayan algoritmaları genişletmekteyiz ve yenilerini ortaya koymaktayız. Buradaki asıl amaç, NAVA'nın beklenen geçiş uzunluğunu minimuma indiren algoritma geliştirmektir. Mevcut sezgisel algoritmalarda kullanılan ağırlığa dayalı fonksiyonları genelleştiriyoruz, ve benzer algoritmaları tek çatı altında birleştiriyoruz. NAVA'nın sensör algılama (gerçek engel olma ihtimali) performans gücünün en zayıftan mükemmel dereceye kadar durumlarda birleştirilen algoritma kümesinden en optimal olanı seçmeyi gösteriyoruz. Bizim sonuçlarımız kapsamlı Monte Carlo simülasyonları ile desteklenmekle beraber, bazı özel graf biçimleri için teorik sonuçlar göstermekteyiz.