Unifying planning and scheduling as timelines in a component-based perspective

• Autorzy: Fratini S. , Pecora F. , Cesta A.
• Języki publikacji: EN

Abstrakty

EN

The timeline-based approach to planning represents an effective alternative to classical planning for complex domains requiring the use of both temporal reasoning and scheduling features. This paper discusses the constraint-based approach to timeline planning and scheduling introduced in OMPS. OMPS is a an architecture for problem solving which draws inspiration from both control theory and constraint-based reasoning, and which is based on the notion of components. The rationale behind the component-based approach shares with classical control theory a basic modeling perspective: the planning and scheduling problem is represented by identifying a set of relevant domain components which need to be controlled to obtain a desired temporal behavior for the entire system. Components are entities whose properties may vary in time and which model one or more physical (or logical) domain subsystems relevant to a given planning context. The planner/scheduler plays the role of the controller for these entities, and reasons in terms of constraints that bound their internal evolutions and the desired properties of the generated behaviors (goals). Our work complements this modeling assumption with a constraint-based computational framework. Admissible temporal behaviors of components are specified as a set of causal constraints within a rich temporal specification, and goals are specified as temporal constraint preferences. The OMPS software architecture presented in this paper combines both specific and generic constraint solvers in defining consistent timelines which satisfy a given set of goals.

Słowa kluczowe

EN

planning; scheduling; timelines

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

Twórcy

autor

Fratini S.

autor

Pecora F.

autor

Cesta A.

• ISTC-CNR,National Research Council of Italy,

Bibliografia

