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. 

• Project Goal
• Project Assignment
• Input Specifications
• Output Specifications
• Your Code
• Project Submission
• Graduate Credit Problem

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:

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:

• 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.
  • 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.
      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.
• 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
  ##### - deadline constraint
  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.

FYI: See a nice extension of this problem to an optimization problem in the Additional Graduate Credit Problem.

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.

Your Code:

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 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.
     
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 we know how to run you system.
   
5. Your program must adhere to the input and output specifications.

Project Submission:

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 program:

• Documentation

1. the names of the members of your group
2. instructions on compiling and running your program
3. 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.
4. 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.

• Program.  
  1. The source code for your program
  2. See more information about the turnin command on http://cs.wpi.edu/Help/turnin.html

• Any ancillary files that your program requires, such as a script to run a language interpreter.

Additional Graduate Credit Problem (20 points)

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