Bir robot en kısa yolu nasıl bulur?

Bir robot en kısa yolu nasıl bulur? www.yzokul.com.tr

Bir yerden başka bir yere hareket eden bir robotun en iyi gitme yolunu bilmesi gerekir. Soru, en kısa yolu nasıl bulduğudur. Kısa yanıt: robot dünyayı bir harita olarak çizer, sonra başlangıçtan hedefe kadar rotaları karşılaştırmak için adım adım bir yöntem kullanır. Bu kitap her parçayı sade bir dille açıklar. 1

Robotu bir kat planı üzerinde küçük bir nokta olarak düşün. Başlangıç noktasından hedef noktasına gitmesi gerekir. Yol, basitçe noktanın yol boyunca geçtiği yerlerin listesidir. Örneğin yol şöyle olabilir: başlangıç hücresi, sonra sağ, sağ, yukarı, yukarı, hedef hücresi. Robotun işi iyi bir liste bulmaktır. 2

Robotun dünyası, satranç tahtası gibi küçük kare hücrelerden oluşan bir ızgara olarak çizilir. Her hücre ya girilebilir ya da engellidir. Girilebilir bir hücre açık zemin olabilir; engelli bir hücre masa veya duvar olabilir. Örneğin 5'e 5 bir ızgara, ortasında masa olan küçük bir odayı temsil edebilir. 3

Robotun hangi hücrelerde durabileceğini ve hangi komşu hücreler arasında hareket edebileceğini işaretle. Bu geçilebilir noktalar ve bağlantılar birlikte, robotun üzerinde akıl yürüttüğü haritayı oluşturur. Örneğin yan yana iki girilebilir hücre bağlantılıdır; engelli bir hücrenin yanındaki girilebilir hücrenin orada bağlantısı yoktur. Robot yalnızca bağlantılar boyunca hareket eder. 4

Engelli hücrelere hiçbir rotada izin verilmez. Robot yalnızca birbirine bağlı girilebilir hücrelerden geçer. Örneğin bir duvar bir koridoru kapatıyorsa robot diğer girilebilir hücrelerden geçerek etrafından dolaşmalıdır. Engelli bir hücreden geçmeye asla çalışmaz, çünkü bu imkânsız veya güvensiz olurdu. 5

Izgaraya bir başlangıç hücresi ve bir hedef hücresi yerleştir. Çoğu zaman aralarında birçok olası rota vardır. Örneğin açık bir ızgarada önce sağa sonra yukarı gidebilir, önce yukarı sonra sağa gidebilir veya daha uzun bir zikzak izleyebilirsin. Robotun işi bir rota seçmektir, ideal olarak bir ölçüte göre en kısa olanı. 6

Algoritma, robotun tahmin yürütmeden izlediği açık bir adımlar listesidir. Başlangıçtan hedefe doğru seçeneklere bakar ve şimdiye kadar bulunan en iyi rotayı takip eder. Örneğin basit bir algoritma önce başlangıç hücresinin tüm komşularını, sonra onların tüm komşularını kontrol edebilir ve hedefe ulaşana kadar böyle devam edebilir. 7

Algoritma komşu hücrelere tek tek bakar ve şimdiye kadar hangi rotanın daha ucuz olduğunu karşılaştırır. Hedefe ulaşana kadar başlangıçtan dışa doğru genişler. Örneğin önce bir adım uzaktaki hücrelere, sonra iki adım uzaktaki hücrelere bakabilir ve her hücreye bilinen en ucuz rotayı her zaman korur. Bu sistematik karşılaştırma en iyi rotayı bulur. 8

Hücreler arasındaki her hareketin bir maliyeti vardır ve maliyetleri toplamak bir rotanın toplam maliyetini verir. Robot toplam maliyeti en küçük olan rotayı tercih eder. Örneğin her adım 1 maliyetindeyse 5 adımlı bir rota 5 maliyetindedir. 7 adımlı bir rota 7 maliyetindedir, bu yüzden robot 5 adımlı rotayı tercih eder. 9

En kısanın bir anlamı en az adım veya kat edilen en küçük toplam mesafedir. Bir ızgarada bu genellikle bir rotanın kaç hücreden hücreye hareket gerektirdiğini saymaktır. Örneğin önce sağa sonra yukarı gitmek 2 adım alır; sağ, sağ, yukarı, yukarı gitmek 4 adım alır. Robot daha az adımlı rotayı seçer. 10

En kısa aynı zamanda en hızlı rota anlamına gelebilir; burada bazı hareketler diğerlerinden daha uzun sürer. Robot o zaman mesafeler yerine seyahat sürelerini toplar. Örneğin engebeli bir bölgeden geçmek hücre başına 3 saniye sürebilirken pürüzsüz zemin 1 saniye sürer. Pürüzsüz zeminde daha uzun bir rota genel olarak daha hızlı olabilir. 11

En kısa, en az enerji kullanmak anlamına gelebilir. Örneğin yokuş yukarı veya engebeli zeminde gitmek, yokuş aşağı veya pürüzsüz zeminde gitmekten daha fazla enerji maliyetlidir. Robot her rota boyunca enerji maliyetlerini toplar ve en ucuzunu seçer. Mesafe olarak daha uzun bir rota, dik tırmanışlardan kaçınıyorsa daha az enerji kullanabilir. 12

Robot aramaya başlamadan önce hangi ölçünün önemli olduğunu bilmelidir. Aynı harita, mesafe, zaman veya enerjinin sayılıp sayılmamasına bağlı olarak farklı en iyi rotalar verebilir. Örneğin en kısa mesafe rotası çamurdan geçebilirken en düşük enerji rotası etrafından dolaşabilir. Robota hangi maliyeti en aza indireceğini söylemelisin. 13

Yeni bir engel, robot başladıktan sonra seçilen rotayı kapatabilir. O zaman eski rota artık geçerli değildir ve robot yeniden arama yapmalıdır. Örneğin koridora bir kutu konursa robot bunu algılar ve kutunun etrafından yeni bir yol hesaplar. Bu, robotu güvende ve rotasında tutar. 14

Tipik başlangıç hatalarını kontrol et: engelli hücreleri unutmak, üç ölçüyü karıştırmak veya harita değiştikten sonra eski bir rotaya güvenmek. Her hata yanlış veya güvensiz bir yola yol açar. Örneğin engelli bir hücreyi yok saymak robotun bir duvardan geçmeye çalışmasına neden olabilir. Haritayı her zaman güncelle ve maliyet ölçüsünü yeniden kontrol et. 15

Dünyayı geçilebilir noktalar ve bağlantılar olarak haritala, engelli hücrelerden kaçın ve bir algoritmanın rota maliyetlerini karşılaştırmasına izin ver. En kısanın seçilen ölçüye bağlı olduğunu unutma: mesafe, zaman veya enerji. Ortam değiştiğinde yolu yeniden hesapla. Örneğin bir depodaki teslimat robotu, bir rafa en hızlı güvenli rotayı bulmak için bu fikirleri kullanır. 16