¡¡Chinese Journal of Computers   Full Text
  TitleFast Forward Planning System Based on Delayed Partly Reasoning
  AuthorsCAI Dun-Bo1),2),3) YIN Ming-Hao1),2),3) GU Wen-Xiang3) SUN Ji-Gui1),2) LIU Ke-Cheng4)
  Address1)(College of Computer Science and Technology, Jilin University, Changchun 130012)
2)(Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Changchun 130012)
3)(College of Computer Science, Northeast Normal University, Changchun 130117)
4)(School of Foreign Languages, Northeast Normal University, Changchun 130024)
  Year2008
  IssueNo.5(793¡ª802)
  Abstract &
  Background 		Abstract 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.
Keywords AI planning£» heuristic search£» Na¢†ve components planning graph£» delayed partly reasoning
Background Artificial Intelligence planning is one of the most active topics in AI research. The aim of the group is to make AI planning methods applicable in realistic problems, specifically, intends to: (1)propose more efficient algorithms for AI planning, (2)make AI planning representation methods richer, (3)make AI planning method applicable under uncertainty environment.
They contributions to this topic now include: (1)a plan recognition algorithm that can be regarded as the counterpart of the famous classical planning system Graphplan, (2)a human-machine collaboration method that integrates plan recognition technology, (3)a causal graph based heuristic approach for conformant planning, (4)a system JLU-CD that is competitive to state-of-the-art conformant planners, (5)a planner JLU-LAO that can solve un-deterministic planning problems, (6)an efficient SAT solving algorithm based on extension rules, (7)an efficient model counting algorithm based on extension rules.
This paper focuses on planning in ADL, which is an expressive planning domain description language. A method called DPR-NCPG is introduced to deal with conditional effects for state-space planning. Experimental results show the power of the proposed method. The work is helpful in improving the efficiency of state-space based conformant and contingent planning methods.