The four design projects in this class are based on an experimental navigation planning system called Router that was developed at Georgia Tech in the early 1990s and is presently embodied in a real robot called Stimpy. At the end of the four projects, each of you will have developed your own "micro-Router" system. In this, the third project, you will explore several refinements to the search-based and memory-based navigation planners you developed in the first two projects.
In particular, the new planner's model (map) of the navigation space should be organized in a neighborhood-subneighborhood semantic hierarchy, and the plan memory should be reorganized around this hierarchy. In this project, you are required to analyze the effects of this knowledge reorganization on
First, organize your planner's model of the navigation space in a two-level neighborhood-subneighborhood semantic hierarchy. The single node at the top level in this hierarchy should correspond to the whole GT campus. It should specify the bottom level nodes, the streets that connect them, and their location relative to one another. The bottom level in the hierachy should describe the streets within each node. The whole campus could for instance be divided into four neighborhoods corresponding to the North East, North West, South East and South West sections of the GT campus.
Next, organize your planner's memory of past plans around the two-level neighborhood-subneighborhood semantic hierarchy. Plans whose initial and final locations both fall within a neighborhood at the bottom level of the hierarchy may be organized around that neighborhood. Plans whose initial and final locations fall in different neighborhoods at the bottom level may be organized around the top-level node in the hierarchy.
Then, investigate the above knowledge organization by studying how it affects the problems you solved and the methods you used in Projects 1 and 2.
In redesigning the solution to Project 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 Project 2, note that the organization of the plan memory implies that each case now has two indices:
Write a function of the form
(plan-path source destination method)
where source is the source intersection,
destination the desired destination, and
method one of the following five:
:dfs
:bfs
:search
:cbr
:choose
You may keep the behavior of all three modules the same as in assignment 2. The output format of the paths should also remain unchanged. Specifically, the path should be a list with the follwing format:
( (source) (next-street next-intersection)* )
Each item in the return path should be a list. The first item
should be a list containing only source. All
other items should be a list of the street that was taken, and the
next intersection that was reached on that street. The last item on
the path should have destination as the
intersection.
For your representation, you have to divide the map into neighborhoods. You may choose the default example presented above - NW, NE, SW, SE. You may choose to have more or less than four neighborhoods. Keep in mind that the benefits you get are likely to be maximized if the neighborhoods are balanced in their complexity, and the program does not really care what the shape of the neighborhoods is.
You will have to redesign your search algorithms to work
appropriately given this representation. For example, if your high
level plan dictates that you get from (10th hemphill) to
the NE neighborhood, there is no longer a single street that can serve
as a destination. You have to design your planning method to
accomodate such requests. See the textbook for more details.
Finally, consider what information is required for CBR at various levels. At the top level, none of the streets other than the ones used for crossing neighborhood boundaries are important. The route from these cross-neighborhood streets to the destination would be of interest only within the neighborhood. Design your case memory to take advantage of this decomposition.
As you design, code and run your programs, think about the following questions:
A written report to be delivered in class, containing:
Mail the code for your program to jimmyd@cc.gatech.edu. send it as plain text, not uuencoded. It's okay to paste it into the body of the message. But MAKE SURE YOUR LINES DON'T WRAP. Keep them short.