The optimal obstacle placement with disambiguation problem
Belirsizliği giderme özellikli optimal engel yerleştirme problemi
- Tez No: 473060
- Danışmanlar: DOÇ. DR. ATİLLA YILMAZ, DOÇ. DR. ELVAN CEYHAN
- Tez Türü: Doktora
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 169
Özet
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.
Özet (Çeviri)
In the optimal obstacle placement with disambiguation (OPD) problem, we investigate how traversal length depends on the spatial pattern of the obstacles. In the OPD problem an obstacle placing agent (OPA) wishes to insert (disk shaped) obstacles of two types as true or false obstacles in an environment so as to maximize the traversal length of a navigating agent (NAVA). NAVA is equipped with a sensor that can only assign probabilities to each obstacle as being a true obstacle, but does not know the actual status of the obstacle until it reaches the boundary of the obstacle. When NAVA comes by the obstacle, it disambiguates the status of the obstacle with a cost added to the traversal length. When OPA equips the overall working window with false and/or true obstacles together where the whole obstacle pattern changing from uniformness to regularity and from uniformness to clustering, then on the average, the mean traversal length tends to increase (decrease) as the obstacle pattern changes from uniformness to regularity (clustering). Secondly, we introduce M2^k algorithm which is the modified version of RD algorithm and mainly based on the effective choice of a subset of possible disambiguations. We observed that the trends for mean traversal length estimated by M2^k algorithm is similar to RD algorithm except for reducing the complexity time and keeping relative error less than 2.5%. Moreover, we study the case when obstacles are distributed inside various obstacle window types such as linear strips, V-shaped, semicircular, and elliptical where we change the parameters such as location, orientation and curvature of these obstacle window forms. We also consider the case where the true obstacles are placed randomly proportional to the areas of Voronoi polygons or Delaunay triangles based on the allocation of the clutter points. On the average, the elliptical window type (a continuous version of V-shaped) reveals to be the best performing in maximizing the traversal length of NAVA and as for tessellations, the mean traversal length is essentially the same as the mean traversal length when obstacles are distributed uniformly. On the other hand, we provide extensions of the existing sub-optimal algorithms in the OPD problem, and introduce new ones for NAVA. The goal is to find an algorithm to minimize the expected traversal length of NAVA. We generalize the penalty-based functions used within the existing heuristic algorithms, and combine possibly related algorithms in a single family. We provide a guidance for choosing the algorithm from the defined family when the performance of NAVA's sensor varies from poor to almost perfect detection (of true obstacles). Our results are supported by extensive Monte Carlo simulations and theoretical results for some special types of graph structures are also provided.
Benzer Tezler
- Placement generation and hybrid planning for robotic rearrangement on cluttered surfaces
Dağınık yüzeylerde robotik düzenleme için yerleşim oluşturma ve hibrit planlama
ABDUL RAHMAN DABBOUR
Yüksek Lisans
İngilizce
2019
Mekatronik MühendisliğiSabancı ÜniversitesiDOÇ. DR. VOLKAN PATOĞLU
DOÇ. DR. ESRA ERDEM
- Kablosuz algılayıcı düğüm dağıtımında evrimsel algoritma tabanlı optimizasyon
Evolutionary algorithm-based optimization of wireless sensor node deployment
SİBEL BİRTANE AKAR
Doktora
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. HAYRİYE KORKMAZ
PROF. DR. ÖZGÜR KORAY ŞAHİNGÖZ
- Extremum seeking method and its applications in automotive control
Ekstremum arama metodu ve otomotiv kontrolu alanında uygulamaları
ERKİN DİNÇMEN
Doktora
İngilizce
2011
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. BİLİN AKSUN GÜVENÇ
DOÇ. DR. TANKUT ACARMAN
- Tekerlekli bir askeri taşıt için otomatik yangın söndürme ve infilak bastırma sistemi tasarımı
Automatic fire suppression and extinguishing system design for a wheeled military vehicle
FATİH AKGÜN
Yüksek Lisans
Türkçe
2017
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
PROF. DR. CEMAL BAYKARA
- Development of various corner-lit backlighting concepts in an advanced smart led tv
İleri akıllı led televizyonlarında köşeden aydınlatmalı farklı arka-ışıklandırma konseptlerinin geliştirilmesi
KIVANÇ KARSLI
Yüksek Lisans
İngilizce
2015
Elektrik ve Elektronik MühendisliğiÖzyeğin ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. MEHMET ARIK