This page is located in archive.

T4c-vi - Value-iteration policy in pursuit-evasion

The main task is to implement a Value-iteration policy for the robotics pursuit-evasion game.

Due date January 13, 2024, 23:59 PST
Deadline January 13, 2024, 23:59 PST
Points 7
Label in BRUTE t4c-vi
Files to submit Player.py
Do not submit the generated policy file.
Resources B4M36UIR_t4ac_resource_pack


The number of players and robots is fixed for this task. There will be two players in the game. One player with a single evading robot and one player with two pursuers. For automatic evaluation to work, use reward -1 for evader and 1 for pursuer when caught and (0,0) when escaped. Save the values from the pursuers point of view and use gamma=0.95
When constructing the matrix Q, according to the equation in the code, you should only add the next state value times gamma, when there is a transition to the next state. When the game ends by the action, there is no such transition and you should only put the reward into the matrix (therefore the resulting values for pursuer should be between 0 and 1).

In file player/Player.py in function value_iteration_policy implement the Value-iteration policy decision making for pursuit-evasion game.

The value_iteration_policy function has the following prescription:

def value_iteration_policy(self, gridmap, evaders, pursuers):
        Method to calculate the value-iteration policy action
        gridmap: GridMap
            Map of the environment
        evaders: list((int,int))
            list of coordinates of evaders in the game (except the player's robots, if he is evader)
        pursuers: list((int,int))
            list of coordinates of pursuers in the game (except the player's robots, if he is pursuer)

The purpose of the function is to generate a value iteration policy for both players and save the resulting policies in a file. Example policy creation and save is in the resource pack of the task. The file is created using the pickle library and has a filename ./policies/name_of_the_game.policy. In the file should be a tuple (values, evader_policy, pursuer_policy, i2c, c2i). i2c is a mapping from integer indexes to passable coordinates in the map, and c2i is mapping from coordinates to indexes. Both are in the form of a dictionary. Policies are saved as a dictionary with state of the game as key in the format of (c2i[evader_position], c2i[pursuer_position], c2i[pursuer_position]), and for each state, we have saved a tuple of two tuples or arrays, where the first contains indexes of possible next actions and the second one contains probabilities of the corresponding actions. Example for evader: key=(1,0,6), value=([6,0,2],[0,0,1]) Example for pursuer: key=(1,0,6), value=([(5, 5), (5, 1), (1, 5), (1, 1)],[0,0,0,1]) Let n be the number of passable coordinates, then values is an array of size (n,n,n) with value for each game state from the perspective of the pursuer. This corresponds to v(s) in the pseudocode.

In the same file in function compute_nash, implement the linear program to compute a matrix game's Nash equilibrium.

The compute_nash function has the following prescription:

def compute_nash(matrix):
        Method to calculate the value-iteration policy action
        matrix: n times m array of floats
            Game utility matrix
            computed value of the game
            probability of player 1 playing each action in nash equilibrium

Purpose of the function is to compute nash equilibrium of any matrix game. The function should compute strategy for the row player assuming he is the maximizing player. If you want to use it to compute the strategy of the other player all you have to do is negate and transpose the matrix.

During the gameplay, our player will load the policy produced by your player and will play according to it.

The game ends after a predefined number of steps or when all the evaders are captured.

Computing the policy

Adaptation of algorithm from MDPs. Iteratively updates values for each state and converges to optimum if each state is updated infinitely often. Let states S be all passable coordinates and A be a function of a state returning all pairs of actions applicable in the given state. r is a function of state and pair of actions that return immediate payoff, and T is transition function that returns next state given state and actions. The algorithm operates as follows

\begin{align} &\forall s \in S \quad \text{initialize} \quad v(s) = 0 \quad \text{and until v converges} \\ &\forall s \in S \\ & \quad \quad \forall (a_1,a_2) \in A(s) \\ & \quad \quad \quad \quad Q(a_1,a_2) = r(s,a_1,a_2) + \gamma v(T(s,a_1,a_2)) \\ & \quad \quad v(s) = \max_x \min_y xQy \end{align}

where Q is the accumulated matrix, corresponding to a matrix game between players. 'x' and 'y' are strategies for player 1 and player 2 in the matrix game Q (so they are all possible moves for both players). After the change in values is under a threshold (evaluation uses 0.0001, so anything lower should be fine) in each state, to obtain the optimal strategy, perform one more iteration, and when computing $v(s) = \max_x \min_y xQy$ instead from the same computation get the x and y. $x = \text{arg} \max_x \min_y xQy$. In the small example that I show here, the optimal strategy in the first step is to pick both free spaces with the same probability.

Vi example

Computing $\max_x \min_y xQy$ can be done by following a linear program.

\begin{align} &\text{maximize} \quad U \\ &\text{subject to} \sum_{a_1 \in A_1}x(a_1)u_1(a_1,a_2) \geq U &\forall a_2 \in A_2 \\ & \quad \quad \quad \quad \sum_{a_1 \in A_1}x(a_1) = 1 \\ & \quad \quad \quad \quad x(a_1) \geq 0 &\forall a_1 \in A_1 \\ \end{align}

You will need LP solver for this task. Upload system should work with Gurobi and CPLEX (extensively tested with Gurobi, should probably work with CPLEX). Great guide for gurobi is available on Combinatorial optimization course pages - https://cw.fel.cvut.cz/b192/_media/courses/ko/01_gurobi.pdf

Make sure to not print information about each matrix solve as BRUTE might not finish when the standard output gets too large. In gurobi it is done by model.setParam(“OutputFlag”, 0)


Automatic evaluation is prepared for this task. You will upload your player, it will generate the policy, and then the game will be played by our player using your policy. Your submission will be tested as both roles against the greedy policy and as a pursuer against our value_iteration. Nash equilibrium computation will also be tested for correctness, and the evaluation will check if your values from the value iteration converged.

courses/uir/hw/t4c-vi.txt · Last modified: 2023/10/12 11:39 by milecdav