CS4341 Introduction to Artificial Intelligence
Project 3 - D 2001
By Chris Shoemaker and Carolina Ruiz
DUE DATE: Friday, April 6 at 5 pm.
EXTENDED DUE DATE: Saturday, April 7 at 5 pm.
To understand Constraint Satisfaction Problems (CSP). To implement a
program that solves a constraint satisfaction problem. To understand how
to create a constraint network and to use binary constraint matrices.
The following is a generic scheduling problem.
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: 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: 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 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):
- 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 one of the following processors:
g, r, e.
- 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):
- 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 Project3 filename.txt" or
"runProject3 filename.txt". The file specified by the
argument has a specific format:
FYI: See a nice extension of this problem to an optimization problem
in the Additional Graduate Credit Problem.
The output of the system should be either:
- An assignment of processors to tasks such that all constraints are
satisfied (including the deadline constraint).
- The total length of tasks assigned to each processor.
- The total length of all tasks.
- A message stating that NO such assignment is possible, IF that's
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.
Your system must satisfy the following requirements:
- The internal representation of the problem should use a constraint net.
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.
- The problem solving strategy should be an implementation of the one
discussed in class:
- Arc consistency checking,
- Depth-first search with backtracking, and
- a sound heuristic to select the first variable and the order in which
other variables are expanded.
- 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 we
know how to run you system.
- Your program must adhere to the input and output specifications.
Along with your code, you must also submit code documentation. It must
follow the Departmental Documentation Standard (see http://www.cs.wpi.edu/Help/documentation-standard.html).
Project 3 is due at 5pm on April 6, 2001. One (and only one) member of
your group must submit the following files using the turnin
- the names of the members of your group
- instructions on compiling and running your program
- describe which tests you ran to try out your program. How did your
- describe the strengths and the weaknesses of your program.
- Remember, you should have sufficient, clear documentation, both external
to your program and internal to your program. This can do nothing
but help your grade. If no one can understand your code, and
something doesn't work, one can only assume that you did not understand
the problem well enough to code it clearly.
- Any ancillary files that your program requires, such as a script to run a
Let's extend the specification of the constraint satisfaction problem of this homework.
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
The file format is simply pairs of a lower case letter (processors, values in
the domain of the variables) and a non-negative integer, as shown:
Extend the constraint satisfaction system that you constructed for Project 3 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. Your program should also
display what the total cost is.