Any angle path finding in stochastic obstacle scenes
Olasılıksal engeli olan alanlarda herhangi açıyöntemi ile yol bulma
- Tez No: 582557
- Danışmanlar: DOÇ. DR. ALİ FUAT ALKAYA
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: İngilizce
- Üniversite: Marmara Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 61
Ö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 problemlerinin çözümünde belirgin bir iyileştirmeyi ortaya koymuştur.
Özet (Çeviri)
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.
Benzer Tezler
- Kapalı alan navigasyon sistemleri ve kullanımına yönelik örnek bir uygulama
A model application for indoor navigation systems and their usage
MUSTAFA TUFAN ALTUNOK
Yüksek Lisans
Türkçe
2022
Mekatronik MühendisliğiTokat Gaziosmanpaşa ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ EBUBEKİR YAŞAR
- An effective path planning algorithm for swarm of robots in an un-known environment
Bilinmeyen ortamlarda robot sürüleri için algoritma planlamada etkin bir yol
MOHAMMED ISAM ISMAEL ABDI
Yüksek Lisans
İngilizce
2020
Mekatronik MühendisliğiAtılım ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
Assoc. Prof. Dr. MUHAMMAD UMER KHAN
- Dinamik ortamlar için yeni bir gerçek zamanlı evrimsel seyrüsefer planlama ve güdümleme sistemi
A new real time evolutionary navigation planning and guidance system for dynamic environments
FERHAT UÇAN
Doktora
Türkçe
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. DENİZ TURGAY ALTILAR
- Makine öğrenmesi ve görüntü işleme tekniklerini kullanarak drone ile yaprak sınıflandırma
Leaf classification with drone by using machine learning and image processing techniques
MEHMET ÖZTÜRK
Yüksek Lisans
Türkçe
2018
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ NAZIM KEMAL ÜRE
- Automated route search for pipeline design
Boru hattı tasarımında otomatik geçki arama
MOHAMMED SAHRAN KHORSHEED KHORSHEED
Yüksek Lisans
İngilizce
2018
Jeodezi ve FotogrametriYıldız Teknik ÜniversitesiHarita Mühendisliği Ana Bilim Dalı
DOÇ. DR. NURSU TUNALIOĞLU