Integrating Planning and Scheduling
Nicola Muscettola · 1993
When addressing specific classes of problems, it is not sufficient for a problem solving paradigm to enable domain descriptions and solution methods; it is necessary to support the process as well. This requires the provision of facilities that help make it reasonably easy, free from errors and efficient. We are interested in generating detailed predictions of the behavior of large scale systems; such problems arise in the operations management of complex systems, such as space-based facilities and transportation systems. Here, the main challenge is the integration of planning and scheduling. Classical planning does not provide reasonable support to the solution of these problems. In essence, it encourages a view of the world where change (action) operates as a labeled transition between two different world states, persisting for undetermined periods of time. The structural complexity of a state is unbound but, paradoxically, the devices provided for its description are unstructured such as complete first order theories or lists of predicates. This lack of balance between generality and structuredness is a major obstacle when addressing integrated planning and scheduling problems. Past research has identified several other problems: representation of processes continuously evolving over time, parallelism, external events, etc. Although solutions for individual aspects have been proposed, no comprehensive approach is currently capable of addressing them all. The lack of an integrated framework for the solution of problems has had two main consequences. First, the present complete separation between planning and scheduling competences has limited the range of solution methodologies available to us. In the classical approach, a pure (process) planning phase precedes a pure scheduling phase. However, it is apparent that this macro separation cannot be easily advocated in several complex domains. While scheduling, for example, it is often necessary to expand setup activities; these are not justified by the achievement of a goal but depend exclusively on how other activities are sequenced on a resource. Moreover, delaying planning into the scheduling phase might allow the selection of courses of action that, although a priori sub-optimal, are clearly convenient when considering the expected usage of resources over time. Second, the difficulty in generating extendeded detailed predictions has encouraged the attempt to completely avoid the process. In approaches that advocate this view classical planning operators can be readily used as simple stimulus-response rules. The rationale behind the denial of prediction is that since the conditions at execution are usually unpredictably different than those assumed during planning, it is futile to look any further than the immediate future. Although unpredictability and reactivity must be certainly taken into account, a purely reactive approach is not acceptable in domains with complex timing constraints and optimization concerns. Temporal myopia, for example, might generate gluts of resource requests in the future. The consequence would be either a suboptimal system utilization or actual system failure. Our research is addressing all the previous issues in a integrated planning and scheduling framework [1]. The representational paradigm stresses the decomposition of a domain as a vector of state variables continuously evolving over time. Each state variable is in effect a generalization of a classical scheduling resource; beyond its availability it also describes its state at any point in time. Temporal flexibility in the final schedule allows a certain amount of adjustment during execution, to adapt the extended to unpredictable events. We have also demonstrated the advantages of coupling temporal flexibility with statistical estimates of expected resource congestion during the generation of extended predictions [2].