The five (5) design projects in this class all deal with a planner for navigating the Georgia Tech campus. In the first project, you need to design a navigational planner that (i) plans routes to go from one location on the Georgia Tech Campus to another, and (ii) stores the planned routes in a plan memory. Your design should use the methods of breadth-first search and depth-first search for the planning task. You also need to implement your design in a computer program (in Lisp of C), experiment with the program, and write a critique of your system design.
Let us suppose that an intelligent agent is given a map of the Georgia Tech campus (even if the map is only rough and approximate). For simplicity, let us assume that the map is in the form of a rectangular grid, i.e., all roads are either North and South, or West and East. Let us also assume that curved roads (such Ferst) are divided into linear segments (such as Ferst-1, Ferst-2 ...) that lie alond the North-South and West-East axes. In addition, let us assume that all roads allow bi-directional flow of traffic.
Your navigational planner 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 planner should output a route from the initial state to the goal state. If more than one path is possible, then it should return any one of them (which may or may not be optimal path). Thus, 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
One way of representing of the map is to have a list in which each element is the representation for one street. One such element could including the following information:
In this project, you may assume that the names of the streets with which a given street intersects are listed in order from North to South or East to West. (In later projects, we will develop this simple representation into a more structured one.) For example, the representation for Atlantic Drive may look like:
(atlantic 10th peachtree-place 8th-2 ferst-1 4th)
(Note again the simplifications: curved streets such as Ferst are decomposed into linear segments Ferst-1, Ferst-2 etc. Also, Northside Drive which continues as Tech-Parkway is simply called Tech-Parkway.)
The search methods will need to extract information about intersections from this representation. For example, to find all the neighboring intersections for an intersection, for either street at the intersection, the methods would need to find the elements 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 10th, 4th, 8th-2 and Peachtree-Place. Similarly, the members in the representation for Ferst-1 that are adjacent to Atlantic are Plum, State, Dalney, Hemphill and Ferst-2. Therefore, the neighbors of the given intersection are
(Atlantic 10th)
(Atlantic 4th)
(Atlantic 8th-2)
(Atlantic Peachtree-Place
(Ferst-1 Plum)
(Ferst-1 State)
(Ferst-1 Dalney)
(Ferst-1 Hemphill)
(Ferst-1 Ferst-2)
You may want to develop and experiment with the depth-first search method first, and try the breadth-first search method later.
You need to store the plans created by your planner in a plan 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
As you encode and run your programs, think about the following questions:
On paper in class:
(10th atlantic) (north-avenue techwood)
(10th atlantic) (10th fowler-1)
(5th Plum) (north-avenue cherry)
(Ferst-1 State) (north-avenue tech-parkway)
(10th tech-parkway) (5th fowler-1)
(10th fowler-1) (ferst-3 cherry)
By email, submitted to jimmyd@cc.gatech.edu:
Grading Criteria
total points: 100
Program: (80 pts)
5 pts clear usage and input format
20 plan storage
40 appropriate output for 6 test cases
15 style (readability, comments, correctness, etc.)
+5% in lisp
+5% if you are one of the best projects and agree to put it on the
newsgroup
Write-up: (20 pts)
2 Name
4 hypotheses explicit in introduction
3 description of experiments (efficiency, answer quality)
4 results (number of trials, quantitative measures, etc.)
5 discussion (Explanation of results,
rationale of representation and implementation, etc.)
2 Style (typed, spelling, grammar, clarity, etc.)