In this assignment, you will be writing a program in Lisp that first plans routes to go from one location on the Georgia Tech Campus to another, and then stores the planned routes in a plan (or case) memory. A program in Lisp is a collection of Lisp functions some of which may call others (including themselves). You will write a set of such functions that together implement depth-first search and breadth-first for route planning. You execute such a program by calling one function, called the top-level function, with the input data. This function calls other functions to get parts of the computation done. It is a good programming practice to write many small functions that are reusable in other situations as well. You should not write one big function that does everything.

Problem Statement: A rough and approximate map of the Georgia-Tech campus is provided. Note that the map is in the form of a rectangular grid; i.e. most of the roads are bi-directional and are going N and S, or, E and W, a few are one way.

Your program should take as input the specification of an initial state and a goal state. The states in the problem are intersections between roads. For instance, the input to the program could be of the form:

(10th atlantic) (north-avenue techwood)

i.e., the initial state is the intersection between 10th and Atlantic, and the final state is the intersection between North-avenue and Techwood. The output of your program should be a route from the initial state to the final state. If more than one path is possible, then it should return any one of them (which may or may not be optimal). So, for going from (10th atlantic) to (north-avenue techwood), the output could resemble something like this:

(((10th atlantic)) ;; initial state

(10th (10th fowler-1)) ;; operator and result state

(fowler-1 (5th fowler-1))

(5th (5th techwood))

(techwood (north-avenue techwood))) ;; final state

You have to write a program go-from-to (i.e., name your top-level function go-from-to) which will take the initial-final pair as input and give the desired route as output.

Representation: You might be wondering how to represent all the knowledge in the map shown below. One simple way to do it is to have a list in which each element is the representation for one street. One such element should including the following information:

1. The name of the street,
2. The directions you can travel on the street, and
3. Names of all the streets with which it intersects
   

You may assume that the names of the streets with which a street intersects are listed in order from North to South or East to West (as the case may be). In later assignments, we will develop this representation into more structured ones.

For Example, the representation for Atlantic Drive may look like:

(Atlantic (N S) (10th Peachtree-place 8th-2 Ferst-1 4^th))

Note that to simplify the representation for the present, we have decomposed some streets such as Ferst into linear segments Ferst-1, Ferst-2 etc. Similarly, Northside Drive which continues as Tech-Parkway can be simply called Tech-Parkway.

Methods: Your search functions will have to extract information about intersections from this representation. For instance, to find all the neighboring intersections for an intersection, for either street at the intersection, you have to find the members in the representations for the streets adjacent to the elements representing the other street. For instance, if the given intersection is:

(Atlantic Ferst-1)

The members in the representation for Atlantic that are adjacent to Ferst-1 are 8th-2 and 4th. Similarly, the members in the representation for Ferst-1 that are adjacent to Atlantic are State and Plum. Therefore, the neighbors of the given intersection are:

(8th-2 Atlantic)

(4th Atlantic)

(State Ferst-1)

(Plum Ferst-1)

Write the depth-first version of your program first. Try the breadth-first search method later. As you build these programs, think about which search method is easier to code? In which is it easier to construct the path for a successful search? Which of the two search methods is ``better'' for the given task of route planning on the Tech campus? Can you generate data to support your hypothesis? Try to do it.

Storage: The functions you write for this assignment will be reused in later assignments. So try to document them nicely and make them small and modular.

In addition, later assignments will reuse the routes produced by the simple search methods used in this one. So you want to store the routes in a plan (or case) memory. You may want to index the stored plans by their initial and final locations. So, for example, the path to go from 10th atlantic to north-avenue techwood may be stored something like this:

(((10th atlantic) (north-avenue techwood)) ;; the index

(10th (10th fowler-1))

(fowler-1 (5th fowler-1))

(5th (5th techwood))

(techwood (north-avenue techwood))) ;; the path

What to turn in:

A. Your documented source code.

B. The output of your program given the following inputs:

1. (10th atlantic) (north-avenue techwood)

2. (10th atlantic) (10th fowler-1)

3. (5th Plum) (north-avenue cherry)

4. (Ferst-1 State) (north-avenue tech-parkway)

5. (10th northside ) (5th fowler-1)

6. (10th fowler-1) (ferst-3 cherry)

C. Data showing which of the two search methods, depth-first or breadth-first, is better for this problem.

1. A print out of the case memory as it stands after the assignment is done.
2. A write-up which includes an analysis of the data obtained in part C.