Lab 5: Search and Localize

VHDLDesign Principles & Methods 
Lab 5: Search and Localize
Submission instructions: Students will work for the first time in their design teams
(team list posted on MyCourses). Similar to prior labs, this lab consists of three components:
demonstration, code submission, and lab report. Demonstration instructions can be found here.
Lab reports and code submission must follow the guidelines established in this handout and for
the course. The lab report grading scheme has been changed, so carefully read the
instructions below. For more information, see the submission instructions on MyCourses.
Note that as you are now working in design teams, code and report submissions are expected
to follow the naming convention Team#_Lab#.zip or Team#_Lab#.pdf as appropriate.
Design objectives
1. Implement a robot with ultrasonic and color sensors for determining the location and color of
a ring without physical contact.
2. Starting in a known corner, localizing to the grid, and performing a search along a specific
path for a colored ring of known dimensions
Design requirements
The following design requirements must be met:
● The system must satisfy the design requirements from Lab 3 with respect to localization:
o You must follow the (X,Y,θ) convention specific to this lab (refer to Figure 2).
o You are free to use any localization method (with or without light localization).
o You are not required to provide a way of selecting rising or falling edge.
o You do not have to wait for user input after completing ultrasonic or light localization.
● The system must follow the same navigation requirements as in Lab 4:
o The robot must navigate through a series of specified points using the minimal
distance.
o A list of waypoints must be provided in one location in the code.
o The robot must use the grid system found on the play floor, where the origin is the
starting corner of a tile.
o Waypoints will be given with respect to the tile grid system. For example, (1, 0) will
be located 30.48 cm to the right of the origin (0, 0).
o When turning to a waypoint, the robot must use the minimal angle needed to turn to
it.
© Instructor and Teaching Assistant generated course materials (e.g., handouts, notes,
summaries, assignments, exam questions, etc.) are protected by law and may not be copied
or distributed in any form or in any medium without explicit permission of the instructor. Note
that infringements of copyright can be subject to follow up by the University under the Code of
Student Conduct and Disciplinary Procedures.
1/10
ECSE 211 Design Principles & Methods 12
th February 2020
● Your robot must be able to localize in the starting corner, navigate through the given
waypoints, detect the color of every ring along its path, and signify when it has reached the
end of its course with 3 beeps.
● Your robot must complete its demonstration procedure in a maximum of 5 minutes.
Color Calibration
The color assignments of the rings are 1: Green, 2: Blue, 3: Yellow, 5: Orange, as defined here.
Part of the preparation for this experiment is calibrating your color sensor against the sample
rings in the lab. This is an important step in the design process because it will allow for greater
color detection accuracy than using constant values or the given leJOS methodology.
Calibrating and validating sensor behaviour before testing the robot as a whole will make the
entire process easier! Each color corresponds to a distribution of Red, Green, and Blue values.
For each ring, you need to take several measurements of the RGB values returned by the
sensor. These measurement values will be used to build a statistical model for each ring’s
color.
Quick Tip: This color calibration should be done and tested in both TR0110 and TR0090,
since they have different lightings and could potentially yield different results! The
demos will be conducted in TR0090 (the small lab), so testing color calibration in that
room especially would be ideal.
A particularly simple approach is to model each RGB channel as a Gaussian distribution, i.e.
empirically compute the mean and standard deviation for the Red, Green, and Blue channels for
each ring from the measurement samples. Therefore, each ring can be represented by its mean
RGB values. A simple means of classifying each ring is to compute the Euclidean distance, d ,
between the RGB values of a measured sample, sR
, sG
, and sB
, and a target ring’s mean RGB
values, μR
, μG and μB
, and. A ring is then deemed to be the match when the minimum
Euclidean distance value is met.
d = √(s ) R − μR
2 + (s ) G − μG
2 + (s ) B − μB
2
However, in a real-world scenario, this approach may not work accurately. Given the Gaussian
distribution for each channel, an easy way to distinguish ring colors from each other is to use
their standard deviations, i.e. σ , , and , precomputed from the measurement samples. R σG σB
For example, if a sample distance is greater than 2 or 3 standard deviations from its mean, that
© Instructor and Teaching Assistant generated course materials (e.g., handouts, notes,
summaries, assignments, exam questions, etc.) are protected by law and may not be copied
or distributed in any form or in any medium without explicit permission of the instructor. Note
that infringements of copyright can be subject to follow up by the University under the Code of
Student Conduct and Disciplinary Procedures.
2/10
ECSE 211 Design Principles & Methods 12
th February 2020
ring is probably not the target. This method uses a probabilistic measure by introducing a level
of uncertainty when dealing with the color sensor samples.
Figure 1. Normalized Gaussian distribution: 68% within ± 1σ, 95.4% within ± 2σ.
In computing your mean statistics, i.e., Rmi
, Gmi
, Bmi
, Rs
, Gs
, and Bs
, variations will creep in due to
changes in ambient lighting. One way of mitigating this is to normalize the mean in a particular
channel by the average over all 3 channels, shown for Rs
, Gs
, and Bs below,
and similarly for Rmi
, Gmi
, and Bmi
.
Demonstration (30 points)
The design must satisfy the requirements by completing the demonstration outlined below.
Design presentation (5 points)
Before demoing the design, your group will be asked some questions for approximately 5
minutes. You will present your design (hardware and software) and answer questions to test
your understanding of the lab concepts. Grades will apply to the entire group, although TAs
reserve the right to grade individually if they deem it necessary.
© Instructor and Teaching Assistant generated course materials (e.g., handouts, notes,
summaries, assignments, exam questions, etc.) are protected by law and may not be copied
or distributed in any form or in any medium without explicit permission of the instructor. Note
that infringements of copyright can be subject to follow up by the University under the Code of
Student Conduct and Disciplinary Procedures.
3/10
ECSE 211 Design Principles & Methods 12
th February 2020
You must present your workflow, an overview of the hardware design, and an overview of the
software functionality. Visualizing software with graphics such as flowcharts is valuable.
Color Classification (5 points)
The TA will check whether your robot can correctly classify the Blue, Green, Yellow and Orange
rings. When any object is brought close to your sensor(s), the LCD must display “Object
Detected” on the first line. The next line should read “Blue”, “Green”, “Yellow” and “Orange” for a
target ring. Nothing should be displayed on the LCD if no object is detected. You can decide the
distance between the tested ring and the sensor. This color classification should not take more
than 10 seconds per trial for 5 successive trials using the rings in the lab. False positives and
negatives are considered incorrect. Hence, the following points are awarded:
● 1 point for each time the robot correctly classifies a ring (i.e. “Object Detected” and color).
Field Test (20 points)
The field test will be set up on an 8x8 grid as shown below in Figure 2. There will be at least 2
and at most 5 rings in the navigation path.
Figure 2: Search and Localize demo setup (with Map 4 and 4 rings)
© Instructor and Teaching Assistant generated course materials (e.g., handouts, notes,
summaries, assignments, exam questions, etc.) are protected by law and may not be copied
or distributed in any form or in any medium without explicit permission of the instructor. Note
that infringements of copyright can be subject to follow up by the University under the Code of
Student Conduct and Disciplinary Procedures.
4/10
ECSE 211 Design Principles & Methods 12
th February 2020
For a successful field test, the following steps must be followed:
● Enter the given path as decided by the TA:
o As in Lab 4, we ask that you encode the given maps (in the FAQ section below) so
you can easily select the correct map to use at demo time.
● Place your robot in the starting corner (0, 0).
● Start your robot upon a button push. At this point, the program should already be fully
loaded and all the sensors initialized.
● Your robot must proceed to localize and navigate through the waypoints.
● While navigating, the robot must then detect rings and their colors:
o If a ring is detected, the robot must stop and display the words “Object Detected” on
the top line of the LCD.
o Once the color of the ring has been determined, the robot must display the color on
the second line of the LCD display, BEEP TWICE, and then pause for about 10
seconds (to allow a TA to remove the ring from the path) before continuing its
navigation.
o Once the ring and color have been detected, the ring will be removed from the
robot’s path so as not to disrupt navigation.
● Once the robot reaches its final waypoint, it should BEEP THREE TIMES and stop.
o For the ease of the demo, the robot should display these two parameters once it has
stopped:
▪ On the first line: The number of rings detected throughout the demo
▪ On the second line: The color of the rings detected, in order from first to last.
▪ For example, for Figure 2 it should display:
Number detected: 4
Colors detected: Blue, Yellow, Orange, Green
● All these steps must be completed within 5 minutes.
Hence, the following points are awarded for the field test:
● 5 points are awarded for localization and navigation to the point (1, 1) before navigation
begins.
● 10 points are awarded for correctly identifying all rings along the path and not misidentifying
their colors. Partial marks will be awarded as deemed by the number of rings detected and
by the TA.
● 5 points are awarded for navigating through all the waypoints and for finishing within
approximately half a tile of the last point.
We recommend referring to the FAQ section for details on some specific limitations.
© Instructor and Teaching Assistant generated course materials (e.g., handouts, notes,
summaries, assignments, exam questions, etc.) are protected by law and may not be copied
or distributed in any form or in any medium without explicit permission of the instructor. Note
that infringements of copyright can be subject to follow up by the University under the Code of
Student Conduct and Disciplinary Procedures.
5/10
ECSE 211 Design Principles & Methods 12
th February 2020
Provided materials
Sample code
No sample code is provided for this lab.
Physical material
The four target rings in Blue, Green, Yellow, and Orange. An 8x8 grid floor will be used for this
demonstration.
Implementation instructions
The implementation of this lab is at your discretion, using the design process methods
discussed in class. Since this lab will be done in conjunction with the entire design team, you
have the opportunity to explore different solution approaches. Keep in mind that with a larger
team, it is important to delegate tasks in an effective manner. We highly suggest you meet as a
team and discuss your strengths and how tasks should be fairly distributed.
Report Requirements
The following sections must be included in your report. Answer all questions in the report and
copy them into your report. For more information, refer to the submission instructions. Always
provide justifications and explanations for all your answers.
Important Note about Grading:
The grading rubric of this report has been altered. Section 1 (Design Evaluation) will now count
for 10 of the 50 marks, and Section 5 (Further Improvements) will count for 5 out of the 50
marks.
Section 1: Design Evaluation
For Lab 5, we are asking that this section be longer than the half a page required for
previous labs. Now that you will be working in larger groups, more thought should be put
into the design process, workflow, and teamwork of this lab. This section now has a limit
of about 2 pages.
Workflow
● How did you distribute tasks amongst team members? How did this distribution of work
aid in the design process?
© Instructor and Teaching Assistant generated course materials (e.g., handouts, notes,
summaries, assignments, exam questions, etc.) are protected by law and may not be copied
or distributed in any form or in any medium without explicit permission of the instructor. Note
that infringements of copyright can be subject to follow up by the University under the Code of
Student Conduct and Disciplinary Procedures.
6/10
ECSE 211 Design Principles & Methods 12
th February 2020
● What was the timeline of your work? Did any aspect of the lab take you longer than
expected?
● Did your design process or workflow change drastically with more group members? How
did you deal with this change in environment?
● Include any flowcharts or graphics to help describe your workflow.
Hardware Design
● Give a general overview of the hardware design. Include graphics or any images taken
of your robot here.
● How did you validate this hardware design prior to building it? If you did not, how could
you include this step in the future?
Software Design
● Give a general overview of the software design. Include graphics and diagrams here.
● How did you validate your software design prior to running it on the robot? If you did not,
how could you include this step in the future?
Section 2: Test Data
This section describes what data must be collected to evaluate your design requirements.
Collect the data using the methodology described below and present it in your report.
Model Acquisition (4x10 independent trials)
● Collect a minimum of 10 RGB color values for each ring color (i.e. Blue, Green, Yellow, and
Orange).
● The ring-to-sensor distance should be within the working range of the sensor (which you
need to determine). You should ensure to sample different points on the surface.
Color and Position Identification (4 independent runs)
● Set the robot to follow the navigation path from Map 4 (Figure 2).
● Place all 4 rings in the search region as shown in Figure 2.
● Run the field test 4 times:
o In each run, record (XF
, YF
), the final position of the robot.
o In each run, record the sample RGB values (s , , ) for all the identified rings. R
sG
sB
These are used to evaluate your classifier’s performance.
o In each run, record how many of the rings were detected and correctly
color-identified.
o Hint: you can write your measurements to the LCD or remote console program.
© Instructor and Teaching Assistant generated course materials (e.g., handouts, notes,
summaries, assignments, exam questions, etc.) are protected by law and may not be copied
or distributed in any form or in any medium without explicit permission of the instructor. Note
that infringements of copyright can be subject to follow up by the University under the Code of
Student Conduct and Disciplinary Procedures.
7/10
ECSE 211 Design Principles & Methods 12
th February 2020
Section 3: Test Analysis
Color Calibration
● Compute the RGB mean and standard deviation values for each of the 4 ring colors.
● For each color, plot the corresponding RGB normalized Gaussian distributions and draw
vertical lines at μ , ±1 σ from μ , and ±2 σ from μ .
● Ensure that your plots are labelled and captioned in sufficient detail.
Color and Position Identification
● For each field test run, compute the Euclidean distance, d , of all recorded RGB values. This
should result in 4 distance values for each recorded sample. Then, rank order the distances
for each ring index in ascending order. For each entry in the rank order table, list the
classification that your algorithm returns (i.e. was a Red ring detected as Red?).
● For each run, compute the Euclidean error distance between (XF
, YF
) and the expected
destination waypoint (XD
, YD
).
Section 4: Observations and Conclusions
● Are rank-ordering Euclidean distances a sufficient means of identifying ring colors? Explain
in detail why or why not.
● Is the standard deviation a useful metric for detecting false positives? In other words, if the
ring color determined using the Euclidean distance metric, d , is incorrect, can this false
positive be detected by using μ ±1 σ or μ ±2 σ values instead?
● Under what conditions does the color sensor work best for correctly distinguishing colors?
Section 5: Further Improvements
● Depending on how you implemented your color classifier, can your results be improved by
using one or more of the noise filtering methods discussed in class?
● How could you improve the accuracy of your target detection?
© Instructor and Teaching Assistant generated course materials (e.g., handouts, notes,
summaries, assignments, exam questions, etc.) are protected by law and may not be copied
or distributed in any form or in any medium without explicit permission of the instructor. Note
that infringements of copyright can be subject to follow up by the University under the Code of
Student Conduct and Disciplinary Procedures.
8/10
ECSE 211 Design Principles & Methods 12
th February 2020
Frequently asked questions (FAQ)
1. Which maps will be used for the field test run?
These 8x8 maps will be used, with your robot starting at point (1, 1). They have been
adjusted from Lab 4 to avoid your robots getting caught in the gap in the middle of the
board:
Map 1: (1, 7), (3 ,4), (7, 7), (7, 4), (4, 1)
Map 2: (5, 4), (1, 7), (7, 7), (7, 4), (4, 1)
Map 3: (3, 1), (7, 4), (7, 7), (1, 7), (1, 4)
Map 4: (1, 4), (3, 7), (3, 1), (7, 4), (7, 7)
Figure 3: Navigation Maps
© Instructor and Teaching Assistant generated course materials (e.g., handouts, notes,
summaries, assignments, exam questions, etc.) are protected by law and may not be copied
or distributed in any form or in any medium without explicit permission of the instructor. Note
that infringements of copyright can be subject to follow up by the University under the Code of
Student Conduct and Disciplinary Procedures.
9/10
ECSE 211 Design Principles & Methods 12
th February 2020
2. Can we demo each part separately if our localization or navigation is inaccurate?
No, all parts must be performed in succession for the field test run.
3. Do we have to follow the (X,Y,θ) convention specified in Figure 1?
Yes. Also, note that the bottom-left corner of Figure 2 is specified as (0,0).
4. How many rings will be there in the navigation region?
There will be at least 2 rings and at most 5 rings in the search region. The rings could have
any color.
5. What is the minimum separation distance between two rings in the search region?
2 rings are separated by a distance of at least 1 ring width (i.e. 10 cm).
6. What happens if the field test run takes longer than 5 minutes?
The TA will conclude your demo at the 5-minute mark and will award 0 points for all the
remaining, incomplete parts.
© Instructor and Teaching Assistant generated course materials (e.g., handouts, notes,
summaries, assignments, exam questions, etc.) are protected by law and may not be copied
or distributed in any form or in any medium without explicit permission of the instructor. Note
that infringements of copyright can be subject to follow up by the University under the Code of
Student Conduct and Disciplinary Procedures.
10/10