Tez No	İndirme	Tez Künye	Durumu
748675		Generalizations of multi-agent path finding problem for incremental environments / Çok etmenli yol bulma probleminin artımlı ortamlar için genelleştirmeleri Yazar:FATİH SEMİZ Danışman: PROF. DR. FARUK POLAT Yer Bilgisi: Orta Doğu Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Kılavuzlu arama = Heuristic search ; Yaşam boyu öğrenme = Lifelong learning ; Yol bulma = Way finding	Onaylandı Doktora İngilizce 2022 124 s.
Ç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.
Multi-Agent Path Finding problem (MAPF) is finding a path for multiple agents from a list of starting locations to a list of goal locations in such a way that the agents' routes do not pass through the same location at the same time. The problem occurs in real-world during the transporting packages in warehouse environments with robots moving on rails, cleaning closed areas with cleaning robots, and protecting areas with multiple robots etc. It is usually sufficient to use discrete maps to express these problems. However, unlike the standard MAPF setting, in these problems there may be a need to replan agent paths while the movement of the agents continues. The need to replan agent paths may be due to the following reasons: packages falling on the road, passing of external vehicles, or new tasks added to the problem while the problem continues. Such situations can be better expressed with an incremental MAPF problem structure. In this thesis, we describe a MAPF variation where certain nodes on the map become temporarily impassable. We have created methods that effectively solve this problem definition and have proven through many experiments that they are effective solutions. We also defined a MAPF problem variation in which agents have multiple destinations in the lifelong MAPF problem structure. We have developed a new algorithm that solves the MAPF problem involving multiple destinations. For the task allocation problem, we created heuristic methods to minimize the total amount of travelled paths, and we tested these methods with many experiments and analyzed their performance.