Speeding up learning in real-time search via automatic state abstraction
Vadim Bulitko, Nathan Sturtevant, Maryia Kazakevich · 2005
Situated agents which use learning real-time search are well poised to address challenges of real-time path-finding in robotic and computer game applications. They interleave a local lookahead search with movement execution, explore an initially unknown map, and converge to better paths over re-peated experiences. In this paper, we first investigate how three known extensions of the most popular learning real-time search algorithm (LRTA*) influence its performance in a path-finding domain. Then, we combine automatic state ab-straction with learning real-time search. Our scheme of dy-namically building a state abstraction allows us to generalize updates to the heuristic function, thereby speeding up learn-ing. The novel algorithm converges up to 80 times faster than LRTA * with only one fifth of the response time of A*.