Real-time search algorithms determine the next move of the problem solver in a constant time and execute that move immediately. The problem solver eventually reaches the goal by repeating the cycle of planning and execution. Real-time search algorithms have some learning ability. For example, through repeated trials of LRTA, a wellknown real-time search algorithm, the estimated distances converge to the exact distances along the optimal path. In the earlier work on real-time search algorithms, however, the efficiencies of a single problem solving trial have been investigated. The purpose of this paper is to evaluate the learning efficiencies of multiple problem solving trials. The major obtained results are as follows. 1) The learning efficiencies of RTA and LRTA are first compared. When solving a problem once, RTA is superior to LRTA. When the problem is solved many times, however, LRTA becomes more efficient. 2) The learning efficiencies of different heuristic functions are then compared. In off-line search, more informative heuristic functions result more efficient problem solving performance. In real-time search, however, more informative heuristic functions improve the efficiency of the convergence through multiple problem solving processes. 3) Finally, the learning efficiencies of LRTA and LCM, the extension of LRTA to perform the locally optimal decisions, are examined. Compared with LRTA, LCM needs less execution time and more planning time. Namely there exists a trade-off between execution and planning.