Fill This Form To Receive Instant Help

Help in Homework
trustpilot ratings
google ratings


Homework answers / question archive / Java maze coursework Chapter 5 Introduction to the Robot-maze Environment The coursework exercises for this year’s CS118 course will be based on a simulated ‘robotmaze’ environment

Java maze coursework Chapter 5 Introduction to the Robot-maze Environment The coursework exercises for this year’s CS118 course will be based on a simulated ‘robotmaze’ environment

Computer Science

Java maze coursework

Chapter 5

Introduction to the Robot-maze Environment

The coursework exercises for this year’s CS118 course will be based on a simulated ‘robotmaze’ environment. A small robot has been designed to be able to navigate its way through mazes to find a target at some given location. This task resembles those used in the classic learning experiments of the 1960s which included laboratory mice (and cheese, mild electric shocks, mice of the opposite sex, etc). The objective of the robot (or mouse as it was then) is to find the given target as rapidly and efficiently as possible, learning the maze over several runs and so on.

Building a real robot and a real maze requires a combination of efficient sensors and mechanics, sophisticated steering and speed control, clever maze exploration and navigation procedures and, no doubt, a good deal of glue. For the purpose of these exercises we focus entirely on designing the maze exploration and navigation algorithms. We make no attempt to model the physics of a moving wheeled (or legged!) robot and concentrate solely on the part of the problem which can best be solved with software.

5.1        The robot-maze environment

The simulated Robot-maze environment has the following characteristics:

  • The robot moves through a simple square-block maze of the type illustrated in Figure 5.1. The floor space of the maze is divided into squares of uniform size. Each square is either occupied by a wall or is empty.
  • The robot occupies exactly one non-wall square and moves in discrete steps, one square at a time, north, south, east, or west. The robot cannot move diagonally. If the robot attempts to move outside the boundary of the maze or into squares occupied by walls it suffers a harmless collision (indicated by flashing red in the simulation) and stays in the same square.
  • The direction the robot moves in is determined by the way it is facing (its heading, indicated by an arrow in the simulation). The robot can change the direction it is facing by rotating on the spot. Each of these rotations are directed by the robot’s control procedure – a method called controlRobot – which is run once before the robot makes a move.
  • A robot run usually begins at the top left-hand square of the maze. The run ends when either the robot reaches the target or the user loses patience and stops the

41

42 CHAPTER 5. INTRODUCTION TO THE ROBOT-MAZE ENVIRONMENT

 

 

Figure 5.1: The Robot-maze environment

robot manually (by pressing Reset). The target square is usually the bottom righthand corner of the maze, but this along with the robot start position can be modified by the user.

During its execution the robot’s control program (which you are required to write) has access to the following information:

  • The direction the robot is currently facing;
  • The status of the squares ahead, behind, left and to the right of the robot. Squares are either walls, empty, or beenbefore squares which are empty squares the robot has previously occupied during its current run through the maze. The boundaries of the maze are treated as walls;
  • The x and y co-ordinates of the square the robot is currently occupying, and those of the target square;
  • How many attempts the robot has made at solving the given maze.

5.2     Programming robot control programs

The simulated robot-maze environment is written in Java. The programs which you are required to write for this course are also Java based which means that you will be writing code which directly hooks into this robot-maze environment.

To allow this hook-up, there needs to be a common interface between the robot-maze Java code and your own Java code. Essentially this means that you need to be talking the same language; we define this language below.

The information listed below is important and you should make sure that you understand what it all means. If you are not clear on anything then you might like to talk about it between yourselves. Understanding program interfaces like this is very important, particularly if you are to use it to write your own program code.

5.2. PROGRAMMING ROBOT CONTROL PROGRAMS                               43

5.2.1        Specifying headings in the maze

Four pre-defined constants are used to specify directions in the maze. These are

NORTH, EAST, SOUTH, WEST

where the maze follows the usual mapping convention of having NORTH upwards and EAST to the right etc.

These elements of the interface language are concretely represented as Java int values. This will be useful to know when you start referring to the types of these values in your programs. One advantage of this scheme is that

NORTH+1 = EAST; EAST+1 = SOUTH; SOUTH+1 = WEST.

5.2.2          Specifying directions relative to the robot heading

Four pre-defined constants are used to specify directions relative to the robot’s heading.

LEFT, RIGHT, AHEAD, BEHIND

As with headings these are also of the type int and therefore

AHEAD+1 = RIGHT; RIGHT+1 = BEHIND; BEHIND+1 = LEFT

A fifth constant CENTRE is also defined, which can be useful as a ‘null’ or ‘give-up’ value when communicating values between parts of complex control programs.

Do not be put off by the fact that these values have an int type. As far as the control programmer (this is you) is concerned, all references to headings and directions are done using the constant name (i.e. RIGHT, NORTH etc.) and not the constant value used to represent it. This is our first encounter with program abstraction.

As the values are defined as part of a Java interface, we need to prefix these values with the name of the interface when they are used in the actual program code. The interface is called IRobot and therefore any reference to the constant AHEAD in the code is in fact done using IRobot.AHEAD. This might seem a bit quirky but you will soon get used to it.

5.2.3         Sensing the squares around the robot

The method robot.look(direction) takes a value specifying a direction relative to the robot (e.g. IRobot.AHEAD or IRobot.LEFT etc.) and returns a value which indicates the state of the corresponding square neighbouring the robot. The possible states are

IRobot.PASSAGE, IRobot.WALL, IRobot.BEENBEFORE

