Single and multi agent real-time path search in dynamic and partially observable environments
Değişken ve kısmi gözlemlenebilir ortamlarda tek ve çoklu etmen gerçek zamanlı yol arama
- Tez No: 198835
- Danışmanlar: PROF. DR. FARUK POLAT
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Mühendislik Bilimleri, Computer Engineering and Computer Science and Control, Engineering Sciences
- Anahtar Kelimeler: Yol Planlama, Gerşek Zamanlı Arama, Coklu Etmen Kovalamac şvii, Path Planning, Real-Time Search, Multi-Agent Pursuitv
- Yıl: 2007
- 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ı: 138
Özet
Bu tezde, kısmen güzlemlenebilir ızgara dünyalardaki gerşek zamanlı yol aramao u cproblemi işin iki farklı tek etmenli ve bir coklu etmenli arama algoritması onerilmekte-c ş üdir.ËIlk algoritma olan Real-Time Edge Follow (RTEF), sabit bir hedefe daha etkinşekilde ulaşabilmek işin yakında bulunan engelleri analiz ederek etmenin cevresindekis s c şkapalı yünleri tespit edebilme, dolayısıyla cıkmaz sokaklardan sakınabilme kabiliyetineo şsahiptir. RTEF'in performansını güsterebilmek işin Korf tarafından onerilen Real-o c üTime A* (RTA*) dikkate alınmış olup, yapılan deneysel calışma sonucunda dikkates şsdeğer bir iyileşme güzlemlenmiştir.g s o sËIkinci algoritma olan Real-Time Moving Target Evaluation Search (MTES) deRTEF gibi kapalı yünleri tespit edebilmekte, ancak ek olarak, sabit veya hareketliobir hedefe en kısa yoldan giden rotayı daha doğru olarak tahmin edebilmektedir. Ekghesaplama maliyeti olsa da, bu yeni algoritma ile RTEF'e karşı yol uzunluğu aşısındans gcüetkileyici bir iyileşme elde edilmiştir. Onerilen algoritmalar, Ishida tarafından geliştiri-s s slen Moving Target Search (MTS) ve cevrim dışı yol planlama algoritması A* ile testş sedildi ve MTES'in MTS'den cok daha iyi performans güsterdiği ve A* tarafındanş o gsağlanan en iyi cüzü mlere şok yakın sonuşlar sunduğu güzlemlendi.g şo u c c goSon olarak, birden fazla avcı ile hareketli bir hedeï¬ kordineli şekilde kovalama ka-svibiliyetine sahip bir coklu etmen yol arama algoritması olan Multi-Agent Real-TimeşPursuit (MAPS) geliştirilmiştir. MAPS, avın muhtemel kaşış yünlerini avcıların ko-s s cs oordineli olarak kesebilmesine yardımcı olan Kaşış Yünlerini Kapama (BES) ve Alter-cs oünatif Onerileri Kullanma (UAL) olarak isimlendirilen iki yeni koordinasyon stratejisiükullanmaktadır. Onerilen bu stratejiler, koordinasyonsuz olanla mukayese edildi veavı yakalama adım sayılarında carpıcı bir iyileşme güzlemlendi.ş s o
Özet (Çeviri)
In this thesis, we address the problem of real-time path search in partially observ-able grid worlds, and propose two single agent and one multi-agent search algorithm.The ï¬rst algorithm, Real-Time Edge Follow (RTEF), is capable of detecting theclosed directions around the agent by analyzing the nearby obstacles, thus avoidingdead-ends in order to reach a static target more eï¬ectively. We compared RTEFwith a well-known algorithm, Real-Time A* (RTA*) proposed by Korf, and observedsigniï¬cant improvement.The second algorithm, Real-Time Moving Target Evaluation Search (MTES), isalso able to detect the closed directions similar to RTEF, but in addition, determinesthe estimated best direction that leads to a static or moving target from a shorterpath. Employing this new algorithm, we obtain an impressive improvement over RTEFwith respect to path length, but at the cost of extra computation. We compared ouralgorithms with Moving Target Search (MTS) developed by Ishida and the oï¬-linepath planning algorithm A*, and observed that MTES performs signiï¬cantly betterthan MTS, and oï¬ers solutions very close to optimal ones produced by A*.Finally, we present Multi-Agent Real-Time Pursuit (MAPS) for multiple predatorsto capture a moving prey cooperatively. MAPS introduces two new coordinationstrategies namely Blocking Escape Directions (BES) and Using Alternative Proposals(UAL), which help the predators waylay the possible escape directions of the prey inivcoordination. We compared our coordination strategies with the uncoordinated one,and observed an impressive reduction in the number of moves to catch the prey.
Benzer Tezler
- Multi-objective path planning for virtual environments
Sanal ortamlar için çok hedefli yol planlama
TUĞCEM ORAL
Yüksek Lisans
İngilizce
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. FARUK POLAT
- Path-connecting multi-agent real-time A-star search
Patika birleştirmeli çoklu-ajan gerçek zamanlı A-yıldız arama
MUSTAFA KEMAL KAPLAN
Yüksek Lisans
İngilizce
2001
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. FARUK POLAT
- Oyun motorlarında güzergah belirleme
Routing in game engines
ABDULKADİR BAYTİMUR
Yüksek Lisans
Türkçe
2021
Bilim ve Teknolojiİstanbul Teknik ÜniversitesiBilişim Uygulamaları Ana Bilim Dalı
DOÇ. DR. CANER GÜNEY
- Multicolor fluorescence microscopy fortracking magnetic micro-agents
Başlık çevirisi yok
MERT KAYA
Doktora
İngilizce
1989
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolUniversity of TwentePROF. DR. SARTHAK MİSRA
- MAPDC: Multi-agent pick and delivery with capacities
Kapasiteli çok etmenli toplama ve dağıtma problemi
ÇAĞRI ULUÇ YILDIRIMOĞLU
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı ÜniversitesiBilgisayar Bilimleri Ana Bilim Dalı
PROF. DR. ESRA ERDEM