Real-Time Planning by Interleaving Real-Time Search with Subgoaling

Shigeo Matsubara and Toru Ishida

Recently, real-time planning has been actively studied for solving problems in uncertain and dynamic environments. RTA* is a real-time search algorithm that can provide a computational basis 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 simple 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 complexity and the ease of operator execution. An analysis using a simple model shows that the search cost can be significantly reduced by switching between subgoaling and real-time search. Furthermore, experiments on a robot task planning problem show that RTSS can attain the goal without performing many superfluous actions, while other algorithms often tend to perform a blind search that fails to attain the goal.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.