Single and multi agent real-time path search in dynamic and partially observable environments

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2007

Öğrenci: ÇAĞATAY ÜNDEĞER

Danışman: FARUK POLAT

Özet:

In this thesis, we address the problem of real-time path search in partially observable 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 the closed directions around the agent by analyzing the nearby obstacles, thus avoiding dead-ends in order to reach a static target more effectively. We compared RTEF with a well-known algorithm, Real-Time A* (RTA*) proposed by Korf, and observed significant improvement. The second algorithm, Real-Time Moving Target Evaluation Search (MTES), is also able to detect the closed directions similar to RTEF, but in addition, determines the estimated best direction that leads to a static or moving target from a shorter path. Employing this new algorithm, we obtain an impressive improvement over RTEF with respect to path length, but at the cost of extra computation. We compared our algorithms with Moving Target Search (MTS) developed by Ishida and the off-line path planning algorithm A*, and observed that MTES performs significanlty better than MTS, and offers solutions very close to optimal ones produced by A*. Finally, we present Multi-Agent Real-Time Pursuit (MAPS) for multiple predators to capture a moving prey cooperatively. MAPS introduces two new coordination strategies namely Blocking Escape Directions (BES) and Using Alternative Proposals (UAL), which help the predators waylay the possible escape directions of the prey in coordination. We compared our coordination strategies with the uncoordinated one, and observed an impressive reduction in the number of moves to catch the prey.