.. role:: python(code) :language: python .. `MDP example game ` `MDP example magic tram ` `MDP example swamp isle ` .. index:: Markov Decision Process; game Markov Decision Process; magic tram Markov Decision Process; swamp isle Markov Decision Process; value iteration .. _`sec:mdp_examples`: Examples -------- Game ^^^^ .. admonition:: Exercise (intermediate) 1. Implement and test the game problem from the :python:`MDPFromMapping`. 2. Implement and test the value iteration algorithm. The output of this algorithm is a policy mapping and a value mapping (the optimal ones). .. _`ex:mdp_game_implementation`: .. collapse:: Hint 2. To keep things more readable, a function :python:`qualities_from_state` is also implemented. .. literalinclude:: ../../../../src/ai/reinforcement/mdp_iteration.py :pyobject: value_iteration_empty :name: value_iteration_empty :linenos: :caption: src .. literalinclude:: ../../../../src/ai/reinforcement/mdp_iteration.py :pyobject: qualities_from_state_empty :name: qualities_from_state_empty :linenos: :caption: src .. collapse:: Correction 1. These tests are almost trivial. They are there to force you to clearly understand the defined types. .. code-block:: python :linenos: mdp_mapping_game: MDPMapping = { "in": { "stay": {"in": (2.0 / 3.0, 4.0), "out": (1.0 / 3.0, 5.0)}, "quit": {"out": (1.0, 10.0)}, }, "out": {}, } .. literalinclude:: ../../../../tests/ai/reinforcement/conftest.py :pyobject: game_mdp :name: game_mdp :linenos: :caption: tests .. literalinclude:: ../../../../tests/ai/reinforcement/test_mdp_example_game.py :name: test_mdp_example_game :linenos: :caption: tests 2. .. literalinclude:: ../../../../src/ai/reinforcement/mdp_iteration.py :pyobject: value_iteration :name: value_iteration :linenos: :caption: src .. literalinclude:: ../../../../src/ai/reinforcement/mdp_iteration.py :pyobject: qualities_from_state :name: qualities_from_state :linenos: :caption: src .. literalinclude:: ../../../../tests/ai/reinforcement/test_mdp_iteration_game.py :name: test_mdp_game :linenos: :caption: tests Magic tramway ^^^^^^^^^^^^^ Extending the magic tram problem from the state problem section, a failure probability is introduced when taking the magic tram. Taking the tram has still a higher cost than walking, still can make you move (state x tram_factor) but now with a fail probability to leave you at your current state. .. figure:: magic_tram_art_fail.png :width: 300 :alt: magic tram fail Magic tram fail .. admonition:: Exercise (intermediate) 1. Implement a :python:`MDPMagicTram` problem from the :python:`MDPProblem` and test it. 2. Interpret the value iteration algorithm for different values of the failure probability. .. _`ex:mdp_tram_implementation`: .. collapse:: Correction 1. .. literalinclude:: ../../../../src/ai/reinforcement/mdp_example_tram.py :pyobject: MDPMagicTram :name: MDPMagicTram :linenos: :caption: src .. literalinclude:: ../../../../tests/ai/reinforcement/test_mdp_example_tram.py :name: test_mdp_example_tram :linenos: :caption: tests 2. For the case of 2 to 13: + For a failure probability of 0, the problem is identical to the :ref:`state problem ` already solved during a previous session. The value of state 2 is supposed to be identical to the total cost of the state problem. + For a failure probability of 1, it is obvious that one should not take the tram. + For a failure probability of 0.2, the value of state 2 is logically larger than a failure probability of 0. However, it is still worth it to take the tram at state 3 and 6. + For a failure probability of 0.4, the value of state 2 is even higher than a failure probability of 0.2. However, now it is not worth it to take the tram at state 3, the risk of failure and the associated cost is to large regarding the length of the jump. The tram at state 6 is still worth it. failure probability 0.0 +---------+----------+---------+ | state | action | value | +=========+==========+=========+ | 2 | walk | -6 | +---------+----------+---------+ | 3 | tram | -5 | +---------+----------+---------+ | 4 | walk | -5 | +---------+----------+---------+ | 5 | walk | -4 | +---------+----------+---------+ | 6 | tram | -3 | +---------+----------+---------+ | 7 | walk | -6 | +---------+----------+---------+ | 8 | walk | -5 | +---------+----------+---------+ | 9 | walk | -4 | +---------+----------+---------+ | 10 | walk | -3 | +---------+----------+---------+ | 11 | walk | -2 | +---------+----------+---------+ | 12 | walk | -1 | +---------+----------+---------+ | 13 | | 0 | +---------+----------+---------+ failure probability 1.0 +---------+----------+---------+ | state | action | value | +=========+==========+=========+ | 2 | walk | -11 | +---------+----------+---------+ | 3 | walk | -10 | +---------+----------+---------+ | 4 | walk | -9 | +---------+----------+---------+ | 5 | walk | -8 | +---------+----------+---------+ | 6 | walk | -7 | +---------+----------+---------+ | 7 | walk | -6 | +---------+----------+---------+ | 8 | walk | -5 | +---------+----------+---------+ | 9 | walk | -4 | +---------+----------+---------+ | 10 | walk | -3 | +---------+----------+---------+ | 11 | walk | -2 | +---------+----------+---------+ | 12 | walk | -1 | +---------+----------+---------+ | 13 | | 0 | +---------+----------+---------+ failure probability 0.2 +---------+----------+---------+ | state | action | value | +=========+==========+=========+ | 2 | walk | -7 | +---------+----------+---------+ | 3 | tram | -6 | +---------+----------+---------+ | 4 | walk | -5.5 | +---------+----------+---------+ | 5 | walk | -4.5 | +---------+----------+---------+ | 6 | tram | -3.5 | +---------+----------+---------+ | 7 | walk | -6 | +---------+----------+---------+ | 8 | walk | -5 | +---------+----------+---------+ | 9 | walk | -4 | +---------+----------+---------+ | 10 | walk | -3 | +---------+----------+---------+ | 11 | walk | -2 | +---------+----------+---------+ | 12 | walk | -1 | +---------+----------+---------+ | 13 | | 0 | +---------+----------+---------+ failure probability 0.4 +---------+----------+---------+ | state | action | value | +=========+==========+=========+ | 2 | walk | -8.3 | +---------+----------+---------+ | 3 | walk | -7.3 | +---------+----------+---------+ | 4 | walk | -6.3 | +---------+----------+---------+ | 5 | walk | -5.3 | +---------+----------+---------+ | 6 | tram | -4.3 | +---------+----------+---------+ | 7 | walk | -6 | +---------+----------+---------+ | 8 | walk | -5 | +---------+----------+---------+ | 9 | walk | -4 | +---------+----------+---------+ | 10 | walk | -3 | +---------+----------+---------+ | 11 | walk | -2 | +---------+----------+---------+ | 12 | walk | -1 | +---------+----------+---------+ | 13 | | 0 | +---------+----------+---------+ Swamp isle ^^^^^^^^^^ The swamp isle problem is similar as the one presented in the state model section. The isle is rectangular, there are some swamps. The goal is to reach the end point limiting the cost. However, walking on dry land has a cost and walking in swamps has an even higher cost. One can walk either vertically or horizontally (not diagonally). The novelty is that the problem is now a MDP because every action can lead to an equiprobable orientation failure in any of the other potential directions: the chance of no failure is 1-failure probability. .. admonition:: Exercise (intermediate) 1. Implement a :python:`MDPSwampIsle` problem from the :python:`MDPProblem` and test it. 2. Interpret the value iteration algorithm for different values of the failure probability. .. _`ex:mdp_swamp_implementation`: .. collapse:: Correction 1. .. literalinclude:: ../../../../src/ai/reinforcement/mdp_example_swamp.py :pyobject: MDPSwampIsle :name: MDPSwampIsle :linenos: :caption: src .. literalinclude:: ../../../../tests/ai/reinforcement/test_mdp_example_swamp.py :name: test_mdp_example_swamp :linenos: :caption: tests 2. + For a failure probability of 0, the problem is identical to the former state search problem. The difference here is that the optimal policy and value is obtained for every state, not only for a starting state. The X symbols denote the swamps. The letter between brackets represent the optimal policy. The value of 25 is from (0,1) is the same as the one obtained in the state model exercise. + For a failure probability of 1, you are **certain** of taking an other direction that the one you ask for. As a result, you can see that the optimal policy is going the opposite of the correct direction in order to hope to fail on the right direction. The cost is higher because when you have several failing direction you are not sure to fail on the correct one, and you have to pay the cost of the uncertainty. + The failure probability of 0.2 gives the same policy as the failure probability of 0, just at a higher cost. failure probability 0.0 +-----------------+----------------------+----------------------+-----------------+ | {'E', 'S'} | {'E', 'W', 'S'} | X | X | | [S] -24.0 | [W] -25.0 | {'E', 'W', 'S'} | {'W', 'S'} | | | | [S] -41.0 | [S] -21.0 | +-----------------+----------------------+----------------------+-----------------+ | {'E', 'N', 'S'} | X | X | {'W', 'N', 'S'} | | [S] -23.0 | {'E', 'W', 'N', 'S'} | {'E', 'W', 'N', 'S'} | [S] -1.0 | | | [S] -41.0 | [E] -21.0 | | +-----------------+----------------------+----------------------+-----------------+ | {'E', 'N'} | {'E', 'W', 'N'} | X | END | | [E] -22.0 | [E] -21.0 | {'E', 'W', 'N'} | | | | | [E] -20.0 | | +-----------------+----------------------+----------------------+-----------------+ failure probability 1.0 +-----------------+----------------------+----------------------+-----------------+ | {'E', 'S'} | {'E', 'W', 'S'} | X | X | | [E] -51.0 | [S] -62.7 | {'E', 'W', 'S'} | {'W', 'S'} | | | | [S] -72.3 | [W] -42.0 | +-----------------+----------------------+----------------------+-----------------+ | {'E', 'N', 'S'} | X | X | {'W', 'N', 'S'} | | [E] -50.0 | {'E', 'W', 'N', 'S'} | {'E', 'W', 'N', 'S'} | [W] -22.0 | | | [E] -72.9 | [W] -65.8 | | +-----------------+----------------------+----------------------+-----------------+ | {'E', 'N'} | {'E', 'W', 'N'} | X | END | | [N] -47.0 | [N] -46.0 | {'E', 'W', 'N'} | | | | | [N] -43.0 | | +-----------------+----------------------+----------------------+-----------------+ failure probability 0.2 +-----------------+----------------------+----------------------+-----------------+ | {'E', 'S'} | {'E', 'W', 'S'} | X | X | | [S] -38.8 | [W] -42.9 | {'E', 'W', 'S'} | {'W', 'S'} | | | | [S] -56.7 | [S] -38.0 | +-----------------+----------------------+----------------------+-----------------+ | {'E', 'N', 'S'} | X | X | {'W', 'N', 'S'} | | [S] -36.5 | {'E', 'W', 'N', 'S'} | {'E', 'W', 'N', 'S'} | [S] -8.4 | | | [S] -52.4 | [E] -35.8 | | +-----------------+----------------------+----------------------+-----------------+ | {'E', 'N'} | {'E', 'W', 'N'} | X | END | | [E] -33.0 | [E] -30.9 | {'E', 'W', 'N'} | | | | | [E] -26.7 | | +-----------------+----------------------+----------------------+-----------------+ .. .. raw:: html :file: swamp_isle.html