In Part I of the project you will implement a Constraint Satisfaction Solver.
It should be flexible enough to solve general CSPs. Read
the description of Part II of the project so that
you make sure you implement Part I in a way that will facilitate your work
on Part II.
Although your Constraint Satisfaction Solver should be flexible enough to solve
general CSPs, the description of Part I below uses a generic scheduling problem
as an illustration to motivate the different features of the Solver.
Assume that we need to execute n tasks using m processors
under certain constraints. It may help to think about these tasks as computer
processes, and processors as CPUs, but this could just as easily apply to
construction workers and jobs, or a software engineering management
problem. For simplicity, we'll use the following notation:
- Tasks (CSP variables):
The n tasks will be denoted by n upper case letters (e.g., A, T, E, G, .....);
- The "length" of each task is given. The length corresponds to the
number of seconds that it takes a processor to perform the task.
- Processors (Variables' domains): The m processors will be denoted by m
lower case letters
(e.g., p, w, f, s, ...).
Each of the processors performs the tasks assigned to it in a sequential manner.
Processors are independent from each other. There is no ordering of
tasks assigned to a processor, that is, you should not care in what order
tasks will be executed, only which processors will execute them.
- Constraints: The constraints are of the following sort:
- Deadline: A deadline d, given in seconds, is specified as a
constraint. All tasks must be executed before the deadline.
That is, each of the processors must be able to sequentially execute
all tasks assigned to it before the deadline.
All processors start executing the processes assigned to them at
time t = 0.
- Unary constraints (involving one variable). There are 2 types of unary constraints in this project:
- A task can only be assigned to one of a subgroup of processors.
For instance, the user may specify that task R can be performed by any one of the following processors:
g, r, OR e; but not by other processors not on this list.
- A task cannot be assigned to any in a given group of processors.
Example: task W can be assigned to neither f nor j.
- Binary constraints (involving two variables). There are 3 types of binary constraints in this project:
- Two given tasks need to be performed on the same processor.
- Two given tasks cannot be assigned to the same processor.
- Two given tasks cannot be simultaneously assigned to a given
pair of processors. For instance, the user can specify that
task D cannot be assigned to processor p if task E is assigned
to processor u. To be more specific, this constraint is regardless of
time, that is, all assignments take place before any tasks have been executed,
at time t = 0. If D is assigned to p, then E can not be assigned to u, even if the two tasks could be executed at different times.
Your program (or a script accompanying your program) must accept a
filename as a one command-line argument. For example, you might run
your program by typing "java Project filename.txt" or
"runProject filename.txt". The file specified by the
argument has a specific format, which is defined below (see an example in the next section below):
- The file has eight sections.
- Each section begins with a line that begins with "#####".
This line may contain comment information, which your program must
ignore. For example, one of the beginning markers may be:
"##### -- This section contains unary inclusion constraints."
- Therefore, there will be 8 section beginning lines.
- The eight sections are each described below:
- names and lengths of tasks
- The beginning of this section is signaled by a single line
that begins with
"#####".
- Tasks are named by a single upper case letter.
- Remember that tasks are the "variables" in the
constraint satisfaction problem.
- Each line in this section contains the name of a task,
followed by one space, followed by the length of the task, in
seconds.
- The length of each task is a positive integer.
- An example line would be "Y 4". This means
that there exists a task Y, and its length is 4 seconds.
- names of processors
- The beginning of this section is signaled by a single line
that begins with
"#####".
- Processors are named by a single lower case letter.
- Remember that processors are the "domain of the
variables" in the constraint satisfaction problem.
- Each line in this section contains only the name of a
processor.
- An example line would be "w". This means that
there exists a processor, w.
- deadline
- The beginning of this section is signaled by a single line
that begins with
"#####".
- The deadline is a special constraint that is particular to the
scheduling constraint satisfaction problem.
- The sum of the lengths of all tasks that are assigned to the
same processor must be less than the deadline time.
- The deadline is an integer.
- An example line would be "24". This means that
the deadline is 24 seconds.
- unary constraints
- Unary constraints contain only one variable (task).
- There are two kinds of unary constraints: inclusive and
exclusive.
- In order to make the constraints easier to parse, the two
different kinds of unary constraints are separated.
- Inclusive unary constraints
- The beginning of this section is signaled by a single line
that begins with
"#####".
- Inclusive unary constraints are specified by a
variable (task), and a list of values (processors).
- The inclusive unary constraints mean that the variable
must be assigned one of the values.
- An example line would be "E d e g a".
This means that the value assigned to task E must be either
d or e or g or a.
- Exclusive unary constraints
- The beginning of this section is signaled by a single line
that begins with
"#####".
- Exclusive unary constraints are also specified by a
variable (task), and a list of values (processors).
- The exclusive unary constraints mean that the variable
must not be assigned one of the values.
- An example line would be "W r q g".
This means that the value assigned to task W must be neither
r nor q nor g.
- binary constraints
- Binary constraints contain two variables (tasks).
- There are three kinds of binary constraints: equal, not equal,
and not simultaneous.
- Equal binary constraints
- The beginning of this section is signaled by a single line
that begins with
"#####".
- Equal binary constraints are specified by two
variables (tasks).
- The equal binary constraints mean that the two
variables (tasks) must be assigned the same value
(processor).
- An example line would be "Y Q". This
means that the same value must be assigned
to both Y and Q.
- Not equal binary constraints
- The beginning of this section is signaled by a single line
that begins with
"#####".
- Not equal binary constraints are also specified by
only two variables (tasks).
- The not equal binary constraints mean that the two
variables (tasks) must be assigned different
values (processors).
- An example line would be "W A". This
means that the W and A must not be assigned to
the same value.
- Not simultaneous binary constraints
- The beginning of this section is signaled by a single line
that begins with
"#####".
- Not simultaneous binary constraints are specified by
two variables (tasks) and two processors.
- The not simultaneous binary constraints mean that a
particular pair of assignments of values to
variables must not be made. (This
constraint says nothing about the individual
assignments. In particular, either assignment may
be allowed, as long as the pair of both
assignments are not made.)
- An example line would be "W A j s".
This means that the W must not be assigned j if
A is assigned s; and A must not
be assigned s if W is assigned j.
- A sample file is included below:
Sample Input File 1
##### - variables
C 6
D 3
E 5
F 8
G 15
H 12
I 7
J 19
K 4
L 9
##### - values
p
q
r
x
y
z
##### - deadline constraint
22
##### - unary inclusive
D q r
G p r y z
##### - unary exclusive
C q r
E z
L y p
##### - binary equals
C D
E F
##### - binary not equals
C G
##### - binary not simultaneous
E G p z
- This file describes a scheduling constraint satisfaction problem
that has 10 tasks and 6 processors, with a deadline of 22 seconds.
- The unary constraints are that
- variable D must be assigned either value q or r;
- variable G must be assigned values p, r, y, or z;
- variable C must be assigned neither value q nor r;
- variable E must not be assigned value z;
- variable L must be assigned neither value y nor p.
- The binary constraints are that
- variable C must be assigned the same value as variable D;
- variable E must be assigned the same value as variable F;
- variables C and G cannot be assigned the same value;
- the assignment of value p to variable E and (simultaneously)
the assignment of value z to variable G is not allowed.
As stated above, each input file has 8 sections, even if some of the sections
are empty. For instance, the following input file there are no "unary exclusive"
or "binary not simultaneous" constraints:
- Another sample file is included below:
Sample Input File 2
##### - variables
C 6
D 3
E 5
F 8
G 15
H 12
I 7
J 19
K 4
L 9
##### - values
p
q
r
x
y
z
##### - deadline constraint
22
##### - unary inclusive
D q r
##### - unary exclusive
##### - binary equals
C D
E F
##### - binary not equals
C G
##### - binary not simultaneous
-
Several other test files will be made available during the course of the project.
Students are encouraged to share their test files and I'll post them here for everyone to use.
The output of the system should contain the following:
-
Either:
- Case 1: When there is at least one solution to the CSP:
- An assignment of processors to tasks such that all constraints are
satisfied (including the deadline constraint), and
- The total length of tasks assigned to each processor, and
- The total length of all tasks.
- Case 2: When there is no solution to the CSP:
- A message stating that NO such assignment is possible, IF that's
the case.
- In addition to the above, your output must provide a trace of the
steps followed by your program in order to solve the input problem. That
is, it keeps track of what variable was selected at each step of the search,
in what order the values were tried, how arc consistency propagated
constraints, what backtracking took place, etc.
Design and implement a constraint satisfaction system that
produces an assignment of processors to tasks which satisfies all
constraints (including the deadline constraint), if such an assignment exists.
You can implement your program in any programming language, for instance,
Python, Java, C, C++, Prolog, Lisp, ... (in case of doubt, ask me).
Your system must satisfy the following requirements:
- The internal representation of the problem should use a constraint graph.
Note that the variables in this problem are the tasks
and the domain of each of the variables is the set of all processors.
- Binary constraints should be represented using constraint matrices.
Each constraint matrix is an m-by-m matrix. For instance, the following
constraint matrix represents the constraint among the variables C and G
in the Sample Input File 1 shown above. Note that the matrix contains
G's "unary inclusive" constraint,
C's "unary exclusive" constraint, and
C and G's "binary not equals" constraint.
| C\G | p | q | r | x | y | z
|
| p | 0 | 0 | 1 | 0 | 1 | 1
|
| q | 0 | 0 | 0 | 0 | 0 | 0
|
| r | 0 | 0 | 0 | 0 | 0 | 0
|
| x | 1 | 0 | 1 | 0 | 1 | 1
|
| y | 1 | 0 | 1 | 0 | 0 | 1
|
| z | 1 | 0 | 1 | 0 | 1 | 0
|
- The problem solving strategy should be an implementation of the CSP
strategies and methods discussed in class and in the textbook:
- An effective search method:
- CSP's backtracking search
- Sound heuristic(s) to select the order in which the variables are expanded:
- Minimumim remaining values (MVR) heuristic, breaking ties with the
degree heuristic
- Sound heuristic(s) to select the order in which the values are considered:
- Least-constraining-value heuristic
- Constraint Propagation:
- Arc consistency checking (use the AC-3 or the AC-4 algorithms)
More precisely: the project requires that you implement the Backtracking-Search algorithm is provided in Fig. 6.5 (p. 215) of the textbook. Section 6.3 describes it in detail. In particular:
- You MUST write YOUR OWN code in any high level programming language.
You MUST include a short user's manual with your submission so that I
know how to run you system.
- Your program must adhere to the input and output specifications.
Let's extend the specification of the constraint satisfaction problem of this
project.
Your program now accepts a second filename specified by a second command-line
argument. This file contains costs associated with using each of the processors. The cost
will represent the amount of dollars charged for using the processor during one second. That is, if a task
W uses the processor d for 12 seconds and the cost of using d is $10/sec then the total charge
for task W will be
$120.
The file format is simply pairs of a lower case letter (processors, values in
the domain of the variables) and a non-negative integer representing the cost per one second, as shown:
x 34
y 22
z 10
p 0
q 2
r 12
Extend the constraint satisfaction system that you constructed to
output an optimal assignment of processors
to tasks, that is an assignment that satisfies all constrains and that
minimizes the total cost of executing the tasks. Note that a greedy approach
usually doesn't produce optimal solutions. Your program should also
display what the total cost is. Include the description of this code in your
written report and also include the code in your project submission.
