A graph theoretic approach on team localization problem
Ekip konumlama problemi üzerine çizge kuramsal bir yaklaşım
- Tez No: 957354
- Danışmanlar: PROF. DR. MUSTAFA DOĞAN
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Makine Mühendisliği, Electrical and Electronics Engineering, Mechanical Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Makine Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Makine Dinamiği, Titreşimi ve Akustiği Bilim Dalı
- Sayfa Sayısı: 95
Özet
Son yıllarda çok etmenli robotik teknolojilerin açık kaynak toplulukları tarafından yaygınlaştırılması ile beraber bu robotların yer tayinleri önemli bir problem olarak karşımıza çıkmaktadır. Özellikle son on yıla kadar konumlama problemi küresel uydu navigasyon sistemleri temelli çözümlere dayanmakta iken bu durum 1990'lı yılların sonuna doğru kablosuz sensör ağları konulu çalışmalarının çoğalması ile değişmiştir. O yıllardan bugüne kadar işbirlikçi konumlama teknikleri üzerine birçok çalışma yapılmış ve bunları konu alan literatür araştırma raporları hazırlanmıştır. Fakat bu raporlardan çok azı konumlama probleminin altında yatan temel prensipleri ele almıştır. Bu da birçok araştırmacının aynı prensipler üzerine kurduğu yöntemlere farklı isimler vererek bir karmaşa yaratmasına neden olmuştur. Bu çalışmanın temel amacı bir görev timini oluşturan robotik unsurların yerlerinin tayin edilmesi amacıyla uygun bir yöntem araştırmak ve bunu konumlamanın temel prensiplerini de gözeterek gerçekleştirmektir. Tezin ikinci bölümünde konumlama amacıyla kullanılan açı, mesafe ve sinyal gücüne dayalı ölçme tekniklerine geçmeden önce gerekli olabilecek birtakım kavramlar ve temel sınıflandırmalardan bahsedilmiştir. Navigasyon kelimesinin kökeni Latince'de gemi anlamına gelen“navis”ve sürmek, seyir ettirmek anlamına gelen“agere”kelimelerinden gelmektedir. Bir cismi bir yerden başka bir yere götürebilmek için öncelikle o cismin konumunu bilmek gerekir. Konumu bilinmeyen cisimlerin yeri, konumları bilinen bir yere göre ölçüm alınarak tayin edilebilir. Otonom ekip konseptinde elde edilen konum bilgilerinin anlamlandırılabilmesi ve kullanılabilmesi için konumlandırmanın temel prensipleri iyi anlaşılmalıdır. Konum bir vektör ile ifade edilir. Konum vektörü ise bir koordinat referans sistemi üzerinde tanımlandığında bir anlam ifade etmektedir. Klasik kartezyen koordinat sisteminde genel olarak X,Y yatay, Z ise düşey ekseni ifade etmektedir. Yatay eksenlerde konum bilgisinin yanına o konuma ilişkin zaman bilgisin de eklenmesi ile elde edilen bilgi dinamik sistemlerde kullanılabilir hale gelecektir. Kıtaların bile hareket ettiği Dünya'da statik hiçbir şey olmadığından bir“Uzay-Zaman Referans Sistemi”ihtiyacı doğmuştur. Uzay-Zaman referans sistemi tanımlandıktan sonra datum kavramı tanımlanabilir. Datum, yerin şeklini ve boyutunu tanımlayan bir referans sistemidir. Tanımlamak için bir referans elipsoit, enlem-boylam oryantasyonu ve yerküre içinde fiziksel bir yerde bulunan orijin noktasına ihtiyaç duyulmaktadır. Bu bilgiler kısaca Referans Elipsoiti ve Başlangıç Noktasının Koordinatları olmak üzere iki parametreye denk gelmektedir. Daha sonra konumlamada kullanılan çeşitli ölçüm yöntemlerinden bahsedilmiştir. Sonuç olarak ölçülen büyüklük ne kadar farklı olursa olsun tüm sistemlerde isabetli ölçümler için alıcı-verici arasındaki görüş hattı açık olmalıdır. \begin{itemize} \item Duvar, cam, kapı gibi ortamların arkasından ya da başka bir yerden çarparak gelen işaretler daha yavaş ya da daha fazla yol alacaktır. Bu da işaret seyahat süresi temelli bir ölçümde hataya sebep olacaktır. \item Yine benzer yerlere çarparak gelen sinyaller gelmesi gereken açıdan farklı bir açıda geleceği için yanlış ölçüm alınacaktır. \item Ortama eklenen veya ortamdan çıkarılan cisimler ortamın ayrımlama sırasında bulunduğu halden farklı bir hale gelmesine neden olmaktadır. Bu sebeple alıcı taraftaki sinyal gücü değişecek ve kayıtlı veritabanındaki değerler ile gerçek değerler farklılaşacaktır. \end{itemize} Bu tip hataların engellenebilmesi için mümkün mertebe görüş hattı açık tutulmalıdır. Görüş hattını açık tutmak için aşağıdaki yöntemler kullanılabilir: \begin{itemize} \item Ekip unsurlarının rijit bir graf oluşturacak şekilde koordine hareket ettirilmesi \item Ağın yedekli ve optimize planlanması ve böylece her durumda en az 2-3 verici görüşünün sağlanması \item Ultrasonik ve ataletsel navigasyon gibi sensör füzyonu çözümleri \end{itemize} Tezin üçüncü bölümünde bir ekip üyelerinin yerini tayin edebilmek için kısım 2'de belirtilen yöntemlerden farklı olarak öne çıkan iki işbirlikçi yöntem ele alınmıştır. Bunlardan ilki Torgerson tarafından ortaya atılan çok boyutlu ölçekleme, diğeri ise mesafe geometrisi problemi olarak da anılan çizge kuramsal temelli çözümdür. Temelleri 1936 yılında Eckart ve Young tarafından atılan ve konumlamada kullanılan versiyonu 1952 yılında Torgerson tarafından ortaya konulan Klasik Çok Boyutlu Ölçekleme algoritması ilk olarak insan psikolojisinde uyartılar (İng. Stimuli) arasındaki benzerliklerin incelenmesi ve gösterimi için oluşturulmuştur. ÇBÖ, söz konusu uyartıların benzerlik/benzersizlik derecelerinden faydalanarak aralarındaki çok boyutlu ilişkiyi belirli boyutlara indirgeyebilen, uyartıların birbirine göre bulunduğu konumu görselleştirebilen bir yöntemdir. Uyartılar arası benzersizlik ilişkisi yerine uzayda dağılmış bir küme içindeki noktalar arası Öklid uzaklıkları konulduğunda ÇBÖ yöntemi bu noktaların birbirine göre nasıl dizildiğini tam olarak ortaya çıkarabilmektedir. Fakat bu dizilim, herhangi bir referans noktası belirtilmediğinden göreli koordinatlarda rasgele bir şekilde dönmüş, ötelenmiş ve katlanmış görünebilmektedir. Çizge kuramsal temelli yöntem ise daha önce çoklu konumlama problemini genelleştirmek amacıyla yapılan birkaç çalışmadan temel alır. Genelleştirmeden kasıt, yöntemin iki veya üç boyutlu uzaylardan herhangi birine geçiş yapıldığında ciddi değişikliklere ihtiyaç duymadan çalştırılabilmesidir. Bu çalışmalar muhteviyetında soyut cebir, diferansiyel topoloji ve çizge kuramı gibi ileri matematik konularından çeşitli kavram ve konseptleri barındırmaktadır. Böylelikle çoklu konumlama probleminin çözümünde kullanılabilecek daha gelişmiş ve dayanıklı yöntemlerin gelişmesinde temel rol oynamışlardır. Bu bölümde teorik ve pratik uygulama bakış açısı ile literatürde dikkat çeken bir yöntem seçilmiş ve derinlemesine analiz edilerek bizim problemimize uygunluğu araştırılmıştır. Tezin dördüncü kısmında çok boyutlu ölçekleme ve çizge kuramsal yöntemin harmanlandığı bir simülasyon çalışması yapılmıştır. Veri hazırlama ve çizge kuramsal koordinat çözümü olmak üzere iki ana aşamadan oluşan bu simülasyon ile Türkiye'de bulunan havalimanlarının koordinatları, yalnızca komşuları arasındaki uzaklıklar kullanılarak hesaplanmıştır. Ayrıca çizge kuramsal yöntemde referans olarak alınan çalışmaya ek olarak stres uzayının örneklem sayısı ile grafın seyrekliği ve mertebesi arasında bir ilişki tespit edilmiştir. Normalde belirtilen çalışmada örneklem sayısı görece yüksek bir değerde sabit tutulmuş ve hesaplamaya etkisi düşük olarak belirtilmişti. Fakat bizim kullandığımız grafın jenerik global rijit olmadığı ve görece seyrek olduğu bir durumda büyük stres uzayının örneklenmesi ve her bir örneğe özdeğer ayrışması yöntemi uygulanması algoritmayı ciddi oranda yavaşlatmaktadır. Dolayısıyla bu örneklem sayısı değeri gürültüyü bastıracak kadar yüksek, fakat yeterince faydalı olacak kadar da düşük olmalıdır. Grafikler ve ilgili haritalar EK-C'de verilmiştir. Sonuç olarak uygulama alanları ve kullanılan kavramlar farklılaşsa da, konumlama ve seyrüsefer anlamında karşılaşılan teknik problemler kara, hava veya su ortamında hayli benzerlik göstermektedir. Daha önce de belirtildiği gibi ölçülen büyüklük ne kadar farklı olursa olsun tüm sistemlerde isabetli ölçümler için alıcı-verici arasındaki görüş hattı açık olmalıdır. Bu ve daha önce bahsedilen problemler çözüldüğü takdirde konumlama teknikleri başlığı altında incelenebilecek birçok problem de kaynağında çözülmüş olacaktır. Zira çok boyutlu ölçekleme ya da çizge kuramsal yöntemlerden hangisini kullanırsak kullanalım mesafe ölçümlerimiz problemli ise ekip üyelerinin konumlarını doğru hesaplamamız mümkün olmayacaktır. Çalışma, böyle bir ortamda ekip konumlama probleminin çözümünde göreli ve mutlak koordinatlar hesaplayan iki farklı yöntemin hibrit bir şekilde kullanılmasını önererek son bulmaktadır.
Özet (Çeviri)
The team localization problem has been emerged recently, especially after the state-of-the-art multi-agent robotic technologies had been released to the public by the open-source robotics communities. Over the past few decades, the localization solutions were relied solely on the established infrastructures, prominently based on global navigation satellite systems (GNSS). Although extensive research has been carried out on cooperative localization solutions, very little attention has been paid to the role of underlying principles. Therefore, most of the researchers had been using different words to describe the same concept in their works. The specific objective of this research is to find a suitable team localization solution by contemplating the fundamentals of positioning. The overall structure of this thesis takes the form of five chapters, including introduction, fundamentals of positioning, cooperative localization techniques, experimental study, and conclusion. Chapter One begins with the introductory section and highlights the motivation of this research. Chapter Two presents the fundamental concepts of the positioning problem and focuses on the standard measurement types used in positioning techniques. Chapter Three puts forward two distinguished cooperative localization techniques and focuses on their theoretical background together with the underlying mathematics. The first one is Multi-Dimensional Scaling (MDS), and the second is a graph theory-based distance geometry solution. The graph-theoretic solution works in two or three dimensions without changing the equations. However, in Chapter Four, we performed a simulation in two dimensions which gathered the two mentioned cooperative localization techniques to mimic real-world conditions. Data preparation with MDS and localization with graph theory are the two main parts of the simulation. Given only neighborhood distances, we have successfully localized the airports of Turkey. Finally, in the last Chapter, we got back to the big picture and presented our conclusions about the positioning techniques with regard to the team localization problem. The current study found that drawbacks of the sole GNSS reliance might be avoided by augmenting it with a relative localization technique in a suitable team localization solution. These results provide further support for continuing with real-world systems. However, caution must be applied, as we assumed the communication works perfectly. In a distributed network, the communication protocol must be carefully designed to reduce traffic and energy consumption while increasing the network throughput and speed. Therefore, there needs to be interdisciplinary work-sharing in order to accomplish a complete solution.
Benzer Tezler
- A scheduling model for centralized cognitive radio networks
Merkezi bilişsel radyo ağları için bir çizelgeleme modeli
DİDEM GÖZÜPEK
Doktora
İngilizce
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. FATİH ALAGÖZ
- Ses sinyallerinin graf tabanlı temsillerinin yapay zekâ yöntemleri ile sınıflandırılması
Classification of graph-based representations of audio signals by artificial intelligence methods
SERKAN AKSU
Doktora
Türkçe
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKarabük ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. İLKER TÜRKER
- Değiştirilmiş düğüm yöntemi kullanılarak durum denklemlerinin elde edilmesi
Obtoining of state equations using modified nodal analysis
BAHADIR ÖZDEMİR
Yüksek Lisans
Türkçe
1997
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDevreler ve Sistemler Ana Bilim Dalı
PROF. DR. FUAT ANDAY
- Hücresel imalatın başlangıç aşamaları için uzman sistem yaklaşımı
An Expert systems approach to the early stages of cellular manufacturing systems design
UFUK CEBECİ
- Diagnosis and troubleshooting using probabilistic networks and value of information
Olasılık ağlarını ve bilginin değerini kullanan teşhis ve sorun giderme sistemleri
KORHAN GÖKÇAY
Yüksek Lisans
İngilizce
1999
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. TANER BİLGİÇ