Constraint Satisfaction with Delayed Evaluation

1 Introduction

A constraint satisfaction problem (CSP) is characterized by a set of variables. Each variable has a possibly infi­ nite domain of values and a set of domain constraints. A solution to a CSP assigns a value consistent with the domain constraints to each variable. A constraint is are­ lated condition, (or predicate), that must hold among a set of variables. The algorithms used in most CSPs are those that find locally consistent assignments, that is, those that satisfy all constraints on a particular variable, in constraint networks by local propagation. The locally consistent assignments can be used to find a globally con­ sistent solution, i.e., one that satisfies all constraints on all variables. Many previous real-world problems have been characterized as CSPs: scheduling [Brown, 1987, Fox, 1983, Johnston, 1989, Rit, 1986, Zweben, 1987], understanding line drawings [Waltz, 1975], electrical cir­ cuit analysis [Steele, 1980], temporal reasoning [Dean, 1985] and aspects of planning problems [Lansky, 1988, Stefik , 1980, Wilkins, 1984].

2 Constraint Satisfaction Problems

In this section, we describe the general constraint satis­ faction algorithm (without delayed evaluation) and show how to improve the basic algorithm by using constraint propagation.

2.1 Uninformed Systematic Search

The most common algorithm for solving CSPs is sys­ tematic backtracking search. In its simplest form, the system takes an arbitrary ordering of variables and pro­ visionally assigns values to them in a generate-and-test

1. Order the variables from 1 ton.
2. Starting with the first variable, pick a value from its set of possible values.
3. Test the constraints associated with the variable to determine whether the value is valid.
4. If it is not valid, continue choosing values until the set is exhausted or until a valid one is found.
5. If a legal value is generated, continue with the next variable at step two.
6. Otherwise, backtrack to the previous variable, reject its current value and continue with its next value at step two.
7. If the system exhausts the first variable's possibilities, then there are no consistent assignments.

Figure 1: Systematic Backtracking Search

manner, until the set of variables has a globally consis­ tent assignment. The basic algorithm is shown in Fig­ ure 1.

Intelligent, or dependency-directed, backtracking schemes, based on knowledge of inter-variable dependen­ cies, and constraint propagation heuristics can be used to improve the basic algorithm's search performance [Stallman and Sussman, 1977]. Suggested schemes in­ clude "look-ahead", such as variable ordering or value ordering, or "look-back", such as constraint recording [Dechter and Pearl, 1987] or going back to the source of failure.

2.2 Propagation

Our system uses constraint propagation, that is, it fil­ ters values from a variable that are inconsistent with its constraints. For example, consider a binary constraint, C, over variables x and y, each having initial domains ranging over the integers. If C requires that all values of y be equal to 2x + 1, then all even integers would be filtered from the domain of y.

The propagation of constraints, or the application of filters, can be done by a number of look-ahead schemes including full look-ahead, partial look-ahead, and for­ ward checking [Haralick and Elliot, 1980]. These heuristics are also referred to as maintaining arc-consistency or path-consistency in constraint networks [Mackworth, 1977, Dechter and Pearl, 1987, Gusgen et al., 1988]. Our system uses the weakest of these heuristic procedures, forward checking, because it has been shown to yield good performance on many problems [Dechter and Pearl, 1987]. The forward-checking heuristic is an extension of the test phase in the algorithm shown in Figure 1 and is inserted as an elaboration of step 3.

1. Apply the constraint filters associated with the variable and determine whether the value is valid.
2. For each of the variables related by constraints to the variable under consideration, filter all values that are not consistent with the constraints.
3. For each of these associated variables, determine whether there exists at least one consistent assignment.
4. If not, then reject the value under consideration; otherwise, accept it.

Any system that propagates constraints runs the risk of introducing a large amount of unnecessary computation into the testing process. The application of a constraint to a variable serves to reduce the number possible of val­ ues, although, in general, there will still be more values remaining than will ever be needed. To avoid unneces­ sary enumeration of values, we have built a constraint satisfaction system that incorporates delayed evaluation techniques.

3 Delayed Evaluation

Delayed evaluation is a demand-driven evaluation scheme - parts of data structures are not generated until needed. There are many ways to implement de­ layed evaluation (see [Filman and Friedman, 1984]) but we have adapted streams [Abelson et al., 1985, Filman and Friedman, 1984].

Streams are an abstraction of lists. As a data ab­ straction, streams and lists are identical, but they differ in that streams delay the evaluation of their cdr's while lists evaluate all elements at once. The operations on streams (head, tail, and cons-stream) are similar to list operations (car, cdr, and cons) . Cons-stream is used to recursively define streams. It only partially constructs a stream, however, and then passes the partial construc­ tion to the program that accesses the stream. If the part of the stream that is not yet constructed is accessed by the tail operation, the stream will automatically con­ struct only that part of itself that the program requires. This permits representations of infinite data. In addition to the delay of the original construction of the stream, the filtering of a stream can be delayed. Both aspects of streams are crucial to our system in that they allow us to represent infinite data structures and they reduce unnecessary application of filters.

