Reference: An Algorithm for Planning Collision-Free Paths Among Polyhedral Obstacles by Lozano-Perez and Wesley.
(70 points) Part I: Write a progam to do 2-D collision-free motion planning. Your program will take as input a file which contains sets of ordered vertices of convex polygons which represents a set of obstacles in your world, along with a bounding box around the entire environment. You will grow these obstacles by the size of the Create robot (we will give you its convex polygonal dimensions) using the reflection algorithm and the convex hull algorithm discussed in class. Then, given an arbitrary start and end point in this environment, create a Visibility graph on these grown obstacles, and search it using Dijkstra's algorithm to find a safe, collision free path. Your program should graphically draw the following (see figure 3b below). You may use the programming language of your choice for this assignment.
Note 1: your program should create a safe path (if one exists) for any file of obstacles we give you, not just the test case.
Note 2: You do now have to grow the walls that enclose the working environment, you may assume that these are already grown obstacles.
Text file containing the description of the obstacles.
Format is as follows
Here is a picture of the start, goal and obstacles environment you will use for Part II below. Please note that for both sets of data, the X-Y axes are aligned with Z pointing up.
(30 points) Part II: ROBORACE 2015 Use your solution to generate path commands to have your Create robot follow the solution you computed above. We will set up a physical obstacle course and see which group's solution is the best: fastest and collision free, with prizes awarded to the winning groups. We will run the race during class time on Nov. 19 outside Davis Auditorium.
Extra Credit: (10 points) You may also use your robot mounted camera to visually "steer" away from obstacles your robot may encounter on its computed path.