================================
REPORT FOR OCTOBER-DECEMBER 2003
================================

MAIN TASKS:
Optimal space allocation (Thuc Vu, Greg Jorstad)
E-mail understanding (Bob Frederking, Richard Wang)
AutoCad data extraction (Ulas Bardak)
Design of domain representation and negotiation module
  (Eugene Fink, Greg Jorstad, Ulas Bardak)

OPTIMAL SPACE ALLOCATION

We have implemented a simple optimizer mechanism for assigning users
to offices based on their constraints. The optimizer uses simulated
annealing to minimize the number of unsatisfied constraints. The
initial version is based on a very simple representation of the
available space and user constraints; in particular, it does not allow
soft preferences or assignment of different importance levels to
different constraints. We plan to implement a more general optimizer,
and we will also experiment with commercially available constraint
solvers, such as ILOG.

E-MAIL UNDERSTANDING

We have developed a preliminary mechanism for processing natural
language e-mails with requests for office space. The mechanism is
based on the Klinger system, designed by William Cohen, which uses
domain-specific rules to identify relevant information in a natural
language text. We have developed rules for identifying key data in
space requests, such as a requester name, building names, floors,
office sizes, relative locations of offices, dates, and purposes of
using requested offices. The system identifies names even if they are
not capitalized, and it also identifies scopes of negations, such as
"not on the third floor." We have created a web server that allows
other Radar members to test the e-mail processing system by applying
it to their e-mails. We have run pilot experiments with the system,
using a set of 120 unseen e-mails; these experiments have shown that
the system's accuracy is about 75%.

AUTOCAD DATA EXTRACTION

ve developed a preliminary procedure for extracting office-space
information from the graphical AutoCad representation. Since we have
AutoCad maps for most buildings, we expect that this procedure will
help to create detailed building representations for the Radar system.
The procedure identifies offices and their numbers in AutoCad maps,
distinguishes offices from other objects (such as corridors and
stairs), and determines sizes of rectangular offices, but it cannot
yet determine sizes of offices with more complex shapes. We plan to
continue work on this procedure, improve the size computation, and add
a mechanism for determining distances between offices.

OTHER TASKS

We are currently working on a mechanism for representing (1) available
office space and related resources, (2) uncertain knowledge of user
preferences, and (3) communications with users. We are also working on
an initial design of mechanisms for preference elicitation, negotiation
with users, and high-level planning of the system's actions. We have
searched related literature, and developed a preliminary specification
of these modules and interactions among them; however, we have not yet
finished the design, and we have not begun the implementation. We have
implemented a canned demo that illustrates the main steps of space
allocation; however, this demo is very limited, and it cannot run on
unseen examples.