IRobot.PASSAGE indicates an empty square that has not yet been visited on the current run through the maze. IRobot.BEENBEFORE indicates an empty square that has already been visited during the current run through the maze. IRobot.WALL indicates a wall or the edge of the maze.

44 CHAPTER 5. INTRODUCTION TO THE ROBOT-MAZE ENVIRONMENT

 

 

Figure 5.2: Example of sensing robot surroundings

Figure 5.2 shows a typical situation that might arise during a robot run. The robot is located in the arrowed square, facing in the direction of the arrow, with squares visited previously during the same run shaded in grey. The walls are in black. In this situation robot.look would return the following values:

 

Functioncall

Result

 

robot.look(IRobot.AHEAD) IRobot.WALL robot.look(IRobot.BEHIND) IRobot.BEENBEFORE robot.look(IRobot.LEFT) IRobot.WALL robot.look(IRobot.RIGHT) IRobot.BEENBEFORE

 

If the robot chooses to turn right and then move forward one square, then a call to the method robot.look(IRobot.AHEAD) would return IRobot.PASSAGE.

5.2.4         Sensing and setting the robot’s heading

The method robot.getHeading() returns the robot’s current heading in the maze. That is either IRobot.NORTH, IRobot.SOUTH, IRobot.EAST or IRobot.WEST. In the example in Figure 5.2 a call to the method robot.getHeading() would return the value IRobot.EAST. There is a sister method called robot.setHeading(x), which can be used to set the robot’s heading (where the parameter x is one of IRobot.NORTH, IRobot.SOUTH, IRobot.EAST or IRobot.WEST).

5.2.5       Sensing the location of the robot and target

The method robot.getLocation() returns a Point object with two public variable members. You can get the x and y co-ordinates of the robot in the maze from the Point class by accessing the x and y members of the instance using robot.getLocation().x and robot.getLocation().y. The top left square in the maze is square (1,1).

Similarly, the method robot.getTargetLocation() can be used to return the x and y co-ordinates of the robot’s target.

5.2.6       Specifying turns

The method robot.face(direction) makes the robot turn in the direction specified (one of IRobot.AHEAD, IRobot.BEHIND, IRobot.LEFT, or IRobot.RIGHT) relative to its current heading. The turn is performed immediately and will be reflected in the results of subsequent calls to robot.getHeading().

5.2. PROGRAMMING ROBOT CONTROL PROGRAMS                               45

5.2.7        Moving the robot

The control software which you will build is polled. This means that the code you write will be called by the robot-maze environment each time it is ready to move the robot. This effectively switches control between the environment and your controller, and the environment and your controller, and the environment and your controller etc.

The code which you write should therefore point the robot in a suitable direction. After the completion of your polled controller, the robot will automatically advance in the direction the robot is facing[1].

5.2.8        Generating random numbers

The Java method Math.random() returns a random floating point number greater than or equal to 0.0 and less than 1.0. The number returned is computed so as to ensure that every number appears with equal probability.

To generate random numbers (almost!) uniformly distributed between 0 and n you will need to take the result, multiply it by n, round it to the nearest integer (using Math.round()), and then cast the result to an int value, e.g. int result = (int) Math.round(Math.random()*n);

So, the code

randno = (int) Math.round(Math.random()*3);

for example, will assign a random integer value between 0 and 3 inclusive (that is one of four distinct possibilities) to the variable randno.

5.2.9        Detecting the start of a run and a change of maze

The method robot.getRuns() returns a number (int) which corresponds to the the number of previous runs which the robot has made on a given maze. After you have run a robot through a maze you will notice that the current controller screen to the right of the robot-maze environment displays 1 Run. This is the result of the robot.getRuns() method. You will find that this method is useful in the second coursework.

46 CHAPTER 5. INTRODUCTION TO THE ROBOT-MAZE ENVIRONMENT

Chapter 6

Coursework 1 (Part 1):

Simple Robots

The first coursework for CS118 consists of two parts. You will need to complete both parts if you are aiming for a top grade.

Your answers to this coursework must be completed by Wednesday 3rd November (Week 5) . You will be expected to justify key decisions and explain the process of your code in a short preamble at the top of each file.

Your work will of course be marked for functionality, that is ensuring the program does what it is supposed to do. It is also useful to remember that the work will be marked for programming style, clarity, re-usability and use of techniques taught throughout the course. This means that even if your code works wonderfully, you may not get fantastic marks if it looks like a dog’s dinner. Likewise, if you do not finish all the exercises, but your solutions look like a masterpiece, then you are likely to do well.

Please note that this coursework may be slightly different to work you have done previously in your education. There will be times when multiple different solutions present themselves, and the benefits of each are not easily comparable. Part of your development as a computer scientist in this coursework is looking at the task presented, and deciding the best course of action. There are solutions that are obviously better, but every year we see something unique that also works effectively. The key point is that you should be able to justify your choices.

Cooperation, Collaboration and Cheating

If a submitted program is not entirely your own work, you will be required to state this when the work is marked. Any and all collaboration between students must be acknowledged, and may result in stricter marking of the work. Consultation of textbooks is encouraged, but programs described elsewhere should not be submitted as your own, even if alterations are made. It will be useful to quote here the University’s regulations on the subject:

...‘cheating’ means an attempt to benefit oneself, or another, by deceit or fraud. This shall include deliberately reproducing the work of another person or persons without acknowledgement. A significant amount of unacknowledged copying shall be deemed to constitute prima facie evidence of deliberation, and in such cases the burden of establishing otherwise shall rest with the candidate against whom the allegation is made.

