{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "# Solving problems by Searching\n", "\n", "This notebook serves as supporting material for topics covered in **Chapter 3 - Solving Problems by Searching** and **Chapter 4 - Beyond Classical Search** from the book *Artificial Intelligence: A Modern Approach.* This notebook uses implementations from [search.py](https://github.com/aimacode/aima-python/blob/master/search.py) module. Let's start by importing everything from search module." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "scrolled": true }, "outputs": [], "source": [ "from search import *\n", "from notebook import psource, heatmap, gaussian_kernel, show_map, final_path_colors, display_visual, plot_NQueens\n", "\n", "# Needed to hide warnings in the matplotlib sections\n", "import warnings\n", "warnings.filterwarnings(\"ignore\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## CONTENTS\n", "\n", "* Overview\n", "* Problem\n", "* Node\n", "* Simple Problem Solving Agent\n", "* Search Algorithms Visualization\n", "* Breadth-First Tree Search\n", "* Breadth-First Search\n", "* Best First Search\n", "* Uniform Cost Search\n", "* Greedy Best First Search\n", "* A\\* Search\n", "* Hill Climbing\n", "* Simulated Annealing\n", "* Genetic Algorithm\n", "* AND-OR Graph Search\n", "* Online DFS Agent\n", "* LRTA* Agent" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## OVERVIEW\n", "\n", "Here, we learn about a specific kind of problem solving - building goal-based agents that can plan ahead to solve problems. In particular, we examine navigation problem/route finding problem. We must begin by precisely defining **problems** and their **solutions**. We will look at several general-purpose search algorithms.\n", "\n", "Search algorithms can be classified into two types:\n", "\n", "* **Uninformed search algorithms**: Search algorithms which explore the search space without having any information about the problem other than its definition.\n", " * Examples:\n", " 1. Breadth First Search\n", " 2. Depth First Search\n", " 3. Depth Limited Search\n", " 4. Iterative Deepening Search\n", "\n", "\n", "* **Informed search algorithms**: These type of algorithms leverage any information (heuristics, path cost) on the problem to search through the search space to find the solution efficiently.\n", " * Examples:\n", " 1. Best First Search\n", " 2. Uniform Cost Search\n", " 3. A\\* Search\n", " 4. Recursive Best First Search\n", "\n", "*Don't miss the visualisations of these algorithms solving the route-finding problem defined on Romania map at the end of this notebook.*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For visualisations, we use networkx and matplotlib to show the map in the notebook and we use ipywidgets to interact with the map to see how the searching algorithm works. These are imported as required in `notebook.py`." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "%matplotlib inline\n", "import networkx as nx\n", "import matplotlib.pyplot as plt\n", "from matplotlib import lines\n", "\n", "from ipywidgets import interact\n", "import ipywidgets as widgets\n", "from IPython.display import display\n", "import time" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## PROBLEM\n", "\n", "Let's see how we define a Problem. Run the next cell to see how abstract class `Problem` is defined in the search module." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "
\n", "class Problem(object):\n",
"\n",
" """The abstract class for a formal problem. You should subclass\n",
" this and implement the methods actions and result, and possibly\n",
" __init__, goal_test, and path_cost. Then you will create instances\n",
" of your subclass and solve them with the various search functions."""\n",
"\n",
" def __init__(self, initial, goal=None):\n",
" """The constructor specifies the initial state, and possibly a goal\n",
" state, if there is a unique goal. Your subclass's constructor can add\n",
" other arguments."""\n",
" self.initial = initial\n",
" self.goal = goal\n",
"\n",
" def actions(self, state):\n",
" """Return the actions that can be executed in the given\n",
" state. The result would typically be a list, but if there are\n",
" many actions, consider yielding them one at a time in an\n",
" iterator, rather than building them all at once."""\n",
" raise NotImplementedError\n",
"\n",
" def result(self, state, action):\n",
" """Return the state that results from executing the given\n",
" action in the given state. The action must be one of\n",
" self.actions(state)."""\n",
" raise NotImplementedError\n",
"\n",
" def goal_test(self, state):\n",
" """Return True if the state is a goal. The default method compares the\n",
" state to self.goal or checks for state in self.goal if it is a\n",
" list, as specified in the constructor. Override this method if\n",
" checking against a single self.goal is not enough."""\n",
" if isinstance(self.goal, list):\n",
" return is_in(state, self.goal)\n",
" else:\n",
" return state == self.goal\n",
"\n",
" def path_cost(self, c, state1, action, state2):\n",
" """Return the cost of a solution path that arrives at state2 from\n",
" state1 via action, assuming cost c to get up to state1. If the problem\n",
" is such that the path doesn't matter, this function will only look at\n",
" state2. If the path does matter, it will consider c and maybe state1\n",
" and action. The default method costs 1 for every step in the path."""\n",
" return c + 1\n",
"\n",
" def value(self, state):\n",
" """For optimization problems, each state has a value. Hill-climbing\n",
" and related algorithms try to maximize this value."""\n",
" raise NotImplementedError\n",
"
class Node:\n",
"\n",
" """A node in a search tree. Contains a pointer to the parent (the node\n",
" that this is a successor of) and to the actual state for this node. Note\n",
" that if a state is arrived at by two paths, then there are two nodes with\n",
" the same state. Also includes the action that got us to this state, and\n",
" the total path_cost (also known as g) to reach the node. Other functions\n",
" may add an f and h value; see best_first_graph_search and astar_search for\n",
" an explanation of how the f and h values are handled. You will not need to\n",
" subclass this class."""\n",
"\n",
" def __init__(self, state, parent=None, action=None, path_cost=0):\n",
" """Create a search tree Node, derived from a parent by an action."""\n",
" self.state = state\n",
" self.parent = parent\n",
" self.action = action\n",
" self.path_cost = path_cost\n",
" self.depth = 0\n",
" if parent:\n",
" self.depth = parent.depth + 1\n",
"\n",
" def __repr__(self):\n",
" return "<Node {}>".format(self.state)\n",
"\n",
" def __lt__(self, node):\n",
" return self.state < node.state\n",
"\n",
" def expand(self, problem):\n",
" """List the nodes reachable in one step from this node."""\n",
" return [self.child_node(problem, action)\n",
" for action in problem.actions(self.state)]\n",
"\n",
" def child_node(self, problem, action):\n",
" """[Figure 3.10]"""\n",
" next_state = problem.result(self.state, action)\n",
" next_node = Node(next_state, self, action,\n",
" problem.path_cost(self.path_cost, self.state,\n",
" action, next_state))\n",
" return next_node\n",
" \n",
" def solution(self):\n",
" """Return the sequence of actions to go from the root to this node."""\n",
" return [node.action for node in self.path()[1:]]\n",
"\n",
" def path(self):\n",
" """Return a list of nodes forming the path from the root to this node."""\n",
" node, path_back = self, []\n",
" while node:\n",
" path_back.append(node)\n",
" node = node.parent\n",
" return list(reversed(path_back))\n",
"\n",
" # We want for a queue of nodes in breadth_first_graph_search or\n",
" # astar_search to have no duplicated states, so we treat nodes\n",
" # with the same state as equal. [Problem: this may not be what you\n",
" # want in other contexts.]\n",
"\n",
" def __eq__(self, other):\n",
" return isinstance(other, Node) and self.state == other.state\n",
"\n",
" def __hash__(self):\n",
" return hash(self.state)\n",
"
class GraphProblem(Problem):\n",
"\n",
" """The problem of searching a graph from one node to another."""\n",
"\n",
" def __init__(self, initial, goal, graph):\n",
" Problem.__init__(self, initial, goal)\n",
" self.graph = graph\n",
"\n",
" def actions(self, A):\n",
" """The actions at a graph node are just its neighbors."""\n",
" return list(self.graph.get(A).keys())\n",
"\n",
" def result(self, state, action):\n",
" """The result of going to a neighbor is just that neighbor."""\n",
" return action\n",
"\n",
" def path_cost(self, cost_so_far, A, action, B):\n",
" return cost_so_far + (self.graph.get(A, B) or infinity)\n",
"\n",
" def find_min_edge(self):\n",
" """Find minimum value of edges."""\n",
" m = infinity\n",
" for d in self.graph.graph_dict.values():\n",
" local_min = min(d.values())\n",
" m = min(m, local_min)\n",
"\n",
" return m\n",
"\n",
" def h(self, node):\n",
" """h function is straight-line distance from a node's state to goal."""\n",
" locs = getattr(self.graph, 'locations', None)\n",
" if locs:\n",
" if type(node) is str:\n",
" return int(distance(locs[node], locs[self.goal]))\n",
"\n",
" return int(distance(locs[node.state], locs[self.goal]))\n",
" else:\n",
" return infinity\n",
"