2015 Project 1B

Overview

This project is the same as Project 1A except that you must solve *concave* problems.

Resources and Ideas

Potential algorithms to consider:

• Dijkstra's algorithm.
• Here's an old paper I wrote that discusses a solution: http://www.cs.cmu.edu/~motionplanning/papers/sbp_papers/integrated1/balch_grid_based_navigation.pdf
• A-star.

You are allowed to use algorithms you find on the web, however, your code must be in C, and you must submit your code and makefile so that it will compile and run within the "src" directory provided in the sailor package.

You must CITE your sources if you choose to use code or algorithms from the web.

What to Turn In

Via t-square turn in attachments only:

• Your code zipped in 1 file: src.zip
• Your report in report.pdf

For evaluation purposes, all of your code should be contained within src.zip and should compile using the command "rm sailor; make clean; make sailor" You can write your code on any platform you like, but it must compile and run on gekko.cc.gatech.edu (a standard CoC linux box). We will compile and test your code against the test problems distributed with the source code (look in the test_problems) subdirectory and against some of our own. We expect your code to solve all concave and convex problems.

Regarding your writeup. Be sure to describe your algorithm sufficiently well that someone else could implement it. Analyze your algorithm, explaining its strengths and weaknesses.

Scoring

We will test your navigate.c code against the concave1 through concave10 problems plus some others. 50% of your score will be tied to the proportion of problems your code solves. If you solve all of them you will get full credit on that portion. The other components: 25% for correct code and comments, 25% for report.

Extra Credit

The following are valid items for extra credit:

• You implemented D* or D* lite
• You believe your solution is especially elegant in some way:
  • Minimum computation
  • Minimum memory usage (no map)
  • Minimum code
• Your solution is new or novel

Your report.pdf for this project should focus just on what your extra credit submission is about.