Personal tools
You are here: Home Courses Algorithmic Robotics and Motion Planning Fall 2019/2020 Assignments Assignment 3: additional information
« September 2020 »
September
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
27282930
Log in


Forgot your password?
 

Assignment 3: additional information

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); Upload the archive to moodle, in the relevant submission box. Make sure to include in the archive a file where you state your names, IDs and explain in detail how to run the program.

Exercise 3.2

General

You may develop in Python or C++
Provide either a plain text fie called ex32.txt or a file in pdf format called ex32.pdf that contains the following:
  1. Instructions how to build and execute the program, and
  2. Assumptions and related information made while developing the code, such as whether the code handles degenerate cases.

Python
Use a single source file called ex32.py
Use Python 3, but do not use 3.8.
implement your code as described in the instructions below

C++
Use a single source file called ex32.cpp
Provide a CMakeLists.txt file, similar to this file
Running cmake on the provided  CMakeLists.txt followed by compilation and linkage should produce an executable called ex32
Make sure your program compiles and runs using a standard version of gcc on Linux
 

Input

The program should accept the absolute path (as a string) to an input scene text file,

The structure of the text file (scene.txt) is as in the following example:

200
230 500 0/3
230 700 1/5
3 300 400 250 250 450 100 
4 600 700 550 550 550 400 750 400
3 200 700 150 400 200 400
  • The first line represents the length of the robot as an integral value.
  • The second line represents the start position of the robot reference point as: x, y coordinates and an angle with the x-axis. The x,y coordinates should be integral values, while the angle  is represented as a rational number, whose value is between 0 and 2*pi.
  • The third line represents the target position of the robot (x,y, and angle).
  • The next lines describe the pairwise-disjoint polygonal obstacles, each obstacle is defined in a separate line as follows:
    • The first integral value represents the number n of vertices of the specific obstacle. 
    • It is followed by n pairs of coordinates, separated by spaces, representing the vertices of the polygonal obstacle in a counter-clockwise order.
  • You can obtain an example of an input file here

Output

  • If you are developing in Python then you should implement the function generate_path(path, length, obstacles, origin, destination) that receives 5 parameters:
    • path: a list that should hold the resulting path in the end of the call to generate_path
    • length: an integral value representing the length of the robot.
    • obstacles: a list of lists of tuples, where the i-th list represents the i-th obstacle
    • origin: a tuple (x, y, angle) of the origin position of the robot's reference point
    • destination: a tuple (x, y, angle) of the destination position of the robot's reference point
  • This function can be implemented in a separate py file. 
  • The function should add the configurations along the generated path by appending tuples (of length 4 each) to the list represented by the input parameter path. Each tuple represents a single configuration: its first 3 indices represent the x, y, angle values of the corresponding configuration as rational numbers. The last item in every tuple is either True or False, stating whether the transition from the previous configuration should be in a clockwise manner or not. Note that for the first configuration, representing the robot in its initial position,  this value is meaningless.  Here is an example of a possible implementation:
def generate_path(path, length, obstacles, origin, destination):
  path.append((FT(Gmpq(230)), FT(Gmpq(500)), FT(Gmpq("0/3")), True))
  path.append((FT(Gmpq(300)), FT(Gmpq(1000)), FT(Gmpq("2/1")), True))
  path.append((FT(Gmpq(230)), FT(Gmpq(700)), FT(Gmpq("1/5")), False))
    • If you are not developing in Python then your program should generate an output file named "path.txt" containing the configurations along the path, each appearing in a separate line. Each line should contain the x,y (rational) coordinates of the reference point, and the angle with the x-axis (as a rational number), followed by either c or cc, defining whether the transition from the previous configuration along the path is in a clockwise or counterclockwise manner. Below is an example of the content of an output file:
    230/1 500/1 0/3 c
    300/1 1000/1 2/1 c
    230/1 700/1 1/5 cc
    • If there's no valid path, generate_path should not populate path with any tuples. Respectively, generated output files should be empty in this case.

    Verifier

    We provide Python code for viewing the scenes and for validating your solutions. This code contains python bindings to various structures and functionalities in CGAL.

    Here are the installation instructions for Windows 10. In case you are working in a separate environment you'll have to compile the bindings on your own (Instructions can be found below and in the additional information for assignment 2).

    1. Install python 3.7 64 bit.

    2. Install PyQt5 via the following command in the command line - “pip install PyQt5”.

    3. If Microsoft Visual C++ is not installed on your computer download and run vc_redist.x64.exe from here: https://support.microsoft.com/en-us/help/2977003/the-latest-supported-visual-c-downloads

    4. Download "Python_code_hw3.zipfrom here. Extract the content of the zip file into a new directory. This zip contains a precompiled library containing Python bindings for CGAL as well as additional python files required for this assignment. 

    5. Important: The zip contained the compiled bindings in release mode. A compiled version of the bindings in debug mode is available here. The latter displays more informative errors, but is significantly slower than the bindings in release mode.

    6. Run the verifier.py script from this directory.

     
    For Linux users: a tar file containing the bindings code is available here. Note that it should be compiled, as in the instructions given in the additional information for Assignment 2.

     

    Running the script opens a UI window with the following options:

    • load scene: loads a scene from a scene txt file (as in scene0.txt), whose name is specified in the text box above the button
    • set destination: set the x y coordinates and angle value specified in the text box above the button as the destination coordinates
    • generate path: calls the function generate_path(path, length, obstacles, origin, destination), which is implemented in a py file whose name is specified in the text box above the button (relevant to Python implementations only)
    • load path: loads a path from a text file in the format of path1.txt , whose name is specified in the text box above the button
    • save path: saves a path to a text file, whose name is specified in the text box above the button
    • animate movement along path
    • Check path validity: display the swept volume of the robot along the path. Prints to the standard output whether the path is valid or not.
     gui_figure.PNG
     

    Collision detector

    We provide a basic collision detector implemented in a function named is_position_valid, which is located in collision_detection.py file.
    The function checks whether a given configuration of the robot (x,y,angle) is collision free or not. The interface of the function is as follows:
    is_position_valid(x, y, a, l, polygon_list, epsilon)
    where x,y,a represent the x,y, and angle values of a specific configuration. The value l represents the length of the robot and polygon_list represents a list of the polygonal obstacles as Polygon_2 objects. Finally, the value epsilon specifies if the robot will be checked for collision as is (if epsilon=FT(Gmpq(0))), or whether it will be transformed into a thin rectangle of width epsilon and length l+epsilon that will be checked for collision instead. The latter option is available since the path validity checker uses a thickened robot for verifying whether the returned path is valid. Here is an example demonstrating how to use the collision detector:
    poly_list = [Polygon_2([Point_2(0,0), Point_2(1,0), Point_2(1,1)])]
    x = FT(0)
    y = FT(-1)
    angle = FT(1)
    robot_length = FT(1)
    eps = FT(0)
    bool_res = is_position_valid(x, y, angle, robot_length , poly_list, eps)
    Important: Note that the path validity checker uses epsilon = 1. As a result, in your implementation you should use epsilon >= 1. When a higher value of epsilon is used,  checking the validity of an edge can be done more quickly (less samples along the edge are needed). However, it may cause the PRM roadmap to be have separate connected components for the start and target, and therefore not to find a solution.

    Examples of scene files 

    You may assume that all workspaces are bounded by a rectangle. This bounding box is part of the obstacles in every scene. You do not need to sample outside this bounding box.
     
    The following scenes are all new. In each scene a solution can be found in several minutes (at most 6 minutes), using a basic implementation of PRM with the basic collision detector that we provide.
    In fact, for most of these scenes a solution can be found in less than 3 minutes. 
    In each scene you may increase the length of the robot to obtain a more difficult scene.

    How to use the bindings of CGAL kd-tree 

    In your implementation you may want to use kd-trees.
    The following example demonstrates how to build a kd-tree for 3D points and use it for answering k-nearest queries in CGAL using the python bindings. The distance metric is the Euclidean distance.
    The parameter eps is used for approximate NN queries (if eps > 0). Otherwise, if eps=0, then exact NN queries are performed.
    from arr2_epec_seg_ex import *
    
    k = 3
    
    points = []
    points.append(Point_3(3,4,0))
    points.append(Point_3(-3,-4,0))
    points.append(Point_3(30,40,0))
    points.append(Point_3(-30,-40,0))
    points.append(Point_3(-1,1,0))
    
    tree = Kd_tree(points)
    
    all_points = []
    tree.points(all_points)
    for x in all_points:
        print(x)
    
    query = Point_3(0, 0, 0)
    
    eps = FT(Gmpq(0.0)) # 0.0 for exact NN, otherwise approximate NN
    search_nearest = True #set this value to False in order to search farthest
    sort_neighbors = False #set this value to True in order to obtain the neighbors sorted by distance
    
    search = K_neighbor_search(tree, query, k, eps, search_nearest, \
                               Euclidean_distance(), sort_neighbors)
    
    lst = []
    search.k_neighbors(lst)
    
    print("Found", len(lst), "neighbors")
    for pair in lst:
        print("Neighboring point is: ", pair[0])
        print("Distance from query is: ", pair[1])

     

    A user-defined distance metric can be used, rather than the Euclidean distance. The following example demonstrates how to specify a user defined distance metric for the k-nearest search.
    As a reference, you may use this example from the CGAL manual.
    from arr2_epec_seg_ex import *
    
    k = 3
    
    points = []
    points.append(Point_3(3,4,0))
    points.append(Point_3(-3,-4,0))
    points.append(Point_3(30,40,0))
    points.append(Point_3(-30,-40,0))
    points.append(Point_3(-1,1,0))
    
    tree = Kd_tree(points)
    
    all_points = []
    tree.points(all_points)
    for x in all_points:
        print(x)
    
    query = Point_3(0, 0, 0)
    
    
    #The following function returns the transformed distance between two points
    # (for Euclidean distance the transformed distance is the squared distance)
    def transformed_distance(p1, p2):
        return FT(Gmpq(1)) #replace this with your implementation 
    
    #The following function returns the transformed distance between the query
    # point q and the point on the boundary of the rectangle r closest to q.  
    def min_distance_to_rectangle(q, r):
        return FT(Gmpq(1)) #replace this with your implementation 
      
    #The following function returns the transformed distance between the query
    # point q and the point on the boundary of the rectangle r furthest to q.
    def max_distance_to_rectangle(q, r):
        return FT(Gmpq(1)) #replace this with your implementation 
    
    #The following function returns the transformed distance for a value d
    # Fo example, if d is a value computed using the Euclidean distance, the transformed distance should be d*d
    def transformed_distance_for_value(d):
        return FT(Gmpq(1)) #replace this with your implementation 
    
    #The following function returns the inverse of the transformed distance for a value d
    # Fo example, if d is a sqaured distance value then its inverse should be sqrt(d)
    def inverse_of_transformed_distance_for_value (d):
        return FT(Gmpq(1)) #replace this with your implementation 
    
    distance = Distance_python(transformed_distance, min_distance_to_rectangle, \
                               max_distance_to_rectangle, transformed_distance_for_value, \
                               inverse_of_transformed_distance_for_value)
    
    
    eps = FT(Gmpq(0.0)) # 0.0 for exact NN, otherwise approximate NN
    search_nearest = True #set this value to False in order to search farthest
    sort_neighbors = False #set this value to True in order to obtain the neighbors sorted by distance
    
    search2 = K_neighbor_search_python(tree, query, k, eps, search_nearest, \
                                       distance, sort_neighbors)
    lst = []
    search2.k_neighbors(lst)
    
    print("Found", len(lst), "neighbors")
    for pair in lst:
        print("Neighboring point is: ", pair[0])
        print("Transformed distance from query is: ", pair[1])
     
    Document Actions