Assignment 2
CSCI-4965/6963: Robot Motion Planning
Fall 2001

FAQ

• Some of you may be running into problems because of floating point issues. For example, if you find the intersection point of two lines (a_1x + b_1y + c_1 = 0 and a_2x + b_2y + c_2 = 0) and substitute back the x and y coordinates of the intersection point into the expression a_1x + b_1y + c_1 (or a_2x + b_2y + c_2), the resulting value may not be exactly zero. One workaround is to define a constant epsilon set to some small value, and for such tests, treat any number with absolute magnitude less than epsilon as being equal to zero.
• For those of you who developed your C++ code using Visual C++ and are having trouble compiling your code on the Solaris machines: Here is an example Makefile that we used to compile the polymaker GUI on our Solaris machines. The polymaker source code consisted of polymaker.cpp and a poly.h header file. It also used a bunch of OpenGL related libraries. You will need to modify this example Makefile for your code.
• NEW: The submission script is now working. Please go to the "Submission Instructions" section below and follow the directions.
  
• If you are using the line equation y = mx + c to compute intersections and running into problems of infinite slope for vertical lines, use the form ax + by + c = 0 instead.
  
• You are not required to use only Dijkstra's algorithm to compute the shortest path. However if your search algorithm does not return the shortest path, you will not receive full credit.
  
• You can assume the initial and goal configurations are not in the interior of the obstacles and also that they are not on the vertices or edges of the obstacles.
  
• If you wish to submit a hardcopy description of your program and algorithms (*in addition* to the stuff you are to submit electronically), that's fine.
  
• You do not need to compute the reduced visibility graph.
  
• Look at the Labs section below for information on remote access.
  
• Note that you cannot assume a fixed limit on the number of edges of a polygonal obstacle.
  

Description

• Assignment 2. postscript file, pdf file.

GUI

• **Updates:** The executables below were updated on September 27 at 9:40pm. The new version can read in polygons and lines with floating point coordinates.
• **Updates:** The executables and the readme file below were updated on September 26 at 1:15pm.
• polymaker executable (for Solaris machines). After downloading, make sure it is an executable file. (Use "chmod +x polymaker" otherwise.)
• polyMaker.exe binary (for Win 32 machines). You may also need the GLUT DLL.
• readme.txt
• Example input/output format files for polygons polyfile.txt and for line segments linefile.txt

Program specifications

• Here are the specifications for your program. It will be given the input file with polygonal obstacles and the initial and goal configurations as command line arguments, as below:

  % visgraph inputpolyfilename xinit yinit xgoal ygoal 
  
  

  For example, the input file may be obstacles.txt , xinit may be 30, yinit may be 90, xgoal may be 65, and ygoal may be 25.

  Your program should output the coordinates of the vertices on the shortest path to the screen. It should also generate a file "path.txt" with the line segments of the path specified as bold lines in the same format as linefile.txt. You must also additionally specify all the visibility edges as regular lines in "path.txt". For proper displaying, make sure you list all the bold lines of the path before you list the regular lines of the visibility edges in "path.txt".

• Your code must compile and run on the Solaris machines in the labs in Amos Eaton (see below).

Labs

• You can use the Sun Ultra10 machines in the Sparc Lab in Amos Eaton 217 or the OOT Lab in Amos Eaton 117. You should already have a CS ID and password to log on to these machines.

• There is an alias that has been created for remote access:
  solaris.remote.cs.rpi.edu
  will connect you to one of 16 computers running Solaris 8. This is the preferred machine name to use if you require remote access to lab machines running Solaris 8. Please do not access machines directly by their name unless you have a compelling reason to be using a specific computer. Certain computers come and go off our network, and reliance on a particular computer may cause you problems later on.

  These machines do not accept unencrypted connections. You should use some version of ssh to connect. If you are connecting from a PC, you can get TeraTerm with SSH extensions from our web page at: http://www.cs.rpi.edu/lab/software

• Note: The Sparc Lab and OOT Lab are usually locked over the weekend, so make sure your code compiles and runs on a machine in the Sparc lab well before the weekend. There may be students working in the lab over the weekend -- you can enter and use the lab over the weekend if you are able to get in.

Submission Instructions

• You will need to have all the source and header files, Makefile, README file, and any other files you are submitting in a single directory on a CS machine.
  You will submit your assignment by running a script that tars and gzips files in the source directory, and emails the uuencoded file. You will automatically receive an email acknowledgment of your submission (sent to your CS account).

• To submit your assignment, follow these steps:

  1. You must be on a CS machine running UNIX. The Ultras in the Sparc lab will do fine.
  2. Go to the directory in which all your source code (source and header files), Makefile, and README file are placed.
  3. Type "submit rmp" at the prompt.
  This script will automatically tar, gzip, uu-encode and email the entire directory contents. It tries to be smart about not including executable and object files, core files, etc.
  4. You will receive an automatic email reply showing all the files that were submitted, along with a timestamp. This email is sent to your CS account, so be sure to check there or forward email from there to your RCS account.
  

  Let me know if you have any problems with this submission procedure.

• Note that you can send in multiple submissions. We will use the most recent one for evaluation of your assignment. The corresponding timestamp will serve to determine the penalty for late submissions.

• Your assignment must be submitted before 11:59pm on Monday, October 1.

• Important: Please save your submitted assignment files (without modifying them) until your assignment has been graded.