Learning where you are going and from whence you came: h- and g-cost learning in real-time heuristic search
Nathan Sturtevant, Vadim Bulitko · 2011
Real-time agent-centric algorithms have been used for learning and solving problems since the in-troduction of the LRTA * algorithm in 1990. In this time period, numerous variants have been pro-duced, however, they have generally followed the same approach in varying parameters to learn a heuristic which estimates the remaining cost to arrive at a goal state. Recently, a different ap-proach, RIBS, was suggested which, instead of learning costs to the goal, learns costs from the start state. RIBS can solve some problems faster, but in other problems has poor performance. We present a new algorithm, f-cost Learning Real-Time A * (f-LRTA*), which combines both ap-proaches, simultaneously learning distances from the start and heuristics to the goal. An empiri-cal evaluation demonstrates that f-LRTA * outper-forms both RIBS and LRTA*-style approaches in a range of scenarios. 1