Assignment 3 information

Announcements

• [4/4] Regarding due dates & deadlines: You can have an extension on submitting the program until midnight Friday night as long as you are in class tomorrow. I will accept the written report without late penalty until 10am Monday morning. (You can drop it off with Shannon Bornt in AE 132 or at the CS main office in Lally 207.)

• [4/3] Question:

     What do you want us to do when the user presses 'n' or 's' to process
     the next SONAR reading or scan. Do you want us to graphically to show
     the arc and the cone when the user presses 's'? Do we have to show
     anything when the user presses 'n'? What should I do when the user
     presses 'n' when all the scans for the existing reading are not yet read?
  

  Answer: It would be helpful if, after processing one or more readings, you at least draw a dot (i.e. a Location) at the robot's current position. You'll probably find it helpful to draw the sonar cone (or at least a circle and the two edges of the cone) also for you debugging. If you do so, please leave it in.

  When all the readings have been processed and the user presses, for example, 'n' you can just print a message saying that all readings have been processed. The program should not quit.

• [3/31] There are a number of updates to this web page regarding the following:
  • A new Tips section.
  • Slightly revised support code.
  • Additional sonar data (plus how you can create your own) and some example output. (See the Sonar data and examples section.)
  • Remaining details on the written report and submission instructions.

• [3/31] Here are some approximate times for my solutions to run on the various problems. These are on the Sun machine in my office. My 1GHz Linux laptop runs perhaps twice as fast.
  • Problem1.txt --- about 2 minutes for the 750 scans of 24 sonars (this used to be more like 3.5 minutes before I started discarding readings beyond a certain threshold.)
  • Problem2.txt --- about 6 seconds for the 58 scans of 16 sonars
  • Problem3.txt --- about 8 seconds for the 124 scans of 16 sonars

• [3/28] As announced in class on Tuesday, I have reduced the scope of the assignment by only requiring that you implement the Dempster-Shafer theory based mapping. However, I have slightly increased the scope of the assignment by asking you to leave some testing code in your program so I can verify the results of your tests. More details appear below in the written report section.

• [3/26] Oops. The permissions on the directory have been fixed, really this time.

• [3/26] The permissions/group problem has been fixed. You can now read the /projects/ira/assign3 directory.

• [3/25] The source code is in the /projects/ira/assign3 directory. There will be a handout in class tomorrow with some details on the code, but you can get started with it in the meantime.

Assignment information

• Tips
• Information on the written report
• Support code
• Sonar data and examples
• Submission instructions

Tips & Suggestions

• I'm coming to the conclusion that the first data set I provided (Problem1.txt and Sonar1.dat) is not a very good data set. You should probably work more with the new simulated data sets. I still expect to have some real data soon. (Once one of the undergrads in my lab can collect and format the data.)

• You will find that your results are better if you disregard at the maximum range (or above some threshold). The reason for this is that a reading at a large range tends to be from multiple specular reflections. A large range reading will start to "color" a lot of cells empty. Be sure to describe the details (i.e. how you compute the threshold you use or other relevant information) in the written report.

• As discussed in class Friday, determining the pixels in the sonar cone is probably the most difficult (or at least time consuming) parts of this assignment. You need to decide how to identify which cells are on the arc of the sonar cone and which cells are considered inside the cone.

  In my solutions, I used a modification of the graphics line and circle drawing algorithms that are part of the support code. Of course, these algorithms are designed to select pixels that visually represent the line or circle. This is not necessarily what we want for this assignment. (Hence the suggestion above that you figure out some criteria for whether a cell is on the arc or in the cone and then that you test your implementation in all the possible cases.)

  Were I to rewrite my solutions, I would probably select a different method of identifying the relevant pixels.

• Some suggestions for testing appear in the section on the written report.

