Artımlı Çoklu Etmen Güzergah Planlama

Date

2023-1-05

Author

Polat, Faruk

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

26
views

39
downloads

Cite This

Çoklu etmenler için yol bulma (İng. Multi-Agent Path Finding--MAPF), birden fazla etmen için birbirleriyle çatışmayacakları yolların bulunması problemidir: verilen bir çizgede (İng. graph), her bir etmen için belirtilen bir başlangıç düğümünden (İng. vertex) bir hedef düğüme yol belirlenmesi ve etmen yollarının birbiri ile çatışmaması (aynı zamanda aynı düğümde birden fazla etmen olmaması) ve etmenlerin toplam yol uzunluklarının minimal olması gerekmektedir. MAPF olarak tanımlanan bu problem, klasik robotik rota planlama problemlerinden farklı olarak, bir yapay zeka planlama problemidir. Bu problem robotların fiziksel düzeyde nasıl hareket edeceğine değil robotun verilen ortam (harita) üzerinde nasıl hareket edeceği üzerinde çalışmalara odaklanır (Ma ve Koenig, 2017). Problemdeki bu sadeleştirme, etmenlerin bu problemin uygulamaları daha çok ızgara tabanlı (İng. grid based) ve dar koridorlar içeren problemler olduğu için problem tanımına uymakta ve klasik robot problemlerine oranla çok daha fazla sayıda etmen ve hedef nokta içeren engellerin fazla olduğu problemlerin oldukça hızlı çözülebilmesini sağlamaktadır (Stern, 2019; Stern vd. 2019). MAPF probleminin gerçek dünya uygulamaları olarak depo yönetimi (Amazon Kiva robotları, Alibaba Quicktrone robotları, Karis robotları) (Hönig vd, 2019b; Dasler ve Mount, 2019; Stenzel ve Luensch, 2016) ve otonom römorkör robotlar (NASA - Ames projesi) (Morris vd., 2016) verilebilir. MAPF çözüm uzayının etmen sayısına bağlı olarak üstel olarak büyüdüğü zor bir problemdir (Yu ve LaValle, 2013b; Hönig vd., 2016). Çatışma tabanlı arama (İng. Conflict-Based Search--CBS) günümüzde MAPF problemini çözmek için kullanılan en etkili tekniklerden birisidir ve bir çözüm varsa bulmayı garanti eder (tam) ve optimal çözüm üretir. Gerçek hayat problem gereksinimleri dikkate alındığında mevcut MAPF algoritmaları yetersiz kalmaktadır ve MAPF problem tanımlarının genişletilmesi gerekmektedir: bunlar i) ortamdaki değişimler, ii) birden fazla hedef noktasına sahip etmenlerin olması, ve iii) yeni görevlerin eklenebilmesi olarak ortaya konulabilir. CBS, alt seviyede tek etmen yol planlaması için A* kullanması sebebiyle dinamik ortamlar için yetersiz kalmaktadır. Zira her bir çevresel değişimden sonra CBS'in etmen yollarını baştan hesaplaması gerekir ve üst seviyede planlayıcının kullandığı kısıt ağacını (İng. Conflict Tree--CT) baştan oluşturmak masraflıdır. Bu projede, çevresel değişimlerden sonra hızlıca yeni planlar oluşturabilmek için, projenin ilk aşamasında artımlı (İng. incremental) bir tek etmenli yol bulma algoritmasının geliştirilerek üst seviye planlayıcıya adapte edilmesi ve CBS algoritmasının genişletilmesi amaçlanmıştır. İkinci aşamada, her bir etmenin birden fazla düğüme uğraması gerektiği problem için düşük maliyetli bir çözüm geliştirilmiştir. Son aşamada sisteme eklenen her bir yeni görev için o görevin hangi etmene atanacağına ve o görevin ne zaman yapılması gerektiğine karar verilmiştir. Bunu yapabilmek için birçok sezgisel görev atama algoritması oluşturulup onlardan en düşük maliyet artışı gerektiren belirlenmiştir. Her aşamada geliştirilen algoritmanın testi için rastgele üretilmiş senaryolar ve literatürde kullanılmakta olan referans çizgeler kullanılmıştır. Geliştireceğimiz artımlı MAPF ile çevresel değişimlerin olduğu senaryolarda CBS?den (literatürde bilinen dinamik olmayan MAPF problemi için en hızlı çözücülerdendir) çok hızlı sonuç üretmeyi ve optimal planlamadan en fazla yüzde 10 sapmaya erişmiş bulunmaktayız. Arama tabanlı, artımlı MAPF algoritması ve çoklu hedef içeren ve yeni görevlerin de eklenebilir olduğu etkili bir MAPF problemi çözümü ile MAPF konusunda önemli bir eksikliğin giderilmesi sağlanmış olup yapay zeka alanında önemli bir temel araştırma alanına katkı sağlanmıştır. Uygulama açısından, otonom depo paket dağıtım problemlerinin gereksinimlerini karşılayacak daha etkili ve verimli bir sistem geliştirilmiştir.

Subject Keywords

Çoklu etmen sistemleri, Çoklu etmen yol bulma

URI

https://search.trdizin.gov.tr/tr/yayin/detay/1223444/artimli-coklu-etmen-guzergah-planlama
https://hdl.handle.net/11511/113778

Collections

Department of Computer Engineering, Project and Design