Tez No	İndirme	Tez Künye	Durumu
198835		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 Yazar:ÇAĞATAY ÜNDEĞER 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 ; Mühendislik Bilimleri = Engineering Sciences Dizin:	Onaylandı Doktora İngilizce 2007 138 s.
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 hedefi 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 oAnahtar Kelimeler: Yol Planlama, Gerşek Zamanlı Arama, Coklu Etmen Kovalamac şvii
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 first 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 effectively. We compared RTEFwith a well-known algorithm, Real-Time A* (RTA*) proposed by Korf, and observedsignificant 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 off-linepath planning algorithm A*, and observed that MTES performs significantly betterthan MTS, and offers 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.Keywords: Path Planning, Real-Time Search, Multi-Agent Pursuitv