47

 

Therefore, it is as serious for a student to permit work to be copied as it is to copy work. Any assistance you receive must be acknowledged. If in doubt, ask. It should also go without saying that you are prohibited from uploading your solutions to the internet.

6.1       Getting started

To begin you need to copy the robot-maze environment and the controller software to your home directory. I suggest that you first create a cs118 directory. Invoke a terminal window and type in this window the UNIX command

mkdir cs118 and then change to this directory using the command cd cs118.

You should now use a web browser to go to the CS118 course web page (which should be in your bookmarks if you have followed all the instructions in Chapter 2).

Under the Coursework section of this web page you will see that there are four links, one of which says Maze software and one of which says Dumbo controller. Click on these with your right mouse button and select the Save Link Target As... option from the menu. This will allow you to save the file. When you save these files, make sure you double-click on the cs118 directory so that the file is saved to the appropriate place. The Download Manager will confirm that the file has been saved and once you have done this for both files, you can check that the files have been saved by typing ls -l in your terminal window (you may need to navigate to the correct folder using some of the commands you encountered earlier).

You should find two new files in this directory. One of these files is a .jar file; this postfix means that the file is a Java archive, an efficient ZIP-like file format which allows all the component parts of the robot-maze environment (stored in this file) to take up as little space as possible in your home directory. The other file is a .java file like those you created in your first seminar. This .java file is the robot controller which interfaces with the robot-maze environment software.

The result of the ls -al command should look something like this:

-rw-------             1 saw   dcsstaff              697 Aug 11 10:32 DumboController.java -rw-------            1 saw   dcsstaff 99539 Aug 11 10:32 maze-environment.jar

If you find that the file size of either of these files is zero (this is the number in the fifth column), then something has gone wrong during the downloading. In this case you should try downloading them once again.

You need to compile the .java file if you are to run it and in order for the controller software to run along side the robot-maze environment the two programs need to be compiled together. This requires a small addition to the javac command which you used in compiling your first Java programs. Type into you terminal window the command

6.2. LOADING CONTROLLERS

javac -classpath maze-environment.jar DumboController.java

This compiles the controller program DumboController.java into a corresponding class file (DumboController.class). The compilation is performed in the context of the robotmaze environment (through the -classpath maze-environment.jar extension) which is just what we want.

You can now run the robot-maze environment by typing

java -jar maze-environment.jar &

The & symbol runs the java command in the background, such that it frees the window so that you can still use it for other business. Admire the baroque elegance of the highly sophisticated computer graphics in the robot-maze environment program. To change the maze, click on the Generators button and then on the PrimGenerator in the window above. You will see that this fills the Current Generator information panel. If you now click on the New Maze button at the bottom right you will get a new maze (generated through an application of Prim’s algorithm).

Now that you have a maze you need a robot. Click on the Controllers button and select the RandomRobotController. You will see that this configures the Current Controller information panel.

The RandomRobotController is a pre-installed piece of controller software which drives the direction-choosing capabilities of a basic robot. Before clicking on the Start button to test the robot, set the Speed gauge to the far right of the screen.

When the robot is running you will see that it exhibits some unusual behaviour. First you will see the direction change, as indicated by the blue arrow. You will also notice that it leaves a trail (of been-before squares) as it moves through the maze. Occaisionally the robot crashes into a wall (indicated in red), this is because the controller which is being used to drive the robot makes no allowance for where the walls are in the maze.

You should familiarise yourself with this environment. See what happens when you increase the speed, try generating new mazes, try editing mazes with your mouse, try moving the location of the target, try changing the dimensions of the maze.

6.2      Loading controllers

One of the nice features of the robot-maze environment is the ability to experiment with different controller software. The DumboController which you compiled earlier can be loaded into the environment by clicking Controllers followed by Add.

This will provide you with a directory menu from which you should double click on your cs118 directory. Here you will find your DumboController.class file which you can then highlight and Open.

You will see that this adds the DumboController to your list of robot controllers. You will use this same process to load all the robot controllers which you write during this first piece of coursework.

If you click on the DumboController in the robot controllers menu, the environment will switch between controllers. Run the new robot controller to see if you can work out where RandomRobotController and DumboController differ. Try to characterise the strategies which they appear to follow. You may find find it helpful to test the robots on different mazes.

It may become obvious that it is not always easy to see exactly what strategies these robot controllers appear to follow. It is often quite difficult to reverse engineer from the behaviour to the specification. Similarly, it is not good practice to have a specification-less program, as if the user is in any doubt as to the behaviour of part of the program, this problem can be easily resolved by consulting the specification.

6.3       Analysing code

Use a text editor to look at the source code in the file DumboController.java. The method controlRobot is the controller part of the code. If you have not already worked it out, study the code and see if you can detect what strategy this control program implements.

Note the use of the import statement at the top of the program. This is the statement which connects the robot-maze environment with the controller code. The behaviour of this interface was described in Chapter 5 and you might like to go back to this chapter and just check what each of the robot methods and constants do.

Talk with your friends about this code. Is it clear to you which parts of the code are ‘pure’ Java and which parts come from the interface to the robot-maze environment?

6.4      Exercise 1

♦ An order is received from an existing customer for a modified dumbo robot:

‘Could we have a modified robot controller that still chooses directions randomly, but avoids crashing into walls.’

