2015 Project 1A
Contents
Overview
Ahhh, life in the Navy. It’s not just a job, it’s a robotics problem! You wake up to the sunrise after your last night of liberty in Singapore. You probably drank too much, but it was worth it. Anyhow, you find yourself amidst hundreds of cargo containers bound for Malaysia. Your watch reads seven forty-five. Uh oh, you’ve only got half an hour to reach your ship before it leaves port. Good thing that from here you can see the mast of your ship. Unfortunately, you still must negotiate the maze of cargo between here and there. Which brings us to the problem. The challenge is for you to write an efficient C routine, navigate(), for navigation across a two dimensional field with obstacles. You will splice your function into the sailor’s brain, sailor.c, and see if he makes it home. As input, your function will get a list of nearby obstacles, and an approximate heading to the ship. It should return a value indicating which way to go. Your function doesn’t necessarily have to keep track of where the sailor is, the main program will do this. main() will repeatedly call your function and move the sailor in whatever direction you say until he reaches his ship.
If your function guides our sailor home, we can measure its efficiency in three ways:
- Path length: how far did the sailor have to walk?
- Brain cells: how large is your compiled function?
- Time: how long did it take? Remember, it hurts to think with a hangover.
More Detail
Here are more details on the rules of the game: For simplicity, this game takes place on a rectangular grid, so there are only a finite number of points the sailor can occupy. In fact, the grid is 23 by 80 cells, a convenient size for ASCII character animation. At each step, the sailor may move in any of eight compass directions: north, northeast, east, etc. (from here on out we’ll abbreviate these with capital letters). Moves E, W, N or S 2 units. Each time your function, navigate(), is called it receives a list of nearby obstacles and the direction to the ship. The obstacle list is an array of nine integers set to EMPTY, OCCUPIED, or GOAL depending on whether or not a cargo container is blocking the way or the goal is adjacent to the sailor’s position. Here is how the obstacle array is indexed:
NW N NE W SAILOR E SW S SE
These symbols have been defined for you in sailor.h, so the result of an expression like if (obstacles[NW] == OCCUPIED) would tell you if there is an obstacle to the NW of the sailor. The SAILOR element is always EMPTY. Note that if you ever command the sailor to move over an obstacle your command will be ignored. The direction to the ship is also given as one of the eight compass directions. If you’d like to keep track of the sailor’s location, you’ll need to declare some static variables on your own.
Download the code here: media:sailor.zip, then unzip it. On a Unix machine you can run a demonstration as follows:
unzip sailor.zip cd sailor ./demo
Your navigation algorithm should be written in the file navigate.c. We provide a simple reactive example for you. Here it is:
#include "sailor.h"
int navigate(int obstacles[9], int ship_direction)
{
int i;
if (obstacles[ship_direction] == EMPTY)
return(ship_direction);
if (obstacles[ship_direction] == GOAL)
return(ship_direction);
else
{
for(i = 0; i <= 9; i++)
if ((obstacles[i] == EMPTY) && (i != SAILOR)) break;
return(i);
}
}
Your Task
You are to write a memoryless function, navigate() in the file navigate.c. In terms of C code that means your navigate.c code can have no global or static variables. Your challenge is to write it so that it is able to solve as many potential navigation problems as possible. It should be able to solve all of the test_worlds/convexX problems that contain only convex obstacles. Note that there are some convex problems that may not be solvable due to the limited sensing your robot has. You will receive bonus points if your navigator can solve concave problems we throw at it.
Exception: It is allowable to use a static variable if necessary to support random number generation. That's the only use of memory allowed.
Resources and Ideas
The Bug 0 algorithm is a good place to start for a memoryless algorithm. Here's a link [1]. Once you have Bug 0 going, consider how it can be defeated and see if you can improve it. Hint: Any deterministic memoryless navigator can be defeated.
What to Turn In
Via t-square turn in attachments only:
- Your code in 1 file, navigate.c
- Your report in report.pdf
For evaluation purposes, all of your code should be contained within navigate.c. 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 problems with convex obstacles only.
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 convex1 through convex10 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.
