実時間探索に副目標生成機構を組み込んだ実時間プラニング

概要

論文の詳細を見る
We propose a real-time planning algorithm called RTSS (Real-Time Search with Subgoaling), which incorporates the STRIPS subgoaling function into a real-time search algorithm called RTA*. This algorithm interleaves subgoaling and real-time search processes in the way that it continues to make subgoals until the subgoal becomes simple enough for an RTA*'s heuristic function, then applies RTA* to the subproblem. RTSS can overcome the drawbacks of RTA* and STRIPS in real-time problem solving, i. e., the algorithm does not lead to a blind search in contrast to the other two. RTSS includes the function of flexibly changing subgoal sequences in order to utilize information obtained during problem solving in dynamic environments. By an analysis using a simple model, we show that the search cost can be significantly reduced by switching between subgoaling and real-time search. Furthermore, experiments on robot task planning problems show that RTSS can attain the goal without performing many superfluous actions, while RTA* and STRIPS often tend to perform a blind search that fails to attain the goal.
社団法人人工知能学会の論文
1997-01-01