Generalizations of multi-agent path finding problem for incremental environments
Çok etmenli yol bulma probleminin artımlı ortamlar için genelleştirmeleri
- Tez No: 748675
- Danışmanlar: PROF. DR. FARUK POLAT
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Kılavuzlu arama, Yaşam boyu öğrenme, Yol bulma, Heuristic search, Lifelong learning, Way finding
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Ö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.
Özet (Çeviri)
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.
Benzer Tezler
- Wind-optimized route planning with deep reinforcement learning
Derin pekiştirmeli öğrenme ile rüzgar optimizasyonlu rota planlaması
MELİH SAFA CENGİZ
Yüksek Lisans
İngilizce
2025
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
DOÇ. DR. BARIŞ BAŞPINAR
- State and civil society relation in Türkiye: The case of women csos
Türkiye'de Devlet ve sivil toplum ilişkisi: Kadın örgütleri örneği
TUNA YÜCEL
Yüksek Lisans
İngilizce
2025
SosyolojiOrta Doğu Teknik ÜniversitesiSosyal Politika Ana Bilim Dalı
DOÇ. DR. AYÇA ERGUN ÖZBOLAT
- Energy management of smart grid based on multi agent system and reinforcement learning
Çok ajanlı sistem ve takviye öğrenimine dayalı akıllı şebeke enerji yönetimi
ALI ABDULHASAN SALMAN AL-SAADI
Yüksek Lisans
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAltınbaş ÜniversitesiFen Bilimleri Ana Bilim Dalı
YRD. DOÇ. DR. OĞUZ KARAN
- Multi agent reinforcement learning using function approximation
Fonksiyon yaklaşımı kullanarak çoklu etmen takviye öğrenme
OSMAN ABUL
Yüksek Lisans
İngilizce
1999
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. FARUK POLAT
- Dört rotorlu insansız hava araçları için fizik rehberli artık geri beslemeli sinir ağı ile çok ajanlı dağıtılmış lineer olmayan model öngörülü formasyon kontrolü
Multi-agent distributed nonlinear model predictive formation control for quadrotor UAVs using a physics-guided residual feedback neural network
DENİZ MUHACİR
Yüksek Lisans
Türkçe
2026
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
PROF. DR. YAPRAK YALÇIN