CS W4733 COMPUTATIONAL ASPECTS OF ROBOTICS, Spring 2007

Columbia University, Computer Science
Department

COMS W4733, COMPUTATIONAL ASPECTS OF ROBOTICS, Spring 2007
Team Project 3, Due March 22

Reference: An Algorithm for Planning Collision-Free Paths Among Polyhedral Obstacles by Lozano-Perez and Wesley.

Part I: Write a progam to do 2-D collision-free motion planning. Your program will take as input a set of ordered vertices of convex polygons which represents a set of obstacles in your world, along with a polygon representing the boundary (walls) of the environment. You will grow the obstacles by the size of the PER robot 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 JAVA program should use the provided framework to render all of the following:

The start point
The goal point
The obstacle set
The grown obstacle set
The Visibility Graph
The safe path

Note your program should create a safe path (if one exists) for any file of obstacles we give you, not just the test case.

Part II: Use your solution to generate path commands to have your PER robot follow the solution. We will set up an obstacle course and see which group's solution is the best: fastest and collision free.

NOTES:

Assume a fixed orientation of the robot (i.e. translational motion only). Assume the robot is facing to the right.
Use your team resources wisely. One team member can write the algorithm to grow the obstacles using reflection and convex hull, one can write the algorithm to compute the Visibility graph and one can write the Graph Search algorithm .

Provided Material:

Source Files: contains provided source code and below input files. Can be directly imported into eclipse.
Obstacles File
Start/Goal File

In case you wish to create your own obstacle files for debugging, the obstacle file format is as follows

first integer gives you the number of obstacles
for each obstacle:

first integer gives you the number of vertices
the vertices follow, one per line, each with two coordinates
you should close the obstacle by linking the last vertex to the first

the first obstacle in the file actually specifies the wall that encloses the working environment.

Similarly, the start/goal file format is:

first line (two coordinates) determines the start point
second line (two coordinates) determines the goal point

To allow your team to focus on the algorithmic aspects of the assignment, a GUI and basic framework is being provided to facilitate the loading of the files and rendering of the GUI.

Figure 1: PERPathPlannerMainUI

Figure 1 shows the provided GUI rendering each stage of the path planning:

Original Obstacles (plus wall boundary) & Start and End Points
Grown Obstacles
Visibility Graph
Shortest Path

The code being provided loads the obstacles and start/goal points. Once you implement the required algorithms and calculate the grown obstacles, visibility graph, and shortest path, they can be rendered using the provided GUI. To facilitate debugging, you can choose which elements are and are not displayed by using the "View" portion of the menu. Also note that you are not required to utilize the provided framework, but you are responsible for ensuring that all of the above information is displayed via some GUI.

Overview of the provided framework:

Vertex.java: Helper class for representing Vertices
Edge.java: Helper class for representing Edges (defined as a list of vertices
Obstacle.java: Helper class for representing obstacles (defined as a list of edges)
SceneMap.java: Helper class for storing the obstacles when rendering within PathPlannerMainUI
PathPlannerMainUI.java: Program entry-point and Main GUI

To actually connect to the PER, pass the PER's IP address on the command line (i.e. "java PERPathPlanner.PathPlannerMainUI 192.168.2.115").
To just work on the algorithms, simply run the program without any arguements

VisibilityGraph.java: provided version parses the input files and creates the appriopriate Objects. Implement computeVisibilityGraph(...) and all dependent functions.
DijkstrasAlgorithm.java: implement calculateShortestPath(...)
PERController.java:
- used for actually controlling the PER
- implement followPath(...)

Citation: The provided code is derived from a similar assignment written by the Red Terror group (David Lariviere, Anita Verma, Aaron Roth, and Leo Gertsenshteyn) for CS4733 in Fall '05.