This task is based on task 15.9 in the course book and on the explanations for matrix based forward filtering operations according to section 15.3.1 of the book, but you must adhere to the detailed instructions given below.

If you do not have access to this particular edition (Artificial Intelligence: A Modern Approach, 3/e, by Stuart Russell and Peter Norvig, ISBN-10: 0132071487) and have difficulties in figuring out what to do without the book, please contact me (Elin) at Elin_Anna.Topp at cs.lth.se before attempting to solve the task!

In short

You will

• implement robot localisation/tracking based on forward filtering with a Hidden Markov Model,
• read a scientificarticle about Monte-Carlo Localisation that was published in the AAAI Conference on AI 1999 and was honoured with the AAAI Classic AI Paper Award in 2017,
• write a report in which you discuss your implementation and results as well as summarise the article and discuss its relation to the implementation you worked with.

Please READ the complete detailed instructions, see below, BEFORE working on the task.

Make also use of the office hours of the course assistants and myself, if you have questions or get stuck with the implementation!

In detail

Implementation:

You'll find a zip-file containing a) the detailed instructions, b) another zip-file with a Java-based tool for visualisation of your transition model, your sensor model and your estimation, and c) some sort of user's guide for the Java tool HERE!

Feel free to use other programming languages (C++, Matlab, Python are ok as well) or tools, but if you choose Java, please make use of the visualisation - it presumably helps us a lot to understand your implementation!

Also, if you use another language, do that only if you are already familiar with it!

Reading:

Read the article "Monte Carlo Localization: Efficient Position Estimation for Mobile Robots" by Dieter Fox et al., which you can find (for example) HERE. It was published in the proceedings of the 16th AAAI Conference on Artificial Intelligence (AAAI-99) in 1999, and received the AAAI Classic AI Paper Award in 2017. Examples relating to this paper will be part of the lecture on Probabilistic Robotics. 

Report:

Write a brief (max 3 filled A4-pages) report that adheres to the following structure and encloses the listed points:

• Summary of the implementation task in your own words
• Description of your implementation, mentioning how you encoded the states, transition and observation model. Do NOT list code!
• Discussion of your results, answering the question: "How accurately can you track the robot?". To do this, compare your results to pure guessing and to using the sensor readings only in terms of error rates and margin. 
• Summary of the article you read.
• Discussion of the relation between your implementation and the work described in the article, answering the question: "Is the HMM approach as implemented suitable for solving the problem of robot localisation?". Give clear evidence / motivation for your statement.

Passing Criteria:

In general, this assignment is not a coding competition, it is meant to give you the opportunity to evaluate a method in a specific scenario and put it into context. To pass, the following criteria need to be fulfilled:

• The implementation must be accessible, executable and produce reasonable results according to the instructions you give in the submission e-mail.
• If the Java-viewer is used, the visualisation of transition and sensor models for a 4x4-grid should look like what is given as example in the instructions, and it must be clear that the visualised models correspond to those used for calculations. 
• The report must contain the above listed items.
• The description of your implementation must actually match your implementation.
• The summary of the article must clearly be written by you in your own words, so that it becomes clear that you actually have read and understood the overall idea and achievements.
• The two core questions as given in the report instructions must be answered with motivations for your answers. "Yes, the approach is suitable." is not sufficient, neither would be "Probably not, as we only get it right x percent of the time." (this number is stated in the instructions, thus information-free wrt your implementation).
• The submission reaches us before the deadline.

The following points must NOT be fulfilled:

• It is obvious that you have implemented something other than forward filtering for an HMM (do not try to implement state-of-the-art robot localisation to impress us, impress us by showing in the report that you know your way around in the material but stick to the task given to you).
• It is obvious that you have used an existing implementation "off-the-shelf" and not really managed to adapt it to the scenario.
• The implementation is not available in the student system, but through Github or similar repositories. 

Important remark: Remember that the time frame allotted to this assignment is approximately three, maybe up to five, days of your work, so please do not overdo it: a decent program and report will suffice to get a pass (see criteria above). However, in particular if you fail to submit a correctly running program, your report will most likely not be reviewed, thus make sure to get that working well before the deadline. 

Note

You are expected to work individually, however, I consider it natural and beneficial to discuss and work together on programming tasks among fellow students. In case you do that, please indicate this clearly in your report (who you consulted with and to what level), which must be written individually. 

Also, if you need advice beyond what fellow students can help you with, contact a course assistant or me (Elin).

If you decide to base your solution on someone else's code (e.g., some library found on the web), please mention it both in the code and in your report: it is a matter of academic honesty. Lund University is committed to fighting every case of dishonesty or plagiarism.

The report should be sent to edap01 at cs.lth.se as an attachment to a mail message with the following subject line: Assignment X by username, where X is the number of the assignment this year, and username is your user name in the student computer system, like dat14eto or el2345to. In the message body, specify the link to the folder on the student computer system where your implementation can be found and executed, as well as instructions on how to run it. Make sure the folder is searchable and the code is executable.