Rob Kremer
	Room Allocation Problem CPSC 433: Artifical Intelligence Winter 2006	Computer Science

• Problem Description
  • Hard Constraints
  • Soft Constraints
• Input/Output Formats
• Parser
• Sample Input

Problem Description

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

Hard Constraints

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.

Soft Constraints

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

Input/Output Formats

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 ingored (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.

Parser

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

• Test: Not much more than a main() method that takes an input filename and a time limit Build on it as your main() program.
• Predicate: The class the encapsulates a predicate as a ADT.
• PredicateReader: The class that does most of the work of parsing a file or a predicate string. Your input reader should extend this class.
• Pair: Simple utility class representing a pair.
• Entity: Basically just a "named thing". The superclass for predicate reader.
• TAallocationPredicates: An interface that defines templates for all the predicates needed in the assignment. Your input reader should implement this interface.

(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).

Sample Input

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:

The following is the solution suggested to the above problem. My utility function rates its utility at 0.

CPSC 433: Artificial Intelligence

Last updated 2006-11-27 9:25

Rob Kremer