Assignment 4: Constraint Satisfaction Problems

CS 440

Fall 2015

 

Due: November 1st, 2015 by 11PM MDT

 

Part 1: Coding [75 pts]

 

The purpose of this assignment is 1) to have you formulate a constraint satisfaction problem and 2) to require you to read and understand the Python implementation of some of the algorithms from the course textbook.

 

A: Solving problems with hard constraints with the Min_Conflicts CSP method

 

Your task is to create a classroom schedule for undergraduate CS classes and their lab sections.  The courses with their lab sections are:

á      cs160 with labs cs160A, cs160B, cs160C and cs160D

á      cs161 with labs cs161A, cs161B, cs161C and cs161D

á      cs200 with labs cs200A and cs200B

á      cs253 with labs cs253A and cs253B

á      cs270 with labs cs270A and cs270B

 

Courses must be assigned to a time slot in the room CSB130. Lab sections may be assigned to CSB215 or CSB225. All courses and lab sections meet for 1 hour.  The available time slots are: 9, 10, 11, 12, 1, 2, 3, 4.

 

A classroom schedule should respect the following constraints:

á      A course cannot meet at the same time as any of its labs.

á      Courses cs200 and cs270 have the additional requirement that they cannot meet at the same time and their lab sections must not meet at the same time as either course.

á      Two courses or labs cannot meet in the same room at the same time.

á      A course must be scheduled in CSB130; a lab section can be scheduled in either CSB215 or CSB225.

 

A solution is a Python dictionary, where the keys are each class/lab that needs to be assigned, and the values are a tuple containing the classroom and time scheduled.

For example: {'cs200A': ('CSB225', 9), 'cs161C': ('CSB225', 4), 'É 'cs253': ('CSB130', 3)}.

 

Your code should include a display function that will report the number of conflicts existing in the current schedule and format the schedule according to the rooms as in:

 

# of conflicts in schedule:  ??

      CSB 130  CSB215  CSB225

-----------------------------

 9 |  #####    #####   #####

10 |  None     #####   #####

11 |  #####    #####   #####

12 |  None     #####   #####

 1 |  None     #####   #####

 2 |  #####    #####   None

 3 |  #####    #####   #####

 4 |  #####    #####   None

 

where ?? should be replaced with the number of conflicts, ##### is one of the courses/labs (cs160, cs160A etc.); a None denotes that the room was not scheduled at the corresponding time.

Use the min_conflicts function from the Russell & Norvig csp.py module to solve the problem (see https://code.google.com/p/aima-python/).  To use of this function you will need to create a subclass of the class CSP from csp.py that models the specifics of the problem.  Make sure you use the latest version of csp.py – the zip file provided on the website is an old one.  The code follows the pseudo-code provided in the book. You are allowed to make changes to csp.py, but if you do so, include any modified code in your module.

 

B:  Solving CSPs with soft constraints

 

Once you can solve a CSP with hard constraints, address the problem of handling soft constraints, i.e. preferences.  To handle preferences, have your nconflicts method, which counts constraints, count the number of conflicts in the current assignment.  Hard constraints should each be counted as 2, soft constraints should be counted as 1. The only soft constraint is:

á      A lab section should be held in a time slot adjacent to the course (e.g., if cs200 is at noon, its two labs should be held at 11 or 1)

 

 

Part 2: Discussion [25 pts]

 

Write a short essay (~1 page single spaced in 10 or 11 pt font) in answer to the following:

1.     Experiment with different numbers of max_steps for min_conflicts. Do you always get the same answer? How many steps are needed to get good solutions for part A? How many are needed for Part B? Why or why not does the number of steps vary?

2.     Do you think min_conflicts is a good approach to solving this CSP? Why or why not?

3.     Describe/explain how you incorporated the constraints. Comment on how soft constraints were incorporated. What are the pros/cons of this approach?  Given an instance to the problem where solution to the hard constraints version is known to exist, is the soft constraint version guaranteed to find it?  Can you think of a better way of modeling them?

 

Relation to Assignment 3

 

None.

 

What to Hand In

1.     A python file called classroomSched.py which includes all the python code needed to run your program.  You can import and use the Russell & Norvig code, and you can assume that such an import will be successful when we test your code.  If you find it necessary to make any modifications to csp.py, then any modified functions/classes should be included in your submission. At the end of your file should be the following code for testing it:

if __name__ == '__main__':

      schedule = makeSchedule()  

      # should return a dictionary that specifies the schedule as

      #described above when using hard constraints

      display(schedule)

      # print the schedule in the format described above

      schedule2  = makeScheduleWithSoftConstraints()

      # same as makeSchedule, except utilizing soft constraints

      display(schedule)

For the hard constraints version of the problem if the solver is not able to find a solution with no conflicts the return value should be ÒNoneÓ.

2.     A pdf file with your answers to part 2. The file should be named Òessay_<YourName>.pdfÓ

We will run your code by calling the three methods makeSchedule(), makeScheduleWithSoftConstraints() and display(schedule).

 

Make sure this will work on department machines and include comments in your functions and classes.