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

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
 
        Parameters
        ----------
        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
 
        Parameters
        ----------
        matrix: n times m array of floats
            Game utility matrix
 
 
        Returns
        -------
        value:float
            computed value of the game
        strategy:float[n]
            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.

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.

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.