Frontier point based autonomous exploration in 2D environment
2B ortamda sınır noktası tabanlı özerk keşif
- Tez No: 732348
- Danışmanlar: PROF. DR. HAKAN TEMELTAŞ
- 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: 2022
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Kontrol ve Otomasyon Mühendisliği Bilim Dalı
- Sayfa Sayısı: 91
Özet
Mobil robotik uygulamalarının önemli bir kısmı için çalışma ortamının bir tür modeline ihtiyaç vardır. Bu nedenle mobil robotik uygulamaları için en önemli sorunlardan biri çevresel modellerin elde edilmesi olmuştur ve bu sebeple literatürde kapsamlı olarak çalışılmıştır. Özellikle tam özerklikten bahsederken çevresel bir modele sahip olmak kritik hale gelir. Bir robotun bulunduğu ortamın bir modelini özerk olarak oluşturması için ortamın haritasını çıkarması, bu sırada haritayı çıkarabilmek için mevcut konumunu hesaplaması, keşif için aday navigasyon hedef noktalarını tespit etmesi, bu noktalar arasından hedef noktayı seçmesi ve seçilen noktaya bir yol planlayıp o yolu takip edebilmesi gerekir. Buradan da anlaşılacağı gibi özerk keşif çok yönlü bir problemdir. Bilinmeyen bir ortamı keşfetmek ve bir temsilini oluşturmak, diğer bir deyişle haritasını çıkarmak, özerkliğin en önemli ön koşullarından biridir. Doluluk ızgara haritaları 2B uygulamalarda en yaygın kullanılan ortam modellerindendir. Bu modelde her bir ızgara hücresi belirli bir bölgeyi temsil etmek için boş, dolu veya bilinmiyor olarak etiketlenir. Çevreyi doğru bir şekilde haritalamak için robotun konumunu veya“Neredeyim?”sorusunun cevabını da bilmesi gerekir. Robotun poz bilgisi harici bir kaynak tarafından sağlanmıyorsa yani poz belirsiz ise, haritalama lokalizasyondan ayrılamaz ve bu görevlerin eş zamanlı olarak gerçekleştirilmesi gerekir ki bu da literatürde eş zamanlı konumlama ve haritalama (EZKH) adı verilen prosedürdür. Bilinmeyen bir bölgenin bir tür temsilini elde etme eylemi keşif olarak tanımlanır. Pasif ve aktif olmak üzere iki tür keşif yöntemi vardır. Pasif keşif yaklaşımları, yalnızca bir harita oluşturmak için çevrelerinden veri toplar ve bu nedenle robotu süren bir insan gibi harici bir karar verme ve planlama mekanizması gerektirir. Aktif olanlar, diğer bir deyişle özerk keşif, ise hedef konumları seçer ve robotun bu hedef noktalara gitmesi için gerçekleştirmesi gereken hareketleri planlar. Kendi başlarına çevrelerinin doğru bir temsilini oluşturabilen robotların, tam özerklik için kilit bir gereklilik olduğu söylenebilir. Bu nedenle, hareket planlama problemi, özerk keşif için ele alınması gereken bir diğer konudur. Literatürde bu problemin üstesinden gelmek için çok sayıda yol planlama tekniği mevcuttur. Tam özerk keşif sürecinin son gereksinimi, sınır noktalarının tespiti ve bu noktalar arasından navigasyon hedefinin seçilmesini içeren iki yönlü bir problemdir. Keşif için bir hedef konum seçilmeden önce haritadaki mevcut sınır bölgeleri çıkarılmalıdır. Bu çalışmada, örnekleme tabanlı bir teknik kullanılarak sınır bölgelerinde yer alan sınır noktaları tespit edilmiştir. İkinci olarak, keşif için en uygun sınır noktası hedef olarak seçilmelidir. Bu sorunu çözmek için bu tez çalışmasında hedef adaylarını içeren bir küme oluşturulduktan sonra bir amaç fonksiyonu kullanılmış ve bu kümeden önerilen amaç fonksiyonuna göre en yüksek gelire sahip nokta hedef olarak seçilmiştir. Bu tezde, bir kalıcı ve iki geçici ağaç olmak üzere üç adet RRT yapısına dayalı bir sınır noktası tespit algoritması sunulmaktadır. Kalıcı ağaç, robotun keşif başlangıcındaki ilk konumundan başlayarak keşif tamamlanana kadar harita üzerinde yayılarak tüm bölgelere ulaşmayı amaçlar. Bu ağacın amacı tüm haritada sınır noktası aramaktır. Geçici ağaçlar ise bir sınır noktası tespit ederse veya kullanıcı tanımlı bir dal sayısına ulaşırsa sıfırlanır. Bu çalışmada ağaçların tamamen haritalanmış bölgelerde sıkışıp kalmaması için maksimum dal sayısı parametresi önerilmiştir. Geçici ağaçlar başlangıç noktalarının farklı olmasından dolayı kendi arasında iki sınıfa ayrılır. Bunlardan ilki, sıfırlandıktan sonra her zaman robotun mevcut konumundan başlar. Bu geçici ağacın öncelikli amacı robotun çevresindeki sınır noktalarını tespit etmektir. İkinci tür geçici ağaç ise robot tarafından görüldüğü için sınır noktası kümesinden elenen sınır noktalarından başlar. Bu noktalar, artık haritalanmış bir bölgede bulundukları için sınır noktası özelliklerini kaybetmişlerdir ve sınır noktası kümesinden çıkarılırlar, ancak yakın çevrelerinde başka sınır bölgelerinin olma olasılığı çok yüksektir. Bu ağaç, bu sınır bölgelerini hızlı bir şekilde tespit etmek için bu çalışma kapsamında geliştirilmiştir. Sınır noktaları tespit edildikten sonra makine öğrenmesi tabanlı bir kümeleme algoritması yardımı ile bu noktalar kümelenir ve sonraki hesaplamalarda yalnızca bu kümelerin merkez noktaları değerlendirmeye alınır. Buradaki amaç çok sayıda noktanın getireceği işlem yükünü azaltmaktır. Bu çalışmada, sınır noktalarını değerlendirmek ve aralarından bir hedef seçmek için bir noktanın bilgi kazancı, sürüş ve yönelim maliyetlerini dikkate alan bir gelir fonksiyonu kullanılmıştır. Bilgi kazancı, sınır noktasında ortalanmış bir daire içindeki bilinmeyen ızgara hücrelerinin sayısı ile ölçülür. Sürüş maliyeti, sınır noktaları ile robotun güncel konumu arasındaki Öklid mesafesini ölçmek yerine tüm sınır noktalarına birer yol planlayarak hesaplanır. Bu sayede sürüş maliyetinin daha doğru hesaplanması hedeflenmektedir. Yol planlamanın başarısız olduğu noktalar, bir diğer deyişle ulaşılamaz noktalar, sınır noktası listesinden filtrelenir. Bu çalışmada kullanılan robot çok yönlü olduğu için yönelim maliyeti mevcut hız vektörünün yönü kullanılarak belirlenir. Sürüş ve yönelim maliyetleri normalleştirilir ve sırasıyla $\beta$ ve $\gamma$ parametreleriyle ağırlıklandırılır. Her nokta için hesaplanan bilgi kazanımı, o noktaya olan maliyetler ile üstel olarak azaltılarak aday sınır noktasının son gelir değeri hesaplanır. Önerilen algoritmanın performansı Gazebo simülatör ile hazırlanan 3 adet simülasyon ortamı kullanılarak denetlenmiştir. Bu simülasyon ortamlarından ikisi özerk keşif metotlarının karşılaştırılması için sunulan hazır ortamlarken üçüncsü önerilen yöntemin büyük bir haritadaki performansını göstermek için özel olarak tasarlanmıştır. Hazır ortamların kullanılmasındaki amaç, değerlendirmeleri daha objektif hale getirmektir. Önerilen yöntemin performansı, bu 3 ortamda gelir fonksiyonunun sırasıyla sürüş ve yönelim maliyetlerini ağırlıklandıran $\beta$ ve $\gamma$ parametrelerinin 5 farklı kombinasyonuna göre incelenmiştir. Her parametre çifti için her ortamda beş adet test gerçekleştirilip toplam keşif süresi ve kat edilen toplam mesafe için ortalama değerler hesaplanmıştır. Ardından Umari tarafından önerilen yöntem karşılaştırmalı değerlendirme için aynı ortamlarda beş kez çalıştırılmıştır. Tüm test sonuçlarının karşılaştırılmasında toplam süre ve toplam mesafenin ortalama değerleri kullanılmış ve tüm ortamlarda başarılı sonuçlar elde edilmiştir. Bu tezin 1. Bölüm'ünde özerk keşfin önemi vurgulanarak bir giriş yapılmış, literatürdeki yöntemlerden bahsedilmiş ve ardından çalışmanın amacı açıklanmıştır. SLAM problemi 2. Bölüm'de tanımlanmış, bu çalışmada kullanılan SLAM tekniği anlatılmış ve literatürde en yaygın olarak uygulanan diğer iki yönteme de kısaca değinilmiştir. Global ve yerel yol planlama arasındaki ayrımdan Bölüm 3'te bahsedilmiş ve bu çalışmada her iki amaç için kullanılan yol planlama yöntemleri daha ayrıntılı olarak açıklanmıştır. Bölüm 4, özerk keşif hakkında ayrıntılı bilgi ve önerilen yöntemin kapsamlı bir tanımını içerirken Bölüm 5'te ise önerilen yöntemin değişik parametre setleri için simülasyon sonuçları ve başka bir özerk keşif tekniği ile karşılaştırması yapılmıştır. Son olarak, Bölüm 6'da sonuç kısmı verilmiştir.
Özet (Çeviri)
A significant portion of mobile robotics applications needs some form of a model of the operating environment. Therefore, one of the most important problems for mobile robotics applications has been the acquisition of environmental models, and for this reason, it has been extensively studied in the literature. Having an environmental model becomes critical, especially when talking about full autonomy. For a robot to create a model of its environment autonomously, it must map the environment, compute its current location to construct the map, identify candidate navigation target points for exploration, select the optimal target point among these points, plan a path to the selected point, and follow it. As can be seen, autonomous exploration is a multifaceted problem. For fast frontier detection, three different tree structures, one permanent and two temporary, based on the RRT method are presented in this thesis. The permanent tree aims to reach all regions by spanning across the map from the robot's initial location at the start of the exploration and grows until the exploration is complete. The purpose of this tree is to search for frontier points on the entire map. Temporary trees, on the other hand, are reset if they detect a frontier point or reach a user-defined number of branches. In this study, the maximum branch number parameter is proposed so that the trees do not get stuck in the fully mapped areas. Temporary trees are divided into two classes among themselves due to the different starting points. The first of these always starts from the robot's current position after reset. The primary purpose of this temporary tree is to detect frontier points around the robot. The second type of temporary tree starts from the frontier points that are eliminated from the frontier point set as they are seen by the robot. Since these points are now in a mapped region, they have lost their frontier point characteristics and are removed from the frontier point set, but there is a high possibility that there are other frontier regions in their immediate vicinity. This tree is developed as part of this study to quickly detect these frontier regions. After the frontier points are determined, these points are clustered with the help of a machine learning-based clustering algorithm and only the center points of these clusters are taken into consideration in further calculations. The aim here is to reduce the processing load of a large number of points. In this study, a revenue function that takes into account the information gain, driving and heading costs of each point is used to evaluate the frontier points and choose a goal among them. Information gain is measured by the number of unknown grid cells in a circle centered at the frontier point. The driving cost is calculated by planning a path to all the frontier points instead of measuring the Euclidean distance between the frontier points and the robot's current position. In this way, it is aimed to calculate the driving cost more accurately. Since the robot used in this study is omni-directional, the heading cost is determined using the current velocity vector. Driving and heading costs are normalized and weighted by the parameters $\beta$ and $\gamma$, respectively. The information gain calculated for each point is exponentially reduced with the costs to that point, and the final revenue of the candidate frontier point is calculated. The performance of the proposed algorithm is tested in 3 simulation environments prepared using the Gazebo simulator. Two of these simulation environments are ready-made benchmark environments for the comparison of autonomous exploration methods, while the third is specially prepared to demonstrate the performance of the proposed method on a large setting. The purpose of using ready-made environments is to make evaluations more objective. The performance of the proposed method is investigated according to 5 different combinations of $\beta$ and $\gamma$ parameters in these 3 environments. Each parameter pair is tested five times in each environment and mean values for total exploration time and total distance traveled is computed. Then, the method proposed by Umari is run five times in the same environments for comparison. The mean values of total time and total distance are used to compare all test results, and successful results are obtained in all environments.
Benzer Tezler
- Türkiye'nin jeoekonomik stratejilerinde Gürcistan'ın yeri
Georgia's place in Turkey's geoeconomic strategies
ALPARSLAN TORUN
Yüksek Lisans
Türkçe
2006
CoğrafyaÇanakkale Onsekiz Mart ÜniversitesiCoğrafya Ana Bilim Dalı
PROF.DR. AYDIN İBRAHİMOV
- Generating representative nondominated point subsets in multi-objective integer programs
Çok amaçlı tamsayı programlarında temsili baskın nokta alt kümelerinin üretilmesi
GÖKHAN CEYHAN
Yüksek Lisans
İngilizce
2014
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA MURAT KÖKSALAN
YRD. DOÇ. DR. BANU LOKMAN
- Alçalma fazındaki en etkin yakıt akışına sahip uçuşların panel veri ve stokastik sınır analizi yöntemleri ile gerçek uçuş verilerine dayalı belirlenmesi
Determination of flights with the most efficient fuel flow during descent phase based on real flight data using panel data and stochastic frontier analysis methods
SERKAN ASLANER
Doktora
Türkçe
2024
Havacılık ve Uzay MühendisliğiEskişehir Teknik ÜniversitesiHava Trafik Kontrol Ana Bilim Dalı
DOÇ. DR. ÖZLEM ŞAHİN
DR. ÖĞR. ÜYESİ İSMAİL YENİLMEZ
- CLIC LHC'ye dayalı gama proton çarpıştırıcısının incelenmesi
The Investigation of gamma proton collider based on CLIC LHC
HÜSNÜ AKSAKAL
Doktora
Türkçe
2007
Fizik ve Fizik MühendisliğiAnkara ÜniversitesiFizik Ana Bilim Dalı
PROF.DR. ABBAS KENAN ÇİFTÇİ