WPI Worcester Polytechnic Institute

Computer Science Department

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:

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:

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:

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:


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

  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.


Additional Graduate Credit Problem (20 points)

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