Assignment 1 information

• I've created two test worlds (and associated problem files) in the worlds.zip file. This zip file contains the files:
  • world1.txt, problem1.txt — a world with no path to the goal

  • world2.txt problem2.txt — a world with two paths to the goal. the best path is more difficult to find than the other.

  Note that I've made the radius of the robot in these problem files smaller (0.2 meters) than in the problem file in the support code. This is (approximately) the radius of the MagellanPro robot that you'll be using, by the way.

• I've created a quick reference guide for dolt-lite. (I'll hand this out in class on 2/2.)

• Support code:

  • worlds.zip — two test worlds

  • assign1.zip — assignment support code [updated 2/7]

    The 2/7 update is a bug fix: only one line of the input.h file was changed, and this should prevent the runtime error some of you have been seeing under windows. You can just replace that file, but the zip archive has been updated too.

  • dolt-lite.zip — graphics library [updated 2/1]

    The [2/1] update is not essential — the main change is that a Vertex_const_iterator was added to the Polygon class. There was already a Vertex_iterator, so this is not strictly necessary, but if you are passing const references (as you should!), then this is useful. Instead of entirely reinstalling dolt-lite, you can just replace the file geometry.h as that is where the changes are. There are a few other minor changes, e.g. visual studio project files added for the test program, minor updates to the unix configure script, etc.

• Files in the support code
  • assign1.cpp — main program, where you will write your code
  • input.h — stuff for reading the problem and world files
  • intersection.{cpp,h} — line segment intersection
  • problem.txt — problem parameters
  • world.txt — world description
  • win32 — directory with MS Visual studio project files
  • Makefile — UNIX makefile

  Testing, written questions, and submission information

  Your answers to the written questions are to be turned in on hardcopy. They are due in class on the day the assignment is due.

  Any late papers should be turned into the CS main office (Lally 207) to be put in Prof. Huang's mailbox.

  0. Please note that your program should print the following to standard output as you do the sampling, generate the graph, and find a solution.
     • the values of N and k
     • the number of samples generated to get N collision-free points
     • the number of edges in your graph
     • the length of a path (if found) or that your program could not find a path

     You will need this information for the first question anyway.

  1. Create at least 3 more worlds (of your own design) to test your code on. Call these worlds world3.txt, world4.txt, and world5.txt. At least one of these worlds should be more constrained (i.e., as hard or harder to find a path) than the difficult-to-find path in world2.txt. You should also create associated problem files, problem3.txt, problem4.txt, and problem5.txt.

     For worlds 2 through 5 (the second one i gave you and your three worlds), run your program to plan a path for the robot, both for random and quasirandom sampling. Determine reasonably small values for N and k for which you can find a path. (They need not be the absolute smallest, but you should try to find small values.) For random sampling, these values should be able to produce a path at least 3 out of 4 attempts.

     Turn in a table that shows, for each world and for each sampling method:

     • N and k
     • number of points sampled in order to get N collision-free points
     • number of edges in your graph
     • length of the resulting path
     • did your program find something close to the best path? (i.e., a path that goes around the obstacles in the same way as the best path)

     For random sampling, you should report average values over 3 or more trials. (Specify how many trials.)

  2. In practice, motion planners can always sample more points if a solution is not found; if a solution is still not found after some number of additional points, the planner will give up. However, this question is about determining initial values to use for N and k.

     How did you determine values for N and k? Can you suggest a general rule for selecting values? You might suggest certain fixed values if they work well, but otherwise, is there some approach to picking values as a function of some simple properties of the world?

     Explain why your suggestions are good ideas.

  3. Characterize how randomized sampling compared with quasirandom sampling, i.e., was one approach better all the time or on certain kinds of worlds? Give a detailed explanation of your answer.

Turning in your code

• You should create either a zip file or a gzipped tar archive. Include all the source code files that we need to compile your program (including any unchanged support code files). Also make sure you include your world files and associated problem files.

  Do not include any executable or object files!!! Your archive file should then be fairly small, like under 20 KB. We'll probably just delete any archive file that is larger than that.

• Email your archive file to irastaff@cs.rpi.edu.