COM1005程序代写、代做java编程语言、代写java程序

日期：2021-05-09 10:43

Assignment: The Rambler’s Problem

COM1005 Machines and Intelligence

Semester 2: Experiments with AI Techniques

Heidi Christensen

University of Sheffield

Version 1.1

This assignment carries 30% of the marks for COM1005

DUE DATE: Friday 21st May 2021 at 23:59 (UK Time)

In this assignment you’ll experiment with search strategies for solving the Rambler’s problem.

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.

1

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 (pgm1

) 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.

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

2

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.,

1 // defining a new terrain map

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

TerrainMap has the following accessors:

1 // accessors

2 public int[][] getTmap() {

3 return tmap;

4 };

5

6 public int getWidth() {

7 return width;

8 };

9

10 public int getDepth() {

11 return depth;

12 };

13

14 public int getHeight() {

15 return height;

16 };

3

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:

c(y, x, y′

, x′

) = {

1 if h(y

′

, x′

) ≤ h(y, x)

1 + |h(y

′

, x′

) ? h(y, x)| otherwise.

(1)

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.

4

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:

1. the Manhattan Distance between the current pixel and the goal (p + q).

2. the Euclidean distance

3. the height difference

4. 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.

5

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.java).

1 /**

2 * TestTerrainMap.java

3 *

4 * Phil Green 2013 version

5 * Heidi Christensen 2021 version

6 *

7 * Example of how you load a terrain map

8 */

9

10 import java.util.*;

11 import java.io.File;

12 import java.io.FileNotFoundException;

13 import java.io.PrintWriter;

14 import java.util.Scanner;

15

16 public class TestTerrainMap {

17

18 /**

19 * constructor , given a PGM image Reads a PGM file. The maximum greyscale value

20 * is rescaled to be between 0 and 255.

21 *

22 * @param filename

23 * @return

24 * @throws FileNotFoundException

25 */

26

27 public static void main(String[] arg) {

28

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

30

31 System.out.println(tm.getWidth());

32 System.out.println(tm.getTmap()[7][2]);

33

34 }

35 }

Summary of assignment

1. Implement a branch-and-bound and an A* search for the Rambler’s problem using the

code provided.

2. Run your code with different start and end points and different heuristics (for A*) on

the different maps, to assess the efficiency of the two types of search algorithms.

3. Complete your report with the results and conclusions.

6

What to submit

Submit your solution, as a zipped file called SURNAME_FIRSTNAME.zip, where SURNAME is

your surname (family name), and FIRSTNAME is your first name (given name). This zip file

should contain:

? a .pdf copy of your report named SURNAME_FIRSTNAME.pdf

? your code.

Marking Scheme

Percentage points Categories and example score weights; Marks will be awarded according to these criteria:

40% Implementation of branch-and-bound and A* search

30% Sensible implementations of RamblersState and

RamblersSearch and the two respective test classes.

Note: marks will be deducted if your code doesn’t compile

and run on the command line. You can use your favourite

IDE but make sure that I can compile & run your code

from the command line in the search3 folder like this ”javac

RunRamblersBB.java” and ”java RunRamblersBB”. You will

lose marks, if I can’t do this without modifying code.

10% Well documented and well presented code. This is about using

comments to ease understanding of more complex parts of

the code, and the consistent use of indentations, brackets and

appropriate choices of variable names. Note, there isn’t much

code programming to do in this assignment ...).

40% Experimental results

15% Good assessment of efficiency of branch-and-bound. More

points are given for exploring a good number of different start

and end points.

25% Good assessment of efficiency of A*. More points are given

for exploring different estimates of the remaining costs to the

goal, and for exploring a good number of different start and

end points.

20% Documentation - quality of presentation and communication

of your experimental results in your report

10% Quality of communication of results in e.g. tables and figures

10% Quality of discussion of results and conclusions

100% Total

Marks and feedback will be returned through Blackboard within 3 weeks.

7

Rules

Unfair means: This is an individual assignment so you are expected to work on your own.

You may discuss the general principles with other students but you must not work together

to develop your solution. You must write your own code. All code submitted may be

examined using specialized software to identify evidence of code written by another student

or downloaded from online resources.

8