WPI Worcester Polytechnic Institute

Computer Science Department

CS534 Artificial Intelligence 
Project - Fall 2005


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:

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:

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 CSP strategies and methods discussed in class and in the textbook:
  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.
  5. Your program must adhere to the input and output specifications.

Project Submission:

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

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.