Real-Time planning by interleaving real-time search with subgoaling

摘要

Recently, real-time planning has been actively studied for solving problems in uncertain and dy-namic environments. RTA * is a real-time search algorithm that can provide a computational ba-sis for real-time planning. However, RTA * is not always efficient since obtaining effective heuristic functions is difficult when the problem becomes complicated. In order to keep the problem sim-ple enough for efficient search, we propose an algorithm called RTSS, which incorporates the STRIPS subgoaling function into RTA*. This algorithm interleaves subgoaling and real-time search processes by evaluating the goal complex-ity and the ease of operator execution. An anal-ysis using a simple model shows that the search cost can be significantly reduced by switching be-tween subgoaling and real-time search. Further-more, experiments on a robot task planning prob-lem show that RTSS can attain the goal without performing many superfluous actions, while other algorithms often tend to perform a blind search that hils to attain the goal.