• [1] J. ALLEN: Maintaining knowledge about temporal intervals. Communications of the ACM, 26(11), (1983), 832-843.
• [2] J. F. ALLEN: Temporal reasoning and planning. In Reasoning About Plans. Morgan Kaufmann Pub., 1991.
• [3] R. ALUR and D. L. DILL: A theory of timed automata. Theor. Comput. Sci., 126(2), (1994), 183-235.
• [4] P. BAPTISTE, C. LE PAPE and W. NUIJTEN: Constraint-Based Scheduling, volume 39 of Mt. Series in Operations Research and Management Science. Kluwer Academic Publishers, 2001.
• [5] P. BAPTISTE and C. LE PAPE: A theoretical and experimental comparison of constraint propagation techniques for disjunctive scheduling. In C. S. Mellish, (Ed), Proc. Fourteenth Mt. Joint Conf. Artificial Intelligence, 1 Morgan Kaufmann, (1995), 600-606.
• [6] R. BARTAK: Constraint satisfaction for planning and scheduling. In I. Vlahavas and D. Vrakas, (Eds), Intelligent Techniques for Planning. Idea Group Publishing, 2004.
• [7] J. C. BECK, A. J. DAVENPORT, E. D. DAVIS and M.S. Fox: The ODO project: Towards a unified basis for constraint-directed scheduling. J of Scheduling, 1 (1998), 89-125.
• [8] P. BRUCKER: Scheduling algorithms. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2001.
• [9] A. CESTA, S. FRATINI and A. ODDI: Planning with concurrency, time and resources: A CSP-based approach. In I. Vlahavas and D. Vrakas, (Eds), Intelligent Techniques for Planning. Idea Group Publishing, 2004.
• [10] A. CESTA and A. ODDI: DDL.1: A Formal Description of a Constraint Representation Language for Physical Domains. In M. M.Ghallab and A. Milani, (Eds), New Directions in AI Planning. IOS Press, 1996.
• [11] A. CESTA, A. ODDI and S. F. SMITH: A Constraint-based method for project scheduling with time windows. J. of Heuristics, 8(1), (2002), 109-136.
• [12] A. CESTA and C. STELLA: A time and resource problem for planning architectures. In ECP-97. Proc. of the Fourth European Conf. on Planning, LNAI 1348, (1997), 117-129.
• [13] C.-C. CHENG and S. F. SMITH: Generating feasible schedules under complex metric constraints. Proc. Twelfth National Conf. on Artificial Intelligence, 2 Seattle, Washington, USA, AAAI Press/MIT Press, (1994), 1086-1091.
• [14] S. CHIEN, G. RABIDEAU, R. KNIGHT, R. SHERWOOD, B. ENGELHARDT, D. MUTZ, T. ESTLIN, B. SMITH, F. FISHER, T. BARRETT, G. STEBBINS, and D. TRAN: ASPEN — automated planning and scheduling for space mission operations. Proc. of SpaceOps 2000, (2000).
• [15] R. DECHTER, I. MEIRI and J. PEARL: Temporal constraint networks. Artificial Intelligence, 49(1-3), (1991), 61-95.
• [16] R. DECHTER: Constraint Processing. Morgan Kaufmann Pub. Inc., 2003.
• [17] M. B. DO and S. KAMBHAMPATI: Planning as constraint satisfaction: Solving the planning graph by compiling it into CSP. Artificial Intelligence, 132(2), (2001), 151-182.
• [18] A. EL-KHOLY and B. RICHARDS: Temporal and resource reasoning in planning: The parcPLAN approach. In W. Wahlster, (Ed), Proc. 12th European Conf on Artificial Intelligence, Wiley & Sons, (1996), 614-618.
• [19] R. E. FIKES and N. J. NILSSON: STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2(3-4), (1971), 189-208.
• [20] M. S. Fox: Constraint guided scheduling: A short history of scheduling research at CMU. Computers and Industry, 14(1-3), (1990), 79-88.
• [21] J. FRANK and A. JONSSON: Constraint-based attribute and interval planning. Constraints, 8(4), (2003), 339-364.
• [22] J. FRANK, A. K. JÓNSSON and P. MORRIS: On reformulating planning as dynamic constraint satisfaction. Lecture Notes in Computer Science, 1864 (2000).
• [23] S. FRATINI, A. CESTA and A. ODDI: Extending a scheduler with causal reasoning: a CSP approach. In Proc. of the ICAPS-05 Workshop on Constraint Programming for Planning and Scheduling, (2005).
• [24] R. E. Frederking and N. Muscettola: Temporal planning for transportation planning and scheduling. Proc. IEEE Mt. Conf on Robotics and Automation, (1992).
• [25] A. GEREVINI, A. SA ETTI and I. SERINA: Planning through stochastic local search and temporal action graphs in LPG. J. Artil Intell. Res. (JAIR), 20 (2003) 239-290.
• [26] M. GHALLAB and H. LARUELLE: Representation and control in IxTeT, a temporal planner. Proc. Second Int. Conf on Artifial Intelligence Planning Scheduling Systems. AAAI Press, (1994).
• [27] D. GHALLAB, M. NAU and P. TRAVERSO: Automated planning, theory and practice. Morgan Kaufmann Publishers, 2004.
• [28] A. K. JONSSON, P. H. MORRIS, N. MUSCETTOLA, K. RAJAN and B. SMITH: Planning in interplanetary space: Theory and practice. Proc. Fifth Int. Conf on Artificial Intelligence Planning and Scheduling, (2000).
• [29] H. KAUTZ and B. SELMAN: Blackbox: A new approach to the application of theorem proving to problem solving. Workshop on Planning as Combinatorial Search, (1998), 58-60.
• [30] H. A. KAUTZ and B. SELMAN: Planning as satisfiability. Proc. Tenth European Conf on Artificial Intelligence, (1992), 359-363.
• [31] P. LABORIE: Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results. Artificial Intelligence, 143 (2003), 151-188.
• [32] J. M. LEVER and B. RICHARDS: parcPLAN: A planning architecture with parallel actions, resources and constraints. Proc. 9th Mt. Symp. on Methodologies for Intelligent Systems, Springer Verlag, (1994), 213-222.
• [33] S. MITTAL and B. FALKENHEIMER: Dynamic constraint satisfaction problems. Proc. 8th National Conf on Artificial Intelligence, (1990), 25-32.
• [34] N. MUSCETTOLA: HSTS: Integrating planning and scheduling. In M. Zweben and M.S. Fox, (Eds), Intelligent Scheduling, Morgan Kauffmann, 1994.
• [35] N. MUSCETTOLA, S. F. SMITH, A. CESTA and D. D'ALOISI: Coordinating space telescope operations in an integrated planning and scheduling architecture. IEEE Control Systems, 12(1), (1992), 28-37.
• [36] A. ODDI and S. F. SMITH: Stochastic procedures for generating feasible schedules. Proc. 14th National Conf on Artificial Intelligence, (1997), 308-314.
• [37] K. M. PASSINO and P. J. ANTSAKLIS: A system and control theoretic perspective on artificial intelligence planning systems. J. of Applied Artificial Intelligence, 3 (1989), 1-32.
• [38] N. M. SADEH: Look-ahead techniques for micro-opportunistic job shop schedul-
• [39] D. E. S MITH, J. FRANK and A.K. JONSSON: Bridging the gap between planning and scheduling. Knowledge Engineering Review, 15(1), (2000), 47-83.
• [40] S. F. S MITH and C. CHENG: Slack-based heuristics for constraint satisfactions scheduling. Proc. 11th National Cont. on Artificial Intelligence, AAAI Press, (1993), 139-144.
• [41] S. F. S MITH: OPIS: A methodology and architecture for reactive scheduling. In M. Zweben and S. M. Fox, (Ed), Intelligent Scheduling. Morgan Kaufmann, 1994.
• [42] E. P. K. TSANG: Foundation of Constraint Satisfaction. Academic Press, London and San Diego, CA, 1993.
• [43] S. WOLFMAN and D. WELD: Combining linear programming and satisfiability solving for resource planning. Knowledge Engineering Review, 16(1), (2000), 85-99.