Assignment 5: Tracking the Martian Gnat

CS100J, Fall 2000

Due in Lecture, Thursday, November 9.

Overview

A gnat-like creature has been found on Mars in an area called Rectangular Rock Crater. A robot will be sent to observe it close up. Your job is to write the robot's control program. Your objective is to keep the robot as close to the gnat as possible, and to minimize the number of times the robot crashes into rocks.

Goals

Practice with 2-dimensional arrays. Practice with 1-dimensional arrays as look-up tables and queues. Exposure to planning.

Introduction to (asynchronous) process control, sensors, and actuators. Exposure to simulation. Practice with methods. Exposure to graphics.

Equipment

The robot has the following equipment:

·         Sensors to detect the x, y coordinates of the gnat.

·         A motor assembly, consisting of

1.        Sensors for the x, y coordinates of the robot .

2.        A clock.

3.        An actuator for moving the robot one cell in any of 4 directions (N, E, W, S). The robot may take up to 5 clock ticks to reach a neighboring cell.

4.        A diagnostic interface.

Rectangular Rock Crater

The environment in which the robot must operate is an n-by-n rectangular region of cells, where n <= 1000 is given to the robot on startup.  Some cells are filled with rock, but the robot only learns about the existence of a rock when it bumps into it. We do not rule out the possibility that the robot and gnat are separated from one another by a solid wall of rock.

We use the following 6-by-6 version of Rectangular Rock Crater for illustration. Rocks are shown in black, and the robot and gnat positions are shown by R and G, respectively:

 

1

2

3

4

5

6

àx

1

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

3

 

 

 

 

 

 

 

4

 

 

R

 

 

 

 

5

 

 

 

 

G

 

 

6

 

 

 

 

 

 

 

¯

y

 

 

 

 

 

 

 

Note that x corresponds to the column index, and y corresponds to the row index. The coordinates deliberately start at 1 (rather than 0) as a convenience to you (see Hint 1).

Control Program (method run)

The objective of your control program is to keep the robot as close to the gnat as possible while avoiding known rocks. To do so, it must repeatedly:

·         sense the location of the gnat,

·         plan how to get closer (based on its current knowledge of the positions of rocks),

·         actuate the motor to take the first step of the plan,

·         wait until either the robot reaches the neighboring cell, or 5 or more clock ticks have elapsed, whichever comes first. If 5 clock ticks have gone by and the robot has not yet reached the neighboring cell, there must be a rock in the way. In this case, update your rock knowledge base with the new rock.

Here is a sample trace of the control program in action. Initially, the control program knows nothing about the locations of rocks:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

R

 

 

 

 

 

 

 

G

 

 

 

 

 

 

 

Based on this incomplete knowledge, the plan is to take the following shortest path from R to G (chosen arbitrarily from several possible shortest paths):

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

2

 

 

 

 

 

3

 

 

 

 

 

 

 

The control program actuates the motor to move right one cell, but after waiting 5 clock ticks, the robot still hasn't moved. This must be because a rock is in the way. By now, the gnat has moved:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

G

 

 

R

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

The new plan is to take the following shortest path to the gnat:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

2

3

4

 

 

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

The control program actuates the motor to move up one cell, and after waiting 5 clock ticks, detects that the robot has reached the neighboring cell. However, the gnat has already moved again:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

R

 

 

 

 

 

 

 

 

 

 

 

 

G

 

 

 

 

 

 

 

 

The new plan is to take the following shortest path to the gnat:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

1

 

 

 

 

 

2

3

 

 

 

 

 

 

 

 

And so forth. Note that the planner never proposes a path that would cause a crash into a known rock.

Planner

As indicated above, your control program should use a "shortest-path" plan.  This is certainly not the only strategy possible. For example, a better plan might take into account the gnat's trajectory. However, for this assignment, you should implement the shortest-path planner described below.

Suppose the robot is in the cell labeled R, the gnat is in the cell labeled G, and the known rocks are shown in black:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

