Artificial Intelligence in Mobile Robots
The Final Challenge  -  2014 Edition


General goal

Write a program for full robot navigation, that integrates planning and reactivity as explained in the lectures, 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. 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)

  1. 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.5 each)

  1. Use both breadth first search and A* search to generate the path, and compare the results.

  2. Use rules for the Avoid and of the GoTo behavior different from the ones given in the lecture, and explain.

  3. 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!

  4. 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.

  5. Update the grid as 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 new openings into account.

  6. 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)

  1. 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.

  2. 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.

  3. 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)

  1. Make your robot do whatever else you want to impress the teacher...! The weight of this option will depend on the difficulty and the novelty of what you have invented.


You must test your program under many different conditions. You should try different combinations of: (1) obstacle layouts, where all obstacles are represented in the map, (2) additional obstacles which are not represented in the map, (3) obstacles of different shapes, colors and materials, (4) different 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 even 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.


Write your report in English or Swedish. Length should be between 5 and 10 pages (not including the appendices). Explain by your own words:
  1. What are the problems to be solved in order to perform this task;
  2. How you have solved these problems;
  3. What optional parts you have done, and how;
  4. How you have tested your system, and show the results;
  5. 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-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, 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 following principles.


The dates for demonstrating the working system, submitting the report, and making the oral discussion are the ones which have been presented in the last lecture.


Home ------------------
Website hosted by AASS
Last updated on Nov 3, 2014.