Solving Sequential Planning Problems via Constraint Satisfaction

• Autorzy: Bartak R. , Toropila D.
• Języki publikacji: EN

Abstrakty

EN

Planning problems deal with finding a sequence of actions that transfer the initial state of the world into a desired state. Frequently such problems are solved by dedicated algorithms but there exist planners based on translating the planning problem into a different formalism such as constraint satisfaction or Boolean satisfiability and using a general solver for this formalism. The paper describes how to enhance existing constraintmodels of sequential planning problems by using techniques such as symmetry breaking (dominance rules), singleton consistency, nogoods, lifting, or techniques motivated by the partial-order planning.

Słowa kluczowe

EN

planning; constraint models; symmetry breaking; lifting; redundant constraints; search strategy

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 99, nr 2
• Strony: 125--145
• Opis fizyczny: Bibliogr. 18 poz., wykr.

Twórcy

autor

Bartak R.

autor

Toropila D.

• Faculty of Mathematics and Physics, Charles University, Malostranskénam. 2/25, 118 00 Prague, Czech Republic,

Bibliografia

• [1] Bäckström, C., Nebel, B.: Complexity Results for SAS+ Planning, Computational Intelligence, 11, 1995, 625-656.
• [2] Barták, R., Toropila, D.: Reformulating Constraint Models for Classical Planning, FLAIRS 21: The Twenty- First International Florida Artificial Intelligence Research Society Conference (D.Wilson, H. C. Lane, Eds.), AAAI Press, 2008, ISBN 978-1-57735-365-2.
• [3] Barták, R., Toropila, D.: Integrated Constraint Models for Sequential and Partial-Order Planning, SARA 2009: Proceedings of the Eighth Symposium on Abstraction, Reformulation and Approximation, AAAI Press, 2009, ISBN 978-1-57735-433-8.
• [4] Barták, R., Toropila, D.: Revisiting Constraint Models for Planning Problems, ISMIS '09: Proceedings of the Eighteenth International Symposium on Foundations of Intelligent Systems, Springer-Verlag, Berlin, Heidelberg, 2009, ISBN 978-3-642-04124-2.
• [5] van Beek, P., Chen, X.: CPlan: A Constraint Programming Approach to Planning, AAAI '99/IAAI '99: Proceedings of the Sixteenth National Conference on Artificial Intelligence and the Eleventh Conference on Innovative Applications of Artificial Intelligence, American Association for Artificial Intelligence, Menlo Park, CA, USA, 1999, ISBN 0-262-51106-1.
• [6] Bessiere, C., Hebrard, E., Hnich, B., Kiziltan, Z., Walsh, T.: Filtering Algorithms for the NValue Constraint, Constraints, 11(4), 2006, 271-293, ISSN 1383-7133.
• [7] Blum, A., Furst, M. L.: Fast Planning Through Planning Graph Analysis, Artificial Intelligence, 90(1-2), 1997, 281-300.
• [8] Carlsson, M., Ottosson, G., Carlson, B.: An Open-Ended Finite Domain Constraint Solver, PLILP '97: Proceedings of the Ninth International Symposium on Programming Languages: Implementations, Logics, and Programs, Springer-Verlag, London, UK, 1997, ISBN 3-540-63398-7.
• [9] Debruyne, R., Bessi`ere, C.: Some Practicable Filtering Techniques for the Constraint Satisfaction Problem, IJCAI '97: Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, 1997.
• [10] Dechter, R.: Constraint Processing, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2003, ISBN 1558608907.
• [11] Do, M. B., Kambhampati, S.: Planning as Constraint Satisfaction: Solving the Planning Graph by Compiling It into CSP, Artificial Intelligence, 132(2), 2001, 151-182, ISSN 0004-3702.
• [12] Ghallab, M., Nau, D., Traverso, P.: Automated Planning: Theory and Practice, Morgan Kaufmann Publishers, 2004.
• [13] Helmert, M.: The Fast Downward Planning System, Journal of Artificial Intelligence Research (JAIR), 26, 2006, 191-246.
• [14] Kautz, H. A., Selman, B.: Planning as Satisfiability, ECAI 92: Tenth European Conference on Artificial Intelligence, Vienna, Austria, 1992.
• [15] Long, D., Fox, M.: Plan Permutation Symmetries as a Source of Planner Inefficiency, Proceedings of UK Workshop on Planning and Scheduling, 2003.
• [16] Lopez, A., Bacchus, F.: Generalizing GraphPlan by Formulating Planning as a CSP, IJCAI '03: Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (G. Gottlob, T. Walsh, Eds.), Morgan Kaufmann, Acapulco, Mexico, 2003.
• [17] Reiter, R.: Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems, The MIT Press, 2001.
• [18] Vidal, V., Geffner, H.: Branching and Pruning: An Optimal Temporal POCL Planner Based on Constraint Programming, Artificial Intelligence, 170(3), 2006, 298-335.