This description can be identified as the specification of requirements for the new robot which the customer requires.

A good software developer will set about solving this problem in a systematic and logical fashion; for example, using the processes of Design, Build and Test which were described in Chapter 3.

Designing a new piece of software requires a complete understanding of the problem to hand; you cannot write a program for a problem which you do not understand. To help work out what the specification states, we will break the description up into its constituent parts.

  • The text describes the modified robot as ‘still choosing directions randomly’. This would suggest that the part of the robot control program which chooses a random number and then converts this to a direction should stay as it is.

 

  • The text also states that the robot should ‘avoid crashing into walls’. Sometimes the existing robot controller chooses a random direction which will point the robot towards a wall. What you need to do is filter out these occurrences. This will involve looking to see if the direction chosen does point the robot towards a wall, and if so, choosing another direction.

A software developer would be right in thinking that the existing controlRobot method in the DumboController.java file can be reused; there are many similarities between the existing robot controller which you studied in previously and the new robot controller. Your answer to this exercise should therefore be based on the code found in DumboController.java.

The main difference between the old controller and the new one is that the new controller will prevent the robot from crashing into walls.

Design question 1: How do you think you can detect if the robot is about to crash into a wall? Hint: look at Section 5.2.3 of The Guide.

Once you have discovered how to detect for collisions, you will need to ensure that the robot controller keeps choosing directions for the robot until a non-wall direction is found.

Design question 2: How do you plan to do this? Hint: look at the lecture notes, this guide and any Java books you have to find out more about loops.

Once you have designed the program you are ready to build the new robot controller. The new robot controller can be built by making modifications to the existing controlRobot method in the DumboController.java file. If you’ve carefully planned how your new robot should work, it should only require about two lines of code to be changed or added, so there is no need to get carried away, or indeed too daunted by the programming task ahead!

After saving the DumboController.java file, you should compile the code using the command

javac -classpath maze-environment.jar DumboController.java

to generate a new DumboController.class file. Once you have eliminated any fatal, compiler-detectable errors, a new class file will be created. The new class file will be detected by the robot-maze software and it will ask you whether you would like to reload this new class; you should press Yes; you can now test your new solution.

Before you finish this exercise, consider how you would convince the customer that you have tested the program and that it fully meets the customer’s requirements.

6.4.1       Performance monitoring

Now that the robot no longer crashes into walls, it is easier for your customer to monitor the robot’s behaviour. As a result, you receive an email stating that they have noticed some rather unexpected behaviour.

While testing the current robot your customer noticed that although it seems to choose directions randomly, some directions appear to be selected more often than others.

This is a difficult trait to investigate by hand. You could try running your robot slowly and making a note of the directions it chooses, but this is rather painful (and life is too short for such tedium). An alternative approach is to add a logging mechanism, so that the robot keeps a record of which direction is selected each time it moves. The idea is that from this log of movements you will be able to analyse the behaviour of the robot for a particular maze.

The following output is taken from a working solution to this exercise:

I’m going forward at a deadend

I’m going forward down a corridor

I’m going forward down a corridor

I’m going forward at a junction

I’m going backwards at a deadend

I’m going backwards at a junction

I’m going backwards at a deadend

I’m going forward at a junction

I’m going backwards down a corridor

I’m going forward at a junction

I’m going backwards at a deadend

I’m going forward at a junction

I’m going forward down a corridor

I’m going forward down a corridor I’m going backwards at a deadend

I’m going forward down a corridor

I’m going forward down a corridor

I’m going forward at a junction

I’m going backwards at a deadend

I’m going right at a junction

I’m going forward down a corridor

I’m going right at a junction

You will see that the first thing that the robot detects (as it begins the exploration of the maze) is that it is at a dead-end and therefore the only thing that it can do in this case is move forward (see Figure 6.1).

Once it has done this, it then detects that it is in a corridor and therefore it decides to move forward. The same thing occurs for the third move.

After three moves the robot finds itself at a junction, here it decides to go forward once more, at which point it reaches a dead-end and can go nowhere but backwards.

You can follow the route of the robot until the reset button was pressed. You will see that the robot is not particularly efficient (as it is operating in just the same way as the robot in the previous task) but it does print out an accurate log which itself might be useful at a later date.

 

 

Figure 6.1: Coverage through an example maze.

It is always simpler to write more complicated software such as this as a series of smaller tasks. We will be building on the results of our previous exercises, so make sure that any programming which you do is done in the file DumboController.java.

Consider the first problem of outputting the text which identifies the direction in which the robot is heading, the

I’m going forward part of the output (again, refer back to Section 5.2.3 of The Guide!).

For the robot controller to print a log of this direction chosen, you need to include an instruction to output text. You may have already seen such an instruction in the exercises in your first problem sheet. You might want to remind yourself how the System.out.println() instruction works. Try adding a simple System.out.println() instruction to your robot controller, one that says “I’m going ”, or something similar. Compile and run the new robot controller to observe its effect.

Now that your controller outputs some text, you are ready to modify the program so that it outputs the forward, backwards, left or right as required. Producing this output is quite simple using the System.out.println instruction; the trick is deciding which of System.out.println("forward"); or System.out.println("backwards"); etc. is required.

Let’s consider the sub-problem of recording the direction chosen. We could use the System.out.print() to build our output string as we go, or we could store "forward", "backwards", etc. in a string and combine all variables later. We could even query the direction variable to find which direction we have chosen to face and use a conditional statement (hint: such as a switch) to write out the correct part of the sentence. The main point here, is that there are many ways to achieve the same goal, try a few and pick your favourite.

