Fast Forward Planning System Based on Delayed Partly Reasoning
Cai Dun · Chinese Journal of Computers · 2008
Heuristic based planning becomes the main trend of AI planning and has been proven to be successful in almost every type of planning problems.High quality heuristics and effective pruning methods are two keys to such planning systems.Realizing the two techniques based on relaxed-plans was first used for the Fast-Forward(FF)planning system and is still used by current top-performing planners.Concerning the inconsistent performance of FF in ADL domains,the authors introduce a new method for extracting relaxed plans while considering the inducing relations between components and the necessity of doing confrontations that are common in ADL planning.A relaxed inducing relation between components is proposed to predict possible inducing relations in the actual planning process.Based on actions' delete effects and a simplified components planning graph,confrontations are done in the relaxed-plan-extraction phase to handle negative interactions between components.Both the improved heuristic and the improved pruning technique based on the new relaxed-plan extraction method are implemented in a system called FFc.Experimental results show FFc outperforms FF in several ADL domains in both planning efficiency and planning quality.The authors' work shows the subtleness of state space planning that handles conditional effects partially using an IPP method or factored expansion,and provides an efficient method to deal with such complicacies.