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

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

Problem Description

The assignment is based on the Sisyphus I problem solving process modeling problem as used in the knowledge accusation community in the KAW series of workshops and other workshops and conferences. The problem has been reformulated (specialized, actually) to be a search problem for the purposes of this course.

The task is to assign office workers to offices, maximizing the happiness of the workers and convenience of the work environment (both of which are, of course, important for worker productivity). There are a large number of factors which our model uses to measure the "goodness" of a solution. These are modeled as constraints.

Hard Constraints

There are a few mandatory constraints that may not be violated. Any room assignment that violates these is not considered a solution. These are:

//everyone is assigned a room
FORALL p:person . EXISTS r:room . assigned-to(p,r)

// no person is assigned more than one room
FORALL p:person . ~ EXISTS r,s:room | r /= s . assigned-to(p,r) /\ assigned-to(p,s)

// not more than 2 people to a room
FORALL r:room . ~ EXISTS x,y,z:person | x /= y /\ x /= z /\ y /= z . assigned-to(x,r) /\ assigned-to(y,r) /\ assigned-to(z,r)

//project heads, group heads, and managers can't share a room with anyone else
FORALL h:person, g:name | heads-project(h,g) \/ heads-group(h,g) \/ manager(h) . ~ EXISTS p:person, r:room | p /= h . assigned-to(p,r) /\ assigned-to(h,r)

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

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: (Yellow highlighting indicates recent changes.)

file	::=	{ predicate \n }*
predicate	::=	predicateName ( params )
params	::=	value {, value }*
			//	-- Parameter List --
predicateName	::=	person	//	name
	::=	room	//	room-name
	::=	project	//	project-name
	::=	group	//	group-name
	::=	role	//	name
	::=	smoker	//	name
	::=	hacker	//	name
	::=	group \| in-group	//	name, group-name
	::=	project \| in-project	//	name, project-name
	::=	heads-group	//	name, group-name
	::=	heads-project	//	name, project-name
	::=	works-with	//	name, name
	::=	works-with	//	name, name-set
	::=	assigned-to	//	name, room-name
	::=	large-project	//	project-name
	::=	close	//	room-name, room-name
	::=	close	//	room-name, room-name-set
	::=	room-size	//	room-name
role	::=	secretary \| manager \| researcher
room-size	::=	small-room \| medium-room \| large-room

value	::=	name \| room-name \| project-name \| group-name \| set
name	::=	" {char}+ "
	::=	letter {letter-or-digit }*
set	::=	{ {name {, name}*} }
room-name	::=	name
project-name	::=	name
group-name	::=	name

There are also a few inference rules that you must observe when reading input files. These may be hard-coded if you wish.

close(x,y)	:-	close(y,x)	// close() is symmetric
works-with(x,y)	:-	works-with(y,x)	// works-with() is symmetric
works-with(x,s)	:-	works-with(y,x), all y in s	// works-with() is symmetric (list version)
group(x,y)	:-	heads-group(x,y)	// the head of a group is a member of the group
project(x,y)	:-	heads-project(x,y)	// the head of project is a member of the project

// these let you assume the type of an identifier
person(x)	:-	role(x)
person(x)	:-	smoker(x)
person(x)	:-	hacker(x)
person(x)	:-	project(x,y)
project(x)	:-	project(y,x)
person(x)	:-	works-with(x,s)
person(x)	:-	works-with(y,s), all x in s	// list version
person(x)	:-	heads-group(x,y)
group(x)	:-	group(y,x)
person(x)	:-	heads-project(x,y)
person(x)	:-	group(x,y)	// corrected from "project(x) :- group(y,x)
room(x)	:-	close(x,y)
room(x)	:-	close(y,x)
room(x)	:-	room-size(x)
person(x)	:-	assigned-to(x,y)
room(x)	:-	assigned-to(x,y)

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.
SisyphusPredicates: 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 assigned-to(name,room-name) predicate (and perhaps comments).

Sample Input

You can use the following sample text as a test suite for your program. It is the problem described in the Sisyphus I problem description. You will be tested on other scenarios.

// the YQT group staff descriptions
researcher(Werner)
group(Werner, YQT)
project(Werner, RESPECT)
hacker(Werner)
works-with(Werner, {Angi, Marc})

