program辅导 、讲解 Python设计编程
2 Programming [50 Points]
For this question, you will implement the value iteration algorithm for MDPs. Modify mdp.py,
which takes an environment file as an argument and prints out the calculated utilities of each
state. Use the value iteration algorithm to calculate the utilities.
Input
The file mdp.py will take as input an environment file. For example, you can run your program
using the following command, where gridtest.txt is the environment file: python mdp.py
gridtest.txt The environment file will specify the MDP. The available actions in any environment are moving north, south, east, and west (there is no possibility of being stationary). Any
action can be taken from any non-terminal state, but hitting a wall causes you to remain in
the same place. Moving into a terminal state ends a run. The first line of the environment file
specifies the discount factor (gamma). The second line specifies the “cost of living” (negative
reward), for the transition to a non-terminal state. The third line specifies the transition
probabilities in the following order:
1. Going in the intended direction
2. Going 90 degrees clockwise from what you intended
3. Going the opposite direction from what you intended
4. Going 90 degrees counterclockwise from what you intended
The rest of the file contains the grid (with no trailing newlines). An asterisk ‘*’ represents a
state, ‘x’ represents a wall, and numbers represent the values of terminal states. Columns are
separated by spaces, and rows are separated by newlines. All grids are rectangular. Here is an
example environment file:
1
-0.04
0.8 0.1 0 0.1
* * * 1
* x * -1
* * * *
In this example file, the discount factor is 1, and the “cost of living” for transition into nonterminal states is -0.04. There is an 80% chance of going in the direction you intended to, a 10%
chance of going 90 degrees clockwise from what you intended, a 0% chance of going in the
opposite direction you intended, and a 10% chance of going 90 degrees counter-clockwise of
the direction you intended. The environment is a grid with 3 rows and 4 columns.
Output
Your program should print out a grid in the same format as the input grid, but with the stars
replaced by the utility values you calculated. Utilities should be accurate to three decimal
places. The output from the above file should be:
0.812 0.868 0.918 1
0.762 x 0.660 -1
0.705 0.655 0.611 0.388
7
Miscellaneous
We will run your code on several test files to ensure accuracy. Important note: Do not add
any extra print statements when submitting to Gradescope. This will cause you to
fail the tests. You should only be printing the resulting grid once (as we already have
for you in the code). You will need to submit your code implementation (mdp.py) to
Gradescope Homework 4.
8