The purpose of this assignment is to demonstrate the usefulness of planning in both static and changing environments. In this assignment, you will write methods to find paths from one city to another on a map. You are given a start state and a goal state and a map simulator. From any city on the map, you can only travel in four cardinal directions (N, E, S, W). If the map simulator is given the name of the city and a direction of travel, it will return the name of the city in that direction (for example if the map simulator was sent Topeka and "N" (for North) it would return Omaha).
Your task consists of two stages. In Stage 1, you must write methods to generate the shortest valid path given a start state and a goal state using exhaustive expansion. The shortest path from city to city is the path that minimizes the number of intermediate cities between the start state and the goal. Given the start state, your program should expand the tree of possible paths from the start state in a breadth-first manner until it reaches the goal state. During this expansion your methods must record all of the expansion information in a memoizing table (similar to the hash table in Assignment #2). For example given the following map:
Salem Omaha Columbus Albany
Sacramento Topeka Knoxville Annapolis
Phoenix Austin Montgomery Columbia
If the start state was Phoenix and the Goal state was Salem, your Stage 1 methods would return the shortest path by expanding the path tree in a breadth first manner. Click here for a representation of this tree after the search and an example of output.
In your expansion of the path tree, make sure that you avoid infinite loops (do not recursively expand on a city that is already in your path -- similar to assignment #1). Record all of the information that you gain in a recursive expansion in an n by n two-dimensional array of paths (Vectors of Path_element objects) where n is the number of cities in the map. For example, for the Phoenix to Salem query above we would store the result in table[#index of Phoenix][#index of Salem]. In addition, during the expansion, we found that Austin was east of Phoenix. Therefore, we would store this information in table[#index of Phoenix][#index of Austin].
In your Stage 1 method, check the table for a given start and goal state path before recursively expanding. If the first query to the function is Phoenix to Salem and the second query is Phoenix to Austin, you should not need to recursively expand to answer the second query.
In Stage 2 of the assignment you will use the table of paths created in Stage 1 to plan routes from city to city on a randomly altered version of the initial map from Stage 1. On this altered map, you cannot count on the paths in your table to be completely accurate (because they were based on the old map). However, the path stored in the table is still your best guess from how to get from city to city.
Therefore, your Stage 2 methods must validate each transition in the old path using calls to the map simulator and updating the path if necessary. For example, suppose that in the randomly altered map you could no longer get to Salem by going north from Sacramento. Given the start state Phoenix and the goal state Salem your Stage 2 method would attempt to validate the old stored path in the table. It would call the map simulator with (Phoenix, N) and check that the result was Sacramento (good so far). Then it would call the simulator with (Sacramento, N) and see if the result was Salem. In this example the map simulator would return "-----" which indicates that Salem cannot be reached by going north from Sacramento. At this point, you know that your stored path is invalid from Sacramento to the Goal. Therefore, starting at Sacramento you recursively expand (like in Stage 1) to find a way to get to Salem using the stored values in the table. In this example, after trying to go north from Sacramento (and failing) your function would try to go East to Topeka. Once at Topeka, it would attempt to validate the path from Topeka to Salem. If no such path existed, it would use the Stage 1 function to recursively expand from Topeka to find Salem (and so on until Salem is found or the tree is fully expanded). If the tree is fully expanded and Salem has not been found then no path exists. If a path is found, this path should be entered into the table (replacing the old path).
For Stage 1 of the assignment you will complete the simple_expansion method. The simple expansion method recieves a starting city and a goal city name as input, and returns a vector of Path_element objects. Feel free to add any mehtods that you desire, but please don't change the simple_expansion declaration.
For Stage 2 of the assignment you will complete the path_validation method. The path_validation method recieves a starting city and a goal city name as input, and returns a vector of Path_element objects. Feel free to add any methods that you desire, but please don't change the path_validation declaration.
The "main" function is Assign3.java sets up the map simulator and will call your functions with start states and goal states and will print out the returned results.
Revised on Thursday, November 6, 1997