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 workspace/maze will fit within 250cm x 125cm (approximately
98.5"x49.2").
- The robot's initial position will be somewhere in the rectangle
defined by points (0,0) and (40,125), which is free of obstacles.
- The goal position is marked by a lightbulb fixture just like the one in
part I of Lab 2. The light is a regular 60W bulb. The goal position
is somewhere in the rectangular goal zone defined by points
(210,0) and
(210,125), which is also free of obstacles.
- In between, there is some number of obstacles, which are
all polyhedral, but can be convex or concave.
- There may be an opening between obstacles that is less than the
width of your robot, but a path will exist through the maze with at
least 25 cm (9.8-inch) clearance.
- The obstacles are not placed on any grid.
- There is a wall around the perimeter of the workspace to help
you stay within bounds.
- The robot's original orientation will be at most 60 degrees off
from the line-of-sight direction towards the goal.
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:
- A subsumption-style architecture for recovery from navigation failure
(where the robot does touch an obstacle as recorded by a touch
sensor) and for stopping when goal is reached
- Good odometry over short distances/angles to make sure the
robot goes where it wants to go, and to keep track of where it has
been
- (Relative) localization of obstacles to compute obstacle-free
potential direction(s) of motion
- (Chunks of) configuration space around the perceived obstacles
in order to disqualify potential paths with too little clearance
- A representation of the workspace or immediately observable
workspace in which to plan a course of action
- A path-planning algorithm such as the wavefront algorithm or A*
search on a graph
- Underlying geometric reasoning about where things are in
relation to each other given odometry and sensor history, current
sensory information and initial conditions
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