Comp150-07: Intelligent Robotics
Project 1 Graduate Version: Navigate an Unknown Maze

Checkpoint: Tuesday March 10, in class
Demo: Tuesday March 24, in class

The project 1 challenge is to design, build and program a robot to navigate an unknown maze towards an unknown but marked goal position while making a map of the workspace. This is a difficult challenge, so we will constrain it in the following ways: The project will take 2 weeks (3 including spring break) and demo day is Tuesday, March 24th, in class.

Demo day

On demo day, your robot will be placed in a random initial position and orientation within the constraints specified above, and it will need to drive towards the goal area while successfully navigating around obstacles using a short path, then drive towards the goal position within the goal area and stop as close to the goal as possible without actually touching it (or ramming into it). A stop within 15.25cm (6 inches) -- as in Lab 2 -- is considered an absolute success.

The path taken by the robot does not have to be the shortest path to the goal, so long as it's a short path, as defined by taking less than 12 minutes combined in 3 trials.

Additionally, your robot must map its surroundings and localize itself on that map while it's driving towards the goal. The robot should display its map as it is being built on the NXT brick's screen, which has a 98 x 62 pixel resolution.

Grading on demo day (70% of project grade, best of 3 trials or 12 minutes, whichever happens first):
A+ - successful navigation while avoiding obstacles (not even touching), stopped within goal radius of 15.25cm (6 inches), behavior can be described as intelligent (avoid exhaustive search, use what we learned in class so far), professional report presentation, reasonable map and robot localization displayed on the screen
A - obstacle(s) touched but recovered, otherwise successful (see above)
B - as for A, but stops anywhere in the goal zone
C - avoids obstacles and attempts navigation in approximately the right direction, but fails to stop, or comes to a stop before the goal zone is reached
D - does not avoid obstacles or does not attempt navigation but clearly does something useful
F - no show

Other behavior, good or bad, may be graded at the instructor's discretion.

Hand in: a team report discussing your design, early test results and obviation of failure, labelled picture of robot, and high-level description of code including (potentially revised) diagram from the checkpoint presentation (see below). Make it a coherent document using the guidelines from previous labs.

Checkpoint day

On checkpoint day (Tuesday March 10 in class), you make a short (5 minutes + 5 minutes for questions) presentation to the class about the overall design of your robot: both hardware and software. List sensors and chassis design, draw a flow chart or other diagram explaining at a high level how pieces of your control code will fit together. Justify your design decisions. Show a timeline with tests and assignment of team members to sub-modules of the design. The rest of the class is invited to critique and ask questions about your design (in a friendly and constructive manner).

You may make your presentation at the whiteboard or as digital slides (we can use the projector at the CEEO).

Grading on checkpoint day (30% of project grade):
A - Project decomposition shows modular software design and clear control flow between modules; timeline and tests are specified; a subset of modules and tests have been done and results discussed; potential difficulties identified and discussed; presentation is coherent and to the point; questions and comments are joyfully taken from the audience

There is no reason to get any other grade on the checkpoint, really. Grade will decrease (progressively) if anything from the above description is missing.

You will also have the opportunity to perform tests "on site" where the demos will happen. We will have a light fixture and some sample obstacles for that purpose. And, of course, you can discuss any issues with the project with the instructor and/or other students.

Tips and things to think about

You only have 4 sensor ports to work with on the NXT brick. You will need at least one light sensor to detect the goal light. You will need at least one sonar sensor to estimate distances to obstacles. And you will need at least one touch sensor to recover from touching an obstacle. Choose the fourth sensor wisely and position them on the robot in such a way as to make your life easier.

You can of course increase your sensory capabilities by using 2 NXT bricks on one robot. That would require you figuring out on your own how to set them up as a master and slave with bluetooth connectivity. It would also make your robot really tall, since you don't want to make it much wider than ~16cm (6 inches). I would recommend against using 2 programmable bricks unless you have lots of time and a particular interest in communications.

Your overall software architecture should take into account many of the things we have learned in this course so far. You may wish to include some aspect of the following in your design, although you are welcome to achieve the desired result in your own, different way:

You cannot assume that obstacles are on a grid (they are not), but you can impose your own grid on the workspace if you like, and estimate which grid cells are occupied by obstacles and which are not, e.g., using the histogrammic method. In that case, you may wish to use the technique of progressive refinement of the "mixed" cells in the grid to make sure you are not excluding an existing path because your grid is too low-resolution.

Effective teamwork, including brainstorming, labor division for easier modules and working together on tougher challenges, will be a great help in the project.

Test early and often, test components separately and together, test in different and difficult situations. Contact me early with any problem areas or questions. Don't get discouraged if you encounter failure -- this should be expected and treated as a learning opportunity. Good luck!

SLAM resources:

Note that most SLAM algorithms and implementations assume laser scanning abilities. You only have access to at most 2 sonar ranges instead. On the other hand, the problem you are solving is simpler as it is constrained and smaller-scale. I do not expect an accurate map, hence the word "reasonable" in the description. What is the best you can do with the resources and time that you have?


Paulina Varshavskaya, paulina at cs.tufts.edu