CPSC 433: Artifical Intelligence Fall 2013 |
The assignment is based on the department's on-going problem of allocating graduate student TAs for undergraduate lab and tutorial sessions (called simple "labs" from now on).
The task is to assign graduate TAs to each of the undergrad lab, maximizing the happiness of the TAs. There are a large number of factors which our model uses to measure the "goodness" of a solution. These are modeled as constraints.
A few simple relations are defined:
instructs: TA -> Lab ; instructs(ta,lab) means TA ta is assigned to Lab lab.
lab-count: TA -> int ; lab-count(ta,n) means TA ta has exactly n distinct instances of instructs(ta,lab).
There are a few mandatory constraints that may not be violated. Any TA assignment that violates these is not considered a solution. These are:
//every TA is assigned at most MAX_LABS labs
FORALL ta:TA . lab-count(ta) <= MAX_LABS)
//every TA is assigned at least MIN_LABS labs (if the TA *has* a lab
assignment)
FORALL ta:TA . lab-count(ta)/=0 -> lab-count(ta) >= MIN_LABS)
// no lab has more than one TA assigned to it
FORALL course:Course, lab:Lab | has-lab(course,?,lab) . ~ EXISTS
ta1,ta2:TA | ta1/= ta2 . instructs(ta1,lab) /\ instructs(ta2,lab)
//every lab has a TA assigned to it
FORALL course:Course, lab:Lab | has-lab(course,?,lab). EXITS ta:TA .
instructs(ta,course,lab)
//no TA is assigned simultanious labs
FORALL ta:TA, c1,c2:Course, b1,b2:Lab | (c1=c2 => b1 /= b2) /\
instructs(ta,c1,b1) /\ instructs(ta,c2,b2) . ~ EXISTS t1,t2 | at(c1,b1,t1)
/\ at(c2,b2,t2) . conflicts(t1,t2)
//no TA is assigned a lab that conflicts with his/her own courses
FORALL ta:TA, course:Course, lab:Lab | instructs(ta,course,lab) .
((~ EXISTS c:Course, lec:Lecture |
taking(ta,c,lec) . EXISTS t1,t2 | at(course,lab,t1) /\ at(c,lec,t2)) .
conflicts(t1,t2)) /\
((~ EXISTS c:Course, b:Lab | taking(ta,c,b) .
EXISTS t1,t2 | at(course,lab,t1) /\ at(c,b,t2)) . conflicts(t1,t2)))
where:
lab-count(TA) is a function that returns the
number of labs a TA instructs.
There are also a large number of "soft" constraints that may be violated (and since some of these constraints actually conflict with each other, sometimes must be violated). These all have a penalty associated with them (reflecting their importance). Your job is to come up with a solution that maximizes the utility function that naturally arises from these soft constraints and their penalty weightings. I have, of course, written my own version of this utility function that (I believe) precisely conforms to the these constraints, and I will test your program's solutions against my utility function. You will have to write your own utility function to test your program.
The soft constraints are available in PDF, Apple Pages .pages format, Microsoft Word .doc format, and RTF. You will note that some of the formal semantics in the soft constraints table are omitted. These should be filled in on the table and the complete table should be submitted as an appendix to your group paper.
The input and output file formats are the same, namely, a set of ASCII-format predicates, one per line. The BNF for this format is:
|
There are a few input constraints you must observe. Otherwise the offending input predicate should be ignored (with an appropriate error message to stderr, of course):
|
There are also a few inference rules that you must observe when reading input files. These may be hard-coded if you wish.
|
You will be pleased to learn that I have saved you the effort of writing a parser for the file format. See the JavaDoc documentation. You can download the following JAVA classes: :
(or download them all in a jar file which includes the .class files and manifest as well).
It is highly recommended that you use this parser for your
assignment, as it will save you a lot of trouble, it works, and might
avoid some possible problems with your assessment and demos. These classes
make use of the JAVA reflect package, so that you need only define
methods a_predicateName()
(to assert a predicate as
true) and/or e_predicateName()
(to evaluate the
truth value of a predicate). Your methods must also, of course, support
the appropriate parameter list. You may define additional predicates if
you wish, but the assessment will only require you to interpret the
predicates listed here. Be warned that the only predicate type
expected in your output file is the instructs(TA-name,course-name,lab-name)
predicate (and perhaps comments).
You can use the following sample texts as a test suite for your program. You will be tested on other scenarios.
There is a long case (and an easier version and a solution), and a trivial case:
minlabs(2) // Time slots
course(CPSC231) senior-course(SENG411) senior-course(CPSC433) grad-course(LING601)
instructor(Kremer) // TAs taking(Heard,LING601,L01) // Instructor prefers |
The following is the solution suggested to the above problem. My utility function rates its utility at 0.
instructs(Heard,CPSC433,B01) |
Last updated 2010-03-15 5:42 |