======================================================================

CS 4611 and CS 7611
AI Problem Solving
Spring 2005

Project 1: Diagrams Representation and Retrieval

Assigned: Feb. 14, 2005
Due: Mar. 7, 2005 (in class)

Note: No extensions will be granted but incomplete projects will be
graded for partial credit. So please, PLEASE start early.

----------------------------------------------------------------------

Introduction:

As we discussed in the class, the three projects in this class pertain
to diagrammatic knowledge and reasoning. The first project will diagram
to examine issues in case representation and case retrieval; the second
to investigate issues in analogical transfer; and the third to explore
problems in learning an memory organization. Thus, succeeding projects
will directly build on preceding ones.


Goals:

The goals of the first project are to (i) draw simple diagrams like
emoticons in weblounges representing emotions such as neutral, happy,
sad, flirting, angry, and so on, (ii) represent the diagrams and build
a library of diagrams, (iii) develop a method for retrieving the
diagram most similar to an input diagrammatic query. At the end, the
program should be able to take any diagram in the emoticon space and
retrieve the most similar diagram in the computer-based library.

Drawing Diagrams:

Use XFIG, a vector graphics program, to draw simple diagrams of
emoticons.  Use only simple geometric objects in the drawings such as
lines and rectangles, arcs and circles. Please make sure that you draw
at least half dozen diagrams for seeding the diagram library.

Representing the Diagrams:

XFIG will produce internal representations of the diagrams you draw in
the form of a text file. Extract these representations from these text
files (see XFIG notes, below) and build semantic networks for each
diagram you draw. This means that you will need to write a program for
building the semantic networks. Extracting the diagram representations
will take some work; this is the hard part in this project.

Building a Diagram Library:

For this project, organize the diagrams in a simple, flat array.
In the third project, we will return to this issue.

Retrieving the Most Similar Diagram:

Develop a nearest neighborhood algorithm for retrieving the diagram
most similar to an new input diagram.

Evaluating the Design:

You may evaluate the design of your computer program by giving it new
diagrams as input and checking if it retrieves the most similar
diagram in the library as output. Please evaluate your program for at
least half dozen new queries.

Storing New Diagrams:

As a new diagram is given as input and the program retrieves the most
similar diagram as output if the input and output are not identical,
then the program should store the new diagram in the library as
another entry.

----------------------------------------------------------------------

Languages and Environments:

We encourage you to use Lisp for this project. However, you may use C++
or Java if you wish.  It is required that your software run on either
helsinki.cc.gatech.edu or gaia.cc.gatech.edu, so that it will be
possible to test your submission.  If this is a problem for some reason,
please contact the TA to work something out.

----------------------------------------------------------------------

Deliverables:

You want to deliver (a) the computer program and the test results, and
(b) a brief design critique that documents the design of your program
and critiques based on the experimental results.

Please submit the design critique in hardcopy, in class.
Please submit your software, along with the inputs you used for
testing and the inputs used for seeding your library in a single
tar file emailed to the TA (jkj@cc).  The tar file should also
contain a readme describing how to build/run your code.

For the email portion of the submission, please use a subject of
'CS4611 Project 1 Submission'.  Please put your full name in the body
of the email somewhere (some email addresses do not reflect your name,
such as prism addresses).

----------------------------------------------------------------------

Notes on XFIG:

XFIG is a freeware vector graphics drawing program, freely downloadable.
The website for the program is here:

  http://www.xfig.org/

There are also Windows and Java versions of the program. The windows
version is called WinFIG:

  http://user.cs.tu-berlin.de/~huluvu/WinFIG.htm

And the Java version is called jFIG:

  http://tech-www.informatik.uni-hamburg.de/applets/jfig/

The file format is a fairly simple format, just lines of text, and
should be simple to read in any programming language. The format is
completely specified here:

  http://www.xfig.org/userman/fig-format.html

But you won't need to be able to support all the object types, or even
all the settable attributes of all the object types.

The only caveat, a relatively minor one, is to note that in XFIG,
coordinates are such that the origin is in the upper left-hand corner,
and the Y-corrdinate increases downward. If you read in files assuming
geometric coordinates, everything will be upside down. This, however,
should not be a major problem.

======================================================================