Integrating Planning and Scheduling : A Constraint-based Approach

Abstract

Automated decision making is one of the important problems of Artificial Intelligence (AI). Planning and scheduling are two sub-fields of AI that research automated decision making. The main focus of planning is on general representations of actions, causal reasoning among actions and domain-independent solving strategies. Scheduling generally optimizes problems with complex temporal and resource constraints that have simpler causal relations between actions. However, there are problems that have both planning characteristics (causal constraints) and scheduling characteristics (temporal and resource constraints), and have strong interactions between these constraints. An integrated approach is needed to solve this class of problems efficiently. The main contribution of this thesis is an integrated constraint-based planning and scheduling approach that can model and solve problems that have both planning and scheduling characteristics. In our representation problems are described using a multi-valued state variable planning language with explicit representation of different types of resources, and a new action model where each action is represented by a set of transitions. This action-transition model makes the representation of actions with delayed effects, effects with different durations, and the representation of complex temporal and resource constraints like time-windows, deadline goals, sequence-dependent setup times, etc simpler. Constraint-based techniques have been successfully applied to solve scheduling problems. Therefore, to solve a combined planning/scheduling problem we compile it into a CSP. This compilation is bounded by the number of action occurrences. The constraint model is based on the notion of “support” for each type of transition. The constraint model can be viewed as a system of CSPs, one for each state variable and resource, that are synchronized by a simple temporal network for action start times. Central to our constraint model is the explicit representation and maintenance of the precedence constraints between transitions on the same state variable or resource. We propose a branching scheme for solving the CSP based on establishing supports for transitions, which imply precedence constraints. Furthermore, we propose new propagation and inference techniques that infer precedence relations from temporal and mutex constraints, and infer tighter temporal bounds from the precedence constraints. The distinguishing feature of these inference and propagation techniques is that they not only consider the transitions and actions that are included in the plan but can also consider actions and transitions that are not yet included in or excluded from the plan. We conclude the thesis with a modeling case study of a complex satellite problem domain to demonstrate the effectiveness of our representation. This problem domain has action choices that are tightly coupled with temporal and resource constraints. We show that most of the complexities of this problem can be expressed in our representation in a simple and intuitive way. Show more