Real-time edge follow: A real-time path search approach

Date

2007-09-01

Author

Undeger, Cagatay
Polat, Faruk

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

212
views

0
downloads

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 alternative reduction method (RTEF-ARM), which makes use of perceptual information in a real-time search. We developed several heuristics powered by the proposed method. Finally, we generated various grids (random-, maze-, and U-type), and compared our proposal with real-time A*, and its extended version real-time A* with n-look-ahead depth; we obtained very significant improvements in the solution quality.

Subject Keywords

Path planning, Real-time heuristic search

URI

https://hdl.handle.net/11511/37615

Journal

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART C-APPLICATIONS AND REVIEWS

DOI

https://doi.org/10.1109/tmscc.2007.900663

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

Single and multi agent real-time path search in dynamic and partially observable environments Ündeğer, Çağatay; Polat, Faruk; Department of Computer Engineering (2007) 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 improvemen...
Real-Time Moving Target Search Undeger, Cagatay; Polat, Faruk (2007-11-23) In this paper, we propose a real-time moving target search algorithm for dynamic and partially observable environments, modeled as grid world. The proposed algorithm, Real-time Moving Target Evaluation Search (MTES), is able to detect the closed directions around the agent, and determine the best direction that avoids the nearby obstacles, leading to a moving target which is assumed to be escaping almost optimally. We compared our proposal with Moving Target Search (NITS) and observed a significant improvem...
Generalizations of multi-agent path finding problem for incremental environments Semiz, Fatih; Polat, Faruk; Department of Computer Engineering (2022-7-20) Multi-Agent Path Finding problem (MAPF) is finding a path for multiple agents from a list of starting locations to a list of goal locations in such a way that the agents’ routes do not pass through the same location at the same time. The problem occurs in real-world during the transporting packages in warehouse environments with robots moving on rails, cleaning closed areas with cleaning robots, and protecting areas with multiple robots etc. It is usually sufficient to use discrete maps to express these pro...
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...
Quantum Search in Sets with Prior Knowledge Çalıkyılmaz, Umut; Turgut, Sadi; Department of Physics (2021-10-7) Quantum search algorithm revolutionized the field by reducing the complexity significantly for the search problem. However, by not being able to decrease the complexity to logarithmic scales, this algorithm still needs a significant amount of time to solve the search problem for large sets. It is proven that the order of the time required to solve this problem cannot be reduced further but, making an improvement by some constant factor is still possible. This aim has been pursued by some scientists in the p...

Citation Formats

C. Undeger and F. Polat, “Real-time edge follow: A real-time path search approach,” IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART C-APPLICATIONS AND REVIEWS, pp. 860–872, 2007, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/37615.