3d Simultaneous Localization And Mapping Methods In Outdoor And Large-scale Environments For Autonomous Robot Navigation

Tez (Doktora) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2012Thesis (PhD) -- İstanbul Technical University, Institute of Science and Technology, 2012Otonom araçların, Global Pozisyonlama Sistemi (GPS) gibi harici bir referans sistemi bilgisinin mevcut olmadığı, bilinmeyen bir ortamda ilerlerken aracın bir taraftan ortamın harita bilgisini çıkarırken diğer taraftan bu haritaya bakarak kendi konum bilgisini üretmesi Eş Zamanlı Konumlama ve Haritalama (EZKH) problemi olarak bilinir. Bu problem son yirmi yılda mobil robotik ve insansız araçlar alanındaki araştırmalarda en önemli çalışmalardan biri olmuştur. EZKH probleminde, konumlama ve haritalama birbirine bağımlı süreçler olduğundan ve ortamın haritasının önceden bilinmediği ya da GPS bilgisinin olmadığı durumlarda ayrı ayrı çözülemediğinden “tavuk-yumurta” problemi olarak da görülmektedir. Modelleme hataları, sensörler tarafından sağlanan bilgilerin belirsiz olması ve doğrusallaştırma problemlerinden dolayı EZKH probleminin çözümü genellikle deterministik yöntemler yerine olasılıksal yöntemlere dayandığı görülmektedir. Ancak olasılıksal yöntemler, haritadaki imleç sayısı ile karesel olarak artan bir hesaplama karmaşıklığına sahip olduğundan çözümü deterministik yöntemlere oranla daha zor ve karmaşıktır. Önerilen bir olasılıksal EZKH yöntemin bilimsel bir sınıflandırma içerisinde nerede olduğu giriş kısmında detaylıca açıklanmıştır. Kısaca bahsetmek gerekirse bu tezde imleç (feature) ve hacimsel haritalama, iki grup EZKH yöntemi içinde kullanılmıştır. İlk olarak imleç tabanlı EZKH yöntemlerinde imleç çıkarma işlemi yapılırken, tarama eşleştirme tabanlı EZKH yöntemlerinde yoğun işlemlerin olduğu hacimsel veriler kullanılmıştır. EZKH probleminin sınıflandırılmasında diğer bir kavram da veri eşleştirmenin olup olmayacağı konusudur. Bu çalışmada yeni bir imleç çıkarma yöntemi önerildiğinden veri ilişkilendirme problemine de yeni bir yaklaşımla çözüm önerilmiştir. Sınıflandırma içerisinde bir diğer kabul de önerilen yöntemin çalışacağı ortam tipi ile ilgilidir. Bu tezde önerilen yöntemler kentsel bir alanda toplanmış olduğundan ortamın dinamik olduğu düşünülmektedir. Ayrıca önemli başlıklardan biri de çevrim kapama problemidir ki robotun görevini tamamladıktan sonra başlangıç noktasına geri geldiğini algılama problemi olarak tanımlanır. İmleç tabanlı EZKH probleminin çözümünde, önerilen imleç çıkarma ve buna yönelik veri eşleştirme yöntemi çevrim kapama işlemini otomatik olarak yaptığından yöntemin harici bir çevrim kapama yöntemine ihtiyacı yoktur. Ancak, tarama eşleştirmeye dayalı EZKH problemlerinin kararlı ve doğru çalışabilmesi için bir çevrim kapamaya ihtiyaç duyarlar. Bu tezde tarama eşleştirmeye yönelik yapılan çalışmalarda çevrim kapama problemi için herhangi bir bilimsel katkı yer almamaktadır. Mevcut EZKH yöntemleri genellikle ortamın kapalı ve görece sınırlı bir alan olduğunu varsayarlar. Bu tip ortamlarda, Genişletilmiş Kalman Filtresi (GKF) kullanan Geleneksel EZKH yöntemleri neredeyse hiç problemsiz çalışabilmektedir. Ancak, harici ve geniş ölçekli ortamlarda EZKH problemin çözümü daha zor ve gerçek zamanda kusursuz çalışabilen bir yöntem bulunmamaktadır. Bir grup EZKH yöntemi, LiDAR veya stereo kameralar ile elde edilen hacimsel verilerden imleç çıkarma yöntemleri ile imleçler çıkarırlar. Dış ortamda imleç çıkarma sürecinin temel problemi, ortamın dinamik, yapısal olmayan ve önceden tahmin edilemeyen gürültü tipine sahip olmasıdır. Diğer bir grup EZKH yöntemleri de iki ardışıl taramadan robotun rölatif dönüşüm parametrelerini hesaplayan tarama eşleştirme algoritmalarına dayanır. Bu tezde, her iki grup EZKH yöntemi de irdelenmiş ve her iki alanda da önemli katkılarda bulunulmuştur. İlk olarak, Normal Dağılım Dönüşümüne (NDD) dayanan yeni bir tarama eşleştirme yöntemi önerilmiştir. Bu yöntem çok katmanlı bir yapıyı yeni bir maliyet fonksiyonu kullandığından Çok Katmanlı Normal Dağılım Dönüşümü (ÇKNDD) olarak adlandırılmıştır ve klasik NDD’ ye nazaran daha hızlı ve daha büyük miktardaki dönüşüm parametrelerini hesaplayabilme kabiliyetine sahiptir. Bu yöntemde, referans nokta bulutu öncelikle her katmanda farklı, aynı katmanda eşit hücre büyüklükleri bölünerek ayrıklaştırılır. Daha sonra her bir hücre içerisindeki noktaların ortalama vektörü ve kovaryans matrisi bulunarak nokta bulutunun Normal Dağılım Dönüşümü (NDD) bulunmuş olur. Eşleştirme sürecinde ise eşleştirme yapılacak olan ikinci nokta bulutundan seçilen noktaların rölatif dönüşüm parametreleri ile modellenmiş referans nokta bulutu üzerine izdüşümü ile hangi hücreye karşılık geldiği bulunur ve bu nokta ile hücre ortalama ve kovaryans değerlerine bağlı olarak bir hata vektörü tanımlanır. Bu hata vektörünün tüm noktaları kapsayan toplamı Newton yöntemi ile iteratif bir şekilde minimize edilerek rölatif öteleme ve dönmeyi birlikte ifade eden dönüşüm parametreleri hesaplanır. İkinci bir katkı olarak, harici ve geniş ölçek ortamlarda EZKH problemine yönelik olarak olasılıksal bir algoritma ile düzlem algılamaya dayanan yeni bir imleç çıkarma yöntemi önerilmiştir. Bu imleç çıkarma yönteminde olasılıksal düzlem algılama yöntemi önerildiğinden yöntem gürültü ve dış ortamda daha dayanıklı sonuçlar vermektedir. Bu yöntemde, nokta bulutu öncelikle eşit hacimli hücrelere bölünür ve her bir hücredeki noktalara varsa bir düzlem uydurulur. Daha sonra bu düzlemler iki boyutlu ana eksenleri üzerine izdüşürülürler ve izdüşümleri üzerinden düzlemlerin dışbükey noktaları bulunur ve bu noktalar tekrar üç boyuta geri izdüşümleri gerçekleştirilir. Son olarak, dolu hücredeki düzlem parçacıkları bu çalışmada önerilen bir düzlem birleştirme yöntemi ile birleştirilerek daha büyük boyutlu düzlemler ede edilir. Bu imleç çıkarma yönteminden iki şekilde faydalanılmıştır. Birincisi çıkarılan düzlemsel imleçler ÇKNDD tarama eşleştirme yöntemin kullanılarak daha dayanıklı ve hızlı eşleştirme yapabilen imleç tabanlı yeni bir tarama eşleştirme yöntemi önerilmiştir. İkincisi ise çıkarılan bu düzlemsel imleçler imleç tabanlı EZKH probleminin çözümünde “işaretçi (landmark)” olarak kullanılmıştır. Son olarak, önerilen tarama eşleştirme ve imleç çıkarma yöntemlerinin EZKH problemine nasıl uygulanacağı sunulmuştur. Tarama eşleştirme yöntemi, ÇKNDD, Kalman Filtresi (KF) ile uyumlu hale getirilmiş ve EZKH problemin çözümünde kullanılmıştır. İmleç çıkarma yöntemi de literatürde önemli yeri olan Genişletilmiş KF (GKF), Kübik KF (KKF) gibi filtrelere uyarlanmış ve geçerliliği gösterilmiştir. Bir sonraki aşamada yeni bir filtre olan Rassallaştırılmış Sigma Nokta KF (RSNKF) EZKH problemine uyarlanmış ve düzlemsel imleçler ile deneyler gerçekleştirilmiştir. Ancak bahsedilen filtre yöntemleri, durum vektörünün boyutunun artması ile hesaplama karmaşıklığı arasında karesel bir ilişkinin olmasından dolayı geniş ölçekli haritalamada önemli bir dezavantaja sahiplerdir. Nihai olarak bu tezde bu amaçla, düzlemsel imleçleri kullanan, geniş ve harici ortamlarda EZKH probleminin çözümü için, imleç sayısından bağımsız hesaplama yapabilen Seyrek Genişletilmiş Bilgi Filtreleri (SGBF) önerilmiştir. SGBF’ leri aslında Kalman filtrelerinin bir kanonik formu olan bilgi filtrelerinin seyreltilmesi ile oluşmaktadır. Robot ile pasif imleçler arasındaki zayıf bağa sahip olan bağlantılar ortadan kaldırılarak bilgi matrisinin seyreltilmesi gerçekleştirilir. Bu sayede bilgi filtrelerinin önemli bir dezavantajı olan ölçüm güncelleme imleç sayısından bağımsız olarak sabit bir zaman içerisinde çözümlenebilmektedir. Önerilen düzlemsel imleçler noktasal imleçlerden farklı olduğundan olasılıksal veri ilişkilendirme yöntemleri kullanılamaz; yerine imleç çıkarma yönteminden elde edilen düzlemlerin diğer özellikleri kullanılarak ilişkilendirme yapılır. Bu sayede bilgi filtrelerinin darboğazı olan veri ilişkilendirme problemi de çözümlenmiş olur. Deneysel sonuçlar şehir ortamında lazer tarayıcılar kullanılarak toplanan gerçek bir veri seti üzerinden gerçekleştirilmiştir. Bazı durumlarda yöntem iyileştirme çalışmaları için simülasyon deneyleri de yapılmış ve sonuçlar tezin ilgili bölümlerinde yer verilmiştir. Son olarak EZKH yöntemlerinin değerlendirilebilmesi amacıyla literatüre mevcut olan iki yöntemden faydalanılmış ve imleç tabanlı tüm filtre performansları karşılaştırılmıştır. Sonuçlar önerilen tarama eşleştirme ve imleç çıkarma yöntemlerinin dış ortamda ve geniş ölçekli EZKH probleminin çözümünde başarılı bir şekilde kullanılabileceğini göstermektedir.The problem of concurrent localization and mapping for a fully autonomous system in an unknown environment, where the external reference systems like Global Navigation Satellite System (GNSS) or Global Positioning System (GPS) is not available, is known as Simultaneous Localization and Map (SLAM) building problem. This problem has been one of the most popular research areas in mobile robotics in the last two decades, and important approaches have been proposed to solve this problem. The SLAM problem is considered as “chicken and egg” problem since both localization and mapping are highly related and cannot be solved individually for unknown and GPS-proof environments. The traditional SLAM methods using Extended Kalman Filter (EKF) work without any problem in indoor environments. However, outdoor and large-scale SLAM is very problematic and there is no perfect solution implemented with actual systems. A group of SLAM methods uses features extracted from the high-volume data, which can be obtained from either Light Detection and Ranging (LiDAR) measurement system or stereo vision cameras. Another group of SLAM methods is based on scan matching algorithms, which provides rigid body transformation parameters of the robot motion. In this thesis, two groups of SLAM methods are investigated, and important contributions are made on both groups. First, a novel scan matching method, ML-NDT, based on normal distribution transform is proposed. This method uses a multi-layered structure with a new score function definition and provides fast and long-range measurement capability with respect to the conventional methods. Second, a new feature extraction method based on stochastic plane detection is proposed for outdoor and large-scale SLAM. This method is used in two ways; first, the extracted plane features are used with in ML-NDT scan registration algorithm to obtain more robust and fast scan matching method, and second the extracted features are used as landmarks for the feature based SLAM methods. In scan matching based SLAM algorithm, the Kalman filter (KF) is used to solve SLAM problem under the assumption of Gaussian noise, and in the feature based SLAM problem, traditional filters are used in the solution of SLAM problem with planar features. Finally, a data association algorithm based on the plane merging criteria is proposed for the planar-feature based SLAM. For the experimental results, actual LiDAR datasets obtained from the urban areas are used to show both scan matching and feature extraction methods performances. Finally, two benchmarking methods for 6D-SLAM is evaluated and used to compare the performance of the proposed feature based SLAM methods. The results show that the proposed methods can be used in outdoor and large-scale SLAM problem successfully.DoktoraPh