Personal tools
You are here: Home Courses Algorithmic Robotics and Motion Planning Spring 2018 Assignments Assignment 1
« September 2020 »
September
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
27282930
Log in


Forgot your password?
 

Assignment 1

Submission

Please submit an archive that contains all source and documentation files in a flat directory structure for each exercise (that is, place all files of a given exercise in one directory); send the archive file via email to idokessler@mail.tau.ac.il with the subject "Assignment1". State your names, IDs and how to run the program in case the instructions deviates from the instructions below.

You don't have to use use CGAL for the programming exercises of this assignment.  However,  you are encouraged to develop in C++. If you want to develop in a different language, please settle it ahead with Ido.

You can develop on any platform, but the code must compile and run using g++ on Linux.

Exercise 1.1

General

Your solution to exercise 1.1 should consist of at least one source file, CMakeLists.txt (input to cmake), and a pdf file called oskar.pdf that describes the implemented algorithm.

Running cmake on the provided CMakeLists.txt followed by compilation and linkage should produce an executable called oskar.

Input

The program oskar accepts 7 arguments on the command line:

  • The source location of the robot, followed by the destination location of the robot, followed by the name of file that contains the description of the obstacle.
  • Each location is a vector of three integral values specifying the x, y, and z coordinates of the robot center.
  • A valid input file starts with the x, y, and z dimensions (in that order) of the puzzle followed by three matrices representing the xy, yz, and zx faces; 0 represents a free location and 1 represents a forbidden location.
  • The dimensions of the standard oskar puzzle are 11, 11, 11. One pair of source and destination locations is (3, 7, 7) and (5, 1, 1), respectively. You can obtain the file that contains the three (11x11) matrices here.
sx sy sz dx dy dz filename

Output

The program should export a series of commands to the standard output. Applying these commands to the robot should move it from the source location to the destination location without passing through forbidden locations. A command is encoded as follows:

0–move one unit along the x-axis in the positive direction
1–move one unit along the x-axis in the negative direction
2–move one unit along the y-axis in the positive direction
3–move one unit along the y-axis in the negative direction
4–move one unit along the z-axis in the positive direction
5–move one unit along the z-axis in the negative direction

Oskar Applet

http://www.cs.tau.ac.il/~efif/applications/puzzles/

To use the applet you must install the required plug-in.

To move Oskar:

  1. Place the output of your program in the Sequence text box, for example 4 4 5 1 2 3 4 0.
  2. Press the "Set Sequence" button.
  3. Download the file.
  4. Double click the file you have downloaded.
  5. Click on the bulb (the yellow circle in the scene).
  6. Sit back and relax.

Results

 
ID  200170504 302695721 304827132 304848336 310055959 311398499 312487861 313393381 315099895 315697011 322026527
ExampleTest INCORRECT CORRECT CORRECT INCORRECT CORRECT CORRECT CORRECT CORRECT CORRECT CORRECT CORRECT
time 141 110 78 78 63 79 94 218 78 94 47
Test_100x100x100 INCORRECT CORRECT CORRECT INCORRECT TIMEOUT CORRECT CORRECT CORRECT TIMEOUT CORRECT CORRECT
time 281 219 313 13015 TIMEOUT 9484 2625 1266 TIMEOUT 1422 4031
Test_10x7x10000 INCORRECT CORRECT TIMEOUT INCORRECT TIMEOUT CORRECT TIMEOUT CORRECT CORRECT TIMEOUT CORRECT
time 188 1281 TIMEOUT 7640 TIMEOUT 1484 TIMEOUT 937 609 TIMEOUT 360
Test_13x13x13 INCORRECT CORRECT CORRECT INCORRECT TIMEOUT CORRECT CORRECT CORRECT CORRECT CORRECT CORRECT
time 188 78 172 13953 TIMEOUT 78 4297 62 63 110 63
Test_14x14x14 INCORRECT CORRECT CORRECT TIMEOUT TIMEOUT CORRECT CORRECT CORRECT CORRECT CORRECT CORRECT
time 204 47 110 TIMEOUT TIMEOUT 78 4829 63 47 63 62
Test_15x15x15 INCORRECT CORRECT CORRECT INCORRECT TIMEOUT CORRECT CORRECT CORRECT CORRECT CORRECT CORRECT
time 203 62 125 9391 TIMEOUT 78 63 78 63 78 63
Test_20x20x20 INCORRECT CORRECT CORRECT INCORRECT TIMEOUT CORRECT CORRECT CORRECT CORRECT CORRECT CORRECT
time 219 78 141 13078 TIMEOUT 125 18938 63 47 94 94
Test_20x20x21 INCORRECT CORRECT TIMEOUT INCORRECT TIMEOUT CORRECT TIMEOUT CORRECT CORRECT TIMEOUT CORRECT
time 172 94 TIMEOUT 4641 TIMEOUT 94 TIMEOUT 63 63 TIMEOUT 93
Test_30x30x30 INCORRECT CORRECT CORRECT INCORRECT TIMEOUT CORRECT TIMEOUT CORRECT CORRECT CORRECT CORRECT
time 235 125 94 5531 TIMEOUT 375 TIMEOUT 78 78 125 125
Test_50x50x50 INCORRECT CORRECT CORRECT INCORRECT TIMEOUT CORRECT TIMEOUT CORRECT CORRECT CORRECT CORRECT
time 203 969 140 4781 TIMEOUT 1218 TIMEOUT 312 141 375 797
avarage time (without timeout) 203.4 306.3 146.625 8012 63 1309.3 5141 314 132.1111111 295.125 573.5
No support in uneven cubes. Wrong parsing but correct. Complexity Issue with very large cube. No support in uneven cubes. No support in uneven cubes.
 

Exercise 1.3

General

Similarly to the previous exercise, your solution to exercise 1.3 should consist of at least one source file, CMakeLists.txt (input to cmake), and a pdf file called fspace.pdf that describes the implemented algorithm.

Running cmake on the provided CMakeLists.txt followed by compilation and linkage should produce an executable called fspace.

Input

The program fspace accepts two arguments on the command line, namely, the name of the files that contains the description of the two input polygons.

Both files have the same format: An integral number that specifies the number of vertices followed by as many vertices; each vertex is a pair of rational numbers.

A rational number is given by a numerator and denominator separated by '/' (e.g., 1/3), where the numerator and denominator are both unlimited integers.

m x1 y1 x2 y2 ... xm ym

Output

The program exports the closed polygons that comprise the free space. Specifically, it exports the number of polygons followed by the interior-disjoint polygons. Each polygon consists of an integral number that specifies the number of vertices followed by as many vertices; each vertex is a pair of rational numbers.

Document Actions