Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
7.7CiteScore
2.0Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2016 Volume 31
Article Contents
Next Previous
RESEARCH ARTICLE   Open Access    

Revisiting dynamic constraint satisfaction for model-based planning

  • Moffett Field

More Information
  • Abstract: As planning problems become more complex, it is increasingly useful to integrate complex constraints on time and resources into planning models, and use constraint reasoning approaches to help solve the resulting problems. Dynamic constraint satisfaction is a key enabler of automated planning in the presence of such constraints. In this paper, we identify some limitations with the previously developed theories of dynamic constraint satisfaction. We identify a minimum set of elementary transformations from which all other transformations can be constructed. We propose a new classification of dynamic constraint satisfaction transformations based on a formal criteria, namely the change in the fraction of solutions. This criteria can be used to evaluate elementary transformations of a constraint satisfaction problem as well as sequences of transformations. We extend the notion of transformations to include constrained optimization problems. We discuss how this new framework can inform the evolution of planning models, automated planning algorithms, and mixed-initiative planning.
  • 加载中
  • Banerjee D. 2009. Integrating planning and scheduling in a CP framework: a transition-based approach. In Proceedings of the 19th International Conference on Automated Planning and Scheduling, 330–333.

    Google Scholar

    Bistarelli S., Montanari U. & Rossi F. 1995. Constraint solving over semirings. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, 624–630.

    Google Scholar

    Bresina J., Jónsson A., Morris P. & Rajan K. 2005. Activity planning for the Mars exploration rovers. In Proceedings of the 15th International Conference on Automated Planning and Scheduling, 40–49.

    Google Scholar

    Dechter R. & Dechter A. 1988. Belief maintenance in dynamic constraint networks. In Proceedings of the 7th National Conference on Artificial Intelligence, 37–42.

    Google Scholar

    Do M. & Kambhampati S. 2000. Solving planning-graph by compiling it into CSP. In Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, 82–91.

    Google Scholar

    Frank J. 2014. Revisiting dynamic constraint satisfaction for automated planning. In Workshop on Constraints and Planning Systems, in conjunction with the 24th International Conference on Automated Planning.

    Google Scholar

    Frank J. & Jónsson A. 2003. Constraint based attribute and interval planning. Journal of Constraints Special Issue on Constraints and Planning 8, 339–364.

    Google Scholar

    Frank J., Jónsson A. & Morris P. 2000. On reformulating planning as dynamic constraint satisfaction. In Proceedings of the 4th Symposium on Abstraction, Reformulation and Approximation.

    Google Scholar

    Freuder E. & Wallace R. 1992. Partial constraint satisfaction. Artificial Intelligence 58, 21–70.

    Google Scholar

    Ghallab M. & Laurelle H. 1994. Representation and control in IxTeT, a temporal planner. In Proceedings of the 4th International Conference on AI Planning and Scheduling, 61–67.

    Google Scholar

    Jónsson A. & Frank J. 2000. A framework for dynamic constraint reasoning using procedural constraints. In Proceedings of the 10th European Conference on Artificial Intelligence, 93–97.

    Google Scholar

    Kambhampati S. 2007. Model-lite planning for the web-age masses: the challenges of planning with incomplete and evolving domain models. In Proceedings of the 13th National Conference on Artificial Intelligence, 1601–1604.

    Google Scholar

    Keyder E. & Geffner H. 2008. Heuristics for planning with action costs, revisited. In Proceedings of the 18th European Conference on Artificial Intelligence, 140–149.

    Google Scholar

    Laborie P. 2003. Algorithms for propagating resource constraints in AI planning and scheduling: existing approaches and new results. Artificial Intelligence 143, 151–188.

    Google Scholar

    Mittal S. & Falkenhainer B. 1990. Dynamic constraint satisfaction problems. In Proceedings of the 9th National Conference on Artificial Intelligence, 25–32.

    Google Scholar

    Soininen T., Gelle E. & Niemela I. 1999. A fixpoint definition of dynamic constraint satisfaction. In Proceedings of the 5th International Conference on the Principles and Practices of Constraint Programming, 419–433.

    Google Scholar

    Tsamardinos I. & Pollack M. 2003. Efficient solution techniques for disjunctive temporal reasoning problems. Artificial Intelligence 151(1–2), 43–90.

    Google Scholar

    van den Briel M., Vossen T. & Kambhampati S. 2005. Reviving integer programming for AI planning: a branch and cut framework. Proceedings of the 15th International Conference on Automated Planning and Scheduling, 562–569.

    Google Scholar

    van den Briel M., Sanchez Nigenda R., Do M. & Kambhampati S. 2004. Effective approaches for partial satisfaction (oversubscription) planning. In Proceedings of the 19th National Conference on Artificial Intelligence.

    Google Scholar

    Vaquero T., Romero V., Tonidanel F. & Silva J. 2007. ItSimple 2.0: an integrated tool for designing planning domains. In Proceedings of the 17th International Conference on Automated Planning and Scheduling, 336–343.

    Google Scholar

    Vidal V. & Geffner H. 2006. Branching and pruning: an optimal POCL planner based on constraint programming. Artificial Intelligence 170(3), 298–335.

    Google Scholar

    Wallace R. 1996. Enhancement of branch and bound methods for the maximal constraint satisfaction problem. In Proceedings of the 13th National Conference on Artificial Intelligence, 188–195.

    Google Scholar

  • Cite this article

    Jeremy Frank. 2016. Revisiting dynamic constraint satisfaction for model-based planning. The Knowledge Engineering Review 31(5)429−439, doi: 10.1017/S0269888916000242
    Jeremy Frank. 2016. Revisiting dynamic constraint satisfaction for model-based planning. The Knowledge Engineering Review 31(5)429−439, doi: 10.1017/S0269888916000242
    shu
Download PDF

Article Metrics

Article views(30) PDF downloads(36)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Revisiting dynamic constraint satisfaction for model-based planning

  • Moffett Field

  • Published online: 20 December 2016
The Knowledge Engineering Review  31,  2016, 31(5): 429−439  |  Cite this article

Abstract: Abstract: As planning problems become more complex, it is increasingly useful to integrate complex constraints on time and resources into planning models, and use constraint reasoning approaches to help solve the resulting problems. Dynamic constraint satisfaction is a key enabler of automated planning in the presence of such constraints. In this paper, we identify some limitations with the previously developed theories of dynamic constraint satisfaction. We identify a minimum set of elementary transformations from which all other transformations can be constructed. We propose a new classification of dynamic constraint satisfaction transformations based on a formal criteria, namely the change in the fraction of solutions. This criteria can be used to evaluate elementary transformations of a constraint satisfaction problem as well as sequences of transformations. We extend the notion of transformations to include constrained optimization problems. We discuss how this new framework can inform the evolution of planning models, automated planning algorithms, and mixed-initiative planning.

    HTML

    Acknowledgments

    • The author would like to thank the anonymous reviewers of the paper for their feedback and editorial comments.

    Rights and permissions
    • © Cambridge University Press, 2016 2016Cambridge University Press
References (22)
  • About this article
    Cite this article
    Jeremy Frank. 2016. Revisiting dynamic constraint satisfaction for model-based planning. The Knowledge Engineering Review 31(5)429−439, doi: 10.1017/S0269888916000242
    Jeremy Frank. 2016. Revisiting dynamic constraint satisfaction for model-based planning. The Knowledge Engineering Review 31(5)429−439, doi: 10.1017/S0269888916000242
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return