Copyright © 2002 Katrin Becker 1998-2002 Last Modified November 15, 2001 02:09 PM

Programming Assignment:

NOTE: The programming parts of this assignment are worth ~2/3 of the total marks. The other 1/3 is for documentation and discussion.

MOBILE ROBOT

CONTENTS of THIS PAGE...Goals, Skills & Concepts Introduction & Background Description Specifications Approach Minimal Requirements ('C' version) ('B' version) ('A' Version) Testing and Marking Bonuses Challenge

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.

For The Robot:

The "legOS" site - another O/S for the robot (with a java-based simulator) - free to download - for Windows, Linux, & UNIX platorms

A few sample maps as .jpg images:
Map 1, Map 2, Map 3, Map 4, Map 5

Goals, Skills and Concepts:

Problem breakdown ; structures design; system design; verification & testing; design documents; user documents

Introduction and Background:

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.

For example: I want to be able to put the robot down anywhere on the second floor of the Math Sciences building, tell it where it is, and have it go to Darcy Grant's office.

All Images Credit: LegoMindstorms

Description:

Robot Processor Specs:

NOTE: none of the specs below are necessary for the basic solution

- 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:

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

Hints:

1. Start with a very rough design of how you want to do the pathfinding algorithm
2. this will suggest ways to store the map,
3. which in turn will suggest ways to have the user describe the map
4. 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?).

1. We need to be able to create the raw data files using an editor. 2 possible approaches come to mind:
   1. 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).
   2. Describe an area as a series of vectors [x,y] endpoints of each wall, etc.

Input Required:

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

Output Produced:

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

Part 2: Implement the Above Designs

1. Make absolutely certain you can verify that your programs works.
2. 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?

Approach:

Hints:

- 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 & Grading:

Requirements:

1. Raw data file must be readable as ASCII
2. 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.
3. 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.
4. 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.
5. 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!

The program used to convert the raw data into the format you have designed for your robot will NOT be downloaded into the robot and need not meet the size constraints.

If you do NOT submit the first report (the design) you will loose 1 full letter grade on your project. (But it doesn't count as an assignment element that was not handed in - i.e. you won't fail if you don't hand this part in. You WILL fail if you don't submit the other two parts!!)

'C' Version:
Average effort;
Minimal requirements (as above) correctly implemented.
Needn't be exceptionally efficient but should be reasonably justified and documented.

'B' Version:
Better documentation;
Submitted initial design;
Good user I/O (graphical output of map / trip)
It should be relatively simple for the user to figure out how to create the raw data file and use the system.

'A' Version:
Clean; clear; few faults.

Testing & Documentation:

You are responsible for all your own testing.

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.

BONUSES:

1. Handle small tolerances (i.e. 12" passageways rather than only full-sized doorways and big fat hallways)
2. Find the Minimal Path.
3. Use sensor input to augment map data
4. Have the robot compensate for minor map errors (need sensors)
5. As in bonus 4 but have the robot 'fix' the map

Challenges:

1. Handle obstacles.
2. Handle 3-D space.
3. Have the robot build it's own map - as it's learning about where it is. When given a location and destination it will use what it has and augment (build) the map as it is searching for the destination.

Copyright © 2002 Katrin Becker 1998-2002 Last Modified November 15, 2001 02:09 PM