COMP4620/8620 – Advanced Topics in AI
Decision-making under Uncertainty in Robotics
Semester-2 2023 – Assignment 2
Due date: Wednesday, 25 October 2023 23:59 Canberra time
Convenor & Lecturer: Hanna Kurniawati
Notes:
1. This is an individual assignment.
2. Submission Instruction:
(a) You must submit a report and codes containing the answers to the questions in this assign-
ment.
(b) For programming questions, you must:
i. Write your program(s) in Python.
ii. Submit your programs and test cases.
(c) All your report, programs, and testcases should be compressed into a single .zip file. You
should name this .zip file A2 [courseCode] [UID].zip, where [courseCode] should be re-
placed by either comp4620 or comp8620, depending on the class you enrolled in, and
[UID] should be replaced by your ANU ID. The .zip file should be submitted through
wattle before the due date.
Part A [1pt]: ID.
Please put your name and ANU ID on the first page of your report.
Part B [10pts]: On Concepts.
1. [5pts] Mr M has been tasked to develop a program to compute the solution of a finite horizon
MDP problem. After a couple of weeks, Mr M demonstrates a prototype of his program. This
program outputs a single mapping from states to actions as the solution to the MDP problem.
You have been asked to help judge the correctness of Mr M program. Given the above infor-
mation alone, would you be able to decide whether Mr M program is correct or not? Please
explain your answer.
2. [5pts] We know that POMDP can be viewed as MDP in the belief space. Does this mean solv-
ing a POMDP is as easy as solving an MDP? Please explain your answer.
Part C [39pts]: Model Building.
A vacuum cleaner robot is tasked to clean a grid-world of size m × n. The floor materials of each cell
may be one of the following three types: Vynil, thin carpet, and thick carpet. The effectiveness of the
robot vacuum depends on the floor type of the cell. Specifically, if a cell’s floor is of type Vynil, the
probability that each vacuum action cleans the cell with probability 95%. If the cell’s floor is of type
thin carpet, each vacuum action cleans the cell with probability 85%. Last but not least, each vacuum
action cleans the cell whose floor is of type thick carpet only with probability 75%. In a single move
step, the robot’s movement is limited to one cell to its left, right, up, or down. The goal is to compute
the strategy for the robot vacuum that would enable the robot to clean the entire grid-world with as
little cost as possible under these different scenarios:
Page 1 of 2 – Advanced Topics in AI – (COMP4620/8620)
Scenario-1. The robot’s motion is perfect and information about the types of flooring in each cell is
known a priori.
Scenario-2. Information about the types of flooring in each cell is known a priori. However, the
robot motion is not perfect: It only moves to its intended destination 85% of the time, with 5%
of the time the robot ended up at the left of its intended destination, 5% of the time the robot
ended up at the right of its intended destination, and 5% of the time the robot ended up not
moving. If the intended destination, or the left/right of the intended destination are obstacles
or outside of the operating environment, then the probability mass will be added to the robot
staying put.
Scenario-3. The robot’s motion is perfect but information about the types of flooring in each cell is
not known a priori and needs to be assessed using the robot’s touch sensor. This touch sensor is
correct only 80% of the time, and wrongly identify the floor type to be one of the wrong floor
types uniformly (10% for each wrong floor type).
For each of the above problem scenario, please:
• [15pts] Identify if it’s more suitable to use the MDP or the POMDP frameworks. Please provide
an explanation of why MDP/POMDP is the suitable framework. This question is worth 3 points
for scenario-1 and 6 points for scenario-2 and scenario-3.
• [24pts] Define the MDP/POMDP model (depending on the identification you made in the point
above). This question is worth 8 points for each scenario.
Part D [25pts]: Basic MDP Solving.
1. [10pts] Please solve Part C – Scenario-1 using the synchronous value iteration method for solv-
ing MDP off-line. To this end, please implement the method using Python. For this question,
you will receive a full mark if your implementation converges to the optimal solution for m = 1
and n = 4 in under 10 minutes.
2. [15pts] Please empirically analyse the above implementation on the problems you have defined
in Part C – Scenario-1 to reveal the scalability issues of the synchronous value iteration method.
You should present the empirical results and a discussion of your findings.
Part E [25pts]: Show us your creativity!
Please improve the rudimentary solver in Part D, so as to either be able to solve larger problems of
Part C Scenario-1 or able to solve Scenario-3. We prefer you explore online-solver. But, we will leave
this open for you to decide.
1. [5pts] Please describe your improved solver and why you think this method will be more scal-
able than the method in Part D.
2. [20pts] Please implement your proposed improvements and empirically analyse your proposed
solver on the appropriate problems you have defined in Part C to reveal the improvements you
have made. You should submit your code and test cases, and present the empirical results and a
discussion of your findings in the report.
oOo That’s all folks oOo
Page 2 of 2 – Advanced Topics in AI – (COMP4620/8620)