4 System Architecture

Our system is implemented in CommonLISP using the CommonLISP Object Standard (CLOS) prototyped by Xerox PARC [Bobrow et al., 1987]. The basic elements of our system are a collection of interrelated objects hav­ ing a built-in hierarchy of attribute (slot) values. The constraint network consists of variable objects, generator objects (the domain of possible values on a variable), and constraint objects. We have defined our own constraint language, allowing the user to add new constraints of any arity (number of related variables).

Our system assigns values to variables and applies each variable's constraints as they are assigned. These con­ straints not only test whether a commitment is legal, but also propagate information from assigned (fixed) vari­ ables to unassigned (constrained) variables through fil­ ter application. The filters that are created during the application of a constraint can either disallow certain values on a variable's domain or change the variable's domain of values in some way.

When a commitment is made to a variable, forward checking is executed by posting filters on the related constrained variables and provisionally assigning a set of values to them. If the related variable has at least one acceptable value on its generator, then the next variable can be assigned. However, if the related variable's gen­ erator is exhausted, any added filters must be removed, and the generator must be returned to the state it was in before the attempted commitment. New values for the current variable are tried (with forward checking) until the variable runs out of possibilities (causing the system to backtrack), or until a legal value is found. Thus, in our system, constraint satisfaction is simply a process of assigning values, posting filters, removing filters, and reinstating generators until a solution is found, or until the first variable exhausts its possible assignments (indi­ cating that there is no solution).

Because of the local/global consistency relationship in constraint networks, our system permits users to work on partially solved problems, to change previously made choices, and to add new information as it becomes avail­ able.

We have applied these ideas to scheduling. The sec­ tion below describes the implementation of the schedul­ ing system.

5 Scheduling

Our implementation views a resource allocation and scheduling problem as a set of task objects, each con­ taining information (slots) about an event's start time, end time, duration, and resource requirements. Resource requirements of a task include information about what type (class) and how much of some resource is needed. In addition to task objects, the system defines resource objects that contain information about the availability of resources.

5.1 Temporal Variables

In our formulation, a task's start time, end time, and du­ ration are represented as distinct variables. The domain of each variable is represented by a set of intervals; only those intervals contained in the set are legal possibilities. We also include special values :pos-inf and :neg-inf that allow us to represent open intervals when the temporal variables are unconstrained.

We represent intervals as dotted pairs whose first value is the start of the interval and whose second value is its end. For example,

((O . 10) (100 . :pos-int)) is interpreted as {t I 0 ~ t ~ 10 V 100 ~ t ~ oo }.

5.2 Temporal Constraints

In general, temporal constraints create filters that change the values of the temporal intervals on a time variable's generator. The rules of a constraint are de­ fined using interval algebra and James Allen's formalism of the relations between two intervals [Allen, 1984].

PLUS-INTERVAL is a 3-place constraint that adds two intervals. In the scheduling application, it main­ tains the following functional relationship among the start time, end time and duration variables of a task:

start time + duration = end time The propagation rules for this constraint are: start time <- end time - duration end time <- start time + duration duration <- end time - start time

A filter is applied to the variable on the left when it is constrained and the variables to the right of the arrow are fixed.

EQUAL is a binary constraint that relates two time variables and creates a filter that ensures that the gen­ erators of the two variables contain the same values.

AFTER is a binary constraint relating start time or end time variables, ensuring that some time interval fol­ lows another.

We have also defined a special instance of a con­ straint, NOT-DURING. NOT-DURING encodes infor­ mation disallowing certain time intervals as possible gen­ erator values. For instance, if it is known that tasks can only be scheduled on weekdays, we can define a NOT­ DURING-WEEKENDS constraint that filters any time intervals falling on weekends. Thus, if we assume that some particular start and end time variables have initial values, in days, of

(1 . :pos-int)

representing an interval from relative day 1, (Monday) with no fixed end, the application of the NOT-DURING­ WEEKENDS filter would create a new infinite possibil­ ity set of intervals

((1. 5) (8. 13) ..... ).

Constraints like these can significantly increase the number of possible values of a variable. It is in this particular case, and cases like it, that the power of the stream representation is realized. If the possible time in­ tervals were represented as a list, the computation (ap­ plication of filters to list elements) would continue end­ lessly. 1

5.3 Resource Variables

