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


Forgot your password?
 

Assignment 5

Submission

Please submit an archive that contains all source and documentation files in a flat directory structure (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 "Assignment5". State your name, and IDs.

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

Exercise 

General

Your solution to exercise 5 should consist of all the provided source files including CMakeLists.txt (input to cmake), and a pdf file called 5.pdf.

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

The files can be found here. The zip contains one input example for the exercise.

Input

The program MotionPlanningForTwoRobots accepts 3 arguments on the command line:

  • The filename of the robots file, which contains the description of the robots.
  • The filename of the obstacles file, which contains all the description of the workspace obstacles. 
  • The filename of the output file.
inputRobots inputObstacles outputFile 

Polygons:

A polygons is counterclockwise in the sense that its interior lies to the left of its edges.

The workspace obstacles consists of zero or one polygonal chain that is a simple polygon oriented clockwise, followed by zero or more polygonal chains that are oriented counterclockwise.

The format follows

n x1 y1 x2 y2 ... xn yn
m
i1 x1 y1 x2 y2 ... xi1 yi1
.
.
.
im x1 y1 x2 y2 ... xim yim
An empty workspace, for example, is given by "0 0".
 

Robot file:

startPoint1.x startPoint1.y endPoint1.x endPoint1.y 
startPoint2.x startPoint2.y endPoint2.x endPoint2.y

The robots are given as plain points. This doesn't mean that they are shapeless! For your convenience, we already made the Minkowski-sum of the shapes and combined them with a 1x1 square - Which is the robot's size, both of them. On the other hand, this doesn't mean that the robot can't hit one another - The two robots touch one another iff |x1-x2|<1 && |y1-y2|<1.

You need to get both robots from their start points to their endpoints without touching one another.

Obstacles file:

obstaclePolygon(The outer boundary of the free workspace)
numberOfObstacles 
obstaclePolygon
.
.
.
obstaclePolygon
The first polygon represents the outer boundary: if it's empty(Polygon with 0 points) it means no boundary. All other polygons are disjoint and are inside the boundary polygon. Notice that those polygons are After Minkowski-sum. This means that you should treat the robots as points for your convenience (but notice that they can collide with one another!).

Output

Output file: 

This is handled by the code in main.cpp. The output consists of the first line for the number of elements in the output and then a 4-tuples of x1,y1,x2,y2 values. 

Instead, you should only implement the "findPath" function in main.cpp.

findPath function

input:

vector<pair<Point_2, Point_2>>
findPath(const Point_2 &start1, const Point_2 &end1, const Point_2 &start2, const Point_2 &end2,
         const Polygon_2 &outer_obstacle, vector<Polygon_2> &obstacles)
  • The start point and end point of both robots, respectively.
  • A clockwise polygon representing the outer boundary of the free workspace.
  • A container of counter-clockwise polygons representing the obstacles.
Polygons are pairwise disjoint except for, perhaps, at vertices.
 

output:

List of pairs of points starting from a pair of both start points of the robots (start1, start2) and ending at the pair of both endpoints (end1, end2), that represents a path that doesn't touch any obstacles and that the robots do not touch one another on it.

Visualization

you can download the preview program here.

python Preview_5.py inputObstacles outputFile

Test Cases

Verify that your implementation handles the four families of cases below.
We reserve the rights to test your implementations of additional cases...
 

Family 1

Every test case in this family has empty obstacles; that is, all test cases share the same obstacle file:

0
0

(It implies that the entire plane is free of obstacles.)

The start and end positions of the robot are chosen in such a way that at least one cannot move in a straight line.

There are two sub types:

  1. The robots simply have to swap:
    0 0 3 0
    3 0 0 0
  2. Either the start or the end configuration of one robot lies on the line segment between the start and end configurations of the other robot, for example
    0 0 3 0
    1 0 4 0
    There are 4 combinations, assuming the robots are symmetric (exchangeable), but you might as well test your implementation with all 8 combinations.

Family 2

Every test case in this family has one unbounded obstacle. Its complement, namely the free working-space, is a snake-like polygon depicted below.

snake_polygon_4.png
 
The Python script gen_snake_polygon.py, which can be found in the archive below, can be used to generate the obstacle file. The complexity of the generated polygon is specified via the command-line option "--turns n". For example, the polygon below is generated as the result of setting the number of turns to 1:
6
0.0 0.0
5.0 0.0
5.0 2.0
3.0 2.0
3.0 1.0
0.0 1.0
0
The robots have to swap, so the start and end configurations of the two robots is:
0 0 1 0
1 0 0 0
Naturally, you can try other valid start and end configurations.

Family 3

Every test case in this family has one unbounded obstacle. However, its complement is no longer a snake-like polygon but rather a maze such as the one depicted below.

maze

The Python script gen_space_with_rest.py, which can be found in the archive below, generates both the obstacle file and the robot file.

A simple input that can be generated using this script (providing 5 & 5 on the command line) is depicted below.

maze_like_player_1
=>maze_like_player_2

 

Family 4

The test cases of the families above can hardly be used to test the qualities of the paths generated by your motion-planning program (i.e., the sum of the lengths of the robot paths) . The following test case can be used to achieve that:

length

General

The visualization script as well as the two aforementioned test generators can be found here.

Both tests generator can be run with "-h" to see their requirements.
 
You have two types of tests generator, both of them will provide you with the polygons before the Minkowski sum. (You can use them as is, but you might as well run the Minkowski sum program on them before hand) 
The first tests will provide you with a snake-like polygon:
The second one will provide you with a maze like polygon, and start and end points. It's discrete, and as such an be tweek with an N and M parameters (matrix-like).
 
Good luck :)
Document Actions