A weighted CSP approach to cost-optimal planning

被引:8
作者
Cooper, Martin C. [1 ]
de Roquemaurel, Marie [1 ]
Regnier, Pierre [1 ]
机构
[1] Univ Toulouse 3, IRIT, F-31062 Toulouse, France
关键词
Optimal planning; planning graph; soft constraints; soft arc consistency; CONSTRAINT SATISFACTION; ARC CONSISTENCY; COMPLEXITY; SEARCH; GRAPH;
D O I
10.3233/AIC-2010-0473
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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.
引用
收藏
页码:1 / 29
页数:29
相关论文
共 75 条
[1]  
[Anonymous], HDB CONSTRAINT PROGR
[2]  
[Anonymous], 2005, ICAPS
[3]   DOWNWARD REFINEMENT AND THE EFFICIENCY OF HIERARCHICAL PROBLEM-SOLVING [J].
BACCHUS, F ;
YANG, Q .
ARTIFICIAL INTELLIGENCE, 1994, 71 (01) :43-100
[4]   Fast planning through planning graph analysis [J].
Blum, AL ;
Furst, ML .
ARTIFICIAL INTELLIGENCE, 1997, 90 (1-2) :281-300
[5]   Planning as heuristic search [J].
Bonet, B ;
Geffner, H .
ARTIFICIAL INTELLIGENCE, 2001, 129 (1-2) :5-33
[6]  
BONET B, 2006, INT C PRINC KNOWL RE, P452
[7]  
Brafman Ronen., 2002, Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI-02), P69
[8]  
Brafman RonenI., 2005, P ICAPS, P182
[9]  
BUNDY A, 1996, C ART INT AAAI 1996, V1, P523
[10]   THE COMPUTATIONAL-COMPLEXITY OF PROPOSITIONAL STRIPS PLANNING [J].
BYLANDER, T .
ARTIFICIAL INTELLIGENCE, 1994, 69 (1-2) :165-204