Izgara Ortamlarında Sezgisel Arama Algoritmalarının Performans Ölçümleri

3 Deneysel ortam ve performans ölçümleri

Sezgisel arama algoritmaları, bir başlangıç konumu ve bir hedef konumu göz önüne alındığında en uygun yolu belirledikleri için robotik yol bulma gibi alanlarda önemli bir rol oynar. Izgara tabanlı ortamlar, otonom navigasyon ve robotik gibi alanlarda bu algoritmaların uygulanabileceği gerçek dünya ortam senaryolarını temsil etmek için yaygın olarak kullanılır [6]. Bu çalışmada, iyi bilinen buluşsal arama algoritmalarını, yani D*, D* Lite, LPA*, LRTA*, RTAA* ve ARA*'yı farklı ızgara ortamlarında kapsamlı bir şekilde analiz ediyoruz. Algoritmaların araştırılmasına rehberlik etmek ve engel yoğunluğu ve ızgara boyutu gibi birkaç ızgara özelliğinin algoritmaların performansı üzerindeki etkisini değerlendirmek için Öklid uzaklık buluşsal yöntemini kullanıyoruz.

Çalışmamızda, araştırma topluluğunda yol planlama görevlerinde yaygın olarak kullanılmasının yanı sıra basitliği ve kontrol kolaylığı nedeniyle ızgara tabanlı ortamlar kullanıyoruz. Izgaralar geçilebilir durumları temsil eden beyaz hücrelerden oluşurken siyah hücreler geçilemeyen engelleri temsil eder. Simülasyonumuzdaki ajan, yatay ve dikey hareketler için 1'e ve çapraz hareketler için √ 2'ye eşit bir maliyetle sekiz yönde hareket edebilir. İki tür ızgara ortamı kullandık: rastgele oluşturulmuş ızgara ortamları ve kişiselleştirilmiş ızgara ortamları.

Rastgele oluşturulmuş ızgara tabanlı ortamlar: Izgaralar üç parametreyle karakterize edilir:

ızgara boyutu (NxN), engel yoğunluğu ve başlangıç ile hedef durumları arasındaki mesafe. Her parametrenin arama algoritmalarının performansı üzerindeki etkisini araştırmak için, diğer parametreleri sabit tutarken her parametreyi bağımsız olarak değiştirdik. Değişiklikler arasında ızgara boyutunun değiştirilmesi, hedefe başlangıç mesafesinin değiştirilmesi ve engel yoğunluklarının değiştirilmesi yer alıyordu. Bir varyasyondaki her ızgara için, aynı ızgara parametrelerinin on rastgele örneğini oluşturduk (örneğin, 0,25 engel yoğunluğuna sahip, 300x300 boyutunda ve başlangıç-hedef mesafesi 140 olan bir ızgara, rastgele oluşturulmuş on örneğe sahiptir).

Kişiselleştirilmiş ızgara ortamı: Daha spesifik senaryoları simüle etmek için tasarlanmıştır. Bu ızgaralar, hem başlangıç hem de hedef durumları için sabit boyuta (71x31 birim) ve sabit bir konuma sahiptir ve engel konfigürasyonlarına göre iki bölüme ayrılmıştır:

• Yatay duvar konfigürasyonu: Bu deneyler için, her 10 birim ızgara uzunluğunda yarım ızgara genişliğinde yatay duvarlar ekliyoruz. Duvarları iki yönde ekledik: yeni oluşturulan ızgarada bir kez soldan sağa, bir kez de sağdan sola.

• Yatay duvar uzunluğu konfigürasyonu: Burada, içine yerleştirilebilecek tüm olası duvarları ekliyoruz.

ızgara uzunluğu ve her yeni ızgara oluşturduğumuzda tüm duvar uzunluklarını 2 birim artırıyoruz.

Kapsamlı bir analiz sağlamak ve iki farklı engelleme senaryosunun varlığında arama algoritmasının performansına ilişkin incelikli bilgileri ortaya çıkarmak amacıyla bu iki farklı ortamı benimsedik. İlkinde engeller ızgara içerisinde rastgele dağılmışken, ikincisinde duvar benzeri yapılar birbirine bağlı engellerden oluşan bir kütle olarak karşımıza çıkıyor.

Deneylerde kullanılan farklı arama algoritmalarının performansını değerlendirmek için aşağıdaki ölçümleri seçtik:

• Yol maliyeti: Metrik, başlangıçtan hedef duruma kadar yol uzunluğunu veya gerçekleştirilen eylemlerin sayısını ölçer. Çözümün kalitesini gösterir.

• Bellek tüketimi: Algoritmanın çözüm bulması için gereken bellek miktarını ölçer. Algoritmanın ölçeklenebilirliğini kontrol etmek önemlidir ve (KB) cinsinden ölçülür.

• Çözme Süresi: Milisaniye (ms) cinsinden ölçülen, bir algoritmanın bir çözüm bulmak için harcadığı toplam süreyi (ms) temsil eder.

Deneylerimizi 250Gb RAM ile donatılmış ve Ubuntu Linux 22.04 çalıştıran 3.30GHz 27 Intel i9 çekirdeği üzerinde gerçekleştirdik. Aşağıdaki ayarları kullanarak: Tüm algoritmalar buluşsal fonksiyon olarak Öklid mesafesini kullanıyordu. LRTA* ve RTAA* için, her yinelemede genişletilen düğümlerin sayısını 250'ye ayarladık. ARA* algoritması buluşsal yöntem için 2,5 ağırlıkla çalıştırıldı. Rastgeleliği hesaba katmak ve sonuçların güvenilirliğini sağlamak için her algoritmayı her ızgarada 100 kez çalıştırdık.