Title | Improving Convergence of LRTA*(k) |
Publication Type | Conference Paper |
Year of Publication | 2005 |
Authors | Hernández C, Meseguer P |
Editor | Bulitko V, Koenig S |
Conference Name | Proceedings of the IJCAI 2005 Workshop on Planning and Learning in a Priori Unknown or Dynamic Domains |
Pagination | 69 - 75 |
Abstract | LRTA* is a real-time heuristic search algorithm widely used. In each iteration it updates the heuristic estimate of the current state. In this paper, we present three versions of LRTA*(k), a new LRTA*- based algorithm that is able to update the heuristic estimates of up to k states, not necessarily distinct. Based on bounded propagation, this updating strategy maintains heuristic admissibility, so LRTA*(k) keeps the good theoretical properties of LRTA*. The new algorithm produces better solutions in the first trial and converges faster when compared with other state-of-the-art algorithms on classical benchmarks for real-time search. We provide experimental evidence of the improvement in performance of these versions, at the extra cost of longer planning steps |