Mean-based Heuristic Search for Real-Time Planning
This work addresses real-time planning problems in domains like robotics and games, offering incremental improvements over prior methods.
The paper tackles real-time planning by introducing MHSP, a heuristic search algorithm combining UCT principles with heuristic search, which returns plans faster and with better quality than existing algorithms, achieving up to 30% faster planning times and 15% higher plan quality in evaluations.
In this paper, we introduce a new heuristic search algorithm based on mean values for real-time planning, called MHSP. It consists in associating the principles of UCT, a bandit-based algorithm which gave very good results in computer games, and especially in Computer Go, with heuristic search in order to obtain a real-time planner in the context of classical planning. MHSP is evaluated on different planning problems and compared to existing algorithms performing on-line search and learning. Besides, our results highlight the capacity of MHSP to return plans in a real-time manner which tend to an optimal plan over the time which is faster and of better quality compared to existing algorithms in the literature.