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

Download

index.pdf

Date

2007

Author

Ündeğer, Çağatay

Metadata

Show full item record

Item Usage Stats

222
views

139
downloads

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.

Subject Keywords

Computer Engineering., Path Planning.

URI

http://etd.lib.metu.edu.tr/upload/12608158/index.pdf
https://hdl.handle.net/11511/17246

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Real-time edge follow: A real-time path search approach Undeger, Cagatay; Polat, Faruk (2007-09-01) Real-time path search is the problem of searching a path from a starting point to a goal point in real-time. In dynamic and partially observable environments, agents need to observe the environment to track changes, explore to learn unknowns, and search suitable routes to reach the goal rapidly. These tasks frequently require real-time search. In this paper, we address the problem of real-time path search for grid-type environments; we propose an effective heuristic method, namely a real-time edge follow al...
Optimization of well placement in complex carbonate reservoirs using artifical intelligence Uraz, İrtek; Akın, Serhat; Department of Petroleum and Natural Gas Engineering (2004) This thesis proposes a framework for determining the optimum location of an injection well by using an inference method, Artificial Neural Networks and a search algorithm to create a search space and locate the global maxima. Theoretical foundation of the proposed framework is followed by description of the field for case study. A complex carbonate reservoir, having a recorded geothermal production history is used to evaluate the proposed framework ( Kizildere Geothermal field, Turkey). In the proposed fram...
Video Shot Boundary Detection by Graph-theoretic Dominant Sets Approach Asan, Emrah; Alatan, Abdullah Aydın (2009-09-16) We present a video shot boundary detection algorithm based on the novel graph theoretic concept, namely dominant sets. Dominant sets are defined as a set of the nodes in a graph, mostly similar to each other and dissimilar to the others. In order to achieve this goal, candidate shot boundaries are determined by using simply pixelwise differences between consequent frames. For each candidate position, a testing sequence is constructed by considering 4 frames before the candidate position and 2 frames after t...
RTTES: Real-time search in dynamic environments Undeger, Cagatay; Polat, Faruk (Springer Science and Business Media LLC, 2007-10-01) In this paper we propose a real-time search algorithm called Real-Time Target Evaluation Search (RTTES) for the problem of searching a route in grid worlds from a starting point to a static or dynamic target point in real-time. The algorithm makes use of a new effective heuristic method which utilizes environmental information to successfully find solution paths to the target in dynamic and partially observable environments. The method requires analysis of nearby obstacles to determine closed directions and...
Dielectric function of the two-dimensional electron liquid: An analytical fitting Bulutay, C; Tomak, Mehmet (1996-03-15) For electron-electron interactions in two-dimensional electronic systems the technique proposed by Singwi, Tosi, Land, and Sjolander (STLS) has been very promising. In this work, after showing the asymptotic behavior of the STLS local held correction we propose a simple expression for the local-held correction that contains two fitting parameters which are smoothly varying functions of the electronic density. The agreement of the fitting for the pair correlation function is remarkable. It further leads to a...

Citation Formats

Ç. Ündeğer, “Single and multi agent real-time path search in dynamic and partially observable environments,” Ph.D. - Doctoral Program, Middle East Technical University, 2007.