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: Belirtilmemiş.
- 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ı: 124
Ö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
- IQ-flow: Mechanism design for inducing cooperative behavior to self-interested agents in sequential social dilemmas
TQ-akışı: Ardışıl sosyal ikilemlerdeki çıkarcı etmenleri işbirlikçi davranışa teşvik etmek için mekanizma tasarımı
BENGİSU GÜRESTİ
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. NAZIM KEMAL ÜRE
- 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
- Türkiye'nin covıd-19 pandemisi ile mücadelesinde karantina yönetimi ve kolluğun rolü
The role of quarantine management and law enforcement in Turkey's fight against the covid-19 pandemic
SULTANGÜL ÖZSOY
Yüksek Lisans
Türkçe
2022
Kamu YönetimiJandarma ve Sahil Güvenlik AkademisiKamu Yönetimi Ana Bilim Dalı
DOÇ. DR. TEKİN AVANER
- Çizge ve içerik verilerinde kolektif sınıflandırma algoritmalarının karşılaştırılması
A comparison of collective classification techniques on network and content data
ÖZGE ATASEVEN
Yüksek Lisans
Türkçe
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. YUSUF YASLAN