In this last assignment, you are required to use a radically different representation of the map, and study the effect of the new representation on the program. The structure of the assignment and the map you have to represent is identical to assignment 3. The system's model (map) of the navigation space should be organized in a neighborhood/sub-neighborhood semantic hierarchy, and the case memory should be reorganized around this hierarchy. You are required to analyze the effects of this knowledge reorganization on (i) the breadth first and depth first search methods for planning paths that you investigated in Assignment 1; (ii) the case-based method that you investigated in Assignment 3.
First, organize your system's model of the navigation space in a two-level neighborhood/sub-neighborhood semantic hierarchy. The single node at the top level in this hierarchy will correspond to the whole GT campus. The bottom level in the hierarchy will contain nodes corresponding to the various parts of campus. A simple organization would involve splitting the campus map into four quarters - North East, North West, South East and South West - and turning each of them into a node. Each of these four nodes may contain knowledge of the streets (and their directions, intersections) with in the respective neighborhoods. The top-level node may contain knowledge of the inter-neighborhood streets (and their directions, intersections) only. It may also contain knowledge of the lower-level neighborhoods (and their relative locations).
Next, organize your system's case memory around the two-level neighborhood/sub-neighborhood semantic hierarchy. Cases whose initial and final locations both fall within a neighborhood at the bottom level of the hierarchy may be organized around that neighborhood. Cases whose initial and final locations fall in different neighborhoods at the bottom level may be organized around the top-level node in the hierarchy. Note that each case now would have two indices: (i) the neighborhood to which it belongs and (ii) its initial and final locations. Each case must still have a utility value attached.
Then, investigate the above knowledge organization by studying how it effects the problems you solved in assignments 1 and 3.
In redesigning the solution to assignment 1, note that the hierarchical organization of the spatial model provides a decomposition of the planning problem. The search methods may now first plan a partial path at the top level and then complete the path by additional planning at the bottom level. They may use either breadth first or depth first search to plan a partial path within a neighborhood.
In redesigning the solution to assignment 3 note that the organization of the case memory implies that each case must now have a more complex indexing scheme. Each case's index must now store more than simply the initial location and the final location of the case. It must also store how the case relates to the higher level data, ie, the neighborhood.
As with previous assignments, you are required to run experiments on your program to determine its performance and the criteria that affect its performance. There is a single change in this assignment - the representation has been radically modified. Assignments 1 and 3 presented a number of aspects of the program that might be studied. Pick one aspect of the program's performance, and study how the new representation affects that aspect of the program.