A weighted CSP approach to cost-optimal planning

作者：Cooper Martin C^*; de Roquemaurel Marie; Regnier Pierre

来源：AI Communications, 2011, 24(1): 1-29.

DOI：10.3233/AIC-2010-0473

• Optimal planning
• planning graph
• soft constraints
• soft arc consistency

For planning to come of age, plans must be judged by a measure of quality, such as the total cost of actions. This paper describes an optimal-cost planner which guarantees global optimality whenever the planning problem has a solution.
We code the extraction of an optimal plan, from a planning graph with a fixed number k of levels, as a weighted constraint satisfaction problem (WCSP). The specific structure of the resulting WCSP means that a state-of-the-art exhaustive solver was able to find an optimal plan in planning graphs containing several thousand nodes.
Thorough experimental investigations demonstrated that using the planning graph in optimal planning is a practical possibility for problems of moderate size, although not competitive, in terms of computation time, with optimal state-space-search planners. Our general conclusion is, therefore, that planning-graph-based optimal planning is not the most efficient method for cost-optimal planning.
Nonetheless, the notions of indispensable (sets of) actions and too-costly actions introduced in this paper have various potential applications in optimal planning. These actions can be detected very rapidly by analysis of the relaxed planning graph.

• 出版日期2011