COSC 387 Project 2

COSC 387: Artificial Intelligence

Project 2
Spring 2008

Due: Feb 22 @ 5 P.M.
7 points

In Lisp, encode the following weighted graph:

Use the following latitudes and longitudes for the cities to write a function that returns the estimated distance between two cities.

Paris, 48:51:00N 2:20:00E
Caen, 49:15:00N 0:20:00W
Calais, 50:57:36N 1:57:00E
Dijon, 47:21:00N 5:02:00E
Lyon, 45:44:00N 4:52:00E
Grenoble, 45:21:36N 5:19:12E
Avignon, 43:50:00N 4:45:00E
Marseille, 43:18:00N 5:25:00E
Nice, 43:42:00N 7:21:00E
Montpellier, 43:38:00N 3:53:00E
Toulouse, 43:37:00N 1:27:00E
Bordeaux, 44:50:00N 0:37:00W
Limoges, 45:30:00N 1:10:00E
Rennes, 48:07:00N 1:02:00W
Brest, 48:24:00N 4:30:00W
Strasbourg, 48:32:24N 7:37:34E
Nancy, 48:50:00N 6:10:00E
Nantes, 47:15:00N 1:30:00W

The file graph.txt should help you save a few keystrokes, especially if you know perl. There is also a copy of this file on seva, which you can copy by executing

seva% cp ~maloofm/cosc387/graph.txt ./

Implement
1. one informed search algorithm (e.g., hill-climbing or best-first search), and
2. A*.
Each function should return the path and its cost.

Using each algorithm, attempt to find the shortest path between the following initial and goal cities:

Run Initial State Goal State
1 Brest Marseille
2 Montpellier Calais
3 Strasbourg Bordeaux
4 Paris Grenoble
5 Grenoble Paris
6 Brest Grenoble
7 Grenoble Brest

For each algorithm, over the seven runs:
1. what was the average number of nodes entered (i.e., visited)?
2. what was the average number of nodes expanded?
3. what was the average number of nodes maintained (i.e., stored)?
4. how often did it find the optimum?
Place these results a README file or in comments at the top of your source file.

Extra Credit

For one point, encode the graph of Romanian highways from the book along with their latitudes and logitudes. Just make sure your code works with this graph.

Instructions for Electronic Submission

In the header comments of the primary file, provide the following information:

;;;;
;;;; COSC 387 Project 2
;;;; Name
;;;; E-mail Address
;;;; Platform: Windows, Linux (seva), etc.
;;;; Lisp Environment: clisp, gcl, cmucl
;;;;
;;;; In accordance with the class policies and Georgetown's Honor Code,
;;;; I certify that, with the exceptions of the course materials and those
;;;; items noted below, I have neither given nor received any assistance
;;;; on this project.
;;;;

If you need to submit a single file, assuming its name is p2.lisp, type

seva% java -jar submit.jar -a p2 -f p2.lisp

If you need to submit multiple files, if you haven't already, place all of your code in a subdirectory named p2. To create this subdirectory, type

seva% mkdir p2

To descend into the directory, type

seva% cd p2

All of the files for your project should be in this directory. The submit program should be above this directory:

seva% ls ..
p2/ submit.jar

If you need to include a message to me about your submission, then place the message in a file named README. Place the README file in the project's directory.

To move up from the p2 directory, type

seva% cd ..

You should be above the p2 directory:

seva% ls
p2/ submit.jar

(Additional useful Unix commands)

When you're ready to submit, change the name of the directory to your netid. For example, if your netid is maloofm, then rename the directory p2 by typing

seva% mv p2 maloofm

Create a zip file of the directory and its contents by typing

seva% zip -r p2.zip maloofm/*

This command creates a zip file named p2.zip by recursively (-r) copying all of the files (*) from the directory maloofm/.

To submit the zip file type

seva% java -jar submit.jar -a p2 -f p2.zip

p2 is the name of the assignment (-a) and p2.zip is the file (-f) to be submitted for that assignment.

If the program submits the file successfully, you will receive a receipt by e-mail at the address <netid>@georgetown.edu.

Submit your project only once.

Once you've submitted your project, it is important to keep an electronic copy on a university machine (e.g., seva) that preserves the modification date and time. If we lose your project or the submission system breaks, then we will need to look at the modification date and time of your project to ensure that you submitted it before it was due.

You can also change the directory's name back to the original name. For example,

seva% mv maloofm p2

Note that changing the name of the directory does not change the dates of the files in the directory. You can also remove the zip file from your directory:

seva% rm p2.zip

You must submit your project before 5 PM on the due date.

Plan B

If something goes wrong with submit, then send your project as an attachment to an e-mail to me. Remember that UIS strips zip files from e-mails, so rename your zip from p2.zip to p2.piz, or something like that.

Run	Initial State	Goal State
1	Brest	Marseille
2	Montpellier	Calais
3	Strasbourg	Bordeaux
4	Paris	Grenoble
5	Grenoble	Paris
6	Brest	Grenoble
7	Grenoble	Brest