Matthew L. Ginsberg
This paper makes two linked contributions. First, we argue that planning systems, instead of being correct (every plan returned achieves the goal) and complete (all such plans are returned), should bc approximately correct and complete, in that most plans returned achieve the goal and that most such plans are returned. Our first contribution is to formalize this notion. Our second aim is to demonstrate the practical importance of these ideas. We argue that the cached plans used by case-based planners are best thought of as approximate as opposed to exact, and also show that we can use our approach to plan for subgoals g1 and g2 separately and to combine the plans generated to produce a plan for the conjoined goal g1 ^ g2. The computational benefits of working with subgoals separately have long been recognized, but attempts to do so using correct and complete planners have failed.