New Strategies in Learning Real Time Heuristic Search
Stefan Edelkamp, Jiirgen Eckerle · 1997
In contrast to o#-line search algorithms suchasA # and IDA # , in real-time heuristic searchwehave to commit amove within a limited search horizon or time. One well known algorithm in this class is RTA # . An algorithm is said to learn if it improves its performance over successive problem trials. In RTA # the heuristic estimation is in general not admissible. Thus RTA # has to be modi#ed to a variant LRTA # that is capable of learning. The aim of the strategies proposed in this paper is to improve the estimations found in LRTA # . First, we examine two new schemas forward updating and backward updating for LRTA # . Then we propose CRTA # whichworks similar to RTA # but terminates with admissible heuristic values. It is shown that the strategy used in CRTA # can be made e#ciently. Combined with lazy evaluation updating CRTA # leads to an improved real time learning algorithm called SLRTA # . Experimentally we show that CRTA # expands signi#cantly less nodes than LRTA # and thus converges faster to the optimal values.