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


Undeger C., Polat F.

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART C-APPLICATIONS AND REVIEWS, cilt.37, ss.860-872, 2007 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 37 Konu: 5
  • Basım Tarihi: 2007
  • Doi Numarası: 10.1109/tmscc.2007.900663
  • Dergi Adı: IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART C-APPLICATIONS AND REVIEWS
  • Sayfa Sayıları: ss.860-872

Özet

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.