SLAM Nedir
2.1.1 SLAM Nedir ?
SLAM problemi, bilinmeyen bir ortamda nereye konulduğu bilinmeyen bir mobil robotun artımlı olarak tutarlı bir harita inşa edebiliyor mu ve aynı anda bu haritadaki konumunun belirleyebiliyor mu sorusunu sorar.
SLAM probleminin çözümü robot topluluğu için son on yılda dikkate değer bir başarıdır. SLAM formüle edilmiş ve teorik olarak değişik formlarda çözülmüştür.
Farklı SLAM çözümleri vardır. Bunlar:
· İçeri Robotlar
· Dışarı Robotlar
· Denizaltı Robotlar
· Hava Robotları
Sistemlerinde ayrı ayrı SLAM çözümleri vardır.
SLAM şu an çözülmüş bir problem olarak düşünülebilir.[10]
2.1.2. SLAM Paradigmaları
SLAM çözümünde kullanılan 3 ana paradigma vardır. İlki Extended Kalman Filter (EKF) SLAM, tarihçe olarak en eskisi olsa da hesaplama özelliklerinde olan kısıtlamalardan dolayı popülaritesini yitirmiştir. İkincisi ise grafiksel sunum tabanlıdır. Başarılı bir şekilde seyrek doğrusal olmayan optimizasyon metotlarına uygulanabiliyor ve bu sayede tüm SLAM problemlerine çözüm için ana paradigma olmuştur. Sonuncu metot ise parametrik olmayan istatiksel filtreleme tekniği olan Particle Filter’dir. Çevrimiçi SLAM için popüler bir metottur. SLAM’ın veri ilişkilendirmesi sorununa yeni bir çözüm sağlar.[11]
2.1.2.1 Extended Kalman Filters ( Genişletilmiş Kalman Filtresi )
Bu anlatımda Extended Kalman Filter ( Genişletilmiş Kalman Filtresi ) GKF kısaltması ile anlatılacaktır.
SLAM problemi için birçok çözüm mevcuttur bunlardan birisi de Genişletilmiş Kalman Filtresi çözümüdür. Bu çözümün diğerlerinden farkı robotun lokalizasyonunu yaparken aynı zamanda oryantasyon bilgisini de bulabilmesidir.[12]
SLAM’ın ilk ve en etkili paradigmasıdır.
Bu algoritma, özellik tabanlı çevre sunumunu objelerin uygun parametre uzayında etkili bir şekilde nokta olarak temsil edildiği metrik bir sunum yapar.
Kalman filtresi ile karşılaştırıldığında Kalman Filtresi sadece doğrusal sistemler için çalışır. Ama Genişletilmiş Kalman Filtresi doğrusal olmayan sistemlerle de çalıştığı için tercih edilir.[13]
Genişletilmiş Kalman Filtresi (GKF), Kalman Filtresi’nin doğrusal olmayan fonksiyonlarda da kullanılmasını sağlayan bir metottur, robotun hareket ve algı fonksiyonları doğrusal olmadığından robotik problemlerinde de kullanılır.[14]
Kalman filtresi formülleri içerisinde sadece küçük bir değişiklik yapılarak Genişletilmiş Kalman filtresi(GKF) ortaya atılmıştır.
GKF’yi örnek üzerinden anlatmak gerekirse:
Bir aracı düşünelim t zaman uzayında hareket ediyor olsun. İlerlerken gözlem ve düzeltme yaparak ilerler. Bu sırada belirsizlik ve işaretlerin konumunu öngörür. Belirsizliklerdeki değişmeler buralarda gözlemlenebilir. Başlangıçta gözlem yapar ve ilerler. Sonraları hem gözlem hem de düzeltme yaparak gitmelidir. İlerledikçe araç önceki adımlardaki işaretleri ve bulunduğu konumu öngörür. Ve düzeltme için algılayıcı gözlemlerine ihtiyaç duyar. Bu şekilde ilerledikçe kendi konumunu ve işaretlerin konum belirsizliklerini çözümler.[15]
Durum matrisi adlı bir sütun matrisinde GKF’nin bütün durum değişkenlerinin parametreleri tutulur.
Bu parametreler SLAM probleminde robot konumu ve yer işaretçilerinin konumu olmaktadır. Bu matriste başlangıçta robotun konumu ile ilgili, sonra yer işaretçileriyle ilgili parametreler tutulur.
Bu algoritmada hareket güncellemesi ve algı güncellemesi bulunur. Hareket güncellemesinde kinematik kullanılarak hesaplanan robotun konumunu ifade eden Gauss dağılımının ortalama ve kovaryans değerleri güncellenir. Algıda ise en son görülen yer işaretçisinin önceden görülmüş olan yer işaretçilerinden biri olup olmadığı kontrol edilir. Buradaki sonuca göre (önceki bir işaretçi ya da yeni bir işaretçi) gözlemin güvenirliliğine bağlı olarak yer işaretçisi ve robot konumunda düzeltmeler yapılır, ilk defa görülüyorlar ise durum matrisine eklenir.
Hareket Güncellemesi: Robotun konum inancına odometri verisi yardımıyla uygulanan güncellemedir.
Algı Güncellemesi: Robotun inancıyla algılayıcı verileri yardımıyla uygulanan güncellemedir. [13]
GKF ‘nin güçlü tarafı robotun konumlarından ve işaretçi nesnelerin yerinden, robotun kendi konumunun koşullu olasılığını gerçek zamanlı olarak çok iyi bir şekilde tahmin edebilmesidir. Bunu ancak gaussian metodları içinde barından yöntemler yapabilir.
GKF’nin gerçek zamanlı olarak robotun konumlarından ve işaretçi nesnelerin yerinden kendi konumunu n koşullu olasılığını yüksek derecede tahmin edebilmesidir. Bunu yaparken de Gaussian Metotları yardımıyla yapar.
GKF’nin eksilerinden bahsetmek gerekirse;
· Yaklaşık Gauss fonksiyonu hesaplanması beraberinde belirsizliklerden dolayı karmaşıklık getirir.
· İşlemlerin artması. (Jacobian Matrislerinin hesaplanması)
· Lineerleştirme (Doğrusallaştırma) gerçek inanç değerlerinden sapar.
· Robotun hareket sisteminin çok iyi yapılmış olması gerekir. Algılayıcı gürültüleri ( tekerlek kayması, takılma, ayna vs.) çok iyi bilinmesi gerekir.[13]
2.1.2.2. Particle Filter ( Parçacık Filtresi )
İkinci pardigma olan Parçacık metotları Parçacık Filtresi tabanlıdır. Bu filtre son yıllarda popüler olmaya başlamıştır. [11]
Sonlu sayıda dağılmış olan parametrelerin inanç değerlerine yakınlaşması ve Bayes filtrelerinin parametrik olmayan (nonparametric) alternatif gerçekleştirimidir. GKF ile karşılaştırıldığında dağılımların Gauss dağılımı olması zorunluluğu yoktur.
PF’de durumların önceki dağılımlarına parçacık adı verilir. Genellikle parçacık sayısı 1000 gibi büyük rakamlar olur.
Parçacık Filtesi algoritması Genişletilmiş Kalman Filtresi ile benzer şekilde inanç değerlerini yaklaşık olarak hesaplar. Bu hesaplamalardaki zamansal gecikmeler kaynaklı zamanı yakınsama hataları oluşur.[13]
Parçacık Filtresi’nin temeli bir değişkenin tüm olasılık dağılım fonksiyonunun örnekleme tabanlı bir temsilini yapmasıdır. Bu örnekleme süreçlere bağlıdır, değişkenin değerleri süreçlerden çıkan sonuçlara göre değişkenin durumu değişir. Bu değişkenin birden fazla parçacık kopyası bulunur. Ve bu kopyaların her birinin kendisiyle ilişkilendirilmiş bir ağırlığı bulunur. Bu kopyalarının her birinin ağırlığı alınarak ana değişkenin değeri hakkında bir tahmin yapılır.
Parçacık Filtresi iki adımda gelişen özyinelemeli bir algoritmadır. Bu adımlar tahmin ve güncelleme adımlarıdır.
Tahmin Adımı: Robotun her konum değiştirmesinde gürültünün rastgele bir değer seçilerek kullanılan modele göre değişkenin değiştirilmesidir.
Güncelleme Adımı: Tahmin adımından sonra çalışır. Algılayıcıdan alınan son bilgiler ışığında her parçacığın ağırlığının tekrar hesaplanmasıdır.
Tahmin adımında parçacıklar için rastgele gürültü değerleri ekler model. Güncelleme adımı parçacık ağırlıklarını güncelleyebilmek için sensörlerden gelen verilerden yardım alır, bunun amacı hareket halindeki robotun olasılık dağılım fonksiyonunun tam olarak tanımlanmasıdır.
Robotun konum tahmini için 3 farklı seçenek mevcuttur. Bunlardan ilki ağırlıklı ortalama, ikincisi en iyi parçacık ve üçüncüsü ise en iyi parçacığın etrafında bir çerçeve içinde ağırlıklı ortalama kullanan gürbüz ortalamadır. En iyi parçacık yönteminin dezavantajı olarak ayrıklaştırma hatalarını ve çok modelli dağılımlarda iyi sonuç verememesini sayabiliriz. En iyi yöntem olarak gürbüz ortalama sayılabilir ama bu da fazlasıyla işlem yükü getirecektir.
Parçacık Filtresi’ndeki önemli problemlerden birisi de birkaç yinelemeden sonra parçacıkların tükenmesidir. Parçacıkların konum tahminlerinin sapma yapıp robotun gerçek konumundan çok farklı konumlarda tahmin yapmaları ve ağırlıklarının robotun konumunu bulunmasına katkılarının küçülmesi de ayrı bir problemdir.[16]
Küçük bir not olarak FastSLAM algoritması parçacık filtresi kullanır.
2.1.2.3. Graf Tabanlı Optimizasyon Teknikleri
Sonuncu paradigma olan Graph-Based Optimization Tecniques adı altında incelenen bu paradigma SLAM problemini doğrusal olmayan seyrek optimizasyon ile çözer. SLAM’ın grafiksel temsilinden alınan sezgileri çizerler.
Graf tabanlı SLAM çözümünde temel sezgiler akıcıdır. Yer işaretleri ve robotun pozisyonu grafın üzerindeki birer düğümdür. Her yer işareti çifti birbirine yayla bağlıdır. Bunlar odometrinin okunması ve iletilmesiyle temsil edilirler. Robotun hissetmesiyle (sensörlerden) diğer yer işaretleri ve konum bilgileri de zamanla oluşur. İletmenin verimine göre robot haritayı ve yolu yumuşatır.
Grafiksel paradigma veri ilişkilendirme problemini ele alabilmek için kolayca genişletilebilir.
Bir diğer avantajı ise yüksek boyutlu haritaları EKF(GKF) SLAM’ından daha iyi boyutlandırabiliyor olmasıdır. GKF kovaryans matrisindeki anahtar limiti sorunu da Grafiksel paradigmada yoktur. Güncelleme zamanı ise sabittir ve gerekli bellek miktarı sabittir(bazı varsayımların altında).
Graf tabanlı paradigma ile yapılmış olan en geniş bazı SLAM haritaları oluşturulmuştur fakat genelde çevrimdışı biçimde.[11]
Problemi temsilen graf kullanılır. Grafikteki her düğüm haritalama sırasında robotun bir pozuna karşılık gelir. İki düğüm arasındaki her kenar, aralarındaki uzamsal kısıtlamaya karşılık gelir. Graf tabanlı SLAM temelde; grafiği oluşturup, kısıtlamalar tarafından getirilen hatayı en aza indirecek bir düğüm yapılandırması bulmak üzerinedir.
Her düğüm robotun pozisyonuna ve lazer ölçümüne karşılık gelir.
Her köşe arası düğümler ise düğümler arasındaki mekânsal kısıtları temsil eder.[17]
Hedef kısıtlamalar tarafından getirilen hatayı en aza indirgeyen düğümlerin bir biçimini bulmaktır.[18]
2.1.3 Haritalama
Robotların otonom bir yapıda olabilmesi için 3 yetiye sahip olması gerekir. Bunlar yürüyebilme, konumlama ve haritalama fonksiyonlarıdır. Bu konu başlığı altında temel fonksiyonlardan birisi olan haritalama problemi üzerinde durulacaktır.
Robotik haritalama için iki bilgi kaynağı vardır. Bunlar allothetic ve idiothetic bilgilerdir. Idiothetic bilgi kaynağı bilgiyi odometriden alır. Robot hareketi hakkında iç bilgiyi destekler. Ve bu bilgiyle dead reckoning yaklaşımı robotun pozisyonunu bulabilir. Allothetic bilgi ise algı ve sensör kaynaklıdır. Çevre hakkındaki dış bilgiyi sağlar. Robot için bilgi lazer, sonar, sensör veya görüntü kaynaklı olabilir.
Robotik haritalamadaki bir problem de ölçüm gürültüsü adıyla bilinir. Bu sorun eğer gürültü istatiksel olarak bağımsız olan çeşitli ölçümler içindeyse kolayca çözülebilir.
Haritalama çeşitli LIDAR, Lazer gibi sensörler yardımıyla yapılabildiği gibi görüntü sistemleriyle de yapılabilir. Bu düşük çözünürlüklü bir LIDAR’dan daha yüksek çözünürlük sunar. Kamera yardımıyla haritalama imaj işleme algoritmaları ile ilişkilidir ve bu da daha yüksek işlem gücü gerektirir.
Tüm haritalama algoritmalarının ortak noktası olasılıksal olmasıdır.
Haritalar ikiye topografiksel ve metrik olmak üzere ikiye ayrılır.
Metrik haritalarda çevre koordinatlı obje gruplarının iki boyutlu uzayda metrik sistemle oluşturulmuş olarak tanıtılır. Mimari taslağına çok benzer. Birçok robotun kullanabileceği haritalardır. Topografiksel haritalara göre oluşturulması daha kolaydır.
Topografiksel haritalarda çevre özel yerlerin ve bu yerlerin arasındaki ilişki olarak temsil edilir. Topografiksel haritalar çeşitli yerler arasındaki bağlantıyı tanımlar ve metrik harita oluşturulurken otomatik olarak çıkartılabilirler. Geometrik çözünürlüğü arttırır ve bu bilgiler planlama, navigasyon gibi görevler için destekleyici olabilir. Büyük ölçekli ortamlar için kullanılır.[19]
Haritalama için bulunan çözümler arasında gmapping ve Hector SLAM metotlarını inceleyeceğiz. Yaygın olarak kullanılan çözüm gmapping algoritmasıdır.
2.1.3.1 Hector SLAM Algoritması ile Haritalama
Hector SLAM metodu ışınların bitiş noktalarının hizalanmasının optimize edilmesi üzerinedir. Bilgisayar görüşündeki işten esinlenen Gauss-Newton yaklaşımı temel fikirdir. Lucas ve Kanade (1981) “An iterative image registration technique with an application to stereo vision” adlı araştırmasında DARPA Image Understanding Workshop içerisinde yayınlanmıştır. Bu yaklaşım ile ışınların bitiş noktaları arasında veri ilişkisi aramaya veya kapsamlı pozisyon aramasına ihtiyaç kalmamıştır.
Bu metotta sadece z bitiş noktasındaki filtreleme tabanlı koordinat kullanılmış. Böylece amaçlanan tarama düzleminin eşiğindeki sadece bitiş noktaları tarama eşleştirme işleminde kullanılmıştır.
Burada algoritma kaynaklı olmayan sıkıntılar doğabilir, örneğin pencereden dışarı çıkan ışınlar haritaya dahil edilebilir. [19]
2.1.3.2 gMapping Algoritması ile Haritalama
Bu haritalama metodu bilinen en popüler ve açıkça bilinen SLAM problemi algoritmasıdır. Giorgia Grisetti, Wolfram Burgard ve Cyrill Stachniss tarafından geliştirilmiştir. Robotun pozisyonlarını takip etmek için Rao-Blackwellized parçacık filtresini kullanır. Halihazırda oluşturulmuş olan harita parçaları ve sensör verileri temellidir.
Her bir parçacık = robotun geçmiş pozisyon örneği + harita üzerinde verilen önceki pozisyon örnek geçmişi; tüm parçacıklar bağımsız olarak kendi haritasını tutar. Gmapping olasılıksal dağılım modeli robotun son gözlemlerini de hesaba katarak bir yayılım oluşturmaktadır. Bu sayede etkin bir şekilde haritalama yapılarak belirsizlikler de aynı zamanda ortadan kalkar[ 364230]
Rao-Blackwellized önem yeniden örnekleme filtresini örnekler. Bunu sensör gözlemleri ve odometri verisi mevcut oldukça artımlı haritalama işlemi için yapar. Aracın yörüngesi ve haritayı temsil eden örnekler setini günceller. Süreç dört adımdan oluşur.
1) Örnekleme: Yeni nesil parçacık { ()}, önerme dağılımı π’den örnekleme yoluyla -1 () neslinden elde edilir. Genellikle, olasılık odometri hareket modeli teklif dağılımı olarak kullanılır.
2) Önem Ağırlığı: Her parçaya, önem örnekleme ilkesine göre bireysel bir önem ağırlığı () atanır.
3) Yeniden Örnekleme: Parçacıklar, önem ağırlığına oranla orantılı olarak çizilir. Sürekli bir dağılıma yaklaşmak için yalnızca sonlu sayıda parçacık kullanıldığından bu adım gereklidir. Ayrıca, yeniden örnekleme, hedef dağılımın öneriden farklı olduğu durumlarda bir parçacık filtresi uygulamamızı sağlar. Yeniden örneklemeden sonra tüm parçacıkların ağırlığı aynıdır.
4) Harita Tahmini: Her bir parçacık için o parçacığın yörüngesi ve gözlemleri temelli karşılık gelen harita tahmini hesaplanır.
Odometri verileri olmadan gmapping yapılamaz.
Rao-Blackwellized filtresinin gmapping algoritması üzerinde yaptığı geliştirmeler sonucu karmaşıklıklar azaltılmış ve daha doğru sonuçlar sağlanmıştır. Yeniden örnekleme kısmında yapılan değişiklikler sonucu bütün parçacıklar değerlerini kaybetmiyor sadece düşük değerli parçacıklar kayboluyor ve yerine daha yüksek olasılıklı parçacıklardan türeyen bir parçacık konuluyor. [19]