Yazarlar:  (1) Aya Kherrour, Trento Üniversitesi Bilgi Mühendisliği ve Bilgisayar Bilimleri Bölümü;  (2) Marco Robol, Trento Üniversitesi Bilgi Mühendisliği ve Bilgisayar Bilimleri Bölümü;  (3) Marco Roveri, Trento Üniversitesi Bilgi Mühendisliği ve Bilgisayar Bilimleri Bölümü;  (4) Paolo Giorgini, Trento Üniversitesi Bilgi Mühendisliği ve Bilgisayar Bilimleri Bölümü.  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ı.    Izgaralar üç parametreyle karakterize edilir: Rastgele oluşturulmuş ızgara tabanlı ortamlar:  ı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).    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: Kişiselleştirilmiş ızgara ortamı:  •   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 konfigürasyonu:  •   Burada, içine yerleştirilebilecek tüm olası duvarları ekliyoruz. Yatay duvar uzunluğu konfigürasyonu:  ı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:  •   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. Yol maliyeti:  •   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. Bellek tüketimi:  •   Milisaniye (ms) cinsinden ölçülen, bir algoritmanın bir çözüm bulmak için harcadığı toplam süreyi (ms) temsil eder. Çözme Süresi:  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.  Bu makale   . arxiv'de CC 4.0 lisansı altında mevcuttur

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

EScholar Technologies

EScholar

Bu ses hikayenin orijinal dilinde üretilmiştir!

Çok uzun; Okumak

Make resilience your competitive advantage

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

About Author

YORUMLAR

ETİKETLERİ ASIN

BU YAZI

Related Stories

HackerNoon Kendi Ana Dilinizde 🆕 ‼️ Teknoloji Blog Yazıları için 77 Dil Ana Sayfası

AI/ML Datalake için Referans Mimarisi Oluşturmaya Yönelik Mimar Kılavuzu

Başarılı Buluta Geçiş İçin Tam Kılavuz: Stratejiler ve En İyi Uygulamalar

Kullanıcı Odaklı Kripto Ürünleri Oluşturma: Müşteri Geri Bildiriminin Önemi

HackerNoon Kendi Ana Dilinizde 🆕 ‼️ Teknoloji Blog Yazıları için 77 Dil Ana Sayfası

AI/ML Datalake için Referans Mimarisi Oluşturmaya Yönelik Mimar Kılavuzu

Başarılı Buluta Geçiş İçin Tam Kılavuz: Stratejiler ve En İyi Uygulamalar

Kullanıcı Odaklı Kripto Ürünleri Oluşturma: Müşteri Geri Bildiriminin Önemi

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps