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

Forgot your password?

Assignment 5


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 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.



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.


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 


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
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)
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 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


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.


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.


you can download the preview program here.

python 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:


(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.

The Python script, 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:
0.0 0.0
5.0 0.0
5.0 2.0
3.0 2.0
3.0 1.0
0.0 1.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.


The Python script, 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.



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:



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