Practice 5_MDP_Presentation

1.

MARKOV DECISION PROCESSES
Worked Example: Campus Service Robot
From states and probabilities → Q-values → Value Iteration → optimal policy
How to use these slides
Follow the calculations step by step. Then solve the Delivery Robot tasks in your
methodological guide using exactly the same procedure.
1

2.

Learning path
One complete example before you solve your own task
Step 1
Step 2
Step 3
Step 4
Understand the problem
Define the MDP
Build transition
probabilities
Understand rewards & γ
Step 5
Step 6
Step 7
Step 8
Calculate Q(s,a)
Choose V(s)
Repeat Value Iteration
Extract the policy
2

3.

Scenario: Campus Service Robot
A robot starts at S and must deliver a document to G. It should
avoid the dangerous area X.
Actions
A
B
C
G +5
D
#
E
X −5
S
F
H
I
UP, DOWN, LEFT, RIGHT
Rewards
Reach G: +5
Reach X: −5
Normal movement: −0.1
Why −0.1 per move?
It encourages the robot to reach the goal without wandering forever.
3

4.

Step 1 – Define the MDP
States S
Actions A
A, B, C, D, E, S, F, H, I, G, X
UP, DOWN, LEFT, RIGHT
Start state
Terminal states
S
G and X
Transition model
Reward function
T(s,a,s′)
R(s,a,s′)
Remember
An MDP is the description of the decision problem. We have not solved it yet.
4

5.

Step 2 – Actions are uncertain
Choosing UP does not always mean moving UP
0.8
A
D
S
B
#
F
C
E
H
G +5
X −5
I
move in the intended direction
Rule at a wall / edge
0.1
If a movement would leave the grid
or enter #, the robot stays in the
same state.
slip to the left side
0.1
slip to the right side
0.8 + 0.1 + 0.1 = 1.0
All possible outcomes of one action must
have total probability 1.
5

6.

Worked transition: from H choose UP
A
B
C
G +5
D
#
E
X −5
S
F
H
I
Intended move
Left slip
Right slip
UP → E
LEFT → F
RIGHT → I
probability 0.8
probability 0.1
probability 0.1
Current
Action
Next
Probability
H
UP
E
0.8
H
UP
F
0.1
H
UP
I
0.1
Check
0.8 + 0.1 + 0.1 = 1.0
6

7.

What if the robot hits a wall?
A
B
C
G +5
D
#
E
X −5
S
F
H
I
Example
Robot is in F and chooses UP.
• 0.8: UP points to # → stay in F
• 0.1: LEFT → S
• 0.1: RIGHT → H
T(F, UP, F) = 0.8
T(F, UP, S) = 0.1
T(F, UP, H) = 0.1
Key point
Blocked movement does not disappear; its probability becomes “stay here”.
7

8.

Step 3 – Discount factor γ
How much does the robot care about future rewards?
γ = 0.2
U = r₀ + γr₁ + γ²r₂ + …
For example: robot moves