Prelab 5: Herbie the Robot

Your solutions to the prelab are due at the beginning of your lab section. You need to understand the concepts and problems presented in this prelab in order to complete the lab assignment.

Assignment Objectives

Reading

grammars

Problem Solving

Often we find that thinking about a complicated problem with many rules and special cases is just too difficult to do correctly. In this case, it is wise to make a simpler problem that only partly models the original, but is much easier to solve. After finding the solution, we can change the problem a little at the time, solving each new instance of the problem as we go, until we have solved the original problem! Instead of taking on one daunting task, we solve several small problems that seem relatively easy. Not only do we arrive at an answer, but if we are short on time or have a problem with one particular part, we at least have a partial solution.

In this prelab and in your lab section you will be presented with a problem to solve and a model to use. You will design an algorithm that solves the problem, and check that it is correct through hand-simulation. You will then be given a series of problems that change the original in some small way. You will change parts of your algorithm to solve the new problem and check for correctness. You will find that through a series of small changes, you have solved a much more difficult problem than was first presented.

Solving Problems with Computers

When using the computer to solve a problem, we must first describe or model the problem in a form that the computer understands. A problem model can be expressed as a picture, diagram, chart or table, for example. Since a computer cannot think in the way we humans do, we need to devise and describe a well-specified plan of what we want the computer to do. It is important to give a clear, concise problem statement. Your problem statement should specify what information is available to the computer for solving the problem (input), and what you expect the computer to provide as a solution (output).

The procedure by which we go from input to output is called an algorithm. An algorithm is a set of ordered, step-by-step instructions to solve the problem. An algorithm may be expressed in plain English, in a formal programming language (a program), or in pseudocode, which is a simplified combination of the two. For this prelab and in your lab section, you will write your algorithms in pseudocde.

When designing an algorithm, it is useful to assign names to values containing information we want to remember for later on. The names we use are called variables. A variable type describes the roles the variable can play and/or the values it can take on. Some examples of variable types are integers, characters, and booleans (variables that may be either true or false). As you develop more complex algorithms, you will find it useful to write subroutines (or methods) that describe how to do one component of your main algorithm - think of a subroutine as a "sub"algorithm. Subroutines are generally used for a computation or function that is used several times by the main algorithm, and we assign names to subroutines just as we do for variables. We give a name to our main algorithm as well.

Herbie

Herbie is a robot whose job is to walk around a room collecting dirty laundry. He must make sure that he has picked up all the dirty laundry in the whole room.

Think about all the things that a real robot with this job would need to be able to do to accomplish this seemingly simple task. For instance,

We will make the problem easier for you in the prelab by providing several assumptions about Herbie and the nature of the laundry task. In the lab assignment, the assumptions will be relaxed bit by bit and you will rewrite your algorithm for a more general case. Later you will be asked to think about other problems a real Herbie might have.

Model and Assumptions

The room that Herbie is in charge of will be modeled as a grid of squares surrounded by four walls. You can visualize the room as a two-dimensional checkerboard. We define the problem such that Herbie is in exactly one of these squares of the room at a time. Herbie has the ability to sense certain things, but he can only "see" the square immediately in front of him. At first, we will assume that there are no obstacles in the room, and that Herbie is able to tell if there is laundry in his current square, and if so, to pick it up and carry it with no problems. He can also distinguish if there is a wall in front of him instead of an empty square.

These are the functions Herbie can perform:

These are the things Herbie can sense or "see":

Problems

You will write the algorithms in pseudocode, using the instructions given. You can use the programming structures discussed in class or from the readings: if, if-else, do, while, or until. Here is an example to get you started:

Example:

Assume that Herbie is positioned in the upper left square of a 10x10 grid facing East. Write an algorithm that lets Herbie walk forward 5 steps. He must pick up any dirty laundry he encounters and then go to sleep.

Solution: Let's call our algorithm walk_five().

procedure walk_five()
{
   step_count = 0;
   while (step_count is less than 5) do
   {
     if sees_laundry()
       pick_up_laundry();
     walk_forward();
     step_count = step_count+1;
   }
   go_to_sleep();
}

As you can see, the algorithm is fairly simple. What particular information were we given in this particular problem that made the algorithm easy to formulate? Would the problem be harder if we had less information? Why or why not? Could you think of additional information that would lead to an even simpler algorithm?

Now try to write your own algorithm to solve the following problem. Identify what information you are given that is necessary to solve the problem, the variables you may require, and the condition(s) in which the algorithm terminates. Remember that a computer only knows what you tell it!

Problems

  1. Herbie can turn_left(), but he currently cannot turn right. Write a procedure where Herbie ends up facing right with respect to his initial position. procedure turn_right()
  2. Write an algorithm that makes Herbie walk forward until he sees a wall, picking up all the laundry he sees on the way. Trace through it to see if it works. In lab, you will trace through each other's prelab solutions for correctness, so please bring along a legible copy of your prelab. If somebody finds a bug in your algorithm, don't panic. We will help you debug it. The goal is to get you thinking about problem-solving in an organized way.
  3. Herbie is in a 5x5 room, and he begins in the lower left hand corner facing East. Write an algorithm that makes him visit every square in the room, picking up laundry as he goes, and go to sleep when he is through.


Comments?