Artificial Intelligence in Mobile Robots
The Final Challenge - 2018 Edition
- General goal
- Write a program for full robot navigation, that integrates planning
and reactivity as explained in the lectures, and then test it 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. 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
- 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. In this
way, 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.25 each)
- Use both breadth first search and A* search to generate the path,
and compare the results.
- Use rules for the Avoid and for the GoTo behaviors 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 ones suggested in the lecture, and explain:
use your own imagination for that!
- Extend your program so that it can cope with the case when there are
obstacles represented in the map, which are not actually present 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 in point (1) above in order to account for disappeared
obstacles, not only for new obstacles, so that next time that the robot
plans a path it takes the newly discovered passages into account.
- You have all the ingredients that you need to implement 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: give a detailed description of how
they should be implemented using the ingredients in your code. The
description must contain enough details (drawings, interfaces,
pseudo-code) to allow a hypothetical programmer to actually implement
- Advanced options (weight = 0.5 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 the
drawbacks of this solution.
- Develop a fuzzy way to update your grid when you perceive a new
obstacle, or a disappeared obstacle. You can ask me 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 provided to you 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, the novelty and
the success of what you have invented.
- You must test your program under many different conditions.
You should try different combinations of: (a) obstacle layouts; (b)
obstacles of different shapes, colors and materials; (c) different start
and goal points, and (d) additional obstacles that are not represented
in the map.
- You should also test the limit conditions. For instance: (a)
obstacles that split the map into disconnected regions; (b) all new
obstacles, that is, the initial map is totally empty; (c) black
obstacles and mirrors; (d) a goal point which is not reachable. Try to
invent even more "pathological" cases.
- Optional parts must be tested and evaluated as well. For instance,
if you did the main option (point 1 above), you should make sure that
the second time you give the robot a goal point it generates a path
using the updated map.
- 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 the main 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 in the report;
- 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 print the map given to the robot,
and put a sequence of photos that shows the actual movement of the robot
in the real environment.
- Remember that all your Lab reports (1-5) must have been submitted
and approved before you can submit you final report!
- You must demonstrate your working program to the lab assistant. He
will ask you to try many configurations of obstacles, start point and
goal point, of his choice, in order to test the quality of your program.
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
- 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
- Your expected grade (in the Swedish system 1-5) is computed as
follows. You start from a base grade of 3 if you pass the exam as per
the previous point, and then you add the weights of the options that you
have done correctly. For instance, suppose that you do the basic part
(with a good demo and convincing explanations), plus Option 1, plus two
options from the "Simple options" group and one from the "Advanced
options" group. Then you should expect a grade of 3+1.0+0.25+0.25+0.5 =
- For international students 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 compute the total weight of the options that
you have done, and you climb one grade (going towards 'A') for each 0.5
- It is important to understand that the above computation only
provides a baseline for the grade that you can expect. The oral
discussion is aimed at assessing your own level of understanding of the
course subject: your grade will only be confirmed after the oral
discussion. It is possible to be awarded a higher or lower grade, or
even to fail the exam, based on the oral discussion. Also, the grade is
individual: it is possible for two students in the same group to get
different grades, if the discussion makes it clear that they have
achieved a different level of understanding of the subject matter.
- Final note: the software and the report that you produce for this
Final Challenge must be the result of your own work, and you can
not under any circumstance use material taken from other
students, neither from this year's edition of this course nor from past
years. Using other people's ideas, code or text in your program or in
your report will be regarded as plagiarism and may lead to disciplinary
- The dates for demonstrating the working system, submitting the
report, and making the oral discussion are the ones which have been
presented in the final wrap-up lecture.
Website hosted by
Last updated on Oct 8, 2018.