♦ Design a program which prints the direction the robot is going in.

Once you have designed this part of the program, it may be worth building it and running some tests to make sure that things are working correctly.

Now you are ready to work on the final part of the software; detecting whether the robot is at a dead-end, in a corridor, at a junction or at a crossroads. Answer the following questions as part of your design:

Design question 1: How is it possible for the robot to detect whether it is at a dead-end, in a corridor, at a junction or at a crossroads?

Design question 2: Is there a corresponding method in the maze-environment package which allows this detection to take place? Hint: see Section 5.2.3.

Design hint 1: You might like to add an additional variable to you code, walls say, in which you store the number of walls surrounding the robot. Once you have done this you will want to answer the following design questions:

Design question 3: Where in the control program do you want to declare this variable? Think carefully about the required scope of the variable.

Design question 4: Where in the control program do you initialise this variable and to what value is it initially set?

Design question 5: What criteria must be fulfilled if values are to be assigned to this variable?

Design question 6: Where in the code is this value inspected and what is the result of this?

This should allow you to establish a design for the second part of this program.

♦ Build the code and design some test criteria. You might want to look at how you would test the logical paths of your code – this was previously discussed in Section 3.3 of The Guide.

It is worth noting that the additional code should be about twenty lines long.

Once you have thoroughly tested your solution so that you are happy that it meets the required behaviour[2], copy your solution to Ex1.java (Make sure you change the class name and check your code compiles after you’ve done this).

Exercise 1 Preamble: At the top of your Ex1.java file you should include a comment that briefly discuss the problem of avoiding collisions. How do you ensure the robot does not hit a wall? Why did you design your code the way you did? This should not be very long - no more than a couple of sentences.

6.4.2       Assessing performance

♦ Using the logging from the previous exercise, determine whether the customer was correct in stating that the robot chooses some directions more often than others.

Hint: Notice how often the robot goes LEFT compared to how often it goes RIGHT, and how often the robot chooses to go AHEAD compared to how often it goes BEHIND. You may find it helpful to run the controller on different mazes. Perhaps even a blank maze?

Investigating the bias in choice of directions is difficult by hand. However, what we can do is use some additional code to analyse the log which the robot prints out.

We have been supplied with some analysis software (by our sceptical customer). Provided that your logging output from the previous exercise is correct, this software will count the number of times the robot heads in each of the four directions.

You should download this analysis software from the course web page. Here you will find a link to the file called count.pl. Right click on this file and Save Link Target As to save the file in your cs118 directory, where you have stored your answers to the exercises and the maze environment. Check that the file has been downloaded properly by typing the command ls -al in a terminal window and inspecting the size of the file.

The count program will examine your output from the previous custome request and produce a summary of the moves of the robot. For this reason, your output must be precisely formatted, otherwise the analysis will not work properly. To run the maze environment alongside the count program you should type

java -jar maze-environment.jar | ./count.pl &

If you are using your own computer for this assignment, with the Windows operating system, you will need to download a different count application, and it is used in a slightly different way. Instruction for this are posted on the course web-page.

The | ./count.pl part of the command tells the computer to send your output to the count program to be analysed.

If you have done everything correctly[3] then the robot should exhibit the same behaviour as before, but will output some different information on the console. This will be the analyser’s output, and will look something like:

Summary of moves: Forward=1 Left=0 Right=0 Backwards=0

Summary of moves: Forward=2 Left=0 Right=0 Backwards=0

Summary of moves: Forward=3 Left=0 Right=0 Backwards=0

Summary of moves: Forward=4 Left=0 Right=0 Backwards=0

Summary of moves: Forward=4 Left=0 Right=0 Backwards=1

Summary of moves: Forward=4 Left=0 Right=0 Backwards=2

Summary of moves: Forward=4 Left=0 Right=0 Backwards=3

Summary of moves: Forward=5 Left=0 Right=0 Backwards=3

Summary of moves: Forward=5 Left=0 Right=0 Backwards=4

Summary of moves: Forward=6 Left=0 Right=0 Backwards=4

Summary of moves: Forward=7 Left=0 Right=0 Backwards=4

Summary of moves: Forward=8 Left=0 Right=0 Backwards=4

Summary of moves: Forward=9 Left=0 Right=0 Backwards=4

Examine whether the summary is actually consistent with the robot’s moves. If you find that the output seems wrong, it is most likely that the log of movements you printed for the previous exercise has not been formatted correctly. Perhaps you have forgotten to add a space character, or your output has a typing error...

There is a lesson here in always paying careful attention to the program specification. It might appear a minor problem to forget a space in a log of robot movements, or you might decide that the output looks nicer formatted slightly differently. Either way you are dicing with death. Of course when a human looks at the output of your program then they can make allowances for slight variations in output. When the output is read by another computer program however, then we might not have this same flexibility. And of course how are we to know who is going to process the output, it could be a human today and another computer program tomorrow. So rather than risk things going wrong we just stick to the specification. This way we have met our side of the agreement, and if something screws up then this is (hopefully) someone else’s problem (legal case, prison sentence or whatever).

If you run tests on a number of mazes for a sufficiently long period of time, then you might notice some pattern in the directions the robot chooses. You should find that the directions chosen by the DumboController are indeed random, but that the directions are not chosen with the same probability[4].

♦ Investigate the definitions of the Math.random() and Math.round() methods from the Java API. Using this information state the probability of the robot choosing the directions left, right, ahead and behind.