R

 

 

 

 

 

 

 

 

G

 

 

 

 

 

 

The shortest path to the gnat can be computed using the following two-step process:

·         Flood Fill.  Determine the "distance" from the robot of every vacant cell. The notion of distance must take into account the limitation that, in each step, the robot can move horizontally or vertically but not diagonally. For example:

 

5

4

3

 

 

 

6

 

2

3

4

5

7

 

1

2

3

4

6

 

0

 

4

5

5

 

1

 

5

6

4

3

2

 

6

7

 

·         Traceback. Starting at the position of the gnat, trace back a sequence of cells that get closer and closer to the robot, until you reach the robot. The reverse of this sequence is the robot's plan.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

2

3

4

 

 

0

 

 

5

 

 

 

 

 

6

 

 

 

 

 

 

Flood Fill

The distances of the cells from the robot can be computed, in increasing order of distance, as follows:

·         List all cells distance 0 away, i.e., just where the robot is,

·         then list all cells distance 1 away,

·         then list all cells distance 2 away,

and so forth, until eventually all cells have been listed. As you list a cell, you can fill in its distance in the map.

Keep the list  (in increasing order of distance) in a pair of arrays row[]and col[], where row[i]and col[i] are the row and column coordinates of the i-th cell listed.

For example, here is the map and list of cells distance 0 away:

 

1

2

3

4

5

6

1

 

 

 

 

 

 

2

 

 

 

 

 

 

3

 

 

 

 

 

 

4

 

 

0

 

 

 

5

 

 

 

 

 

 

6

 

 

 

 

 

 

 

row

4

 

 

 

 

 

 

col

3

 

 

 

 

 

 

 

And here is the map and list of cells distance up to 1 away:

 

1

2

3

4

5

6

1

 

 

 

 

 

 

2

 

 

 

 

 

 

3

 

 

1

 

 

 

4

 

 

0

 

 

 

5

 

 

1

 

 

 

6

 

 

 

 

 

 

 

row

4

3

5

 

 

 

 

col

3

3

3

 

 

 

 

 

To list the cells distance d+1 away, you just need to list all currently unlisted immediate neighbors of cells distance d away (that are not rocks or off the edge of the map).

Let's see how that would work for distance 2. We introduce two variables, L and R, indicating the positions in the list of the next cell to be "processed", and the next available slot in the list, respectively:

 

 

L

 

R

 

 

 

row

4

3

5

 

 

 

 

col

3

3

3

 

 

 

 

 

The next cell to be "processed", i.e., the L-th cell in the list, is <3,3>. It has two unlisted neighbors, <2,3> and <3,4>, so after "processing" it, the map and list are:

 

1

2

3

4

5

6

1

 

 

 

 

 

 

2

 

 

2

 

 

 

3

 

 

1

2

 

 

4

 

 

0

 

 

 

5

 

 

1

 

 

 

6

 

 

 

 

 

 

 

 

 

 

L

 

 

R

 

row

4

3

5

2

3

 

 

col

3

3

3

3

4

 

 

The next cell to be "processed", i.e., the L-th cell in the list, is <5,3>. It has one unlisted neighbor, <6,3>, so after "processing" it, the map and list are:

 

1

2

3

4

5

6

1

 

 

 

 

 

 

2

 

 

2

 

 

 

3

 

 

1

2

 

 

4

 

 

0

 

 

 

5

 

 

1

 

 

 

6

 

 

2

 

 

 

 

 

 

 

 

L

 

 

R

row

4

3

5

2

3

6

 

col

3

3

3

3

4

3

 

 

At this point, we have completed the computation of the cells distance 2 away, and are about to compute the cells distance 3 away.

Notice that the items in the row and col arrays are being "processed" in the order in which they were inserted into the list. This is called FIFO ("first-in first-out ") order. Such a list is called a queue. Variable L is the subscript of the next element to be "processed", i.e., the head of the queue. Variable R is the subscript of the next available slot into which a new element can be inserted, i.e., the end of the queue. Eventually, when all cells have been processed, L will equal R.

