COSC 387 Project 2

COSC 387: Artificial Intelligence

Project 2
Fall 2010

Due: Tue, Oct 12 @ 10 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. 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.

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

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

You'll be using Blackboard to submit your assignments. Put everything in a zip file and upload it.

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

Plan B

If something goes wrong with Blackboard, then send your project as an attachment to an e-mail to me.