RTTES: Real-time search in dynamic environments


Undeger C., Polat F.

APPLIED INTELLIGENCE, vol.27, no.2, pp.113-129, 2007 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 27 Issue: 2
  • Publication Date: 2007
  • Doi Number: 10.1007/s10489-006-0023-1
  • Journal Name: APPLIED INTELLIGENCE
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.113-129
  • Keywords: real-time search, path planning
  • Middle East Technical University Affiliated: Yes

Abstract

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 estimate the goal relevance of open directions in order to identify the most beneficial move. We compared RTTES with other competing real-time search algorithms and observed a significant improvement on solution quality.