Constraint satisfaction techniques in planning and scheduling: An introduction

• Autorzy: Bartak R.
• Języki publikacji: EN

Abstrakty

EN

Planning and scheduling are two closely related areas that, despite their similarity, deal with different problems. While the planning ask is to decide which actions are necessary to achieve a given goal, the scheduling task is to allocate known activities to scarce resources, such as machines, over time. Typically planning and scheduling problems are solved separately using different solving techniques. However, real-life problems require a more integrated approach. Constraint satisfaction seems to be such a unifying solving technology for both planning and scheduling problems. This paper describes how constraint satisfaction techniques can be applied to planning and scheduling problems.

Słowa kluczowe

EN

constraint satisfaction; problem modeling; planning; scheduling

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2008
• Tom: Vol. 18, no. 2
• Strony: 141--158
• Opis fizyczny: Bibliogr. 37 poz., rys.

Twórcy

autor

Bartak R.

• Charles University, Czech Republic,

Bibliografia

• [1] K. R. APT: Principles of constraint programming. Cambridge University Press, 2003.
• [2] P. BAPTISTE, C. LE PAPE and W. NUIJTEN: Constraint-based optimization and approximation for job-shop scheduling. Proc. AAAI-SIGMAN Workshop on IntelligentManufacturing Systems, (1995).
• [3] P. BAPTISTE and C. LE PAPE: Edge-finding constraint propagation algorithms for disjunctive and cumulative scheduling. Proc. Fifteenth Workshop of the U.K. Planning Special Interest Group, (1996).
• [4] P. BAPTISTE, C. LE PAPE and W. NUIJTEN: Constraint-based scheduling: applying constraint programming to scheduling. Kluwer Academic Publishers, 2001.
• [5] P. BAPTISTE, P. LABORIE, C. LE PAPE and W. NUIJTEN: Constraint-based scheduling and planning. In Rossi, van Beek, Walsh (Eds.): Handbook of Constraint Programming, Elsevier, 2006, 761-799.
• [6] R. BARTAK: Constraint satisfaction for planning and scheduling. In Vlahavas, Vrakas (Eds.): Intelligent Techniques for Planning, Idea Group. 2005, 320-353.
• [7] R. BARTAK and D. TOROPILA: Reformulating constraint models for classical planning. Proc. 21st Int. Florida AI Research Society Conference, AAAI Press, (2008), 525-530.
• [8] N. BELDICEANU, M. CARLSSON and J.X. RAMPON: Global constraint catalogue. Technical Report T2005-06, SICS, Uppsala, (2005).
• [9] C. BESSIERE: Arc-consistency and arc-consistency again. Artificial Intelligence, 65 (1994), 179-190.
• [10] A. BLUM and M. FuRST: Fast planning through planning graph analysis. Artificial Intelligence, 90 (1997), 281-300.
• [11] J. CARLIER and E. PINSON: Adjustment of heads and tails for the job-shop problem. European J. of Operational Research, 78(2), (1994), 146-161.
• [12] R. DECHTER, I. MEIRI and J. PEARL: Temporal constraint networks. Artificial Intelligence, 49 (1991), 61-95.
• [13] R. DECHTER: Constraint processing. Morgan Kaufmann, (2003).
• [14] M. R. GAREY and D. S. JOHNSON: Computers and intractability: A Guide to the theory of NP-completeness. W.H. Freeman and Co., San Francisco, 1979.
• [15] M. GHALLAB, D. NAU and P. TRAVERSO: Automated planning: Theory and practice. Morgan Kaufmann. 2004.
• [16] S. GOLOMB and L. BAUMERT: Backtrack programming. J. of the ACM, 12 (1965), 516-524.
• [17] R. M. HARALICK and G. L. ELLIOT: Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14 (1980), 263-314.
• [18] H. KAUTZ and B. SELMAN: Planning as satisfiability. Proc. of ECAI, (1992), 359-363.
• [19] P. LABORIE: Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results. Artificial Intelligence, 143 (2003), 151-188.
• [20] J. Y. T. LEUNG: Handbook of scheduling: Algorithms, models, and performance analysis. Chapman & Hall, 2004.
• [21] O. LHOMME Consistency techniques for numeric CSPs. In Ruzena Bajcsy (Ed.): Proc. of 13th Mt. Joint Conf on Artificial Intelligence, Morgan Kaufmann, (1993).
• [22] A. LOPEZ and F. BACCHUS: Generalizing GraphPlan by formulating planning as a CSP. Proc. of IJCAI, (2003), 954-960.
• [23] A. K. MACKWORTH: Consistency in networks of relations. Artificial Intelligence, 8 (1977), 99-118.
• [24] K. MARRIOTT and P. J. STUCKEY: Programming with constraints: An Introduction. The MIT Press, 1998.
• [25] J.-C. REGIN: A filtering algorithm for constraints of difference in CSPs. Proc. Of the National Conf on Artificial Intelligence, AAAI Press, (1994), 362-367.
• [26] R. REITER Knowledge in action: Logical foundation for specifying and implementing dynamic systems. MIT Press, 2001.
• [27] F. ROSSI, P. VAN BEEK and T. WALSH: Handbook of constraint programming. Elsevier, 2006.
• [28] S. F. SMITH and CH.-CH. CHENG: Slack-based heuristics for constraint satisfaction scheduling. Proc. National Conf on Artificial Intelligence, (1993), 139-144.
• [29] P. TORRES and P. LOPEZ: On Not-First/Not-Last conditions in disjunctive scheduling. European J. of Operational Research, 127, (2000), 332-343.
• [30] E. TSANG: Foundations of constraint satisfaction. Academic Press, 1993.
• [31] P. VAN BEEK and X. CHEN: CPlan: A constraint programming approach to planning. Proc. of AAAI-99, (1999), 585-590.
• [32] P. VAN HENTENRYCK: Constraint satisfaction in logic programming. The MIT Press, Cambridge, MA, 1989.
• [33] V. VIDAL and H. GEFFNER: Branching and pruning: An optimal temporal POCL planner based on constraint programming. Proc. of AAA1-04, (2004), 570-577.
• [34] P. VILIM: O(n log n) filtering algorithms for unary resource constraint. Proceedings of CP-AI-OR 2004, LNCS, Springer Verlag, (2004).
• [35] P. VILIM, R. BARTÁK and O. ČEPEK: Extension of O(n log n) filtering algorithms for the unary resource constraint to optional activities. Constraints, 10(4), (2005), 403-425.
• [36] D. L. WALTZ: Understanding line drawings of scenes with shadows. In Psychology of Computer Vision, McGraw-Hill, New York, 1975, 19-91.
• [37] A. WOLF: Pruning while sweeping over task intervals. In Principles and Practice of Constraint Programming (CP 2003). LNCS 2833, Springer Verlag, 2003, 739-753.