You must take care to never list a cell more than once. The easiest way to tell whether a cell has been listed already is to look in the map, where a blank indicates that it has not yet been listed. In your program, the map will be a two-dimensional array of integers, so the blank should be represented by some unique, large integer value.

Traceback

Given the map of distances, a plan can be developed backwards, i.e., by starting at the gnat and listing a sequence of cells that are closer and closer to the robot.  In our example, the gnat is shown in cell <5,6> lightly shaded:

 

 

1

2

3

4

5

6

1

5

4

3

 

 

 

2

6

 

2

3

4

5

3

7

 

1

2

3

4

4

6

 

0

 

4

5

5

5

 

1

 

5

6

6

4

3

2

 

6

7

 

 

0

1

2

3

4

5

6

7

rowP

 

 

 

 

 

 

5

 

colP

 

 

 

 

 

 

6

 

 

Two of the gnat's neighbors are distance 5 from the robot. The traceback can choose among these arbitrarily.

 

1

2

3

4

5

6

1

5

4

3

 

 

 

2

6

 

2

3

4

5

3

7

 

1

2

3

4

4

6

 

0

 

4

5

5

5

 

1

 

5

6

6

4

3

2

 

6

7

 

 

0

1

2

3

4

5

6

7

rowP

 

 

 

 

 

4

5

 

colP

 

 

 

 

 

6

6

 

 

In general, a cell in the plan distance d+1 from the robot has several neighbors that are distance d from the robot. The planner is free to choose any of them. When the traceback is finished, the plan would be:

 

0

1

2

3

4

5

6

7

rowP

4

3

3

3

3

4

5

 

colP

3

3

4

5

6

6

6

 

Simulator

Rather than send your robot code to Mars untested, we have built a simulator. (Only NASA can afford to blow $150,000,000 on bonehead errors!)  Develop, debug, and test your robot control program in this test harness. The simulator:

·         Chooses a size for the crater and strews rocks in it.

·         Starts the gnat somewhere in the crater.

·         Creates the robot and starts your control program.

·         Graphically displays the crater and its contents

The simulator's graphical display:

·         Draws the gnat as a black disk. 

·         Draws the robot as a blue circle.

·         Draws rocks that the robot couldn't know about yet as hollow green squares.

·         Draws rocks that the robot has bumped into (but that the robot has not registered as known) as hollow red squares.

·         Draws rocks that the robot has registered as known as filled-in magenta squares.

·         Draws the current plan as black multi-segment line.

The simulator bumps the drawing whenever the robot crashes into a rock.

The simulator has two methods that your control program should use to update the display:

·         void registerRock(int x, int y) Invoke this method to let the simulator know that you know there is a rock at position x, y.  This is how it knows to draw a filled-in magenta square at x, y.

·         registerPlan(int steps, int[] col, int [] row) Invoke this method to let the simulator know your current plan. Pass the plan to the method as two one-dimensional arrays col and row, corresponding to x and y coordinates, respectively. Thus, the plan is to go from cell <col[0], row[0]> to cell <col[steps], row[steps] >.

Getting Started

To get started, obtain files Robot.java and Mars.java from the CS100 website. Create a new project using the CUCSGraphicsApplication stationery.  Delete the CUCSGraphicsApplication.java program file from the project, and add Robot.java and Mars.java to the project.

Run the project a few times to get a feel for what we have provided. (It won’t stop by itself, so you’ll have to stop it yourself.)  Observe the gnat flying around and the robot staying still.  Further observe that sometimes the robot cannot reach the gnat due to the rocks: Part of your assignment is to have the robot identify such situations and give up trying to reach the gnat.

Robot.java

Here is what we provide you in file Robot.java:

public abstract class Sensor {

       abstract public int value();

}

 

public abstract class Motor {

    abstract public void move(int direction);

    public Sensor x;

    public Sensor y;

    abstract public int clock();

}

 

// continued on next page

