Generalizations of multi-agent path finding problem forincremental environments

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Fen Bilimleri Enstitüsü, BİLGİSAYAR MÜHENDİSLİĞİ ANABİLİM DALI, Türkiye

Tezin Onay Tarihi: 2022

Tezin Dili: İngilizce

Öğrenci: FATİH SEMİZ

Danışman: FARUK POLAT

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Çoklu Etmenler için Yol Bulma problemi (MAPF) gerçek dünyada da örnekleri olan ve bilgisayar bilimleri alanında sıklıkla çalışılan bir problemdir. Amacı birden çok etmen için onların başlangıç noktalarından bitiş noktalarına etmenlerin rotaları aynı anda aynı lokasyondan geçmeyecek şekilde yol bulmaktır. Gerçek dünya problemlerine örnek olarak ray üzerinde hareket eden robotlar ile depo ortamlarında paket taşınması, kapalı alanların temizlik robotları ile temizlenmesi, alanların çoklu robotlar ile korunması gibi problemler verilebilir. Bu problemleri ifade etmek için sayısal haritalar kullanmak genelde yeterli olabilmektedir. Ancak bu problemler standart MAPF senaryolarının aksine yola paketlerin düşmesi, harici araçların geçmesi veya problem devam ederken probleme yeni işler eklenmesi gibi durumlardan dolayı etmenlerin hareketi devam ederken yeniden planlama yapmaya ihtiyaç duyabilir. Bu gibi durumlar artımlı bir MAPF problem yapısı ile daha iyi ifade edilebilir. Bu tez çalışmasında haritadaki belli düğümlerin geçici bir süre geçilemez hale geldiği bir MAPF varyasyonu tanımladık. Bu problem tanımını etkili bir şekilde çözen yöntemler oluşturduk ve onların etkili çözümler olduklarını birçok deney ile kanıtladık. Ayrıca hayat boyu MAPF problem yapısında etmenlerin birden fazla hedef noktasına sahip olduğu bir MAPF problemi tanımladık. Birden fazla hedef noktasına sahip etmenler içeren MAPF problemini çözen yeni bir algoritma geliştirdik. İş dağıtımı problemi için de toplam gezilen yol miktarını minimize etmeye yönelik sezgisel yöntemler oluşturduk ve bu yöntemleri birçok deney ile test ederek performanslarını analiz ettik.