• For the empty and full maps, please use the Grid::Grayscale[] values so I can check your maps. Here's the transformation that I use:

        int gsValue = (int) floor(emptyGridValue*64);
        if (gsValue == 64) gsValue = 63;
        G->setCell(r,c, Grid::Grayscale[gsValue]);
  

  where emptyGridValue is a floating point number between 0 and 1.

  For the combined map, you can use any scheme that you wish (including using color).

• As mentioned in class on Friday, I'm describing the written part as a "report" to convey that it shouldn't just be hastily scribbled answers but should be treated as a piece of writing. It doesn't need to be long but you need to address relevant details.

• If you are working on a Linux system, make sure you test your program on a Sun, since that is the platform where I will be doing my testing. There can be some differences due to numerical errors associated with floating point. For example, the integer 1, when expressed in a floating point number, might be actually slightly more (say, 1.000002) or less (say, 0.9999994) than the integral value. If you then take the floor of this value, the result might be different on different platforms.

  One solution to this is to add or subtract (as appropriate) a small number such as 1e-6 or 1e-5. There are several places in my solutions that I do this with x and y coordinates. For this problem, since our units are in meters, these numbers correspond to distances too small to be of practical interest for these algorithms.

• graphics.cc --- corrected two bugs, one which causes an error when the window is taller than it is wide and one which prevented ellipses from being drawn in the correct color.
• graphics.h --- removed an outdated ellipse class declaration
• smproblem.{cc,h} --- added an ellipse class that works with the (revised) drawableObject interface.

The other files are unchanged.

• Problem2.txt and Sonar2.dat contain data from this world. (The path of the robot through the world is shown in yellow.)

  As an example, here are the empty map and full map from my solutions using these data.

• Problem3.txt and Sonar3.dat contain data from this world. (The path of the robot through the world is shown in yellow.)

  ./simsonar Problem2.txt

You should be able to figure out the input files very easily if you want to generate some of your own data.

1. demonstrate that your program works correctly by present the tests you ran

2. describe/document the problems you solved (and your solution) in completing this assignment

3. evaluate the effectiveness of Dempster-Shafer theory based sonar mapping

These are described in the following sections.

1. Demonstrate that your program works correctly

You should test your program to make sure that these things are correct. I am also asking you to leave the testing code in your program (along with some way to run it) so that I can verify the test results in your report. The way that you do this is up to you, but I will suggest either:

• a command line switch that start your program in a "testing" mode and then reads in test commands from a file and displays the results, or
• key commands that can be given (during normal program operation) that run a test and display the result

I would recommend that test commands be read from a file --- this can streamline the testing process and is generally worth the time invested to write the code for it.

Here are some suggestions for these tests:

• Draw the pixels in the sonar cone and/or on the arc of the sonar cone, and overlay graphics on top of the image to show where the actual sonar cone is.

• Test that you are getting the correct set of pixels for different configurations and different sonar range measurements. (As I mentioned in class the other day, you need to do this correctly for the simple case when the cone lies entirely on the grip as well as for more complicated cases where the cone lies partially outside the image.)

  You can assume that the robot's position will always be contained in the grid.

• Make sure you cover all the cases. (Or alternatively, don't only test special cases.) For example, if you wrote a circle drawing routine and only drew circles at centers along the line x = y, you wouldn't know whether you switched the x and y coordinates. As another example, if your routine for determining the grid cells in the sonar cone works when the cone extends past the right side of the grid, that doesn't mean that it works when the cone extends past the left side of the grid.

  Exactly what inputs constitute a "case" depends on how your code is written. In theory, your tests should ensure that every line of code is run.

• Devise some test to verify that you are applying the update to the maps correctly.

2. Describing/documenting your program

3. Evaluating the Dempster-Shafer theory based mapping

You can create the file using the following commands:

$ cd ira/assign3
$ tar cfz whuang.tgz *.cc *.h Makefile

You can email me this as an attachment using your favorite mailer. If you want to mail it from a CS machine (at least the new Suns), the following command should work:

uuencode whuang.tgz whuang.tgz | /usr/ucb/mail -s "IRA Assign 3" whuang