CENG786 - Robot Motion Control and Planning
Homework #3 - Trapezoidal Cell Decomposition and Coverage

• Out: Dec 22, 2015
• Due: Jan 3, 2016

For this homework, you are required to implement a coverage algorithm for a point robot navigating in a polygonal environment based on a trapezoidal decomposition of the free configuration space. The homework has three parts. First, you should implement a function to take a polygonal environment specification consisting of non-intersecting polygonal obstacles and a polygonal boundary, and generate a trapezoidal decomposition using the sweep line algorithm. The decomposition should also generate an adjacency graph between trapezoidal cells, which you will use later for your planner. Second, you should implement a path-planner for this environment using A* search on the adjacency graph, taking the robot from any given point to any other given point. Finally, you should implement a coverage algorithm which exhaustively explores all trapezoidal cells. For this last step, you can use your laser range scanner implementation from your first homework.

As described in the assignments section of this web site, your submission should be in the form of a web page which nicely describes your work. Please do not collaborate with your classmates except exchanging ideas and other inspirational materials.

In summary, you should do the following for this homework

1. Implement a program to perform trapezoidal cell decomposition on polygonal environments consisting of non-intersecting polygonal obstacles and a polygonal outer boundary. You should visualize both the decomposition, as well as the resulting adjacency graph.
2. Implement a path planner based on this decomposition, taking the robot to the center (up to you to define what this means) of its starting cell, uses A* to find an optimal path in the adjacency graph and finally brings the robot to its destination point in the final cell.
3. Implement an algorithm to exhaustively cover the entire free workspace relying on the adjacency graph constructed in the first part as well as a laser range sensor to locate and trace trapezoidal region boundaries. You should attempt to minimize the amount of space covered more than once by the robot.

[ Home | Schedule | Assignments | Readings | Projects | Software | Resources ]

saranli@cs, Uluç Saranlı
The overall design of this web page was inspired by similar pages by Frank Pfenning.