Cost-Algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Uniform Cost Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this exercise you'll implement extend breadth-first search by incorporating a cost for each action."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from enum import Enum\n",
    "from queue import PriorityQueue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://wiki.python.org/moin/TimeComplexity gives a solid overview of Python data structures and their time complexity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* [`Enum`](https://docs.python.org/3/library/enum.html#module-enum) is used to represent possible actions on the grid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Action(Enum):\n",
    "    \"\"\"\n",
    "    An action is represented by a 3 element tuple.\n",
    "    \n",
    "    The first 2 values are the delta of the action relative\n",
    "    to the current grid position. The third and final value\n",
    "    is the cost of performing the action.\n",
    "    \"\"\"\n",
    "    LEFT = (0, -1, 1)\n",
    "    RIGHT = (0, 1, 1)\n",
    "    UP = (-1, 0, 1)\n",
    "    DOWN = (1, 0, 1)\n",
    "    \n",
    "    def __str__(self):\n",
    "        if self == self.LEFT:\n",
    "            return '<'\n",
    "        elif self == self.RIGHT:\n",
    "            return '>'\n",
    "        elif self == self.UP:\n",
    "            return '^'\n",
    "        elif self == self.DOWN:\n",
    "            return 'v'\n",
    "    \n",
    "    @property\n",
    "    def cost(self):\n",
    "        return self.value[2]\n",
    "    \n",
    "    @property\n",
    "    def delta(self):\n",
    "        return (self.value[0], self.value[1])\n",
    "            \n",
    "    \n",
    "def valid_actions(grid, current_node):\n",
    "    \"\"\"\n",
    "    Returns a list of valid actions given a grid and current node.\n",
    "    \"\"\"\n",
    "    valid = [Action.UP, Action.LEFT, Action.RIGHT, Action.DOWN]\n",
    "    n, m = grid.shape[0] - 1, grid.shape[1] - 1\n",
    "    x, y = current_node\n",
    "    \n",
    "    # check if the node is off the grid or\n",
    "    # it's an obstacle\n",
    "    \n",
    "    if x - 1 < 0 or grid[x-1, y] == 1:\n",
    "        valid.remove(Action.UP)\n",
    "    if x + 1 > n or grid[x+1, y] == 1:\n",
    "        valid.remove(Action.DOWN)\n",
    "    if y - 1 < 0 or grid[x, y-1] == 1:\n",
    "        valid.remove(Action.LEFT)\n",
    "    if y + 1 > m or grid[x, y+1] == 1:\n",
    "        valid.remove(Action.RIGHT)\n",
    "        \n",
    "    return valid\n",
    "\n",
    "def visualize_path(grid, path, start):\n",
    "    sgrid = np.zeros(np.shape(grid), dtype=np.str)\n",
    "    sgrid[:] = ' '\n",
    "    sgrid[grid[:] == 1] = 'O'\n",
    "    \n",
    "    pos = start\n",
    "    \n",
    "    for a in path:\n",
    "        da = a.value\n",
    "        sgrid[pos[0], pos[1]] = str(a)\n",
    "        pos = (pos[0] + da[0], pos[1] + da[1])\n",
    "    sgrid[pos[0], pos[1]] = 'G'\n",
    "    sgrid[start[0], start[1]] = 'S'  \n",
    "    return sgrid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cost Search\n",
    "\n",
    "In this section you will extend the breadth-first search algorithm by incorporating a cost for each action. Your task is to compute the lowest cost path. Does this change the data structures you should use?\n",
    "\n",
    "You will need to implement the remaining `TODOs`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def uniform_cost(grid, start, goal):\n",
    "\n",
    "    # TODO: Initialize the starting variables\n",
    "    path = []\n",
    "    queue = PriorityQueue()\n",
    "    visited = set()\n",
    "    \n",
    "    queue.put((0, start))\n",
    "    visited.add(start)\n",
    "    \n",
    "    branch = {}\n",
    "    found = False\n",
    "    \n",
    "    while not queue.empty():\n",
    "        # TODO: Remove the first element from the queue\n",
    "        item = queue.get()\n",
    "        current_cost = item[0]\n",
    "        current_node = item[1]\n",
    "        print(item, current_cost, current_node)\n",
    "        \n",
    "        # TODO: Check if the current vertex corresponds to the goal state\n",
    "        if current_node == goal:        \n",
    "            print('Found a path.')\n",
    "            found = True\n",
    "            break\n",
    "        else:\n",
    "            for action in valid_actions(grid, current_node): \n",
    "                # TODO: determine the next_node using the action delta\n",
    "                delta = action.delta\n",
    "                cost = action.cost\n",
    "                next_node = (current_node[0] + delta[0], current_node[1] + delta[1])\n",
    "                # TODO: compute the new cost\n",
    "                new_cost = (current_cost + cost)\n",
    "                \n",
    "                # TODO: Check if the new vertex has not been visited before.\n",
    "                # If the node has not been visited you will need to\n",
    "                # 1. Mark it as visited\n",
    "                # 2. Add it to the queue\n",
    "                if next_node not in visited:\n",
    "                    visited.add(next_node)\n",
    "                    queue.put((new_cost, next_node))\n",
    "                    branch[next_node] = (new_cost, current_node, action)\n",
    "             \n",
    "    path = []\n",
    "    path_cost = 0\n",
    "    if found:\n",
    "        \n",
    "        # retrace steps\n",
    "        path = []\n",
    "        n = goal\n",
    "        path_cost = branch[n][0]\n",
    "        while branch[n][1] != start:\n",
    "            path.append(branch[n][2])\n",
    "            n = branch[n][1]\n",
    "        path.append(branch[n][2])\n",
    "            \n",
    "    return path[::-1], path_cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Executing the search\n",
    "\n",
    "Run `uniform_cost()` and reference the grid to see if the path makes sense."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "start = (0, 0)\n",
    "goal = (4, 4)\n",
    "\n",
    "grid = np.array([\n",
    "    [0, 1, 0, 0, 0, 0],\n",
    "    [0, 1, 0, 1, 0, 0],\n",
    "    [0, 1, 0, 0, 0, 0],\n",
    "    [0, 1, 0, 0, 1, 0],\n",
    "    [0, 0, 0, 1, 0, 0],\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, (0, 0)) 0 (0, 0)\n",
      "(1, (1, 0)) 1 (1, 0)\n",
      "(2, (2, 0)) 2 (2, 0)\n",
      "(3, (3, 0)) 3 (3, 0)\n",
      "(4, (4, 0)) 4 (4, 0)\n",
      "(5, (4, 1)) 5 (4, 1)\n",
      "(6, (4, 2)) 6 (4, 2)\n",
      "(7, (3, 2)) 7 (3, 2)\n",
      "(8, (2, 2)) 8 (2, 2)\n",
      "(8, (3, 3)) 8 (3, 3)\n",
      "(9, (1, 2)) 9 (1, 2)\n",
      "(9, (2, 3)) 9 (2, 3)\n",
      "(10, (0, 2)) 10 (0, 2)\n",
      "(10, (2, 4)) 10 (2, 4)\n",
      "(11, (0, 3)) 11 (0, 3)\n",
      "(11, (1, 4)) 11 (1, 4)\n",
      "(11, (2, 5)) 11 (2, 5)\n",
      "(12, (0, 4)) 12 (0, 4)\n",
      "(12, (1, 5)) 12 (1, 5)\n",
      "(12, (3, 5)) 12 (3, 5)\n",
      "(13, (0, 5)) 13 (0, 5)\n",
      "(13, (4, 5)) 13 (4, 5)\n",
      "(14, (4, 4)) 14 (4, 4)\n",
      "Found a path.\n",
      "14 [<Action.DOWN: (1, 0, 1)>, <Action.DOWN: (1, 0, 1)>, <Action.DOWN: (1, 0, 1)>, <Action.DOWN: (1, 0, 1)>, <Action.RIGHT: (0, 1, 1)>, <Action.RIGHT: (0, 1, 1)>, <Action.UP: (-1, 0, 1)>, <Action.UP: (-1, 0, 1)>, <Action.RIGHT: (0, 1, 1)>, <Action.RIGHT: (0, 1, 1)>, <Action.RIGHT: (0, 1, 1)>, <Action.DOWN: (1, 0, 1)>, <Action.DOWN: (1, 0, 1)>, <Action.LEFT: (0, -1, 1)>]\n"
     ]
    }
   ],
   "source": [
    "path, path_cost = uniform_cost(grid, start, goal)\n",
    "print(path_cost, path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([['S', 'O', ' ', ' ', ' ', ' '],\n",
       "       ['v', 'O', ' ', 'O', ' ', ' '],\n",
       "       ['v', 'O', '>', '>', '>', 'v'],\n",
       "       ['v', 'O', '^', ' ', 'O', 'v'],\n",
       "       ['>', '>', '^', 'O', 'G', '<']], \n",
       "      dtype='<U1')"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# S -> start, G -> goal, O -> obstacle\n",
    "visualize_path(grid, path, start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Solution](/notebooks/Cost-Solution.ipynb)"
   ]
  },
  {
   "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}