Labirentler ve Robotlar
Robot bir fare karmaşık bir labirenti nasıl çözebilir?
Bir labirent ve ufak bir fare robot birleşirse en fazla ne olabilir? 50 yıldan fazla tarihi bulunan Micromouse yarışmasının da cevap aradığı soru tam olarak bu. Gelin sizinle beraber biz de bu sorunun cevabını arayalım.
Micromouse yarışmasını tarif etmek aslında gayet basit. Yarışmacılara bir labirent veriliyor ve bu labirenti gördükten sonra robot fareleri ile en hızlı şekilde orta merkeze gitmeleri isteniyor. Fakat bu anlattığım kadar kolay bir olay değil. Fareler tamamen otonom olmak zorunda. Bunun yanı sıra labirenti öğrenmek ve en hızlı süreyi yapmak için sadece 5 kere girip çıkabilirler. Olayın asıl zor olan kısmı ise labirentin örtüsü açıldıktan sonra farenizde değişiklik yapmanız tamamen yasak!
Peki ya bu fareler daha önce hiçbir bilgi sahibi olmadıkları karmakarışık labirentleri nasıl oluyor da saniyeler içinde çözüyorlar? Bu iş tamamen 50 yıllık algoritma ve donanım gelişmeleri ile oluyor. Bu gelişmeler nelerdir, hemen bir göz atalım.
Micromouse yarışmasının ilk yıllarında en basit teknik kullanılıyordu. Eğer fare, sağındaki duvarı sonuna kadar takip ederse eninde sonunda labirentin çıkışına geliyordu. Maalesef ki bu çözümün geçerliliğini uzun sürmedi. İlerideki yıllarda bitiş merkezi merkeze alındı ve duvarların dizilişi bu yöntemle çözülemeyecek şekilde değiştirildi. İşte tam olarak bu değişimden sonra daha çok yapay zekaya dayalı algoritmalar kullanılmaya başlandı. Bu değişimden sonra üç farklı teknik göze çarpmaya başladı ama hepsinin kendi dezavantajları vardı.
İlk teknik Depth First Search adıyla ortaya çıktı: fare robot her yol ayrımına geldiğinde bu iki yol ayrımından birini denemesi ve çıkmaza gelirse geri dönüp diğer yol ayrımına girmesi. Evet bu teknikle fare bitiş merkezini bulabiliyordu fakat merkeze giden ilk yolu belleğine kaydediyordu ve daha hızlı olan yolları kaçırabiliyordu. Çünkü merkeze giden yaklaşık üç yol belirleniyordu ve en hızlısını bulmak tamamen farenin algoritmasına bırakılıyordu. Bu yüzden başka bir tekniğe geçildi. Breadth First Search adlı teknikte ise fare robotumuz yol ayrımında ucu açık bir yol bulduğunda en geriye gidip diğer yol ayrımlarını da deniyordu. Sözde iyi olsa da teker teker tüm yol ayrımlarını denemek çok vakit alıyordu ve sahip oldukları 5 hakkı heba etmek istemeyen yarışmacılar daha hızlı teknikler aramaya başladı.
Bazı gruplar ise biraz eleştiriye yol açan üçüncü tekniğe yöneldi. Whole Maze dediğimiz bu teknik: tüm labirentin dolanılarak haritasının çizilmesi ve en hızlı yolun bulunmasıydı. Fazla vakit alan bu teknik de bir süre sonra bırakıldı. Şu an kendinize şunu soruyor olabilirsiniz: “Peki en optimal teknik hangisi?”. Yaklaşık yirmi sene önce bulunan ve günümüzde tüm takımlar tarafından kullanılan Flood Fill tekniğine gelin göz atalım.
Bu teknik ile tatlı fare robotumuz iyimser bir yolculuğa çıkıyor. Hatta faremiz o kadar iyimser ki sanki duvar yokmuşçasına kafasında bir harita belirliyor ve merkeze doğru en kısa yolu çiziyor. Bu yolda ilerleyen fare robotumuz önüne bir engel çıkınca duruyor, engeli belleğine kaydediyor ve tekrar en kısa yolu çiziyor. Sürekli en kısa yolu çiziyor, ilerliyor, çiziyor, ilerliyor ve engellere çok kez takılsa da en kısa yolu en optimal şekilde buluyor. Bir nevi labirente su döküp akan suyu takip etmek gibi tabir edilen bu teknik çok basit ve fare robotumuzu oldukça hızlı şekilde merkeze ulaştırıyor. Nihai olarak bu teknik artık kullanılan tek teknik oluyor.
Toparlamak gerekirse elli yıldan fazla süredir gelişen fare robotumuzun tek bir duvarı takip etmekten, oldukça zor bir labirenti yaklaşık on saniyede çözmek gibi seviyelere gelmesi gerçekten bize teknolojinin ne kadar hızlı ilerlediğini bir kere daha gösteriyor. Bu ve buna benzer yazılar ilginizi çekiyorsa daha fazlası için takipte kalın!