Hint: The Java APIs are an excellent source of code that tens of thousands of programmers draw upon every day. They provide a repository of program code that you can use to construct more complex code. A word of warning though; just because someone else has written the code, doesn’t mean that when you employ it you are excused the task of understanding exactly what that code does. Using the Math.random() and Math.round() methods does indeed allow the robot to generate random directions, but probably not in the same way that you first thought.

6.5      Exercise 2

♦ After further discussion with your customer they submit a revised specification.

‘Could we have a modified robot controller that chooses directions randomly with equal probability? The robot should still avoid crashing into walls and should still print a log of its movements.’

You should base your solution to this exercise on the previous exercise. So make sure that you continue working on the DumboController.java file. You should also remember to keep regular back-ups at this point.

Hint: Review your answer to Exercise 1. There are many ways to accomplish this task; think carefully about the use of the Math.random() and Math.round() functions.

 

6.5. EXERCISE 2

6.5.1       Improving performance?

♦ Use the same method of design, build and test and further modify DumboController so that it meets the following customer requirements:

‘The robot should only change direction if to carry on ahead would cause a collision. As before, when DumboController chooses a direction, it should select randomly from all directions which won’t cause a collision. Directions should be chosen with equal probability and a log should be kept of the robot’s movements.’

Your solution should be building upon the work you have done previously, so again modify the code in the file DumboController.java. The modification you are required to make is again very small. These are the design questions which you need to consider:

Design question 1: How will you instruct the robot controller to check if there is a wall ahead before it decides to change direction?

Design question 2: What should the controller do if there is a wall ahead of the robot?

Design question 3: What should the controller do if there is not a wall ahead?

Design question 4: Does your controller program work the very first time it is run? What is the initial value of the variable direction?

6.5.2        Reaching the end

You may notice your robot has some issues after implementing the last algorithm. To correct this issue, it is decided some elements of randomness will be added back into the robot controller.

♦ Again building on your previous work, modify the controller in DumboController.java. This time, as well as displaying all the previous characteristics, the robot controller should also have a chance to choose a new direction randomly, irrespective of whether there is a wall ahead or not. This chance should result in the robot selecting a random direction on average every 1 in 8 moves. It should be a chance, meaning that the robot may choose a random direction 2 moves in a row, or not for 20 moves, but, over a long time, the proportion of random moves should be about 1 in 8.

There are two design questions which need to be considered:

Design question 1: How will you get your robot controller to choose a new direction on average every 1 in 8 moves? Hint: you have given this some thought earlier.

Design question 2: How will you incorporate this into the existing code? Can you combine this new code with your existing if statement by employing some boolean algebra? Hint: look at the lecture notes and your textbooks for information on logical operators in Java.

Once you have established your design, build the new robot controller. Again, your solution should modify no more than two lines of the controller program, so do not get too carried away.

One example of the resulting behaviour will be that a robot which is travelling forwards in a straight line will occasionally change direction. It may choose to go backwards, continue on its original path forwards, or choose a left or a right turn if these are available. Can this version of DumboController be expected to reach the target if given enough time? Test your solution on some suitable examples.

Make a copy of your final solution to this exercise by typing

cp DumboController.java Ex2.java

Exercise 2 Preamble: At the top of your Ex2.java file you should include a comment that briefly discusses the problems solved during this exercise. In particular, you should explain your method of ensuring ‘fair’ probabilities and justify how it ensures even probabilities. Include a discussion of the initial issue that had to be solved - what caused the initial uneven probabilities? Also discuss how you decided to incorporate the 1-in-8 chance into your design. Was this a disruptive change? Do you think it could be done in a better way? This preamble will likely be longer than your previous preamble, but should still be no more than two short paragraphs.

6.6      Final words

You may have decided while doing the previous exercises that there are many alternative solutions to these problems; you would of course be right. Which solution you ultimately choose is a matter of taste, though later in your programming career you may well find that in-house styles or programming templates dictate the approach which you use.

Think about an alternative approach to solving one of the previous exercises. Why is your alternative solution better and why?

Important note

Before moving onto Part 2, ensure you have correctly renamed all of your files and classes ready for submission. The marking process for this module is partially automated and any compile errors will result in a loss of marks. Additionally, ensure that you haven’t accidentally pasted rubbish into your files by accidentally hitting the middle click button.

Chapter 7

Coursework 1 (Part 2): A Homing Robot

In this part of the coursework we get to grips with some slightly more difficult programming tasks, consider the problem of ensuring that software is working correctly, and experiment with additional elements of the Java language.

The main aim of the exercises in this chapter is to guide you through building a robot controller which will make the robot home in on the target. The robot controllers which we have built so far will ensure that the robot eventually reaches the target; however, they will not direct the robot in any meaningful way. The target is reached because the robot chooses directions randomly and if enough random moves are made then the robot will eventually find the target. The trouble with this method is that it may take a long time for the robot to reach the target, particularly if the maze is very large.

If the robot controller is able to sense where the target is located, then a better search technique can be applied. Rather than the robot moving randomly, it could attempt to move closer to the target. This is roughly the technique which we will follow in this chapter.

7.1       Starting again

Before you begin building the homing robot, it is worth noting some of the programming errors which you may encounter.

Use your text editor to study the robot controller in the file Broken.java which can be downloaded from the course web page. This robot controller has two programming errors that the compiler cannot detect. You can compile the code using the command

javac -classpath maze-environment.jar Broken.java

