Anytime replanning using local subplan replacement

摘要

Planning is a very hard problem in general. Many interesting planning problems are NP-Complete, PSPACE-Complete, or undecidable. Furthermore, in the context of a planner being used to control a robot, events beyond the control of the robot may occur that cause its plan to fail. When a plan fails, it is necessary to devise a new plan that accommodates the exogenous event or events that caused the old plan to fail. This new plan must be devised in a timely manner. Anytime planners seek to allow the system to exchange execution time for solution quality. I have analyzed how local subplan replacement can be utilized to implement an anytime planning system that devises new plans to accommodate plan failures. Local subplan replacement consists of selecting subsequences of operators centered around failure points and replacing them with new subsequences of higher quality. The key idea behind local subplan replacement is that it utilizes the results of the search process that produced the original plan in order to guide the search for a new plan. An anytime planning algorithm requires two key components: the rapid generation of an initial plan and a means for establishing a progression of improved plans. Local subplan replacement begins by quickly repairing the flaws in the original plan. This results in a plan that achieves all of its goals, but may be of low quality. Local subplan replacement is then used to improve the quality of the plan. At low subplan levels, short subplans are replaced. These replacements are generated relatively quickly. At higher subplan levels, longer subplans are replaced. This requires more time, but results in plans of higher overall quality. My experimental results demonstrate that utilizing the results of the earlier search process is effective for organizing anytime planning. I also describe some theoretical and practical limitations of this approach and suggest directions for further research.