public abstract class DiagnosticPanel {

    abstract public void registerPlan

(int steps, int[] col, int[] row);

    abstract public void registerRock

(int x, int y);

}

 

public class Robot implements Runnable {

    // YOUR DECLARATIONS GO HERE!

 

    // Robot constructor

    public Robot

(int size,   // crater length and width

 Motor m,    // motor assembly

 Sensor sx,  // gnat's x position

 Sensor sy,  // gnat's y position

 DiagnosticPanel p // diag. interface

)

    {

       // YOUR CODE GOES HERE!

    }

 

    public void run()

    {

       // YOUR CODE GOES HERE

    }

}

 

A Sensor is a measuring device. If s is a sensor, then invoking s.value() gets the measurement from sensor s.

A Motor is an assembly consisting of two position sensors, an actuator for moving the robot, and a clock. If m is a motor, then invoking m.x.value() and m.y.value() gets the x and y coordinates of the motor. To attempt to move the robot to a neighboring cell, invoke m.move(d), where d is an integer in the range 0-3 that encodes directions as follows:

 

3

 

2

 

1

 

0

 

A motor may take up to 5 clock units to move the robot to a neighboring cell. To read the clock, invoke m.clock().

A DiagnosticPanel has two methods, registerRock and registerPlan, by which the robot can communicate with the simulator. These are described under Simulator above.

Robot is the control program. The simulator first invokes the Robot constructor with these arguments:

·         int size, the height and width of Rectangular Rock Crater,

·         Motor m, a motor object,

·         Sensor sx and Sensor sy, sensors for the gnat's x and y positions.

Then, the simulator invokes the class Robot's run method. The constructor is your chance to initialize the robot. The control program itself should be the body of the run method.

Additional Requirements

·         Fill in the Robot's declarations, the definition of the Robot constructor method, and the definition of the Robot run method.

·         The robot cannot avoid crashing into rocks that it does not know about, but it must not hit a rock more than once.

·         The robot must register known rocks and plans with the simulator so that the diagnostic display is correct.

·         If it is impossible for the robot to reach the gnat, the robot must (eventually) execute the following statement:

   throw new RuntimeException

("Gnat is unreachable!");

·         Use good style: indentation, comments, variable names, clear and concise code.

Hints

·         You will need to maintain a map of known rocks. We suggest that you treat the outer walls of the crater as a border of rocks. The coordinate system of Rectangular Rock Crater conveniently ranges between 1 (not 0) and the size of the crater, leaving room for your border.

·         Your flood-fill algorithm can use the same map for the distances from the robot as you use for known rocks. Just be sure to represent the rocks as some impossible distance.

·         Don’t forget to register the rocks and the plan with the simulator so they show up in the graphic display.

·         The robot needs to keep track of where it wanted to go.  That way, it can compare the location of where it wanted to go with its current, actual location (as given by the motor’s sensors) to determine if it has bumped into a rock.

·         You can slow down the simulation by entering a delay (in milliseconds) in the Console window.

What to Hand In

·         A printout of Robot.java.

·         A snapshot showing the Drawing window after your program has been running for a while. You can take the snap shot while the program is still running.  A color printout is not required.

Administrivia — Please Read!

Please feel free to write an elaborate private version that goes beyond our requirements for additional practice and your own enjoyment, but please hand in a program that does not exceed our specifications.

Programs are due at the end of lecture on the day assigned.  No late assignments will be accepted.  Programs will not be accepted in Carpenter on the day they are due, but you may hand in your program to a consultant in Carpenter until the close of business the day before the program is due.  You must give the program to a consultant personally.  Do not just leave it on a desk or table.

Program listings must be printed.  Output must be printed and be exactly as produced by the program handed in.  All printouts must be separate pages, without perforated edges, and stapled together in order.  The first comment in the program must contain your (and your partner's) name, Cornell ID#, section's day & time & instructor, and the assignment number.  These cannot be written in by hand.  You (both) must sign the first page of the program.