EAI6000_M2_AstarBugFix_HariShankaraNarasimhamGanjam.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/Narasimham88445/Data-science/blob/master/EAI6000_M2_AstarBugFix_HariShankaraNarasimhamGanjam.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dB4_y4GBm0tt"
      },
      "source": [
        "# A-Star(A*) Search Algorithm"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hRmWMPwTm5Ob"
      },
      "source": [
        "This notebook complements the walkthrough article [here](https://towardsdatascience.com/a-star-a-search-algorithm-eb495fb156bb) on the A-Star search algorithm. Throughout the notebook, we ask to you finish sections on your own and answer questions."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "auBnTGWHoMle"
      },
      "source": [
        "## [Question - Describe A*]\n",
        "Question: Describe A&ast; search in your own words."
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Answer: </br>\n",
        ">*The A* (A-Star) algorithm is an informed search algorithm widely used for finding the optimal path between an initial state and a goal state. It is particularly effective in path-finding applications, such as routing and navigation systems, gaming, and robotics. The A* algorithm combines the advantages of two other search strategies: Dijkstra's algorithm, which finds the shortest path, and greedy best-first search, which attempts to minimize the estimated cost to the goal.*\n",
        "\n",
        ">*The A* algorithm works by maintaining a prioritized list of nodes to explore, ordered by an evaluation function that considers both the actual cost from the start node to the current node and an admissible heuristic estimate of the remaining cost to reach the goal. This heuristic function plays a crucial role in guiding the search towards the most promising nodes, allowing the algorithm to find the optimal solution efficiently.\n",
        "\n",
        "One of the key strengths of the A* algorithm is its ability to find the shortest path while avoiding unnecessary explorations, making it highly effective in scenarios where computational resources are limited or the search space is large. Additionally, the algorithm's optimality and completeness guarantees, combined with its flexibility to incorporate domain-specific heuristics, have made it a widely adopted solution for path-finding problems across various domains.*"
      ],
      "metadata": {
        "id": "SzE0yCqrucUp"
      }
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FsP7pSLAoooN"
      },
      "source": [
        "## [Question - Describe h and g]\n",
        "Question: *In A&ast; search, describe the two key elements of f(n) (namely h(n) and g(n)). What do they represent in the algorithm and how do they differ?*"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Answer: </br>\n",
        ">*In A&ast; search algorithm, there are 2 key elements namely g(n) and h(n). The significance of these 2 are:*\n",
        "\n",
        ">**g(n)**: *This represents the actual cost incurred from the start node to the current node (n) being evaluated. It is the cumulative sum of the costs associated with traversing the nodes along the path from the initial node to the current node. This cost is calculated based on the specific problem domain and the traversal cost between nodes.*\n",
        "\n",
        ">**h(n)**: *is is a heuristic function that estimates the remaining cost from the current node (n) to the goal node. Since the actual cost to the goal is unknown until the goal is reached, h(n) provides an admissible estimate or lower bound of the remaining cost. The accuracy of this heuristic plays a crucial role in the efficiency of the A* algorithm, as it helps prioritize the exploration of more promising nodes.*\n",
        "\n",
        "To ensure the optimality of the solution, the heuristic function h(n) must be admissible, meaning it should never overestimate the actual cost to the goal. An admissible heuristic guarantees that the A* algorithm will find the optimal path if one exists. However, underestimating the cost can lead to suboptimal solutions or unnecessary explorations.\n",
        "\n",
        "The evaluation function used by the A* algorithm combines g(n) and h(n) to determine the order in which nodes are explored. The node with the lowest value of g(n) + h(n) is considered the most promising and is expanded next. This approach allows the algorithm to balance the exploration of nodes with the lowest actual cost so far (g(n)) and those with the most promising estimated remaining cost (h(n)).\n",
        "\n",
        "By effectively utilizing these two components, the A* search algorithm can efficiently find the optimal path while minimizing unnecessary explorations, making it a powerful and widely adopted technique for path-finding and search problems in various domains."
      ],
      "metadata": {
        "id": "QBkOWz83u0yV"
      }
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-_VkEgNWuMDK"
      },
      "source": [
        "## [Activity - run Node]\n",
        "Examine and run the below code."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ufRvBVJBmmxA"
      },
      "source": [
        "class PathfindingPawn():\n",
        "    \"\"\"\n",
        "    A pawn on the chessboard of pathfinding,\n",
        "    ready to embark on a quest for the optimal route.\n",
        "    \"\"\"\n",
        "\n",
        "    def __init__(self, parent_square=None, current_square=None):\n",
        "        self.parent_square = parent_square\n",
        "        self.current_square = current_square\n",
        "        self.steps_taken = 0\n",
        "        self.estimated_steps_left = 0\n",
        "        self.total_steps_projected = 0\n",
        "\n",
        "    def __eq__(self, other):\n",
        "        return self.current_square == other.current_square\n",
        "\n",
        "    def reach_for_the_goal(self, goal_square):\n",
        "        \"\"\"\n",
        "        Calculate the estimated steps left and the total projected steps.\n",
        "        This method fuels the pawn's determination to find the optimal path.\n",
        "        \"\"\"\n",
        "        # Estimate the steps left using a heuristic (e.g., Manhattan distance)\n",
        "        self.estimated_steps_left = calculate_heuristic(self.current_square, goal_square)\n",
        "\n",
        "        # Combine the steps taken so far with the estimated steps left\n",
        "        self.total_steps_projected = self.steps_taken + self.estimated_steps_left\n",
        "\n",
        "    def advance_one_step(self, new_square):\n",
        "        \"\"\"\n",
        "        Move the pawn to a new square, updating its journey.\n",
        "        \"\"\"\n",
        "        self.parent_square = self.current_square\n",
        "        self.current_square = new_square\n",
        "        self.steps_taken += 1\n",
        "\n",
        "def calculate_heuristic(current_square, goal_square):\n",
        "    \"\"\"\n",
        "    A heuristic function to estimate the remaining steps.\n",
        "    In this example, we'll use the Manhattan distance.\n",
        "    \"\"\"\n",
        "    x1, y1 = current_square\n",
        "    x2, y2 = goal_square\n",
        "    return abs(x1 - x2) + abs(y1 - y2)"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ucsmb_lfuTrp"
      },
      "source": [
        "## [Question - Explain 'Node']\n",
        "In your own words, describe what the purpose of the *Node* class is. Why do we have to initialize a parent and a position?"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Answer: </br>\n",
        ">*The 'Node' class is an initiator which creates objects of the nodes to be used in the program. Objects created by this Node class has all of the node's attributes, such as its parent, location, and all three costs (g, h, and f).*\n",
        "\n",
        ">*This Node class will create objects for both parent node and their children nodes. Children nodes will need to have information about their parent. Moreover, a node should be able to identify its position in the maze. There can not be rogue nodes wavering the maze and each node is assigned a place to be at. Therefore, it is important to initialize a parent (if applicable) and a position when creating objects using Node class.*"
      ],
      "metadata": {
        "id": "31M1_7IkD_v3"
      }
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B6s0TVMuur8t"
      },
      "source": [
        "## [Activity - Run astar() ]"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wYzrkdjZpxZs",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "08493bcc-5284-4a98-db1e-8d0bcdab67cc"
      },
      "source": [
        "import heapq\n",
        "\n",
        "class Node:\n",
        "    \"\"\"Represents a node in the maze with A* pathfinding metrics.\"\"\"\n",
        "    def __init__(self, parent=None, position=None):\n",
        "        self.parent = parent\n",
        "        self.position = position\n",
        "        self.g = 0\n",
        "        self.h = 0\n",
        "        self.f = 0\n",
        "\n",
        "    def __eq__(self, other):\n",
        "        return self.position == other.position\n",
        "\n",
        "    def __lt__(self, other):\n",
        "        \"\"\"Heapq uses this to compare which node has lower f value.\"\"\"\n",
        "        return self.f < other.f\n",
        "\n",
        "def astar(maze, start, end):\n",
        "    \"\"\"Perform the A* search algorithm to find the shortest path from start to end in a maze.\"\"\"\n",
        "    # Initialize the start and end nodes\n",
        "    start_node = Node(None, start)\n",
        "    end_node = Node(None, end)\n",
        "\n",
        "    # Priority queue to hold nodes to be explored, and set to hold visited nodes\n",
        "    open_heap = []\n",
        "    closed_set = set()\n",
        "    heapq.heappush(open_heap, start_node)\n",
        "\n",
        "    # Directions for moving in the maze (4-connected grid)\n",
        "    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # Up, Right, Down, Left\n",
        "\n",
        "    while open_heap:\n",
        "        current_node = heapq.heappop(open_heap)\n",
        "\n",
        "        # If the end node is reached, reconstruct the path\n",
        "        if current_node == end_node:\n",
        "            path = []\n",
        "            while current_node:\n",
        "                path.append(current_node.position)\n",
        "                current_node = current_node.parent\n",
        "            return path[::-1]\n",
        "\n",
        "        # Add the current node to the closed set\n",
        "        closed_set.add(current_node.position)\n",
        "\n",
        "        # Explore neighbors\n",
        "        for direction in directions:\n",
        "            neighbor_position = (current_node.position[0] + direction[0], current_node.position[1] + direction[1])\n",
        "\n",
        "            # Ensure the neighbor is within the maze and walkable\n",
        "            if 0 <= neighbor_position[0] < len(maze) and 0 <= neighbor_position[1] < len(maze[0]):\n",
        "                if maze[neighbor_position[0]][neighbor_position[1]] == 0:\n",
        "                    neighbor_node = Node(current_node, neighbor_position)\n",
        "                    if neighbor_node.position in closed_set:\n",
        "                        continue\n",
        "\n",
        "                    # Calculate g, h, and f values\n",
        "                    neighbor_node.g = current_node.g + 1\n",
        "                    neighbor_node.h = (end_node.position[0] - neighbor_position[0]) ** 2 + (end_node.position[1] - neighbor_position[1]) ** 2\n",
        "                    neighbor_node.f = neighbor_node.g + neighbor_node.h\n",
        "\n",
        "                    # Check if neighbor should be added to open heap\n",
        "                    if not any(open_node.position == neighbor_node.position and open_node.g <= neighbor_node.g for open_node in open_heap):\n",
        "                        heapq.heappush(open_heap, neighbor_node)\n",
        "\n",
        "    return None  # Return None if no path is found\n",
        "\n",
        "# Example usage\n",
        "maze = [\n",
        "    [0, 0, 0, 0],\n",
        "    [1, 1, 1, 0],\n",
        "    [0, 0, 0, 0]\n",
        "]\n",
        "start = (2, 0)\n",
        "end = (0, 0)\n",
        "path = astar(maze, start, end)\n",
        "print(\"Path:\", path)\n"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Path: [(2, 0), (2, 1), (2, 2), (2, 3), (1, 3), (0, 3), (0, 2), (0, 1), (0, 0)]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hral7UX2vF0z"
      },
      "source": [
        "## [Question - Explain maze]\n",
        "What type of input should value of *maze* be?"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Answer: </br>\n",
        ">*The type of input of maze should be either be -*\n",
        "\n",
        ">*   *NESTED TUPPLE*\n",
        ">*   *TUPPLE of DICTIONARIES*\n",
        "\n",
        ">*The nested part refers to multiple number of nodes in a row and column as well.*\n",
        "\n",
        ">*The next important part in this maze is that the value '0' is the walkable path. Even the end node should be a walkable node (having value 0) to be able to be reached. Nodes with any other value than '0' are not walkable.*"
      ],
      "metadata": {
        "id": "qMCwfJjKG6V3"
      }
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EcB70Wbet1-w"
      },
      "source": [
        "## [Question - Build Main]\n",
        "Please use the above code that uses the astar() function to define a path from the beginning to the end of a maze. You can choose how the maze looks and where the start and end are."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MY8tTsSbt1XE",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b0c4448f-81c5-464f-c5f6-381fd91d113c"
      },
      "source": [
        "import heapq\n",
        "\n",
        "class Node:\n",
        "    def __init__(self, parent=None, position=None):\n",
        "        self.parent = parent\n",
        "        self.position = position\n",
        "        self.g = 0\n",
        "        self.h = 0\n",
        "        self.f = 0\n",
        "\n",
        "    def __eq__(self, other):\n",
        "        return self.position == other.position\n",
        "\n",
        "    def __lt__(self, other):\n",
        "        return self.f < other.f\n",
        "\n",
        "def astar(maze, start, end):\n",
        "    start_node = Node(None, tuple(start))\n",
        "    start_node.g = start_node.h = start_node.f = 0\n",
        "    end_node = Node(None, tuple(end))\n",
        "    end_node.g = end_node.h = end_node.f = 0\n",
        "\n",
        "    open_heap = []\n",
        "    heapq.heappush(open_heap, start_node)\n",
        "    closed_set = set()\n",
        "\n",
        "    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 4 possible directions\n",
        "\n",
        "    while open_heap:\n",
        "        current_node = heapq.heappop(open_heap)\n",
        "\n",
        "        if current_node == end_node:\n",
        "            path = []\n",
        "            while current_node:\n",
        "                path.append(current_node.position)\n",
        "                current_node = current_node.parent\n",
        "            return path[::-1]\n",
        "\n",
        "        closed_set.add(current_node.position)\n",
        "\n",
        "        for direction in directions:\n",
        "            node_position = (current_node.position[0] + direction[0], current_node.position[1] + direction[1])\n",
        "\n",
        "            if 0 <= node_position[0] < len(maze) and 0 <= node_position[1] < len(maze[0]) and maze[node_position[0]][node_position[1]] == 0:\n",
        "                new_node = Node(current_node, node_position)\n",
        "                if new_node.position in closed_set:\n",
        "                    continue\n",
        "\n",
        "                new_node.g = current_node.g + 1\n",
        "                new_node.h = ((end_node.position[0] - node_position[0]) ** 2) + ((end_node.position[1] - node_position[1]) ** 2)\n",
        "                new_node.f = new_node.g + new_node.h\n",
        "\n",
        "                if not any(node.position == new_node.position and node.g <= new_node.g for node in open_heap):\n",
        "                    heapq.heappush(open_heap, new_node)\n",
        "\n",
        "    return None\n",
        "\n",
        "def main():\n",
        "    maze = [\n",
        "        [0, 0, 1, 0, 0],\n",
        "        [0, 0, 1, 0, 1],\n",
        "        [1, 0, 0, 0, 0],\n",
        "        [0, 0, 0, 1, 0],\n",
        "        [0, 1, 1, 0, 0]\n",
        "    ]\n",
        "    start = (0, 0)  # Starting position at top-left corner\n",
        "    end = (4, 4)    # Ending position at bottom-right corner\n",
        "\n",
        "    path = astar(maze, start, end)\n",
        "    if path:\n",
        "        print(\"Path found:\", path)\n",
        "    else:\n",
        "        print(\"No path found\")\n",
        "\n",
        "if __name__ == \"__main__\":\n",
        "    main()\n"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Path found: [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_t_M9LWSwc79"
      },
      "source": [
        "## [Question - Impossible Maze]\n",
        "Now create a maze that the algorithm cannot solve. What is the output of the algorithm?"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Answer:</br>\n",
        ">The outcome comes out to be 'NONE' in case of impossible maze."
      ],
      "metadata": {
        "id": "P612wCNFlsrJ"
      }
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yoQ3fuVbwnuv",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "aa60235d-c34a-452d-a20e-4946030dc584"
      },
      "source": [
        "def find_path_through_impossible_maze(start, end):\n",
        "    \"\"\" Solve the maze using the A* search algorithm with a given start and end point. \"\"\"\n",
        "\n",
        "    class Node:\n",
        "        \"\"\" Represents a maze position with A* pathfinding metrics. \"\"\"\n",
        "        def __init__(self, parent=None, position=None):\n",
        "            self.parent = parent\n",
        "            self.position = position\n",
        "            self.g = 0  # Cost from start to node\n",
        "            self.h = 0  # Heuristic estimated cost from node to end\n",
        "            self.f = 0  # Total cost\n",
        "\n",
        "        def __eq__(self, other):\n",
        "            return self.position == other.position\n",
        "\n",
        "        def __lt__(self, other):\n",
        "            \"\"\" Heapq uses this to prioritize nodes with lower total cost. \"\"\"\n",
        "            return self.f < other.f\n",
        "\n",
        "    import heapq\n",
        "\n",
        "    maze = (\n",
        "        (0, 0, 0, 0, 0, 1),\n",
        "        (0, 0, 0, 1, 1, 0),\n",
        "        (0, 1, 0, 1, 1, 1),\n",
        "        (0, 1, 0, 0, 1, 0),\n",
        "        (0, 1, 0, 0, 1, 1),\n",
        "    )\n",
        "\n",
        "    # Initialize start and end nodes\n",
        "    start_node = Node(None, start)\n",
        "    end_node = Node(None, end)\n",
        "\n",
        "    open_heap = []\n",
        "    closed_set = set()\n",
        "    heapq.heappush(open_heap, start_node)\n",
        "\n",
        "    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # Move in four possible directions\n",
        "\n",
        "    while open_heap:\n",
        "        current_node = heapq.heappop(open_heap)\n",
        "\n",
        "        if current_node == end_node:\n",
        "            path = []\n",
        "            while current_node:\n",
        "                path.append(current_node.position)\n",
        "                current_node = current_node.parent\n",
        "            return path[::-1]\n",
        "\n",
        "        closed_set.add(current_node.position)\n",
        "\n",
        "        for direction in directions:\n",
        "            node_position = (current_node.position[0] + direction[0], current_node.position[1] + direction[1])\n",
        "\n",
        "            if 0 <= node_position[0] < len(maze) and 0 <= node_position[1] < len(maze[0]):\n",
        "                if maze[node_position[0]][node_position[1]] == 0:\n",
        "                    neighbor_node = Node(current_node, node_position)\n",
        "                    if neighbor_node.position in closed_set:\n",
        "                        continue\n",
        "\n",
        "                    neighbor_node.g = current_node.g + 1\n",
        "                    neighbor_node.h = (end_node.position[0] - node_position[0]) ** 2 + (end_node.position[1] - node_position[1]) ** 2\n",
        "                    neighbor_node.f = neighbor_node.g + neighbor_node.h\n",
        "\n",
        "                    if not any(open_node.position == neighbor_node.position and open_node.g <= neighbor_node.g for open_node in open_heap):\n",
        "                        heapq.heappush(open_heap, neighbor_node)\n",
        "\n",
        "    return None  # If no path is found\n",
        "\n",
        "# Example\n",
        "start = (0, 0)\n",
        "end = (4, 5)\n",
        "path = find_path_through_impossible_maze(start, end)\n",
        "print(\"Path:\", path if path else \"No path found\")\n"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Path: No path found\n"
          ]
        }
      ]
    }
  ]
}