and then load the Broken controller into the robot-maze environment in the usual way. When you try and run the robot you will find that it stalls; it seems not to move and when you press the Reset button this is confirmed when it reports that no moves have been made. It is clear that in this case the robot does not meet the customers requirements. We will work through the problems together. First look at the line

59

 

direction = robot.look(IRobot.EAST);

If you study the details of the method robot.look in Section 4.2.3 of The Guide, then you will find that it returns a result IRobot.WALL, IRobot.BEENBEFORE, etc. The variable direction will be assigned that value.

The first question to ask yourself is ‘is this correct?’ Is it right to set the direction variable to IRobot.WALL or IRobot.BEENBEFORE, etc? The answer really depends on what you want to do with that variable. We are given a clue as to its use later on in the program

robot.face(direction);

This seems to suggest that once the direction is chosen, the robot is then faced in that direction before the robot is finally moved. So now you should ask yourself what happens when the robot tries to face IRobot.WALL or IRobot.BEENBEFORE?

Whatever the answer is, and I am not really sure, the programmer is using the methods robot.look and robot.face in a way which makes no sense according to the programming interface. What this means is that these methods are strictly defined and serve the purpose of interfacing between the controller software and the robot-maze environment. If these methods are used differently than intended then we can not be sure how these methods will behave.

This might not seem particularly interesting, or indeed important, but adhering to the interface specification is crucial if your programs are to work correctly. Even if you have a good feeling about the way in which a method works outside of this specification – and this is justified by a few test calls – if you are using a method differently from the way in which it is specified then you are playing with fire. The method may work well for the first 100 calls and then blow up on the 101st call. Then you are in trouble.

In this example I think the programmer just read the interface specification wrong and decided that a call to robot.look(IRobot.EAST) was probably a reasonable thing to do. This is an error which is going to occur a lot in these exercises and you may well be the one who falls into this trap.

You might (reasonably) have expected the compiler to signal an error in this example. After all, the method robot.look is expecting something of type IRobot.AHEAD, IRobot.LEFT, etc. and is passed something of type IRobot.NORTH, IRobot.SOUTH, etc. But the Java compiler is oblivious to the problem. As far as the compiler is concerned, both these abstract types look the same. Both are represented in the program as integer values, and so any type-checking that the compiler performs will just ensure that the value assigned to the variable direction and passed to the function robot.look is an int – which it is.

This problem is an interesting example of the difference between a syntax error (which the Java compiler can detect) and a semantic error (which the Java compiler cannot).

There is one other semantic error in the code. See if you can spot where it is and once you have detected it, correct the program so that it runs in accordance with the specification of Exercise 1.

7.2. EXERCISE 3

 

 

Figure 7.1: The robot homing towards a target that is north-east would choose to go ahead (north) or right (east) as opposed to behind (south) or left (west). Note the relationship between the x- and y-coordinates of the robot and the target.

7.2      Exercise 3

The controller of the homing robot which we are going to build is based on a heading controller.

Our new homing robot will choose a heading based on its current location and the location of the target. For instance, if the robot is heading NORTH and the target is to the north of it, as in Figure 7.1, then it makes sense for the robot to select NORTH in preference to SOUTH. Based on this assumption, you will construct controller code to determine whether the target is to the north, south, east or west of the robot, and then build a heading controller that will guide the robot closer to the target. Essentially what the robot is trying to do is ‘sense’ the target and move towards it if at all possible. A scheme that seems inherently sensible, at least at the outset.

7.2.1        Finding the target

It is possible to decide whether the target is to the north of the robot by examining the y-coordinate of the robot and the target[5]. If the robot’s y-coordinate is greater than that of the target, then the target is north of the robot. Similarly, if the robot’s y-coordinate is less than that of the target, then the target is to the south. If the y-coordinates of both the robot and target are the same, then you will find that both the robot and target are on the same latitude.

♦ Add a new method called isTargetNorth to the file Broken.java. The method should take one parameter (the robot itself[6]) and should return 1 if the target is north of the robot, -1 if the target is south of the robot and 0 otherwise.

The method should look something like

private byte isTargetNorth(IRobot robot) {

byte result ...

// returning 1 for ‘yes’, -1 for ‘no’ and 0 for ‘same latitude’ ...

return result;

} and should not be more than about five lines long.

First sketch your solution on paper, answering the following design questions as you go along:

Design question 1: Where in the Broken.java file should you locate this new method?

Design question 2: How can you determine the relative positions of the robot and the target?

Design question 3: What parts of the robot interface can help you in this calculation?

Once your code compiles correctly, you should consider how to go about testing it. Is it possible to develop some exhaustive tests to cover all eventualities? You might want to look back to Section 3.3 of The Guide to see what testing technique would me more appropriate.

Consider adding some appropriate System.out.println statements, and running the robot slowly to examine whether the output makes sense. You might find that moving the target and the robot will help you test more cases. Be prepared to talk about how you tested your solution and why you tested it in that way.

♦ Use your isTargetNorth method as a basis for a second method called isTargetEast. This should return 1 if the target is to the east of the robot, -1 if the target is to the west of the target, and 0 otherwise.

7.2.2       Sensing your environment

Currently the robot can sense its environment using the look() function. The function takes relative directions in order to operate correctly. The functions you have just written return the target’s position in absolute directions and your controller will need to give the robot an absolute direction, so it makes sense that you sense the environment using absolute directions.

