zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Planning as constraint satisfaction: Solving the planning graph by compiling it into CSP. (English) Zbl 0983.68181
Summary: The idea of synthesizing bounded length plans by compiling planning problems into a combinatorial substrate, and solving the resulting encodings has become quite popular in recent years. Most work to-date has however concentrated on compilation to SATisfiability (SAT) theories and Integer Linear Programming (ILP). In this paper we will show that CSP is a better substrate for the compilation approach, compared to both SAT and ILP. We describe GP-CSP, a system that does planning by automatically converting Graphplan’s planning graph into a CSP encoding and solving it using standard CSP solvers. Our comprehensive empirical evaluation of GP-CSP demonstrates that it is superior to both the Blackbox system, which compiles planning graphs into SAT encodings, and an ILP-based planner in a wide range of planning domains. Our results show that CSP encodings outperform SAT encodings in terms of both space and time requirements in various problems. The space reduction is particularly important as it makes GP-CSP less susceptible to the memory blow-up associated with SAT compilation methods. The paper also discusses various techniques in setting up the CSP encodings, planning specific improvements to CSP solvers, and strategies for variable and value selection heuristics for solving the CSP encodings of different types of planning problems.

MSC:
68T20AI problem solving (heuristics, search strategies, etc.)
WorldCat.org
Full Text: DOI
References:
[1] Bayardo, R.; Miranker, D.: A complexity analysis of space-bounded learning algorithms for the constraint satisfaction problem. Proc. AAAI-96, Portland, OR (1996)
[2] Blum, A.; Furst, M.: Fast planning through planning graph analysis. Artificial intelligence 90, No. 1-2, 281-300 (1997) · Zbl 1017.68533 · doi:10.1016/S0004-3702(96)00047-1
[3] Bockmayr, A.; Dimopolous, Y.: Mixed integer programming models for planning problems. Proc. CP’98 workshop on constraint problem reformulation (1998)
[4] Bonet, B.; Geffner, H.: Planning as heuristic search: new results. Proc. 5th European conference on planning (1999) · Zbl 0971.68146 · doi:10.1016/S0004-3702(01)00108-4
[5] Bonet, B.; Loerincs, G.; Geffner, H.: A robust and fast action selection mechanism for planning. Proc. AAAI-97, providence, RI (1999)
[6] Dechter, R.; Meiri, I.; Pearl, J.: Temporal constraint networks. Artificial intelligence 49, 61-95 (1991) · Zbl 0737.68070 · doi:10.1016/0004-3702(91)90006-6
[7] Do, M.; Srivastava, B.; Kampahampati, S.: Investigating the effect of relevance and reachability constraints on SAT encodings of planning. Proc. AIPS-2000 (2000)
[8] Do, M.; Kampahampati, S.: Solving planning-graph by compiling it into CSP. Proc. AIPS-2000 (2000)
[9] Ernst, M.; Millstein, T.; Weld, D.: Automatic SAT compilation of planning problems. Proc. IJCAI-97, nagoya, Japan (1997)
[10] Fox, M.; Long, D.: The detection and exploitation of symmety in planning domains. Proc. IJCAI-99, Stockholm, Sweden (1999)
[11] Frank, J.; Jonsson, A.; Morris, P.: On reformulating planning as dynamic constraint satisfaction (extended abstract). Symposium on abstraction reformulation and approximation (2000)
[12] Frost, D.; Dechter, R.: Dead-end driven learning. Proc. AAAI-94, Seattle, WA (1999)
[13] Ginsberg, M.; Parkes, A.: Satisfiability algorithms and finite quantification. Proc. KR-2000 (2000)
[14] Hoffman, J.: A heuristic for domain independent planning and its use in an enforced Hill-climbing algorithm. (2000)
[15] Kambhampati, S.: Challenges in bridging plan synthesis paradigms. Proc. IJCAI-97, nagoya, Japan (1997)
[16] Kambhampati, S.: Improving graphplan’s search with ebl & ddb techniques. Proc. IJCAI-99, Stockholm, Sweden (1999)
[17] Kambhampati, S.: On the relation between intelligent backtracking and failure-driven explanation-based learning in constraint satisfaction and planning. Artificial intelligence 105, 161-208 (1998) · Zbl 0909.68139 · doi:10.1016/S0004-3702(98)00087-3
[18] Kambhampati, S.: Planning graph as a (dynamic) CSP: exploiting EBL, DDB and other CSP search techniques in graphplan. J. artificial intelligence res. 12, 1-34 (2000) · Zbl 0940.68100 · http://www.jair.org/abstracts/kambhampati00a.html
[19] Kambhampati, S.; Parker, E.; Lambrecht, E.: Understanding and extending graphplan. Proc. 4th European conference on planning (1997)
[20] Kambhampati, S.; Sanchez, R.: Distance-based goal-ordering techniques for graphplan. Proc. AIPS-00 (2000)
[21] Kautz, H.; Selman, B.: Blackbox: unifying SAT-based and graph-based planning. Proc. IJCAI-99, Stockholm, Sweden (1999)
[22] Kautz, H.; Selman, B.: Pushing the envelope: planning, propositional logic and stochastic search. Proc. AAAI-96, Portland, OR (1996) · Zbl 0882.68137
[23] Kautz, H.; Walser, J.: State-space planning by integer optimization. Proc. AAAI-99, Orlando, FL (1999)
[24] Long, D.; Fox, M.: Efficient implementation of the plan graph in STAN. J. artificial intelligence res. 10, 87-115 (1999) · Zbl 0914.68180 · http://www.jair.org/abstracts/long99a.html
[25] Mali, A.; Kambhampati, S.: On the utility of plan-space (causal) encodings. Proc. AAAI-99, Orlando, FL (1999)
[26] Mcdermott, D.: AIPS-98 planning competition results. (1998)
[27] Mittal, S.; Falkenhainer, B.: Dynamic constraint satisfaction problems. Proc. AAAI-90, Boston, MA (1990)
[28] Rintanen, J.: A planning algorithm non-based on directional search. Proc. internat. Conference on the principles of knowledge representation and reasoning (KR-98), Trento, Italy (1998)
[29] Smith, D.; Weld, D.: Temporal planning with mutual exclusion reasoning. Proc. IJCAI-99, Stockholm, Sweden (1999)
[30] Smith, D.; Frank, J.; Jonsson, A.: Bridging the gap between planning and scheduling. Knowledge engineering review 15, No. 1, 47-83 (2000)
[31] Srivastava, B.; Kambhampati, S.; Do, M.: Planning the project management way: efficient planning by effective integration of causal and resource reasoning in realplan. Artificial intelligence 131, 73-134 (2001) · Zbl 1042.68104 · doi:10.1016/S0004-3702(01)00122-9
[32] Tsang, E.: Foundations of constraint satisfaction. (1993)
[33] Van Beek, P.: CSPLIB: A library of CSP routines. (1994)
[34] Van Beek, P.; Chen, X.: Cplan: A constraint programming approach to planning. Proc. AAAI-99, Orlando, FL (1999)
[35] Vossen, T.; Ball, M.; Lotem, A.; Nau, D.: On the use of integer programming models in AI planning. Proc. IJCAI-99, Stockholm, Sweden (1999)
[36] Weld, D.; Anderson, C.; Smith, D.: Extending graphplan to handle uncertainty & sensing actions. Proc. AAAI-98, Madison, WI (1998)
[37] Wolfman, S.: Automatic discovery and exploitation of domain knowledge in planning. (1999)
[38] Zimmerman, T.; Kambhampati, S.: Exploiting symmetry in the plan-graph via explanation-guided search. Proc. AAAI-99, Orlando, FL (1999)
[39] Zweben, M.; Fox, M.: Intelligent scheduling. (1994)