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.