Suboptimal conflict based search for multi agent path finding
Çok unsurlu yol bulma için en uyguna yakın çözümlüçatışma tabanlı arama
- Tez No: 584883
- Danışmanlar: PROF. DR. FARUK POLAT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- 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
Çok unsurlu yol bulma, bilgisayar oyunları, simülasyon yazılımları ve robotik gibi birçok alanda ka¸sıla¸sılan bir problemdir. Bu alanlar genellikle her örnek için ve gerçek zamanlı çözümlere ihtiyaç duyar. Sorunu optimum ve her örnek için çözen yöntemler, gerçek zamanlı çözümlerden çok daha fazla zaman harcamaktadır. Beklenilen zaman sınırları içerisinde çözüm bulan yöntemler ise ço˘gunlukla tüm örnekleri çözemiyor ve optimum çözümden uzaklar. Bu tezde, Conflict Based Search algoritmasını geli¸stirerek, tüm örnekler için sonuç veren ve optimum bir yöntem önerdik. Bu ¸sekilde, sahada kullanılabilecek bir algoritma geli¸stirmek için iki farklı çözüm sınıfının özelliklerini birle¸stirmi¸s olduk. Sezgisel yakla¸sım tabanlı bir yöntem kullanarak, her örnek için çalı¸san, zaman açısından verimli ve optimum çözümlere yakın sonuçlar veren bir algoritma geli¸stirdik. Yöntemimizi CBS ve optimum olmayan algoritmalarla kar¸sıla¸stırdık ve yöntemimizin avantajlarını gösterdik.
Özet (Çeviri)
Multiagent pathfinding is a problem faced in many fields including computer games, simulation software, and robotics. These applications generally require complete and real-time solutions. The class of methods which solves the problem optimally and completely spends much more time than real-time solutions. The algorithms to solve the problem within expected time limits, are mostly incomplete and do not guarantee an optimum solution. In this thesis, we proposed a method that improves the Conflict Based Search algorithm which is complete and optimum. In this way, we combined the features of two different classes of solutions to develop an algorithm that can be used in real-life problems. Using a heuristic-based approach, we developed an algorithm which is complete, time-efficient and producing near-optimal solutions. We compared our method with CBS and suboptimal algorithms experimentally and showed the advantage of our proposed method.
Benzer Tezler
- Negotiation-based decentralized conflict resolution in multi-agent path finding
Başlık çevirisi yok
CİHAN ERAN
Yüksek Lisans
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolÖzyeğin ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ REYHAN AYDOĞAN
- Interregional Relations: Perspectives on the Summit of South American-Arab Countries 'New' patterns of engagement
Bölgelerarasi ilişkiler: Güney Amerika - Arap Ülkeleri zirvesindeki“Yeni”angajman yapısı perspektifleri
MARSHA MARİE HALL
Yüksek Lisans
İngilizce
2015
Uluslararası İlişkilerOrta Doğu Teknik ÜniversitesiOrtadoğu Araştırmaları Ana Bilim Dalı
PROF. DR. MELİHA BENLİ ALTUNIŞIK
DOÇ. DR. DERYA GÖÇER AKDER
- Why Clinical Practice Guidelines Shift Over Time:A Dynamic Model with Application to Prostate Cancer Screening
Klinik Uygulama Kılavuzları Neden Zaman İçinde Değişiyor: Prostat Kanseri Taramasına Yönelik Dinamik Bir Simulasyon Modeli
ÖZGE KARANFİL
Doktora
İngilizce
2016
İşletmeMassachusetts Instıtute Of Technologyİşletme Ana Bilim Dalı
PROF. DR. JOHN DAVİD STERMAN
- A performance based decision-making approach for insulation material selection: A social housing case
Yalıtım malzemesi seçiminde performans odaklı bir karar verme yöntemi: Sosyal konut örneği
BURCU ÇİĞDEM ÇELİK
Doktora
İngilizce
2018
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
DOÇ. SEDEN ACUN ÖZGÜNLER