Columbia University, Computer Science
Department Columbia University, Computer Science Department

Homework 4, Team Project, Due Wednesday, Nov. 18 11:59 PM.

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.

Figure 1: Sample output for homework 4

Figure 1 shows a GUI rendering of each stage of the path planning:
  1. Original Obstacles (plus wall boundary) & Start and End Points
  2. Grown Obstacles
  3. Visibility Graph
  4. Shortest Path

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

Text file containing the start and goal point for the path planning algorithm.

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.