Write a program for full robot navigation, that integrates planning
and reactivity as explained in the lecture, and test is extensively.
Detailed description
The program should be given a map of the enviroment, and then accept
goal points from the user and drive the robot to that point while
avoiding all the obstacles on the way. You need to use the map to plan
a collision-free path from the starting position to the end position,
and then follow this path. You are expected to use fuzzy rule-based
control to follow the path.
The program should be prepared to cope with the possibility that
there are obstacles in the environment which were not represented in the
map. Some obstacle might even be slowly moving around. The robot
should detect these new obstacles and reactively avoid them, while still
trying to reach the final goal point. An extreme case of this is when
the initial map is empty, but there are obstacles in the environment.
You are expected to use fuzzy rule-based control for obstacle avoidance.
Optional parts
Main option (weight = 1.0)
When the robot encounters a new obstacle, it should update the grid
and generate a new path to the goal using the updated grid. Then, the
next time the robot is given a goal point, it will already know about
that new obstacle and plan its path accordingly.
Simple options (weight = 0.5 each)
Use both breadth first search and A* search to generate the path,
and compare the results.
Use rules for the Avoid and of the GoTo behavior different from the
ones given in the lecture, and explain.
Try to combine the path following behavior with obstacle avoidance
in a different way than the one suggested in the lecture, and explain:
use your own imagination for that!
Make sure that your program is also prepared to the possibility that
there are obstacles reported in the map which are not actually in the
environment. The robot should detect that there might be an opportunity
for a shortcut there, and take it if possible. An extreme case of this
is when there are obstacles in the initial map, but in reality the
environment is empty.
Update the grid as above in order to account for disappeared
obstacles, not only for new obstacles.
You have all the ingredients that you need to implement either a
"sense-plan-act" architecture, a "reactive" architecture, or a "hybrid"
architecture. Explain clearly, in your report, what functionalities
(and parts of your code) are needed to realize each one of these
architectures, how they should be connected, and why. You do not need
to implement these architectures: just give a detailed description of
how they should be implemented using the ingredients that you already
have in your code. The description should contain enough details
(drawings, interfaces, pseudo-code) to allow a hypothetical programmer
to actually implement your idea.
Advanced options (weight = 1.0 each)
Replace the "path generation + path following" blocks of the overall
solution by a "distance map generation + gradient following". Explain
clearly in the report how you did it, and what are the advantages or
drawbacks of this solution.
Develop a fuzzy way to update your grid when you perceive a new
obstacle, or a disappeared obstacle. You can come to me to ask for
papers to read if you want to try this. Clearly explain in your report
the methods and formulas that you use, and justify them.
Implement the fuzzy rule-based controller using your own
implementation, not the one in the library. Clearly explain in your
report your implementation, and justify it.
The open option (weight = up to 1.0)
Make your robot do whatever else you want to impress the teacher...!
The weight of this option will depend on the difficulty and novelty of
what you have invented.
Testing
You must test your program under many different conditions. You
should try different configurations of: (1) obstacles in the map, (2)
new obstacles which are not in the map, (3) obstacles of different
shapes, colors and materials, (4) start and goal points.
You should also test the limit conditions. For instance: (1)
obstacles that split the map into disconnected regions, (2) all the
obstacles are new, that is, the initial map is totally empty, (3) black
obstacles and mirrors, (4) a goal point which is not reachable. Try to
invent more "pathological" cases.
If you did any optional parts, they should be tested and evaluated
as well. For instance, if you did the "update grid" options above, you
should make sure that the second time you give the robot a goal point it
generates a path using the updated map.
Report
Write your report in English or Swedish. Length should be between 5
and 10 pages (not including the appendices). Explain by your own words:
What are the problems to be solved in order to perform this task;
How you have solved these problems;
What optional parts you have done, and how;
How you have tested your system, and show the results;
Discuss the quality of your system, based on the above results,
comment on the limitations, and say how these could be overcome.
Make sure that you cleary discuss all the above five points. You may
want to use separate sections for them, but this is not mandatory.
Add to the report an appendix with your full commented code.
Only put your own code, not the libraries!
Make sure to include data and pictures that show the performance of
your system. For instance, you can put pictures that show the map given
to the robot, and sequences of photos that show the actual trajectory
made by the robot in the real environment. If you have many of these
pictures, they may be included as additional appendices.
Remember that all your Lab reports (1-6) must have been submitted
and approved before you can submit you final report!
Evaluation
You must demonstrate your working program to the lab assistant. He
will ask you to try many configurations of obstacles, start point, goal
point, of his choice, in order to test the quality of your robot. Once
he is satisfied with your demo, you must submit your report to the
teacher and discuss it with him. Your final score will be based on the
following principles.
You must successfully do the parts described in the "detailed
description" section, in the "Testing" section, and in the "Report"
section in order to pass the exam. In particular, your demonstration
must have worked fine, and you must show, in your report and in the oral
discussion, that you have a good understanding of what you have done.
Your expected grade is computed as follows (using the ECTS grading
system -- A,B,C,...). You start from a base grade of E if you pass the
exam as per the previous point. Then, you climb one "letter" for each
accumulated unit in the "weights" for the options that you have done.
For instance, suppose that you do the basic part (with a good demo and
convincing explanations), you do Option 1, and you also do two options
from the "Simple options" group and one from the "Advanced options"
group. Then you should expect a grade of E+1.0+0.5+0.5+1.0 = B.
It is important to notice that the above computation only provides a
baseline for the grade that you may expect. The oral discussion is
aimed at assessing your level of understanding of the course subject:
your grade will only be confirmed after the oral discussion. It is
possible in principle to be awarded a higher grade, or even to fail the
exam, because of the oral discussion.
Final note: the software and the report that you produce for this
Final Challenge is the result of your individual work, and you can
not under any circumstance use ideas or code from other students,
neither from this year's edition of this course nor from past years.
Using other people's ideas and code in your program or report will be
regarded as plagiarism and may lead to disciplinary actions.