A task's resource requirements and the available re­ sources are represented by resource class and resource pool variables. A resource pool is an instance of a re­ source class. For example, if there exists a resource class, technicians, we can think of each resource pool as an equivalence class of individual technicians. We may want to distinguish between two pools of technicians for rea­ sons such as different costs associated with each pool, or different locations in which the pools reside. For our purposes, if a resource pool contains more than one of some resource, each resource is interchangeable within a single pool, but not across multiple pools. Thus, differ­ ent resource pools represent distinguishable resources.

Any variables whose values change over time are rep­ resented as histories. Histories are lists of changes to a variable's value indexed by time. The most important time-based variables in a scheduling system are those that track information about resource availability. In our system, resource availability histories are represented as lists (or streams) of time interval/quantity available pairs. For instance,

( ((O . 10) . 75) ((11 50) . 25) ((51 . :pos-int) . 75) ) is interpreted as: { 75 Availability( resource, t) = 25 75 0 ~ t ~ 10 11 ~ t ~50 51~ t ~ 00

5.4 Resource Constraints

Resource variables are used to evaluate the truth of the RESOURCE-AVAILABLE constraint and to propagate its effects. The RESOURCE-AVAILABLE constraint is a 4-place constraint relating a task's start time, end time, quantity-of-resource-needed, and resource pool. It is used to determine if a particular amount of some re­ source is available during the given interval of time. If the resource pool and required amount of the resource is known, the constraint restricts (filters) the values of the start and end times to intervals that begin when the re­ quired quantity of that pool is available. If the time and quantity variables are fixed, then those resource pools that do not meet the requirements are filtered from the resource pool variable.

The EQUAL and NOT-DURING constraints can be used in much the same way as they are used in temporal reasoning. Instead of filtering possible values of time intervals, the possible resource pools are filtered.

1 However, infinite streams must be handled carefully as they do not avoid infinite computation, but rather delay it. In practice, this means that filter application must be ordered so that more constraining filters are applied first.

5.5 Scheduling

The scheduling process begins by placing all tasks on a priority queue of unscheduled tasks. This priority queue generally prefers tasks that are closer to the anchors of the schedule (the tasks fixed in time due to external forces). As tasks are removed from the queue, a variable commitment strategy is chosen that guides the search for appropriate times and resource pools for the task. 2 An example of a commitment strategy is to schedule a task's variables in the following order: end-time, start­ time, resource-pool1, resource-pool2 ... 3

When all of the variables (i.e., start time, end time, quantity-of-resource-needed, and resource pool) for are­ source allocation are committed, the effects of this usage are recorded in the resource pool. When a task has been completely scheduled, it is placed on a list of scheduled tasks. We use the systematic backtracking procedure discussed above to instantiate the variables of a task (using the commitment strategy as the variable order­ ing). When a task can not be scheduled (i.e., there is no instantiation of its variables consistent with constraints) the procedure removes the previous task from the list of scheduled tasks and tries new values for its variables (in backwards chronological order).

5.6 Scheduling Example

To illustrate the use of streams for a scheduling applica­ tion, we present a simple example. Consider two tasks, receiving and installation, whose start and end times are fixed to the same value (i.e., the tasks are performed in parallel) and each of which need one technician. The resource pool utilization variable of receiving is fixed to:

(Sid)

Installation's resource pool utilization is constrained to: (Pete, Roger, Keith, Sid, Albert, Eric, Mick)

The system evaluates the constraints on the installation's usage that propagates information from the receiving us­ age. When lists are used to represent the pools of techni­ cians, this propagation manifests itself as a filter on the generator of installation, resulting in the following new list (reflecting that Roger and Albert were being used by some other task at this time):

(Pete, Keith, Eric, Mick)

In this case, the entire list was checked. Compare this to the stream representation. The new stream (after filtering) is:

(Pete . <delayed closure>)

Since Pete meets the constraints imposed upon the in­ stallation task, he remains on this list and the filtering of the rest of the list is delayed. If Pete were judged to be unacceptable, he would be rejected and the next available technician would be chosen.

2 1n general, the duration of tasks as well as the type and quantity of resources they require are known a priori. How­ ever, if these variables were not known, they would be added to the commitment strategy (and constrained) like the other variables.

3 This is the commitment strategy chosen for the results reported in the next section.

Only at this point is Roger filtered and Keith chosen, avoiding the unneccessary processing employed by a tra­ ditional constraint propagator.

6 Results

We have formulated and solved two problems as CSPs using our system: the n-queens problem (i.e., place n queens on an n x n chess board so that no two queens share the same row, column, or diagonal) and a real world scheduling problem based on NASA's Space Shut­ tle payload processing domain (EMPRESS-A) [Hankins et al., 1985] .

Payloads that fly on the shuttle rest upon modular containers called carriers. Kennedy Space Center per­ sonnel have generated a partially ordered hierarchy of tasks necessary to process the payloads and carriers be­ fore and after a shuttle flight. In addition, resource types and quantities required to accomplish these tasks have been determined. The anchor of a schedule in this do­ main is the launch date of the shuttle. The task queue is ordered so that post-launch tasks are scheduled first in chronological order (with respect to the partial or­ der) and pre-launch tasks are scheduled backwards from launch in reverse chronological order.

6.1 Efficiency Gain

The most significant advantage of delayed evaluation is its efficiency. If one were to propagate constraints in a straightforward manner, without delayed evaluation, many more filter checks would be performed. We have demonstrated this efficiency gain by applying our sys­ tem to the n-queens problem and to the EMPRESS-A scheduling problem with and without using delayed eval­ uation. To test without delayed evaluation, we simply redefined the head, tail and cons-stream operations so that they were car, cdr and cons, respectively. Then we compiled statistics on the total number of consistency checks made for finding the first acceptable solution. A consistency check occurs each time the program verifies that a variable's value is consistent with its constraints. In the n-queens problem, as the size of the problem in­ creases, so does the efficiency gain (see Figure 2). The improvement was on the order of 20 percent. 4 Figures 3 and 4 describe the problem size and illustrate the ben­ efit of using streams in the EMPRESS-A application. In general, representing possibilities as streams is most use­ ful when the average number of candidate values for a variable is large. In EMPRESS-A, this is realized when resource pool variables have many possible pools and temporal variables have many possible interval values.

6.2 Representational Advantages

Our system is highly extensible, can be used to represent infinite data structures and can be used to find adequate or optimal solutions to a problem.

4 The fluctuations in the results are due to the fact that some problems had initial streams that were serendipitously close to solutions.

Problems are specified in our system by defining con­ straints and attaching instances of the constraints to variables. Because the filtering mechanisms coordinate constraint behavior during propagation, the definition of each individual constraint is made independently of oth­ ers. When a vocabulary of constraints has been declared in a particular problem domain, users can extend and modify problems without programming, by using the constraint language to add and delete constraints. Fur­ thermore, the system can dynamically adapt to changes in a problem domain without modifying its search algo­ rithm by adding and retracting constraints. These char­ acteristics contribute to the modularity and extensibility of the system.

We have discussed the advantages of having the ability to represent infinite lists as streams. The transparency between list and stream operations also extends the rep­ resentational capabilities of our system by providing the ability to find optimal solutions to problems.

Although most problem spaces are so large that opti­ mization is unrealistic, our system can find optimal so­ lutions based on some metric. To optimize an assign­ ment, all of a variable's values must be considered and compared. In this case, delayed evaluation offers no sav­ ings. Many domains, however, require some variables to be optimally assigned while others can be assigned any acceptable value. We allow both options by defining different kinds of generators, stream-generators and list­ generators. The stream generators are used for satisfic­ ing and operate through the application of filters (using delayed evaluation). The list generators optimize and operate through the application of filters and compara­ tors - predicates that determine if one value is more de­ sirable than another. Without any significant change in the system's operations or representations, we are able to integrate the benefits of delayed evaluation into a CSP when satisficing.

7 Previous Work

Our implementation extends previous work in constraint satisfaction, planning and scheduling. The seminal work of Vere [Vere, 1983] represents actions by maintaining constraints between the start, finish, and duration of tasks. In our system, we can maintain arbitrary con­ straints between variables (e.g., resource constraints). We extend the constraint management mechanisms of non-linear planners like NonLin [Tate, 1977] and SIPE [Wilkins, 1984] by offering a uniform mechanism for constraint propagation over all variables. Like Dean's TMM [Dean, 1985], our system maintains information over time. However, the representation we use takes the resource perspective, that is, variables range over values that are not necessarily Boolean.

8 Conclusions and Future Work

We have implemented a system using a formulation of constraint satisfaction problems that is modular and takes advantage of delayed evaluation techniques.

The performance of the system improves significantly when it is applied to both EMPRESS-A scheduling and to n-queens with streams instead of lists representing the variables' domain of possible values.

Future goals of this project are to use explanation­ based learning techniques to learn heuristics that rec­ ognize resource bottlenecks and adjust the search pro­ cess accordingly, to build an efficient scheduling system, and to test the system against other NASA domains. This will provide a better analysis of the system since every scheduling problem has different constraints, dif­ ferent unknowns, different required optimality, and dif­ ferent levels of resource availability.

Acknowledgements

We thank Richard H. Brown for his invaluable ideas con­ cerning constraint satisfaction that have made this work possible. We also thank Melissa P. Chase for introduc­ ing us to delayed evaluation, Will Taylor for designing the user interface, James Allen, Walter Hamacher, Paul Morris, and Amy Lansky for their comments and sug­ gestions, and Mark Drummond, Phil Laird, and Peter E. Friedland for careful review of this paper.