Online_Optimization_9x9_counter_clockwise_twoadvs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us label the cells where the adversary can move below as cells 1 through 8. Cell number 6 is the starting cell for our adversary. The adversary can only randomly move to its adjacent cells."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "Game_Grid = []\n",
    "Game_Grid_Inv = []\n",
    "rewards = [(7,1),(1,7)]\n",
    "maze_size = 9\n",
    "for reward in rewards: \n",
    "    \n",
    "    game_grid = np.zeros((maze_size,maze_size))\n",
    "    \n",
    "    game_grid[reward[0]-1, reward[1]-1] = 1  #State 1\n",
    "    game_grid[reward[0]-1, reward[1]] = 2  #State 2\n",
    "    game_grid[reward[0]-1, reward[1]+1] = 3  #State 3\n",
    "    game_grid[reward[0], reward[1]-1] = 4  #State 4\n",
    "    game_grid[reward[0], reward[1]+1] = 5  #State 5\n",
    "    game_grid[reward[0]+1, reward[1]-1] = 6  #State 6\n",
    "    game_grid[reward[0]+1, reward[1]] = 7  #State 7\n",
    "    game_grid[reward[0]+1, reward[1]+1] = 8  #State 8\n",
    "    Game_Grid.append(game_grid) \n",
    "    \n",
    "    game_grid_inv={}\n",
    "\n",
    "    game_grid_inv[1]=(reward[0]-1,reward[1]-1)\n",
    "    game_grid_inv[2]=(reward[0]-1,reward[1])\n",
    "    game_grid_inv[3]=(reward[0]-1,reward[1]+1)\n",
    "    game_grid_inv[4]=(reward[0],reward[1]-1)\n",
    "    game_grid_inv[5]=(reward[0],reward[1]+1)\n",
    "    game_grid_inv[6]=(reward[0]+1,reward[1]-1)\n",
    "    game_grid_inv[7]=(reward[0]+1,reward[1])\n",
    "    game_grid_inv[8]=(reward[0]+1,reward[1]+1)\n",
    "    Game_Grid_Inv.append(game_grid_inv)\n",
    "    \n",
    "Game_Grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Game_Grid_Inv"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Trans_Matrix will be our transition probability matrix for the adversary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = np.sum(Game_Grid[0] > 0)\n",
    "Trans_Matrix = np.zeros((m, m))\n",
    "Trans_Matrix[0,1] = 1\n",
    "Trans_Matrix[1,2] = 1\n",
    "Trans_Matrix[2,4] = 1\n",
    "Trans_Matrix[3,0] = 1\n",
    "Trans_Matrix[4,7] = 1\n",
    "Trans_Matrix[5,3] = 1\n",
    "Trans_Matrix[6,5] = 1\n",
    "Trans_Matrix[7,6] = 1\n",
    "#Trans_Matrix = np.linalg.inv(Trans_Matrix)\n",
    "Trans_Matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from gurobipy import *\n",
    "from itertools import combinations \n",
    "import networkx as nx\n",
    "import numpy as np\n",
    "\n",
    "def Manhattan_Distance(x,y):\n",
    "    return np.abs(x[0]-y[0])+np.abs(x[1]-y[1])\n",
    "\n",
    "## Construct network\n",
    "grid_dimension=maze_size\n",
    "G=nx.Graph()\n",
    "for i in range(grid_dimension):\n",
    "    for j in range(grid_dimension):\n",
    "        G.add_node((i,j))\n",
    "        \n",
    "for (i,j) in combinations(G.nodes(),2):\n",
    "     if Manhattan_Distance(i,j)<=1:\n",
    "            G.add_edge(i,j)\n",
    "pos={}\n",
    "for i in G.nodes():\n",
    "    pos[i]=(int(i[0]), maze_size-int(i[1]))\n",
    "    \n",
    "nx.draw(G,pos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "starting_agent_location=(0,0)\n",
    "for i in G.nodes():\n",
    "    G.nodes[i]['current_agent']=False\n",
    "    for j in range(0,len(rewards)):\n",
    "        current_adversary = 'current_adversary' + str(j)\n",
    "        G.nodes[i][current_adversary] = False\n",
    "        reward = 'reward'+ str(j)\n",
    "        G.nodes[i][reward] = False\n",
    "        possible_adversary = 'possible_adversary' + str(j)\n",
    "        G.nodes[i][possible_adversary] = False\n",
    "for j in range(0,len(rewards)):\n",
    "    reward = 'reward'+ str(j)\n",
    "    G.nodes[rewards[j]][reward]=True\n",
    "    possible_adversary = 'possible_adversary' + str(j)\n",
    "    G.nodes[rewards[j][0]-1,rewards[j][1]-1][possible_adversary] = True\n",
    "    G.nodes[rewards[j][0]-1,rewards[j][1]][possible_adversary] = True\n",
    "    G.nodes[rewards[j][0]-1,rewards[j][1]+1][possible_adversary] = True\n",
    "    G.nodes[rewards[j][0],rewards[j][1]+1][possible_adversary] = True\n",
    "    G.nodes[rewards[j][0]+1,rewards[j][1]+1][possible_adversary] = True\n",
    "    G.nodes[rewards[j][0]+1,rewards[j][1]][possible_adversary] = True\n",
    "    G.nodes[rewards[j][0]+1,rewards[j][1]-1][possible_adversary] = True\n",
    "    G.nodes[rewards[j][0],rewards[j][1]-1][possible_adversary] = True\n",
    "    \n",
    "\n",
    "G.nodes[starting_agent_location]['current_agent']=True\n",
    "for j in range(0,len(rewards)):\n",
    "    current_adversary = 'current_adversary' + str(j)\n",
    "    G.nodes[rewards[j][0]-1,rewards[j][1]-1][current_adversary]=True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(G,pos)\n",
    "nx.draw_networkx_nodes(G, pos, nodelist=[i for i in G.nodes() if i==starting_agent_location], node_color='black') \n",
    "for j in range(0,len(rewards)):\n",
    "    reward = 'reward' + str(j)\n",
    "    nx.draw_networkx_nodes(G, pos, nodelist=[i for i in G.nodes() if G.nodes[i][reward]], node_color='g')    \n",
    "    possible_adversary = 'possible_adversary' + str(j)\n",
    "    nx.draw_networkx_nodes(G, pos, nodelist=[i for i in G.nodes() if G.nodes[i][possible_adversary]], node_color='y')\n",
    "    current_adversary = 'current_adversary' + str(j)\n",
    "    nx.draw_networkx_nodes(G, pos, nodelist=[i for i in G.nodes() if G.nodes[i][current_adversary]], node_color='r')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Set definitions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "starting_agent_location=(0,0)\n",
    "dest=(maze_size-1,maze_size-1)\n",
    "T=maze_size*maze_size\n",
    "done=False\n",
    "captured=[False]*len(rewards)\n",
    "maxReward=100\n",
    "\n",
    "current_agent_location=starting_agent_location\n",
    "current_adversary_location = []\n",
    "for i in range(0,len(rewards)):\n",
    "    current_adversary_location.append((rewards[i][1]-1,rewards[i][0]-1))\n",
    "current_time=0\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Main online optimization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "start_time = time.time()\n",
    "import random\n",
    "from collections import Counter\n",
    "reward = {}\n",
    "importance=100000\n",
    "n_success = 0\n",
    "total_reward = 0\n",
    "total_regret = 0\n",
    "average_agent_heatmap = {}\n",
    "for j in range(0,maze_size):\n",
    "    for k in range(0,maze_size):\n",
    "        average_agent_heatmap[(j,k)] = 1\n",
    "\n",
    "for e in range(50):\n",
    "    agent_heatmap = {}\n",
    "    for j in range(0,maze_size):\n",
    "        for k in range(0,maze_size):\n",
    "            agent_heatmap[(j,k)] = 0\n",
    "    reward[e] = 0\n",
    "    done=False\n",
    "    captured=[False]*len(rewards)\n",
    "    current_agent_location=starting_agent_location\n",
    "    current_adversary_location = []  \n",
    "    for i in range(0,len(rewards)):\n",
    "        current_adversary_location.append((rewards[i][1]-1,rewards[i][0]-1))\n",
    "    current_time=0\n",
    "    while True:\n",
    "        #print(\"Current Time:\" + str(current_time))\n",
    "        ####################\n",
    "        ##Printing details##\n",
    "        ####################\n",
    "        current_adversary_loc = []\n",
    "        for z in range(0,len(rewards)):\n",
    "            current_adversary_loc.append(int(Game_Grid[z][current_adversary_location[z][1],current_adversary_location[z][0]]))\n",
    "        #print(\"Current agent location: \"+str(current_agent_location))\n",
    "        #print(\"Current adversary location: \"+str(current_adversary_location))\n",
    "        #print(\"Current adversary loc:\" + str(current_adversary_loc))\n",
    "        #print(\"Current time: \"+str(current_time))\n",
    "\n",
    "\n",
    "        for z in range(0,len(rewards)):\n",
    "            if current_agent_location==current_adversary_location[z]:\n",
    "                #print(\"Captured Reward \"+str(z))\n",
    "                break\n",
    "        if done==True:\n",
    "            average_agent_heatmap = Counter(average_agent_heatmap) + Counter(agent_heatmap)\n",
    "            n_success += 1\n",
    "            total_reward += reward[e]\n",
    "            total_regret += (475-reward[e])\n",
    "            #print(\"Successful\")\n",
    "            break\n",
    "\n",
    "        ######################\n",
    "        ##Setting up rewards##\n",
    "        ######################\n",
    "        #print(\"captured:\"+str(captured))\n",
    "        if all(captured):\n",
    "            destination=dest\n",
    "        else:\n",
    "            #rew = random.choice((np.where(np.array((captured))==False)[0]))\n",
    "            #print(captured)\n",
    "            rew = (np.where(np.array((captured))==False)[0])[0]\n",
    "            destination = (rewards[rew][0],rewards[rew][1])\n",
    "        #print(\"destination:\"+ str(destination))\n",
    "        r={}\n",
    "        for (i,d) in G.nodes(data=True):\n",
    "            r[i] = 0\n",
    "        for z in range(0,len(rewards)):\n",
    "            for (i,d) in G.nodes(data=True):\n",
    "                if d['reward'+str(z)]==True and not captured[z]:\n",
    "                    r[i]=maxReward\n",
    "\n",
    "        ########################\n",
    "        ##Setting up penalties##\n",
    "        ########################\n",
    "        p={}\n",
    "        for (i,d) in G.nodes(data=True):\n",
    "            p[i]={}\n",
    "            p[i][current_time]=0\n",
    "\n",
    "        for t in range(current_time, T):\n",
    "            for (i,d) in G.nodes(data=True):\n",
    "                p[i][t]=0\n",
    "        for t in range(current_time, T):\n",
    "            for z in range(0,len(rewards)):\n",
    "                original_probabilities = np.linalg.matrix_power(Trans_Matrix, t+1-current_time)[current_adversary_loc[z]-1,] # probabilities using matrix power function \n",
    "                #for (i,d) in G.nodes(data=True):\n",
    "                #    if d['possible_adversary'+str(z)]==True:\n",
    "                #        p[i][t]=original_probabilities[int(Game_Grid[z][i[1]][i[0]])-1]\n",
    "                for i, e in enumerate(list(original_probabilities)):\n",
    "                    if e != 0:\n",
    "                        p[(Game_Grid_Inv[z][i+1][1],Game_Grid_Inv[z][i+1][0])][t] = original_probabilities[i]\n",
    "                        \n",
    "        \n",
    "\n",
    "        ####################\n",
    "        ##Setting up model##\n",
    "        ####################          \n",
    "        model=Model(\"model_time\"+str(current_time))\n",
    "        model.setParam('OutputFlag', 0) \n",
    "        x={}\n",
    "        y={}\n",
    "        for i in G.nodes():\n",
    "            y[i]={}\n",
    "            y[i][current_time]=model.addVar(vtype=GRB.BINARY, name=\"y\"+str(i)+\",\"+str(t))\n",
    "            for t in range(current_time, T):\n",
    "                y[i][t+1]=model.addVar(vtype=GRB.BINARY,obj=t-r[i]+importance*p[i][t], name=\"y\"+str(i)+\",\"+str(t))\n",
    "        for (i,j) in G.edges():\n",
    "            x[i,j]={}\n",
    "            x[j,i]={}\n",
    "            for t in range(current_time, T):\n",
    "                x[i,j][t]=model.addVar(vtype=GRB.BINARY, name=\"x\"+str(i)+\",\"+str(j)+\",\"+str(t))\n",
    "                x[j,i][t]=model.addVar(vtype=GRB.BINARY, name=\"x\"+str(j)+\",\"+str(i)+\",\"+str(t))\n",
    "\n",
    "\n",
    "        ################################\n",
    "        ## Setting up the constraints ##\n",
    "        model.addConstr(y[current_agent_location[0], current_agent_location[1]][current_time]==1) \n",
    "        ################################\n",
    "\n",
    "        # agent only be at one node at a time\n",
    "        for t in range(current_time, T):\n",
    "            #print(\"time:\"+str(t))\n",
    "            model.addConstr(quicksum(y[i[0],i[1]][t] for i in G.nodes()) <= 1)\n",
    "\n",
    "        # agent can only be in each node once when planning\n",
    "        for i in G.nodes():\n",
    "            model.addConstr(quicksum(y[i[0],i[1]][t] for t in range(current_time,T)) <= 1)\n",
    "\n",
    "        # The agent can and will only exit from the node it is currently in\n",
    "        for i in G.nodes():\n",
    "            for t in range(current_time+1, T):\n",
    "                model.addConstr(quicksum(x[j,i][t-1] for j in G[i])==y[i][t])\n",
    "\n",
    "        # When an agent enters a node it must exit it as well\n",
    "        for i in G.nodes():\n",
    "            if i!=destination and i!=current_agent_location:\n",
    "                for t in range(current_time+1, T):\n",
    "                    model.addConstr(quicksum(x[j,i][t-1] for j in G[i])==quicksum(x[i,j][t] for j in G[i]))#, name=str(i))\n",
    "\n",
    "        # agent has to move every step\n",
    "        model.addConstr(quicksum(x[current_agent_location, j][current_time] for j in G[current_agent_location])==1)\n",
    "\n",
    "        #have to reach destination(might not be needed)\n",
    "        expr=LinExpr()\n",
    "        for j in G[destination]:\n",
    "            for t in range(current_time, T):\n",
    "                expr+=x[j, destination][t]\n",
    "        model.addConstr(expr==1)\n",
    "\n",
    "        #model.write(\"myModel\"+str(current_time)+\".lp\")\n",
    "\n",
    "        model.optimize()\n",
    "        next_location=-1\n",
    "        for t in range(current_time, T):\n",
    "            for (i,j) in G.edges():\n",
    "                if x[i,j][t].X==1:\n",
    "                    #print(t)\n",
    "                    #print(i,j)\n",
    "                    if t==current_time:\n",
    "                        next_location=j\n",
    "                if x[j,i][t].X==1:\n",
    "                    #print(t)\n",
    "                    #print(j,i)\n",
    "                    if t==current_time:\n",
    "                        next_location=i\n",
    "        for i in G.nodes():\n",
    "            if y[i][current_time].X==1:\n",
    "                #print(i)\n",
    "                continue\n",
    "\n",
    "        current_agent_location=next_location \n",
    "\n",
    "        #print(\"Next agent location: \" + str(next_location))\n",
    "        for (i,d) in G.nodes(data=True):\n",
    "            for z in range(0,len(rewards)):\n",
    "                if d['reward'+str(z)]==True:\n",
    "                    if str(i)==str(next_location):\n",
    "                        captured[z]=True\n",
    "                        print(\"Just captured reward \" + str(z))\n",
    "\n",
    "\n",
    "\n",
    "        current_time+=1\n",
    "\n",
    "        ### THIS IS THE PART THAT NEEDS UPDATING ########\n",
    "        from random import choices\n",
    "        next_adversary_location = []\n",
    "        for z in range(0,len(rewards)):\n",
    "            choose=choices(range(0,8), Trans_Matrix[current_adversary_loc[z]-1,:])\n",
    "            #print(choose)\n",
    "            next_adversary_location.append((Game_Grid_Inv[z][choose[0]+1][1],Game_Grid_Inv[z][choose[0]+1][0]))\n",
    "        ########################################\n",
    "\n",
    "        for z in range(0,len(rewards)):\n",
    "            current_adversary_location[z]=next_adversary_location[z]\n",
    "            #print(\"Next adversary location: \" + str(next_adversary_location))\n",
    "\n",
    "            \n",
    "        agent_heatmap[(current_agent_location[1],current_agent_location[0])] -= .2\n",
    "        \n",
    "        if current_agent_location in current_adversary_location:\n",
    "            reward[e] -= 1000\n",
    "        elif current_agent_location in rewards:\n",
    "            #if agent_heatmap[current_agent_location] == 0:\n",
    "            reward[e] += 200\n",
    "            #else:\n",
    "                #reward[e] -= 1\n",
    "        elif current_agent_location == destination:\n",
    "            reward[e] += 100\n",
    "        else:\n",
    "            reward[e] -= 1\n",
    "            \n",
    "        \n",
    "        \n",
    "\n",
    "        if current_agent_location==dest:\n",
    "            #if captured == True:\n",
    "                #print(\"Won Game\")\n",
    "                #zprint(reward)\n",
    "            done=True\n",
    "\n",
    "            \n",
    "print(\"time: \",time.time()-start_time)            \n",
    "import matplotlib.pyplot as plt\n",
    "plt.grid('on')\n",
    "n = maze_size\n",
    "ax = plt.gca()\n",
    "ax.set_xticks(np.arange(0.5, n, 1))\n",
    "ax.set_yticks(np.arange(0.5, n, 1))\n",
    "ax.set_xticklabels([])\n",
    "ax.set_yticklabels([])\n",
    "canvas = maze = np.full(\n",
    "                        shape=(maze_size,maze_size),\n",
    "                        fill_value=1,\n",
    "                        dtype=np.int)\n",
    "for cell in average_agent_heatmap:\n",
    "    canvas[cell] = average_agent_heatmap[cell]\n",
    "img1 = plt.imshow(canvas, interpolation='none', cmap='gray', vmin=0, vmax=1)\n",
    "print(\"number of successes\",n_success)\n",
    "print(\"average reward:\",total_reward/n_success)\n",
    "print(\"average regret:\",total_regret/n_success)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Final Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "start_time = time.time()\n",
    "\n",
    "import numpy as np\n",
    "Game_Grid = []\n",
    "Game_Grid_Inv = []\n",
    "rewards = [(7,1),(1,7)]\n",
    "maze_size = 9\n",
    "for reward in rewards: \n",
    "    \n",
    "    game_grid = np.zeros((maze_size,maze_size))\n",
    "    \n",
    "    game_grid[reward[0]-1, reward[1]-1] = 1  #State 1\n",
    "    game_grid[reward[0]-1, reward[1]] = 2  #State 2\n",
    "    game_grid[reward[0]-1, reward[1]+1] = 3  #State 3\n",
    "    game_grid[reward[0], reward[1]-1] = 4  #State 4\n",
    "    game_grid[reward[0], reward[1]+1] = 5  #State 5\n",
    "    game_grid[reward[0]+1, reward[1]-1] = 6  #State 6\n",
    "    game_grid[reward[0]+1, reward[1]] = 7  #State 7\n",
    "    game_grid[reward[0]+1, reward[1]+1] = 8  #State 8\n",
    "    Game_Grid.append(game_grid) \n",
    "    \n",
    "    game_grid_inv={}\n",
    "\n",
    "    game_grid_inv[1]=(reward[0]-1,reward[1]-1)\n",
    "    game_grid_inv[2]=(reward[0]-1,reward[1])\n",
    "    game_grid_inv[3]=(reward[0]-1,reward[1]+1)\n",
    "    game_grid_inv[4]=(reward[0],reward[1]-1)\n",
    "    game_grid_inv[5]=(reward[0],reward[1]+1)\n",
    "    game_grid_inv[6]=(reward[0]+1,reward[1]-1)\n",
    "    game_grid_inv[7]=(reward[0]+1,reward[1])\n",
    "    game_grid_inv[8]=(reward[0]+1,reward[1]+1)\n",
    "    Game_Grid_Inv.append(game_grid_inv)\n",
    "    \n",
    "m = np.sum(Game_Grid[0] > 0)\n",
    "Trans_Matrix = np.zeros((m, m))\n",
    "Trans_Matrix[0,3] = 1\n",
    "Trans_Matrix[1,0] = 1\n",
    "Trans_Matrix[2,1] = 1\n",
    "Trans_Matrix[3,5] = 1\n",
    "Trans_Matrix[4,2] = 1\n",
    "Trans_Matrix[5,6] = 1\n",
    "Trans_Matrix[6,7] = 1\n",
    "Trans_Matrix[7,4] = 1\n",
    "\n",
    "from gurobipy import *\n",
    "from itertools import combinations \n",
    "import networkx as nx\n",
    "import numpy as np\n",
    "\n",
    "def Manhattan_Distance(x,y):\n",
    "    return np.abs(x[0]-y[0])+np.abs(x[1]-y[1])\n",
    "\n",
    "## Construct network\n",
    "grid_dimension=maze_size\n",
    "G=nx.Graph()\n",
    "for i in range(grid_dimension):\n",
    "    for j in range(grid_dimension):\n",
    "        G.add_node((i,j))\n",
    "        \n",
    "for (i,j) in combinations(G.nodes(),2):\n",
    "     if Manhattan_Distance(i,j)<=1:\n",
    "            G.add_edge(i,j)\n",
    "pos={}\n",
    "for i in G.nodes():\n",
    "    pos[i]=(int(i[0]), maze_size-int(i[1]))\n",
    "    \n",
    "starting_agent_location=(0,0)\n",
    "for i in G.nodes():\n",
    "    G.nodes[i]['current_agent']=False\n",
    "    for j in range(0,len(rewards)):\n",
    "        current_adversary = 'current_adversary' + str(j)\n",
    "        G.nodes[i][current_adversary] = False\n",
    "        rewardz = 'reward'+ str(j)\n",
    "        G.nodes[i][rewardz] = False\n",
    "        possible_adversary = 'possible_adversary' + str(j)\n",
    "        G.nodes[i][possible_adversary] = False\n",
    "for j in range(0,len(rewards)):\n",
    "    rewardz = 'reward'+ str(j)\n",
    "    G.nodes[rewards[j]][rewardz]=True\n",
    "    possible_adversary = 'possible_adversary' + str(j)\n",
    "    G.nodes[rewards[j][0]-1,rewards[j][1]-1][possible_adversary] = True\n",
    "    G.nodes[rewards[j][0]-1,rewards[j][1]][possible_adversary] = True\n",
    "    G.nodes[rewards[j][0]-1,rewards[j][1]+1][possible_adversary] = True\n",
    "    G.nodes[rewards[j][0],rewards[j][1]+1][possible_adversary] = True\n",
    "    G.nodes[rewards[j][0]+1,rewards[j][1]+1][possible_adversary] = True\n",
    "    G.nodes[rewards[j][0]+1,rewards[j][1]][possible_adversary] = True\n",
    "    G.nodes[rewards[j][0]+1,rewards[j][1]-1][possible_adversary] = True\n",
    "    G.nodes[rewards[j][0],rewards[j][1]-1][possible_adversary] = True\n",
    "    \n",
    "\n",
    "G.nodes[starting_agent_location]['current_agent']=True\n",
    "for j in range(0,len(rewards)):\n",
    "    current_adversary = 'current_adversary' + str(j)\n",
    "    G.nodes[rewards[j][0]-1,rewards[j][1]-1][current_adversary]=True\n",
    "    \n",
    "starting_agent_location=(0,0)\n",
    "dest=(maze_size-1,maze_size-1)\n",
    "T=maze_size*maze_size\n",
    "done=False\n",
    "captured=[False]*len(rewards)\n",
    "maxReward=100\n",
    "\n",
    "y = 0\n",
    "current_agent_location=starting_agent_location\n",
    "current_adversary_location = ((rewards[y][1]-1,rewards[y][0]-1))\n",
    "current_time=0\n",
    "current_adversary_loc = (int(Game_Grid[y][current_adversary_location[1],current_adversary_location[0]]))\n",
    "\n",
    "from random import choices\n",
    "y = 0\n",
    "m = np.sum(Game_Grid[y] > 0)\n",
    "obs_trans_matrix = np.zeros((m,m))\n",
    "for f in range(0,8):\n",
    "    choose=choices(range(0,8), Trans_Matrix[current_adversary_loc-1,:])\n",
    "    next_adversary_location=(Game_Grid_Inv[y][choose[0]+1][1],Game_Grid_Inv[y][choose[0]+1][0])\n",
    "    next_adversary_loc=int(Game_Grid[y][next_adversary_location[1],next_adversary_location[0]])\n",
    "    obs_trans_matrix[current_adversary_loc-1,next_adversary_loc-1] += 1\n",
    "    current_adversary_loc = next_adversary_loc\n",
    "    current_adversary_location = next_adversary_location\n",
    "    \n",
    "for i in range(m):\n",
    "    obs_trans_matrix[i, ] = obs_trans_matrix[i, ]/np.sum(obs_trans_matrix[i,:])\n",
    "\n",
    "import random\n",
    "from collections import Counter\n",
    "reward = {}\n",
    "importance=100000\n",
    "n_success = 0\n",
    "total_reward = 0\n",
    "total_regret = 0\n",
    "average_agent_heatmap = {}\n",
    "for j in range(0,maze_size):\n",
    "    for k in range(0,maze_size):\n",
    "        average_agent_heatmap[(j,k)] = 1\n",
    "\n",
    "for e in range(50):\n",
    "    agent_heatmap = {}\n",
    "    for j in range(0,maze_size):\n",
    "        for k in range(0,maze_size):\n",
    "            agent_heatmap[(j,k)] = 0\n",
    "    reward[e] = 0\n",
    "    done=False\n",
    "    captured=[False]*len(rewards)\n",
    "    current_agent_location=starting_agent_location\n",
    "    current_adversary_location = []  \n",
    "    for i in range(0,len(rewards)):\n",
    "        current_adversary_location.append((rewards[i][1]-1,rewards[i][0]-1))\n",
    "    current_time=0\n",
    "    while True:\n",
    "        #print(\"Current Time:\" + str(current_time))\n",
    "        ####################\n",
    "        ##Printing details##\n",
    "        ####################\n",
    "        current_adversary_loc = []\n",
    "        for z in range(0,len(rewards)):\n",
    "            current_adversary_loc.append(int(Game_Grid[z][current_adversary_location[z][1],current_adversary_location[z][0]]))\n",
    "        #print(\"Current agent location: \"+str(current_agent_location))\n",
    "        #print(\"Current adversary location: \"+str(current_adversary_location))\n",
    "        #print(\"Current adversary loc:\" + str(current_adversary_loc))\n",
    "        #print(\"Current time: \"+str(current_time))\n",
    "        \n",
    "        agent_heatmap[(current_agent_location[1],current_agent_location[0])] -= .2\n",
    "\n",
    "        for z in range(0,len(rewards)):\n",
    "            if current_agent_location==current_adversary_location[z]:\n",
    "                #print(\"Captured Reward \"+str(z))\n",
    "                break\n",
    "        if done==True:\n",
    "            average_agent_heatmap = Counter(average_agent_heatmap) + Counter(agent_heatmap)\n",
    "            n_success += 1\n",
    "            total_reward += reward[e]\n",
    "            total_regret += (475-reward[e])\n",
    "            #print(reward[e])\n",
    "        \n",
    "            break\n",
    "\n",
    "        ######################\n",
    "        ##Setting up rewards##\n",
    "        ######################\n",
    "        #print(\"captured:\"+str(captured))\n",
    "        if all(captured):\n",
    "            destination=dest\n",
    "        else:\n",
    "            #rew = random.choice((np.where(np.array((captured))==False)[0]))\n",
    "            #print(captured)\n",
    "            rew = (np.where(np.array((captured))==False)[0])[0]\n",
    "            destination = (rewards[rew][0],rewards[rew][1])\n",
    "        #print(\"destination:\"+ str(destination))\n",
    "        r={}\n",
    "        for (i,d) in G.nodes(data=True):\n",
    "            r[i] = 0\n",
    "        for z in range(0,len(rewards)):\n",
    "            for (i,d) in G.nodes(data=True):\n",
    "                if d['reward'+str(z)]==True and not captured[z]:\n",
    "                    r[i]=maxReward\n",
    "\n",
    "        ########################\n",
    "        ##Setting up penalties##\n",
    "        ########################\n",
    "        p={}\n",
    "        for (i,d) in G.nodes(data=True):\n",
    "            p[i]={}\n",
    "            p[i][current_time]=0\n",
    "\n",
    "        for t in range(current_time, T):\n",
    "            for (i,d) in G.nodes(data=True):\n",
    "                p[i][t]=0\n",
    "        for t in range(current_time, T):\n",
    "            for z in range(0,len(rewards)):\n",
    "                original_probabilities = np.linalg.matrix_power(obs_trans_matrix, t+1-current_time)[current_adversary_loc[z]-1,] # probabilities using matrix power function \n",
    "                #for (i,d) in G.nodes(data=True):\n",
    "                #    if d['possible_adversary'+str(z)]==True:\n",
    "                #        p[i][t]=original_probabilities[int(Game_Grid[z][i[1]][i[0]])-1]\n",
    "                for i, e in enumerate(list(original_probabilities)):\n",
    "                    if e != 0:\n",
    "                        p[(Game_Grid_Inv[z][i+1][1],Game_Grid_Inv[z][i+1][0])][t] = original_probabilities[i]\n",
    "                        \n",
    "        \n",
    "\n",
    "        ####################\n",
    "        ##Setting up model##\n",
    "        ####################          \n",
    "        model=Model(\"model_time\"+str(current_time))\n",
    "        model.setParam('OutputFlag', 0) \n",
    "        x={}\n",
    "        y={}\n",
    "        for i in G.nodes():\n",
    "            y[i]={}\n",
    "            y[i][current_time]=model.addVar(vtype=GRB.BINARY, name=\"y\"+str(i)+\",\"+str(t))\n",
    "            for t in range(current_time, T):\n",
    "                y[i][t+1]=model.addVar(vtype=GRB.BINARY,obj=t-r[i]+importance*p[i][t], name=\"y\"+str(i)+\",\"+str(t))\n",
    "        for (i,j) in G.edges():\n",
    "            x[i,j]={}\n",
    "            x[j,i]={}\n",
    "            for t in range(current_time, T):\n",
    "                x[i,j][t]=model.addVar(vtype=GRB.BINARY, name=\"x\"+str(i)+\",\"+str(j)+\",\"+str(t))\n",
    "                x[j,i][t]=model.addVar(vtype=GRB.BINARY, name=\"x\"+str(j)+\",\"+str(i)+\",\"+str(t))\n",
    "\n",
    "\n",
    "        ################################\n",
    "        ## Setting up the constraints ##\n",
    "        model.addConstr(y[current_agent_location[0], current_agent_location[1]][current_time]==1) \n",
    "        ################################\n",
    "\n",
    "        # agent only be at one node at a time\n",
    "        for t in range(current_time, T):\n",
    "            #print(\"time:\"+str(t))\n",
    "            model.addConstr(quicksum(y[i[0],i[1]][t] for i in G.nodes()) <= 1)\n",
    "\n",
    "        # agent can only be in each node once when planning\n",
    "        for i in G.nodes():\n",
    "            model.addConstr(quicksum(y[i[0],i[1]][t] for t in range(current_time,T)) <= 1)\n",
    "\n",
    "        # The agent can and will only exit from the node it is currently in\n",
    "        for i in G.nodes():\n",
    "            for t in range(current_time+1, T):\n",
    "                model.addConstr(quicksum(x[j,i][t-1] for j in G[i])==y[i][t])\n",
    "\n",
    "        # When an agent enters a node it must exit it as well\n",
    "        for i in G.nodes():\n",
    "            if i!=destination and i!=current_agent_location:\n",
    "                for t in range(current_time+1, T):\n",
    "                    model.addConstr(quicksum(x[j,i][t-1] for j in G[i])==quicksum(x[i,j][t] for j in G[i]))#, name=str(i))\n",
    "\n",
    "        # agent has to move every step\n",
    "        model.addConstr(quicksum(x[current_agent_location, j][current_time] for j in G[current_agent_location])==1)\n",
    "\n",
    "        #have to reach destination(might not be needed)\n",
    "        expr=LinExpr()\n",
    "        for j in G[destination]:\n",
    "            for t in range(current_time, T):\n",
    "                expr+=x[j, destination][t]\n",
    "        model.addConstr(expr==1)\n",
    "\n",
    "        #model.write(\"myModel\"+str(current_time)+\".lp\")\n",
    "\n",
    "        model.optimize()\n",
    "        next_location=-1\n",
    "        for t in range(current_time, T):\n",
    "            for (i,j) in G.edges():\n",
    "                if x[i,j][t].X==1:\n",
    "                    #print(t)\n",
    "                    #print(i,j)\n",
    "                    if t==current_time:\n",
    "                        next_location=j\n",
    "                if x[j,i][t].X==1:\n",
    "                    #print(t)\n",
    "                    #print(j,i)\n",
    "                    if t==current_time:\n",
    "                        next_location=i\n",
    "        for i in G.nodes():\n",
    "            if y[i][current_time].X==1:\n",
    "                #print(i)\n",
    "                continue\n",
    "\n",
    "        current_agent_location=next_location \n",
    "\n",
    "        #print(\"Next agent location: \" + str(next_location))\n",
    "        for (i,d) in G.nodes(data=True):\n",
    "            for z in range(0,len(rewards)):\n",
    "                if d['reward'+str(z)]==True:\n",
    "                    if str(i)==str(next_location):\n",
    "                        captured[z]=True\n",
    "                        #print(\"Just captured reward \" + str(z))\n",
    "\n",
    "\n",
    "\n",
    "        current_time+=1\n",
    "\n",
    "        ### THIS IS THE PART THAT NEEDS UPDATING ########\n",
    "        next_adversary_location = []\n",
    "        for z in range(0,len(rewards)):\n",
    "            choose=choices(range(0,8), Trans_Matrix[current_adversary_loc[z]-1,:])\n",
    "            #print(choose)\n",
    "            next_adversary_location.append((Game_Grid_Inv[z][choose[0]+1][1],Game_Grid_Inv[z][choose[0]+1][0]))\n",
    "        ########################################\n",
    "\n",
    "        for z in range(0,len(rewards)):\n",
    "            current_adversary_location[z]=next_adversary_location[z]\n",
    "            #print(\"Next adversary location: \" + str(next_adversary_location))\n",
    "\n",
    "        \n",
    "        if current_agent_location in current_adversary_location:\n",
    "            reward[e] -= 1000\n",
    "        elif current_agent_location in rewards:\n",
    "            if agent_heatmap[(current_agent_location[1],current_agent_location[0])] == 0:\n",
    "                reward[e] += 200\n",
    "            else:\n",
    "                reward[e] -= 1\n",
    "        elif current_agent_location == destination:\n",
    "            reward[e] += 100\n",
    "        else:\n",
    "            reward[e] -= 1\n",
    "            \n",
    "        \n",
    "\n",
    "        if current_agent_location==dest:\n",
    "            #if captured == True:\n",
    "                #print(\"Won Game\")\n",
    "                #zprint(reward)\n",
    "            done=True\n",
    "\n",
    "            \n",
    "print(\"time: \",time.time()-start_time)            \n",
    "import matplotlib.pyplot as plt\n",
    "plt.grid('on')\n",
    "n = maze_size\n",
    "ax = plt.gca()\n",
    "ax.set_xticks(np.arange(0.5, n, 1))\n",
    "ax.set_yticks(np.arange(0.5, n, 1))\n",
    "ax.set_xticklabels([])\n",
    "ax.set_yticklabels([])\n",
    "canvas = maze = np.full(\n",
    "                        shape=(maze_size,maze_size),\n",
    "                        fill_value=1,\n",
    "                        dtype=np.int)\n",
    "for cell in average_agent_heatmap:\n",
    "    canvas[cell] = average_agent_heatmap[cell]\n",
    "img1 = plt.imshow(canvas, interpolation='none', cmap='gray', vmin=0, vmax=1)\n",
    "print(\"number of successes\",n_success)\n",
    "print(\"average reward:\",sum(reward.values())/n_success)\n",
    "print(\"average regret:\",475-(sum(reward.values())/n_success))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "plt.grid('on')\n",
    "n = maze_size\n",
    "ax = plt.gca()\n",
    "ax.set_xticks(np.arange(0.5, n, 1))\n",
    "ax.set_yticks(np.arange(0.5, n, 1))\n",
    "ax.set_xticklabels([])\n",
    "ax.set_yticklabels([])\n",
    "canvas = maze = np.full(\n",
    "                        shape=(maze_size,maze_size),\n",
    "                        fill_value=1,\n",
    "                        dtype=np.int)\n",
    "for cell in average_agent_heatmap:\n",
    "    canvas[cell] = average_agent_heatmap[cell]\n",
    "img1 = plt.imshow(canvas, interpolation='none', cmap='gray', vmin=0, vmax=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}