COM1005-Assignment: The Rambler’s Problem Solved

The Problem
The problem is to work out the best walking route from a start point to a goal point, given a terrain map for the walking area. A terrain map specifies the height of each point in the area. Figures 1 shows an example of a realistic terrain map.

Figure 1: A realistic Terrain Map

A more simple terrain map is shown in Figure 2.

For a rambler, the best route is the one which involves the least climbing.

Figure 2: A simple Terrain Map. White is highest, black is lowest. This map is saved in tmc.pgm

Representing Terrain Maps
We’ll store our terrain maps in Portable Grey Map (pgm[1]) format.

In this format each cell is represented by an int from 0 to 255.

You can view and edit pgm files using irfanviewer - free download here: http://www. irfanview.com or just a normal text editor as it is in fact just a normal text file. In Figure 3 you can see a screenshot of the content of the tmc.pgm.

Figure 3: This is the content of the file tmc.pgm when viewed in a terminal window.

A pgm file contains a header followed by a matrix with the actual data. Figure 4 shows the header information. Figure 5 shows the x- and y-axis definitions.

Code
Code for handling the terrain maps is in the code folder within the assignment folder.

Figure 4: Header information in the pgm file.

Figure 5: PGM data matrix with x and y orientation.

You are provided with the file tmc.pgm and a java class TerrainMap whose constructor is given the filename of a pgm image and reads its contents, i.e.,

// defining a new terrain map

TerrainMap tm = new TerrainMap("tmc.pgm");
1

2

TerrainMap has the following accessors:

// accessors public int[][] getTmap() { return tmap;

};

public int getWidth() { return width;

};

public int getDepth() { return depth;

};

public int getHeight() { return height;

};
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Rambler’s costs
The Rambler steps one pixel at a time North, South, East or West (not diagonally). An upward step is more costly. The local cost c(y,x,y′,x′) of a step from (y,x) to (y′,x′) is:

{
1                                           if h(y′,x′) ≤ h(y,x)

c(y,x,y′,x′) =(1)

1+ |h(y′,x′) − h(y,x)|       otherwise.

where h(y,x) is the height in the terrain map at point (y,x). NOTE, that y is written before x!

Figure 6: Illustration of a lowest cost route found from a start point (car park at (7,0)) and point at (5,8).

What you must do
Using the Java code provided for the assignment do the following four tasks:

Task 0: Set up a GitHub (or similar) repository for keeping versions of your code as you develop your solution. Make sure to push updates regularly. The purpose of using a git repository is twofold: i) to develop good habits and practice around version control; ii) in case of a suspicion of unfair means, you have clear evidence that code was developed along the way by yourself. You must add the url of your github repository to your LATEX report (I’ve added a nifty little footnote to the title where this info can go).

Task 1: Implement branch-and-bound for the Rambler’s problem Working with search4 code and following the procedure of taking a set of general classes and making a specific solution for a particular problem, implement branch-and-bound search for the Rambler’s problems. You will need to define a class RamblersState and a class RamblersSearch. Look at the corresponding classes for Map Traversal (week3) for guidance. You will also need a class for running the tests. Call this RunRamblersBB.

Task 2: Assess the efficiency of branch-and-bound Try out a number of start and end points on the tmc map and assess the efficiency of branch-and-bound in this domain. You may also create other Terrain Maps of your own, or make use of diablo.pgm in the Rambler’s folder which is a terrain map of Mt Diablo in California. Tip: that map is a lot bigger, so if your code takes a long time to run, consider editing the map down.

Task 3: Implement A* search for the Rambler’s problem Working from the search4 code, implement A* search for the Rambler’s problem. Remember that for A* you need (under)estimates of the remaining cost to the goal. Experiment with different choices for this heuristics, for example:

the Manhattan Distance between the current pixel and the goal (p + q).
the Euclidean distance
the height difference
combinations of these
You may also devise other ways of combining the estimates. You will also need a class for running the tests. Call this RunRamblersAstart.

Task 4: Compare the efficiency of branch-and-bound and A* Perform experiments to test the hypothesis that A* is more efficient than branch-and-bound and that the efficiency gain is better for more accurate heuristics.

Task 5: Produce a report Your experimental report should describe your implementations and your results. Your report should include at the very least:

Description of your branch-and-bound and A* search implementations.
Presentation of results obtained when testing the efficiency of these two approaches.
A comparison of the results - can you verify your hypothesis?
A LATEX report template is provided, with compulsory sections specified. You may add more sections if you wish: include in your report what you think is interesting.

Note 1: you must use the LATEX template provided for your report. However, you will not be marked on your ability to use LATEX to format your report (i.e., there are no extra marks for making it look fancy!). That being said, LATEX is an essential piece of software for communicating research and results in engineering and science, so we want you to get experience using it early on.

Note 2: you should not have to make any changes to the Java code provided except to control the amount of printout during a search and perhaps to modify what a successful search returns. It’s a good idea to revisit the week 3 lab class for a reminder of how you worked with branch-and-bound and A* searches.

Code
In the downloaded zip-file you will find a code/search3 folder. This is your working folder where you should also develop your code. There are the usual classes that implements the search engines (Search.java, SearchState.java and SearchNode.java).

In addition, you will find a class that can read a terrain map (TerrainMap.java) as well as a class that easily enables you to handle coordinates (Coords.java). Finally, I’ve given you test class to illustrate how you load a particular pgm file (TestTerrainMap

[1] http://netpbm.sourceforge.net/doc/pgm.html