♦ Write a method called lookHeading that takes an absolute direction and returns whether there is a WALL, a PASSAGE or a BEENBEFORE square, much like the current look() function. Hint: You may need to pass the robot object to the function in addition to a heading.

7.2.3        Building a heading controller

Using the methods that you have developed so far, it is possible to calculate where the target is relative to the current position of the robot and to analyse the robots surround-

7.2. EXERCISE 3

ings. As in Figure 7.1, if we detect that the target is to the north-east of the robot, it makes sense to direct it either north or east. That is, as long as there is not a wall in either (or both) of these headings.

♦ Create a headingController method that exhibits the following behaviour:

Given the state of the robot in the maze, the controller should return a heading that will head the robot towards the target if at all possible. This means that: (i) if it can select a heading that will move the robot closer to the target then it should do so; (ii) it should not lead the robot into a wall; (iii) if the robot has the choice of more than one route, then it should randomly choose between them; (iv) if there are no headings that will move the robot towards the target, pick randomly between all available headings.

Before trying to write the software, you must have a clear understanding as to what this specification means exactly.

Design question 1: What should the robot controller do if travelling NORTH or EAST will move the robot towards the target, and these passages are not blocked by walls?

Design question 2: What should the robot controller do if travelling NORTH or EAST will move the robot towards the target, and there is a wall to the north but not to the east?

Design question 3: What should the robot controller do if travelling NORTH or EAST will move the robot towards the target, and there is a wall to the east of the robot but not to the north?

Try to design your code on paper first. You might find it useful to create a table of the scenarios that the robot might encounter and use this when designing your code.

7.2.4       Testing your solution

♦ Now that the controller code is becoming more complex, it is important that we test it to see that it meets the desired functionality.

To help with testing, we have constructed a test harness that you can use to test your headingController.

To access the test harness you need to first download it from the course web page; you will see that it is named ControlTest.class and it should be saved to the same directory as your source code.

To call this test harness you need to add a couple of lines of code to your program. The first thing you should do is add a call to the test harness (ControlTest.test) just before your robot sets its heading to the newly chosen direction and advances, i.e.

...

heading = headingController(robot); ControlTest.test(heading, robot); robot.setHeading(heading); ...

This test-calling code will check each heading that your robot selects and compare it against a working solution.

Next you need to add some code that will print the log of test results at the end of the robot’s run. You should include the code

public void reset() {

ControlTest.printResults();

}

to your class (outside the definition of the controlRobot method, yet within the brackets of the whole class).

These modifications will allow you to test the behaviour of your headingController method. You should ensure that your robot passes these tests (indicated by a status report of ok). Example test reports can be found on the course web page.

Don’t take this testing too lightly. If you were a customer buying the controller code then you would be pretty careful to check that it works, particularly if you are paying good money for it.

After thoroughly testing your solution, save it as Ex3.java.

Exercise 3 Preamble: At the top of your Ex3.java file you should include a comment that discusses key elements of this exercise. How did you choose your design for your heading controller? Does it ensure that the robot always moves, when possible, closer to the target? Furthermore, can the homing robot always be expected to find the target? Carefully justify your answer. What improvements would you suggest for the robot? This preamble should be of a similar size as exercise 2.

7.3      Final remarks

It is interesting that developing a smarter control algorithm does not actually provide us with a better robot. The random robot is preferable to the homing robot in the sense that it will eventually reach the target, albeit after a very long wait.

Also of interest is the fact that specifying and ordering a homing robot seemed sensible. It is quite possible that a customer, wanting a more sophisticated robot, would request such behaviour, unaware that the resulting robot would not reach the target in some cases.

An answer to this sort of problem is to build a prototype. Software developers will often produce some small cheap code to model a potential solution to a coding problem. The code does not need to be shown to the customer, as in itself it is not important. What is important is the input and output behaviour that the code exhibits. A customer will be shown the prototype and asked to inspect the behaviour. It is at this point that the customer can say, ‘hang on, this was not what I thought it would do!’

Prototypes are an excellent way of developing potentially expensive software. They ensure that when a customer pays twenty million pounds for some code, it turns out to be what they wanted.

7.3. FINAL REMARKS

It is quite possible to write prototypes in the Java programming language, but it is often argued that other languages are better suited to the task. For example, functional programming languages are favoured for the speed at which software can be developed and the size of the resulting code. They do not produce particularly fast code, but then again at the prototyping stage this probably does not matter.

This is the end of the first coursework. Submit your work through the Tabula submission system, making sure to include the following files:

Ex1.java, Ex2.java, Ex3.java

Don’t forget that your deadline for submission is Wednesday 3rd November (Week 5) .

 

[1] This is a change from previous years, where your controller would advance the robot manually. If your controller points the robot at a wall, when the environment advances, the robot will cause a collision with the wall.

[2] paying careful attention to the layout of the logging output

[3] If, for some reason, this does not work, do two things: 1. check that the file you have saved is called count.pl and if it is not do a mv x count.pl, where x is the name of the file you saved; 2. make sure that it executes correctly, you can ensure this by typing chmod u+x count.pl in the command window.

[4] If you did not spot this previously then this is the difference between the DumboController and the RandomRobotController.

[5] The coordinates begin (1,1) at the top left-hand corner of the maze and increase to (n,n) at the bottom right-hand corner of the maze (the default maze is 15 by 15).

[6] You will need this parameter if you are to check the y-coordinate of both the robot and target.

Purchase A New Answer

Custom new solution created by our subject matter experts

GET A QUOTE