Requirement
This request deals with an offline navigation problem. In the general case, search would be on a directed, labelled graph. Here we make a number of simplifying assumptions. An agent is given an n × n grid, with co-ordinates in the range 0,…,n - 1. For the most part, each position (i, j) is connected to its immediate neighbours; i.e. to (i, j + 1), (i, j − 1), (i + 1, j), and (i − 1, j), provided no index goes outside the grid’s boundary. However, some connections are blocked, and a path will have to go around them. Your program is to take a pair of points, say (s(x), s(y)) and (g(x) , g(y)), and find a shortest path from the first point to the second.
There are two parts to the request. For both parts, assume that you are give the scenario as in the figure: The grid is 18 × 18, with co-ordinates running from (0, 0) to (17, 17). There are two obstacles, and the following co-ordinate points are inaccessible:1
2(7, 5), (7, 6), (7, 7), (7, 8), (7, 9) and
(10, 13), (11, 13), (12, 13), (13, 13), (14, 13), (15, 13), (15, 12).
So, for example, a path cannot go through (7, 5). You do not need to handle arbitrary board configurations, so it’s ok to hard code the example in your program.
Part 1
For this part, ignore the letters “a”-“d” in the figure. Write a program that determines the shortest path between any two points. While you can chose your language for the request, it must be one of the ones commonly used in the School – i.e. C/C++, Python, or Java. Justify your choice of search strategy. Make sure that you test you program with start point (0, 0) and goal (17, 17); carry out any other testing that you feel is necessary to illustrate that your program does what it’s supposed to do.
Your program should output:
- The length of the shortest path.
- The shortest path.
- The total number of nodes placed on the fringe (frontier).
- Anything else you think may be helpful.
Part 2
In this part you want to find a path that is not necessarily optimal, but uses a search that is expected to be more efficient. (So here we’re going to trade off optimality for speed.)
A common scheme to improve search in such a setting is to choose a number of “landmarks”, and precompute the paths between adjacent landmarks. The landmark graph then becomes another, higher-level representation for the search. Then the general search algorithm could be something like:
- Find the shortest path from the start position to the nearest landmark
- Find the shortest path from the goal position to the nearest landmark
- Add in the precomputed path between the two landmarks.
However, you need to be careful, since it may be more efficient to go directly between the start and goal states, rather than going through any landmarks.
In the figure, landmarks are at the points labelled “a”, “b”, “c”, and “d”, at (5, 12), (12, 12), (5, 5), and (12, 5). Since there are only 4 landmarks, the shortest path between all landmarks (there are 6 of them) can be precomputed. You can do this by hand, or you can use your program in Part 1 to find them. Again in your testing you should find a path from (0, 0) to (17, 17), and you should output:
- The length of the shortest path.
- The shortest path (although you do not need to output the path between landmarks).
- The number of nodes on the fringe.
- Anything else you think may be helpful.
Please fully comment and document your programs, and discuss the heuristics used along with any other interesting features of your programs. As well, include a README file that describes how to run your programs.