  ### CS534 Artificial Intelligence Project - Fall 2005

#### PROF. CAROLINA RUIZ

Due Date: December 5th, 2005 at 6 PM #### Project Goal:

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.

#### Project Assignment: (25% of course grade)

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.

#### Input Specifications:

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:
• 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 it's 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.
• 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.
1. 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.
2. 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.
1. 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.
2. 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.
3. Not simultaneous binary constraints
1. The beginning of this section is signaled by a single line that begins with "#####".
2. Not simultaneous binary constraints are specified by two variables (tasks) and two processors.
3. 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.)
4. An example line would be "W A j s".  This means that the W must not be assigned j if A is assigned s.  Conversely, A must not be assigned s if W is assigned j.
• Several test files contributed by your classmates can be found here.
• An example file is here.
```##### - 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
22
##### - unary inclusive
D q r
##### - unary exclusive
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 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; the assignment of value p to variable E and (simultaneously) the assignment of value z to variable G is not allowed.

#### Output Specifications:

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.

OR

• A message stating that NO such assignment is possible, IF that's the case.

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:

1. 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.
2. Binary constraints should be represented using constraint matrices. Each constraint matrix is an m-by-m matrix.
3. The problem solving strategy should be an implementation of the CSP strategies and methods discussed in class and in the textbook:
• Arc consistency checking (use the AC-3 or the AC-4 algorithms),
• an effective search method,
• a sound heuristic to select the order in which the variables are expanded, and
• a sound heuristic to select the order in which the values are considered.
4. 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.

#### Project Submission:

Along with your code, you must also submit a written report.

• Program.
• Email me the source code for your program and ancillary files that your program requires, such as a script to run a language interpreter, IF ANY, before the project deadline. Your code should be fully documented and easy to read.

• Written Report
2. instructions on compiling and running your program
3. detailed description of your approach. That is, what search method and what heuristics were used, how was AC employed, etc. Please try to describe your approach in an algorithmic manner (i.e., include pseudo-code of the overall approach).
4. results:
• describe which tests you ran to try out your program. How did your program perform?
• describe the strengths and the weaknesses of your program.
5. 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.

#### In-Class Presentations:

Each student will have up to 8 minutes to discuss his/her project in class. Prepare slides for your presentation. Try to highlight the most important and novel parts of your work (a maximum limit of 8 minutes per presentation will be enforced). We'll have project presentations on Dec. 5th and Dec. 12th. The order in which the students will present will be selected at random during those classes. Your presentation will count for 10% of your project grade.

#### Optional Part - Extra Credit (5% extra)

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, 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.  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.