Robot Assignment

CAUTION: Don't get carried away on the GUI part of this assignment. The marks you will get for that part are limited because that's NOT what this assignment is about.

We have a mobile robot. Our assignment is to make it so we can have the robot move independently around a building and maybe even do stuff.

has 3 sensor ports (for touch, light, rotation, or temperature sensors)
3 output ports (for motors, etc.)
4 control buttons
LCD display
built-in speaker
internal counter
internal timer
If you're really keen, the firmware specs for the above pictured processor can be examined (note: The firmware documentation is in PDF and totals 108 printed pages): http://mindstorms.lego.com/sdk2/index.html

Specifications:
Part 1: Data Representation / File / Interface Design

Design the Data Structures used to Represent some Physical Space
Design the File Structure that will allow efficient access to the Spatial Information
NOTE: You are NOT bound by your initial design - if you think of ways to improve it and have the time to do so, then you may do that but be sure you discuss it in your final document and explain (justify) your changes.

Assumptions:

The map is on a single level (no stairs, hills, or noticeable bumps) i.e. 2D
any doorways noted on (in) the map will be unobstructed
there will be no unexpected obstacles (nothing that isn't on the map)
measurements are to be made in meters
turns are to be described in degrees
the batteries in the robot will not run out


Hints:

Start with a very rough design of how you want to do the pathfinding algorithm
this will suggest ways to store the map,
which in turn will suggest ways to have the user describe the map
Make a VERY ROUGH outline (still readable though) and run it by your TA before beginning to code.



Design the Interface Between the Robot and The Outside World

Since we don't have the actual robot (well, you don't anyway), we will have to 'pretend'. Our map representation and pathfinding program will be written as though we were going to be able to download them into the robot's processor. We will assume it can cope with our executables and our map data. We do need to remember to keep things as small as possible. The processor is not large nor is it powerful.

Our interface for this assignment is a simulated one rather than an actual one (what do you call an artificial AI?).

We need to be able to create the raw data files using an editor. 2 possible approaches come to mind:

Have the map entered as a 2-D grid of characters, where each character position has a scale factor (such as 1 char = 25cm):

*	*	*	*	*	*	*	*
*	.	.	.	.	.	.	*
*	*	*	.	.	*	*	*
*	*	.	.	.	.	.	*
*	.	.	.	.	.	.	*
*	.	.	*	*	.	.	*
*	.	*	.	.	*	.	*
*	*	*	*	*	*	*	*

Keep in mind that a map of a small area (like a bathroom) may want to use a different scale than one of a large area (like the entire 2nd floor).

Describe an area as a series of vectors [x,y] endpoints of each wall, etc.


Input Required:

The map (in the form of a "raw data" file, which must be ASCII, and must be annotated)
the robot's current location (and orientation)
the robot's destination

Output Produced:

The "trip": a description of the path taken by the robot, if we had a robot

Part 2: Implement the Above Designs

Make absolutely certain you can verify that your programs works.
TAs are NOT required to spend time puzzling out how to make your code work or in making sure it is correct. It is YOUR job to prove (not formally) this to your TA's satisfaction. A program that cannot be verified will be judged to be a non-working program (which can't get more than a 'D')

Part 3: Post Mortem
Examples: http://www.gamasutra.com/features/index_postmortems.htm
The preceding link leads to numerous "postmortems" of various computer games. Please look at some of them to see the kinds of things they discuss. Your own post mortem must be well-organized, clear and to the point. Fewer words are almost always preferable over more. Proper grammar is essential.

Analysis and Discussion:
Describe and fully justify your structure(s) :
- Your implementation should make efficient use of space and minimize processing time and searching as much as possible. Justify all design decisions regarding data structures used and how they affect efficiency and speed.
- Comment on any special problems encountered as a result of your design and possible solutions or modifications recommended for the next version.
How is the spatial information implemented?
- diagrams (like UML or some such) are acceptable

What kind of search did you implement? What makes it efficient? What are the costs? Why did you choose this one?

Keep it simple.
Speed and efficiency are very important.
Be sure to keep the interface in mind.
The data file must be relatively small in size because it will have to be downloaded to the robot before it can be used and you can't count on much there.
This software to generate the raw data file need only run on the server's machine (Sun Ultra's running Solaris) This part of the assignment does not have to be done in C, C++, or Java. Any language, utility, or combination thereof is acceptable. Other suggestions: Awk, Perl, Python, Ruby, ????
VERY IMPORTANT!!! You may make use of existing code found on the net or elsewhere but you MAY NOT use any code "wholesale" (i.e. in its entirely, w/o modification, and you MUST acknowledge your sources). Failure to follow this requirement constitutes cheating and such a submission will be given an 'F', along with a letter of explanation to the Department Head and Dean of Science. NO EXCEPTIONS.
Make use of the facilities and utilities provided by the operating system (UNIX).
Make sure you are able to justify all of your decisions.

Requirements:

Raw data file must be readable as ASCII
The total space you have available for the data file and pathfinding program is 32K. You must be able to load both the data and program as well as run the program in that space.
Your 'system' must be able to read the raw data file and create an 'internal representation' of the data. This must be in the form of a binary file that can be stored apart from the system. The idea here is that we want to be able to create a number of maps and store them. Then, when we want to use one of them, we will simply download the map into the robot and go on from there.
Your system must be able to input a source and destination given within the context of an existing map. You must decide on the format for this - it should be as simple as possible.
Finally, your robot simulator (the AAI?) will produce as output a description of it's trip or the moves it must make to get from the source to the destination.

The format of the raw data file need not be related to the internal data format for the map. It's just that certain combinations will make life easier for everyone and others will make it harder.

The deadline for this part is flexible but be warned!!!!!!!!!!!!!!!!!! If you don't pace yourself properly and spread out the work reasonably, you will never get this working!

You MUST make it easy to verify that your program converts the raw data correctly AND that the pathfinding algorithm works correctly (i.e. the robot starts and ends where it's supposed to; it does not pass through walls, etc.) This can be done with graphical output or hand-drawn diagrams. You can display your binary file using UNIX's od and annotate the output. You can create diagrams that illustrate the organization of your data as well as the function of your pathfinder.

CLARITY is CRUCIAL. Clumsy, choppy documents with poor flow will be rejected. Remember that you are writing TECHNICAL documents, not stories. They need not be dry or boring but neither are they indented as entertainment.

*	*	*	*	*	*	*	*
*	.	.	.	.	.	.	*
*	*	*	.	.	*	*	*
*	*	.	.	.	.	.	*
*	.	.	.	.	.	.	*
*	.	.	*	*	.	.	*
*	.	*	.	.	*	.	*
*	*	*	*	*	*	*	*

*	*	*	*	*	*	*	*
*	.	.	.	.	.	.	*
*	*	*	.	.	*	*	*
*	*	.	.	.	.	.	*
*	.	.	.	.	.	.	*
*	.	.	*	*	.	.	*
*	.	*	.	.	*	.	*
*	*	*	*	*	*	*	*

*	*	*	*	*	*	*	*
*	.	.	.	.	.	.	*
*	*	*	.	.	*	*	*
*	*	.	.	.	.	.	*
*	.	.	.	.	.	.	*
*	.	.	*	*	.	.	*
*	.	*	.	.	*	.	*
*	*	*	*	*	*	*	*