researcher(Jurgen)
group(Jurgen, YQT)
project(Jurgen,EULISP)
hacker(Jurgen)
works-with(Jurgen,{Harry, Thomas})

researcher(Marc)
group(Marc, YQT)
project(Marc, KRIPTON)
hacker(Marc)
works-with(Marc,{Angi, Werner})

researcher(Angi)
group(Angi, YQT)
project(Angi, RESPECT)
works-with(Angi, {Marc, Werner})

researcher(Andy)
group(Andy, YQT)
project(Andy,TUTOR2000)
smoker(Andy)

researcher(Michael)
group(Michael, YQT)
project(Michael, "BABYLON Product")
hacker(Michael)
works-with(Michael,{Hans})

researcher(Harry)
group(Harry, YQT)
project(Harry, EULISP)
hacker(Harry)
works-with(Harry,{Jurgen, Thomas})

researcher(Uwe)
group(Uwe, YQT)
project(Uwe, "Autonomous Systems")
smoker(Uwe)
hacker(Uwe)

researcher(Thomas)
group(Thomas, YQT)
heads-group(Thomas, YQT)
project(Thomas, EULISP)
works-with(Thomas,{Jurgen, Harry})

secretary(Monika)
group(Monika, YQT)
works-with(Monika,{Thomas, Ulrike, Eva})

secretary(Ulrike)
group(Ulrike, YQT)
works-with(Ulrike,{Thomas, Monika, Eva})

researcher(Hans)
group(Hans, YQT)
project(Hans, "BABYLON Product")
heads-project(Hans, "BABYLON Product")
smoker(Hans)
works-with(Hans,{Michael})

manager(Eva)
group(Eva, YQT)
works-with(Eva,{Thomas, Ulrike, Monika})

researcher(Joachim)
group(Joachim, YQT)
project(Joachim, ASERTI)
heads-project(Joachim, ASERTI)

researcher(Katharina)
group(Katharina, YQT)
project(Katharina, MLT)
heads-project(Katharina, MLT)
smoker(Katharina)
hacker(Katharina)

// project descriptions
large-project("Babylon Product")
large-project(ASERTI)
large-project(MLT)

// room sizes
small-room (C5113)
small-room (C5114)
small-room (C5115)
small-room (C5116)
large-room(C5117)
large-room (C5119)
large-room (C5120)
medium-room (C5121)
medium-room (C5122)
medium-room(C5123)

// room proximity
close(C5113, C5114)
close(C5113, C5115)
close(C5114, C5115)
close(C5114, C5116)
close(C5115, C5116)
close(C5115, C5117)
close(C5116, C5117)
close(C5117, C5119)
close(C5119, C5120)
close(C5119, C5121)
close(C5119, C5122)
close(C5120, C5121)
close(C5121, C5120)
close(C5121, C5122)
close(C5123, C5122)

The following is a solution suggested to the above problem in the Sisyphus I problem description. My utility function rates its utility at -407.

assign-to(Andy, C5113)
assign-to(Angi, C5113)
assign-to(Eva, C5114)
assign-to(Hans, C5115)
assign-to(Harry, C5116)
assign-to(Joachim, C5117)
assign-to(Jurgen, C5116)
assign-to(Katharina, C5119)
assign-to(Marc, C5120)
assign-to(Michael, C5123)
assign-to(Monika, C5121)
assign-to(Thomas, C5122)
assign-to(Ulrike, C5121)
assign-to(Uwe, C5123)
assign-to(Werner, C5120)
// Attributes: complete, solved, utility=-407, 15/15 people assigned.
// searched 229878 nodes, including 8070 solved leaves, 0 unsolved leaves, 5748 dead-end internal nodes.
// seach time = 33s
// Const    #     Pen    Total
// -----    ---    ---    -----
// 1        : 1      * -40    = -40
// 2        : 9      * -2     = -18
// 5        : 1      * -20    = -20
// 6        : 1      * -20    = -20
// 7        : 9      * -2     = -18
// 8        : 1      * -5     = -5
// 9        : 1      * -10    = -10
// 10       : 1      * -10    = -10
// 11       : 2      * -50    = -100
// 12       : 2      * -7     = -14
// 14       : 10     * -4     = -40
// 15       : 4      * -3     = -12
// 16       : 4      * -25    = -100
//                              -----
//                              -407

CPSC 433: Artificial Intelligence

Last updated 2013-01-10 21:41

Rob Kremer